subject – solutions adda

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

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 4 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 5

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 5 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 6

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 6 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 7

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 7 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 8

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 8 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 9

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 9 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 10

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 10 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 11

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 11 Explanation:

Question 12

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 12 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 13

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 13 Explanation:

→ An expression is called the prefix expression if the operator appears in the expression before the operands.

Question 14

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 14 Explanation:

It depends on whether to insert the node at first, middle or last. No proper input in question.
Note: Excluded for evaluation.

Question 15

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 15 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 16

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 16 Explanation:

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

So, total 7 unlabeled nodes are possible. Option (C) is correct.

Question 17

The maximum number of edges in a n-node undirected graph without self loops is

A	n₂
B	n * (n-1)/2
C	n – 1
D	(n + 1) * n/2

Data-Structures Graphs ISRO CS 2008

Question 17 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 18

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 18 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 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	(n²)

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(n²)

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

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 27 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 28

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 28 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 29

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 29 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 30

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 30 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 31

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 31 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 49^th element = base address of array + number of elements before current element * size of element
= 1120 + 48 * 3 = 1264

Question 32

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 32 Explanation:

Question 33

A full binary tree with n leaves contains:

A	n nodes
B	log₂ n nodes
C	2n-1
D	2ⁿ

Data-Structures Binary-Trees ISRO CS 2009

Question 33 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 34

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 34 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 35

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 35 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 36

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 36 Explanation:

Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7

Question 37

A complete binary tree with n non-leaf nodes contains

A	log₂n nodes
B	n+1 nodes
C	2n nodes
D	2n+1 nodes

Data-Structures Binary-Trees ISRO-2016

Question 37 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 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(n^0.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 n^n-2 number of different trees
n=4. Here, n is number of nodes.
4^4-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

A full binary tree with n non-leaf nodes contains

A	log ₂ n nodes
B	n+1 nodes
C	2n nodes
D	2n+1 nodes

Data-Structures Binary-Trees Nielit Scientist-C 2016 march

Question 70 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 71

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

Data-Structures Heap-Tree Nielit Scientist-C 2016 march

Question 71 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 72

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 ₂ n)
B	O(nlog ₂ n)
C	O(n)

Data-Structures Heap-Tree Nielit Scientist-C 2016 march

Question 72 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 73

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 73 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 74

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 74 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 75

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 75 Explanation:

Question and options are wrong. So, excluded for evaluation.

Question 76

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 76 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 77

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 77 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 78

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 78 Explanation:

Question 79

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 79 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 80

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 80 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 81

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 81 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 82

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 82 Explanation:

Question 83

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 83 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 84

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 84 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 85

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 85 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 86

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 86 Explanation:

a+bc-d＾e＾f
⟶ left to right
Step 1: abc+

Question 87

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 87 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 88

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 88 Explanation:

Max-Heap has 5 elements:

The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.

Question 89

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 89 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 90

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 90 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(V²).

Question 91

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 91 Explanation:

Total nodes = nk+1 (1 for root)
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1

Question 92

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 92 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 93

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 93 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 94

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 94 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 95

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 95 Explanation:

Post order: 5,4,10,8,6,17,31,49,43,19,11

Question 96

A complete binary tree with the property K_ni>=K_cn where K_n is n^thnode value and K_c 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 96 Explanation:

A complete binary tree with the property K_ni>=K_cn where K_n is n^thnode value and K_c be the value of its child node is called heap

Question 97

___ 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 97 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 98

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+iNS
B	A+(iN+j)S
C	A+(iN+jM)*S
D	A+(iM+jN)*S

Data-Structures Nielit STA [02-12-2018]

Question 98 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 99

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 99 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 100

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 100 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 101

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 101 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 ¹⁰ ⇒ 0.37(approximately)

Question 102

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 102 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 103

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 103 Explanation:

Recursion and Expression evaluation is implemented by using Stack.

Question 104

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 104 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 105

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 105 Explanation:

Question 106

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 106 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 107

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 107 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 108

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 108 Explanation:

Question 109

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 109 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 110

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 110 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 ² -1=3

Question 111

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 111 Explanation:

Adjacency Matrix
● Uses O(n² ) 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 ² )
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 112

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 112 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 113

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 113 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 114

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 114 Explanation:

Final Pop sequence: 22112

Question 115

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 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 CS 2015

Question 115 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 116

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 116 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 117

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 117 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 118

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 118 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 119

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 119 Explanation:

→ Height of the full binary tree 2^h -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, 2^h-1 = 2⁹ = 512.
The nodes with degree 2 are internal nodes 2^h-1 - 1 = 511.

Question 120

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 120 Explanation:

