Computer Science – Data Structures

Consider the following tree
pic ?
If the post order traversal gives a b- c d * + then the label of the nodes 1, 2, 3, … will be

Consider the following tree.
pic ?
If this tree is used for sorting, then a new number 8 should be placed as the

The initial configuration of a queue is a, b, c, d, (‘a’ is in the front end). To get the configuration d, c, b, a, one needs a minimum of

The number of possible*ordered trees with 3 nodes A, B, C is

The number of swappings needed to sort the number 8, 22, 7, 9, 31, 19, 5, 13 in a ascending order, using bubble sort is

Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed is the worst case by the merge sort algorithm will be

If the sequence of operations – PUSH (1), PUSh (2), PoP , PUSH (1), PUSH (2), PoP, PoP, PoP, PUSH (2), PoP, are performed on a stack, the sequence of popped out values are

A hash table with 10 buckets with one slot per bucket is depicted in Fig 9.3
The symbols, S1, to S7 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

A binary tree in which every non-leaf node has non-empty left and right subtrees is called strictly binary tree. Such a tree with 10 leaves

The depth of a complete binary tree with ‘n’ nodes is (log is to the base two)

Preorder is same as

Which of the following traversal techniques lists the nodes of a binary search tree in ascending order?

The average successful search time taken time taken by binary search on a sorted array of 10 items is

A hash function f defined as f (key) = key mod 7, with linear probing, is used to insert be the location of key 11?

The average successful search time for sequential search on ‘n’ items is

The running time of an algorithm T(n), Where ‘n’ is the input size is givn by
T(n) = 8T(n/2) + qn, if n > 1
p, if n = 1
Where p, q are constants. The order of this algorithm is

Let m, n be positive integers. Define Q (m,n) as
Q(m,n) = 0, if m < n Q(m-n,n) + p, if m ≥ n Then Q(m,3) is (a div b, gives the quotient when a is divided by b)

Six files F1, F2, F3, F4, F5 and F6 have 100, 200, 50, 80, 120, 150 number of records respectively. In what order should they be stored so as to optimize access time? Assume each file is accessed with the same frequency

In Qn. 18, the average access time will be

An algorithm is made up of 2 modules M1 and M2, If order of M1 is f (n) and M2 is g (n) then the order of the algorithm is

The concept of order (Big O) is important because

The running time T(n) where ‘n’ is the input size of a recursive algorithm is given as follows
T(n) = c + T(n – 1), if n > 1
d, if n ≤ 1
The order of this algorithm is

There are 4 different algorithms A1, A2, A3, A4, to solve a given problem with the order log (n) , log (log (n) ), nlog (n), n/log(n) respectively. Which of the best algorithm

The number of possible binary trees with 3 nodes is

The number of possible binary trees with 4 nodes is

The time complexity of an algorithm T(n), where n is the input size is given by
T(n) = T(n – 1) + 1/n, if n > 1
1, otherwise
The order of this algorithm is

Sorting is useful for

Choose the correct statements.

A sorting technique that guarantees, that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be

A text is made up of the characters a, b, c, d, e each occurring with the probability 12, 4,15, .08 and .25 respectively. The optimal coding technique will have the average length of

In the previous question, which of the following characters will have codes of length 3?

The running time of an algorithm is given by
T(n) = T(n – 1)+ T(n -2) – T(n – 3), if n > 3
n, otherwise.
The order of this algorithm is

What should be the relation between T(1) T(2) and T(3) so that Qn, 32, gives an algorithm whose order is constant?

The Ackermann’s function

The order of an algorithm that finds whether a given Boolean function of ‘n’ variables, produces a 1 is

In evaluating the arithmetic expression 2*3 – (4 + 5), using stacks to evaluate its equivalent post-fix form. Which of the following stack configuration is not possible?
[ ] [ ] [ ] [ ]
(a) [ ] (b) [5] (c) [ ] (d) [9]
[4] [4] [9] [3]
[6] [6] [6] [2]

The way a card game player arranges his cards as he picks them up one by one, is an example of

You want to check whether a given set of items is sorted. Which of the following sorting methods will be the most efficient if it is already in sorted order?

The average number of comparisons performed by the marge sort algorithm, in merging two sorted lists of length 2 is

Which of the following sorting methods will be the best if number of swappings done, is the only measure of efficiency?

You are asked to sort 15 randomly generated numbers. You should prefer

As part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be

The maximum number of comparisons needed to sort 7 items using radix sort is (assume each item is a 4 digit decimal number)

Which of the following algorithms exhibits the unnatural behavior that, minimum number of comparisons are needed if the list to be sorted is in the reverse order and maximum number of comparisons are needed if they are already in sorted order?

Which of the following sorting algorithm has the worst time complexity of nlog(n)?

Which of the following sorting methods sorts a given set of items that is already in sorted order or in reverse sorted order with equal speed?

Which of the following algorithms solves the all-pair shortest path problem?

Consider the graph in fig 9.4
pic ?
The third row in the transitive closure of the above graph is

The eccentricity of node labeled 5 in the graph in fig 9.5 is
pic ?

The center of the graph in Qn. 49 is the node labeled
pic ?

Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of stack B can only be printed. In this arrangement, Which of the following of a, b, c is not possible?

In the previous proble. if the stack A has 4 entries, then the number of possible permutation will be

The information about an array that is used in a program will be stored in

Which of the following expressions accesses the (ij)th entry of a (m x n) matrix stored column major form?

Sparse matrices have

In which of the following cases, linked list implementation of sparse matrices consumes the same memory space as the conventional way of storing the entire array?
(Assume all data-types need the same amount of storage.)

The linked list implementation of sparse matrices is superior to the generalized dope vector method because it is

