Section A : Basic Concepts (30 Marks)
1.Consider that a heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value?
(a) data[0] (b) data[n-1] (c) data[n] (d) data[2*n + 1] (e) data[2*n + 2].
2.Which of the following are used to represent the sparse matrices?
(a)Singly Linked List where each node contains non- zero elements of the matrix
(b)Circular Linked List for each row, column with each node corresponding to non-zero element
(c)Doubly Linked List
(d)Can’t be represented using Linked List, but with arrays only
(e)Can be represented only by queues.
3.Which of the following has a desired key is searched, starting itself from hash address, sequentially in a table?
(a)Quadratic probing (b)Random probing (c)Reverse probing (d)Chaining
(e)Linear probing.
4.Consider A is an array of order m*n stored in a Row Major order. If the address of the first element in the array is K which is there at A[0, 0], then What is the address of A[i, j]?
(a) K + (i-1) * m + j – 1 (b) K + (i-1) * n + j – 1 (c) K + i * m + j (d) K + (j-1) * m + j – 1
(e) K + j * n + i.
5.Which of the following is used in conversion of an infix expression to a postfix expression?
(a) Circular lis (b) Array (c) Stack (d) Queue (e) Dequeue.
6.What is the output of the following function when it is called?
void disp( node *first )
if( first->next )
{
{
printf("%4d", first->data);
disp( first->next );
}
}
(a) Display the data of next node always in the list
(b) Display the data of all nodes of the list
(c) Does not execute
(d) Display the data of the first node only
(e) Display the data of the last node only.
7.With the “wrap around” implementation of a queue, which of the following code should be used to work out the next location of deletion?
(a) front++ (b) front-- (c) front = (front % max_queue_size) + 1 (d) front = (front ++) % max_queue_size (e) front = 0.
8.Consider the order of a tree is represented by M. Then, which of the following is true?
(a) Every non-leaf node must have M subtrees
(b) Every non-leaf node must have M keys
(c) Every non-leaf node can have atmost M subtrees
(d) Every non-leaf node can have atmost M keys
(e) The Height of the tree is M.
9.What are the time complexities of binary search for an array of size N in best and worst cases respectively?
(a) N, N2 (b) 1, Log N (c) Log N, N2 (d) 1, N Log N (e) N, N.
10.What is the algorithm, which scans the list by swapping the entries whenever pair of adjacent keys is out of desired order?
(a)Insertion sort (b) Quick sort (c) Shell sort (d) Bubble sort (e) Radix sort. 11.The in-order traversal of some binary tree produced the sequence HFIEJGZ, and the post-order traversal of the same tree produced the sequence HIFJZGE. What will be the total number of nodes in the left sub tree of the given tree?
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5
12.Which of the following shows the difference between a queue and a stack?
(a) Queues require linked lists, but stacks do not
(b) Stacks require linked lists, but queues do not
(c) Queue is used for complex programs and stack for simple programs
(d) Stacks use two ends of the structure, queues use only one
(e) Queues use two ends of the structure; stacks use only one.
13.Which of the following is generated by Folding method?
(a) A hash function (b) Index function for a triangular matrix
(c) Linking the tail node to the head node in linked list
(d) Linear probing
(e) Chaining.
14.From the following choose the one which belongs to the algorithm paradigm other than to which others from the following belongs to.
(a) Minimum & Maximum problem
(b) Knapsack problem
(c) Selection problem
(d) Merge sort
(e) Quick sort.
15.Which of the following data structures is used by breadth first search as an auxiliary structure to hold nodes for future processing?
(a) Queue (b) Linked list (c) Graph (d) B-Tree (e) Stack.
16.Pick the correct statement(s) from the following set of statements.
I. In the Kruskal’s algorithm, for the construction of minimal spanning tree for a graph, the selected edges always form a forest.
II. In Prim’s algorithm, for the construction of minimal spanning tree for a graph, the selected edges always form an orchard.
III. DFS, BFS algorithms always make use of a queue, and stack respectively.
(a)Only (I) above (b)Only (II) above (c)Only (III) above (d)Both (I) and (III) above
(e)Both (II) and (III) above.
17.Which of the following methods of collision processing has some of their addresses may remain unchecked?
(a) Linked collision processing
(b) Quadratic collision processing
(c) Linear collision processing
(d) Random collision processing
(e) Clustering collision processing.
18.Consider a tree ‘t’ has two subtrees t1 and t2. Identify the tree where the subtree t1 has minimum height and the subtree t2 has maximum height.
(a) Fibonacci (b) B+ (c) Sparse (d) Complete binary (e) B.
19.Which of the following is used to select the first entry which has the free block equal to or more than required one in memory allocation?
(a)Best fit method (b) Average fit method (c) Worst fit method (d) Big fit method
(e) First fit method.
20.What is the total number of nodes at every level (L) of a complete binary tree?
(a) 2L (b) 2L– 1 (c) 2 L-1 (d) 2L–1 (e) 2L.
21.Which of the following statements is true related to a B-tree?
(a) All entries of a node are greater than or equal to the entries in the node's children
(b) All leaves are at the different depths
(c) All the leaf nodes appear at same level
(d) All non-leaf nodes have the exact same number of children
(e) All nodes contain the exact same number of entries.
22.A simple graph has no loops. Which of the following forms another property of a simple graph?
(a) Contain un-weighted edges
(b) Undirected
(c) Have at least one vertex
(d) Have no multiple edges
(e) Must be directed.
23.Which of the following information is not saved in the activation record, when ever a function call is executed?
(a) Static and dynamic address links
(b) Current depth of recursion
(c) Formal parameters
(d) Location where the function should return when done
(e) Local variables.
24.Use the following code and the linked list pictured below to answer the questions 24 - 26.
First Then, First ànextànextàdata is
(a) Null (b) Syntax Error (c) 30 (d) 20 (e) 45.
25.Pick the right option from the following:
I. Firstànext == Temp1.
II. Temp1ànextàdata == 60.
III. Temp2ànext ànext == NULL.
(a) Only (I) is TRUE
(b) Only (II) is TRUE
(c) Both (I) and (II) are TRUE
(d) Both (I) and (III) are TRUE
(e) Both (II) and (III) are TRUE. 26.Decide whether the syntax of each of the following statements is valid or invalid.
I. Firstànext = Temp1ànext;
II. First ànext = *( Temp2ànext);
III. * First = Temp2;
(a) Only (I) is valid
(b) Only (II) is valid
(c) Only (III) is valid
(d) Both (I) and (III) are valid
(e) Both (II) and (III) are valid.
27.Which of the following is not possible as a balance factor of any node of an AVL tree?
I. -2.
II. ±1.
III. 0.
IV. 2.
(a) Only (I) above
(b) Only (II) above
(c) Only (III) above
(d) Both (I) and (IV) above
(e) Both (III) and (IV) above.
28.Which of the following statement(s) is/are TRUE in view of a multi-way search tree? If a node has
I. 4 sub trees it contains 3 keys.
II. 5 keys, it has 7 sub trees.
III. 6 sub trees, it contains 6 keys.
IV. 10 keys if it contains 11 children.
(a) Only (I) above
(b) Only (II) above
(c) Only (III) above
(d) Both (I) and (IV) above
(e) Both (II) and (III) above.
29.Identify the name of the sorting in which time is not proportional to n2.
(a) Selection sort (b) Bubble sort (c) Qucik sort (d) Merge sort (e) Insertion sort.
30.How many fields are required by a node to represent the polynomials in computer memory using linked list?
(a) Two fields (b) Four fields (c) More than three fields (d) One is enough (e) Three fields.
Section B : Problems (50 Marks)
1.
a. What is a Circular queue? Mention the advantages of it.
b. Write a ‘C’ program to implement a Circular Queue. (5 + 5 = 10 marks) 2.What is meant by HAMILTONIAN GRAPH? Give the algorithm to find the Hamiltonian cycles of a graph. (10 marks)
3. Write a ‘C’ program to traverse the graph in DFS manner. (10 marks) 4. Write a program to sort the elements following Divide & conquer merge sort technique. (10 marks)
5.
a. Explain briefly about P-Class and NP-Class problems.
b. Write a ‘C’ FUNCTION to find the height of the tree. (5 + 5 = 10 marks)
Section C : Applied Theory (20 Marks)
6.
a. Explain the algorithm/function to copy a tree into another tree.
b. Write an algorithm to find the solution for TREE VERTEX SPLITTING PROBLEM.
(5 + 5 = 10 marks)
7. Write short notes on any two of the following:
i. Complexity Theory.
ii. AVL trees.
iii. Hashing.
iv. Greedy algorithms. (10 marks)
Suggested 1.
Answer : (a)
Reason: if a heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), then the entry with the greatest value is data[0] .
2.
Answer : (a)
Reason: To represent the sparse matrices, we have Singly Linked List where each node contains non- zero elements of the matrix
3.
Answer : (e)
Reason: Linear Probing has a desired key is searched, starting itself from hash address, sequentially in a table.
4.
Answer : (b)
Reason: If A is an array of order m*n stored in a Row Major order. If the address of the first element in the array is K which is there at A[0, 0], then the address of A[i, j] is K + (i-1) * n + j –1
5.
Answer : (c)
Reason: Stack is used in conversion of an infix expression to a postfix expression.
6.
Answer : (b)
Reason: if the following function is called.
void disp( node *first )
if( first->next )
{
{
printf("%4d", first->data);
disp( first->next );
}
} then it Display the data of all nodes of the list.
7.
Answer : (d)
Reason: With the ``wrap around'' implementation of a queue, front = (front ++) % max_queue_size should be used to work out the next location of deletion.
8.
Answer : (c)
Reason: if the order of a tree is represented by M. Then , Every non-leaf node can have at most M subtrees is true.
9.
Answer : (b)
Reason: 1, Log N are the time complexities of binary search for an array of size N in best and worst cases respectively
10.
Answer : (d)
Reason: Bubble sort is the algorithm, which scans the list by swapping the entries whenever pair of adjacent keys is out of desired order.
11.
Answer : (c)
Reason: The in-order traversal of some binary tree produced the sequence HFIEJGZ, and the post-order traversal of the same tree produced the sequence HIFJZGE. Then the total number of nodes in the left sub tree of the given tree is 3.
12.
Answer : (e)
Reason: Queues use two ends of the structure; stacks use only one show the difference between them.
13.
Answer : (a)
Reason: a hashing function is generated by Folding method.
14.
Answer : (b)
Reason: Knapsack problem is the one which belongs to the algorithm paradigm other than to which others from the following belongs to
15.
Answer : (a)
Reason: Queue is the data structure used by breadth first search as an auxiliary structure to hold nodes for future processing.
16.
Answer : (a)
Reason: In the Kruskal’s algorithm, for the construction of minimal spanning tree for a graph, the selected edges always form a forest.
17.
Answer : (b)
Reason: Quadratic collision processing has some of their addresses may remain unchecked.
18.
Answer : (a)
Reason: Consider a tree‘t’ has two sub trees t1 and t2. Fibonacci is the tree where the sub tree t1 has minimum height and the sub tree t2 has maximum height.
19.
Answer : (e)
Reason: First fit method is used to select the first entry which has the free block equal to or more than required one in memory allocation.
20.
Answer : (e)
Reason: The total number of nodes at every level ( L ) of a complete binary tree is 2L.
21.
Answer : (c)
Reason: All the leaf nodes appear at same level is true related to a B-tree.
22.
Answer : (d)
Reason: A simple graph has no loops. Other property is to have no multiple edges.
23.
Answer : (b)
Reason: Current depth of recursion is not saved in the activation record, when ever a function call is executed.
24.
Answer : (e)
Reason: the following code and the linked list pictured
Then, First ànextànextàdata = 45
25.
Answer : (b)
Reason: Firstànext == Temp1 and Temp2ànext ànext == NULL are true.
26.
Answer : (a)
Reason: The syntax of Firstànext = Temp1ànext is valid.
27.
Answer : (e)
Reason: -2 and 2 is not possible as a balance factor of any node of an AVL tree.
28.
Answer : (e)
Reason: If a node has 4 sub trees it contains 3 keys and 10 keys if it contains 11 children. is TRUE in view of a multi-way search tree.
29.
Answer : (d)
Reason: Merge Sort is a sort in which time is not proportional to n2.
30.
Answer : (e)
Reason: Three fields are required by a not to represent the polynomials in computer memory using linked list.
No comments:
Post a Comment