Font size
WorksheetsAdvanced Data Structure
Total questions: 153
Worksheet time: 2hrs 10mins
Array can be classified in how many types ?
1
2
3
More than 4
Null
address of first node
only data value
only address
People standing in queue at railway ticket counter is that
Queue
Stack
Array
Tree
Linked list
Array
Both Array & Linked list
None of these
Rear / Back
Front
Both
None
Which of the following are types of data structures?
Select all that are correct.
Arrays
Lists
Records
Tables
Files
Here is a Python list
data = ["Computer", "Science", "is", "awesome"]
Which item has an index of 2?
Computer
Science
is
awesome
Here is a 2-dimensional Python list.
scores = [["Bob", 15] , ["Jane", 32] , ["Dave", 4] , ["Lucy", 19]]
Which data is at index scores[3][1]?
Lucy
19
Dave
4
To store larger sets of data that multiple users can access, we use a
(a)
To store data from a list into a text file, it will be structured as a ...
record
constant
variable
array
What is the difference between a list and a variable?
The elements in a list can be changed, while a variable cannot.
A list can store multiple items while a variable holds only one.
A list is easier to use than a variable.
How can data be stored when a program is not running?
Lists
Arrays
Variables
Text files
Which of these statements about record structures is NOT true?
A record structure is a collection of related fields
A field is a variable
Each field in a record can have a different data type
You can create record structures in Python
To find out how many characters are in the string dataStoredHere, which Python function do we use?
len(dataStoredHere)
COUNT(dataStoredHere)
LEN(dataStoredHere)
dataStoredHere.length
Which Python function will convert a string to all upper-case characters?
data = "here is a string"
data.toUpper()
data.upper
upper(data)
data.upper()
The best technique for handling collision is
Separate Chaining
Linear Probing
Double hashing
Quadratic probing
Choose the correct option denoting the most desirous characteristics of a hash function.
It must cause more collisions.
It must cause less collisions.
It must be easy to implement.
It must occupy less space.
People have used the word ________ to mean computer information that is transmitted or stored.
Beta
Data
Database
None of above
_____________ specifies how we enter data into our programs and what type of data we enter.
data type
data
datum
all of above
Array is ___________ data type.
user defined
primary
derived
all of above
A data structure in which elements can be inserted or deleted at/from both ends but not in the middle is?
Priority queue
Dequeue
Circular Queue
Queue
Which is the most appropriate data structure for reversing a word?
Stack
Queue
Hashing
Tree
Quick sort follows which type of algorithm
Greed
Top down
Divide and Conquer
Branch and bound
Which sorting algorithm is known for its average time complexity of O(n log n)?
Bubble sort
Insertion sort
Merge sort
Selection sort
What data structure is best suited for implementing undo functionality in a text editor?
Queue
Stack
Linked list
Heap
which of the following are the tree traversal
Hashing
Defense first search
Bottom first search
Depth first search
Which data structure is suitable for implementing a breadth-first search algorithm?
Stack
Queue
Heap
Linked list
What is the best data structure for implementing a priority queue?
Heap
Queue
Stack
Linked list
The prefix form of A-B/ (C * D ^ E) is?
-A/B*C^DE
-A/BC*^DE
-ABCD*^DE
-/*^ACBDE
Minimum nodes possible height for a AVL tree with 16 nodes
2
3
4
Either 3 or 4
In AVL tree, the balance factor of a node is defined as the difference between the heights of its left and right subtrees. What is the range of the balance factor for a node in a balanced AVL tree?
-1 to 1
0 to 2
-2 to 2
1 to 3
Consider the binary tree given : and find the level order
5,3,8,1,4,9,7
5,3,8,1,4,7,9
1,3,4,5,7,8,9
1,4,3,5,8,7,9
Given the following preorder and inorder traversals of a binary tree:
Preorder: M, N, O, P, Q, R, S, T
Inorder: O, P, Q, R, N, T, M, S
Reconstruct the binary tree and determine the number of values after the root node.
1
2
5
4
Consider an undirected graph with weighted edges, where the weights represent the cost of traversal between nodes. You are tasked with finding the path between two nodes with the minimum total cost. Which traversal algorithm is more suitable for this scenario?
BFS
DFS
Both DFS and BFS
It depends on specific graph
Suppose you have a doubly linked list, and you want to delete a node given its pointer. What is the time complexity to delete the node?
O(1)
O(log n)
O(n)
O(n^2)
Consider the following array: [7, 4, 2, 8, 5, 1, 6, 3]. If you use the QuickSort algorithm and choose the pivot as the last element, what will be the array after the first partitioning step?
[2, 4, 1, 3, 5, 7, 6, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[3, 4, 2, 1, 5, 7, 6, 8]
[7, 4, 2, 8, 5, 1, 6, 3]
You have a hash table with 8 slots and the following hash function: ℎ(K)=(3K+7)mod 8 If you want to search for the key 5, what is the index where it will be located in the hash table?
5
6
8
7
Why is a circular queue preferred in certain applications over a regular queue?
Circular queues have better memory utilization than regular queues.
Circular queues avoid the issue of front and rear pointers reaching the end, making them more efficient for continuous data streams.
Regular queues have faster insertion and deletion operations compared to circular queues.
Circular queues are only used in specialized applications and are not generally preferred.
Select the non-linear data structure from the options below:
Queue
linked list
Array
Tree
Consider an array of integers: [10, 25, 30, 45, 50, 65, 70, 85]. If you are searching for element 10, which searching technique would be most efficient
Linear Search
Binary Search
Hashing
Jump Search
Matrix A - p rows, q columns
Matrix B - s rows, t columns
if ((p !=s) && (q!=t)) - Then what will happen for Addition of Matrix A and B?
(a)
Consider the following statements in a Queue:
enqueue(8);
enqueue(2);
enqueue(6);
enqueue(4);
dequeue();
enqueue(5);
What is the current size of the queue?
5
6
4
3
If the elements P, W,S,D are placed in a stack and are deleted one at a time, what is the order of removal?
PWSD
PDWS
DWSP
DSWP
Write the postfix notation of the following infix expression.
A+B*C+(D*E+F)*G
(a)
Write only the function to delete a node at the beginning of a doubly linked list.
Queue Implementation using Array. Array name is Queuearray and rear is the current element pointer and "data" is the new item to be added. For adding a new element int the queue, is the following statement correct?
queue[rear] = data;
Queuearray[rear] = data;
True
False
An exam was attended by 80 students. Min marks-0, Max Mark-50. I need to store the frequency of marks >30. What will be the size of the array needed for it?
80
20
30
50
Below is a stack operation
int x = a[top--];
return x;
if top becomes zero, then what is that condition called?
overflow
underflow
pop
push
Write the condition to check whether a queue is full or not?
(rear, front are the pointers, size of the array =MAX)
(a)
What is the way to increment the rear end of a circular queue?
(Rear+1) mod MAX
Rear mod MAX
(Front+1) mod MAX
(Rear-1) mod MAX
Write the function to insert a node to the beginning of a singly linked list?
The front and rear pointers of a queue are monitored in a linked list implementation. During an insertion into a NONEMPTY queue, which of these pointers would change?
Only rear pointer
Only Front pointer
Both Front and Rear
Which of the following statement about binary tree is CORRECT?
Every binary tree is either complete or full
Every complete binary tree is also a full binary tree
Every full binary tree is also a complete binary tree
A binary tree cannot be both complete and full
Which type of traversal of binary search tree outputs the value in sorted order?
Pre-order
Post-order
In-Order
None
A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of the node in the left sub-tree and right sub-tree of the root, respectively, is
(4, 7)
(7, 4)
(8, 3)
(3, 8)
In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?
Inorder Successor is always a leaf node
Inorder successor is always either a leaf node or a node with empty left child
Inorder successor may be an ancestor of the node
Inorder successor is always either a leaf node or a node with empty right child
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
2
3
4
5
In the balanced binary tree in the figure given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?
1
3
7
8
Which of the following sequences denotes the post order traversal sequence of the tree?
f e g c d b a
g c b d a f e
g c d b f e a
f e d g c b a
Consider the following operation performed on a stack of size 5.
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
4
3
2
1
Consider the following definition in c programming language.
struct node { int data; struct node next; }
typedef struct node NODE;
NODE *ptr;
Which of the following c code is used to create new node?
ptr = (NODE*)malloc(sizeof(NODE));
ptr = (NODE*)malloc(NODE);
ptr = (NODE*)malloc(sizeof(NODE*));
ptr = (NODE)malloc(sizeof(NODE));
What does the following function 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); }
Prints all nodes of linked lists
Prints all nodes of linked list in reverse order
Prints alternate nodes of Linked List
Prints alternate nodes in reverse order
What is the output of following function for start pointing to first node of following linked list? 1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);
if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
}
1 4 6 6 4 1
1 3 5 1 3 5
1 2 3 5
1 3 5 5 3 1
Assume that the operators +,-, X are left associative and ^ is right associative.
The order of precedence (from highest to lowest) is ^, X, +, -.
The postfix expression for the infix expression
a + b X c – d ^ e ^ f is?
abc X+ def ^^ –
abc X+ def ^^ –
ab+c Xd – e ^f^
-+aXbc^ ^def
After performing these set of operations, what does the final list look contain? InsertFront(10);
InsertFront(20);
InsertRear(30);
DeleteFront();
InsertRear(40);
InsertRear(10);
DeleteRear();
InsertRear(15);
display();
10 30 10 15
20 30 40 15
20 30 40 15
20 30 40 15
Convert the following infix expressions into its equivalent postfix expressions.
(A + B ⋀D)/(E – F)+G
(A B D ⋀ + E F – / G +)
(A B D +⋀ E F – / G +)
(A B D ⋀ + E F/- G +)
(A B D E F + ⋀ / – G +)
What does the following code do?
public Object function()
{ if(isEmpty())
return -999;
else
{ Object high;
high = q[front];
return high; } }
Dequeue
Enqueue
Return the front element
Return the last element
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?
struct node
{
int value;
struct node *next;
};
void rearrange(struct node *list)
{
struct node p, q;
int temp;
if ((!list) || !list->next)
return;
p = list;
q = list->next;
while(q)
{
temp = p->value;
p->value = q->value;
q->value = temp;
p = q->next;
q = p?p->next:0;
}
}
1,2,3,4,5,6,7
2,1,4,3,6,5,7
1,3,2,5,4,7,6
2,3,4,5,6,7,1
Consider the function f defined below.
struct item
{
int data;
struct item * next;
};
int f(struct item *p)
{
return (
(p == NULL) ||
(p->next == NULL) ||
(( P->data <= p->next->data) && f(p->next))
);
}
not all elements in the list have the same data value
the elements in the list are sorted in non-decreasing order of data value
the elements in the list are sorted in non-increasing order of data value
None of them
You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?
Delete the first element
Insert a new element as a first element
Delete the last element of the list
Add a new element at the end of the list
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?
O(n)
O(log2 n)
O(logn)
O(1)
Assume there is a tree in which every node has a value greater than value of any node in its LST but lesser
than any node in its RST. An in order traversal of this tree shall result in
A. a sorted sequence in ascending order
B. a sorted sequence in descending order
C. sequence is sorted only of tree is a complete or full binary tree
D. sequence is not always sorted
Assume an algebric expression E is represented using the binary tree
A. the variable in E forms external nodes and operators in internal nodes
B. the operators in E forms external nodes and variables in internal nodes
C. the variable and operations in E forms internal nodes
D. the variable and operations in E forms external nodes
Balance factor is defined as the
A. Difference between Left sub tree and Right sub tree
B. Difference between the height of Left sub tree and the height of Right sub tree
C. Difference between Right sub tree and Left sub tree
D. Difference between the height of Right sub tree and the height of Left sub tree
Assume the level of root node is 1 and the levels of left and right children of root is 2. The maximum number of
nodes on level i of a binary tree is
A. 2^i
B. 2^(i-1)
C. 2^(i+1)
D. 2^i+1
The maximum number of binary trees that can be formed with three nodes
A. 3
B. 1
C. 5
D. 4
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-1
B. 2^(h-1)-1
C. 2^(h+1)-1
D. 2*(h+1)
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of
nodes in a binary tree of height 4 are
A. 31 and 5
B. 32 and 5
C. 15 and 5
D. 15 and 4
When the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree, the CORRECT option is
A. W is an internal node
B. V is a leaf node
C. S is a root node
D. B is a leaf node
When the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree, the CORRECT option is
A. Height of tree is 2
B. Height of tree is 3
C. Height of tree is 4
D. Height of tree is 5
When the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree, the CORRECT option is
A. Balance Factor of node S is -2
B. Balance Factor of node S is +2
C. Balance Factor of node S is -1
D. Balance Factor of node S is +1
When the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree, the CORRECT option is
A. Balance Factor of all nodes are -1, 0 or +1, so the tree is an AVL tree
B. Balance Factor of node S needs to be altered
C. Balance Factor of node M needs to be altered
D. Node S has to be rotated to Right for Height adjustment
Initially the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree. It has been checked and made
to an AVL tree. The CORRECT option is
A. S forms the leaf node
B. S forms the root node
C. S has two children
D. S has only Right child T
Initially the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree. It has been checked and made
to an AVL tree. The CORRECT option is
A. Double rotation (Right, Left) makes the tree into an AVL tree
B. Single Right rotation makes the tree into an AVL tree
C. Single Left rotation makes the tree into an AVL tree
D. Double rotation (Left, Right) makes the tree into an AVL tree
Initially the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree. The CORRECT option is
A. Zig-zag rotation is required to splay the node H
B. Zig-zag rotation is required to splay the node V
C. Zig-zag rotation is required to splay the node W
D. Zig-zag rotation is required to splay the node S
Initially the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree. The CORRECT option is
A. Splaying T requires zig-zag, and zig rotation
B. Splaying T requires zig-zig, and zig rotation
C. After splaying T, height of the tree is 4
D. After splaying T, S takes the position of root
Initially the keys like M, S, G, H, B, V, W, T are inserted into Binary Search Tree. The CORRECT option is
A. After splaying T, the node S forms the Right child of M
B. After splaying T, the node S forms the Left child of V
C. After splaying T, the nodes W, B, H changed their positions
D. After splaying T, the node V takes the position as leaf node
The keys like M, S, G, H, B, V, W, T are inserted into B-tree of order 5. The CORRECT option is
A. Leaf node is split, when key B is inserted
B. Leaf node is split, when key G is inserted
C. Leaf node is split, and B goes to root node
D. Leaf node is split, and G goes to root node
The maximum time taken by linear search algorithm when
A. Search element is in the middle of an array
B. Search element is present as the first item
C. Search element is the maximum of all items
D. Search element is present as the last item
The maximum time taken by binary search algorithm when
A. Search element is in the middle of an array
B. Search element is present as the first item
C. Search element is the maximum of all items
D. Search element is presnt as the last item
Maximum number of comparisons required to search the leaf node of Binary search tree is
A. log n
B. n
C. n+1
D. n-1
The search algorithm(s) which can be implemented using recursive approach is/are
A. Linear search
B. Binary search
C. Both Linear Search and Binary Search
D. No search algorithms
The search algorithm(s) which can be implemented using iterative approach is/are
A. Linear search
B. Binary search
C. Both Linear Search and Binary Search
D. No search algorithms
Identify the correct sequence of sorting algorithms w.r.t their sorting time (increasing order of time taken)
A. Insertion sort, Shell sort, Bubble sort
B. Bubble sort, Insertion sort, Shell sort
C. Shell sort, Insertion sort, Bubble sort
D. Insertion sort, Bubble sort, Shell sort
The algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of desired order
A. Insertion sort
B. Quick sort
C. Selection sort
D. Bubble sort
Q1. The inorder traversal of binary tree is: B C G K L M S V. The preorder is: G C B L K S M V. Post order
traversal is
A. B C K M V S L G
B. B C M V K S L G
C. B C K M S V L G
D. B C K L S M V G
Select the examples of non linear data structures
Google map
Stack of plates
Family Tree
Train
The index of last element in the array is 10,then what will be the size of array
10
11
9
12
(a) data structures arrange element in sequential manner
Give any one real time example for Array
Youtube downloader uses which data structure
stack
queue
linked list
tree
Which data structures used in operating system for job scheduling
stack
queue
tree
linked list
Music player is an example of which data structures
stack
queue
linked list
graph
To store data in the linked list contiguous memory location is essential
True
False
Expansion of ADT
(a)
What is meant by data structures
Queue is a
Non-linear data structure
linear data structure
Queue follows
FIFO
LIFO
None of these
In queue, an element can be inserted in location pointed by
top
front (or head)
rear (or tail)
none of the above
In queue, an element can be deleted in location pointed by
top
front (or head)
rear (or tail)
none of the above
In ordinary queue, priority of every element
can be different
is same
none of the above
In priority queue, a priority is assigned to every element
False
True
In a double-ended queue, an element can be inserted in
front end
rear end
either front or rear end
Dequeue refers to
deletion from queue
double ended queue
demand queue
none of the above
Is it possible to create a doubly linked list using only one pointer with every node.
Not Possible
Yes, possible by storing XOR of addresses of previous and next nodes.
Yes, possible by storing XOR of current node and next node
Yes, possible by storing XOR of current node and previous node
Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.
Possible if size of linked list is even.
Possible if size of linked list is odd
Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X
You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?
Delete the first element
Insert a new element as a first element
Delete the last element of the list
Add a new element at the end of the list
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?
O(n)
O(log2 n)
O(logn)
O(1)
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together
O(Log^(2)N)
O(N)
O(N^2)
Θ(N^2 Log N)
The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?
singly linked list
doubly linked list
circular doubly linked list
array implementation of lists
Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node and lengths of lists are not known. What is worst case time complexity of optimal algorithm to find intersecting node from two intersecting linked lists?
Θ(n*m), where m, n are lengths of given lists
Θ(n^2), where m>n and m, n are lengths of given lists
Θ(m+n), where m, n are lengths of given lists
Θ(min(n, m)), where m, n are lengths of given lists
In a doubly linked list, the number of pointers affected for an insertion operation will be
4
0
1
None of these
Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in O(1) time ?
Insertion at the front of the linked list.
Insertion at the end of the linked list.
Deletion of the front node of the linked list.
Deletion of the last node of the linked list.
What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
If several elements are competing for the same bucket in the hash table, what is it called?
a) Diffusion
b) Replication
c) Collision
d) Duplication
Which of the following is not a technique to avoid a collision?
a) Make the hash function appear random
b) Use the chaining method
c) Use uniform hashing
d) Increasing hash table size
A technique for direct search is
a) Binary Search
b) Linear Search
c) Tree Search
d) Hashing
The goal of hashing is to produce a search that takes
a) O(1) time
b) O(n2 )time
c) O(log n ) time
d) O(n log n ) time
Which of the following statement(s) is TRUE?
I. A hash function takes a message of arbitrary length and generates a fixed length code.
II. A hash function takes a message of fixed length and generates a code of variable length.
III. A hash function may give the same hash value for distinct messages.
I only
II and III only
I and III only
II only
What is direct addressing?
A. Distinct array position for every possible key
B. Fewer array positions than keys
C. Fewer keys than array positions
D. None of the mentioned
What can be the techniques to avoid collision?
A. Make the hash function appear random
B. Use the chaining method
C. Use uniform hashing
D. All of the mentioned
In linear probing, the cost of an unsuccessful search can be used to compute the average cost of a successful search.
True
False
Which of the following algorithms solves the all-pair shortest path problem?
a. Floyd's algorithm
b. Prim's algorithm
c. Dijkstra's algorithm
d. Warshall's algorithm
The minimum number of colors needed to color a graph having n (>3) vertices and 2 edges is
1
2
3
4
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any distinct. Consider the following statements:
I. Minimum Spanning Tree of G is always unique.
II. Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
a.I only
b.II only
c.both I and II
d.neither I and II
The maximum degree of any vertex in a simple graph with n vertices is
a.n–1
b.n+1
c.2n–1
d.n
In binary tree nodes with 2 children are called ……..
A. Interior node
B. Domestic node
C. Internal node
D. Inner node
A vertex of Out-degree zero in a directed graph is called a/an
(A) Root vertex
(B) Isolated vertex
(C) Sink
(D) Articulation point
