1.
In linked lists there are no NULL links in
Correct Answer
C. Circular linked list
Explanation
Circular linked lists do not have NULL links because the last node of the list points back to the first node, creating a circular structure. This allows for easy traversal of the list and eliminates the need for NULL pointers to indicate the end of the 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
To access the nth element from the top of the stack S, the command would be S [Top-n]. This is because the top of the stack is considered as the 1st element, and to access the nth element from the top, we need to subtract n from the top index. Therefore, the correct command would be S [Top-n].
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 preorder traversal of a binary tree, the root node is always traversed first, followed by the left subtree and then the right subtree. Therefore, in this case, the node "xxx" will be traversed first in the preorder traversal.
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 the two sub trees of every node cannot differ by more than 1. This means that the heights of the left and right sub trees should either be equal or differ by at most 1. This balance ensures efficient search and insertion operations in the tree. If the height difference is more than 1, the tree becomes unbalanced, leading to slower operations. 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. Plugging in the values of a=3, b=6, c=1, d=5, we get */6+0*3*1+5. Following the order of operations, we first evaluate the multiplication and division from left to right. So, we have 6/6+0*3*1+5. Next, we evaluate the addition and subtraction from left to right. So, we have 1+0*3*1+5. Finally, we evaluate the remaining multiplication. So, we have 1+0+5. Simplifying further, we get 6 as the final result. Therefore, the correct answer 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 the location of 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 represents 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(n^2). In bubble sort, each element is compared with its adjacent element and swapped if necessary. This process is repeated for each element in the list, resulting in n comparisons for each pass. Since there are n passes in total, the total number of comparisons is n * n = n^2.
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 certain operations on the list. It does not contain any actual data, but it serves as a placeholder or starting point for the list. The first record of the actual data is stored after the dummy header, so it can be accessed easily. Therefore, the correct answer is "First record of the actual data."
9.
Write the output of following program:int a[ ] = {1,2,3,} *p;
Correct Answer
B. Junk value
Explanation
The program is trying to assign the value of the third element of the array 'a' to a pointer variable 'p'. However, there is no reference to the address of the array 'a' in the code. Therefore, the pointer 'p' does not point to any valid memory location and will contain a junk value.
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 is called a full m-ary tree. This means that each node in the tree has either M children or no children at all. On the other hand, a tree where the number of nodes at level K is Mk-1 is called a complete m-ary tree. This means that each level of the tree is completely filled, except possibly for the last level which may be partially filled. Therefore, the given tree satisfies the conditions for both a full m-ary tree and a complete m-ary tree, making the answer "Both (i) and (ii)" correct.
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*+" suggests that the label of the nodes in the tree is +, -, *, x, y, z, w. This means that the node labeled 1 is "+", node 2 is "-", node 3 is "*", node 4 is "x", node 5 is "y", node 6 is "z", and node 7 is "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 answer states that the new number 10 should be placed as the left child of the node labeled 14. This means that the number 10 should be inserted as a lower value than 14 in the tree hierarchy. Placing it as the left child ensures that it is on the left side of the node labeled 14 and has a lower value.
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 to get b,c,d.
2. Delete b to get c,d.
3. Delete c to get d.
4. Add a to get d,a.
5. Add b to get d,a,b.
6. Add c to get d,a,b,c.
Therefore, we need 3 deletions and 3 additions to achieve the desired configuration.
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, C can be determined by considering the different ways these nodes can be arranged. In this case, there are 3 nodes, so there are 3 choices for the root node. After selecting the root node, there are 2 remaining nodes that can be arranged in 2! = 2 ways. Therefore, the total number of possible ordered trees is 3 * 2 = 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
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. In this case, the given numbers are 8, 22, 7, 9, 31, 19, 5, and 13. To sort them in ascending order using bubble sort, the algorithm will make a total of 13 swaps.
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 input into smaller sublists, sorting them, and then merging them back together. In the worst case scenario, the algorithm will need to compare every element in both lists before merging them. Since there are L1 elements in the first list and L2 elements in the second list, the total number of comparisons needed will be L1 + L2. However, when merging the lists, the last element of the first list will already be in its correct position, so it does not need to be compared again. Therefore, the final 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 searching for an item that is not present, we need to check each slot in the hash table until we either find the item or reach an empty slot. In this case, since there are 10 buckets with one slot per bucket, the maximum number of comparisons needed to search for an item that is not present would be equal to the number of slots in the hash table, which is 10. However, since the answer given is 5, there might be some additional information or context missing from the question that would explain why the correct answer 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
Explanation
The given sequence of operations on the stack can be broken down as follows:
- Push(1) - The value 1 is pushed onto the stack.
- Push(2) - The value 2 is pushed onto the stack.
- Pop - The topmost value on the stack (2) is popped out.
- Push(1) - The value 1 is pushed onto the stack.
- Push(2) - The value 2 is pushed onto the stack.
- Pop - The topmost value on the stack (2) is popped out.
- Pop - The topmost value on the stack (1) is popped out.
- Pop - The topmost value on the stack (1) is popped out.
- Push(2) - The value 2 is pushed onto the stack.
- Pop - The topmost value on the stack (2) is popped out.
Therefore, the sequence of popped out values is 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 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 must have both a left and right subtree, there must be 10 non-leaf nodes in addition to the 10 leaves. Therefore, the total number of nodes in the tree is 10 leaves + 10 non-leaf nodes = 20 nodes. However, the question states that the tree has 19 nodes, which is incorrect.
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 can be calculated using the formula log (n +1) - 1, where n represents the number of nodes in the tree. This formula is derived from the fact that the maximum number of nodes at any level in a binary tree is 2^k, where k is the level number. By solving for k in the equation 2^k = n, we can find the depth of the 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 traversal ensures that the nodes are visited in ascending order, making it suitable for arranging the binary tree 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 desired element in the array using binary search. Binary search is an efficient search algorithm that works by repeatedly dividing the search space in half, making it very fast for sorted arrays. In this case, the average time is 2.9, indicating that it is slightly slower than the other options provided.
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
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 is expected to be found halfway through the list, so the average 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 that indicates the running time of the algorithm. The formula T(n) = 8 T(n/2) + qn suggests that each recursive call has a running time of qn, and the algorithm makes 8 recursive calls with input size n/2. This indicates that the algorithm has a divide and conquer approach, where it divides the problem into smaller subproblems and solves them recursively.
By analyzing the formula, we can see that the algorithm has a time complexity of O(n^3). This is because each recursive call contributes a factor of qn, and there are a total of log(n) recursive calls (since n is halved in each call). Therefore, the total running time can be expressed as qn * log(n), which simplifies to O(n^3) when we drop the constant factors.
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 order is based on the number of records in each file, with the file with the highest number of records (X2) being stored first and the file with the lowest number of records (X3) being stored last. By storing the files in this order, the system can prioritize accessing the files with more records first, which can potentially reduce access time and improve efficiency.
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 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 3 (the number of access times) 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 that takes the longest time to execute. In this case, the algorithm consists of two modules, X1 and X2, with orders f(n) and g(n) respectively. The order of the algorithm will be the maximum of f(n) and g(n) because the algorithm's overall performance will be limited by whichever module takes longer to execute. Therefore, the correct answer is Max(f(n),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), where c is a constant. This means that for each input size n, the algorithm performs a constant amount of work (c) plus the running time for the input size n-1. Since the algorithm only performs a constant amount of work for each input size, the order of the algorithm is linear, or O(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
Algorithm A1 is the best algorithm because it has the lowest time complexity of O(log(n)). This means that as the input size increases, the time taken by A1 to solve the problem will increase at a slower rate compared to the other algorithms. A2 has a time complexity of O(log log(n)), A3 has a time complexity of O(n log(n)), and A4 has a time complexity of O(n). Therefore, A1 is the most efficient algorithm for solving the given problem.
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 recursive formula where the time complexity of T(n) is equal to T(n-1) plus 1/n. This means that for every input size n, the algorithm will make a recursive call on an input size of n-1, and also perform a constant amount of work (1/n). As the input size decreases by 1 with each recursive call, the algorithm will have a total of n recursive calls. Therefore, the time complexity can be calculated as follows: T(n) = T(n-1) + 1/n = T(n-2) + 1/(n-1) + 1/n = ... = T(1) + 1/2 + 1/3 + ... + 1/n. This is known as the harmonic series, and it grows as O(log n). However, since the algorithm also performs a constant amount of work (1) in each recursive call, the overall time complexity becomes O(n + log n) which simplifies to O(n). Therefore, the order of the algorithm is n, not n^2 or any other option.
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 because it is not feasible to fit all the items in the main memory. External sorting involves dividing the data into smaller chunks that can fit in the memory, sorting each chunk individually, and then merging the sorted chunks together. This process requires the use of auxiliary storage, such as disk space, to store the intermediate sorted chunks. In contrast, internal sorting is used when the number of items can fit in the main memory, eliminating the need for auxiliary storage.
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 considered 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. This means that if two records have the same primary key value, 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 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 the probability of each character by the length of its corresponding code and summing up these values. For character T1, the length is 2, so the contribution to the average length is 0.12 * 2 = 0.24. Similarly, for T2, the length is 3, so the contribution is 0.4 * 3 = 1.2. For T3, the length is 2, so the contribution is 0.15 * 2 = 0.3. For T4, the length is 1, so the contribution is 0.88 * 1 = 0.88. And for T5, the length is 3, so the contribution is 0.25 * 3 = 0.75. Adding up all these contributions gives 0.24 + 1.2 + 0.3 + 0.88 + 0.75 = 3.37. Dividing this sum by the total probability (0.12 + 0.4 + 0.15 + 0.88 + 0.25 = 1.8) gives the average length of 2.15.
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 relation T(n) = T(n-1) + T(n-2) + T(n-3) suggests that the running time of the algorithm is dependent on the sum of the running times of the previous three iterations. Therefore, in order for the algorithm order to become constant, the running times of T(1), T(2), and T(3) should be related in such a way that the difference between T(1) and T(3) is equal to T(2). This can be represented as T(1) - T(3) = T(2).
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 because in insertion sort, each element is compared to the elements before it and inserted into its correct position in the sorted sequence. Similarly, when arranging a pack of cards, we compare each card to the cards before it and insert it into the correct position in the sorted sequence.
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' variables produces a '1' is exponential. This means that the time complexity of the algorithm increases exponentially with the size of the input. In other words, as the number of variables increases, the algorithm's running time grows at an exponential rate. This suggests that the algorithm may need to evaluate all possible combinations of inputs in order to determine the output, resulting in an exponential time complexity.
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
Merge sort algorithm divides the list into two halves and recursively sorts them. In the merging step, it compares the elements from both halves and merges them in sorted order. When merging two sorted lists of length 2, there are a total of 4 elements to compare. The first element from one list is compared with the first element from the other list, and similarly for the second element. Therefore, a total of 4 comparisons are performed. Since the question asks for the average number of comparisons, we divide 4 by the number of lists being merged, which is 2. Hence, the average number of comparisons performed is 4/2 = 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 a library. Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It has a time complexity of O(n log n), which means it is efficient for large datasets. Additionally, heap sort is an in-place sorting algorithm, which means it does not require any additional space for sorting. Therefore, heap sort is the most suitable method for arranging books in a library efficiently.
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 O(n log n). This is because in the worst case scenario, each element needs to be compared with all the previous elements in the sorted portion of the array, resulting in a nested loop. The outer loop iterates n times, and the inner loop iterates i times, where i is the current position of the element being inserted. As a result, the time complexity of insertion sort is n * (n/2) = O(n^2). However, in the best case scenario where the array is already sorted, the time complexity reduces to O(n), making it more efficient.
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 single source node and all other nodes in a graph. It does not solve the all pair shortest path problem. On the other hand, Floyd's algorithm is specifically designed to solve the all pair shortest path problem. It finds the shortest path between all pairs of nodes in a weighted graph, making it the correct answer to the question. Prim's algorithm is used for finding the minimum spanning tree in a graph, and Worshall's algorithm is used to find the transitive closure of a directed graph.
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 nodes in the graph. The eccentricity of a node is the maximum shortest path length from that node to any other node in the graph. In this case, the node labeled 5 has a shortest path length of 2 to itself, which is the minimum among all nodes in the graph. Therefore, the centricity of node labeled 5 is 2.
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 contains details such as the size of the array, the starting address of the array, and other relevant information. This information is used by the program to perform operations on the array efficiently. The symbol table, register vector, and activation table are not specifically designed to store array information, making them incorrect choices.
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 consumption is reduced because only the non-zero elements are stored. The number of non-zero entries determines the memory consumption. In this case, the 6 x 5 matrix with 8 non-zero entries would consume the same memory as a normal array because both would need to allocate space for 8 elements. The other options have either more or fewer non-zero entries, resulting in different memory consumption compared to a normal array.
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 sparse matrix linked list representation over the dope vector method is that the former is completely dynamic. This means that the linked list representation can handle matrices of any size, with varying numbers of non-zero entries, without requiring any additional memory allocation. In contrast, the dope vector method requires pre-allocation of memory for the entire matrix, which can be inefficient if the matrix is large or if the number of non-zero entries is small. Therefore, the completely dynamic nature of the sparse matrix linked list representation makes it a more flexible and efficient option.
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. It follows a Last In, First Out (LIFO) order, where the most recently added item is the first one to be removed. Therefore, the correct answer is FILO.
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 product of the number of elements in the input (n) and the logarithm of that number (log n). As the input size increases, the time taken by the algorithm increases at a slower rate compared to n2 or n. This is because binary search divides the input in half at each step, resulting in a logarithmic time complexity. Therefore, the correct answer is n log n.