1.
What is Non-linear data structure
Correct Answer
A. Tree
Explanation
A tree is a non-linear data structure that organizes data in a hierarchical structure. It consists of nodes connected by edges, where each node can have multiple children but only one parent (except for the root node). This allows for efficient searching, insertion, and deletion operations. Trees are commonly used to represent hierarchical relationships, such as file systems, organization charts, or family trees. Unlike linear data structures like arrays, linked lists, or stacks, trees do not have a linear sequence and can have multiple branches and levels.
2.
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 in the list points back to the first node, creating a circular structure. This means that there is no end or beginning of the list, and every node is connected to another node, forming a loop. Therefore, there are no NULL links in a circular linked list.
3.
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 correct command would be S [Top-n]. This means that starting from the top of the stack, we count n elements downwards to access the desired element. The other options, S [Top+n] and S [Top-n-1], do not accurately represent the correct command for accessing the nth element from the top of the stack.
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 subtrees of every node can differ by at most 1. This means that the absolute difference between the heights of the left and right subtrees of any node is either 0 or 1. If the difference is 2 or more, then the tree is considered unbalanced. Therefore, the correct answer is 1.
5.
The result of evaluating prefix expression */b+*dacd, where a=3, b=6, c=1, d=5 is
Correct Answer
C. 10
Explanation
The given prefix expression */b+*dacd can be evaluated as follows:
1. *da = 3 * 5 = 15
2. +15c = 15 + 1 = 16
3. *b16 = 6 * 16 = 96
So, the result of evaluating the prefix expression is 96.
6.
In array representation of binary tree the right child of root will be at location of
Correct Answer
A. 2
Explanation
In an array representation of a binary tree, the right child of the root will be at location 2. This is because the array is usually indexed starting from 0, and in a binary tree, the left child is typically stored at index 2*i+1 and the right child 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 will be at index 2*0+2 = 2.
7.
The total number of comparisons in a bubble sort is
Correct Answer
C. O(n2)
Explanation
The bubble sort algorithm compares adjacent elements in a list and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted. In the worst-case scenario, where the list is in reverse order, the algorithm needs to make n-1 passes through the list, each time comparing and swapping adjacent elements. Since each pass requires n-1 comparisons, the total number of comparisons in a bubble sort is O(n^2).
8.
The dummy header in linked list contain
Correct Answer
D. None of above
Explanation
The dummy header in a linked list does not contain any of the options mentioned in the question. A dummy header is an empty node that is used as a placeholder at the beginning of the linked list. It helps simplify the implementation of certain operations, such as inserting or deleting nodes, by providing a consistent starting point. However, it does not contain any actual data or pointers to the first or last records of the actual data.
9.
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 steps:
1. Delete configuration a.
2. Delete configuration b.
3. Delete configuration c.
4. Add configuration d.
5. Add configuration c.
6. Add configuration b.
Therefore, we need a minimum of 3 deletions and 3 additions.
10.
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 3 nodes, so there are 3 possible choices for the root node. Once the root node is chosen, there are 2 remaining nodes that can be arranged as the left and right children of the root. Therefore, the total number of possible ordered trees is 3 * 2 = 6.
11.
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
12.
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
A. 4
13.
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
B. 2,2,1,1,2
14.
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 has two children, there must be 10 + 9 = 19 nodes in total. Therefore, the correct answer is that the tree has 19 nodes.
15.
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 with n nodes can be calculated using the formula log (n +1) - 1. The logarithm function helps determine the number of levels in the binary tree by finding the exponent to which the base (in this case, 2) must be raised to get the number of nodes (n +1). Subtracting 1 from the result gives the depth of the tree.
16.
To arrange a binary search tree in ascending order we need
Correct Answer
B. Inorder traversal
Explanation
In order to arrange a binary search tree in ascending order, we need to perform an inorder traversal. In inorder traversal, we visit the left subtree first, then the root, and finally the right subtree. This ensures that we visit the nodes in ascending order, as the left subtree contains smaller values, the root contains the current value, and the right subtree contains larger values. Therefore, inorder traversal is the correct choice for arranging a binary search tree in ascending order.
17.
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 binary search. Binary search is an efficient search algorithm that works by repeatedly dividing the search interval in half, narrowing down the search space until the desired element is found. The average search time is influenced by factors such as the size of the array and the distribution of the elements within it.
18.
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 give the remainder when the key is divided by 7. Using linear probing, if a collision occurs, the next available slot in the table will be checked.
When inserting the keys 37, 38, 72, 48, 98, 11, 56, the hash values will be as follows:
- f(37) = 37 mod 7 = 2
- f(38) = 38 mod 7 = 3
- f(72) = 72 mod 7 = 2 (collision with key 37, so next available slot 3 is checked)
- f(48) = 48 mod 7 = 6
- f(98) = 98 mod 7 = 0
- f(11) = 11 mod 7 = 4 (collision with key 48, so next available slot 5 is checked)
- f(56) = 56 mod 7 = 0 (collision with key 98, so next available slot 1 is checked)
Therefore, key 11 will be stored at location 5.
19.
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 in the middle of the list, which is at position (n+1)/2. Therefore, the average successful search time is (n+1)/2.
20.
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 would be the maximum of f(n) and g(n) because the algorithm's overall efficiency is determined by the slowest module. Therefore, the correct answer is "Max(f(n),g(n))".
21.
Bib O notation w.r.t algorithm signifies
Correct Answer
D. None of the above
22.
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 running time of the recursive algorithm is T(n) = c + T(n-1) if n > 1, T(n) = d if n < 1. This means that for any input size n greater than 1, the algorithm will perform a constant amount of work (c) plus the running time for an input size of n-1. Since the algorithm is recursive and each recursive call reduces the input size by 1, the running time can be represented as a linear function of the input size (n). Therefore, the order of the algorithm is n.
23.
Four algorithm 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 running time of A1 grows 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.
24.
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 before it and insert it into its correct position in the sequence. This process continues until all the cards are sorted.
25.
In evaluating arithmatic expression 2*3-(4+5) using postfix stack form. Which of the following stack configuration is not possible
Correct Answer
D. ------Top--| 9 | 3 | 2 |------------
Explanation
The given stack configuration is not possible because in postfix form, the operators are placed after the operands. So, the correct stack configuration for the given arithmetic expression would be:
------Top--| 5 | 4 | 6 |------------
26.
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 because it is an efficient sorting algorithm that guarantees a worst-case time complexity of O(n log n). Heap sort works by creating a binary heap data structure and repeatedly extracting the maximum element from it, resulting in a sorted list. This sorting algorithm is particularly useful for large datasets and has good performance characteristics in terms of both time and space complexity.
27.
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. The dope vector is typically used by the compiler or runtime system to perform operations on the array, such as bounds checking or memory allocation. Therefore, the information about an array used in a program will be stored in a dope vector.
28.
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 depends on the number of non-zero entries in the matrix. The linked list implementation only stores the non-zero elements and their corresponding row and column indices, which reduces memory usage compared to a normal array that would store all elements of the matrix. In this case, a 6 x 5 matrix with 8 non-zero entries would consume the same amount of memory as a normal array because both would require storage for 8 non-zero elements.
29.
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 element that is inserted first into the stack will be the last one to be removed. In other words, the most recently added element will be the first one to be removed from the stack. This behavior is similar to a stack of plates, where you can only remove the top plate, which is the last one that was added. Therefore, the correct answer is FILO.
30.
The order of binary search algorithm is
Correct Answer
D. Log n
Explanation
The order of the binary search algorithm is log n. This is because in each step of the algorithm, the search space is divided in half, resulting in a logarithmic time complexity. As the size of the input increases, the number of steps required to find the target element increases at a much slower rate compared to linear or quadratic time complexity. Therefore, the binary search algorithm has a logarithmic time complexity of log n.
31.
The Worst case occur in linear search algorithm when
Correct Answer
D. Item is the last element in the array or is not there at all
Explanation
In the worst case scenario for a linear search algorithm, the item being searched for is either the last element in the array or it is not present in the array at all. This means that in both cases, the algorithm will have to iterate through the entire array before determining that the item is either the last element or not present. This results in the worst possible time complexity for the linear search algorithm.
32.
Arrays are best data structures
Correct Answer
A. For relatively permanent collections of data
Explanation
Arrays are best data structures for relatively permanent collections of data because arrays have a fixed size and are efficient for accessing elements at specific indices. They provide constant time access to elements, making them suitable for situations where the size of the structure and the data in the structure are not constantly changing. Additionally, arrays are contiguous blocks of memory, allowing for efficient memory allocation and deallocation. Therefore, arrays are ideal for situations where the data collection is relatively permanent and does not require frequent resizing or modification.
33.
Linked lists are best suited
Correct Answer
B. for the size of the structure and the data in the structure are constantly changing
Explanation
Linked lists are best suited for situations where the size of the structure and the data in the structure are constantly changing. This is because linked lists allow for efficient insertion and deletion of elements at any position in the list. Unlike arrays, which have a fixed size, linked lists can easily accommodate changes in size without the need for resizing or shifting elements. Therefore, linked lists are a flexible data structure for managing dynamic collections of data.
34.
The elements of an array are stored successively in memory cells because
Correct Answer
A. By this way computer can keep track only the address of the first element and the addresses of other elements can be calculated
Explanation
The elements of an array are stored successively in memory cells because by this way the computer can keep track only the address of the first element and the addresses of other elements can be calculated. This allows for efficient memory management and easy access to array elements using index calculations based on the address of the first element.
35.
Under which condition circular queue is Full
Correct Answer
B. Front=(rear+1)%maxsize
Explanation
The circular queue is considered full when the front pointer is equal to the value of (rear+1)%maxsize. This condition indicates that the next position after the rear pointer is the same as the front pointer, which means that there are no more empty spaces in the queue to add new elements.
36.
Which is not application of stack
Correct Answer
C. Real operating system
Explanation
The given question asks for an application that is not related to a stack. The options provided are "Reversal of string," "evaluation of arithmetic operation," "Real operating system," and "Recursion." The correct answer is "Real operating system" because it is not an application that typically involves the use of a stack. Stacks are commonly used in tasks such as reversing a string, evaluating arithmetic operations, and implementing recursion. However, a real operating system is not directly associated with stack operations.
37.
A leaf node have degree
Correct Answer
C. 0
Explanation
A leaf node is a node in a tree data structure that does not have any child nodes. The degree of a node is defined as the number of child nodes it has. Since a leaf node does not have any child nodes, its degree is 0.
38.
The value of structure is resizing during run time by using
Correct Answer
D. Realloc
Explanation
realloc is used to resize the memory allocated for a structure during runtime. It allows us to change the size of the structure by reallocating memory for it. This function takes two arguments - a pointer to the previously allocated memory and the new size of the structure. It then reallocates memory for the structure with the new size, copying the contents from the old memory to the new memory if necessary. realloc is useful when we need to dynamically resize a structure based on the requirements of the program.
39.
How many types of queue's are available
Correct Answer
D. 4
Explanation
There are four types of queues available. The question is asking about the number of types, and the answer is given as 4. This means that there are four different categories or classifications of queues that exist.
40.
Disadvantage of linear queue is overcome by using
Correct Answer
B. Circular queue
Explanation
A disadvantage of a linear queue is that once the queue is full, it cannot accommodate any more elements, even if there are empty spaces at the front of the queue. This limitation is overcome by using a circular queue. In a circular queue, when the queue is full, the rear pointer wraps around to the front of the queue, allowing new elements to be added in the empty spaces at the front. This ensures efficient utilization of the available space in the queue and avoids wastage. Therefore, a circular queue is a suitable solution to overcome the disadvantage of a linear queue.
41.
An Array is what kind of data structure
Correct Answer
A. Linear
Explanation
An array is a linear data structure because it stores elements in a sequential manner, where each element is accessed by its index. The elements in an array are stored in contiguous memory locations, allowing for efficient access and retrieval of elements. This linear arrangement of elements makes it easy to perform operations like traversal, insertion, and deletion. Therefore, the correct answer is linear.
42.
While inserting an item in an array of integers which loop is right, where pos is the pos at which insertion is to be made(assume array starts from 1 and N is the max no. of items in the array.)
Correct Answer
D. For(i=N; i>=pos;i--) { A[i+1] = A[i] }
Explanation
The correct loop for inserting an item in an array of integers at a given position is "for(i=N; i>=pos;i--) { A[i+1] = A[i] }". This loop starts from the last element of the array and moves towards the position where the insertion is to be made. It shifts each element one position to the right, creating space for the new item to be inserted at the desired position.
43.
To delete an item from an array which loop is correct, where p is the position of deletion( assume array starts from 1 and N is the max no. of items in the array.)
Correct Answer
B. For(i=pos;i
Explanation
The correct loop for deleting an item from an array at position p is "for(i=pos;i
44.
What is the contents of the array after the execution of the following program :-int a[] = {10,30, 20, 10, 30, 40};for(i=1;i<=6;i++) { for(j=i+1 ; j<= 6; j++) { if(a[i] == a[j]) { a[j] = 0; }}
Correct Answer
D. 10,30, 20, 0, 0, 40
Explanation
The given program compares each element of the array 'a' with all the elements that come after it. If a duplicate element is found, it is replaced with 0. The program starts with the first element and compares it with all the elements that come after it. Then, it moves on to the second element and compares it with the remaining elements, and so on. Based on this logic, the correct answer is 10,30, 20, 0, 0, 40.
45.
A Stack follows the principle of
Correct Answer
A. LIFO
Explanation
A stack follows the principle of LIFO, which stands for Last In, First Out. This means that the last item added to the stack is the first one to be removed. In a stack, new elements are added to the top and removed from the top. This behavior is similar to a stack of plates, where you can only remove the top plate and add new plates on top. Therefore, the correct answer is LIFO.
46.
With every push in the stack the top
Correct Answer
B. Increments by one
Explanation
The given answer states that with every push in the stack, the top increments by one. This means that whenever a new element is added to the stack, the top position is updated to point to the newly added element. This is a common behavior in stack data structures, where the top position keeps track of the most recently added element.
47.
Identify the UnderFlow condition for a Stack
Correct Answer
A. If( top < 1)
Explanation
The correct answer is "if( top < 1)". This condition checks if the top of the stack is less than 1, indicating that the stack is empty or underflowing. If the top is less than 1, it means there are no elements in the stack and any attempt to pop or access an element would result in an underflow condition.
48.
Identify the OverFlow condition for a Queue
Correct Answer
A. If(REAR > N)
Explanation
The correct answer is if(REAR > N). This condition checks if the rear index of the queue is greater than the maximum size of the queue (N). If this condition is true, it means that the queue has reached its maximum capacity and cannot accept any more elements, resulting in an overflow condition.
49.
To Delete an item from a Queue identify the correct set of statements :-
Correct Answer
B. Item = Q[FRONT];
FRONT++;
Explanation
This set of statements correctly identifies the process of deleting an item from a queue. The first statement assigns the value of the item to be deleted to the variable Q[REAR]. Then, the second statement increments the value of REAR to indicate that the item has been removed from the queue. Finally, the third statement assigns the value of the item to the variable Q[FRONT] and increments the value of FRONT to indicate that the front of the queue has moved forward. This sequence of steps ensures that the item is properly deleted from the queue.
50.
To Insert an item from a stack identify the correct set of statements :-
Correct Answer
A.
top++;
S[top] = Item;
Explanation
These statements correctly show the process of inserting an item into a stack. The first statement increases the top pointer to point to the next available position in the stack. The second statement assigns the item to that position in the stack. Therefore, the correct answer is "top++; S[top] = Item;".