Data-Structures

Question 1
Which of the following is application of Breadth First Search on the graph?
A
Finding the diameter of the graph
B
Finding the bipartite graph
C
Both (a) and (b)
D
None of the above
       Data-Structures       Graphs       ISRO-2018
Question 1 Explanation: 
Breadth-first search can be used to solve many problems in graph theory

Examples
1. Copying garbage collection, Cheney's algorithm
2. Find the diameter of the graph
3. Testing bipartiteness of a graph.
4. Finding the shortest path between two nodes u and v, with path length measured by the number of edges (an advantage over depth-first search)
5. (Reverse) Cuthill–McKee mesh numbering
6. Ford–Fulkerson method for computing the maximum flow in a flow network
7. Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be reconstructed in an efficient manner.
8. Construction of the failure function of the Aho-Corasick pattern matcher.
Question 2
A doubly linked list is declared as Where Fwd and Bwd represent forward and a backward link to the adjacent elements of the list. Which of the following segments of code deletes the node pointed to by X from the doubly linked list, if it is assumed that X points to neither the first nor the last node of the list?
A
X→ Bwd→ Fwd = X→ Fwd; X→ Fwd → Bwd = X→ Bwd ;
B
X→ Bwd.Fwd = X→ Fwd ; X.Fwd→ Bwd = X→ Bwd ;
C
X.Bwd→ Fwd = X.Bwd ; X→ Fwd.Bwd = X.Bwd ;
D
X→ Bwd→ Fwd = X→ Bwd ; X→ Fwd→ Bwd = X→ Fwd;
       Data-Structures       Linked-List       ISRO-2018
Question 2 Explanation: 
Let the element just before x be y and that just after be z. In order to link y to z,
we need x→ Bwd→ Fwd = x.
Fwd and in order to link z to y, we need x→ Fwd→ Bwd=x→ Bwd.
Question 3
If Tree-1 and Tree-2 are the trees indicated below :

Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?
A
Preorder, Postorder
B
Postorder, Inorder
C
Postorder, Preorder
D
Inorder, Preorder
       Data-Structures       Binary-Trees       ISRO-2018
Question 3 Explanation: 
→ Pre order traverses Root, Left, Right.
→ Post order traverses Left, Right, Root.
→ In-order traverses Left, Root, Right.
Tree-1: Post order: GJIHEFBDCA
Tree-2: In order: GJIHEFBDCA
Question 4
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A
A
B
B
C
C
D
D
       Data-Structures       Queues-and-Stacks       ISRO-2007
Question 4 Explanation: 
When five items: A, B, C, D, and E are pushed in a stack: Order of stack becomes: A, B, C, D, and E (A at the bottom and E at the top.) stack is popped four items and each element is inserted in a queue: Order of queue: B, C, D, E (B at rear and E at the front) Order of stack after pop operations = A. Two elements deleted from the queue and pushed back stack: New order of stack = A, E, D(A at the bottom, D at the top) As D is on the top so when pop operation occurs D will be popped out. So, correct option is (D).
Question 5
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
A
Delete the last element of the list
B
Delete the first element of the list
C
Add an element after the last element of the list
D
Interchange the first two elements of the list
       Data-Structures       Linked-List       ISRO-2018
Question 5 Explanation: 
F and L must point to the first and last elements respectively.
Option B: It needs only the operation F=F→ next
Option C: It needs only the operations L→ next=new node, L = new node
Option D: It needs only the operations T=F, F=F→ next, T→ next =F→ next, F→ next=T
→ All these operations do not depend on the length of the list.
→ Indeed in order to delete the last element from the list, we need to first locate the element before the last (which can not be accessed from L). Thus we must parse all the list from the first and till the element just before the last after which we can delete the last element and assign L to the one before.
Question 6
Let X be the adjacency matrix of a graph G with no self loops. The entries along the principal diagonal of X are
A
all zeros
B
all ones
C
both zeros and ones
D
different
       Data-Structures       Graph-Theory       ISRO-2007
Question 6 Explanation: 
In an adjacency matrix of a graph G the entries along the principal diagonal are reflexive, i.e. elements showing connectivity with themselves. Since the GrapH G has no self loops so all these entries should be 0.
Question 7
Given a binary-max heap. The elements are stored in an array as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?
A
14,13,8,12,10
B
14,12,13,10,8
C
14,13,12,8,10
D
14,13,12,10,8
       Data-Structures       Binary-Heap       ISRO-2018
Question 7 Explanation: 
Step-1: Initially, the heap structure is

Step-2: We have to perform 2 delete operations.
In max-heap (or) min-heap by default we are deleting root element only.
After 1st delete, the heap structure is

Step-3: After 2nd delete operation, the heap structure is
Question 8
A hash table with 10 buckets with one slot per bucket is depicted here. The symbols, S1 to s7 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is
A
4
B
5
C
6
D
3
       Data-Structures       Hashing       ISRO-2018
Question 8 Explanation: 
In this, maximum size of cluster=4(S6, S3, S7, S1)
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum number of comparisons = 4 + 1 = 5
Question 9
Let P be a procedure that for some inputs calls itself (i.e. is recursive). If P is guaranteed to terminate, which of the following statement(s) must be true?
I. P has a local variable
II. P has an execution path where it does not call itself
III. P either refers to a global variable or has at least one parameter
A
I only
B
II only
C
III only
D
II and III only
       Data-Structures       ISRO-2018
Question 9 Explanation: 
In any recursive procedure:
→ P has an execution path where it does not call itself
→ P either refers to a global variable or has at least one parameter

Recursion Rules
Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.
The recursive calls must eventually reach a base case, which is solved without further recursion.
Question 10
Which of the following is an illegal array definition?
A
Type COLOGNE : (LIME, PINE, MUSK, MENTHOL); var a : array [COLOGNE] of REAL;
B
var a : array [REAL] of REAL;
C
var a : array [‘A’…’Z’] of REAL;
D
var a : array [BOOLEAN] of REAL;
       Data-Structures       Arrays       ISRO CS 2008
Question 10 Explanation: 
Array index should be integer not real numbers.
Expect the option B, All remaining indexes are not real numbers.
Option A , takes enum value as index which is integer number.
Option C, takes character which is having equivalent decimal value.
Option D, has boolean value as index whose value may be 0 or 1
Question 11
Given two statements:
(i) Insertion of an element should be done at the last node in a circular list
(ii) Deletion of an element should be done at the last node of the circular list
A
Both are true
B
Both are false
C
First is false and second is true
D
None of the above
       Data-Structures       Linked-List       ISRO-2017 May
Question 11 Explanation: 
There are three situation for inserting element and deleting an element in Circular linked list.
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.
Question 12
Which of the following data structure is useful in traversing a given graph by breadth-first search?
A
Stack
B
List
C
Queue
D
None of the above
       Data-Structures       Graphs       ISRO-2017 May
Question 12 Explanation: 
Question 13
The number of distinct simple graphs with up to three nodes is
A
15
B
10
C
7
D
9
       Data-Structures       Graphs       ISRO CS 2008
Question 13 Explanation: 

The number of distinct simple graphs with up to three nodes:



So, total 7 unlabeled nodes are possible. Option (C) is correct.
Question 14
The maximum number of edges in a n-node undirected graph without self loops is
A
n2
B
n * (n-1)/2
C
n – 1
D
(n + 1) * n/2
       Data-Structures       Graphs       ISRO CS 2008
Question 14 Explanation: 
A complete graph can have a maximum edges for ‘n’ nodes as each node is connected to every other node. So, for n nodes, maximum n * (n-1)/2 nodes are possible.
Question 15
The best data structure to check whether an arithmetic expression has balanced parenthesis is a
A
Queue
B
Stack
C
Tree
D
List
       Data-Structures       Queues-and-Stacks       ISRO-2017 May
Question 15 Explanation: 
→ The stack is the best data structure to validate the arithmetic expression.
→ While evaluating when left parentheses occur then it pushes into the stack when right parentheses occur pop from the stack. While at the end there is empty in the stack.
Question 16
Embedded pointer provides
A
A secondary access path
B
A physical record key
C
An inverted index
D
A primary key
       Data-Structures       Relational-databases       ISRO CS 2008
Question 16 Explanation: 

1. To understand how pointers and their associated data elements are allocated in Microsoft RPC, you have to differentiate between top-level pointers and embedded pointers

2. Top-level pointers are those that are specified as the names of parameters in function prototypes. Top-level pointers and their referents are always allocated on the server.

3. Embedded pointers are pointers that are embedded in data structures such as arrays, structures, and unions. When embedded pointers only write output to a buffer and are null on input, the server application can change their values to non-null. In this case, the client stubs allocate new memory for this data.

4. If the embedded pointer is not null on the client before the call, the stubs do not allocate memory on the client on return. Instead, the stubs attempt to write the memory associated with the embedded pointer into the existing memory on the client associated with that pointer, overwriting the data already there.
Question 17
Choose the equivalent prefix form of the following expression (a + (b − c))* ((d − e)/(f + g − h))
A
* +a − bc /− de − +fgh
B
* +a −bc − /de − +fgh
C
* +a − bc /− ed + −fgh
D
* +ab − c /− ed + −fgh
       Data-Structures       Prefix-Postfix-Expression       ISRO-2017 May
Question 17 Explanation: 
→ An expression is called the prefix expression if the operator appears in the expression before the operands.


Question 18
In a doubly linked list, the number of pointers affected for an insertion operation will be
A
4
B
0
C
1
D
None of these
       Data-Structures       Linked-List       ISRO-2017 May
Question 18 Explanation: 
It depends on whether to insert the node at first, middle or last. No proper input in question.
Note: Excluded for evaluation.
Question 19
What is the value of F(4) using the following procedure:
function F(K : integer)
integer;
begin
if (k<3) then F:=k
else F:=F(k-1)*F(k-2)+F(k-3)
end;
A
5
B
6
C
7
D
8
       Data-Structures       Programming       ISRO CS 2008
Question 19 Explanation: 

F(4) = F(3)*F(2)+F(1) = 5

F(3) = F(2)*F(1)+F(0) = 2

F(2) = 2

F(1) = 1

F(0) = 0
Question 20
Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of the stack B can be only be printed. In this arrangement, which of the following permutations of a, b, c are not possible?
A
b a c
B
b c a
C
c a b
D
a b c
       Data-Structures       Stacks-queues       ISRO CS 2008
Question 20 Explanation: 
Explanation:
Option (A):
Pop a from stack A
Push a to stack B
Print b
Print a from stack B
Print c from stack A
Order = b a c
Option (B):
Pop a from stack A
Push a to stack B
Print b from stack A
Print c from stack A
Print a from stack A
Order = b c a
Option (C):
Pop a from stack A
Push a to stack B
Pop b from stack A
Push b to stack B
Print c from stack A
Now, printing a will not be possible.
Question 21
The time required to search an element in a linked list of length n is
A
O(log n)
B
O(n)
C
O(1)
D
(n2)
       Data-Structures       Searching       ISRO CS 2008
Question 21 Explanation: 
In the worst case, the element to be searched has to be compared with all elements of linked list. It will take O(n) time to search the element.
Question 22
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?
A
Deleting a node whose location is given
B
Searching an unsorted list for a given item
C
Inserting a node after the node with a given location
D
Traversing the list to process each node
       Data-Structures       Linked-list       ISRO CS 2008
Question 22 Explanation: 
Searching node / traversing the list means we need to traverse the entire list whether it may be linear linked list or doubly linked list.
Inserting the node after the node with the a given location won’t require of traversing the list to previous nodes or memory locations.In this case also, there is no difference between whether it may be linear linked list or doubly linked list.

The main purpose of double linked list is to traverse the list in both directions so Deleting the node becomes easy while traversing the both directions.
Question 23
The time required to search an element in a linked list of length n is
A
O(log n)
B
O(n)
C
O(1)
D
O(n2)
       Data-Structures       Searching       ISRO CS 2008
Question 23 Explanation: 
In the worst case, the element to be searched has to be compared with all elements of linked list, so the time complexity is O(n)
Question 24
A complete binary tree with the property that the value at each node is as least as large as the values at its children is known as
A
binary search tree
B
AVL tree
C
completely balanced tree
D
Heap
       Data-Structures       Binary-trees       ISRO CS 2008
Question 24 Explanation: 
In a Max. Binary Heap, the key value at each node is as least as large as the values at its children. Similarly in Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap.
Question 25
The minimum number of fields with each node of doubly linked list is
A
1
B
2
C
3
D
4
       Data-Structures       Linked-list       ISRO CS 2008
Question 25 Explanation: 
Explanation: In general, each node of doubly link list always has 3 fields, i.e., the previous node pointer, the data field, and the next node pointerSo, answer should be option (C) 3.
However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient
doubly linked list, Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.
Question 26
The infix expression A+(B–C)*D is correctly represented in prefix notation as
A
A+B−C∗D
B
+A∗−BCD
C
ABC−D∗+
D
A+BC−D∗
       Data-Structures       Prefix-Postfix-Expression       ISRO CS 2009
Question 26 Explanation: 

Given Expression = A + (B – C)* D

Prefix Notation:

A + (- B C) * D

A + (* - B C D)

+ A * - B C D
Question 27
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * –
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are
A
6,1
B
5,7
C
3,2
D
1,5
       Data-Structures       Queues-and-Stacks       ISRO-2016
Question 27 Explanation: 
Expression: 8 2 3 ^ / 2 3 * + 5 1 * –
Rule (1): If the element is a number, Push it into stack.
Rule (2): If the element is an operator, Pop operands from the stack. Evaluate the operator operation and Push the result back into the stack.
Question 28
A Hash Function f is defined as f(key) = key mod 7. With linear probing, while inserting the keys 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0, in which location the key 11 will be stored (Count table index 0 as 0th location)?
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       ISRO-2016
Question 28 Explanation: 
Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7
Question 29
A complete binary tree with n non-leaf nodes contains
A
log2n nodes
B
n+1 nodes
C
2n nodes
D
2n+1 nodes
       Data-Structures       Binary-Trees       ISRO-2016
Question 29 Explanation: 
→ A binary tree where each non-leaf node has exactly two children. The number of leaves is n+1. Total number of nodes is 2n+1.
Note: if two leaves having the same parent are removed from the tree, the number of leaves and non-leaves will decrease by 1 because the parent will be a leaf. That means the difference between them is constant. And for a tree having just one node that difference is 1.
Question 30
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder traversal sequence of the resultant tree?
A
7 5 1 0 3 2 4 6 8 9
B
0 2 4 3 1 6 5 9 8 7
C
0 1 2 3 4 5 6 7 8 9
D
9 8 6 4 2 3 0 1 5 7
       Data-Structures       Binary-search-tree       ISRO CS 2009
Question 30 Explanation: 
Binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.) in memory.

The in-order traversal of BST will gives the elements in the sorted order( ascending order)
Question 31
A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set.
I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
A
A heap can be used but not a balanced binary search tree
B
A balanced binary search tree can be used but not a heap
C
Both balanced binary search tree and heap can be used
D
Neither balanced search tree nor heap can be used
       Data-Structures       Binary-search-tree       ISRO CS 2009
Question 31 Explanation: 
Heap is a balanced binary tree (or almost complete binary tree), insertion complexity for heap is O(logn). We can get smallest element from the min heap in O(logn) time. But we can’t insert an element if it is not already present in O(logn) time .

A self-balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a self balancing BST, we can easily find out minimum element in O(logn) time which is always the leftmost element.
Question 32
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
A
2
B
3
C
4
D
6
       Data-Structures       Binary-search-tree       ISRO CS 2009
Question 32 Explanation: 


So, height of the tree is defined maximum distance of a leaf node from the root.The root node is “10” and lead node is “5”.The maximum distance is 3
Question 33
Assume that the operators +, −, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, −. The postfix expression corresponding to the infix expression is a + b × c − d ^ e ^ f  
A
abc x + def ^ ^ −
B
abc x + de ^ f ^ −
C
ab + c × d − e^f^
D
− + a × b c^^ def
       Data-Structures       Prefix-Postfix-Expression       ISRO CS 2009
Question 33 Explanation: 


The operators in the expression are +,x,- ^



First we will convert e^f ad ef^ (as highest precedence and right associativity) and later

d ^( e f ^ ) to def^^ and so on , you can find the same thing from the below steps.

The postfix expression:

a + b × c − ( d ^( e ^ f))

a + b × c − ( d ^( e f ^ ))

a + b × c − ( d e f ^ ^)

(a + (b × c)) − d e f ^ ^

(a + (b c x)) − d e f ^ ^

(a (b c x) +) − d e f ^ ^

(a b c x +) - (d e f ^ ^)

(a b c x +) - (d e f ^ ^)

a b c x + d e f ^ ^ -
Question 34
A one dimensional array A has indices 1….75. Each element is a string and takes up three memory words. The array is stored at location 1120 decimal. The starting address of A[49] is
A
1267
B
1164
C
1264
D
1169
       Data-Structures       Arrays       ISRO CS 2009
