Data Structures Previous Year Questions

Explanation

Kₘ,ₙ is Hamilton circuit if and only if m = n ≥ 2, (Circuit is a path similar to a cycle that starts and ends at the same vertex) and Kₘ,ₙ is a Hamilton circuit if m = n ≥ 2, so the correct answer is (c).

Explanation

After the two recursive calls in Mergesort complete, but before the merge step, elements in each half of the array are sorted amongst themselves because, Mergesort is possible when two arrays are sorted. If two unsorted arrays are submitted to Mergesort algorithm. It will sort each of them first before merging them, because Mergesort is a divide and conquer algorithm, Hence the answer is option (b).

Explanation

Base address of an array is the starting address of an array. One can easily access to all the cells of an array if information about this can be achieved.

Explanation

Removing left recursion and left factoring the grammar do not suffice to convert an arbitrary CFG to an LL(1) grammar. LL(1) parsing is top-down; for it the grammar must also be unambiguous and deterministic (e.g. an ambiguous grammar stays non-LL(1)), besides being free from left recursion.

Explanation

It is a search algorithm that seeks to decrease the number nodes that are evaluated by the Min-max algorithm in its search tree. It is an adversial search algorithm used commonly for machine playing of two-player games.

Explanation

In Quicksort, the depth of a leaf depends on how the input size reduces at each level. If the split is always in the ratio (1 − α) to α, the minimum depth corresponds to the path where the recursion always follows the smaller partition, i.e. of size αn. At each level the size becomes n, αn, α²n, α³n, … We stop when the size becomes 1: αᵏn = 1 ⇒ k log α + log n = 0 ⇒ k = −lg n / lg α. Hence the answer is (c).

Explanation

The greedy algorithm work in a way that it has same estimate (called a heuristic) of how for from the goal any vertex is. Instead of selecting the vertex closet to the starting point, it selects the vertex closet to the goal, so the answer is (c).

Explanation

Fopen() : creates a file or opens an existing file and returns a file pointer, e.g. FILE ∗fp; fp = fopen("<file-name>", "<mode>"); fclose() : closes a file; returns 0 on success and EOF otherwise. ferror() : checks the error indicator for the given file stream, returning non-zero if set and 0 otherwise. feof() : checks the end-of-file indicator for the given file stream, returning non-zero if set and 0 otherwise.

Explanation

The postfix form of the expression is AB*CD*E/+. Counting a PUSH for each of the 5 operands and a POP for each of the 4 operators (ignoring the pushes of intermediate results), the evaluation needs 5 PUSH and 4 POP instructions.

Explanation

Each cell needs 4 words. In row-major order, rows 0 to 10 contain 11 × 10 = 110 elements, and A[11][0] to A[11][4] add 5 more, so 115 elements precede A[11][5]. Address = 100 + 4 × 115 = 560.

Explanation

A full binary tree with n leaves contains n – 1 internal nodes, so total nodes = internal nodes + leaves = (n – 1) + n = 2n – 1.

Explanation

The program text is shared, so it is not multiplied by 5. As given in the book, total memory = 200 + 15 + 50 + 70 = 335 K.

Explanation

Cyclomatic complexity measures the logical complexity of a program (the number of independent paths). It can be computed as: (1) the number of regions of the flow graph; (2) V(G) = E – N + 2, where E is the number of edges and N the number of nodes; (3) V(G) = P + 1, where P is the number of predicate nodes in the flow graph G.

Explanation

For any comparison-based sort the decision tree has at least n! leaves, so its height is at least lg(n!) = Ω(n lg n).

Explanation

Take the first node in preorder traversal a will be the root. Now we construct the binary tree Therefore, postorder is - debfgca

Explanation

Level order traversal is similar to breadth first search, whereas preorder traversal is similar to depth first search. So the answer is (a).

Explanation

Linear search runs in at worst linear time and make at most n comparisons, where n is the length of the list. If each element is equally likely to be searched then the linear search has an average case of (n/2) comparisons, but the average case can be affected if the search probability for each element vary.

