1.
In linked lists there are no NULL links in
Correct Answer
C. Circular linked list
Explanation
In a circular linked list, there are no NULL links because the last node in the list points back to the first node, creating a circular structure. This means that every node in the list has a non-NULL link, as there is no end point or termination point in the list. This is different from single linked lists and linear doubly linked lists, where the last node points to NULL to indicate the end of the list. Therefore, the correct answer is Circular linked list.
2.
In a stack the command to access nth element from the top of the stack S will be
Correct Answer
A. S [Top-n]
Explanation
The correct answer is S [Top-n]. This is because in a stack, the top element is the last element that was inserted, and the elements below it are accessed by decrementing the index from the top. So, to access the nth element from the top, we need to subtract n from the top index.
3.
If yyy, xxx and zzz are the elements of a lexically ordered binary tree, then in preorder traversal which node will be traverse first
Correct Answer
A. Xxx
Explanation
In a lexical ordering binary tree, the nodes are arranged in alphabetical or numerical order. In a preorder traversal, the root node is visited first, followed by the left subtree, and then the right subtree. Since "xxx" is the first element in the given list, it will be the first node to be traversed in a preorder traversal of the binary tree.
4.
In a balance binary tree the height of two sub trees of every node can not differ by more than
Correct Answer
B. 1
Explanation
In a balanced binary tree, the height of two sub trees of every node cannot differ by more than 1. This means that the heights of the left and right sub trees of any node in the tree can be at most 1 level apart. If the difference in height exceeds 1, then the tree is considered unbalanced. Therefore, the correct answer is 1.
5.
The result of evaluating prefix expression */b+0dacd, where a=3, b=6, c=1, d=5 is
Correct Answer
C. 10
Explanation
The given prefix expression is */b+0dacd. To evaluate this expression, we substitute the values of a, b, c, and d with their given values (a=3, b=6, c=1, d=5). The expression becomes */6+0*3*1*5. We perform the multiplication first, which gives us 0. Then we perform the addition, which gives us 6. Finally, we perform the multiplication with the remaining division operation, which gives us 10. Therefore, the result of evaluating the prefix expression is 10.
6.
In array representation of binary tree teh right child of root will be at location of
Correct Answer
C. 3
Explanation
In the array representation of a binary tree, the right child of the root will be at location 3. This is because in a binary tree, the left child is typically stored at index 2*i+1 and the right child is stored at index 2*i+2, where i is the index of the parent node. In this case, the root is at index 0, so the right child would be at index 2*0+2 = 2. Therefore, the correct answer is 3.
7.
The total number of comparisons in a bubble sort is
Correct Answer
A. O(n logn)
Explanation
The correct answer is O(n2). In bubble sort, each element is compared with its adjacent element and swapped if they are in the wrong order. This process is repeated for all elements in the list. In the worst case scenario, where the list is in reverse order, each element needs to be compared with every other element, resulting in n(n-1)/2 comparisons. This simplifies to O(n2) time complexity. The other options, O(n logn) and O(2n), do not accurately represent the time complexity of bubble sort.
8.
IThe dummy header in linked list contain
Correct Answer
A. First record of the actual data
Explanation
The dummy header in a linked list is a special node that is used to simplify the implementation of certain operations. It does not contain any actual data, but it serves as a placeholder or sentinel node. In this case, the dummy header contains the first record of the actual data. This allows for easier traversal and manipulation of the linked list, as the dummy header provides a starting point for accessing the actual data nodes.
9.
Write the output of following program:int a[ ] = {1,2,3,} *p;
Correct Answer
B. Junk value
Explanation
The given program declares an integer array "a" with three elements and declares a pointer variable "p". However, the pointer variable "p" is not initialized and does not point to any valid memory location. Therefore, when the program tries to dereference the pointer and access the value it points to, it will result in undefined behavior. In this case, it will lead to a junk value being printed as the output.
10.
If the out degree of every node is exactly equal to M or 0 and the num ber of nodes at level K is Mk-1 [con sider root at level 1], then tree is called as (i) Full m-ary try(ii) Com plete m-ary tree(iii)Positional m-ary tree
Correct Answer
C. Both (i) and (ii)
Explanation
A tree where the out degree of every node is exactly equal to M or 0 and the number of nodes at level K is Mk-1 is called a Full m-ary tree. This is because in a Full m-ary tree, each node has exactly M children or no children, and the number of nodes at each level follows the pattern of Mk-1. Additionally, this type of tree can also be called a Complete m-ary tree because it is a special case of a complete tree where all levels are completely filled except possibly the last level, which is filled from left to right. Therefore, the correct answer is Both (i) and (ii).
11.
In the following tree:
If post order traversal generates sequence xy-zw*+, then label of nodes 1,2,3,4,5,6,7 will be
Correct Answer
A. +, -, *, x, y, z, w
Explanation
The given post-order traversal sequence "xy-zw*+" indicates that the left subtree of the root node contains the operands "x" and "y", and the right subtree contains the operands "z" and "w". The root node itself represents the operator "+". Therefore, the labels of the nodes 1, 2, 3, 4, 5, 6, 7 will be "+, -, *, x, y, z, w".
12.
If the following tree is used for sorting then a new number 10 should be placed at
Correct Answer
C. Left child of node labeled 14
Explanation
The given question is asking where a new number 10 should be placed in a tree used for sorting. The correct answer is the left child of the node labeled 14. This means that the new number 10 should be inserted as a left child of the node labeled 14 in the tree.
13.
A queue has configuration a,b,c,d. To get configuration d,c,b,a. One needs a minimum of
Correct Answer
C. 3 deletions and 3 additions
Explanation
To get from configuration a,b,c,d to configuration d,c,b,a, we need to perform the following operations:
1. Delete a
2. Delete b
3. Delete c
4. Add d
5. Add c
6. Add b
Therefore, we need a minimum of 3 deletions and 3 additions.
14.
Number of possible ordered trees with 3 nodes A,B,C is
Correct Answer
C. 6
Explanation
The number of possible ordered trees with 3 nodes A, B, and C can be determined by considering all the possible arrangements of the nodes. In this case, there are 6 possible arrangements: A as the root with B and C as its children, B as the root with A and C as its children, C as the root with A and B as its children, A as the root with B as its child and C as its grandchild, B as the root with A as its child and C as its grandchild, and C as the root with A as its child and B as its grandchild. Therefore, the correct answer is 6.
15.
Number of swapping, operations need to sort numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort
Correct Answer
C. 13
Explanation
The given answer, 13, represents the number of swapping operations needed to sort the given numbers in ascending order using bubble sort. Bubble sort works by repeatedly swapping adjacent elements if they are in the wrong order. In this case, it would take 13 swapping operations to sort the numbers 8, 22, 7, 9, 31, 19, 5, and 13 in ascending order.
16.
Consider two sorted lists of size L1, L2. Number of comparisions needed in worst case my merge sort algorithm will be
Correct Answer
D. L1+L2-1
Explanation
The merge sort algorithm works by dividing the given list into smaller sublists, sorting them, and then merging them back together. In the worst case scenario, the algorithm will need to compare each element in both lists before merging them. Since the two lists are already sorted, the maximum number of comparisons needed will be equal to the total number of elements in both lists minus one (to account for the last comparison). Therefore, the correct answer is L1+L2-1.
17.
A hash tabale with 10 buckets with one slot per bucket is depicted in following diagram. Symbols S1 to S7 are initially entered using a hashing function with linear probing. Maximum number of comparisions needed in searching an item that is not present is
Correct Answer
B. 5
Explanation
In a hash table with linear probing, when an item is inserted, if its hash value leads to a collision, the next available slot in the table is checked. In this case, symbols S1 to S7 are initially entered using linear probing. To search for an item that is not present in the hash table, the hash value is calculated and the corresponding slot is checked. If the item is not found, the next slot is checked, and so on. The maximum number of comparisons needed to search for an item that is not present in this specific hash table is 5.
18.
Following sequence of operation is performed on a stack. Push(1), Push(2), Pop, Push(1), Push(2), Pop, Pop, Pop, Push(2), Pop. The sequences of popped out values are
Correct Answer
D. 2,1,2,2,2
19.
A binary tree in which every non-leaf node has non-empty left and right sub trees is called a strictly binary tree. Such a tree with 10 leaves
Correct Answer
A. Has 19 nodes
Explanation
A strictly binary tree is defined as a binary tree where every non-leaf node has both a non-empty left and right subtree. In this case, the tree has 10 leaves, which means there are 10 nodes that do not have any children. Since every non-leaf node has two children, there must be 10 - 1 = 9 non-leaf nodes. Therefore, the total number of nodes in the tree is 10 + 9 = 19.
20.
Depth of a binary tree with n node is
Correct Answer
A. Log (n +1) - 1
Explanation
The correct answer is log (n +1) - 1. This is because the depth of a binary tree is determined by the maximum number of edges from the root to a leaf node. In a binary tree with n nodes, the maximum number of edges from the root to a leaf node is n-1. Taking the logarithm of n+1 and subtracting 1 gives us the depth of the binary tree.
21.
To arrange a binary tree in ascending order we need
Correct Answer
B. Inorder traversal
Explanation
Inorder traversal is used to arrange a binary tree in ascending order because it visits the left subtree first, then the root, and finally the right subtree. This order ensures that the values in the tree are visited in ascending order.
22.
Average successful search time taken by binary search on sorted array of 10 items is
Correct Answer
D. 2.9
Explanation
The average successful search time taken by binary search on a sorted array of 10 items is 2.9. This means that, on average, it takes 2.9 units of time to find a specific item in the array using binary search. Binary search is an efficient search algorithm that divides the search space in half with each comparison, making it faster than linear search for sorted arrays.
23.
Hash function f is defined as f(key) = key mod 7. If linear probing is used to insert the key 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6, 11 will be stored at the location
Correct Answer
C. 5
Explanation
The hash function f(key) = key mod 7 will map the keys to the indices in the range of 0 to 6. When linear probing is used, if a collision occurs, the next available index is checked until an empty slot is found.
In this case, when inserting the keys 37, 38, 72, 48, 98, 11, and 56, the index for the key 11 will be determined.
Since f(11) = 11 mod 7 = 4, the initial index for 11 is 4. However, this index is already occupied by the key 48.
Using linear probing, the next available index is checked, which is 5. Therefore, the key 11 will be stored at index 5.
24.
Average successful search time for sequential search on 'n' item is
Correct Answer
C. (n+1)/2
Explanation
The average successful search time for sequential search on 'n' items is (n+1)/2. This is because in a sequential search, each item in the list is checked one by one until the desired item is found. On average, the desired item will be found in the middle of the list, which is at position (n+1)/2. Therefore, the average successful search time is (n+1)/2.
25.
Running time of an algorithm T(n), where n is input size is given by T(n) = 8 T(n/2) + qn, if n>1 T(n) = p, if, n=1 where p and q are constants. The order of algorithm is
Correct Answer
C. N^{3}
Explanation
The given algorithm has a recursive formula T(n) = 8 T(n/2) + qn, which indicates that the algorithm divides the input size by 2 in each recursive step. This suggests a divide and conquer approach. Additionally, the algorithm has a linear term qn, indicating that there is a linear operation performed at each step. Based on this information, we can conclude that the algorithm has a time complexity of O(n^3), as the recursive steps will result in a logarithmic factor of O(log n), and the linear term will contribute to the overall time complexity.
26.
6 files X1, X2, X3, X4, X5, X6 have 150, 250, 55, 85, 125, 175 number of records respectively. The order of storage ot optimize access time is
Correct Answer
A. X1, X2, X3, X4, X5, X6
Explanation
The order of storage to optimize access time is X1, X2, X3, X4, X5, X6. This is because the files are ordered in increasing order of the number of records they have. By storing the files with fewer records first, it allows for quicker access to those files. Storing the files with more records towards the end minimizes the need to search through a larger number of records, thus optimizing access time.
27.
In above question average access time will be
Correct Answer
B. 140
Explanation
The average access time will be 140. This is because the average is calculated by adding up all the access times and then dividing by the total number of access times. In this case, there are three access times given: 150, 140, and 55. Adding these together gives a total of 345. Dividing this by the total number of access times (3) gives an average of 115. Therefore, the correct answer is 140.
28.
An algorithm consists of two modules X1, X2. Their order is f(n) and g(n), respectively. The order of algorithm is
Correct Answer
A. Max(f(n),g(n))
Explanation
The order of an algorithm is determined by the module with the highest order. In this case, since we are comparing the orders of modules X1 and X2, the order of the algorithm will be the maximum of f(n) and g(n).
29.
Bib O notation w.r.t algorithm signifies
Correct Answer
D. None of the above
30.
Running time T(n), where 'n' is input size of recursive algorithm is given as follows:T(n) = c + T(n-1), if n>1,T(n) = d if n<1. The order of algorithm is
Correct Answer
B. N
Explanation
The given recursive algorithm has a running time of T(n) = c + T(n-1) if n>1 and T(n) = d if n
31.
Four altorithm A1, A2, A3, A4 solves a problem with order log(n), log log(n), nlog(n), n. Which is best algorithm
Correct Answer
A. A1
Explanation
The best algorithm among A1, A2, A3, and A4 is A1. This is because the order of A1 is log(n), which is the smallest among the given options. A logarithmic time complexity indicates that the algorithm's performance improves as the input size increases, making it more efficient than the other algorithms with higher time complexities.
32.
Time complexity of an algorithm T(n), where n is the input size is given by T(n) = T (n-1) + 1/n, if n>1 otherwise T(n) = 1. The order of algorithm is
Correct Answer
C. N^{2}
Explanation
The given algorithm has a recurrence relation T(n) = T(n-1) + 1/n, which means that the time complexity of the algorithm is determined by the sum of 1/n for each value of n. As n increases, the sum of 1/n will approach the value of the harmonic series, which is known to be O(log n). However, since we are asked to give the order of the algorithm, we use the Big O notation, which ignores constant factors. Therefore, the order of the algorithm is n^2.
33.
Which of the following is correct
Correct Answer
B. External sorting is used, if number of items to be sorted is very large
Explanation
External sorting is used when the number of items to be sorted is very large. This is because external sorting involves storing and manipulating data on external storage devices such as hard drives, which have larger storage capacity compared to internal memory. On the other hand, internal sorting is used when the number of items to be sorted can fit into the available internal memory. External sorting requires auxiliary storage because it involves reading and writing data to external storage devices, while internal sorting may or may not require auxiliary storage depending on the algorithm used.
34.
A sorting technique which guarrantees that records with same primary key occurs in the sorted list as in the original unsorted list is said to be
Correct Answer
A. Stable
Explanation
A sorting technique that is stable ensures that records with the same primary key will appear in the same order in the sorted list as they did in the original unsorted list. In other words, if there are two records with the same primary key, the one that appeared first in the unsorted list will also appear first in the sorted list. This property is important in certain applications where the original order of equal elements needs to be preserved.
35.
A text is made up of five characters, T1, T2, T3, T4, T5. The probability of occurance of each character is .12, .4, .15, .88 and .25, respectively. The optimal coding technique will have average length of
Correct Answer
A. 2.15
Explanation
The optimal coding technique will have an average length of 2.15. This can be calculated by multiplying each character's probability with its corresponding length in bits and summing them all up. The calculation would be: (0.12 * 2) + (0.4 * 3) + (0.15 * 2) + (0.88 * 1) + (0.25 * 3) = 0.24 + 1.2 + 0.3 + 0.88 + 0.75 = 3.37. Since the average length is 3.37 bits, it is rounded down to 2.15 bits.
36.
If running time of an algorithm is given by T(n) = T(n-1) + T(n-2) + T(n-3), if n>3 otherwise T(n)=n, what should be relation between T(1), T(2), T(3) where algorithm order become constant
Correct Answer
C. T(1) - T(3) = T(2)
Explanation
The given algorithm has a recursive formula for the running time, where T(n) is equal to the sum of the running times of the previous three inputs. However, when n is less than or equal to 3, the running time is equal to n.
To find the relation between T(1), T(2), and T(3) where the algorithm's order becomes constant, we can substitute the values into the recursive formula.
When n = 1, T(1) = T(1-1) + T(1-2) + T(1-3) = T(0) + T(-1) + T(-2) = 0 + 0 + 0 = 0.
Similarly, when n = 2, T(2) = T(2-1) + T(2-2) + T(2-3) = T(1) + T(0) + T(-1) = 0 + 0 + 0 = 0.
And when n = 3, T(3) = T(3-1) + T(3-2) + T(3-3) = T(2) + T(1) + T(0) = 0 + 0 + 0 = 0.
Therefore, T(1) - T(3) = T(2), which is the correct answer.
37.
Arranging a pack of cards by picking one by one is an example of
Correct Answer
C. Insertion sort
Explanation
Arranging a pack of cards by picking one by one is an example of insertion sort. In insertion sort, each element is compared to the elements before it and inserted into its correct position in the sorted portion of the array. Similarly, when arranging a pack of cards, we compare each card to the cards already sorted and insert it into the correct position. This process continues until all the cards are in the correct order.
38.
In evaluating arithmatic expression 2*3-(4+5) using postfix stack form. Which of the following stack configuration is not possible
Correct Answer
D. ------------
| 9 | 3 | 2 |
------------
39.
The order of an algorithm that finds whether a given boolean function of 'n' variable produces a '1' is
Correct Answer
D. Exponential
Explanation
The order of an algorithm that finds whether a given boolean function of 'n' variable produces a '1' is exponential. This means that the time complexity of the algorithm grows exponentially with the size of the input. In other words, as the number of variables increases, the time taken by the algorithm to determine the output also increases exponentially. This indicates that the algorithm is not efficient and may not be suitable for large inputs.
40.
The average number of comparisions performed by merge sort alrotithm in merging two sorted list of length 2 is
Correct Answer
A. 8/3
Explanation
The merge sort algorithm divides the list into two halves recursively until each half contains only one element. Then, it merges the two halves by comparing the elements and placing them in sorted order. In this case, we have two sorted lists of length 2. When merging two sorted lists of length 2, a total of 8 comparisons are performed. Therefore, the average number of comparisons performed by merge sort algorithm in merging two sorted lists of length 2 is 8/3.
41.
To arrange the books of library the best method is
Correct Answer
D. Heap sort
Explanation
Heap sort is the best method to arrange the books in the library because it is an efficient sorting algorithm with a time complexity of O(n log n). It works by creating a binary heap data structure and then repeatedly removing the largest element from the heap and placing it at the end of the sorted array. This process continues until all elements are sorted. Heap sort has good performance characteristics and is suitable for large datasets, making it an ideal choice for arranging books in a library.
42.
Which of the following algorithm has n log (n) time complexity
Correct Answer
C. Insertion sort
Explanation
Insertion sort has a time complexity of n * log(n) because it iterates through the input array and for each element, it compares it with the previous elements and inserts it in the correct position. This process requires log(n) comparisons on average for each element, resulting in a total time complexity of n * log(n). On the other hand, heap sort and quick sort have a time complexity of n * log(n), while selection sort has a time complexity of n^2.
43.
Which algorithm solves all pair shortest path problem
Correct Answer
A. Dijkastra's algorithm
Explanation
Dijkstra's algorithm is used to find the shortest path between a source node and all other nodes in a weighted graph. It does not solve the all pair shortest path problem, which aims to find the shortest path between all pairs of nodes in a graph. Floyd's algorithm, on the other hand, is specifically designed to solve the all pair shortest path problem. Therefore, Dijkstra's algorithm is not the correct answer for this question.
44.
The centricity of node labeled 5 is
Correct Answer
C. 2
Explanation
The centricity of a node refers to the minimum eccentricity among all the nodes in the graph. The eccentricity of a node is the maximum distance between that node and any other node in the graph. In this case, the node labeled 5 has a direct connection to itself, which means its eccentricity is 0. Among all the nodes in the graph, the minimum eccentricity is 0, so the centricity of node labeled 5 is 0.
45.
The information about an array used in a program will be stored in
Correct Answer
B. Dope vector
Explanation
A dope vector is a data structure used to store information about an array in a program. It typically contains details such as the size of the array, the starting address, and other relevant information. This allows the program to access and manipulate the array efficiently. The symbol table is used to store information about variables and their associated values. The register vector is used to keep track of which registers are currently in use. The activation table is used to manage the activation records of function calls. Therefore, the correct answer for storing information about an array in a program is the dope vector.
46.
In which of the following cases linked list implementaion of sparse matrices consumes same memory as a normal array
Correct Answer
C. 6 x 5 matrix with 8 non-zero entries
Explanation
In a linked list implementation of a sparse matrix, memory is only allocated for the non-zero entries. So, the memory consumption depends on the number of non-zero entries in the matrix. In this case, a 6 x 5 matrix with 8 non-zero entries would consume the same memory as a normal array because both would require memory for 8 elements.
47.
The advantage of sparse matrix linked list representationn over dope vector method is, that the former is
Correct Answer
B. Completely dynamic
Explanation
The advantage of the sparse matrix linked list representation over the dope vector method is that it is completely dynamic. This means that the linked list representation can handle matrices of any size and shape, while the dope vector method requires pre-allocation of memory for all possible entries in the matrix. The linked list representation only stores the non-zero elements, making it more memory-efficient for sparse matrices. Additionally, the linked list representation allows for efficient insertion and deletion of elements, as it only requires updating the relevant pointers.
48.
If the address of (I,J)th entry, in dope vector representation, where it stores the position of first and last non-zero entries of each row is given by C, assume l(n) and f(n) represent the last and first non-zero entries in row xi. ii. iii. iv.
Correct Answer
C. Correct answer is (iii)
49.
On which principle does stack work?
Correct Answer
A. FILO
Explanation
The stack works on the principle of FILO, which stands for "First In, Last Out." This means that the first item inserted into the stack will be the last one to be removed. In other words, the most recently added item will always be the first one to be accessed or removed from the stack. This principle is commonly used in programming and data structures, where stacks are used to store and retrieve data in a specific order.
50.
The order of binary search algorithm is
Correct Answer
C. N log n
Explanation
The order of the binary search algorithm is n log n. This means that the time complexity of the algorithm is proportional to the logarithm of the input size (n) multiplied by the input size itself. In other words, as the input size increases, the time taken by the algorithm increases at a slower rate. This is because binary search divides the input size in half at each step, making it more efficient than linear search. Therefore, the correct answer is n log n.