Linear Data Structures: Arrays, Stacks, Queues & Linked Lists: 28 flashcards
All 28 flashcards from this kit, free and with no sign-up.
1. What is a linear data structure?
Show the answer
A structure that stores elements in a sequence where each element has at most one predecessor and one successor.
2. State the array address formula.
Show the answer
$\text{Address}(A[i]) = B + i \times w$, where $B$ is the base address and $w$ is the element size in bytes.
3. Why is array access $O(1)$?
Show the answer
Because the address is computed directly using $B + i \times w$; no traversal is needed.
4. What is the cost of inserting or deleting in the middle of an array?
Show the answer
$O(n)$, because elements must be shifted to maintain contiguity.
5. What is a sparse matrix?
Show the answer
A matrix in which most elements are zero, so storing every cell wastes memory.
6. How is a sparse matrix stored in triplet form?
Show the answer
Only non-zero entries are stored as $(row, column, value)$ triples, along with matrix dimensions and the count of non-zeros.
7. Define LIFO.
Show the answer
Last In, First Out — the most recently inserted element is removed first, as in a stack.
8. What are the two core stack operations and their complexity?
Show the answer
Push (insert at top) and pop (remove from top); both are $O(1)$.
9. What is Polish notation?
Show the answer
Prefix notation in which the operator precedes its operands, e.g. $+\,A\,B$.
10. What is Reverse Polish notation?
Show the answer
Postfix notation in which the operator follows its operands, e.g. $A\,B\,+$.
11. How is a postfix expression evaluated using a stack?
Show the answer
Push operands; on an operator, pop two operands, apply the operator, and push the result. The final stack value is the answer.
12. How many moves does the Tower of Hanoi need for $n$ disks?
Show the answer
$2^n - 1$ moves.
13. Define FIFO.
Show the answer
First In, First Out — the earliest inserted element is removed first, as in a queue.
14. Where do enqueue and dequeue occur in a queue?
Show the answer
Enqueue at the rear; dequeue at the front.
15. How does a circular queue wrap the rear index?
Show the answer
$\text{rear} = (\text{rear} + 1) \bmod \text{size}$, so freed slots at the front are reused.
16. How does a priority queue differ from a normal queue?
Show the answer
It dequeues the highest-priority element, not the earliest one.
17. Compare dequeue cost in an array-based priority queue and a heap.
Show the answer
Array-based dequeue is $O(n)$; a heap reduces it to $O(\log n)$.
18. What is a deque?
Show the answer
A double-ended queue that allows insertion and deletion at both front and rear.
19. What does a singly linked list node contain?
Show the answer
Data and a pointer to the next node.
20. What extra pointer does a doubly linked list node have?
Show the answer
A pointer to the previous node, enabling backward traversal.
21. What defines a circular linked list?
Show the answer
The last node points back to the first node, useful for round-robin scheduling.
22. Compare access and insertion cost in a linked list.
Show the answer
Access is $O(n)$ because you traverse from the head; insertion or deletion at a known position is $O(1)$.
23. Why is a linked stack preferred when size is unknown?
Show the answer
It pushes and pops at the head in $O(1)$ with no fixed size limit, avoiding overflow.
24. How does a linked queue achieve $O(1)$ operations?
Show the answer
It keeps front and rear pointers; enqueue at rear and dequeue at front are both $O(1)$.
25. Why are arrays cache-friendly?
Show the answer
Their elements occupy contiguous memory locations, improving cache locality.
26. Name two applications of priority queues.
Show the answer
Dijkstra's algorithm and Huffman coding (also OS task scheduling).
27. Name two applications of deques.
Show the answer
Sliding-window algorithms and undo/redo buffers.
28. What real-world processes do queues model?
Show the answer
Fair-order processes such as print spooling and CPU scheduling.
Your notes can be a kit like these
Every kit here was made from real study material. Point Veda at a chapter, a PDF, a photo or a link and get notes, flashcards, practice MCQs, games and a scored test — free, in 42 languages.
- Chapter notes
- Flashcards
- Practice MCQs
- Scored tests
- Exam prep
Get Veda free See what students get
Free to start · No ads · Works in 42 languages