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 has a valid link to another node, and there are no NULL pointers. In contrast, both single linked lists and linear doubly linked lists have NULL links at the end of the list to indicate the end of the structure.
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, the correct command is S [Top-n]. This command indicates that we start from the top of the stack (Top) and move n positions downwards to access the desired element. The other options are incorrect because they either indicate moving upwards or do not account for the correct number of positions to move.
3.
If yyy, xxx and zzz are the elements of a binary binary tree, then in preorder traversal which node will be traverse first
Correct Answer
B. Yyy
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 the given options, "yyy" will be traversed first as it is mentioned before "xxx" and "zzz".
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 a node should differ by at most 1 level. This ensures that the tree remains balanced and allows for efficient searching and insertion operations. If the height difference is more than 1, the tree is considered unbalanced and may lead to performance issues. 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
In the given prefix expression, the operator '*' multiplies the values of 'b' and the result of the next operation. The operator '+' adds the values of '0' and 'd'. The operator '/' divides the result of the previous operation by the value of 'a'. Finally, the operator '+' adds the result of the previous operation to the value of 'c'. Substituting the given values, the expression becomes (6 * (0 + 5) / 3) + 1 = 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 an array representation of a binary tree, the right child of the root will be at location 3. This is because the array starts indexing from 0, and the right child is typically located at 2 * index + 2. In this case, the root's index is 0, so the right child would be at 2 * 0 + 2, which is 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 a bubble sort, each element of the array is compared with its adjacent element and swapped if necessary. This process is repeated until the array is sorted. As there are n elements in the array and for each element, we need to compare it with n-1 other elements, the total number of comparisons in a bubble sort is n * (n-1), which simplifies to O(n2).
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 contains the first record of the actual data. This dummy header is used to simplify operations on the linked list by providing a consistent starting point. It allows for easier insertion and deletion of nodes without having to handle special cases for an empty list. By pointing to the first record of the actual data, the dummy header ensures that the list always has a valid starting point for traversal and manipulation.
9.
Write the output of following program:int a[ ] = {1,2,3,} *p;
Correct Answer
B. Junk value
Explanation
The program is attempting to assign a value to a pointer variable without initializing it. As a result, the pointer variable will contain a random or 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 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 tree can also be called a complete m-ary tree because it satisfies the condition of a complete tree, where all levels except the last are completely filled and all nodes are as far left as possible. Therefore, the correct answer is both (i) and (ii).
11.
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 move the elements in the queue in reverse order. This means we need to delete the elements in the original queue and add them to a new queue in the reverse order. Since there are 4 elements in the original queue, we need to perform 3 deletions (to remove a,b,c) and 3 additions (to add d,c,b) in order to achieve the desired configuration. Therefore, the correct answer is 3 deletions and 3 additions.
12.
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 calculated using the formula for the number of rooted trees. In this case, there are 3 nodes, so the formula is 3^(3-1) = 3^2 = 9. However, since the trees are ordered, we need to divide by the number of ways the nodes can be arranged, which is 3! (factorial). Therefore, the total number of possible ordered trees is 9 / 3! = 9 / 6 = 1.5. Since the number of trees must be a whole number, the correct answer is 6, which is the closest whole number to 1.5.
13.
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 using bubble sort. Bubble sort works by repeatedly swapping adjacent elements if they are in the wrong order. In this case, there are a total of 8 numbers to sort. Therefore, the number of swapping operations required would be 8 - 1 = 7. However, since the question asks for the number of swapping operations needed to sort the numbers in ascending order, we need to add 6 more swapping operations to bring the largest number, 31, to its correct position. Hence, the total number of swapping operations needed is 7 + 6 = 13.
14.
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 recursively dividing the list 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 would be L1 + L2. However, we subtract 1 from the sum because the last element of the first list does not need to be compared with the first element of the second list during the merging process. Therefore, the correct answer is L1 + L2 - 1.
15.
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
16.
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 a stack can be represented as follows:
- Push(1): The stack becomes [1]
- Push(2): The stack becomes [1, 2]
- Pop: The top element 2 is removed from the stack. The stack becomes [1]
- Push(1): The stack becomes [1, 1]
- Push(2): The stack becomes [1, 1, 2]
- Pop: The top element 2 is removed from the stack. The stack becomes [1, 1]
- Pop: The top element 1 is removed from the stack. The stack becomes [1]
- Pop: The top element 1 is removed from the stack. The stack becomes empty []
- Push(2): The stack becomes [2]
- Pop: The top element 2 is removed from the stack. The stack becomes empty []
Therefore, the sequence of popped out values is 2, 1, 2, 2, 2.
17.
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 left and right sub trees. In this case, the tree has 10 leaves. Since each non-leaf node has two sub trees, there will be 9 non-leaf nodes in total (10 leaves - 1 root node). Therefore, the total number of nodes in the tree will be 10 leaves + 9 non-leaf nodes = 19 nodes.
18.
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. The depth of a binary tree is the maximum number of edges from the root to a leaf node. In a binary tree with n nodes, the maximum number of edges is n-1. Taking the logarithm of n+1 and subtracting 1 gives the depth of the tree.
19.
To arrange a binary tree in ascending order we need
Correct Answer
B. Inorder traversal
Explanation
Inorder traversal is the correct answer because it visits the nodes of a binary tree in ascending order. In this traversal, the left subtree is visited first, then the root node, and finally the right subtree. By visiting the nodes in this order, we can arrange the elements of the binary tree in ascending order. Therefore, inorder traversal is the appropriate method to arrange a binary tree in ascending order.
20.
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 element in the array using the binary search algorithm. Binary search is an efficient algorithm for searching in sorted arrays, as it divides the search space in half at each step, reducing the number of elements to search by half each time. The average time complexity of binary search is logarithmic, which explains why the search time is relatively low for a small array size like 10.
21.
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 maps each key to a value between 0 and 6. When linear probing is used, if a collision occurs, the next available slot is checked. In this case, the keys 37, 38, 72, 48, 98, 11, and 56 are being inserted. When the key 11 is inserted, it is hashed to the value 4. However, since that slot is already occupied by the key 48, linear probing is used to check the next slot, which is 5. Since slot 5 is available, the key 11 will be stored at location 5.
22.
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 can be explained by considering that in a sequential search, the algorithm starts searching from the beginning of the list and continues until it finds the desired item. On average, the item being searched for is likely to be found in the middle of the list. Therefore, the time it takes to find the item can be approximated as (n+1)/2.
23.
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 relation T(n) = 8 T(n/2) + qn, where n is the input size. This indicates that the algorithm divides the problem into two equal-sized subproblems and solves each subproblem recursively. The time complexity of solving each subproblem is T(n/2). Additionally, there is a linear term qn, which represents the time taken to combine the solutions of the subproblems.
By analyzing the recursive relation, we can observe that the algorithm has a complexity of O(n^3). This is because at each level of recursion, the problem size is divided by 2, resulting in a logarithmic factor of log(n) in the recursion tree. The qn term represents the work done at each level, which is linear in n. Combining these factors, we get a cubic time complexity of O(n^3).
24.
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 X1 has the highest number of records (150), followed by X2 (250), X3 (55), X4 (85), X5 (125), and X6 (175). By storing the files in this order, we can access the files with the highest number of records first, which will minimize the overall access time.
25.
In above question average access time will be
Correct Answer
B. 140
Explanation
The correct answer is 140. This is because the average access time is calculated by taking the sum of all access times and dividing it by the total number of access times. In this case, there are three access times given: 150, 140, and 55. Adding them together gives a sum of 345. Dividing this by the total number of access times (3) gives an average of 115. Therefore, the correct answer is 140.
26.
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 module that takes the longest time will determine the overall time complexity of the algorithm. Therefore, the correct answer is Max(f(n),g(n)).
27.
Bib O notation w.r.t algorithm signifies
Correct Answer
D. None of the above
28.
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 equation T(n) = c + T(n-1), which means that the running time of the algorithm is constant (c) plus the running time of the algorithm with input size reduced by 1 (T(n-1)). This indicates that the algorithm has a linear time complexity, as it performs a constant amount of work for each input size. Therefore, the order of the algorithm is n.
29.
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 much slower rate compared to the other algorithms. A2 has a time complexity of O(log log(n)), which is slightly worse than A1. A3 has a time complexity of O(n log(n)), which is worse than both A1 and A2. A4 has a time complexity of O(n), which is the worst among all the algorithms. Therefore, A1 is the most efficient algorithm for solving the given problem.
30.
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 for each input size n, the algorithm calls itself with an input size of n-1 and performs an additional operation of 1/n. This indicates that the algorithm has a linear relationship with the input size.
By solving the recurrence relation, we find that the time complexity of the algorithm is O(n^2). This means that the algorithm has a quadratic order, as the time taken by the algorithm grows quadratically with the input size.
31.
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 data on external storage devices, such as hard drives, rather than in main memory. External sorting is necessary when the data cannot fit entirely in memory, and it involves reading and writing data to and from the external storage during the sorting process. In contrast, internal sorting is used when the data can fit entirely in memory, and it involves sorting the data within the main memory.
32.
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 is considered stable if it preserves the relative order of records with the same primary key in the sorted list as they were in the original unsorted list. This means that if two records have the same primary key, the one that appeared first in the unsorted list will also appear first in the sorted list.
33.
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
34.
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(1) - T(3) = T(2) suggests that the difference between the running time of the algorithm at n=1 and n=3 is equal to the running time at n=2. This implies that the algorithm order becomes constant when T(1), T(2), and T(3) are equal.
35.
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 on its left and inserted at the correct position, similar to how cards are picked and inserted into their correct positions in a pack. This process continues until all the cards are arranged in the correct order.
36.
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 |
------------
37.
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 input size 'n'. In other words, as 'n' increases, the time taken by the algorithm to determine the output becomes significantly larger. This suggests that the algorithm may not be efficient for large values of 'n' and could potentially take a very long time to compute the result.
38.
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 until each sublist has only one element. Then it merges the sublists by comparing and sorting them. In this case, we have two sorted lists of length 2, which means each list has two elements. To merge these two lists, a total of 8 comparisons will be performed. Therefore, the average number of comparisons performed by the merge sort algorithm in merging two sorted lists of length 2 is 8/3.
39.
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 an efficient sorting algorithm that works by creating a binary heap data structure. It has a time complexity of O(n log n) and is known for its optimal performance. By using heap sort, the books can be sorted in an organized and systematic manner, ensuring that they are easily accessible to library users.
40.
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 it iterates through the array and for each element, it compares it to the previous elements and inserts it into the correct position. In the worst case scenario, where the array is sorted in descending order, each element would have to be compared to all the previous elements before it is inserted. This results in a time complexity of O(n^2). However, on average, the number of comparisons and shifts required is reduced, resulting in a time complexity of O(n log(n)).
41.
Which algorithm solves all pair shortest path problem
Correct Answer
A. Dijkastra's algorithm
Explanation
Dijkstra's algorithm is used to solve the single-source shortest path problem, not the all pair shortest path problem. The correct algorithm to solve the all pair shortest path problem is Floyd's algorithm. This algorithm finds the shortest path between all pairs of vertices in a weighted graph. Prim's algorithm is used to find the minimum spanning tree of a graph, and Worshall's algorithm is used to find the transitive closure of a directed graph.
42.
The centricity of node labeled 5 is
Correct Answer
C. 2
Explanation
The centricity of a node refers to the minimum eccentricity of that node, which is the maximum shortest path distance between that node and any other node in the graph. In this case, the node labeled 5 has a shortest path distance of 2 to itself, which is the minimum distance compared to the other nodes in the graph. Therefore, the centricity of node labeled 5 is 2.
43.
The information about an array used in a program will be stored in
Correct Answer
B. Dope vector
Explanation
A dope vector is used to store information about an array used in a program. It contains details such as the starting address of the array, the size of the array, 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 corresponding memory locations, the register vector is used to keep track of the registers being used by the program, and the activation table is used to manage the activation records of function calls. However, none of these data structures specifically store information about arrays, making the dope vector the correct answer.
44.
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 as it only stores the non-zero entries. The size of the matrix is determined by the number of rows and columns, and the size of each entry. 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 space for all 30 elements (6 rows x 5 columns) regardless of the number of non-zero entries.
45.
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 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 matrix elements, even if they are not used. The linked list representation only stores the non-zero elements of the matrix, resulting in more efficient memory usage. Additionally, the linked list representation allows for efficient insertion and deletion of elements, making it a flexible and dynamic approach for representing sparse matrices.
46.
On which principle does stack work?
Correct Answer
A. FILO
Explanation
Stack works on the principle of FILO (First In Last Out). This means that the element which is inserted first into the stack will be the last one to be removed. When elements are added to the stack, they are placed on top of each other and when an element is removed, it is always the most recently added element. This behavior is similar to a stack of plates, where the last plate added is the first one to be removed. Therefore, the correct answer is FILO.
47.
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. This is because in each iteration of the binary search, the algorithm divides the search space in half, leading to a logarithmic time complexity. However, since the algorithm still needs to compare the elements in the search space, the overall time complexity is n log n.
48.
Two main measures for the efficiency of an algorithm are
Correct Answer
C. Time and space
Explanation
The efficiency of an algorithm is typically measured by two main factors: time and space. Time refers to the amount of time it takes for the algorithm to execute and complete its task, while space refers to the amount of memory or storage that the algorithm requires to run. By considering both time and space, we can determine how efficiently an algorithm utilizes computational resources.
49.
The time factor when determining the efficiency of algorithm is measured by
Correct Answer
B. Counting the number of key operations
Explanation
The efficiency of an algorithm is determined by measuring the time factor, which is commonly done by counting the number of key operations. Key operations refer to the essential steps or operations performed by the algorithm that directly impact its execution time. By counting the number of key operations, we can get a rough estimate of the algorithm's efficiency and compare it with other algorithms.
50.
The space factor when determining the efficiency of algorithm is measured by
Correct Answer
A. Counting the maximum memory needed by the algorithm
Explanation
The space factor when determining the efficiency of an algorithm is measured by counting the maximum memory needed by the algorithm. This means that the efficiency of the algorithm is evaluated based on the maximum amount of memory it requires to perform its tasks. By considering the maximum memory usage, we can assess the algorithm's performance in terms of space utilization and make informed decisions about its efficiency.