USN 1 S P 2 3 7.
The data structure required for Breadth First
Traversal on a graph is?
S.E.A COLLEGE OF ENGINEERING AND TECHNOLOGY
a) Array
DATA STRUCTURES AND APPLICATIONS
Time:30Mins. Second Assignment Semester: III b) Stack
Section:ISE/AIML/AI&DS Subject Code: BCS304 c) Tree
Max Marks: 25 d) Queue
Note:
i. Answer All Questions.
1. What is a data structure?
a) A programming language
b) A collection of algorithms
c) A way to store and organize data
d) A type of computer hardware
2. What are the disadvantages of arrays?
a) Index value of an array can be negative 8. Which of the following is not the type of
b) Elements are sequentially accessed queue?
c) Data structure like queue or stack cannot be a) Priority queue
implemented b) Circular queue
d) There are chances of wastage of memory c) Single ended queue
space if elements inserted in an array are lesser d) Ordinary queue
than the allocated size 9. What will be the output of the following
program?
3. Which data structure is used for main()
implementing recursion?
{
a) Stack
charstr[]="san foundry";
b) Queue
c) List intlen=strlen(str);
d) Array inti;
4. The data structure required to check
for(i=0;i<len;i++)
whether an expression contains a balanced
push(str[i]);// pushes an
parenthesis is?
a) Queue element into stack
b) Stack
c) Tree for(i=0;i<len;i++)
d) Array
pop();//pops an element from the stack
5. Which data structure is needed to convert }
infix notation to postfix notation? a) yrdnuofnas
a) Tree b) foundry nas
b) Branch c) sanfoundry
c) Stack d) san foundry
d) Queue
10. What is the advantage of a hash table as a data
6. What is the value of the postfix expression 6 structure?
3 2 4 + – *? a) easy to implement
a) 74 b) faster access of data
b) -18 c) exhibit good locality of reference
c) 22 d) very efficient for less number of entries
d) 40
11.What is a dequeue? 18.In general, the node content in a threaded binary
a) A queue implemented with both singly and doubly tree is ________
linked lists a) leftchild_pointer, left_tag, data, right_tag,
b) A queue with insert/delete defined for front side of the rightchild_pointer
queue b) leftchild_pointer, left_tag
c) A queue with insert/delete defined for both front and c) leftchild_pointer, left_tag, right_tag, rightchild_pointer
rear ends of the queue d) leftchild_pointer, left_tag, data
d) A queue implemented with a doubly linked list
19. Which of the following is false about a binary
search tree?
a) The left child is always lesser than its parent
b) The right child is always greater than its parent
c) The left and right sub-trees should also be binary
12.Which matrix has most of the elements (not all) as
search trees
Zero?
d) In order sequence gives decreasing order of elements
a) Identity Matrix
b) Unit Matrix 20. If several elements are competing for the same
c) Sparse Matrix bucket in the hash table, what is it called?
d) Zero Matrix a) Diffusion
b) Replication
13. How many children does a binary tree have?
c) Collision
a) 2
d) Duplication
b) any number of children
c) 0 or 1 or 2 21. What is the hash function used in the division
d) 0 or 1 method?
a) h(k) = k/m
14. What must be the ideal size of array if the height
b) h(k) = k mod m
of tree is ‘l’?
c) h(k) = m/k
a) 2l-1
d) h(k) = m mod k
b) l-1
c) l 22. Using division method, in a given hash table of size
d) 2l 157, the key of value 172 be placed at position ____
a) 19
15. The number of edges from the root to the node is
b) 72
called __________ of the tree.
c) 15
a) Height
d) 17
b) Depth
c) Length 23.A graph having an edge from each vertex to every
d) Width other vertex is called a ___________
a) Tightly Connected
16. What is a full binary tree?
b) Strongly Connected
a) Each node has exactly zero or two children
c) Weakly Connected
b) Each node has exactly two children
d) Loosely Connected
c) All the leaves are at the same level
d) Each node has exactly one or two children 24. What would be the DFS traversal of the given
Graph?
17. Which of the following is not an advantage of
trees?
a) Hierarchical structure
b) Faster search
c) Router algorithms
d) Undo/Redo operations in a notepad
a) ABCED
b) AEDCB
c) EDCBA
d) ADECB
25. What is the maximum number of edges present in
a simple directed graph with 7 vertices if there exists
no cycles in the graph?
a) 21
b) 7
c) 6
d) 49
