Study sets
English

Fundamental Information Technology Engineer Examination (FE) | Subject A Data Structures and Algorithms Questions 01

1 / 100.0s

Problem 1

Starting with an empty stack, perform push(A), push(B), push(C), pop(), push(D), and pop() in that order. push(x) stores x, and pop() removes the top element.

Which pair lists the elements removed by the two pop() operations in order?

View explanation

After the first three pushes, the stack holds A, B, and C from bottom to top, so the first pop removes C, the last item added. Pushing D then places D on top, so the second pop removes D. A stack follows LIFO: the last item stored is the first removed.

Problem 2

Starting with an empty circular queue of capacity four, perform enqueue(A), enqueue(B), enqueue(C), dequeue(), dequeue(), enqueue(D), and enqueue(E). No operation occurs while the queue is full.

If dequeue() is then repeated until the queue is empty, in what order are the elements removed?

View explanation

The first two dequeue operations remove A and B, leaving C at the front. D and E are then added at the rear, so the remaining logical order is C, D, E. Wrapping around the underlying array does not change FIFO order.

Problem 3

In a singly linked list, node P's next field points to node Q. Insert a new node R between P and Q so that the result is P→R→Q. Each right-hand side uses the references that exist when that assignment is executed.

Which assignment order inserts R without losing the reference to Q?

View explanation

First set R.next to Q so that R points to the original successor, and then change P.next to R. If P.next is changed to R first and R.next is then assigned P.next, R points to itself and the reference to Q is lost.

Problem 4

Insert keys 10, 17, and 24 in that order into an empty seven-element hash table indexed from 0 through 6. Use h(k) = k mod 7 and, after a collision, inspect successive indices until an empty slot is found. Index 0 follows index 6.

At which index is key 24 stored?

View explanation

Each of 10 mod 7, 17 mod 7, and 24 mod 7 equals 3. Key 10 occupies index 3 and the colliding key 17 occupies index 4, so key 24 finds the next empty slot at index 5. A collision must not overwrite an existing key.

Problem 5

A binary search tree has root 8. Its left child is 3 and its right child is 10. Node 3 has left child 1 and right child 6, while node 10 has right child 14. There are no other children.

Which sequence results from an inorder traversal of left subtree, node, and right subtree?

View explanation

The left subtree yields 1, 3, 6, followed by root 8, and the right subtree yields 10, 14. The full sequence is therefore 1, 3, 6, 8, 10, 14. Inorder traversal of a binary search tree produces keys in ascending order.

Problem 6

An undirected graph has edges A-B, A-C, B-D, C-D, and C-E. Run breadth-first search from A, adding unvisited adjacent vertices to the queue in alphabetical order. Mark a vertex visited when it is added to the queue.

In what order are vertices removed from the queue for processing?

View explanation

Processing A enqueues B and C. Processing B then adds D. When C is processed, D is already visited, so only E is added. Queue order therefore produces A, B, C, D, E. Following A, B, D deep along one route resembles depth-first search instead.

Problem 7

A directed graph with no negative weights has edges A→B (weight 4), A→C (weight 1), C→B (weight 2), B→D (weight 1), and C→D (weight 5).

Which combination gives the shortest path from A to D and its total weight?

View explanation

The path A→C→B→D has weight 1 + 2 + 1 = 4, less than 5 for A→B→D and 6 for A→C→D. A path with more edges can still have the smallest total weight. A→B→C→D is not a valid path because there is no B→C edge.

Problem 8

Consider the following recursive function f. f(n): if n <= 1 then return 1 else return n * f(n - 1) endif

What value does f(4) return?

View explanation

f(4) = 4 × f(3) = 4 × 3 × f(2) = 4 × 3 × 2 × f(1). The base case gives f(1) = 1, so the result is 24. The value 10 comes from adding 4 + 3 + 2 + 1, while 16 is the square of 4.

Problem 9

Let n be a positive integer, and assume operation X takes constant time. Consider this pseudocode. for i = 1 to n for j = 1 to i operation X endfor endfor

Which combination gives the total executions of X and the time complexity?

View explanation

The inner loop runs i times for i = 1, 2, ..., n. Its total is 1 + 2 + ... + n = n(n + 1)/2. The highest-order term is n^2/2, so after omitting constant factors and lower-order terms, the time complexity is O(n^2).

Problem 10

Sort records by score in ascending order using a stable sort. Before sorting, their order is (90, A), (70, B), (90, C), (70, D). There is no additional ordering rule for equal scores.

What is the order after sorting?

View explanation

Ascending score places the two 70 records before the two 90 records. A stable sort preserves the original relative order of records with equal keys, so B remains before D and A remains before C. The second choice is ordered by score but reverses both equal-score pairs.