Explanation

Using Kruskal's algorithm: take 10 (1–6), 12 (3–4), 14 (2–7), 16 (2–3); skip 18 (4–7, cycle); take 22 (4–5); skip 24 (5–7, cycle); take 25 (5–6). Total = 10 + 12 + 14 + 16 + 22 + 25 = 99, which is option (b).

Explanation

The Floyd–Warshall algorithm uses dynamic programming and compares all possible paths through the graph between each pair of vertices. It does this with Θ(|V|³) comparisons.

Explanation

XML data is described using a DTD (or schema) and description nodes; XSL is used to transform/present XML, not to describe it. The correct statements are (1) and (3). Hence the answer is option (d).

Explanation

A clique is a maximal complete subgraph (every vertex connected to all other vertices in the subgraph). Such subgraphs are: (i) {b, c, e, f} (ii) {a, d, g} (iii) {a, b, g} (iv) {b, e, g} (v) {d, e, g}. There are 5 cliques.

Explanation

Since the given stack size is 5 and at most two elements are on the stack at any time, and no Pop is done on an empty stack, there is no overflow or underflow. The stack operations are performed smoothly.

Explanation

In a full binary tree (each node has 0 or 2 children) with n nodes, the number of internal nodes is I = (n – 1)/2. When the tree is skewed (each internal node has one leaf child), every internal node adds one level, so the maximum height is also (n – 1)/2.

Explanation

If we delete the root node of a binary search tree, it can be replaced by its inorder successor or inorder predecessor. The inorder predecessor of 24 (largest node in the left subtree) is 16 and the inorder successor is 26. So, from the left subtree, 16 will be the new root.

Explanation

The number of spanning trees in a complete graph with n vertices = nⁿ⁻² = 4⁴⁻² = 16. A complete bipartite graph Kₘ,ₙ has mⁿ⁻¹ × nᵐ⁻¹ spanning trees = 2¹ × 2¹ = 4.

Explanation

In 'C', int (*f( ))[ ]; declares f as a function returning a pointer to an array of integers.

Explanation

In sequence (c), after visiting 912 (912 > 364) the search moves to the left subtree of 912, so every later node must be less than 912. 913 cannot appear after 912. So, the answer is (c).

Explanation

B is a MIN node: min(3, 12, 8) = 3, so A (MAX) gets α = 3. At C, the first leaf G = 2 gives C a value ≤ 2, which is less than α = 3. Whatever H and I produce, C cannot be chosen by A, so H and I are pruned. Option (b) is correct.

Explanation

Properties of Max Heap: Must be complete binary tree. All levels are completely filled except possibly the last level. The last level is filled from Left to Right. Each parent node has a value greater than or equal to its children. Option (a) Not fulfill the property of Max Heap. Option (b) Not fulfill the property of Max Heap. Option (c) Fulfill the property of Max Heap. Option (d) Not fulfill the property of Max Heap. So, the correct option is (c). (xii) Divide and Conquer

Explanation

FORTRAN I, II & IV contain only static variables. All objects in Java are explicit heap dynamic variable & are destroyed by "Garbage Collector" Languages Such as APL, ALGOL 68, & LISP Use implicit heap dynamic variables. So, a-iii, b-i, c-iv, d-ii Hence, correct option is (c).

Explanation

A queue can be implemented using two stacks S1 and S2: enqueue pushes onto S1; for dequeue, if S2 is not empty pop from it, otherwise first pop all elements of S1 and push them into S2, then pop from S2. So S₁ is correct. Similarly, a stack can be implemented using two queues, so S₂ is also correct. Hence, the answer is option (c).

Explanation

Although we have a tail pointer, it is of no use for deletion because there is no previous pointer. To delete the last node we need a pointer to the second-last node so that it can become the new last node; finding it requires traversing the whole list, which takes O(n) time.

Explanation