Question 34 Explanation: 
Given data is each string takes up three memory words which is nothing but size is 3.
Base or starting address of the array is 1120.
The address of the 49th element = base address of array + number of elements before current element * size of element
= 1120 + 48 * 3 = 1264
Question 35
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A
A
B
B
C
C
D
D
       Data-Structures       Queues-and-Stacks       ISRO CS 2009
Question 35 Explanation: 

Question 36
A full binary tree with n leaves contains:
A
n nodes
B
log2 n nodes
C
2n-1
D
2n
       Data-Structures       Binary-Trees       ISRO CS 2009
Question 36 Explanation: 
A Binary Tree is full if every node has 0 or 2 children. So, in such case, the binary tree with n leaves contains a total of 2*n-1 nodes.

Question 37
The expression 1 * 2 ^ 3 * 4 ^ 5 * 6 will be evaluated as
A
3230
B
16230
C
49152
D
173458
       Data-Structures       Prefix-Postfix-Expression       ISRO CS 2009
Question 37 Explanation: 
The expression consists of the following operators *, ^
Between * and ^ , operator ‘^’ is highest precedence so it will execute first.
The expression consists of more than one ‘^’ operator is presented then it will follow right to left associativity.
Multiplication operator associativity is left to right.
1 * 2 ^ 3 * 4 ^ 5 * 6 = 1 * (2 ^ 3)* (4 ^ 5) * 6
= 1 * 8 * 1024 * 6
= 49152
Question 38
How many distinct binary search trees can be created out of 4 distinct keys?
A
5
B
14
C
24
D
35
       Data-Structures       Binary-search-tree       ISRO CS 2011
Question 38 Explanation: 
The number of distinct BST for n nodes are given as ((2n)Cn)/(n+1)
So, for 4 distinct nodes, we can have (8C4)/5 = 14 distinct BSTs
Question 39
If node A has three siblings and B is a parent of A, what is the degree of A?
A
0
B
3
C
4
D
None of the above
       Data-Structures       Graphs       ISRO CS 2011
Question 39 Explanation: 
The degree of a vertex of a graph is the number of edges incident to the vertex, and in a multigraph, loops are counted twice.
According to question, there is no information regarding children nodes of node “A”. So the degree of A is 0.
Question 40
Consider the following pseudocode:
x:=1;
i:=1;
while (x ≤ 500)
begin
x:=2x ;
i:=i+1;
end
What is the value of i at the end of the pseudocode?
A
4
B
5
C
6
D
7
       Data-Structures       Programming       ISRO CS 2011
Question 40 Explanation: 
After completion of first iteration x and i values are : x = 2 and i = 2
After completion of second iteration x and i values are : x = 4 and i = 3
After completion of third iteration x and i values are : x = 16 and i = 4
After completion of fourth iteration x and i values are : x =256 and i = 5
After completion of fifth iteration x and i values are : x = 65536 and i = 6(Condition is false)
Then the value of “i” is 5
Question 41
The average depth of a binary search tree is:
A
O(n0.5)
B
O(n)
C
O(log n)
D
O(n log n)
       Data-Structures       Binary-search-tree       ISRO CS 2011
Question 41 Explanation: 
A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right.
The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.
The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.
The average depth of a binary search tree is log(n)
Question 42
The in-order traversal of a tree resulted in FBGADCE. Then the pre-order traversal of that tree would result in
A
FGBDECA
B
ABFGCDE
C
BFGCDEA
D
AFGBDEC
       Data-Structures       Tree-traversal       ISRO CS 2011
Question 42 Explanation: 
→ In order traversal properties are left,root and right.
→ Pre order properties are root,left and right
→ Based on the given sequence, we will get binary tree is

→ Based upon the inorder traversal, we will get preorder sequence is ABFGCDE.
Question 43
A symbol table of length 152 is processing 25 entries at any instant. What is occupation density?
A
0.164
B
127
C
8.06
D
6.08
       Data-Structures       ISRO CS 2011
Question 43 Explanation: 
Given data,
Symbol table length=152,
Number of entries=25,
Occupation density=?
Step-1: To find Occupation density require number of entries and length of symbol table.
Occupation Density = Number of entries/ Length of symbol table
= 25/152
= 0.164
Question 44
The following steps in a linked list
p = getnode()
info (p) = 10
next (p) = list
list = p
result in which type of operation?
A
pop operation in stack
B
removal of a node
C
inserting a node
D
modifying an existing node
       Data-Structures       Programming       ISRO CS 2013
Question 44 Explanation: 
p = getnode() // Allocating memory for node and starting address of that node will store in the pointer “p”
info (p) = 10 // Storing the value of 10 into the info field of new node
next (p) = list // adding new node to the existing list.
list=p // the starting address of the list will
point to the new node
Question 45
Which of the following number of nodes can form a full binary tree?
A
8
B
15
C
14
D
13
       Data-Structures       Binary-Trees       ISRO CS 2013
Question 45 Explanation: 
A full binary tree is a tree in which every node other than the leaves has two children. In short, a full binary tree with N leaves contains 2N - 1 nodes.

Question 46
In an array of 2N elements that is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?
A
1
B
2
C
N/2
D
2N-1
       Data-Structures       Array       ISRO CS 2013
Question 46 Explanation: 
Given data,
Array=2N elements
Elements are used 2-ordered and 3-ordered
Step-1: If array used 2-ordered, if it contains an element which is at most two positions away from its original position in a sorted array.
Sep-2: Maximum number of positions that an element can be from its position if the array were
1-ordered = 1
Question 47
Consider the following pseudocode: x : integer := 1 y : integer := 2 procedure add x := x + y procedure second (P: procedure) x : integer := 2 P() procedure first y : integer := 3 second(add) first() write_integer (x) What does it print if the language uses dynamic scoping with deep binding?
A
2
B
3
C
4
D
5
       Data-Structures       Programming       ISRO CS 2013
Question 47 Explanation: 
Scope rule:
The “current” binding for a given name is the one encountered most recently during execution
Dynamic scoping :
The scope of bindings is determined at run time not at Compile time .
→ For deep binding, the referencing environment is bundled with the subroutine as a closure and passed as an argument. A subroutine closure contains
– A pointer to the subroutine code
– The current set of name-to-object bindings
→ By considering dynamic scoping with deep binding when add is passed into second the environment is x = 1, y = 3 and the x is the global x so it writes 4 into the global x, which is the one picked up by the write_integer.
Question 48
The number of rotations required to insert a sequence of elements 9,6,5,8,7,10 into an empty AVL tree is?
A
0
B
1
C
2
D
3
       Data-Structures       AVL-tree       ISRO CS 2013
Question 48 Explanation: 
Step-1: Initially, the elements are

Question 49
Let A(1:8, -5:5, -10:5) be a three dimensional array. How many elements are there in the array A?
A
1200
B
1408
C
33
D
1050
       Data-Structures       Array       ISRO CS 2013
Question 49 Explanation: 
Array declaration in C language is int A[10] which means there are 10 elements in the array. Similarly int A[10][10] means array consists of the 100 elements.
In the given question, Array is represented with lower bound and upper bound.
The following ARRAY statement defines an array containing a total of five elements, a lower bound of 72, and an upper bound of 76. It represents the calendar years 1972 through 1976: array years{72:76} first second third fourth fifth.
The following ARRAY statement arranges the variables in an array by decades. The rows range from 6 through 9, and the columns range from 0 through 9.
array X{6:9,0:9} X60-X99.
Question 50
Consider a standard Circular Queue ‘q’ implementation (which has the same condition for Queue Full and Queue Empty) whose size is 11 and the elements of the queue are q[0], q[1], q[2]…..,q[10]. The front and rear pointers are initialized to point at q[2] . In which position will the ninth element be added?
A
q[0]
B
q[1]
C
q[9]
D
q[10]
       Data-Structures       Queues-and-Stacks       ISRO CS 2014
Question 50 Explanation: 
A circular queue is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end.
The front and rear pointers are initialized to point at q[2] which means third element.
First element will add at q[3] , second element will add at q[4] and so on eight element will add at q[10].
Q[10] is the end of the queue which is connected to q[0]
So ninth element can be added at q[0] pointer
Question 51
Consider the following binary search tree T given below: Which node contains the fourth smallest element in T?
A
Q
B
V
C
W
D
X
       Data-Structures       Binary-search-tree       ISRO CS 2014
Question 51 Explanation: 
In-order traversal of binary search tree gives the ascending order of the elements.
The in-order traversal of the above tree is UQXWPVZY
So the fourth smallest element is 4th element of the inorder which is W
Question 52
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A
A
B
B
C
C
D
D
       Data-Structures       Queues-and-Stacks       ISRO CS 2014
Question 52 Explanation: 
Stack representation after inserting 5 elements
Question 53
Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order?
A
0
B
1
C
11
D
12
       Data-Structures       Hashing       ISRO CS 2014
Question 53 Explanation: 
The hash table size is 13 so the indexes are 0 to 12.So that the elements will store in to any of the 13 locations
661 mod 13 = 11
182 mod 13 = 0
24 mod 13 = 11, already filled, so after linear probing it will get index 12
103 mod 13 = 12, already filled, so after linear probing it will get index 1
Question 54
How many different trees are there with four nodes A, B, C and D ?
A
30
B
60
C
90
D
None of the above
       Data-Structures       Binary-Trees       ISRO CS 2014
Question 54 Explanation: 
For a given nodes”n” , we can get nn-2 number of different trees
n=4. Here, n is number of nodes.
44-2=16.
Given options are wrong options.
  Note: Correct answer is 16
Question 55
Which of the following is NOT represented in a subroutine activation record frame for a stack-based programming language?
A
Values of local variables
B
Return address
C
Heap area
D
Information needed to access non local variables
       Data-Structures       Queues-and-Stacks       ISRO CS 2014
Question 55 Explanation: 
Stack is used for static memory allocation and Heap for dynamic memory allocation, both stored in the computer's RAM .
Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and it's allocation is dealt with when the program is compiled
Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory . Element of the heap have no dependencies with each other and can always be accessed randomly at any time
Question 56
Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list?
A
Delete the first element of the list
B
Interchange the first two elements of the list
C
Delete the last element of the list
D
Add an element at the end of the list
       Data-Structures       Linked-List       ISRO CS 2014
Question 56 Explanation: 
1. Two pointers are pointing to first and last node in the linked list.
2. In order to delete first element , change first pointer to the next element.It won’t require length of the linked list.
3. To interchange first two elements also, We need to work with only first two nodes only.Here also no need of length of linked list.
4. To add an element at the last node, we already has one pointer which is pointing to the last node, simple add new node to last node by storing last pointer next address to new node.
5. But in order to delete last node , we need to traverse the entire list , So it requires length of the linked list. By using the last node pointer , we can’t move to previous node in the single linked list.
Question 57

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).

A
3, 14
B
3, 10
C
4, 14
D
4, 10
       Data-Structures       Heap-Tree       UGC-NET JUNE Paper-2
Question 57 Explanation: 
A heap is a MAX-Heap if all the root nodes (parent nodes) have maximum value.
Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max-heapify operation from the largest index parent node (node having 1 or more children).






The above Heap is the max-heap where each root node have maximum value.
Now depth of the Max-heap is 3 and right child of the Root node is 10.
Question 58

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 ?

A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC-NET JUNE Paper-2
Question 58 Explanation: 
h(key) = key mod 7 is the given hash function and it is mentioned that linear probing is used.
h(44) = 44 mod 7 ⇒ 2
h(45) = 45 mod 7 ⇒ 3
h(79) = 79 mod 7 ⇒ 2 (collision occurred)
h(79) = (79+1) mod 7 ⇒ 3 (collision occurred)
h(79) = (79+2) mod 7 ⇒ 4
h(55) = 55 mod 7 ⇒ 6
h(91) = 91 mod 7 ⇒ 0
h(18) = 18 mod 7 ⇒ 4 (collision occurred)
h(79) = (18+1) mod 7 ⇒ 5
h(63) = 63 mod 7 ⇒ 0 (collision occurred)
h(63) = (63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations.
Question 59

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.

 
A
3, 10, 1, 8, ___ , ___, ___.
B
1, 3, 8, 10, ___, ___, ___.
C
1, ___, 3, ___, 8, ___, 10
D
3, 10, ___, ___, 8, ___, ___.
       Data-Structures       Hashing       UGC-NET JUNE Paper-2
Question 59 Explanation: 
h(1) = ((7*1)+3) mod 4 = 2
h(3) = ((7*3)+3) mod 4 = 0
h(8) = ((7*8)+3) mod 4 = 3
h(10) = ((7*10)+3) mod 4 = 1
Question 60
___ number of leaf nodes in a rooted tree of n nodes, where each node is having 0 or 3 children.
A
n/2
B
(2n+1)/3
C
(n-1)/n
D
(n-1)
       Data-Structures       Nielit Scentist-B [02-12-2018]
Question 60 Explanation: 
→ Any n-ary tree in which every node has either 0 or n children will take L=(n-1)*I +1
[ Where L is the number of leaf nodes and I is the number of internal nodes]
→ Given data n=3.
L=(3-1)I +1
=2I +1 ------------> 1
→ To find total number of nodes is nothing but sum of leaf nodes and internal nodes
n=L+I ------------> 2
With the help of 1 and 2, we get L =(2n+1)/3/
Question 61
_____ is used to convert from recursive to iterative implementation of an algorithm
A
Array
B
Tree
C
Stack
D
Queue
       Data-Structures       Nielit Scentist-B [02-12-2018]
Question 61 Explanation: 
→ Stack is used to convert recursive to iterative implementation of an algorithm using last in first out method.
→ Stack to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes.
→ The functions follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls.
→ This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Question 62
Evaluation of the given postfix expression
10 10 +60 6 / * 8 - is:
A
192
B
190
C
110
D
92
       Data-Structures       Nielit Scentist-B [02-12-2018]
Question 62 Explanation: 
→ '10' is pushed in the stack


Question 63
___ pairs of traversals is not sufficient to build tree
A
Preorder and Inorder
B
Postorder and Inorder
C
Postorder and Preorder
D
None of these
       Data-Structures       Nielit Scentist-B [02-12-2018]
Question 63 Explanation: 
We can't build a tree without the in-order traversal.
Consider two different trees,
TREE-1
root=a;
root→ left=b;
root→ left→ right=c;
TREE-2
root=a;
root→ right=b;
root→ right→ left=c;
Both the trees are different, but have same pre-order and post-order sequence.
pre-order - a b c
post-order - c b a
Because we cannot separate the left subtree and right subtree using the pre-order or post-order traversal alone
Question 64
______ to evaluate an expression an execution without any embedded function calls
A
Two stacks are required
B
One stack is needed
C
Three stacks are required
D
More than three stacks are required
       Data-Structures       Nielit Scentist-B [02-12-2018]
Question 64 Explanation: 
Applications of stack are
Converting infix expression into post/prefix expression
Evaluating post/pre-fix expression
Parenthesis matching
With one stack also we can easily evaluate the expression.
Question 65
____ number of queues are needed to implement a stack
A
1
B
2
C
3
D
4
       Data-Structures       Nielit Scentist-B [02-12-2018]
Question 65 Explanation: 
→ Implementing stack by using two queues:
push(s,x)
1) Enqueue x to q1 (assuming size of q1 is unlimited). pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
→ Implementing queue by using two stack:
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
Question 66
The number of unused pointers in a complete binary tree of depth 5 is:
A
4
B
8
C
16
D
32
       Data-Structures       Trees       Nielit Scientist-B IT 4-12-2016
Question 66 Explanation: 
It gives ambitious answer. It may give 32 if root start from 0. It start from means 16.
Question 67
A__ is a linear list in which insertions and deletions are made to from either end of the structure.
A
Circular queue
B
Priority queue
C
Stack
D
Dequeue
       Data-Structures       Queues-and-Stacks       Nielit Scientist-B IT 4-12-2016
Question 67 Explanation: 
● A deque, also known as a double ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection.
● What makes a deque different is the unrestrictive nature of adding and removing items.New items can be added at either the front or the rear.
● Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
Question 68
What data structures is used for depth first traversal of a graph
A
Queue
B
Stack
C
List
D
None of above
       Data-Structures       Graphs       Nielit Scientist-B IT 4-12-2016
Question 68 Explanation: 
Depth First Search (DFS) algorithm traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
Question 69
In the __ traversal we process all of a vertex's descendants before we move to an adjacent vertex
A
Depth First
B
Breadth First
C
Width First
D
Depth Limited
       Data-Structures       Graphs       Nielit Scientist-B IT 4-12-2016
Question 69 Explanation: 
● Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
● Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 70
What does the following functions do for a given Linked list with first node as head?
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
A
Prints all nodes of linked lists
B
Prints all nodes of linked list in reverse order
C
Prints alternate nodes of Linked List
D
Prints alternate nodes in reverse order
       Data-Structures       Linked-List       Nielit Scientist-B CS 22-07-2017
