Q.7➡|UGC NET JUNE 2023 Suppose a circular queue of capacity ( n−1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variable respectively. Initially, REAR=FRONT=0. The conditions to detect queue empty and queue full are
i ➥ EMPTY: REAR ==FRONT FULL : ( REAR+1) mod n== FRONT
ii ➥ EMPTY: ( FRONT +1)mod n== REAR FULL: REAR+1 mod n==FRONT
iii ➥ EMPTY REAR+1) mod n==FRONT FULL: REAR == FRONT
iv ➥ EMPTY: REAR== FRONT FULL: ( FRONT+1) mod n== REAR
Best Explanation: Answer: I Explanation: Upload Soon
Q.8➡|UGC NET JUNE 2023 The total cost of retrieving records in sorted order using an unclustered B+ tree is (P-Average number of records per data page N- Data pages F- Ratio of the size of a data entry to the size of a data record)
Q.9➡|UGC NET JUNE 2023 Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: It is possible to create doubly linked list using only one pointer with every node. Reason R: By storing the XOR of the addresses of the previous and next nodes. In the light of the above statements, choose the most appropriate answer from the options given below.
i ➥ Both A and R are true and R is the correct explanation of A
ii ➥ Both A and R are true but R is NOT the correct explanation of A
iii ➥ A is true but R is false
iv ➥ A is false but R is true
Best Explanation: Answer: I Explanation: Upload Soon
Q.10➡|UGC NET JUNE 2023 A three dimensional array in C ++ is declared as int A[a][b] [c]. Consider that array elements are stored in row major order and indexing begin from 0. Here the address of an item at the location A[r][s][t] computed in terms of word length w of an integer is
i ➥
ii ➥
iii ➥
iv ➥
Best Explanation: Answer: II Explanation: Upload Soon
Q.11➡|UGC NET JUNE 2023 Consider a hash table of size seven with starting index zero and a hash function (6x+3)mod 4. Assuming the hash table is initially empty. Which of the following is the content of the table when the sequence 1,3,8,10,5, is inserted into the table using closed hashing? Here ” denotes an empty location in the table.
i ➥ 1,3,8,10,5,_,_
ii ➥ 3,8,1,_,10,5
iii ➥ _,3,8,1,_,10,5
iv ➥ _1,3,8,10,5,_
Best Explanation: Answer: IV (ACCORDING TO UGC *) MAY BE (II) Explanation: Upload Soon
Q.13➡| NET December 2022 Given an expression (A + B*D) / (E-F) + G (A) The prefix notation is +/+A*DB-EFG (B) The prefix expression is the reverse of the postfix expression (C) The order of operands in infix expression and postfix expression are the same. (D) The order of operands in infix expression, prefix expression and postfix expression are the same Choose the most appropriate answer from the options given below:
i ➥ A, C and D only
ii ➥ C and D only
iii ➥ A and B only
iv ➥ A and D only
Best Explanation: Answer: (ii) Explanation: Upload Soon
Q.14➡| NET June 2022 How many rotations are required during the construction of an AVL tree if the following elements are to be added in the given sequence? 35, 50, 40, 25, 30, 60, 78, 20, 28
i ➥ 2 left rotation, 2 right rotation
ii ➥ 2 left rotation, 3 right rotation
iii ➥ 3 left rotation, 2 right rotation
iv ➥ 3 left rotation, 1 right rotation
Best Explanation: Answer: (iii) Explanation: Upload Soon
Q.15➡| NET June 2022 Consider the hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function. A sequence of records with keys 43, 36, 92, 87, 11, 47, 11, 13, 14 is inserted into an initially empty hash table. The bins of which are indexed from 0 to 10. What is the index of the bin into which the last record is inserted?
i ➥ 8
ii ➥ 7
iii ➥ 10
iv ➥ 4
Best Explanation: Answer: (ii) Explanation: Upload Soon
Q.17➡| NET June 2022 Consider the following graph: For the graph : the following sequences of depth first search (DFS) are given (A) abcghf (B) abfchg (C) abfhgc (D) afghbc Which of the following is correct?
i ➥ (A), (B) and (D) only
ii ➥ (A) ,(B) and (D) only
iii ➥ (B), (C) and (D) only
iv ➥ (A), (C) and (D) only
Best Explanation: Answer: (iv) Explanation: Upload Soon
Q.19➡| NET June 2022 Consider the traversal of a tree Preorder → ABCEIFJDGHKL Inorder → EICFJBGDKHLA Which of the following is correct post order traversal ?
i ➥ EIFJCKGLHDBA
ii ➥ FCGKLHDBUAE
iii ➥ FCGKLHDBAEIJ
iv ➥ IEJFCGKLHDBA
Best Explanation: Answer: (iv) Explanation: Upload Soon
Q.20➡| Data Structure Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in time.
Q.21➡|NTA UGC NET November 2020 Let G be a simple undirected graph, TD be a DFS tree on G, and TB be the BFS tree on G. Consider the following statements. Statement I: No edge of G is a cross with respect to TD Statement II: For every edge (u,v) of G, if u is at depth i and v is at depth j in TB then |i-j|=1
In the light of the above statements, choose the correct answer from the options given below:
i➥Both Statement I and Statement II are true
ii ➥ Both Statement I and Statement II are false
iii ➥Statement I is correct but Statement II is false
iv ➥ Statement I is incorrect but Statement II is true
Show Answer With Best Explanation
Answer: III Explanation: Statement I: True. TD be a DFS tree on G, & there is no edge cross with respect to any Tree but can have cross in directed graphs. Statement II: False. This is not always correct.
Q.22➡|NTA UGC NET November 2020 Which among the following statement(s) is (are) true? A) A hash function takes a message of arbitrary length and generates a fixed length code. B) A hash function takes a message of fixed length and generates a code of variables. C) A hash function may give the same value for distinct messages.
Choose the correct answer from the options given below:
Q.23➡|NTA UGC NET November 2020 A complete n-ary tree is a tree in which nodes have children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L=41, and I=10, what is the value of n?
i➥ 3
ii ➥ 4
iii ➥5
iv ➥ 6
Show Answer With Best Explanation
Answer: III Explanation: L = (n-1) * I + 1 where, L = Leaf Node, I = Internal Node, n = n-ary Tree L = (n-1)*I +1 41 = (n-1) * 10 +1 41 = 10n -10 +1 10n = 50 n = 5
Q.24➡|NTA UGC NET November 2020 In a binary max heap containing n numbers, the smallest element can be found in_____ time.
i➥ O(n)
ii ➥ O(log2 n)
iii ➥O(1)
iv ➥ O(log2 log2 n)
Show Answer With Best Explanation
Answer: I Explanation:
As we know the structure of MAX heap.
In a max heap, the smallest element is always present at a leaf node. As we know the heap being a complete binary tree, there can be up to n/2 leaf nodes. If we are going to examine all of them, we would need O(n) time. Correct Answer is (I)
Q.25➡|NTA UGC NET December 2019 A tree has 2n vertices of degree 1, 3n vertices of degree 2, n vertices of degree 3. Determine the number of vertices and edges in tree.
i➥ 12,11
ii ➥ 11,12
iii ➥10,11
iv ➥ 9,10
Show Answer With Best Explanation
Answer: I
Explanation: By Handshaking theorem, Sum of the Degree of vertices = 2 * Number of Edges 2n1 + 3n2 + n3 = 2E 2n + 6n + 3n = 2E E = 11n/2 —————— equation (1) We know , In Tree Number of vertices = Number of edges + 1 2n + 3n + n = 11n/2 + 1 6n = 11n/2 +1 12n = 12n + 2 n = 2 put n =2 in eqution (1), we got E = 11n/2 E = 112 / 2 E = 11 Number of vertices = number of edges + 1 V = E + 1 V = 11 + 1 V = 12
Q.26➡|NTA UGC NET December 2019 What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume that all insertions can be accommodated.
i➥ θ(1) , θ(n)
ii ➥ θ(n) , θ(1)
iii ➥θ(1) , θ(1)
iv ➥ θ(n) , θ(n)
Show Answer With Best Explanation
Answer: I Explanation: In the worst case running time of insert in unsorted Array, we can simply insert an element at the end of the unsorted array, it would need Θ (1) time. Worst case complexity is Θ(1). ——————————————————————————————– In the worst case running time extract min, there is no specific algorithm for extract min. So, the linear search is an only way to extract min on the unsorted array. it would need Θ (n) time. Worst case complexity is Θ(n). So. the correct answer is (I)
Q.27➡|NTA UGC NET December 2019 B-Tree, each node represents a disk block. Suppose one block holds 8192 bytes. Each key uses 32 bytes. In a B-tree of order M there are M – 1 keys. Since each branch is on another disk block, we assume a branch is of 4 bytes. The total memory requirement for a non-leaf node is
i➥ 32 M – 32
ii ➥ 36 M – 32
iii ➥36 M – 36
iv ➥ 32 M – 36
Show Answer With Best Explanation
Answer: II
Explanation: It is given that , Block pointer = 4 byte Record pointer = 0 , {consider it as 0 because it is not given in the question} Search Key value = 32 byte Size of non-leaf node in B Tree = m * Block pointer + (m – 1)*(search key value + record pointer) = m * 4 + (m-1)*(32 + 0) = 4m + 32m -32 = 36m – 32
Q.28➡|NTA UGC NET December 2019 What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume that all insertions can be accommodated.
i➥ θ(1) , θ(n)
ii ➥ θ(n) , θ(1)
iii ➥θ(1) , θ(1)
iv ➥ θ(n) , θ(n)
Show Answer With Best Explanation
Answer: I Explanation: In the worst case running time of insert in unsorted Array, we can simply insert an element at the end of the unsorted array, it would need Θ (1) time. Worst case complexity is Θ(1). ——————————————————————————————– In the worst case running time extract min, there is no specific algorithm for extract min. So, the linear search is an only way to extract min on the unsorted array. it would need Θ (n) time. Worst case complexity is Θ(n). So. the correct answer is (I)
Q.29➡| NTA UGC NET December 2019 Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[v]=29. d[u] = 15, w[u, v] = 12. What is the updated value of d[u] based on current information
Q.31➡| NTA UGC NET June 2019 Consider double hashing of the form h(k,i)=(h 1 (k)+ih 2 (k)) mod m Where h 1 (k)=k mod m h 2 (k)=1+(k mod n) Where n=m-1and m=701 for k=123456, what is the difference between first and second probes in terms of slots?
Q.32➡| NTA UGC NET December 2018 The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as
Q.33➡| NTA UGC NET December 2018 Consider the following postfix expression with single digit operands : 6 2 3 * / 4 2 * + 6 8 * – The top two elements of the stack after second * is evaluated, are :
Q.34➡| NTA UGC NET December 2018 Consider the singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list ?
Q.35➡| NTA UGC NET December 2018 In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is
Q.36➡| NTA UGC NET December 2018 A binary search tree is constructed by inserting the following numbers in order: 60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34 The number of nodes is the left sub-tree is.
Q.37➡| NTA UGC NET December 2018 An attribute A of data type varchar(20) has the value ‘xyz’ and attribute B of data type char(20) has the value “Imnop” , then the attribute A has _____ spaces and attribute B has_________spaces.
Q.38➡| NTA UGC NET JUNE 2018 A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :
Q.39➡| NTA UGC NET JUNE 2018 A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be :
Q.40➡| NTA UGC NET JUNE 2018 Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ? Here “___” denotes an empty location in the table.
Q.41➡| NTA UGC NET JUNE 2018 Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are__________ and ________respectively. (Root is at level 0).
Q.42➡| NTA UGC NET JUNE 2018 A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?
Q.43➡| NTA UGC NET November 2017 Paper-3 Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf. Which of the following is correct for the full binary tree?
Q.44➡| NTA UGC NET November 2017 Paper-3 Which of the following addressing mode is best suited to access elements of an array of contiguous memory locations ?
Q.45➡| NTA UGC NET January 2017 Paper-2 Which of the following statements is false ? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming. (B) Breadth-first search cannot be used to find connected components of a graph. (C) Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely. (D) Depth-first-search can be used to find the connected components of a graph.
Q.46➡| NTA UGC NET January 2017 Paper-2 The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue.Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is __.
Q.47➡| NTA UGC NET January 2017 Paper-2 If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key x is less than____.
i ➥ 1
ii ➥ 1/n
iii ➥ 1/m
iv ➥ n/m
Show Answer With Best Explanation
Answer: I (Marks to all ) Explanation: Upload Soon
Q.48➡| NTA UGC NET January 2017 Paper-2 Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?
i ➥ Insertion – 0(1), Deletion – 0(1), Maximum – 0(1), Minimum – 0(1)
ii ➥ Insertion – 0(1), Deletion – 0(1), Maximum – 0(n), Minimum – 0(n)
iii ➥ Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1)
iv ➥ Insertion – 0(n), Deletion – 0(n), Maximum – 0(n), Minimum – 0(n)
Q.50➡| NTA UGC NET August 2016 Paper-3 A priority queue is implemented as a max-heap. Initially, it has five elements. The level-order traversal of the heap is as follows: 20, 18, 15, 13, 12 Two new elements ‘10’ and ‘17’are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:
Q.51➡| NTA UGC NET August 2016 Paper-2 Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) | 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c, d) if |a – c| ≤ 1 or | b–d| ≤ 1. The number of edges in this graph is:
Q.52➡| NTA UGC NET August 2016 Paper-2 Consider the following statements: S1: A queue can be implemented using two stacks. S2: A stack can be implemented using two queues. Which of the following is correct?
Q.55➡| NTA UGC NET July 2016 Paper-3 Suppose that we have numbers between 1 and 1,000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined ?
Q.58➡| NTA UGC NET July 2016 Paper-2 Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be
Q.60➡| NTA UGC NET July 2016 Paper-2 Consider the following binary search tree: If we remove the root node, which of the node from the left sub-tree will be the new root?
Q.61➡| NTA UGC NET July 2016 Paper-2 Consider the following operations performed on a stack of size 5 : Push (a); Pop() ; Push(b); Push(c); Pop(); Push(d); Pop();Pop(); Push (e) Which of the following statements is correct?
Q.62➡| NTA UGC NET June 2015 Paper-3 Consider a hash table of size m = 100 and the hash function h(k) = floor(m(kA mod 1)) for A = frac{(sqrt5 – 1) 2 = 0.618033 Compute the location to which the key k = 123456 is placed in hash table.
Q.63➡| NTA UGC NET December 2015 Paper-3 A three dimensional array in ‘C’ is declared as int A[x][y][z]. Here, the address of an item at the location A[p][q][r] can be computed as follows (where w is the word length of an integer):
Q.65➡| NTA UGC NET December 2015 Paper-3 The number of disk pages access in B-Tree search, where ‘h’ is height, ‘n’ is the number of keys, and ‘t’ is the minimum degree, is:
Q.67➡| NTA UGC NET JUNE 2015 Paper-2 Consider the following statements: (a) Depth first search is used to traverse a rooted tree. (b) Preorder, Postorder and Inorder are used to list the vertices of an ordered rooted tree. (c) Huffman’s algorithm is used to find an optimal binary tree with given weights. (d) Topological sorting provides a labelling such that the parents have larger labels than their children. Which of the above statements are true?
Q.69➡| NTA UGC NET JUNE 2015 Paper-2 The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The post-order Traversal is __.
Q.70➡| NTA UGC NET December 2014 Paper-3 How many PUSH and POP operations will be needed to evaluate the following expression by reverse polish notation in a stack machine (A * B) + (C * D/E) ?