Question 121

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 121 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 ₂(l)⎤ + 1 = ⎡ log ₂ ((n + 1 )/2)⎤ + 1 = ⎡ log₂ (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 122

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 122 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 123

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 123 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 124

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 124 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 125

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 125 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 126

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 126 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 = ⌈(log₂ 31)⌉
= ⌈4.954196310386876⌉
⇒5

Question 127

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 127 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 128

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 128 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 129

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 130

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 130 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 131

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 131 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 132

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 132 Explanation:

⌈log₂n⌉
=log₂63
=6

Question 133

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 133 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 134

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 134 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 135

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 135 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 136

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 136 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 137

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 137 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 138

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 138 Explanation:

Declaration syntax is
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};

Question 139

The worst case complexity for searching an element in binary search tree is:

A	O(lgn)
B	O(nlogn)
C	O(n²)
D	O(n)

Data-Structures Binary-search-tree KVS 22-12-2018 Part-B

Question 139 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 140

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 140 Explanation:

Process scheduling operating system is application of queue.

Question 141

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 141 Explanation:

→ Recursion is implemented stack
→ Scheduling can be implemented using Queue.
→ The inorder traversal of binary search gives sorting order.

Question 142

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 142 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 143

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 143 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 144

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 144 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 145

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 145 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 146

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 146 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 147

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 147 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 148

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 148 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 149

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 149 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 150

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 150 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 151

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 151 Explanation:

Consider the array with “n” elements . smaller index value is 0(lower bound) and lager index value is “n-1”(upper bound)

Question 152

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 152 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 153

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 153 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 154

Remove procedure is implemented using

A	String
B	Queue
C	Stack
D	Linked list

Data-Structures Queues-and-Stacks KVS DEC-2017

Question 154 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 155

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 155 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 156

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 156 Explanation:

Here, inoperate the traversal yields the expression means INORDER.
Inorder→ left,root and right.
a+b*d-c/f

Question 157

The five items P<Q<R

A	S
B	P
C	Q
D	R

Data-Structures Queues-and-Stacks KVS DEC-2017

Question 157 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 158

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 158 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 159

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 159 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 160

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 160 Explanation:

→A[0] is first element and a[4] means 5^th 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 161

Array A[8,15] is sorted in row major order with first element A[1,1] stored at location A₀. Assuming that each element of the array is size of size s, element A[i,j] can be accessed at

A	A₀ + 15s(i-1)+(j-1)
B	A₀ + 8s(i-1)+(j-1)
C	A₀ + 15s(j-1)+(i-1)
D	A₀ + 8s(j-1)+(i-1)

Data-Structures Arrays KVS 30-12-2018 Part B

Question 161 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 162

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 n_A is the number of elements in stack A and n_B is the number of elements in stack B, then overflow occurs when Push Operation is performed on either stack and

A	n_A=n_B
B	n_A=n_B=n
C	n_A+n_B=n
D	n_A+n_B>=n

Data-Structures Queues-and-Stacks KVS 30-12-2018 Part B

Question 162 Explanation:

→n_Ais the number of elements in stack A and n_B is the number of elements in stack B, Where “n” is total elements we can insert into stack.
→The sum of the n_A and n_B is equal to the number of elements there is no possibility of inserting element into stack.

Question 163

Translation of infix string a+b*c-d/e*h to postfix form is

A	abc+deh/-
B	ab+cde/h-
C	(a b c)+(de/h-)
D	abc+de/h-

Data-Structures Queues-and-Stacks KVS 30-12-2018 Part B

Question 163 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 164

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 164 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 165

A full binary tree with height h has _____ nodes.(Assume leaves at h=0)

A	2^h-1
B	2^h+1
C	2^h+1-1
D	2^h+1+1

Data-Structures Binary-Trees KVS 30-12-2018 Part B

Question 165 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 166

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 166 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 167

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 167 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 168

Given a tree with k nodes, the sum of degrees of all nodes is

A	2^k-1
B	2*(k-1)
C	2^k+1
D	2((k+1)

Data-Structures Trees KVS 30-12-2018 Part B

Question 168 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 169

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 169 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 170

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 170 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 171

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 171 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 172

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 172 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 173

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 173 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 174

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 174 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 175

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 175 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 176

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 176 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 177

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 177 Explanation:

Here, stack size is 5. Stack operations are explained in step by step.

Question 178

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 178 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 179

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 179 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 180

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 180 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 181

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 181 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 182

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 183

The hash function used in double hashing is of the form:

A	h (k, i) = (h ₁ (k) + h₂ (k) + i) mod m
B	h (k, i) = (h ₁ (k) + h₂ (k) - i) mod m
C	h (k, i) = (h ₁ (k) + i h₂ (k)) mod m
D	h (k, i) = (h ₁ (k) - i h₂ (k)) mod m

Data-Structures Hashing UGC NET CS 2015 Dec- paper-2

Question 183 Explanation:

Double Hashing with second hash function is h(k,i) = (h ₁ (k) + i·h₂ (k)) mod m 0≤ i ≤m-1
h ₁ → hash function
h ₂ → 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 184

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 184 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 185

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 185 Explanation:

Inorder traversal through Left, Root and Right. Inorder yield procedure given below.

Question 186

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 186 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 187

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 187 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 188

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 188 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 189

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 189 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 190

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 190 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 ₁ i+c ₂ i² )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 ² ) % 100
= (94 + 1) % 100
= 95
Step-3: Third pass: (4594 + 2 ² ) % 100
= (94 + 4) %100
= 98
Step-4: Fourth pass: (4594 + 1 ² ) % 100
= (94 + 9) %100
= 103 % 100
= 3