Question 70 Explanation: 
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.
Input : Head of following linked list
1->2->3->4->NULL
Output : Linked list should be changed to,
4->3->2->1->NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr->next
// Now change next of current
// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Question 71
Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
 temp=current → prev;
 Current → prev=current → next;
 Current → next=temp;
 current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <-->  2 <--> 3 <--> 4<--> 5 <--> 6. What should be the modified linked list after the function call?
A
1<-->2<-->4<-->3<-->6<-->5
B
5<-->4<-->3<-->2<-->1<-->6
C
6<-->5<-->4<-->3<-->2<-->1
D
6<-->5<-->4<-->3<-->1<-->2
       Data-Structures       Linked-List       Nielit Scientist-B CS 22-07-2017
Question 71 Explanation: 
Struct node *current=*head_ref; ---> This statement meant for storing start of linked list onto current pointer.
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
Question 72
Following is C like Pseudo code of a function that takes a number as an argument, and uses a stack S to do argument, and uses a stack S to do processing.
void fun(int n)
{
Stack s;//Say it creates an empty stack S
while(n>0)
{
 // This line pushes the value of n%2 to
 Stack S;
 Push(&S,n%2);
 n=n/2l
}
// Run while Stack S is not empty
while(!is Empty(&S)) Printf(%d",pop(&S));//pop an element from S and print it
}
What does the above function do in general order
A
Prints binary representation of n in reverse order
B
prints binary representation of n
C
Prints the value of Logn
D
Prints the value of Logn in reverse order
       Data-Structures       Queues-and-Stacks       Nielit Scientist-B CS 22-07-2017
Question 72 Explanation: 
For any number, we can check whether its ‘i’th bit is 0(OFF) or 1(ON) by bitwise ANDing it with “2^i” (2 raise to i).,
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit == 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integer (32 bit), which consist of 0-31 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number. void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
Question 73
Assume that the operators +,-,x are left associative and 6 right associative. the order of precedence(from highest to lowest) is 6,x,+,-. The postfix expression corresponding to the infix expression a+bxc-d^e^f is
A
abc x+def^^-
B
abc xde^f^-
C
ab +c xd -e^f ^
D
-+ a x bc ^^def
       Data-Structures       Queues-and-Stacks       Nielit Scientist-B CS 22-07-2017
Question 73 Explanation: 
a+bc-d^e^f
⟶ left to right
Step 1: abc+
Question 74
A balance factor in AVL tree is used to check
A
What rotation to make
B
if all childs nodes are at same level
C
when the last rotation occurred
D
if the tree is unbalanced
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 22-07-2017
Question 74 Explanation: 
It is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
Question 75
A full binary tree with n non-leaf nodes contains
A
log​ 2​ n nodes
B
n+1 nodes
C
2n nodes
D
2n+1 nodes
       Data-Structures       Binary-Trees       Nielit Scientist-C 2016 march
Question 75 Explanation: 
● A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children
● In a binary tree - a tree where each non-leaf node has exactly two sons - number of leaves is n+1. Total number of nodes is 2n+1.
Full Binary Tree:

In the above tree,non-leaf nodes are 7 so total nodes are 2x7+1=15
Question 76
A priority queue is implemented as a Max-heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10,8,5,3,2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is
A
10,8,7,3,2,1,5
B
10,8,7,2,3,1,5
C
10,8,7,1,2,3,5
D
10,8,7,5,3,2,1
       Data-Structures       Queues-and-Stacks       Nielit Scientist-B CS 22-07-2017
Question 76 Explanation: 
Max-Heap has 5 elements:
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 77
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT(n refers to the number of items in the QUEUE)?
A
Both operations can be performed in O(1) time
       Data-Structures       Queues-and-Stacks       Nielit Scientist-B CS 22-07-2017
Question 77 Explanation: 
Since it is mentioned in the question that both of the operations are performed efficiently. Hence even the worst case time complexity will be O(1) by the use of the Circular queue there won't be any need of shifting in the array.
Question 78
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. Total time required for this is
A
O(logn)
B
O(n)
C
O(nlogn)
D
O(n​ 2​ )
       Data-Structures       Heap-Tree       Nielit Scientist-C 2016 march
Question 78 Explanation: 
Possibility-1: Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements. O(n) complexity can be to take the ‘n’ elements of the heap and other ‘n’ elements together and construct heap So, O(n).
Possibility-2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)
Note: We can also insert all the elements once, there will be no difference on time complexity.
But according GATE solution they given possibility-1.
Question 79
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the position for the newly inserted element, the number of comparisons performed is
A
O(log​ 2​ n)
B
O(nlog​ 2​ n)
C
O(n)
       Data-Structures       Heap-Tree       Nielit Scientist-C 2016 march
Question 79 Explanation: 
Max heap is the complete binary tree that means each node has either zero children or two children except last level. So in worst case insertion of element is at last level. So, number of comparisons required at each level starting from root is equal to 1+2+4+8+16+---- this series is equal to "logn".
Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply maxheapify.
Question 80
In a circularly linked list organization, insertion of a record involves the modification of
A
no pointer
B
1 pointer
C
2 pointer
D
3 pointer
       Data-Structures       Linked-List       Nielit Scientist-C 2016 march
Question 80 Explanation: 
Suppose we have to insert node “x” after node “n1” then
x → next = n1 → next
n1 → next = x
So, we need to modify two pointers only to insert node into the linked list.
Question 81
The average search time of hashing, with linear probing will be less if the load factor
A
is far less than one
B
equals one
C
is far greater than one
D
none of these
       Data-Structures       Hashing       Nielit Scientist-C 2016 march
Question 81 Explanation: 
A critical statistic for a hash table is the load factor, defined as
Load factor= n / k
where
● n is the number of entries occupied in the hash table.
● k is the number of buckets.
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)
The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1
Question 82
A hash table with 10 buckets with one slot per bucket is depicted. The symbols, S1 to S7 are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is
A
6
B
5
C
4
D
3
E
None of the above
       Data-Structures       Hashing       Nielit Scientist-C 2016 march
Question 82 Explanation: 
Question and options are wrong. So, excluded for evaluation.
Question 83
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on DFS of G? Assume that the graph is represented using adjacency matrix
A
O(n)
B
O(m+n)
C
O(n^2)
D
O(mn)
       Data-Structures       Graphs       Nielit Scientist-B CS 22-07-2017
Question 83 Explanation: 
DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V) time, so overall the running time will be O(V2).
Question 84
In a complete k-array, every internal node has exactly k children. The number of levels in such a tree with n internal nodes is
A
nk
B
(n-1)k+1
C
n(k-1)+1
D
n(k-1)
       Data-Structures       Trees       Nielit Scientist-B CS 22-07-2017
Question 84 Explanation: 
Total nodes = nk+1 (1 for root)
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1
Question 85
Which among the following algorithm can’t be used with linked list?
A
Binary search
B
Linear Search
C
Insertion sort
D
Merge Sort
       Data-Structures       Nielit STA [02-12-2018]
Question 85 Explanation: 
→ Binary search increases the traversal steps per element in linked list just to find the middle element. This makes it slow and inefficient. Whereas the binary search on an array is fast and efficient because of its ability to access any element in the array in constant time.
→ Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
→ Insertion sort & Linear search can use linked list. Note:But Binary search also can implement using linked list but it takes O(n) time complexity.
Question 86
A program P reads in 1000 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
A
An array of 50 numbers
B
An array of 100 numbers
C
An array of 500 numbers
D
A dynamically allocated array of 550 numbers
       Data-Structures       Nielit STA [02-12-2018]
Question 86 Explanation: 
→ Here we are storing values above 50 and we are ignoring the scores which is less than 50.
→ Then using array of 50 numbers is the best way to store the frequencies.
Question 87
The catalan number for generating different binary trees is given by:
A
!2n / (!n*!(n+1))
B
C(n,2n) (n+1)
C
!n*C(2n,n) (n+1)
D
C(2n,n)/ !n
       Data-Structures       Nielit STA [02-12-2018]
Question 87 Explanation: 
→ In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).
→ Total number of possible Binary Search Trees with n different keys
BST(n)=Cn=(2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….
So are numbers of Binary Search Trees.
→ Total number of possible Binary Trees with n different keys BT(n)=BST(n)*n!
Question 88
A hash function f defined as f(key)=key mod 7, with linear probing, insert the keys 37,38,72,48,98,11,56 into a table indexed from 11 will be stored in the location
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       Nielit Scientist-B CS 2016 march
Question 88 Explanation: 
The hash starts from 0th index.
37%7=2
38%7=3
72%7=2. Here, collision happened because already index 2 is already filled by 37.
According to linear probing, increment index value by 1.
2+1=3 but index 3 also filled with 38 element. So, again increment by 1.
72%7=2( getting index position in hash table ​ 4 ​ )
48%7=6
98%7=0
11%7=4. Here, collision happened because already index 4 is already filled by 72.
According to linear probing, increment index value by 1.
11%7=4 (getting index position in hash table ​ 5 ​ )
56%7=0Here, collision happened because already index 0 is already filled by 98.
According to linear probing, increment index value by 1.
56%7=0 (getting index position in hash table ​ 1 ​ )
Question 89
traversing a binary tree first root and then left and right subtree called__ traversalt
A
postorder
B
preorder
C
inorder
D
none of these
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 2016 march
Question 89 Explanation: 
In order:​ The left subtree is visited first, then the root and later the right subtree.
Pre order:​ The root node is visited first, then the left subtree and finally the right subtree.
Post order:​ First we traverse the left subtree, then the right subtree and finally the root node.
Question 90
Given the sequence of nodes {11,6,8,19,4,10,5,17,43,49,31} not necessarily in correct order for generating binary search tree. The corresponding postorder traversal of the BST is:
A
5,4,10,8,6,49,31,43,19,17,11
B
4,5,6,8,10,11,19,17,43,31,49
C
4,5,8,10,6,17,31,49,43,19,11
D
5,4,10,8,6,17,31,49,43,19,11
       Data-Structures       Nielit STA [02-12-2018]
Question 90 Explanation: 

Post order: 5,4,10,8,6,17,31,49,43,19,11
Question 91
A hash table has space for 100 records. then the probability of collision before the table is 10% full, is
A
0.45
B
0.5
C
0.3
D
0.34(approximately)
       Data-Structures       Hashing       Nielit Scientist-B CS 2016 march
Question 91 Explanation: 
Here, we can get the answer using 1-Probability of no collision for first 10 entries.
So, 1- (100*99*98*97*96*95*94*93*92*91)/100​ 10​ ⇒ 0.37(approximately)
Question 92
A complete binary tree with the property Kni>=Kcn where Kn is nthnode value and Kc be the value of its child node is called:
A
B+ tree
B
Threaded binary tree
C
Heap
D
AVL tree
       Data-Structures       Nielit STA [02-12-2018]
Question 92 Explanation: 
A complete binary tree with the property Kni>=Kcn where Kn is nthnode value and Kc be the value of its child node is called heap
Question 93
___ is a parameter passing method that waits to evaluate the parameter value until it is used?
A
Pass by value
B
Pass by name
C
Pass by reference
D
Pass by pointer
       Data-Structures       Nielit STA [02-12-2018]
Question 93 Explanation: 
Pass by value: The method parameter values are copied to another variable and then the copied object is passed, that’s why it’s called pass by value.
Pass by reference: An alias or reference to the actual parameter is passed to the method.Passing a pointer to the actual parameter, and indirect through the pointer
Pass by name: re-evaluate the actual parameter on every use. For actual parameters that are simple variables, this is the same as call by reference. For actual parameters that are expressions, the expression is re-evaluated on each access.
There is no parameter passing method with the name “ Pass by pointer”
Question 94
Suppose that we have an MxN array ‘A’ in row major order, where the size of the elements is S. Then the location of A[i,j] elements is given by:
A
A+i*N*S
B
A+(i*N+j)*S
C
A+(i*N+j*M)*S
D
A+(i*M+j*N)*S
       Data-Structures       Nielit STA [02-12-2018]
Question 94 Explanation: 
“A” is the base address,
M is number of the rows and N is number of Columns and S is size of the element.
The elements are storing row major order. So the elements are in the following order.
A[1,1],A[1,2],A[1,3] ….. A[1,N]
A[2,1],A[2,2],A[2,3]........A[2,N]
……
….
A[M,1],A[M,2],A[M,3]........A[M,N]
We will get the location of A[i,j] by using formula A+(i*N+j)*S where “i” is the index of the row and “j” index of the column and “N” is number of columns.
Question 95

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

A
11
B
12
C
10
D
9
       Data-Structures       Trees       UGC-NET DEC Paper-2
Question 95 Explanation: 
Number of internal nodes= 4+3+3 = 10
Number of leaf nodes = Sum of degrees of all internal nodes - number of internal nodes +1
= (4*1 + 3*2 + 3*3 ) - 10 + 1
= 19 - 10 + 1
= 10
Formula: nd - n + 1 where n is number of nodes and d is degree of the tree.
Question 96

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.

A
20, 20
B
3, 20
C
3, 5
D
20, 5
       Data-Structures       ADT       UGC-NET DEC Paper-2
Question 96 Explanation: 
→ char is a fixed-length data type, the storage size of the char value is equal to the maximum size for this column.
→ varchar is a variable-length data type, the storage size of the varchar value is the actual length of the data entered, not the maximum size for this column.
→ So, A varchar(20) has only 3 spaces because its initialized to 'xyz' and B char(20) has 20 spaces as char data type occupies the storage space equivalent to the maximum size.
Question 97

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 subtree is

A
7
B
6
C
3
D
5
       Data-Structures       Binary-search-tree       UGC-NET DEC Paper-2
Question 97 Explanation: 
Question 98

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 ?

A
O(1)
B
O(lg n)
C
O(n)
D
O(n lg n)
       Data-Structures       Linked-List       UGC-NET DEC Paper-2
Question 98 Explanation: 
If we have pointer to the tail of the list in order to delete it, which can be obtained by traversing the list which takes O(n) time.
Question 99

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 :

A
6, 3
B
8, 1
C
8, 2
D
6, 2
       Data-Structures       Prefix-Postfix-Expression       UGC-NET DEC Paper-2
Question 99 Explanation: 
For evaluating a postfix expression we start traversing from first element of the expression.
While traversing the expression if you find an element value then push it on the top of stack this way the top element of the stack will represent the second operand of an operation and the element presents after top element will represent the first operand of the operation.
While traversing the postfix expression if you find an operation symbol then pop 2 elements from the top of the stack and then after performing operation store it’s result on the top of stack.
Step 1:

Step 2:

Step 3:
Step 4:

So Pop top 2 elements from stack and save the result on the top of stack.
2*3=6

Step 5:

Again Repeat step-4.
6/6=1

Step 6:


Step 7:


Step 8:

Do what we did in step-4.
4*2 = 8
Question 100

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

A
<42, 35, 40, 22, 25, 26, 30>
B
<42, 35, 40, 22, 25, 30, 26>
C
<42, 40, 35, 25, 22, 26, 30>
D
<42, 40, 35, 25, 22, 30, 26>
       Data-Structures       Heap-Tree       UGC-NET DEC Paper-2
Question 100 Explanation: 
After inserting each element we will apply MAX-Heapify operation to get the MAX-Heap.
The resultant MAX_Heap will look like

<42, 40, 35, 25, 22, 30, 26>
Question 101
In a binary max heap containing n numbers, the smallest element can be found in time
A
O(n)
B
O(logn)
C
O(loglogn)
D
O(A)
       Data-Structures       Heap-Tree       NieLit STA 2016 March 2016
Question 101 Explanation: 
In Binary Max Heap, the smallest element will always be a leaf node either in left subtree or right subtree. So you have to traverse both left and right subtrees in each step to find the smallest element. So, it takes O(n) time.
Question 102
Queues serve major role in
A
Simulation of recursion
B
Simulation of arbitrary linked list
C
Simulation of limited resources allocation
D
Expression evaluation
       Data-Structures       Queues-and-Linked-Lists       NieLit STA 2016 March 2016
Question 102 Explanation: 
Recursion and Expression evaluation is implemented by using Stack.
Question 103

Consider the following minimax game tree search

What will be the value propagated at the root ?

A
6
B
3
C
5
D
4
       Data-Structures       Trees Data-Structures       UGC-NET DEC Paper-2
Question 103 Explanation: 
Question 104
Which of the following need not be a binary tree?
A
Search tree
B
Heap
C
AVL tree
D
B tree
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 4-12-2016
Question 104 Explanation: 
B trees need not be the binary tree. B trees may have more than 2 children. The order of B tree is maximum number of children a node can have.
Question 105
The maximum number of nodes in a binary tree of level k, k>=1 is:
A
2​ k​ +1
B
2​ k-1
C
2​ k​ -1
D
2​ k-1​ -1
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 4-12-2016
Question 105 Explanation: 
The number of nodes is equal to 2​ k​ -1 where k≥1. So the minimum level is 1.
For example

The minimum number of nodes 2​ 2​ -1=3
Question 106
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
A
In adjacency list representation, space is saved for sparse graphs.
B
Deleting a vertex in adjacency list representation is easier than adjacency matrix representation
C
Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
D
All of the option
       Data-Structures       Graphs       Nielit Scientist-B IT 22-07-2017
Question 106 Explanation: 
Adjacency Matrix
● Uses O(n​ 2​ ) memory
● It fast to lookup and check for presence or absence of a specific edge between any two nodes O(1)
● It slow to iterate over all edges
● It slow to add/delete a node is a complex operation O(n​ 2​ )
Adjacency List
● Use memory pending on the number of edges (not number of nodes), Which might save a lot of memory if the adjacency matrix is a sparse
● Finding the presence or absence specific edge between any two nodes Is slightly slower than with the matrix O(k) where k number of neighbors nodes
● It is fast to iterate over all edges,because you can access any node neighbors directly
● It is fast to add/delete a node is easier than the matrix representation
Question 107
what are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms?
A
Stack for BFS and Queue for DFS
B
Queue for BFS and Stack for DFS
C
Stack for BFS and Stack for DFS
D
Queue for BFS and Queue for DFS
       Data-Structures       Graphs       Nielit Scientist-B IT 22-07-2017
Question 107 Explanation: 
● Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
● Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 108
In a given following graph among the following sequences:

i)abeghf
ii)abfehg
iii)abfhge
iv)afghbe
Which are depth first traversals of the above graph?
A
I,II and IV only
B
I and IV only
C
II,III and IV only
D
I,III and IV only
       Data-Structures       Graphs       Nielit Scientist-B IT 22-07-2017