If the dope vector stores the position of the first and last non-zero entries in each row, then (i, j)^th entry in the array can be calculated as (L(x) and F(x) represent the last and first non-zero entries in row x)

The postfix equivalent of the prefix * + a b – c d is

The order of the binary search algorithm is

The average search time of hashing, with linear probing will be less if the load factor

A hash table can store a maximum of 10 records. Currently there are records in location 1, 3, 4, 7, 8, 9, 10. The probability of a new record going into location 2, with a hash function resolving collisions by linear probing is

Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8. Which of the following locations will never be probed if a collision occurs at position 4?

A hash table has space for 100 records, What is the probability of collision before the table is 10% full?

Which of the following remarks about Trie Indexing are true?

Which of the following remarks about Trie Indexing are true?

Pick the correct statements.

Stack cannot be used to

Let M be a 3 x 3. adjacency matrix corresponding to a given graph of three nodes labeled 1, 2, 3. If entry (1, 3) in M³ is 2, then the graph could be

Consider the graph in Fig. 9.6
What should be the labels of nodes marked 1 and 2 if the breadth first traversal yields the list a b c d e?

If the depth first search of the graph given in Qn. 70 yields the list A B C D E, then the labels of the nodes marked 1 and 2 will be

Which of the following abstract data types can be used to represent a many to many relation?

Consider the graph in Fig. 9.7
Which of the following is a valid topological sorting?

Consider the graph in Fig 9.8
Which of the following is a valid strong component?

Consider the undirected weighted graph in Fig 9.9
The minimum cost spanning tree for this graph has the cost

Merge sort uses

The principle of locality justifies the use of

For merging two sorted lists of sizes m and n into a sorted list of size m+n we require comparisons of

A binary tree has n leaf nodes. The number of nodes of degree 2 in this stree is

The minimum number of edges in a connected cyclic graph on n vertices is

The postfix expression for the infix expression
A + B* ( C + D) / F + D*E is:

Which of the following statements is true?
I) As the number of entries in the hash table increases, the number of collisions increases.
II) Recursive programs are efficient.
III) The worst time complexity of quick sort is O(n² ).
IV) Binary search implemented using a linked list is efficient.

The number of binary trees with 3 nodes which when traversed in post-order gives the sequence A, B, C is

The minimum number of colors needed to color a graph having n (>3) vertices and 2 edges is

Which of the following file organizations is preferred for secondary key processing?

Mr. Fool designed a crazy language called STUPID that included the following features.
+ has precedence over /
/ has precedence over – (binary)
– (binary) has precedence over *
* and ^ (exponentiation) have the same precedence.
+ and * associate from right to left.
The rest of mentioned operators associate from left to right. Choose the correct stack priorities Mr. Fool should assign to +, *, ^, / respectively, for correctly converting an arithmetic expression in infix form to the equivalent postfix form.

The infix priorities of +, *, ^, / could be

Mr. Fool’s STUPID language will evaluate the expression 2 * 2 ^ 3 * 4 to

The expression 1 * 2 ^ 3 * 4 ^ 5 * 6 will be evaluated to

In a circularly linked list organization, insertion of a record involves the modification of

Stack is useful for implementing

To store details of an employee, a storage space of 100 characters is needed. A magnetic tape with a density of 1000 characters per inch and an inter-record gap of 1 inch is used to store information about all employees in the company. What should be the blocking factor so that the wastage does not exceed one-third of the tape?

A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately

A machine took 200 sec to sort 200 names, using bubble sort. In 800 sec, it can approximately sort

The correct order of arrangement of the name Bradman, Lamb, May Boon, Border, Underwood and Boycott, so that the quick sort algorithm makes the least number of comparisons is

Which of the following is useful is traversing a given graph by breadth first search?

Which of the following is useful in implementing quick sort?

Queue can be used to implement

The expression tree given in Fig 9.10 evaluates to 1, if

A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the m^th record is the first record to result in collision is

The process of accessing data stored in a tape is similar to manipulating data on a

If the hashing function is the remainder on devision. then clustering is more likely to occur if the storage space is divided into 40 sectors rather than 41. This conclusion is

Unrestricted use of goto is harmful, because it

The maximum degree of any vertex in a simple graph with n vertices is

The recurrence relation that arises in relation with the complexity of binary search is

An item that is read as input can be either pushed to a stack and later popped and printed, or printed directly. Which of the following will be output if the input is the sequence of items- 1, 2, 3, 4, 5?

Which of the following algorithm design technique is used in the quick sort algorithm?

Linked lists are not suitable for implementing

Which one of the following statements is false?

The number of edges in a regular graph of degree d and n vertices is

Consider the following two function

f (n) = n³, if 0 ≤ n < 10.000

n² , otherwise

g (n) = n, if 0 ≤ n < 100

n² + 5n, otherwise

Which of the following is/are true?

A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will be

The concatenation of two lists is to be performed in O(1) time. Which of the following implementation of a list could be used?

The correct matching for the following pairs is
A) All pairs shortest path                                (1)  Greedy
B) Quick sort                                                     (2) Depth first search
C) Minimum weight spanning space           (3)   Dynamic programming
D) Connected Components                           (4)  Divide and conquer

Which of the following is essential for converting an infix expression to the postfix form efficiently?

A binary search tree contains the values – 1, 2, 3, 4, 5, 6, 7, and 8, The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output ?

Let T(n) be the function defined by
T(1) = 1, if n=1
= 2T([n/2]) + √n, for n ≥ 2
Which of the following statements is true?

Which of the following need not be a binary tree?

Assume 5 buffer pages are available to sort a file of 105 pages. The cost of sorting using m-way merge sort is