The root is ↔, its left subtree is ~(p ∧ q) and its right subtree is (~p ∧ ~q). Prefix: ↔~∧pq∧~p~q Postfix: pq∧~p~q~∧↔ Option (b) is the answer.

Explanation

Printing the elements in order means printing them in sorted order; inorder traversal of a BST gives the sorted order and visits each node once, taking O(n) time. For a balanced BST T(n) = 2T(n/2) + c and for a skewed tree T(n) = T(n – 1) + c; both solve to O(n).

Explanation

To minimize average response time the jobs must run in shortest-job-first order: C(3), E(3 < x < 5), D(5), B(6), A(9).

Explanation

Each internal node of the derivation tree has exactly k children. The tree is shortest when it is complete, giving h ≥ logₖ |W|, and tallest when each level has only one internal node, giving h ≤ (|W| – 1)/(k – 1). So logₖ |W| ≤ h ≤ (|W| – 1)/(k – 1).

Explanation

By Dirac's theorem, deg(v) ≥ n/2 for every vertex; by Ore's theorem, deg(v) + deg(w) ≥ n for every pair of non-adjacent vertices v and w; and a graph with |E(G)| ≥ (1/2)(n – 1)(n – 2) + 2 edges is Hamiltonian. So all of the above.

Explanation

Statement B is false: breadth-first search can be used to find the connected components of a graph, just like depth-first search. Optimal binary search tree construction is a well-known dynamic programming application, and given only the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely.

Explanation

In a sorted array, insertion and deletion take O(n) in the worst case (elements must be shifted), while the minimum and maximum are always at the two ends, so finding them takes O(1).

Explanation

Data pointer = child pointer + search field value = 7 + 14 = 21 bytes. Maximum number of entries = 1 KB/21 bytes = 1024/21 ≈ 48.76. The book picks 16 since all other options are greater than 48.

Explanation

(A) fails the max-heap property (4 has child 8). (B) is a valid max heap because every parent ≥ its children. (C) fails (1 has child 7). (D) fails (3 has children 9 and 10; 4 has child 8; 1 has child 7).

Explanation

A header file cannot be passed to a function in C++, while a constant, a structure and an array can be passed to a function.

Explanation

A binary tree of height h has at most 2ʰ leaves. Sorting n elements requires at least n! leaves, so n! ≤ 2ʰ, giving h ≥ lg(n!) ≥ (n/2) lg(n/2) = Ω(n lg n).

Explanation

Red-black trees are one of many search tree schemes that are 'balanced' in order to guarantee that basic dynamic-set operations take O(lg n) time in the worst case.

Explanation

The loop copies all values of 'array' into p. After q = p, q refers to the same array object as p, so p[4] = 20 also makes q[4] = 20. 'array' itself is unchanged, so array[4] = 18. The output is 18 : 20.

Explanation

A planning graph consists of a sequence of levels that correspond to time steps in the plan; level 0 is the initial state. Each level contains a set of literals (all that could be true at that time step) and a set of actions (all whose preconditions could be satisfied at that step). It is used to obtain heuristic estimates, and a solution can be extracted using GRAPHPLAN.

Explanation

Deterministic and non-deterministic pushdown automata have different expressive power (NPDA accept all context-free languages, DPDA only deterministic CFLs). DFA and NFA are equivalent, and all the Turing machine variants are equivalent.

Explanation

An in-order traversal of a binary search tree always gives the keys in ascending order, so the in-order sequence is 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20.

Explanation

Inserting 10, 1, 3, 5, 15, 12, 16: 10 is the root; 1 is its left child, 3 is the right child of 1 and 5 is the right child of 3; 15 is the right child of 10 with children 12 and 16. The longest root-to-leaf path is 10-1-3-5 with 3 edges, so the height is 3.

Explanation

Kruskal's algorithm picks edges in increasing order of weight while avoiding cycles: GC = 2, AD = 2, GB = 3, GA = 3, then BF = 4 and AE = 4. So the order is GC, AD, GB, GA, BF, AE. Note: more than one order is possible since edge weights are repeated.