Data Structure MCQ with Answers Set-2

This post contains a computer network related to 20 multiple-choice questions (DS SET-2) that help you to go through the subject and prepare you for Data Structure related questions in competitive exams.

Data Structure MCQ Test Series Set-2

Total Number of Questions: 20
Each question carries equal marks i.e 1
No Negative Marking

Page 1 of 2

1. Which of the following data structures is used for converting the infix notation to postfix notation?

A.Branch

B.Tree

C.Queue

D.Stack

E.Graph

2. A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.

A.$\Theta(1),\Theta(1)$

B.$\Theta(1),\Theta(n)$

C.$\Theta(n),\Theta(1)$

D.$\Theta(n),\Theta(n)$

The preorder traversal of a binary search tree is 15, 10, 12, 11 20, 18, 16, 19. Which one of the following is the post-order traversal of the tree?

A.10, 11, 12, 15, 16, 18, 19, 20

B.11, 12, 10, 16, 19, 18, 20, 15

C.20, 19, 18, 16, 15, 12, 11, 10

D.19, 16, 18, 20, 11, 12, 10, 15

4. When a push operation is performed on a stack that is already full, it might result in __________.

A.Overflow

B.Underflow

C.Peep

D.Push

E.Pop

5. What is the worst-case time complexity of inserting elements into an AVL tree with $n^{2}$ elements initially?

A.$\Theta(n^{4})$

B.$\Theta(n^{2})$

C.$\Theta(n^{2}logn)$

D.$\Theta(n^{3})$

6. Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

A.$k \geq 2^{N}$

B.$k \geq n$

C.$k \leq n^{2}$

D.$k \leq 2^{n}$

7. _________ tree has all the nodes having at most two child nodes.

A.Complete Binary

B.Binary

C.Binary search

D.AVL

E.Directed

8. In which of the following linked lists, the link of the last item points to the first element as the next item?

A.Singly Linked List

B.Doubly Linked List

C.Circular Linked List

D.Complex Linked List

E.None of these

9. Which of the following trees examines the height of left sub-trees and right sub-trees and ensures that the difference between their heights is not greater than 1?

A.AVL

B.MST

C.B+

D.A+

E.B+ and A+

10. What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

A.$\Theta(n)$

B.$\Theta(n log n)$

C.$\Theta(n^{2})$

D.$\Theta(1)$

Page 2 of 2

11. __________ is a linear data structure.

A.Trees

B.Graphs

C.Arrays

D.Database

E.Object

12. Which type of data structure is used to represent the internal storage of data in RDBMS efficiently?

A.Stack

B.B+ Tree

C.Circular Queue

D.Linked List

E.None of these

13. Consider the following ANSI C program:
#include <stdio.h>
#include <stdlib.h>
Struct Node{
Int value;
Struct Node *next;};
Int main (){
Struct Node *boxE, *head, *boxN; int index=0;
boxE=head=(struct Node *) malloc (sizeof(struct Node));
head->value=index;
for (index=1; index<=3; index++){
boxN=(struct Node*)malloc(sizeof(struct Node));
boxE->next=boxN;
boxN->value=index;
boxE=boxN;}
for (index=0; index<=3; index++){
printf(“Value at index %d is %d\n”, index, head->value);
head=head->next;
printf(“Value at index %d is %d\n”, index+1, head->value);}}
Which one of the statements below is correct about the program?

A.Upon execution, the program creates a linked list of five nodes.

B.Upon execution, the program goes into an infinite loop.

C.It has a missing return which will be reported as an error by the compiler.

D.It dereferences an uninitialized pointer that may result in a run-time error.

14. Which data structure is capable of performing recursion?

A.Stack

B.Tree

C.Pointer

D.Queue

E.None of these

15.

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?

A.The root of T can never be an articulation point in G.

B.The root of T is an articulation point in G if and only if it has 2 or more children.

C.A leaf of T can be an articulation point in G.

D.If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

16.

In a balanced binary search tree with n elements, what is the worst-case time complexity of reporting all elements in the range [a,b]? Assume that the number of reported elements is k.

A.$\Theta (log n)$

B.$\Theta (log n+k)$

C.$\Theta (k log n)$

D.$\Theta (n log k)$

17. The post order traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The in order traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _____.

A.2

B.4

C.6

D.8

18.

Consider a double hashing scheme in which the primary hash function is $h_{1} (k) = k mod 23$ and the secondary hash function is $h_{2} (k) = 1+(k mod 23)$.Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is

A.12

B.13

C.14

D.15

19.

Consider the following sequence of operations on an empty stack.

Push (54); Push (52); pop (); Push (55); Push (62); s=pop ();

Consider the following sequence of operations on an empty queue.

enqueue (21); enqueue (24); dequeue ();enqueue (28); enqueue (32); q=dequeue ();

The value of s+q is ____

A.85

B.82

C.86

D.82

20.

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________.

A.4.25

B.4.15

C.3.25

D.3.15

Data Structure MCQ Test Series Set-2

Total Number of Questions: 20

Each question carries equal marks i.e 1

No Negative Marking

Related