Question 108 Explanation: 
The basic idea of DFS is
● Pick a starting node and push all its adjacent nodes into a stack.
● Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack.
● Repeat this process until the stack is empty. However, ensure that the nodes that are visited are marked.
● This will prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you visit the same node more than once, you may end up in an infinite loop.
Question 109
If the sequence of operations – push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop are performed on a stack, the sequence of popped out values
A
2,2,1,1,2
B
2,2,1,2,2
C
2,1,2,2,1
D
2,1,2,2,2
       Data-Structures       Queues-and-Stacks       ISRO CS 2015
Question 109 Explanation: 

Final Pop sequence: 22112
Question 110
Ordering is immaterial as all files are accessed with the same frequency.

A
4
B
5
C
6
D
3
       Data-Structures       Hashing       ISRO CS 2015
Question 110 Explanation: 
In this, maximum size of cluster = 4 (S6, S3, S7, S1)
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisons = 4+1
= 5
Question 111
The queue data structure is to be realized by using stack. The number of stacks needed would be
A
It cannot be implemented
B
2 stacks
C
4 stacks
D
1 stack
       Data-Structures       Queues-and-Stacks       ISRO CS 2015
Question 111 Explanation: 
Step-1: Pop elements from Stack-1 and push into Stack-2.
For this,
int x=element=stack-1,pop();
stack-2.push(element);

Step-2: Once the complete stack-1 gets copied to Stack-2, then we can simply call pop() on s2, it will remove the element-1.
So, A queue can be implemented using 2 stacks.
Question 112

Considering 0-address instructions machine, what will be the top of the stack after executing the following sequence of instructions?

PUSH 15, PUSH 4, PUSH 6, MULT, PUSH 30, ADD, ADD

A
30
B
69
C
54
D
10
       Data-Structures       Queues-and-Stacks       JT(IT) 2018 PART-B Computer Science
Question 112 Explanation: 
Initially stack is empty. We are using last in first out strategy.
Step-1: PUSH 15,PUSH 4 and PUSH 6 from bottom to top. Now top of the stack value is 6.
Step-2: Perform MULT operation. 6*4=24. Now present stack values are from bottom is 15 and 24.
Step-3: Next again PUSH 30. Now top of the stack is 30.
Step-4: Perform ADD operation. 30+24=54
Step-5: Now present stack values are from bottom is 15 and 54. Perform ADD operation.
Step-6: 15+54=69
Question 113

Which of the following data structures is used in level order traversal of a binary tree?

A
Skip list
B
Stack
C
Array
D
Queue
       Data-Structures       Binary-Trees       JT(IT) 2018 PART-B Computer Science
Question 113 Explanation: 
Queue data structures is used in level order traversal of a binary tree.
Example:
Level order traversal of binary tree.
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.
printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
a) print temp_node->data
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node
Note:
Level order traversal of binary tree is time Complexity is O(n) where n is number of nodes in the binary tree.
Question 114
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is
A
2​ h
B
2​ h-1​ -1
C
2​ h+1​ -1
D
2​ h+1
       Data-Structures       Binary-Trees       Nielit Scientific Assistance IT 15-10-2017
Question 114 Explanation: 
● The number of nodes n in a full binary tree, is at least n = 2 h + 1 and at most n = 2 h+1 − 1 , where h is the height of the tree. A tree consisting of only a root node has a height of 0.
● The number of leaf nodes l in a perfect binary tree, is l = ( n + 1 )/2 because the number of non-leaf (a.k.a. internal) nodes

● This means that a perfect binary tree with l leaves has n = 2 l − 1 nodes. ● In a balanced full binary tree, h = ⎡ log 2 (l)⎤ + 1 = ⎡ log 2 ((n + 1 )/2)⎤ + 1 = ⎡ log 2 (n + 1 )⎤
● In a perfect full binary tree, l = 2 h thus n = 2 h+1 − 1
● The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is ( n + 1 ) , where only 1 node exists in bottom-most level to the far left.
●The number of internal nodes in a complete binary tree of n nodes is ⎣ n/2⎦ .
Question 115
which of the following is useful in traversing a given graph by breadth first search?
A
Stack
B
Set
C
List
D
Queue
       Data-Structures       Graphs       Nielit Scientific Assistance IT 15-10-2017
Question 115 Explanation: 
Queue can be generally thought as horizontal in structure i.e, breadth/width can be attributed to it - BFS, whereas Stack is visualized as a vertical structure and hence has depth - DFS.
Question 116
If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?
A
O(n), O(n)
B
O(n), O(1)
C
O(1), O(n)
D
O(1), O(1)
       Data-Structures       Queues-and-Stacks       Nielit Scientific Assistance IT 15-10-2017
Question 116 Explanation: 
Everyone thought that answer in worst case time is O(n) for both the cases but using circular queue, we can implement in constant amount of time.
Question 117
The number of possible binary trees with 4 nodes is
A
12
B
13
C
14
D
15
       Data-Structures       Binary-Trees       Nielit Scientific Assistance IT 15-10-2017
Question 117 Explanation: 
There is one binary tree with one node. There are two differently shaped trees with two nodes. There are 14 different (shaped) binary trees with four nodes. These different trees are shown below.
Question 118
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________
A
2
B
4
C
3
D
5
       Data-Structures       Nielit Scientist-B 17-12-2017
Question 118 Explanation: 
→ If we apply binary search to find the first occurrence of 1 in the list, it will give us the smallest index i where 1 is stored.
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
→ So number of probes = ⌈(log2 31)⌉
= ⌈4.954196310386876⌉
⇒5
Question 119
If for a given binary search tree(BST) the pre order traversal is 41,23,11,31,62,50,73. then which of the following is its postorder traversal?
A
11,31,23,50,73,62,41
B
31,11,23,50,41,62,73
C
11,31,50,23,73,62,41
D
11,31,23,50,62,73,41
       Data-Structures       Nielit Scientist-B 17-12-2017
Question 119 Explanation: 
Option B is wrong, because pre order first element is root element and post order last element is root element.
According to pre order we will get below graph based on Inorder is 11,23,31,41,50,62,73.

Question 120
If x is a one dimensional array, then:
A
*(x+i) is same as *(&x[i])
B
&x[i] is same as x+i-1
C
*(x+i) is same as *x[i]
D
*(x+i) is same as *x+i
       Data-Structures       Nielit Scientist-B 17-12-2017
Question 120 Explanation: 
⇒The statement *(x+i) means Value at “i” location of “ x address”.
⇒* is nothing but Value at address location
⇒&x[i] means address of ith element
⇒*(&x[i]) means Value at “i” location of “ x address”.
We can also write it into *(X+i) = X[i] =*(&x[i])
Question 121

In a full binary tree of height 10, the number of nodes with degree 0,1, and 2 will be ____,____ and ____ respectively.

Note: Consider height of a tree as the number of nodes in the longest path from root to any leaf node

A
512, 0, 511
B
512, 1, 510
C
511, 0, 512
D
511, 1, 511
       Data-Structures       Binary-Trees       JT(IT) 2018 PART-B Computer Science
Question 121 Explanation: 
→ Height of the full binary tree 2h -1.
Full binary tree consists of either 0 or 2 childs . So one child to the node is not possible.
The number of nodes with the degree of 1 is 0.
The nodes with degree 0 are leaf nodes, 2h-1 = 29 = 512.
The nodes with degree 2 are internal nodes 2h-1 - 1 = 511.
Question 122
On a set A={a,b,c,d} a binary operation * is defined as given in the following table. The relation is:  
A
Commutative but not associative
B
neither commutative nor associative
C
Both commutative and associative
D
Associative but not commutative
       Data-Structures       Nielit Scientist-B 17-12-2017
Question 123
The average search time for hashing with linear probing will be less if the load factor
A
Is far less than one
B
Equals one
C
Is far greater than one
D
None of the above
       Data-Structures       Hashing       Nielit Scientific Assistance IT 15-10-2017
Question 123 Explanation: 
Load factor is the ratio of number of records that are currently present and the total number of records that can be present. If the load factor is less, free space will be more. This means probability of collision is less. So, the search time will be less.
Question 124

Consider an AVL tree constructed by inserting the elements 18, 10, 5, 3, 27, 7, 35, 43, 32 one by one. Which of the following options give the number of comparisons to search the key value 45 in this AVL tree?

A
5
B
4
C
3
D
2
       Data-Structures       Binary-Trees       JT(IT) 2018 PART-B Computer Science
Question 124 Explanation: 
Question 125
In binary search tree which traversal is used for getting ascending order values?
A
Inorder
B
Preorder
C
Postorder
D
None of the above
       Data-Structures       Nielit STA 17-12-2017
Question 125 Explanation: 
To traverse a binary search tree in inorder following operations are carried-out
(i) Traverse the left most subtree starting at the left external node,
(ii) Visit the root, and
(iii) Traverse the right subtree starting at the left external node.
The Inorder traversal of the above tree will outputs: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Question 126
If file size is large and if it is to be accessed randomly then which of the following allocation strategy should be best to use in a system?
A
Linked allocation
B
Indexed allocation
C
Contiguous allocation
D
None of the options
       Data-Structures       Nielit STA 17-12-2017
Question 126 Explanation: 
Contiguous:All blocks of a file are stored contiguously.
Advantages:
Faster access as all blocks are nearby.
Suitable for small sequentially accessed file
Disadvantages:
Poor performance if file grows or shrinks.

Linked Allocation:Each block stores pointer to next block
Advantages:
No fragmentation.
Suitable for large sequentially accessed file
Disadvantages:
Random access is not possible, If one link is lost, cannot access subsequent blocks
Note: In File Allocation Table (FAT) all links are cached in a table for faster access.

Indexed Allocation:A single bock stores indexes of all blocks of a file.
Advantage:
Suitable for large randomly accessed file
Eg: UNIX inode stores the first 12 or so data block pointers and then singly, doubly, and triply indirect pointers.
Question 127
In a full binary tree number of nodes is 63 then the height of the tree is:
A
2
B
4
C
3
D
6
       Data-Structures       Nielit STA 17-12-2017
Question 127 Explanation: 
⌈log2n⌉
=log263
=6
Question 128
The 2-3-4 tree is a self balancing data structure, which is also called:
A
2-4 tree
B
B+ tree
C
B-Tree
D
None of the options
       Data-Structures       Nielit STA 17-12-2017
Question 128 Explanation: 
In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that is commonly used to implement dictionaries.
The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:
→ a 2-node has one data element, and if internal has two child nodes;
→ a 3-node has two data elements, and if internal has three child nodes;
→ a 4-node has three data elements, and if internal has four child nodes.
Question 129
The average search time of hashing, with linear probing will be less if the load factor:
A
is far less than 1
B
equals 1
C
is far greater than 1
D
none of the options
       Data-Structures       Nielit STA 17-12-2017
Question 129 Explanation: 
→ In other words, insert, remove and search operations can be implemented in O(1), as long as the load factor of the hash table is a constant strictly less than one.
Question 130
Which of the following is illegal declaration in C language?
A
char*str="Raj is a research scholar";
B
charstr[25]="Raj is a research Scholar";
C
charstr[40]="Raj is a research Scholar";
D
char[] str="Raj is a research Scholar";
       Data-Structures       Nielit STA 17-12-2017
Question 130 Explanation: 
The initialization of variable in option D is not valid.
Variable initialization syntax : Datatype varible_name[size]="sring"
(or)
Datatype variable_name[ ]=”string”
Question 131
The address field of linked list:
A
contain address of next node
B
may contain null character
C
contain address of next pointer
D
both (A) and (B)
       Data-Structures       Nielit STA 17-12-2017
Question 131 Explanation: 
→ Each record of a linked list is often called an 'element' or 'node'.
→ The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'.
→ The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields. Note: Option C is also correct.
Question 132
The expression 5-2-3*5-2 will evaluate to 19, if:
A
'-' is left associative and '*' has precedence over '-'
B
'-' is right associative and '*' has precedence over '-'
C
'-' is right associative and '-' has precedence over '*'
D
'-' is left associative and '-' has precedence over '*'
       Data-Structures       Nielit STA 17-12-2017
Question 132 Explanation: 
Evaluation procedure:
Step-1: 5-2-3*5-2 will be 19.
Step-2: if it is treated as (5-(2-3))*(5-2)
Step-3: - has precedence over * and if it associates from the right.
Question 133
Which of the following is the correct declaration of linked list?
A
Struct node*
{
Int data;
node*link;
}
B
Struct node
{
int data;
Struct node*link;
}
C
Struct node
{
int data;
node link;
}
D
Struct node*
{
int data;
struct node*link;
}
       Data-Structures       Linked-List       KVS 22-12-2018 Part-B
Question 133 Explanation: 
Declaration syntax is
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};
Question 134
The worst case complexity for searching an element in binary search tree is:
A
O(lgn)
B
O(nlogn)
C
O(n2)
D
O(n)
       Data-Structures       Binary-search-tree       KVS 22-12-2018 Part-B
Question 134 Explanation: 
→ The worst case scenario is when a binary search tree(skew tree) is fully degenerate, a binary search tree is a chain of n nodes.
→ The worst-case time complexity of a search in a binary search tree is O(n).
Question 135
Which of the following applications may use a stack?
(a) Parenthesis balancing program
(b) Process scheduling operating system
(c) Conversion of infix arithmetic expression to postfix form
A
(a) and (b)
B
(b) and (c)
C
(a) and (c)
D
(a),(b) and (c)
       Data-Structures       Queues-and-Stacks       KVS 22-12-2018 Part-B
Question 135 Explanation: 
Process scheduling operating system is application of queue.
Question 136
Given the list of tasks in Col-A and list of data structure in Col-B. Identify the best match
A
(i) (iii) (ii)
B
(ii) (i) (iii)
C
(iii) (ii) (i)
D
(ii) (iii) (i)
       Data-Structures       Queues-and-Stacks       KVS 22-12-2018 Part-B
Question 136 Explanation: 
→ Recursion is implemented stack
→ Scheduling can be implemented using Queue.
→ The inorder traversal of binary search gives sorting order.
Question 137
A binary search tree contains the values- 1,2,3,4,5,6,7 and 8. The tree is traverses in preorder and the values are printed out. Which of the following sequences is a valid output?
A
5 3 1 2 4 7 8 6
B
5 3 1 2 6 4 9 7
C
5 3 2 4 1 6 7 8
D
5 3 1 2 4 7 6 8
       Data-Structures       Binary-Trees       Nielit Scientific Assistance CS 15-10-2017
