NIELIT A Level July, 2012
A6-R4: DATA STRUCTURES THROUGH C++
PART ONE
(Answer all the questions)
1. Each question below gives a multiple choice of answers. Choose the most appropriate one and enter in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1x10)
A) Sorting
B) Searching
C) Critical Path
D) Minimum Spanning Tree
1.2 Which of the method belong to external sorting?
A) Bucket Sort
B) Multi way Merge
C) Selection Sort
D) Insertion Sort
1.3 The following sequence of operations is performed on stack:
Push (10), Push (20), POP, Push(10), Push (20), POP, POP, POP, PUSH(20), POP
The sequence of values popped out from the stack is
A) 20,10, 20,10, 20
B) 20,20, 10,10,10,20
C) 10,20, 20,10, 20
D) 20,20, 10, 20,10
1.4 The number of distinct simple graphs with up to three nodes is
A) 15
B) 10
C) 7
D) 9
1.5 f(n) is asymptotically bounded by g(n), which means
A) f(n) = O(g(n))
B) f(n) = (g(n))
C) f(n) = q (g(n))
D) None of the above
1.6 Merge Sort uses
A) Backtracking approach
B) Divide and Conquer strategy
C) Greedy Approach
D) Heuristic approach
1.7 A binary tree has n leaf nodes. The number of nodes of degree 2 in T is
A) log (n)
B) n-1
C) n
D) 2^n
1.8 In a connected planar graph G with v vertices and e edges, then the number of regions in a
planar representation is ________
A) e- v+ 1
B) e – v + 2
C) e*e
D) v*v
1.9 What is the maximum number of edges when a graph with 5 vertices is undirected with no
self loops?
A) 10
B) 20
C) 4
D) 16
1.10 The number of comparisons in selection sort of a list of n
A) O(n2)
B) O(n)
C)
2
n−1
D)
2
n
2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “tear-off” sheet attached to the question paper, following instructions therein. (1x10)
2.2 Queue is a suitable data structure for recursion implementation.
2.3 The largest sum of possible sum of weights in a connected graph is minimum spanning tree.
2.4 In a k-ray tree of height h, there are at most kh leaves.
2.5 A data structure is an implementation of an ADT.
2.6 In breadth first traversal, all the predecessors of a visited node will be visited before visiting
their successors.
2.7 The number of minimum spanning trees for a graph with V vertices is V^V.
2.8 Stack is suitable data structure to simulate recursion.
2.9 The number of edges in an n-vertex complete graph is n(n-1)/2.
2.10 The worst case and average number of comparisons required in merge-sort is less than or
equal to n log n.
3. Match words and phrases in column X with the closest related meaning/word(s)/phrase(s) in column Y. Enter your selection in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1x10)
X Y
3.1 Time and space A. O(n*n)
3.2 Deleting elements from front and inserting at rear B. O(n)
3.3 Linear data structure C. Graph
3.4 Hierarchical relationship D. Gray code
3.5 Inorder traversal of tree E. List
3.6 Linear search F. Binary search tree
3.7 Bubble sort G. Trees
3.8 Non-linear data structure H. Hamming code
3.9 Adjacent arcs labeled with bit strings that differ in I. Queues
exactly one bit
3.10 Isomorphic simple graphs J. Equivalence relation
K. Efficiency of algorithm
L. Abelian Group
M. Deque
4. Each statement below has a blank space to fit one of the word(s) or phrase(s) in the list below. Enter your choice in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1x10)
A. Omega(log N) B. 168 C. maxheap
D. Vv-2 E. AVL F. N log N - 2ˆlog N + 1
G. DAG H. Topological sorting I. Omega(N Log N)
J. abc*+de*f+g*+ K. Eight L. abcdefg*+*+*+
M. N Log N
4.1 The cost of splitting a list of six into two lists of three to find the minimum and maximum
element requires ________ comparisons.
4.2 The number of minimum spanning trees in a graph with V vertices is ________.
4.3 The postfix expression for (a+b *c) + ((d *e + f) * g) is ________.
4.4 A complete binary tree with the property that the value at each node is at least as large as
the values at its children, if exist, is termed as ________.
4.5 Given an array X[6][6] whose base address is 100. If each element occupies 4 bytes and
array is stored row wise, then location X[2][5] is ________.
4.6 Sorting algorithm which uses only comparisons between elements requires ________
comparisons.
4.7 A binary tree with K leaves must have depth at least ________.
4.8 In the analysis of merge sort if the constants are disregarded, then the number of
comparisons used in the worst case by merge sort method is ________.
4.9 A balanced binary tree in which height of two subtrees of every node is never more than
one, ________ tree.
4.10 Ordering of vertices in a directed acyclic graph based on path information is called
________.
PART TWO
(Answer any FOUR questions)
5.a) Write a function to merge two linked lists. The input lists have their elements in sorted order,
from lowest to highest. The output list should also be sorted from lowest to highest. Your
algorithm should run in linear time on the length of the output list.
b) Propose a polynomial time algorithm to decide if two trees T1 and T2 are isomorphic.
c) Write a recursive algorithm to compute the value of the recurrence relation
T(1) = 1:
n
n
T
n
T( n ) T +
+
=
2 2
(6+6+3)
6.
a) Write a program in C++ for sorting n elements using quick sort method and analyze the
complexity of your program.
b) What are the minimum and maximum numbers of elements in a heap of height h?
c) A deque (pronounced “deck”) is like a queue, except that items may be added and removed
from both the front and the rear. Write either an array-based or linked implementation for the
deque.
(8+2+5)
7.
a) A palindrome is a string that reads the same forwards as backwards. Write an algorithm to
determine if a string is a palindrome. Assume that the string is read from standard input one
character at a time. The algorithm should output true or false as appropriate.
b) Show how heap sort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242,
811 and 102.
(5+10)
8.
a) Write a procedure to traverse a Binary Search Tree to prevent the contents of nodes in
descending order.
b) Write a non recursive function to reverse a single linked list in O(N) time.
(8+7)
9.
a) Write an algorithm to determine whether a directed graph of |V| vertices contains a cycle.
b) Write an algorithm to detect the element in position i of a max heap.
c) Consider the collection of edges selected by Dijkstra’s algorithm as the shortest paths to the
graph’s vertices from the start vertex. Do these edges form a spanning tree (not necessarily
of minimum cost)? Explain why or why not.
(6+6+3)
No comments:
Post a Comment