Data Structures Previous Year Questions

Explanation

Records are stored one after another, so the Nth record begins after N−1 records, at byte offset (N−1)*sizeof(EMP). seekp() moves the put pointer there; tellg() only reports the current position.

Explanation

In-order (left, root, right) gives a+b*c, pre-order (root first) gives +a*bc, and post-order (root last) gives abc*+.

Explanation

Sequential, direct, random and associative access are the access methods used to describe computer memory systems.

Explanation

The log-scale graph shows transistors per chip doubling at regular intervals, which is Moore's law.

Explanation

A control array is a group of controls of the same type that share one name and are told apart by an Index property.

Explanation

In inorder, preorder and postorder the left subtree is always visited before the right subtree. Only the position of the root changes.

Explanation

In a BST, an inorder traversal (left, root, right) visits the keys in ascending order.

Explanation

After pushing P to T, popping four times sends T, S, R, Q to the queue, leaving P on the stack. Dequeuing two gives T and S, which are pushed back (stack P, T, S). The next pop returns S.

Explanation

CALL pushes the return address (the address of the next instruction) onto the stack, and RET pops it back into the program counter.

Explanation

An XML document has exactly one root element, which encloses every other element.

Explanation

In a circular doubly linked list the last node is reached directly through head->prev. So two lists can be joined by changing a few pointers in O(1) time, without traversing.

Explanation

Merge sort splits the array, recursively sorts each half and merges them. Insertion, bubble and heap sort are usually written iteratively.

Explanation

seek(offset) moves the file pointer to a given position. tell() only reports the current position.

Explanation

A balanced BST has height O(log₂N). If keys are inserted in sorted order the tree becomes a chain with height N−1.

Explanation

Several bus segments branch out from a main backbone cable, making a hierarchy of buses. This is a tree topology.

Explanation

Binary search repeatedly halves the search range by comparing with the middle element, which only works if the array is sorted. Linear search works on unsorted data.

Explanation

The figure shows a root with a left subtree A and a right subtree B. This is the recursive definition of a binary tree.

Explanation

A self-referential structure has a pointer to its own type: struct node { int data; struct node *link; };. A member of type node itself would be infinitely recursive.

Explanation

A spanning tree of n vertices keeps exactly n − 1 edges. So from a graph with e edges you remove e − (n − 1) = e − n + 1 edges.

Explanation

Quick sort and merge sort are divide-and-conquer algorithms and are normally written recursively. Bubble sort and insertion sort are simple iterative algorithms.

Explanation

Tree A is strictly binary because every node has 0 or 2 children. Tree B is not, because L and R each have only one child. Tree C is a full tree of height 2 with every level filled, so it is complete.

Explanation

Rows 1 to i−1 hold 1 + 2 + … + (i−1) = i(i−1)/2 elements. A[i, j] is the j-th element of row i, so its location is i(i−1)/2 + j. Check: A[1,1] gives 0 + 1 = 1.

Explanation

The parentheses bind * to p first, so p is a pointer, and that pointer points to an array of 5 ints. Without parentheses, int *p[5] would be an array of 5 pointers to int.

Explanation

The accumulator holds an operand and stores the result of arithmetic and logic operations. The program counter holds the next instruction's address, and the stack pointer holds the top of the stack.

Explanation

A stack machine takes its operands implicitly from the top of the stack. So instructions like ADD need no address fields, which makes them zero-address instructions.

Explanation

seekg(F.tellg()*N) multiplies the current position by N, which is not the offset of the (N+1)th record. The correct offset is N*sizeof(EMPLOYEE).

Explanation

Zig-zig rotations are the restructuring steps of a splay tree, which move an accessed node up to the root.

Explanation

A skewed (degenerate) BST is like a linked list, so a search may have to visit all n nodes: O(n) in the worst case.

Explanation

ReDim resizes a dynamic array in VB (ReDim Preserve also keeps its existing contents). Dim only declares the array.

Explanation

Removing B separates {A, D} from {C, E}, and removing C cuts off E. Removing A, D or E leaves the graph connected, so the cut vertices are B and C.

Explanation

In a B-tree of order p, every non-root node has at least ⌈p/2⌉ children. So the maximum height is log base ⌈p/2⌉ of (n+1)/2.

Explanation

8 2 3 ^ gives 2³ = 8, then 8 / 8 = 1. Next 2 and 3 are pushed and * gives 6. The stack now holds 1, 6, so the top two elements are 6 and 1.

Explanation

Each recursive call pushes its return address and local variables onto a stack, so recursion is implemented with a stack.

Explanation

Inserting B, I, N, A, R, Y gives root B with A on the left and the chain I → N → R → Y to the right. The longest path B-I-N-R-Y has 4 edges, so the height is 4.

Explanation

pl.plot([5, 2, 3, 1]) draws a line graph, using the indexes 0-3 as x values. bar and scatter give different charts, and pl.line does not exist.

Explanation

The new node's next and prev pointers are set, and the next pointer of the previous node and the prev pointer of the following node are updated. That makes 4 pointer changes.

Explanation

The loop must stop at the end of the list or when X is found, so it continues only while P != NULL && P→Element != X. Checking for NULL first also avoids dereferencing a null pointer.

Explanation

NumPy subtracts arrays element by element: [12−10, 23−20] = [2 3]. It does not stack or combine the arrays.

Explanation

Answer as per the book's key (b). Note that S→next == NULL would normally mean the stack is empty, so this question is doubtful.

Explanation

The loop body does constant work and runs N times, so the running time is linear, O(N). O(2N) also simplifies to O(N).

Explanation

The figure compares pairs, moves the smaller key up each level and puts the minimum (06) at the root. This tournament-style structure is tree (tournament) sort.

Explanation

Inorder traversal visits left subtree, root, then right subtree. Left subtree gives a + b * d, then the root −, then the right subtree e / f, giving a + b * d − e/f.

Explanation

In Java, new int[4][5] creates 4 rows and 5 columns. Declarations like int array[4][5] are not valid Java, and [5][4] has the dimensions reversed.

Explanation

Operands are pushed onto a stack. When an operator is read, the top two operands are popped, the operator is applied and the result is pushed back, so a stack is the natural structure for postfix evaluation.

Explanation

C supports only call by value. Even a pointer is passed by value (a copy of the address); call by reference is only simulated by using that address.

Explanation

Memory allocated with new[] for an array must be freed with delete [] pp, so that the whole array is released and destructors run for every element.

Explanation

Python dictionaries have pop(), popitem() and get(), but no remove() method. remove() belongs to lists and sets.

Explanation

The event queue holds incoming events and decides the order (sequence) in which they are dispatched and handled.

Explanation

In any binary tree, the number of leaf nodes is one more than the number of nodes with two children, so n leaves means n − 1 nodes of degree 2.

Explanation

In a 1-based circular queue of size N, it is full (overflow) when Front = 1 and Rear = N, or when Front = Rear + 1 (rear has wrapped round to just behind front).