Question 137 Explanation: 
Preorder traversal yields (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.
Question 138
For which of the following tasks, stack is not suitable data structure?
(a) Binary search in an array
(b) Breadth first search
(c) Implementing function calls
(d) Process scheduling
A
(b) and (d)
B
(b) and (c)
C
(a) and (c)
D
(c) and (d)
       Data-Structures       Queues-and-Stacks       KVS 22-12-2018 Part-B
Question 138 Explanation: 
Breadth first search and Process scheduling can be implemented by using Queue.
Binary search can be implemented by using recursion. So Stack is suitable for implementing function calls.
Question 139
When a circular queue is implemented in an array of the following condition holds when there is only one element in the queue?
A
Front=rear=null
B
Front=Rear!=null
C
Front=Rear+1
D
Front=Rear-1
       Data-Structures       Queues-and-Stacks       KVS 22-12-2018 Part-B
Question 139 Explanation: 
Front and rear initially points to same location and once rear is incremented by 1 it means element is added and front is used to delete so here we don't need front for 1 element in the queue.
Question 140
The elements of the triangular array are stored as a vector in the A[1,1], A[2,1],A[2,2],A[3,1] A[3,2], A[3,3]..A[n,n] Assuming that A[1,1] is stored at location 1, addressing function for A[i,j] is given by;
A
(i-1)/2 +j
B
((i-1)*i)/2 +j
C
(i*i)/2 +j
D
(i*j-1)/2
       Data-Structures       Arrays       KVS 22-12-2018 Part-B
Question 140 Explanation: 
This is lower triangular matrix. For 4,4 we need to cross 4 rows and 4 columns. So, most suitable answer is Option C.
Question 141
An array is
A
Probably the most widely used data structure
B
A homogeneous structure
C
A random access structure
D
All of these
       Data-Structures       Arrays       KVS DEC-2013
Question 141 Explanation: 
● An array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.
● An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.
● Memory is allocated homogeneously and we can access any element by using index value.
Question 142
The figure below represents a
A
Binary tree
B
Recursive tree
C
Insert sort
D
Unitary tree
       Data-Structures       Binary-Trees       KVS DEC-2013
Question 142 Explanation: 
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Question 143
An important quantitative measure of the complexity of a binary tree is its__. It also provides a measure of the average depth of all nodes in the tree
A
Average path length
B
Median path length
C
Mode path length
D
Simple deviation path length
       Data-Structures       Binary-Trees       KVS DEC-2013
Question 143 Explanation: 
The number of decisions or, alternatively, the number of branches traversed, in reaching a node is called the path length or path to the node.
Question 144
The following figure is a____ tree after zig-zig rotations
A
Heap
B
Bubble
C
Splay
D
Binary
       Data-Structures       Trees       KVS DEC-2013
Question 144 Explanation: 
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.
Question 145
Representation of data structure in memory is known as
A
Recursive
B
Abstract data type
C
Storage Structure
D
File structure
       Data-Structures       ADT       KVS DEC-2013
Question 145 Explanation: 
An abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations
Question 146
The largest element of an array index is called its
A
Lower bound
B
Range
C
Upper bound
D
All of these
       Data-Structures       Arrays       KVS DEC-2013
Question 146 Explanation: 
Consider the array with “n” elements . smaller index value is 0(lower bound) and lager index value is “n-1”(upper bound)
Question 147
In the context of visual basic, multiple controls of the same type can be grouped into an array, in the same manner as a collection of data items. Such a grouping is known as
A
Control array
B
Primary array
C
Secondary array
D
An integer array
       Data-Structures       Arrays       KVS DEC-2017
Question 147 Explanation: 
A control array is a group of controls that share the same name type and the same event procedures. Adding controls with control arrays uses fewer resources than adding multiple control of same type at design time.
A control array can be created only at design time, and at the very minimum at least one control must belong to it.
Features:
1. Controls that belong to the same control array share the same set of event procedures; this often dramatically reduces the amount of code you have to write to respond to a user's actions.
2. We can dynamically add new elements to a control array at run time; in other words, you can effectively create new controls that didn't exist at design time.
3. Elements of control arrays consume fewer resources than regular controls and tend to produce smaller executables. Besides, Visual Basic forms can host up to 256 different control names, but a control array counts as one against this number. In other words, control arrays let you effectively overcome this limit.
Question 148
Which of the following data structures is most suitable for evaluating postfix expressions?
A
Tree
B
Stack
C
Linked List
D
Queue
       Data-Structures       Queues-and-Stacks       KVS DEC-2017
Question 148 Explanation: 
Postfix Expression are usually converted from infix Expression using Stack Data structure.
Algorithm
We have Postfix[ ] Array, Stack, Infix[ ] Array
1. Scan the given expression (Infix ) from Left to Right [ one character at a time].
2. Check Whether the given character is an operator [+, -, *, /, ^ etc] or operand.
3. If it is an operand, then copy it in the Prefix Array.
4. If it is a operator then,
1. Check whether, Stack is empty or not
2. If it is empty then, push the operator in the stack and go to step
3. If Stack is not empty then compare the precedence of Top of stack with operator.
4. If the Top of Stack has higher or equal precedence then pop it and copy in the postfix array.
5. If the operator has higher precedence, push it in the stack and go to step 5.
6. If Stack is not empty go back to step 4(1).
5. Continue solving the expression in usual manner until the expression come to end.
6. Pop the remaining operand in the stack and copy it to postfix array.
Question 149
Remove procedure is implemented using
A
String
B
Queue
C
Stack
D
Linked list
       Data-Structures       Queues-and-Stacks       KVS DEC-2017
Question 149 Explanation: 
→ Every processor provides us with some form of call instruction, which pushes the address of the next instruction on the stack and transfers control to the address specified by the call.
→ When the called procedure is done, it issues a return instruction, which pops the address from the top of the stack and transfers control there.
→ That’s just the basic processor mechanism that makes it easy to implement procedure calls. The actual details of identifying the parameters, placing them on the stack, executing a call instruction are up to the compiler.
→ In the called function, the compiler is responsible for ensuring any registers that may be clobbered are saved, allocating stack space for local variables, and then restoring the registers and stack prior to a return.
Question 150
For a tree just one node, the root node is the height of a binary tree is defined to zero, if there are 2 levels of nodes, the height is 1 and so on. A binary search tree is built according to the usual rules with the following six key inserted one at a time as given B,I,N,A,R,Y. What is the height of the tree?
A
5
B
2
C
3
D
4
       Data-Structures       Binary-search-tree       KVS DEC-2017
Question 150 Explanation: 
Step-1: Given data, binary tree starts with height 0. It means root node.
Step-2: According to BST, the properties are left child is smaller than his root node and right subtree is greater than his root node.
Step-3: They given characters B,I,N,A,R,Y. And corresponding alphabetical number are B=2,I=9,N=14,A=1,R=18,Y=25.
Question 151

Which of the following is wrong while inserting a node in the beginning of list?

A
Obtain a node from available list
B
Make the next pointer of the current head pointer to new node
C
Make the node pointer of the list pointer to new node
D
Make the next pointer of the new node pointer to current head of the list
       Data-Structures       Linked-List       JT(IT) 2016 PART-B Computer Science
Question 151 Explanation: 
• Option A: If we want to insert a node but the node is already in available list we can’t insert a node at beginning.
• Option B, C and D: It shows actual procedure to insert a node at beginning. So, Option A is wrong
Question 152
For the following binary tree, in operate the traversal yields the expression
A
-+*/abdef
B
a+bd*-ef/
C
abdef*/+-
D
a+b*d-e/f
       Data-Structures       Binary-Trees       KVS DEC-2017
Question 152 Explanation: 
Here, inoperate the traversal yields the expression means INORDER.
Inorder→ left,root and right.
a+b*d-c/f
Question 153
The five items P<Q<R
A
S
B
P
C
Q
D
R
       Data-Structures       Queues-and-Stacks       KVS DEC-2017
Question 153 Explanation: 
Step-1: Initially P,Q,R,S and T are pushed in a stack. The stack elements will be placed in LIFO manner. It beans that bottom of the stack value from P to T.
Step-2: Then we have to pop 4 elements. So, present having only one element,that is P.
Step-3: 4 elements we have to insert into a Queue. Queue follows FIFO manner.
Step-4: Again we have to delete two elements from queue and inserted into stack.
Step-5: The inserted elements are T and S.
Step-6: Final pop element is S.
Step-7: Stack having only two elements. P and T.
Question 154
If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively and each element occupies 2 bytes, then the array has been stored in ____ order
A
Row major order
B
Column major
C
Matrix major
D
Simple
       Data-Structures       Arrays       KVS 30-12-2018 Part B
Question 154 Explanation: 
→Row-major order and column-major order are methods for storing multidimensional arrays in linear storage such as random access memory.
→First element address is 1000 and Second element address is 1002 and so on
→A[2][1] means Second row first element whose address is 1010.
Question 155
If an array is declared as Int a[5]={3,0,1,2}, then values assigned to a[0] and a[4] will be
A
3,2
B
0,2
C
3,0
D
0,4
       Data-Structures       Arrays       KVS 30-12-2018 Part B
Question 155 Explanation: 
→A[0] is first element and a[4] means 5th element. Array is declared for 5 elements are only four elements are initialized and the default value is 0.
→The first value is 3 and a[4] value is 0
Question 156
Array A[8,15] is sorted in row major order with first element A[1,1] stored at location A0. Assuming that each element of the array is size of size s, element A[i,j] can be accessed at
A
A0 + 15s(i-1)+(j-1)
B
A0 + 8s(i-1)+(j-1)
C
A0 + 15s(j-1)+(i-1)
D
A0 + 8s(j-1)+(i-1)
       Data-Structures       Arrays       KVS 30-12-2018 Part B
Question 156 Explanation: 
The element A[i,j] can be accessed by using the following formulae
A[i,j]=Base address+ j*sizeof the array(i-1)+(j-1)
Question 157
Consider a single dimension array A[n], which houses two stacks as shown in the figures. A[1] is the bottom of stack A and A[n] is the bottom of stack B.

If nA is the number of elements in stack A and nB is the number of elements in stack B, then overflow occurs when Push Operation is performed on either stack and
A
nA=nB
B
nA=nB=n
C
nA+nB=n
D
nA+nB>=n
       Data-Structures       Queues-and-Stacks       KVS 30-12-2018 Part B
Question 157 Explanation: 
→nA is the number of elements in stack A and nB is the number of elements in stack B, Where “n” is total elements we can insert into stack.
→The sum of the nA and nB is equal to the number of elements there is no possibility of inserting element into stack.
Question 158
Translation of infix string a+b*c-d/e*h to postfix form is
A
abc*+deh/*-
B
ab+c*de/h*-
C
(a b c*)+(de/h*-)
D
abc*+de/h*-
       Data-Structures       Queues-and-Stacks       KVS 30-12-2018 Part B
Question 158 Explanation: 
The infix string a+b*c-d/e*h.
=a+[bc*]-d/e*h // Select highest priority operators and convert into postfix form,If same priority then go for associativity
=a+[bc*]-[de/]*h
=a+[bc*]-[de/h*]
=[abc*+]-[de/h*]
=abc*+de/h*-
Question 159
Queue is an appropriate data structures for
a) Implementation breadth first search
b) Implementation depth first search
c) Process scheduling
Which of the following is the correct option?
A
a and b
B
a and c
C
b and c
D
a,b and c
       Data-Structures       Queues-and-Stacks       KVS 30-12-2018 Part B
Question 159 Explanation: 
→Various Queues like Ready queue,Job Queue , Waiting Queue and so on are used in the operating system for process scheduling.
→Queue is also used for Breadth first traversal also
Question 160
A full binary tree with height h has _____ nodes.(Assume leaves at h=0)
A
2h-1
B
2h+1
C
2h+1-1
D
2h+1+1
       Data-Structures       Binary-Trees       KVS 30-12-2018 Part B
Question 160 Explanation: 
→A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.
→The height of the binary tree is the longest path from root node to any leaf node in the tree
Question 161
A complete n-ary tree is one in which every node has 0 or n children. If there are x internal nodes in a complete n-ary tree, the number of leaves is
A
(n-1)x+1
B
(n-1)x-1
C
nx+1
D
nx-1
       Data-Structures       Trees       KVS 30-12-2018 Part B
Question 161 Explanation: 
Consider binary tree with two children.
Then n value is 2 and internal node is 1 then the number of leaves are (2-1)1+1=2 leaves.
Question 162
Given m and n as pointers to two linked lists, what does the following functions do? Void op(node *m,node *n) { Node *p=m; while(P→ next !=null) { P=P→ next; } P→ next=n; }
A
Always appends list ‘m’ at the end of list ‘n’
B
Always appends list ‘n’ at the end of list ‘m’
C
Append list ‘m’ at the end of list ‘n’ with possibility of error
D
Appends list ‘n’ at the end of list ‘m’ with possibility of error
       Data-Structures       Linked-List       KVS 30-12-2018 Part B
Question 162 Explanation: 
→The while loop will traverse the at the end of the list “m” and this is appended to the link list “n”.
→Non-availability of the any one of the linked list leads to possibility of error.
Question 163
Given a tree with k nodes, the sum of degrees of all nodes is
A
2k-1
B
2*(k-1)
C
2k+1
D
2((k+1)
       Data-Structures       Trees       KVS 30-12-2018 Part B
Question 163 Explanation: 
The number of edges in tree with “k” nodes are K-1..
According to the handshaking lemma , the sum of the degree is 2* number of edges So the option B is suitable one.
Question 164
Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?
A
Insertion – 0(1), Deletion – 0(1), Maximum – 0(1), Minimum – 0(l)
B
Insertion – 0(1), Deletion – 0(1), Maximum – 0(n), Minimum – 0(n)
C
Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1)
D
Insertion – 0(n), Deletion – 0(n), Maximum – 0(n), Minimum – 0(n)
       Data-Structures       Arrays       UGC NET CS 2017 Jan -paper-2
Question 164 Explanation: 
→ Insertion will take O(n). Let, 1,2,3,4,5. Suppose we want to insert an array. It will traverse end of the array. So, it takes worst case O(n) and best case O(1). But we always consider worst case time complexity.
→ Deletion will take O(n). Let, 1,2,3,4,5. Suppose we want to delete last element in the array, It will traverse end of the array. So, it takes worst case O(n) and best case O(1). But we always consider worst case time complexity.
→ Maximum will take O(1) because we know location of maximum element. So it requires only constant amount.
→ Minimum will take O(1) because we know location of maximum element. So it requires only constant amount.
Question 165
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 ________.
A
A
B
B
C
F
D
G
       Data-Structures       Queues-and-Stacks       UGC NET CS 2017 Jan -paper-2
Question 165 Explanation: 
Step-1: Insert all elements into stack in reverse order then the stack is look like

Step-2: Stack is pooped five elements then stack is look like

Step-3: Popped five elements are inserted into a queue then queue is look like

Step-4: Two elements are deleted from the queue

Step-5: deleted queue elements are pushed back onto the stack

Top of the stack is B.
Question 166
Which of the following is a valid heap ?
A
A
B
B
C
C
D
D
       Data-Structures       Heap-Tree       UGC NET CS 2017 Jan -paper-2
Question 166 Explanation: 
Option A is violated max heap property because 8 is greater than his root.
Option B is satisfied max heap property.
Option C is violated max heap property because 7 is greater than his root.
Option D is violated max heap property because 9,10,8,7 elements are greater than his root.
Question 167
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 _______.
A
1
B
1/n
C
1/m
D
n/m
       Data-Structures       Hashing       UGC NET CS 2017 Jan -paper-2
Question 167 Explanation: 
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 1. It is direct theorem from universal hashing.
Question 168
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.
A
A
B
B
C
C
D
D
       Data-Structures       Graphs       UGC NET CS 2017 Jan -paper-2
Question 168 Explanation: 
→ For connected components we are using Depth first search but not breadth first search.
→ A connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
1. Kosaraju’s algorithm for strongly connected components.
2. Tarjan’s Algorithm to find Strongly Connected Components Time complexity for both algorithms are O(V+E).
Question 169
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:
A
726
B
796
C
506
D
616
       Data-Structures       Graphs       UGC NET CS 2016 Aug- paper-2
Question 169 Explanation: 
The total number of vertices in the graph is 12*12=144. The vertices are allowed to connect in both horizontal and vertical directions which are separated by at most 1 distance.
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8. From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012=2*E
⇒ E=506
Question 170
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?
A
S ​ 1​ is correct and S ​ 2​ is not correct.
B
S 1​ ​ is not correct and S 2​ ​ is correct.
C
Both S​ 1 and S​ 2​ are correct.
D
Both S​ 1​ and S​ 2​ are incorrect.
       Data-Structures       Queues-and-Stacks       UGC NET CS 2016 Aug- paper-2
Question 170 Explanation: 
→ Implementing queue by using two stack:
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
→ A stack can be implemented using two queues
Question 171
Consider the following binary search tree:

If we remove the root node, which of the node from the left subtree will be the new root?
A
11
B
12
C
13
D
16
       Data-Structures       Binary-search-tree       UGC NET CS 2016 July- paper-2
Question 171 Explanation: 
Usually binary search tree follows inorder. When we are using inorder automatically, the elements are in sorted order. There are worst case also, elements are not in sorted order.
After removing root element, binary search tree is looks like

Question 172
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?
A
Underflow occurs
B
Stack operations are performed smoothly
C
Overflow occurs
D
None of the above
       Data-Structures       Queues-and-Stacks       UGC NET CS 2016 July- paper-2
Question 172 Explanation: 
Here, stack size is 5. Stack operations are explained in step by step.
Question 173
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
A
(n/2) -1
B
(n/2) +1
C
(n–1) / 2
D
(n+1) / 2
       Data-Structures       Binary-Trees       UGC NET CS 2016 July- paper-2
Question 173 Explanation: 
→ They are given definition of full binary tree. The full binary tree each node has exactly either zero or two children.
→ The maximum height of the tree will be (n–1) / 2. It is standard property of full binary tree.
Question 174
Which of the following is not an inherent application of stack?
A
Implementation of recursion
B
Evaluation of a postfix expression
C
Job scheduling
D
Reverse a string
       Data-Structures       Queues-and-Stacks       UGC NET CS 2016 July- paper-2
Question 174 Explanation: 
Applications
1. Implementation of recursion
2. Evaluation of a postfix expression
3. Expression evaluation and syntax parsing
4. Backtracking
5. Compile time memory management
6. Reverse a string
Question 175
In how many ways can the string A ∩ B – A ∩ B – A be fully parenthesized to yield an infix expression?
A
15
B
14
C
13
D
12
       Data-Structures       Queues-and-Stacks       UGC NET CS 2016 July- paper-2
Question 175 Explanation: 
In this problem look very difficult to solve, but problem is following standard formula only.
Step-1: Total number of letters/operands with duplication is 5.
Step-3: To find total number of ways, we have catalan formula.
Here, n=5
Catalan number = (2n)! / (n! * (n+1)!)
= (2*5)! / (5! * (5+1)!)
= 10! / (5! * 6!)
= 14
Note: We used catalan formula because they given in fully parenthesized to yield an infix expression.
Question 176
The cyclomatic complexity of a flow graph V(G), in terms of predicate nodes is: [Where P is number of predicate nodes in flow graph V(G).]
A
P + 1
B
P – 1
C
P – 2
D
P + 2
       Data-Structures       Graphs       UGC NET CS 2016 July- paper-2
Question 176 Explanation: 
There are 3 formulas to find cyclomatic complexity. 1. The number of regions corresponds to the cyclomatic complexity
2. V(G),Flow graph is defined as V(G)=E-N+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
Question 177
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):
A
&A[0][0][0] + w(y* z* q + z* p + r)
B
&A[0][0][0] + w(y* z* p + z*q + r)
C
&A[0][0][0] + w(x* y* p + z* q+ r)
D
&A[0][0][0] + w(x* y* q + z* p + r)
       Data-Structures       Arrays       UGC NET CS 2015 Dec- paper-2
Question 178
The hash function used in double hashing is of the form:
A
h (k, i) = (h​ 1​ (k) + h​ 2​ (k) + i) mod m
B
h (k, i) = (h​ 1​ (k) + h​ 2​ (k) - i) mod m
C
h (k, i) = (h​ 1​ (k) + i h​ 2​ (k)) mod m
D
h (k, i) = (h​ 1​ (k) - i h​ 2​ (k)) mod m
       Data-Structures       Hashing       UGC NET CS 2015 Dec- paper-2
Question 178 Explanation: 
Double Hashing with second hash function is​ ​ h(k,i) = (h​ 1​ (k) + i·h​ 2​ (k)) mod m 0≤ i ≤m-1
h​ 1​ → hash function
h​ 2​ → Step function
First try h(k,0) = h​ 1​ (k), if it is occupied, try h(k,1) etc..,
Advantage: less clusters, uses Θ(m*m) permutations of index addressing sequences.
Question 179
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:
A
θ(log​ n​ h*t)
B
θ(log​ t​ n*h)
C
θ(log​ h​ n)
D
θ(log​ t​ n)
       Data-Structures       B-Trees       UGC NET CS 2015 Dec- paper-2
Question 179 Explanation: 
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 θ(log​ t​ n).
Note: B-Tree search operation best,average and worst case will take θ(logn).
Question 180
The inorder traversal of the following tree is:
A
2 3 4 6 7 13 15 17 18 18 20
B
20 18 18 17 15 13 7 6 4 3 2
C
15 13 20 4 7 1718 2 3 6 18
D
2 4 3 13 7 6 15 17 20 18 18
       Data-Structures       Tree-traversals       UGC NET CS 2015 Dec- paper-2
Question 180 Explanation: 
Inorder traversal through Left, Root and Right. Inorder yield procedure given below.
Question 181
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?
A
(a) and (b)
B
(c) and (d)
C
(a), (b) and (c)
D
(a), (b), (c) and (d)
       Data-Structures       Graphs-and-Tree       UGC NET CS 2015 Jun- paper-2
Question 181 Explanation: 
→ Preorder, Postorder and Inorder are traversing techniques where all the nodes of the tree will be traversed from the root node.
→ Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
→ The optimal binary tree, which has minimum weighted path length when the characters of the alphabet are stored at its n terminal nodes.An optimal binary tree generates what is called a Huffman code
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.
Question 182
The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The post-order Traversal is __________.
A
dbefacg
B
debfagc
C
dbefcga
D
debfgca
       Data-Structures       Binary-Trees       UGC NET CS 2015 Jun- paper-2
Question 182 Explanation: 
Inorder: Left root Right
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g

Pre order: a b d e c f g
Post order: d e b f g c a
Question 183
Level order Traversal of a rooted Tree can be done by starting from root and performing:
A
Breadth First Search
B
Depth First Search
C
Root Search
D
Deep Search
       Data-Structures       Graphs-and-Tree       UGC NET CS 2015 Jun- paper-2
Question 183 Explanation: 
Breadth first search:
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 184
What item is at the root after the following sequence of insertions into an empty splay tree :
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?
A
1
B
2
C
4
D
8
       Data-Structures       Binary-Trees       UGC NET CS 2004 Dec-Paper-2
Question 184 Explanation: 
A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown.



Question 185
Suppose we are implementing quadratic probing with a Hash function, Hash(y)=X mod 100. If an element with key 4594 is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is :
A
2
B
3
C
9
D
97
       Data-Structures       Hashing       UGC NET CS 2004 Dec-Paper-2
Question 185 Explanation: 
Given quadratic probing with a Hash function,
-- Hash(y)=X mod 100
-- Key=4594
-- First 3 locations are already occupied.
-- Next cell=?
Step-1: Quadratic Probing function is​ ​ h(k,i) = (h'(k) +c​ 1​ i+c​ 2​ i​ 2​ )mod m 0≤ i ≤ m-1
where c1 and c2 constants ≠0
Step-2: First pass: 4594 % 100
= 94
Sep-3: Second pass: (4594 + 1​ 2​ ) % 100
= (94 + 1) % 100
= 95
Step-3: Third pass: (4594 + 2​ 2​ ) % 100
= (94 + 4) %100
= 98
Step-4: Fourth pass: (4594 + 1​ 2​ ) % 100
= (94 + 9) %100
= 103 % 100
= 3
Question 186
Weighted graph :
A
Is a bi-directional graph
B
Is directed graph
C
Is graph in which number associated with arc
D
Eliminates table method
       Data-Structures       Graphs-and-Tree       UGC NET CS 2004 Dec-Paper-2
Question 186 Explanation: 
→ Weighted graph is a graph in which number associated with arc. A weighted graph is a graph in which each branch is given a numerical weight.
→ A weighted graph is therefore a special type of labeled graph in which the labels are numbers.
Question 187
What operation is supported in constant time by the doubly linked list, but not by the singly linked list ?
A
Advance
B
Backup
C
First
D
Retrieve
       Data-Structures       Linked-List       UGC NET CS 2004 Dec-Paper-2
Question 187 Explanation: 
→ Backup operation is supported in constant time by the doubly linked list, but not by the singly linked list.
Question 188
Which of the following is not collision resolution technique ?
A
Hash addressing
B
Chaining
C
Both (A) and (B)
D
Indexing
       Data-Structures       Hashing       UGC NET CS 2004 Dec-Paper-2
Question 188 Explanation: 
→ Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys.
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 189
In what tree, for every node the height of its left subtree and right subtree differ at least by one :
A
Binary search tree
B
AVL - tree
C
Threaded binary tree
D
Complete tree
       Data-Structures       Trees       UGC NET CS 2005 Dec-Paper-2
Question 189 Explanation: 
Threaded binary tree:​ A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.
1. Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right).
2. Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right).
Question 190
A hash function ​ f ​ defined as ​ f ( ​ key)5 key mod 7, with linear probing it is used to insert the key 37,38,72,48,98,11,56 into a table index from 0 to 6. What will be the locations of 11 :
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC NET CS 2005 Dec-Paper-2
Question 190 Explanation: 
Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7
Question 191
Consider the graph, which of the following is a valid topological sorting ?
A
ABCD
B
BACD
C
BADC
D
ABDC
       Data-Structures       Graphs-and-Tree       UGC NET CS 2005 Dec-Paper-2
Question 191 Explanation: 
Finding valid topological sorting we have two methods.
1. Using DFS method
2. Using indegree elimination method
The simplest method is indegree elimination method.
Indegrees:
A →0
B →1
D →2
C → 1 (Final)
We can assume that indegree value of A is ‘0’. So, it is starting point.
Step-1: Remove ‘A’ from graph, then indegrees are
B →0
D →1
C →1
Sequence:

Step-2: Remove ‘B’ from graph, then indegrees are
D →0
C →1
Sequence:

Step-3: Remove ‘C’ from graph then indegrees are
C →0
Sequence:
Question 192
The initial configuration of queue is a, b, c, d. ‘​ a’​ is at the front. To get the configuration d, c, b, a how many deletions and additions required :
A
2 deletions, 3 additions
B
3 deletions, 2 additions
C
3 deletions, 4 additions
D
3 deletions, 3 additions
       Data-Structures       Queues-and-Stacks       UGC NET CS 2005 Dec-Paper-2
Question 192 Explanation: 
Initially the queue order is

Step-1: Delete ‘a’ from queue. The deletion operation performs First In First Out.We will perform the deletion at front end
After deleting queue will become

Step-3: Delete ‘b’ from queue. The deletion operation performs First In First Out.
After deleting queue will become

Step-3: Delete ‘c’ from queue. The deletion operation performs First In First Out.
After deleting queue will become

Step-4: Insert the element “c” into the queue, We will perform the insertion at rear end
The elements of queue after inserting the element ”c” are

Step-5: Insert the element “b” into the queue,then the elements of queue after inserting the element ”b” are

step-6: Insert the element “a” into the queue,then the elements of queue after inserting the element ”a” are

→ Step-1,step-2 and step-3 are deletion operations and step-4,step-5 and step-6 are deletions operations.
→ So total 3 deletions and 3 insertions are required to get required configuration.
Question 193
Which traversal techniques lists the nodes of a binary search tree in ascending order ?
A
post – order
B
in - order
C
pre - order
D
linear - order
       Data-Structures       Binary-Trees       UGC NET CS 2005 Dec-Paper-2
Question 193 Explanation: 
Inorder traversal technique in binary search tree will always produce ascending order.
Example:

In this traversal method, the left subtree is visited first, then the root and later the right subtree. We should always remember that every node may represent a subtree itself.
Question 194
Which of the following is not collision Resolution Technique :
A
Hash addressing
B
Chaining
C
Indexing
D
None of these
       Data-Structures       Hashing       UGC NET CS 2005 Dec-Paper-2
Question 194 Explanation: 
→ Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys.
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 195
What is the time required to insert an element in a stack with linked implementation ?
A
O (log​ 2​ n)
B
O (n)
C
O (n log​ 2​ n)
D
O (1)
       Data-Structures       Queues-and-Stacks       UGC NET CS 2005 june-paper-2
Question 195 Explanation: 
Question 196
Which of the following statement is false ?
A
Every tree is a bipartite graph
B
A tree contains a cycle
C
A tree with n nodes contains n-1 edges
D
A tree is a connected graph
       Data-Structures       Trees       UGC NET CS 2005 june-paper-2
Question 196 Explanation: 
A tree never contains cycles. If it contains a cycle, we are calling as graph but not tree.
Note: Minimum 1 edge and maximum n-1 edges.
Question 197
In the balanced binary tree given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g” ?
A
1
B
3
C
7
D
8
       Data-Structures       Binary-Trees       UGC NET CS 2005 june-paper-2
Question 197 Explanation: 

a, c, d are going to unbalance.
Question 198
If the postfix form of a string is ABC+ - D*, the actual string is :
A
(A-(B+C))*D
B
((A-B)+C)*D
C
((A+B)-C)*D
D
(A+(B-C))*D
       Data-Structures       Queues-and-Stacks       UGC NET CS 2005 june-paper-2
Question 198 Explanation: 
Question 199
The algorithm that will efficiently sort an array that is nearly sorted except for the interchange of some adjacent pairs of numbers like : { 1, 3, 2, 5, 4, 6} is :
A
Quick sort
B
Bubble sort
C
Merge sort
D
Selection sort
       Data-Structures       Arrays       UGC NET CS 2005 june-paper-2
Question 199 Explanation: 
If we are using quick sort to sort a nearly sorted/sorted elements will give worst case time complexity. Here the number interchanges are more.
Bubble sort will give best complexity, when the array is very sorted. Here the number interchanges are very less.
Merge sort will will gives best time complexity but not like bubble in this case. Here the number interchanges are more.
Selection sort will always gives worst performance, whether it is sorted order or not.
Question 200
Binary search tree is an example of :
A
Divide and conquer technique
B
Greedy algorithm
C
Back tracking
D
Dynamic Programming
       Data-Structures       Binary-Trees       UGC NET CS 2006 Dec-paper-2
Question 200 Explanation: 
Binary search tree is an example of divide and conquer technique.
Procedure:
1. Divide: select lower or upper half
2. Conquer: search selected half
3. Combine: None
Recurrence relation​ : T(n)=T(n/2)+Θ(1)
Using masters theorem,
a=1, b=2, k=0,p=0
T(n)=Θ(logn)
Question 201
What is the time required to insert an element in a stack with linked implementation ?
A
O (log​ 2​ n)
B
O (n)
C
O (n log​ 2​ n)
D
O (1)
       Data-Structures       Queues-and-Stacks       UGC NET CS 2006 Dec-paper-2
Question 201 Explanation: 
Average case in linked list:

Worst case in linked list:
Question 202
The equivalent postfix expression for d/(e +f) +b*c
A
defbc/++*
B
def+/bc+*
C
def+/bc *+
D
None of these
       Data-Structures       Queues-and-Stacks       UGC NET CS 2006 Dec-paper-2
Question 202 Explanation: 

Postfix expression: d ef + / bc * +
Question 203
Which one of the following is a physical data structure ?
A
Array
B
Linked lists
C
Stacks
D
Tables
       Data-Structures       Arrays       UGC NET CS 2006 Dec-paper-2
Question 203 Explanation: 
→ An array is a number of elements in a specific order, typically all of the same type (depending on the language, individual elements may either all be forced to be the same type, or may be of almost any type).
→ Elements are accessed using an integer index to specify which element is required. Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed-length or resizable.
Note: Arrays are directly stored in a memory location. Linked list, Stacks and table(using array) are used logical memory rather than physical memory.
Question 204
In the balanced binary tree given below, how many nodes will become unbalanced when a node is inserted as a child of the node ​ ”g”.
A
1
B
3
C
7
D
8
       Data-Structures       Binary-Trees       UGC NET CS 2006 June-Paper-2
Question 204 Explanation: 

a, c, d are going to unbalance.
Question 205
Preorder is also known as :
A
Depth first order
B
Breadth first order
C
Topological order
D
Linear order
       Data-Structures       Trees       UGC NET CS 2006 June-Paper-2
Question 205 Explanation: 
Preorder is also known as topological order. Every preorder can be given a topology, and indeed, every preorder on a set is in one-to-one correspondence with an topology on that set.
Question 206
Which of the following statement is false ?
A
Every tree is a bipartite graph
B
A tree contains a cycle
C
A tree with n nodes contains (n-1) edges
D
A tree is connected graph
       Data-Structures       Trees       UGC NET CS 2006 June-Paper-2
Question 206 Explanation: 
A tree never contains cycles. If it contains a cycle, we are calling as graph but not tree.
Note: Minimum 1 edge and maximum n-1 edges.
Question 207
If the post-fix form of a string is ABC+ -D*, The actual string is :
A
(A-(B+C))*D
B
((A-B)+C)*D
C
((A+B)-C)*D
D
(A+(B-C)*D)
       Data-Structures       Queues-and-Stacks       UGC NET CS 2006 June-Paper-2
Question 207 Explanation: 
Question 208
Application of data structure queue is :
A
Level wise printing of tree
B
Implementation of priority queues
C
Function call implementation
D
Depth first search in a graph
       Data-Structures       Queues-and-Stacks       UGC NET CS 2006 June-Paper-2
Question 208 Explanation: 
Application of data structure queue is implementation of priority queues. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined. While priority queues are often implemented with heaps.
Applications:
1.Bandwidth management
2.Discrete event simulation
3.Dijkstra's algorithm
4.Huffman coding
5.Best-first search algorithms
6.ROAM triangulation algorithm
7.Prim's algorithm for minimum spanning tree
Question 209
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) ?
A
4 PUSH and 3 POP instructions
B
5 PUSH and 4 POP instructions
C
6 PUSH and 2 POP instructions
D
5 PUSH and 3 POP instructions
       Data-Structures       Queues-and-Stacks       UGC NET CS 2014 Dec-Paper-2
Question 209 Explanation: 
Given infix notation, we have to change infix notation into postfix notation.
after converting postfix notation the notations are ab* cde /* +

Total 5 PUSH and 4 POP operations performed.
Question 210
Convert the following infix expression into its equivalent postfix expression (A + B^ D) / (E – F) + G
A
ABD^ + EF – / G+
B
ABD + ^EF – / G+
C
ABD + ^EF / – G+
D
ABD^ + EF / – G+
       Data-Structures       Prefix-Postfix-Expression       UGC NET CS 2014 Dec-Paper-2
Question 210 Explanation: 
→ According to priority (or) infix expression we can write expression like this ((A + B^D) / (E – F)) + G
→ Actual tree structure is
Question 211
A full binary tree with n leaves contains
A
n nodes
B
log​ 2​ n nodes
C
2n –1 nodes
D
2​ n​ nodes
       Data-Structures       Binary-Trees       UGC NET CS 2014 Dec-Paper-2
Question 211 Explanation: 
A Binary Tree is full if every node has 0 or 2 children. So, in such case, the binary tree with n leaves contains a total of 2*n-1 nodes.

There are 4 leaf nodes in the above tree.
So, total number of nodes are 2*4-1
=8-1
=7
Question 212
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.
A
20 , 20
B
3 ,20
C
3, 5
D
20, 5
       Data-Structures       ADT       UGC NET CS 2018-DEC Paper-2
Question 212 Explanation: 
→ char is a fixed-length data type, the storage size of the char value is equal to the maximum size for this column.
→ varchar is a variable-length data type, the storage size of the varchar value is the actual length of the data entered, not the maximum size for this column.
→ So, A varchar(20) has only 3 spaces because its initialized to 'xyz' and B char(20) has 20 spaces as char data type occupies the storage space equivalent to the maximum size.
Question 213
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 subtree is
A
7
B
6
C
3
D
5
       Data-Structures       Binary-search-tree       UGC NET CS 2018-DEC Paper-2
Question 213 Explanation: 
Question 214
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 :
A
6, 3
B
8, 1
C
8, 2
D
6, 2
       Data-Structures       Prefix-Postfix-Expression       UGC NET CS 2018-DEC Paper-2
Question 214 Explanation: 
For evaluating a postfix expression we start traversing from first element of the expression
While traversing the expression if you find an element value then push it on the top of stack this way the top element of the stack will represent the second operand of an operation and the element presents after top element will represent the first operand of the operation. While traversing the postfix expression if you find an operation symbol then pop 2 elements from the top of the stack and then after performing operation store it’s result on the top of stack.


Question 215
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
A
<42, 35, 40, 22, 25, 26, 30>
B
<42, 35, 40, 22, 25, 30, 26>
C
<42, 40, 35, 25, 22, 26, 30>
D
<42, 40, 35, 25, 22, 30, 26>
       Data-Structures       Heap-Tree       UGC NET CS 2018-DEC Paper-2
Question 215 Explanation: 
After inserting each element we will apply MAX-Heapify operation to get the MAX-Heap.
The resultant MAX_Heap will look like

< 4 2, 40, 35, 25, 22, 30, 26 >
Question 216
​ Consider the following minimax game tree search

What will be the value propagated at the root ?
A
6
B
3
C
5
D
4
       Data-Structures       Trees       UGC NET CS 2018-DEC Paper-2
Question 216 Explanation: 
Question 217
The minimum number of nodes in a binary tree of depth d (root is at level 0) is
A
2d – 1
B
2d + 1 – 1
C
d + 1
D
d
       Data-Structures       Binary-Trees       UGC NET CS 2013 Sep-paper-2
Question 217 Explanation: 
Binary tree is a tree where each node has at most 2 children nodes.
Properties:
→The number of nodes at depth d in a perfect binary tree = 2d
→A perfect binary tree of height h has 2h+1 -1 nodes
→Number of leaf nodes in a perfect binary tree of height h = 2h
→Number of internal nodes in a perfect binary tree of height h = 2h -1
→The minimum number of nodes in a binary tree of height h = h+1
→The maximum number of nodes in a binary tree of height h = 2h+1 -1
Question 218
The efficient data structure to insert/delete a number in a stored set of numbers is
A
Queue
B
Linked list
C
Doubly linked list
D
Binary tree
       Data-Structures       Linked-List       UGC NET CS 2013 Sep-paper-2
Question 218 Explanation: 
Doubly linked list is the efficient data structure to insert/delete a number in a stored set of numbers.

Question 219
Consider the In-order and Post-order traversals of a tree as given below :
In-order : j e n k o p b f a c l g m d h I
Post-order : j n o p k e f b c l m g h i d a
The Pre-order traversal of the tree shall be
A
a b f e j k n o p c d g l m h i
B
a b c d e f j k n o p g l m h i
C
a b e j k n o p f c d g l m h i
D
j e n o p k f b c l m g h i d a
E
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2013 Sep-paper-2
Question 219 Explanation: 
Step-1: Post order traversal is Left, Right and Root according to post order we are dividing into in-order list.

Step-2:

Step-3: Final tree is

Step-4: Preorder traversal is Root,left and right
preorder= a b e j k n p o f d g l c m i h
Note: Given options are wrong. Excluded for evaluation.
Question 220
Linked Lists are not suitable for _____.
A
Binary Search
B
Polynomial Manipulation
C
Insertion
D
Radix Sort
       Data-Structures       Linked-List       UGC NET CS 2013 Sep-paper-2
Question 220 Explanation: 
Linked Lists are not suitable for binary search.
Note: We can also implement binary search using linked list but it will give time complexity is O(n) instead of O(logn).
Question 221
The worst case time complexity of AVL tree is better in comparison to binary search tree for
A
Search and Insert Operations
B
Search and Delete Operations
C
Insert and Delete Operations
D
Search, Insert and Delete Operations
       Data-Structures       Binary-Trees       UGC NET CS 2012 Dec-Paper-2
Question 221 Explanation: 
AVL tree is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.

Question 222
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).
A
3, 14
B
3, 10
C
4, 14
D
4, 10
       Data-Structures       Heap-Tree       UGC NET CS 2018 JUNE Paper-2
Question 222 Explanation: 
A heap is a MAX-Heap if all the root nodes(parent nodes) have maximum value.
Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max- heapify operation from the largest index parent node(node having 1 or more children).



The above Heap is the max-heap where each root node have maximum value. Now depth of the Max-heap is 3 and right child of the Root node is 10.
Question 223
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 ?
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC NET CS 2018 JUNE Paper-2
Question 223 Explanation: 
h(key)=key mod 7 is the given hash function and it is mentioned that linear probing is used.
h(44)=44 mod 7 ⇒ 2
h(45)=45 mod 7 ⇒ 3
h(79)=79 mod 7 ⇒ 2 (collision occurred)
h(79)=(79+1) mod 7 ⇒ 3 (collision occurred)
h(79)=(79+2) mod 7 ⇒ 4
h(55)=55 mod 7 ⇒ 6
h(91)=91 mod 7 ⇒ 0
h(18)=18 mod 7 ⇒ 4 (collision occurred)
h(79)=(18+1) mod 7 ⇒ 5
h(63)=63 mod 7 ⇒ 0 (collision occurred)
h(63)=(63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations
Question 224
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 :
A
cannot have more than 37 nodes
B
has exactly 37 nodes
C
has exactly 35 nodes
D
cannot have more than 35 nodes
       Data-Structures       Binary-search-tree       UGC NET CS 2018 JUNE Paper-2
Question 224 Explanation: 
L = I(n-1)+ 1
Where, L= Number of leaf nodes
n= N-ary tree
I = Number of intermediate nodes
Now, 19 = I(2-1)+1
19 = 2I-I+1
19 = I+1
I = 18
Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes
Total Number of nodes in a tree = 19+18
Total Number of nodes in a tree = 37
Question 225
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 :
A
30
B
33
C
45
D
None of the above
       Data-Structures       Trees       UGC NET CS 2018 JUNE Paper-2
Question 225 Explanation: 
L = I(n-1)+ 1
Where, L= Number of leaf nodes
n= N-ary tree
I = Number of intermediate nodes
Now, L =8(5-1)+1
L =8(4)+1
L =33
Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes
Total Number of nodes in a tree = 8+33
Total Number of nodes in a tree = 41
Question 226
In which tree, for every node the height of its left subtree and right subtree differ almost by one ?
A
Binary search tree
B
AVL tree
C
Threaded Binary Tree
D
Complete Binary Tree
       Data-Structures       Binary-Trees       UGC NET CS 2012 Dec-Paper-2
Question 226 Explanation: 
→ AVL tree is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
→ ALV tree
Question 227
A hash function f defined as f(key) = key mod 13, with linear probing is used to insert keys 55, 58, 68, 91, 27, 145. What will be the location of 79 ?
A
1
B
2
C
3
D
4
       Data-Structures       Hashing       UGC NET CS 2012 Dec-Paper-2
Question 227 Explanation: 

Question 228
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.
A
3, 10, 1, 8,___ ,___,___.
B
1, 3, 8, 10,___,___,___.
C
1,___,3,___, 8,___,10
D
3,10,___,___, 8,___,___.
       Data-Structures       Hashing       UGC NET CS 2018 JUNE Paper-2
Question 228 Explanation: 
h(1)= ((7*1)+3) mod 4 = 2
h(3)= ((7*3)+3) mod 4 = 0
h(8)= ((7*8)+3) mod 4 = 3
h(10)= ((7*10)+3) mod 4 = 1
Question 229
Consider the tree given below

Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree.
A
d & h
B
c & k
C
g, b, c, h, i, m
D
c & h
       Data-Structures       Binary-Trees       UGC NET CS 2012 Dec-Paper-2
Question 229 Explanation: 

Eccentricity of a vertex u, is
E(u) = maxu∈v(G) d(u, v)
i.e., the maximum distance of a node to other nodes is the eccentricity of that node

Radius: The minimum eccentricity from all the vertices is considered as the radius of the Graph G denoted by r(G).
Here radius of the graph, r(G)=3
Center:- If the eccentricity of a graph is equal to its radius, then it is known as the central point of the graph.
And in above graph vertex "h" and " c" have eccentricity equal to the radius of the graph. So vertex h and c are the center of graph.
Hence correct answer is option (D).
Question 230
Given an empty stack, after performing Push(1), Push(2), Pop, Push(3), Push(4), Pop, Pop, push(5), Pop. what is the value of the top of the stack ?
A
4
B
3
C
2
D
1
       Data-Structures       Queues-and-Stacks       UGC NET CS 2012 Dec-Paper-2
Question 230 Explanation: 

Question 231
What is the value of the postfix expression ?
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5)
A
–3/8
B
–8/3
C
24
D
–24
       Data-Structures       Queues-and-Stacks       UGC NET CS 2013 Dec-paper-2
Question 231 Explanation: 

Question 232
If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a non-empty queue ?
A
Neither of the pointers change
B
Only front pointer changes
C
Only rear pointer changes
D
Both of the pointers changes
       Data-Structures       Linked-List       UGC NET CS 2013 Dec-paper-2
Question 232 Explanation: 

Observe 1, 2, 3 whenever we are inserting an element into a queue (singly linked list) we are updating Rear pointer.
Question 233
The postfix expression AB + CD – * can be evaluated using a
A
stack
B
tree
C
queue
D
linked list
       Data-Structures       Queues-and-Stacks       UGC NET CS 2012 June-Paper2
Question 233 Explanation: 

Question 234
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
A
ABFCDE
B
ADBFEC
C
ABDECF
D
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2012 June-Paper2
Question 234 Explanation: 
Post order traversal tree is look like

Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 235
A binary search tree is a binary tree :
A
All items in the left subtree are less than root
B
All items in the right subtree are greater than or equal to the root
C
Each subtree is itself a binary search tree
D
All of the above
       Data-Structures       Binary-Trees       UGC NET CS 2012 June-Paper2
Question 235 Explanation: 
Binary search tree properties: 1. All items in the left subtree are less than root
2. All items in the right subtree are greater than or equal to the root
3. Each subtree is itself a binary search tree
Question 236
Which of the following data structure is linear type ?
A
Strings
B
Lists
C
Queues
D
All of the above
       Data-Structures       Lnear-Data-Structure       UGC NET CS 2012 June-Paper2
Question 236 Explanation: 
A data structure is said to be linear if its elements form a sequence or a linear list.
Examples:
1. Array
2. Linked List
3. Stacks
4. Queues
Question 237
To represent hierarchical relationship between elements, which data structure is suitable ?
A
Dequeue
B
Priority
C
Tree
D
All of the above
       Data-Structures       Binary-Trees       UGC NET CS 2012 June-Paper2
Question 237 Explanation: 
Double-Ended Queue is a data structure in which insertion and deletion of data takes place from different ends. The insertion of data takes place from REAR end and deletion of data takes place from FRONT end. It follows FIFO( First In First Out) order for implementation.

Priority Queue is like a regular queue or stack data structure, but here each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Tree: A tree is a data structure containing a collection of nodes. Here a node can have any number of children. A node with no child is called as leaf node and a node with 1 or more child is called parent node. Each parent node have a pointer to its children.

Question 238
Which of the following data structure is Non-linear type ?
A
Strings
B
Lists
C
Stacks
D
None of the above
       Data-Structures       Lnear-Data-Structure       UGC NET CS 2011 Dec-Paper-2
Question 238 Explanation: 
A data structure is said to be linear if its elements form a sequence or a linear list.
Examples:
1. Array
2. Linked List
3. Stacks
4. Queues
Question 239
Which of the following is a bad example of recursion ?
A
Factorial
B
Fibonacci numbers
C
Tower of Hanoi
D
Tree traversal
       Data-Structures       Recursion       UGC NET CS 2011 Dec-Paper-2
Question 239 Explanation: 
→ Fibonacci Series using recursion using condition is
Condition: fibonacci(n-1) + fibonacci(n-2)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Factorial number using recursion is
Condition: fact(n-1)*n
Recurrence relation is: T(n)=T(n+1)+1
Time Complexity: O(n)
→ Tower of Hanoi using recursion is
Step-1: Hanoi(disk - 1, source, aux, dest)
Step-2: move disk from source to dest
Step-3: Hanoi(disk - 1, aux, dest, source)
Recurrence relation is: T(n)=2T(n-1)+C
Time Complexity: O(2n)
→ Tree traversals like Preorder,Postorder and Inorder using recursion only
Note: Recursion is best in the case of Tower of Hanoi,Factorial number and Tree traversals but it is not give good performance to fibonacci numbers.
Question 240
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
A
ABFCDE
B
ADBFEC
C
ABDECF
D
ABDCEF
       Data-Structures       Binary-Trees       UGC NET CS 2011 Dec-Paper-2
Question 240 Explanation: 
Post order traversal tree is look like

Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 241
The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to
A
20 + 21 + ….. 2h
B
20 + 21 + ….. 2h – 1
C
20 + 21 + ….. 2h + 1
D
21 + ….. 2h + 1
       Data-Structures       Binary-Trees       UGC NET CS 2011 Dec-Paper-2
Question 241 Explanation: 
The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to 20 + 21 + ….. 2h. because every phase we are getting 2h.
Suppose, in level-3, it have 23=8 nodes.
Question 242
The number of different trees with 8 nodes is
A
256
B
255
C
248
D
None of these
       Data-Structures       Binary-Trees       UGC NET CS 2011 June-Paper-2
Question 242 Explanation: 
Given data
-- nodes=8
-- Total number of trees=?
Possibility-1: To find total number of trees using nn-2.
= 88-2
= 262144 trees are possible.
Possibility-2: According to given problem, they are using binary tree based on below formula
= 2n -n

= 28 -8
= 248
Note: They are not given proper input.
Question 243
Given a binary tree whose inorder and preorder traversal are given by
In order : E I C F B G D J H K
Preorder : B C E I F D G H J K
The post order traversal of the above binary tree is
A
I E F C G J K H D B
B
I E F C J G K H D B
C
I E F C G K J H D B
D
I E F C G J K D B H
       Data-Structures       Binary-Trees       UGC NET CS 2011 June-Paper-2
Question 243 Explanation: 

Question 244
Consider a hash table of size m = 10000 and the hash function h(k) = ⌊m(kA mod 1)'⌋ for      A=(√5 – 1)/2 . The location to the key k=123456 is
A
46
B
47
C
41
D
43
       Data-Structures       Hashing       UGC NET CS 2011 June-Paper-2
Question 244 Explanation: 
Given data,
-- size m=10000
-- hash function h(k) = ⌊m(kA mod 1)'⌋
-- A=(√5 – 1)/2
-- key k=123456 location =?
Step-1: Find out h(123456) = ⌊(10000 * (123456 * (√5 − 1) / 2) mod 1)⌋
= ⌊(10000 * (76300.004115 mod 1)⌋
= ⌊(10000 * (.004115))⌋
= ⌊41.15⌋
= 41
Question 245
When the priority queue is represented by max heap, the insertion and deletion of an element can be performed in (queue containing n elements)
A
θ(n) and θ(1) respectively
B
θ(n) and θ(n) respectively
C
θ(1) and θ(1) respectively
D
None of the above
       Data-Structures       Heap-Tree       UGC NET CS 2011 June-Paper-2
Question 245 Explanation: 

Question 246
Given an open address hash table with load factor α < 1, the expected number of probes in a successful search is
A
At most (1/α) ln ((1–α)/α)
B
At most (1/α) ln (1/(1–α))
C
At least (1/α) ln (1/(1– α))
D
At least (1/α) ln (α/(1– α))
       Data-Structures       Hashing       UGC NET CS 2013 June-paper-2
Question 246 Explanation: 
Analysis of Open Addressing:
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
Question 247
The time complexity to build a heap with a list of n numbers is
A
O(log n)
B
O(n)
C
O(n logn)
D
O(n2)
       Data-Structures       Heap-Tree       UGC NET CS 2013 June-paper-2
Question 247 Explanation: 
Build-Max-Heap(A)
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heap-size[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 Max-Heapify(A, i)
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.
→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.
Question 248
The value of postfix expression :
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
A
17
B
131
C
64
D
52
       Data-Structures       Queues-and-Stacks       UGC NET CS 2013 June-paper-2
Question 248 Explanation: 

Question 249
Consider the following statements for priority queue :
S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields.
Which of the following is correct ?
A
Both S1 and S2 are incorrect.
B
S1 is correct and S2 is incorrect.
C
S1 is incorrect and S2 is correct.
D
Both S1 and S2 are correct
       Data-Structures       Queues-and-Stacks       UGC NET CS 2013 June-paper-2
Question 249 Explanation: 
S1: TRUE: It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2: TRUE: The elements of a priority queue may be complex structures that are ordered on one or several fields.
Question 250
A binary tree with 27 nodes has _______ null branches.
A
54
B
27
C
26
D
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2010 Dec-Paper-2
Question 251
The time complexity to build a heap of n elements is
A
O(1)
B
O(lgn)
C
O(n)
D
O(nlgn)
       Data-Structures       Heap-Tree       UGC NET CS 2010 Dec-Paper-2
Question 251 Explanation: 
The time complexity to build a heap of n elements is O(n).
Build-Max-Heap(A)
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heap-size[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 Max-Heapify(A, i)
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.
→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.
Question 252
Linear probing suffers from a problem known as
A
Secondary clustering
B
Primary clustering
C
Both (A) and (B)
D
None of these
       Data-Structures       Hashing       UGC NET CS 2010 Dec-Paper-2
Question 252 Explanation: 
→ Primary clustering means that if there is a cluster and the initial position of a new record would fall anywhere in the cluster the cluster size increases.
Example: Linear probing
→ Secondary clustering is less severe, two records do only have the same collision chain if their initial position is the same.
Example: Quadratic probing
Question 253
Which of the following can be the sequence of nodes examined in binary search tree while searching for key 88 ?
A
90, 40, 65, 50, 88
B
90, 110, 80, 85, 88
C
190, 60, 90, 85, 88
D
65, 140, 80, 70, 88
       Data-Structures       Binary-search-tree       UGC NET CS 2010 Dec-Paper-2
Question 253 Explanation: 
Binary search tree will follow some rules
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform


Note: The sequence of searching should be continuous.
Question 254
If we have six stack operations pushing and popping each of A, B and C such that push(A) must occur before push(B) which must occur before push(C), then A, C, B is a possible order for the pop operations,since this could be our sequence : push(A), pop(A), push(B), push(C), pop(C), pop(B). Which one of the following orders could not be the order the pop operations are run, if we are to satisfy the requirements described above ?
A
ABC
B
CBA
C
BAC
D
CAB
       Data-Structures       Queues-and-Stacks       UGC NET CS 2010 June-Paper-2
Question 254 Explanation: 

Option-A: According to constraint,
Push(A) then Pop(A)
Push(B) then Pop(B)
Push(C) then Pop(C)
Then the possible pop sequence is ABC. So, it is TRUE
Option-B: According to given constraint, Push(A),Push(B) and Push(C) then Pop(C),
Pop(B) and Pop(A). The possible Pop sequence is CBA. So, it is TRUE
Option-C: According to given constraint, Push(A) and Push(B) then Pop(B) and Pop(A)
then push(C) and Pop(C). The possible Pop sequence is BAC. So, it is TRUE
Option-D: This is not possible.
Question 255
What is the most appropriate data structure to implement a priority queue ?
A
Heap
B
Circular array
C
Linked list
D
Binary tree
       Data-Structures       Queues-and-Stacks       UGC NET CS 2010 June-Paper-2
Question 255 Explanation: 
→ Priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.
→ In a priority queue, an element with high priority is served before an element with low priority.
→ In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.
→ While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map".
→ just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
Question 256
In a complete binary tree of n nodes, how far are the two most distant nodes? Assume each edge in the path counts as !
A
About log2n
B
About 2 log2n
C
About n log2n
D
About 2n
       Data-Structures       Binary-Trees       UGC NET CS 2010 June-Paper-2
Question 256 Explanation: 
According to binary two most distinct nodes are in
level-1: 1 and 2
level-2: 3 and 6.
[Note: Assume that root starts from level-0]

The height of the binary tree is O(log2n). As per the given constraint, we have to calculate individually of left farthest node and right farthest node height.
=log2n*log2n
=2*log2n or (log2n)2
Question 257
A chained hash table has an array size of 100. What is the maximum number of entries that can be placed in the table ?
A
100
B
200
C
10000
D
There is no upper limit
       Data-Structures       Hashing       UGC NET CS 2010 June-Paper-2
Question 257 Explanation: 
Here, two things we have to remember
1. They given chained hash. It is like linked list.
2. Maximum number of entries that can be placed in the table.
In chained hash, we adding new element when collisions are happened.
Question 258
Queue is a __________ list.
A
LIFO
B
LILO
C
FILO
D
FIFO
       Data-Structures       Queues-and-Stacks       UGC NET CS 2009-June-Paper-2
Question 258 Explanation: 
Queue is FIFO(First In First Out) and Stack is LIFO(Last In First Out).
Question 259
In a full binary tree of height k, there are __________ internal nodes.
A
2k-1
B
2k-1
C
2k
D
2k+1
       Data-Structures       Binary-Trees       UGC NET CS 2009-June-Paper-2
Question 259 Explanation: 
→ In a full binary tree of height k, there are 2k-1 internal nodes.
→ A Binary Tree is full if every node has 0 or 2 children.
→ In a Full Binary, number of leaf nodes is number of internal nodes plus 1
L = I + 1
Where,
L = Number of leaf nodes,
I = Number of internal nodes.
Question 260
A binary tree is said to have heap property if the elements along any path :
A
from leaf to root are non–increasing
B
from leaf to root are non–decreasing
C
from root to leaf are non–decreasing
D
from root to leaf are non–increasing
       Data-Structures       Binary-Trees       UGC NET CS 2009-June-Paper-2
Question 260 Explanation: 
A heap is a complete binary tree. A binary tree is said to have heap property if the elements along any path from root to leaf are non–increasing
Question 261
Recursive functions are executed in a
A
First in first out-order
B
Last in first out-order
C
Parallel fashion
D
Load balancing
       Data-Structures       Recursion       UGC NET CS 2009 Dec-Paper-2
Question 261 Explanation: 
Recursive functions are executed in a last in first out-order. It is using stack data structure to evaluate recursive functions.
Question 262
If the number of leaves in a strictly binary tree is an odd number, then what can you say with full conviction about total number of nodes in the tree ?
A
It is an odd number.
B
It is an even number.
C
It cannot be equal to the number of leaves.
D
It is always greater than twice the number of leaves.
       Data-Structures       Data-Structures       UGC NET CS 2009 Dec-Paper-2
Question 262 Explanation: 
Strictly binary tree with n leaf nodes always has 2n-1 nodes.
Ex: n=5
= (2*5)-1
= 9
Question 263
At a hill station, the parking lot is one long driveway snaking up a hill side. Cars drive in and park right behind the car in front of them, one behind another. A car can’t leave until all the cars in front of it have left. Is the parking lot more like
A
An array
B
A stack
C
A queue
D
A linked list
       Data-Structures       Queues-and-Stacks       UGC NET CS 2009 Dec-Paper-2
Question 263 Explanation: 
The above data clearly using first in first out(FIFO) condition. FIFO we are using queue data structure.
Question 264
With regard to linked list, which of the following statement is false ?
A
An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case.
B
An algorithm for deleting the first element in a singly linked list requires 0(n) operations in the worst case.
C
An algorithm for finding the maximum value in a circular linked list requires 0(n) operations.
D
An algorithm for deleting the middle node of a circular linked list requires 0(n) operations.
       Data-Structures       Linked-List       UGC NET CS 2009 Dec-Paper-2
Question 264 Explanation: 
Deleting the first element in a singly linked list requires 0(1) operations in the worst case.
Question 265
A hash function f defined as f(key) = key mod 7, with linear probing used to resolve collisions. Insert the keys 37, 38, 72, 48, 98 and 11 into the table indexed from 0 to 6. What will be the location of 11 ?
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC NET CS 2009 Dec-Paper-2
Question 265 Explanation: 
Given data, insertion order is 37, 38, 72, 48, 98, 11
Hash function = f(key) = key mod 7

Question 266
In a heap, every element is __________ of all the elements in the subtree.
A
maximum
B
minimum
C
sum
D
product
E
None of the above
       Data-Structures       Heap-Tree       UGC NET CS 2008 Dec-Paper-2
Question 266 Explanation: 
Heap is complete binary tree. Sometimes we are calling as binary heap that may be either Max heap or Min heap.
In Max heap→ The root element is greater than of his all childs.
In Min heap→ Te root element is smaller than of his all childs.
Question 267
If (rear == maxsize -1) rear=0; else rear=rear+1; is required in :
A
Circular Queue
B
Linear Queue
C
Stack
D
Deque
       Data-Structures       Queues-and-Stacks       UGC NET CS 2008 Dec-Paper-2
Question 268
Which of the following does not define a tree ?
A
A tree is a connected acyclic graph.
B
A tree is a connected graph with n-1 edges where ‘n’ is the number of vertices in the graph.
C
A tree is an acyclic graph with n-1 edges where ‘n’ is the number of vertices in the graph.
D
A tree is a graph with no cycles.
       Data-Structures       Trees       UGC NET CS 2008-june-Paper-2
Question 268 Explanation: 
→ An undirected graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. An undirected graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints.
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas "A tree is a graph with no cycles." is not always correct as it can be bipartite.
Hence D does not define a tree.
Question 269
Which of the following data structures is most efficient in terms of both space and time to reverse a string of characters ?
A
Linked list
B
Stack
C
Array
D
Tree
       Data-Structures       Queues-and-Stacks       UGC NET CS 2008-june-Paper-2
Question 269 Explanation: 
To print values in reverse order we are preferring stack data structure only. Stack using Last in first out(LIFO) procedure.

Question 270
Which of the following can be the sequence of nodes examined in a binary search tree while searching for key 98 ?
A
100,50,75, 60, 98
B
100, 120, 90, 95, 98
C
200,70,100, 95, 98
D
75, 150, 90, 80, 98
       Data-Structures       Binary-Trees       UGC NET CS 2008-june-Paper-2
Question 270 Explanation: 
Binary search tree will follow some rules
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform


Question 271
Consider the following linked list: Which of the following piece of code will insert the node pointed to by q at the end of the list ?
A
for (p=list; p !=NULL; p=p →next); p=q;
B
for (p=list; p !=NULL; p=p →next); p →next=q;
C
for (p=list; p →next!=NULL; p=p→next); p=q;
D
for (p=list; p →next !=NULL; p=p →next); p →next=q;
       Data-Structures       Linked-List       UGC NET CS 2007-Dec-Paper-2
Question 271 Explanation: 
→ n order to add a new node to the end of the list, first we need to traverse the entire list.
→ To the traverse the list, we will take one pointer.
→ We will traverse the list till the end by moving the pointer to next node.
→ The pointer will point to the last node and from there the pointer next address will point to the new node.
Option D will provide the above steps.
Q
Question 272
Consider a rooted tree in which every node has at least three children. What is the minimum number of nodes at level i (i > 0) of the tree ? Assume that the root is at level 0 :
A
3i
B
3i
C
3
D
3i + 1
       Data-Structures       Trees       UGC NET CS 2007-Dec-Paper-2
Question 272 Explanation: 
From the given question,
Given condition is every node has at least three children.
the root node is present at level 0, here only one is present(30)
at level 1, three nodes are present based upon the condition( 31 nodes)
at level 2, nine nodes will be present (32 nodes ) [Each node has at least three children]
and so on the at level "i", 3i nodes will be present.
Question 273
Which of the following data structure is used to implement recursion ?
A
Arrays
B
Stacks
C
Queues
D
Linked lists
       Data-Structures       Queues-and-Stacks       UGC NET CS 2007-Dec-Paper-2
Question 273 Explanation: 
→ Stack is used to implement recursion. It uses Last in first out procedure.
→ Recursion is one the application of stack. It supports many applications.
Applications:
1. Expression Evaluation
2. Expression Conversion
3. Syntax Parsing
4. Backtracking
5. Parenthesis Checking
6. String Reversal
Question 274
The height of a binary tree with ‘n’ nodes, in the worst case is :
A
O(log n)
B
O(n)
C
Ω(n log n)
D
Ω (n2)
       Data-Structures       Binary-Trees       UGC NET CS 2007-Dec-Paper-2
Question 274 Explanation: 
The height of a binary tree with ‘n’ nodes, in the worst case is O(n). Sometimes, it will get left skewed/ right skewed based on given input.

Question 275
Depth ion travels of the following directed graph is :

A
A B C D E F
B
A B D E F C
C
A C E B D F
D
None of the above
       Data-Structures       Graphs-and-Tree       UGC NET CS 2007 June-Paper-2
Question 275 Explanation: 
To find depth ion traverse using DFS.
Option-A: It is ruled out because we can’t move after C to D. It is violating DFS property.
Option-B: It is following actual DFS structure.

Option-C: It is ruled out because after visiting E we can’t visit B again. It is violating DFS properties.
Question 276
The maximum number of nodes in a binary tree of depth 10 :
A
1024
B
210 - 1
C
1000
D
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2007 June-Paper-2
Question 276 Explanation: 
→ The depth of binary tree starts from 0 but not 1.
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2h+1 -1
= 211 -1
= 2048-1
= 2047

Question 277
Pre order is also known as :
A
Depth first order
B
Breadth first order
C
Topological order
D
Linear order
       Data-Structures       Graphs-and-Tree       UGC NET CS 2007 June-Paper-2
Question 277 Explanation: 
→ Pre order is also known as depth first order.
→ A depth-first order is defined to be the reverse of the order in which we last visit the nodes of the control graph when we create the Depth first spanning tree(DFST).
Question 278
The equivalent postfix express for d/(e+f) + b*c is :
A
defbc/+ +
B
def+/bc+*
C
def+/bc*+
D
None of these
       Data-Structures       Queues-and-Stacks       UGC NET CS 2007 June-Paper-2
Question 278 Explanation: 

Question 279
Application of data structure is queue is :
A
Level wise printing of tree.
B
Implementation of priority queues.
C
Function call implementation
D
Depth first search in a graph
       Data-Structures       Queues-and-Stacks       UGC NET CS 2007 June-Paper-2
Question 279 Explanation: 
Queue applications:
1. CPU scheduling
2. Disk Scheduling
3. synchronization(IO Buffers, pipes, file IO, etc.)
4. Breadth First search
5. Implementation of priority queues.
Question 280
Which of the following addressing mode is best suited to access elements of an array of contiguous memory locations ?
A
Indexed addressing mode
B
Base Register addressing mode
C
Relative address mode
D
Displacement mode
       Data-Structures       Arrays       UGC NET CS 2017 Nov- paper-3
Question 280 Explanation: 
Index mode:
The address of the operand is obtained by adding to the contents of the general register (called index register) a constant value. The number of the index register and the constant value are included in the instruction code.
→ Index Mode is used to access an array whose elements are in successive memory locations (or) contiguous memory locations.
Question 281
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?
A
e = i+n
B
e = i+2n
C
e = 2i+n
D
e = 2n+i
       Data-Structures       Binary-Trees       UGC NET CS 2017 Nov- paper-3
Question 281 Explanation: 
→ A node's path length is the number of links (or branches) required to get back to the root.
→ The root has path length zero and the maximum path length in a tree is called the tree's height.
→ The sum of the path lengths of a tree's internal nodes is called the internal path length and the sum of the path lengths of a tree's external nodes is called the external path length.
External Path Length:

The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path length is 25 (Knuth 1997, pp. 399-400). The internal and external path lengths are related by
E = I + 2n,
where n is the number of internal nodes.
There are 281 questions to complete.