⏱️
15 questions · 24 marks · 50 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1NAT2 marksAddress
int A[1..20][1..30] (4 bytes) is row-major from 1000. Address of A[10][15]?
Numerical answer: ________
Q2NAT2 marksColumn-major
The same array column-major. Address of A[10][15]?
Numerical answer: ________
Q3MCQ1 markStack
push 1, push 2, pop, push 3, push 4, pop, pop, pop. Output?
- (A) 2 4 1 3
- (B) 1 2 3 4
- (C) 2 3 4 1
- (D) 2 4 3 1
Q4MCQ2 marksPostfix
The postfix of (a + b) * c - d / e ^ f is:
- (A)
a b c + * d e f ^ / - - (B)
a b + c d * e f ^ / - - (C)
a b + c * d e / f ^ - - (D)
a b + c * d e f ^ / -
Q5NAT2 marksPostfix value
Evaluate 2 3 4 * + 5 -.
Numerical answer: ________
Q6MCQ2 marksStack permutation
Input 1, 2, 3, 4, 5 through one stack. Which output is impossible?
- (A) 2 5 3 4 1
- (B) 1 5 4 3 2
- (C) 3 2 1 5 4
- (D) 4 5 3 2 1
Q7NAT1 markCatalan
How many stack permutations do 6 items have?
Numerical answer: ________
Q8MCQ1 markQueue
Linear array queue of size 6 (front = 0, rear = −1): enqueue ×6, dequeue ×3. Can another item be enqueued?
- (A) Only after shifting
- (B) Yes, at index 0
- (C) Yes, 3 slots are free
- (D) No, rear == MAX − 1
Q9NAT1 markCircular queue
Circular queue, N = 9, front = 6, rear = 2 (standard convention). Number of items?
Numerical answer: ________
Q10MCQ2 marksTwo stacks
A queue from two stacks (pour when out is empty) gets n enqueues then n dequeues. Total stack pushes?
- (A) 3n
- (B) n²
- (C) 2n
- (D) n
Q11MCQ1 markPriority queue
In an unsorted-array priority queue of n items, delete-max costs:
- (A) O(log n)
- (B) O(n log n)
- (C) O(n)
- (D) O(1)
Q12MCQ2 marksLinked list
What does this print?
int main(void)
{
int a[] = {4, 8, 15, 16, 23};
struct node *head = build(a, 5);
struct node *p = head->next->next;
p->next = p->next->next;
head = head->next;
printList(head);
return 0;
}
- (A)
15 23 - (B)
4 8 15 23 - (C)
8 15 23 - (D)
8 15 16 23
Q13NAT2 marksReverse
Iterative reversal of a 12-node list: how many times is the statement cur->next = prev executed?
Numerical answer: ________
Q14MCQ1 markDoubly
Which needs only O(1) time in a doubly linked list given a pointer p to a node?
- (A) search for a value
- (B) find the k-th node
- (C) sort the list
- (D) delete p
Q15MSQ2 marksImplementations
Which are O(1) per operation?
- (A) dequeue from the tail of a singly linked list with a tail pointer
- (B) enqueue/dequeue of a circular array queue
- (C) enqueue/dequeue of a linked queue with front and rear
- (D) push/pop of a linked stack (at head)
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 21362 marks
((9)·30 + 14)·4 = 1136 → 2136.
Re-read: Lesson 3.1 — Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and search
Q2 Answer: 21562 marks
((14)·20 + 9)·4 = 1156 → 2156.
Re-read: Lesson 3.1 — Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and search
Q3 Answer: (D)1 mark
LIFO.
- (A) is wrong: 3 comes before 1.
- (B) is wrong: Not FIFO.
- (C) is wrong: 4 is on top of 3.
Re-read: Lesson 3.2.1 — Stack ADT; push/pop/peek; array implementation; overflow and underflow
Q4 Answer: (D)2 marks
a b + c * d e f ^ / -.
- (A) is wrong: a + b is bracketed.
- (B) is wrong: * applies to (a + b) and c.
- (C) is wrong: ^ binds before /.
Re-read: Lesson 3.2.2 — Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluation
Q5 Answer: 92 marks
2 + 12 − 5 = 9.
Re-read: Lesson 3.2.2 — Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluation
Q6 Answer: (A)2 marks
After 5 is popped the top is 4, not 3.
- (B) is wrong: push 1, pop, push 2–5, pop ×4.
- (C) is wrong: push 1 2 3, pop ×3, push 4 5, pop ×2.
- (D) is wrong: push 1–4, pop 4, push 5, pop 5, pop 3 2 1.
Re-read: Lesson 3.2.3 — Valid stack permutations; Catalan numbers
Q7 Answer: 1321 mark
C(6) = 132.
Re-read: Lesson 3.2.3 — Valid stack permutations; Catalan numbers
Q8 Answer: (D)1 mark
The linear version cannot reuse freed slots.
- (A) is wrong: Without shifting, no.
- (B) is wrong: Indices do not wrap.
- (C) is wrong: The free slots are behind front.
Re-read: Lesson 3.3.1 — Queue ADT; linear array queue and its wasted-space problem
Q9 Answer: 51 mark
(2 − 6 + 9) % 9 = 5.
Re-read: Lesson 3.3.2 — Circular queue: full/empty conditions and index arithmetic
Q10 Answer: (C)2 marks
Each item is pushed into in and once into out.
- (A) is wrong: Only two pushes per item.
- (B) is wrong: Each item is moved once.
- (D) is wrong: Pouring pushes again.
Re-read: Lesson 3.3.3 — Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)
Q11 Answer: (C)1 mark
A full scan.
- (A) is wrong: No structure to exploit.
- (B) is wrong: One scan suffices.
- (D) is wrong: The maximum must be found.
Re-read: Lesson 3.3.3 — Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)
Q12 Answer: (C)2 marks
Lesson 3.4.1.
Output
8 15 23
- (A) is wrong: 8 remains.
- (B) is wrong: head moved.
- (D) is wrong: 16 is unlinked.
Re-read: Lesson 3.4.1 — Singly linked list: node, head, traversal, search, insertion (head/tail/middle), deletion
Q13 Answer: 122 marks
Once per node: 12.
Re-read: Lesson 3.4.2 — Reversing a list (iterative and recursive); finding the middle; detecting a cycle (fast/slow pointers)
Q14 Answer: (D)1 mark
Neighbours are known.
- (A) is wrong: Needs a walk.
- (B) is wrong: Needs a walk.
- (C) is wrong: Needs many steps.
Re-read: Lesson 3.4.3 — Doubly and circular linked lists; operation costs compared with arrays
Q15 Answer: (B) (C) (D)2 marks
Deleting the tail needs its predecessor.
- (A) is wrong: O(n): the new tail must be found.
Re-read: Lesson 3.4.4 — Stack and queue built on linked lists
If you got these wrong, re-read
| Question | Marks | Topic | Re-read |
|---|---|---|---|
| Q1 | 2 | Address | Lesson 3.1 |
| Q2 | 2 | Column-major | Lesson 3.1 |
| Q3 | 1 | Stack | Lesson 3.2.1 |
| Q4 | 2 | Postfix | Lesson 3.2.2 |
| Q5 | 2 | Postfix value | Lesson 3.2.2 |
| Q6 | 2 | Stack permutation | Lesson 3.2.3 |
| Q7 | 1 | Catalan | Lesson 3.2.3 |
| Q8 | 1 | Queue | Lesson 3.3.1 |
| Q9 | 1 | Circular queue | Lesson 3.3.2 |
| Q10 | 2 | Two stacks | Lesson 3.3.3 |
| Q11 | 1 | Priority queue | Lesson 3.3.3 |
| Q12 | 2 | Linked list | Lesson 3.4.1 |
| Q13 | 2 | Reverse | Lesson 3.4.2 |
| Q14 | 1 | Doubly | Lesson 3.4.3 |
| Q15 | 2 | Implementations | Lesson 3.4.4 |