Question 191

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 191 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 192

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 192 Explanation:

→ Backup operation is supported in constant time by the doubly linked list, but not by the singly linked list.

Question 193

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 193 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 194

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 194 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 195

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 195 Explanation:

Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7

Question 196

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 196 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 197

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 197 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 198

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 198 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 199

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 199 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 200

What is the time required to insert an element in a stack with linked implementation ?

A	O (log ₂ n)
B	O (n)
C	O (n log ₂ n)
D	O (1)

Data-Structures Queues-and-Stacks UGC NET CS 2005 june-paper-2

Question 200 Explanation:

Question 201

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 201 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 202

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 202 Explanation:

a, c, d are going to unbalance.

Question 203

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 203 Explanation:

Question 204

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 204 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 205

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 205 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 206

What is the time required to insert an element in a stack with linked implementation ?

A	O (log ₂ n)
B	O (n)
C	O (n log ₂ n)
D	O (1)

Data-Structures Queues-and-Stacks UGC NET CS 2006 Dec-paper-2

Question 206 Explanation:

Average case in linked list:

Worst case in linked list:

Question 207

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 207 Explanation:

Postfix expression: d ef + / bc * +

Question 208

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 208 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 209

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 209 Explanation:

a, c, d are going to unbalance.

Question 210

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 210 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 211

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 211 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 212

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 212 Explanation:

Question 213

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 213 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 214

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 214 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 215

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 215 Explanation:

→ According to priority (or) infix expression we can write expression like this ((A + B^D) / (E – F)) + G
→ Actual tree structure is

Question 216

A full binary tree with n leaves contains

A	n nodes
B	log ₂ n nodes
C	2n –1 nodes
D	2ⁿ nodes

Data-Structures Binary-Trees UGC NET CS 2014 Dec-Paper-2

Question 216 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 217

The minimum number of nodes in a binary tree of depth d (root is at level 0) is

