SYMCA (Part (Under Engg.) Examination, 2017
DATA STRUCTURE
Day and Date Thursday, 4-5-2017 Total Marks 100
Time 3.00 p.m. to 6.00 p.m.
1. Multiple Choice Questions. 20
If the sequence of operations pop, pop,
pop, pop, pop are performed on a stack, the sequence of popped out
values are
2 2
1 2
The postfix expression for ab cd is
ab cd ab cd
ab cd ab cd
Which of the following is/are the levels of implementation of data structure
Abstract level Application level
Implementation level All of the above
Stack is also called as
Last in first out First in last out
Last in last out First in first out
is very useful in situation when data have to stored and then
retrieved in reverse order.
Stack Queue List Link list
Which of the following data structure can't store the non-homogeneous data
elements
Arrays Records Pointers Stacks
Which of the following data structure is non linear type
Strings Lists
Stacks Graph
Seat
No.
SLR-L 11
What will be the value of top, if there is a size of stack STACK_SIZE is 5
5 6
4 None
In the traversal we process all of a vertex's descendants
before we move to an adjacent vertex.
Depth First Breadth First With First Depth Limited
10) A is a graph that has weights of costs associated with its
edges.
Network Weighted graph
Both a and b None a and b
11) A binary search tree whose left sub tree and right sub tree differ in height by
at most 1 unit is called
AVL tree Red-black tree
Lemma tree None of the above
12) Any node is the path from the root to the node is called
Successor node
Ancestor node
Internal node
None of the above
13) A slight modification of indexing in B tree is called
B-tree
B+tree
B+tree which allows redundant storage of key values
All above
14) The average search time of hashing with linear probing will be less if the load
factor
is far less than one equals one
is far greater than one None of above
15) In linked list, we traverse the list in
Only one direction Two direction
Sometimes a or b None of these
16) Dynamic structures are ones
Which expand or shrink as required during the program execution
Their associated memory location change
Both a and b
None of the above
17) The most recently arrived data object is the
First one to depart from a stack
Last one to depart from stack
Second one to depart from a stack
Second last to depart from a stack
18) Which is/are the application(s) of stack
Function calls
Large number arithmetic
Evaluation of arithmetic expressions
All of the above
19) A graph is a tree if it has properties
it is connected there are no cycles in the graph
a and b None of these
20) In adjacency list representation, we store graph as
Cross linked structure Linked structure
a and b None
SECTION I
2. Write short note on following (any 20
Time and space complexity.
Circular linked list.
Application of stack.
Dequeue.
Program for insertion sort.
3. What is single linked list and explain its operation in detail. 10
"Insertion sort is better than selection sort". Explain in detail. 10
OR
What is queue Explain its type. Write operations on queue in detail. 10
SECTION II
4. Write short note on following (any 20
Hashing functions.
Path length.
Heap sort
B-tree
Adjacency list.
5. What is graph Write algorithm of graph traversing method. 10
Write a program to search an element from binary tree. 10
OR
What is indexing Also explain B and indexing. 10