A	2^d – 1
B	2^{d + 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 = 2^d
→A perfect binary tree of height h has 2^h+1 -1 nodes
→Number of leaf nodes in a perfect binary tree of height h = 2^h
→Number of internal nodes in a perfect binary tree of height h = 2^h -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 = 2^h+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

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 222 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 223

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 223 Explanation:

Question 224

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 224 Explanation:

Eccentricity of a vertex u, is
E(u) = max_u∈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 225

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 225 Explanation:

Question 226

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 226 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 227

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 227 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 228

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 228 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 229

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 229 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 230

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 230 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 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(2ⁿ)
→ 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(2ⁿ)
→ 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	2⁰ + 2¹ + ….. 2^h
B	2⁰ + 2¹+ ….. 2^{h – 1}
C	2⁰ + 2¹ + ….. 2^{h + 1}
D	2¹ + ….. 2^{h + 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 2⁰ + 2¹+ ….. 2^h. because every phase we are getting 2^h.
Suppose, in level-3, it have 2³=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 n^n-2.
= 8^8-2
= 262144 trees are possible.
Possibility-2: According to given problem, they are using binary tree based on below formula
= 2ⁿ -n

= 2⁸ -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(n²)

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 log₂n
B	About 2 log₂n
C	About n log₂n
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(log₂n). As per the given constraint, we have to calculate individually of left farthest node and right farthest node height.
=log₂n*log₂n
=2*log₂n or (log₂n)²

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	2^k-1
B	2^k-1
C	2^k
D	2^k+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	3ⁱ
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(3⁰)
at level 1, three nodes are present based upon the condition( 3¹ nodes)
at level 2, nine nodes will be present (3² nodes ) [Each node has at least three children]
and so on the at level "i", 3ⁱ 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	Ω (n²)

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	2¹⁰ - 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
= 2^h+1 -1
= 2¹¹ -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 = 2ⁿ+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.

Question 282

A recursive function h, is defined as follows :

h(m) = k, if m = 0

= 1, if m = 1

= 2 h(m – 1) + 4h(m – 2), if m ≥ 2

If the value of h(4) is 88 then the value of k is :

A	0
B	1
C	2
D	-1

Data-Structures Recursion UGC NET CS 2017 Jan- paper-3

Question 282 Explanation:

If k=2, 24 + 32 × 2 = 24 + 64 = 88

Each iteration:
h(2) = 2h(1) + 4h(0) = 2 + 4k
h(3) = 2h(2) + 4h(1) = 4 + 8k + 4 = 8 + 8k
h(4) = 2h(3) + 4h(2) = 16 + 16k + 8 +16k = 32k + 24 = 88 (if k=2)

Question 283

Consider a hash table of size m = 10000, and the hash function h(K) = floor (m(KA mod1)) for A = ( √(5) – 1)/2. The key 123456 is mapped to location ______.

A	46
B	41
C	43
D	48

Data-Structures Hashing UGC NET CS 2016 Aug- paper-3

Question 283 Explanation:

Given data,
-- Hash table size(m)=10000
-- Hash function(h(K))= floor (m(KA mod1))
-- A=(√(5)-1)/2
-- key(K)=123456
-- location=?
Step-1: Hash function(h(K))= floor (m(KA mod1))
h(123456) = floor(10000 * (123456 * (√5 − 1) / 2) mod 1)
= floor(10000 * (76300.004115 mod 1)
= floor(10000 * (.004115))
= floor(41.15)
= 41

Question 284

A priority queue is implemented as a max-heap. Initially, it has ve elements. The level-order traversal of the heap is as follows: 20, 18, 15, 13, 12 Two new elements ‘10’ and ‘17’are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:

A	20, 18, 17, 15, 13, 12, 10
B	20, 18, 17, 12, 13, 10, 15
C	20, 18, 17, 10, 12, 13, 15
D	20, 18, 17, 13, 12, 10, 15

Data-Structures Heap-Tree UGC NET CS 2016 Aug- paper-3

Question 284 Explanation:

Question 285

The number of different binary trees with 6 nodes is ______.

A	6
B	42
C	132
D	256

Data-Structures Binary-Trees UGC NET CS 2016 July- paper-3

Question 285 Explanation:

Using catalan formula to find the total number of binary trees is (2n)! / (n! * (n+1)!)

Here, n=6

= (2*6)! / (6! * (6+1)!)

= (12)! / (6! * (7)!)

= 479001600 / (720*5040)

= 132

Question 286

Which one of the following arrays represents a binary max-heap?

A	[26, 13, 17, 14, 11, 9, 15]
B	[26, 15, 14, 17, 11, 9, 13]
C	[26, 15, 17, 14, 11, 9, 13]
D	[26, 15, 13, 14, 11, 9, 17]

Data-Structures Binary-Heap UGC NET CS 2016 July- paper-3

Question 286 Explanation:

Question 287

Suppose that we have numbers between 1 and 1,000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined ?

A	925, 221, 912, 245, 899, 259, 363, 364
B	3, 400, 388, 220, 267, 383, 382, 279, 364
C	926, 203, 912, 241, 913, 246, 364
D	3, 253, 402, 399, 331, 345, 398, 364

Data-Structures Binary-Trees UGC NET CS 2016 July- paper-3

Question 287 Explanation:

Question 288

Consider double hashing of the form
h(k,i)=(h ₁ (k)+ih₂ (k)) mod m
Where h ₁ (k)=k mod m
h ₂ (k)=1+(k mod n)
Where n=m-1and m=701
for k=123456, what is the difference between first and second probes in terms of slots?

A	255
B	256
C	257
D	258

Data-Structures Hashing UGC NET June-2019 CS Paper-2

Question 288 Explanation:

Given h(k,i)=h1(k)+ih2(k)
where h1(k)=k mod m
h2(k)=1+k mod n
where n=m-1 and m=701. For k=123456
h1(k)=123456 mod 701
h1(k)=80
h2(k)=1+(123456 mod 700)
h2(k)=1+256=257
1st probe: i=1
h(k,i)=h1(k)+ih2(k)
h(k,1)=h1(k)+ih2(k)
h(k,1)=80+257=337
h(k,1)=337
2nd probe: i=2
h(k,2)=80+2257
h(k,2)=80+514
h(k,2)=594
∴ Difference h(k,2)-h(k,1)
594-337
257

Question 289

Which of the following is an application of depth-first search?

A	Only topological sort
B	Only strongly connected components
C	Both topological sort and strongly connected components
D	Neither topological sort not strongly connected components

Data-Structures Graphs-and-Tree UGC NET June-2019 CS Paper-2

Question 289 Explanation:

Both topological sort and strongly connected components are applications of DFS.
Topological sort time complexity is O(V+E)
Strongly connected components time complexity is O(V+E)
DFS time complexity is O(V+E)

Question 290

Consider the game tree given below:

A	4
B	7
C