Loading...
Loading...
Phase 1: Technical Theory | Date: 29 July 2026 | Subject: Linear Data Structures | Questions in Exam: Approximately 8
A data structure is a method of organizing data so that it can be stored, accessed, and changed efficiently.
Today, we will study four important linear data structures:
Arrays
Linked Lists
Stacks
Queues
Focused Practice
| Hour | Topic | Main Target |
|---|---|---|
| 1 | Arrays | Calculate addresses in row-major and column-major order |
| 2 | Linked Lists | Understand all types and basic operations |
| 3 | Stacks | Master stack operations and infix-to-postfix conversion |
| 4 | Queues | Compare simple, circular, priority, and double-ended queues |
| 5 | Practice | Solve address and expression-conversion problems |
| Term | Simple Meaning |
|---|---|
| Data | Raw values such as numbers, names, and marks |
| Data structure | A method of organizing data |
| Linear data structure | Elements are arranged in a sequence |
| Non-linear data structure | Elements form a hierarchy or network |
| Static | Size is normally fixed before execution |
| Dynamic | Size can grow or shrink during execution |
| Traversal | Visiting elements one by one |
| Insertion | Adding a new element |
| Deletion | Removing an element |
| Searching | Finding a required element |
| Index | Position number of an array element |
| Pointer | A variable that stores a memory address |
| Node | A unit containing data and one or more links |
Data Structures
|
+-- Linear
| |
| +-- Array
| +-- Linked List
| +-- Stack
| +-- Queue
|
+-- Non-linear
|
+-- Tree
+-- Graph
In a linear structure, elements can normally be viewed in a sequence:
Element 1 -> Element 2 -> Element 3 -> Element 4
An array is a collection of elements of the same data type stored in consecutive, or contiguous, memory locations.
For example:
int marks[5] = {70, 82, 91, 65, 88};
Conceptual representation:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 70 | 82 | 91 | 65 | 88 |
Important observations:
0.If the first element begins at address 1000 and each integer occupies 4 bytes:
| Element | Address |
|---|---|
marks[0] | 1000 |
marks[1] | 1004 |
marks[2] | 1008 |
marks[3] | 1012 |
marks[4] | 1016 |
This is why array access by index takes constant time, written as O(1).
| Operation | Meaning | Typical Time |
|---|---|---|
| Access by index | Read A[i] | O(1) |
| Update by index | Change A[i] | O(1) |
| Traversal | Visit every element | O(n) |
| Linear search | Check elements one by one | O(n) |
| Insertion at beginning | Shift existing elements right | O(n) |
| Deletion at beginning | Shift remaining elements left | O(n) |
| Insertion at end | Add after last element, if space exists | O(1) |
| Deletion at end | Remove last element | O(1) |
The final two O(1) values assume that the current size and free capacity are already known.
A one-dimensional array, or 1D array, uses one index.
Example:
int A[5] = {10, 20, 30, 40, 50};
A[0] = 10
A[1] = 20
A[2] = 30
A[3] = 40
A[4] = 50
Let:
B = base address, meaning the address of the first array elementW = size of one element in bytesi = required indexLB = lower bound, meaning the first valid indexThen:
Address of A[i] = B + W × (i − LB)
An integer array A[0...9] starts at address 1000. Each element occupies 4 bytes. Find the address of A[6].
Given:
Calculation:
Address of A[6]
= B + W × (i − LB)
= 1000 + 4 × (6 − 0)
= 1000 + 24
= 1024
Answer: 1024
Array B[5...15] starts at address 200. Each element occupies 2 bytes. Find the address of B[11].
Address of B[11]
= 200 + 2 × (11 − 5)
= 200 + 2 × 6
= 212
Answer: 212
Do not multiply the element value by its width. Multiply the number of positions from the lower bound by the width.
A two-dimensional array, or 2D array, has rows and columns.
Example:
int A[2][3] = {
{10, 20, 30},
{40, 50, 60}
};
Matrix view:
| Row/Column | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 10 | 20 | 30 |
| 1 | 40 | 50 | 60 |
An element is written as A[i][j], where:
i is the row index.j is the column index.Computer memory is a one-dimensional sequence of locations. Therefore, the rows and columns must be converted into a linear storage order.
The two main orders are:
In row-major order, all elements of the first row are stored first. Then all elements of the second row are stored, and so on.
For this array:
| Column 0 | Column 1 | Column 2 | |
|---|---|---|---|
| Row 0 | A | B | C |
| Row 1 | D | E | F |
Row-major storage is:
A, B, C, D, E, F
C and C++ store multidimensional arrays in row-major order.
For an array:
A[LR...UR][LC...UC]
Let:
B = base addressW = size of one elementI = required row indexJ = required column indexLR = lower row boundLC = lower column boundN = total number of columnsNumber of columns:
N = UC − LC + 1
Formula:
Address of A[I][J] = B + W × [(I − LR) × N + (J − LC)]
Before reaching A[I][J]:
(I − LR) complete rows.N elements.(J − LC) elements inside the required row.W.Row-major uses the number of Columns.
Remember:
R-C: Row-major → Columns
Array A[0...3][0...4] has:
Find the address of A[2][3].
Number of columns:
N = 4 − 0 + 1 = 5
Calculation:
Address
= 1000 + 2 × [(2 − 0) × 5 + (3 − 0)]
= 1000 + 2 × [10 + 3]
= 1000 + 26
= 1026
Answer: 1026
Array B[1...5][2...8] begins at address 500. Each element is 4 bytes. Find the row-major address of B[4][6].
Number of columns:
N = 8 − 2 + 1 = 7
Calculation:
Address
= 500 + 4 × [(4 − 1) × 7 + (6 − 2)]
= 500 + 4 × [3 × 7 + 4]
= 500 + 4 × 25
= 600
Answer: 600
In column-major order, all elements of the first column are stored first. Then all elements of the second column are stored, and so on.
For this array:
| Column 0 | Column 1 | Column 2 | |
|---|---|---|---|
| Row 0 | A | B | C |
| Row 1 | D | E | F |
Column-major storage is:
A, D, B, E, C, F
Fortran traditionally uses column-major order.
Let:
B = base addressW = size of one elementI = required row indexJ = required column indexLR = lower row boundLC = lower column boundM = total number of rowsNumber of rows:
M = UR − LR + 1
Formula:
Address of A[I][J] = B + W × [(J − LC) × M + (I − LR)]
Before reaching A[I][J]:
(J − LC) complete columns.M elements.(I − LR) elements down the required column.Column-major uses the number of Rows.
Remember:
C-R: Column-major → Rows
Array A[0...3][0...4] begins at address 1000. Each element occupies 2 bytes. Find the column-major address of A[2][3].
Number of rows:
M = 3 − 0 + 1 = 4
Calculation:
Address
= 1000 + 2 × [(3 − 0) × 4 + (2 − 0)]
= 1000 + 2 × [12 + 2]
= 1000 + 28
= 1028
Answer: 1028
Array B[1...5][2...8] begins at address 500. Each element occupies 4 bytes. Find the column-major address of B[4][6].
Number of rows:
M = 5 − 1 + 1 = 5
Calculation:
Address
= 500 + 4 × [(6 − 2) × 5 + (4 − 1)]
= 500 + 4 × [20 + 3]
= 500 + 92
= 592
Answer: 592
| Point | Row-Major | Column-Major |
|---|---|---|
| First complete group stored | Row | Column |
| Main multiplier | Number of columns | Number of rows |
| Formula begins with | (I − LR) × N | (J − LC) × M |
| Used by | C, C++ | Fortran, MATLAB internally uses column-major conventions |
| Memory sequence for 2 × 3 array | A, B, C, D, E, F | A, D, B, E, C, F |
Row-major: row changes slowly, column changes quickly.
Column-major: column changes slowly, row changes quickly.
Use these steps in every numerical question:
B.W.I, J, LR, and LC.W.B.A[1...10] contains 10 elements, not 9.Upper bound − Lower bound + 1.A[LR][LC].A linked list is a linear data structure made of separate units called nodes.
A node normally contains:
Unlike an array, linked-list nodes do not need to occupy consecutive memory locations.
Example:
HEAD
|
v
+------+-------+ +------+-------+ +------+------+
| 10 | o------->| 20 | o------->| 30 | NULL |
+------+-------+ +------+-------+ +------+------+
Each box represents a node.
HEAD stores the address of the first node.NULL means that there is no next node.| Feature | Array | Linked List |
|---|---|---|
| Memory arrangement | Contiguous | Usually non-contiguous |
| Size | Normally fixed | Dynamic |
| Direct access by position | Yes, O(1) | No, O(n) |
| Insertion at beginning | O(n) due to shifting | O(1) |
| Deletion at beginning | O(n) due to shifting | O(1) |
| Extra pointer memory | Not required | Required |
| Cache performance | Usually better | Usually weaker |
| Binary search | Practical on sorted array | Not efficient due to no direct access |
| Memory use | May waste reserved space | Allocated as nodes are needed |
| Term | Meaning |
|---|---|
| Node | A structure containing data and link fields |
| Head | Pointer to the first node |
| Tail | Last node |
| Link | Pointer connecting one node to another |
| NULL | No valid next or previous node |
| Traversal | Visiting nodes one by one |
| Predecessor | Node before a given node |
| Successor | Node after a given node |
A singly linked list has one link in each node. The link points to the next node.
Node form:
+---------+---------+
| Data | Next |
+---------+---------+
List form:
HEAD -> [10 | next] -> [20 | next] -> [30 | NULL]
Movement is normally possible only in the forward direction.
Traversal means visiting each node.
Conceptual algorithm:
Step 1: Set current = HEAD
Step 2: While current is not NULL:
Process current's data
Set current = current->next
Step 3: Stop
Example:
HEAD -> 5 -> 8 -> 12 -> NULL
Traversal output:
5 8 12
Time complexity: O(n)
Original list:
HEAD -> 20 -> 30 -> NULL
Insert 10:
HEAD to the new node.Result:
HEAD -> 10 -> 20 -> 30 -> NULL
Time complexity: O(1)
Original list:
HEAD -> 10 -> 20 -> NULL
Insert 30:
NULL.Result:
HEAD -> 10 -> 20 -> 30 -> NULL
Time complexity:
HEAD is availableTAIL pointer is maintainedOriginal:
HEAD -> 10 -> 20 -> 40 -> NULL
Insert 30 after 20:
new->next = node20->next.node20->next = new.Result:
HEAD -> 10 -> 20 -> 30 -> 40 -> NULL
Always connect the new node to the remaining list before changing the previous node's link. Otherwise, the rest of the list may become unreachable.
Original:
HEAD -> 10 -> 20 -> 30 -> NULL
Steps:
HEAD to HEAD->next.Result:
HEAD -> 20 -> 30 -> NULL
Time complexity: O(1)
Original:
HEAD -> 10 -> 20 -> 30 -> NULL
To delete 30:
NULL.Result:
HEAD -> 10 -> 20 -> NULL
Time complexity: O(n) in a singly linked list.
To delete 20:
Before: HEAD -> 10 -> 20 -> 30 -> NULL
After: HEAD -> 10 ------> 30 -> NULL
The link of node 10 is changed to point to node 30.
Time complexity: O(n) because the node may need to be searched.
A doubly linked list has two links in every node:
Node form:
+----------+---------+----------+
| Previous | Data | Next |
+----------+---------+----------+
List form:
NULL <- [10] <=> [20] <=> [30] -> NULL
Before:
A <=> B
Insert X:
A <=> X <=> B
Four link relationships must be correct:
X.previous = A
X.next = B
A.next = X
B.previous = X
Before:
A <=> X <=> B
After deleting X:
A <=> B
Updates:
A.next = B
B.previous = A
If the address of X is already known, deletion can take O(1).
In a circular linked list, the last node points back to the first node instead of pointing to NULL.
HEAD
|
v
[10] -> [20] -> [30]
^ |
|_______________|
The last node's next link contains the address of the first node.
NULL link at the end.In an ordinary list, traversal stops at NULL.
In a circular list, traversal stops when the current pointer reaches the starting node again. Otherwise, the traversal will continue forever.
| Feature | Singly | Doubly | Circular |
|---|---|---|---|
| Links per node | One | Two | One or two |
| Forward traversal | Yes | Yes | Yes |
| Backward traversal | No | Yes | Only if doubly circular |
| Last link | NULL | Next is NULL | Points to first node |
| Memory requirement | Lowest | Higher | Depends on form |
| Easy backward movement | No | Yes | Only doubly circular |
| Typical application | Simple dynamic list | Browser history | Round-robin processing |
S-D-C
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
| Access kth node | O(n) | O(n) |
| Search by value | O(n) | O(n) |
| Insert at beginning | O(1) | O(1) |
| Delete from beginning | O(1) | O(1) |
| Insert at end with tail pointer | O(1) | O(1) |
| Delete known middle node | Previous node may be required | O(1) |
| Traversal | O(n) | O(n) |
A stack is a linear data structure that follows the Last In, First Out, or LIFO, principle.
The item added last is removed first.
Real-life example: a stack of plates.
Top
|
v
+-------+
| Plate C | <- Added last; removed first
+-------+
| Plate B |
+-------+
| Plate A |
+-------+
LIFO = Last In, First Out
Examples:
| Operation | Meaning |
|---|---|
| Push | Add an element to the top |
| Pop | Remove and return the top element |
| Peek or Top | Read the top element without removing it |
| isEmpty | Check whether the stack is empty |
| isFull | Check whether an array-based stack is full |
| Size | Return the number of elements |
Start with an empty stack.
push(10)
push(20)
push(30)
Stack:
TOP -> 30
20
10
Now:
pop() returns 30
Remaining stack:
TOP -> 20
10
Then:
peek() returns 20
The value 20 remains in the stack because peek does not remove it.
Suppose the stack capacity is 5.
Initially:
TOP = -1
This means the stack is empty.
To push an element:
TOP.stack[TOP].Conceptual steps:
TOP = TOP + 1
stack[TOP] = item
To pop an element:
stack[TOP].TOP.Conceptual steps:
item = stack[TOP]
TOP = TOP - 1
return item
For an array stack of capacity N:
| Condition | Test |
|---|---|
| Empty | TOP = -1 |
| Full | TOP = N − 1 |
| Number of elements | TOP + 1 |
Overflow occurs when a push operation is attempted on a full stack.
Underflow occurs when a pop or peek operation is attempted on an empty stack.
| Operation | Time |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| Search | O(n) |
A linked-list stack normally uses the head as the top.
TOP -> [30] -> [20] -> [10] -> NULL
A linked-list stack does not have a fixed array capacity. However, it can still fail if system memory is unavailable.
When a function calls another function, information about the current function is placed on the call stack.
Example:
main calls A
A calls B
B finishes
A finishes
main finishes
Stack behaviour:
Push main
Push A
Push B
Pop B
Pop A
Pop main
An expression contains:
A, B, 5, and 9+, -, *, /, and ^The operator is written between its operands.
A + B
The operator appears before its operands.
+ A B
The operator appears after its operands.
A B +
| Form | Example for (A + B) × C |
|---|---|
| Infix | (A + B) * C |
| Prefix | * + A B C |
| Postfix | A B + C * |
Postfix expressions do not need parentheses because the order is represented by operator positions.
Precedence tells us which operator should be processed first.
| Priority | Operators | Meaning |
|---|---|---|
| Highest | () | Parentheses |
| 2 | ^ | Exponent |
| 3 | *, /, % | Multiplication, division, remainder |
| 4 | +, - | Addition, subtraction |
The numbering above describes processing order, not a numeric precedence value.
Mnemonic:
P-E-MD-AS
Parentheses, Exponent, Multiplication/Division, Addition/Subtraction
Associativity decides the processing direction when operators have equal precedence.
| Operators | Associativity |
|---|---|
+, -, *, /, % | Left to right |
^ | Right to left |
Examples:
A - B + C
Because - and + are left-associative:
(A - B) + C
But:
A ^ B ^ C
Because ^ is right-associative:
A ^ (B ^ C)
This difference is important during infix-to-postfix conversion.
Use an operator stack and an output list.
Read the infix expression from left to right.
If the symbol is an operand, send it directly to the output.
Input: A
Output: A
If the symbol is (, push it onto the stack.
If the symbol is ):
( is found.(.When an operator arrives:
After the input ends, pop all remaining operators to the output.
For +, -, *, /, and %:
Pop while the stack top has precedence greater than or equal to the incoming operator.
For ^:
Pop only operators with greater precedence, not equal precedence, because
^is right-associative.
A + B * C| Read | Action | Stack | Output |
|---|---|---|---|
| A | Output operand | Empty | A |
| + | Push | + | A |
| B | Output operand | + | AB |
| * | Higher than +, push | + * | AB |
| C | Output operand | + * | ABC |
| End | Pop all operators | Empty | ABC*+ |
Postfix: ABC*+
Reason: multiplication happens before addition.
(A + B) * C| Read | Action | Stack | Output |
|---|---|---|---|
| ( | Push | ( | Empty |
| A | Output | ( | A |
| + | Push | ( + | A |
| B | Output | ( + | AB |
| ) | Pop +; remove ( | Empty | AB+ |
| * | Push | * | AB+ |
| C | Output | * | AB+C |
| End | Pop * | Empty | AB+C* |
Postfix: AB+C*
A + B * C - D / E| Read | Action | Stack | Output |
|---|---|---|---|
| A | Output | Empty | A |
| + | Push | + | A |
| B | Output | + | AB |
| * | Push because it has higher precedence | + * | AB |
| C | Output | + * | ABC |
| - | Pop *, then pop +, then push - | - | ABC*+ |
| D | Output | - | ABC*+D |
| / | Push | - / | ABC*+D |
| E | Output | - / | ABC*+DE |
| End | Pop /, then - | Empty | ABC*+DE/- |
Postfix: ABC*+DE/-
A * (B + C) / D| Read | Stack | Output |
|---|---|---|
| A | Empty | A |
| * | * | A |
| ( | * ( | A |
| B | * ( | AB |
| + | * ( + | AB |
| C | * ( + | ABC |
| ) | * | ABC+ |
| / | / | ABC+* |
| D | / | ABC+*D |
| End | Empty | ABC+*D/ |
Why was * popped when / arrived? They have equal precedence and are left-associative.
Postfix: ABC+*D/
A ^ B ^ CBecause exponentiation is right-associative:
A ^ (B ^ C)
Postfix:
A B C ^ ^
Answer: ABC^^
It is not AB^C^, because that would represent (A ^ B) ^ C.
To evaluate postfix:
left operator right.5 2 3 * +| Token | Action | Stack |
|---|---|---|
| 5 | Push | 5 |
| 2 | Push | 5, 2 |
| 3 | Push | 5, 2, 3 |
| * | Pop 3 and 2; calculate 2 × 3 = 6; push 6 | 5, 6 |
| + | Pop 6 and 5; calculate 5 + 6 = 11 | 11 |
Answer: 11
For subtraction and division:
First popped value = right operand
Second popped value = left operand
For postfix 8 2 /:
Right operand = 2
Left operand = 8
Result = 8 / 2 = 4
A queue is a linear data structure that follows the First In, First Out, or FIFO, principle.
The element inserted first is removed first.
Real-life example: people waiting at a service counter.
Removal Insertion
| |
v v
FRONT -> [A] [B] [C] [D] <- REAR
FIFO = First In, First Out
| Operation | Meaning |
|---|---|
| Enqueue | Insert an element at the rear |
| Dequeue | Remove an element from the front |
| Front or Peek | Read the front element without removing it |
| Rear | Read the last element |
| isEmpty | Check whether the queue is empty |
| isFull | Check whether an array-based queue is full |
Start with an empty queue:
enqueue(10)
enqueue(20)
enqueue(30)
Queue:
FRONT -> 10, 20, 30 <- REAR
Now:
dequeue() returns 10
Remaining queue:
FRONT -> 20, 30 <- REAR
A simple queue, or linear queue, follows FIFO.
Suppose an array queue has size N.
Common initial values:
FRONT = -1
REAR = -1
When the first element is inserted:
FRONT = 0
REAR = 0
Increase REAR and store the new element.
Read the element at FRONT and increase FRONT.
Suppose the array has five positions:
Index: 0 1 2 3 4
Data: _ _ C D E
^ ^
FRONT REAR
Positions 0 and 1 are empty because earlier elements were deleted. However, if REAR = 4, a basic linear queue cannot insert another element without shifting data.
This situation is called false overflow or wasted-space problem.
A circular queue solves this problem.
A circular queue connects the last array position logically back to the first position.
+--------------------------------+
| |
v |
[0] [1] [2] [3] [4] ------------+
After index N − 1, the next index is 0.
The next position is calculated using:
Next position = (current position + 1) mod N
Here, mod gives the remainder.
For N = 5:
After index 0 -> (0 + 1) mod 5 = 1
After index 3 -> (3 + 1) mod 5 = 4
After index 4 -> (4 + 1) mod 5 = 0
This is called wrap-around.
With the common initialization:
FRONT = -1
REAR = -1
The queue is empty when:
FRONT = -1
When one direct front/rear design is used, the circular queue is full when:
(REAR + 1) mod N = FRONT
Example for N = 5:
FRONT = 2
REAR = 1
Then:
(1 + 1) mod 5 = 2 = FRONT
Therefore, the queue is full.
Check whether the queue is full.
If empty, set FRONT = REAR = 0.
Otherwise set:
REAR = (REAR + 1) mod N
Store the new element at REAR.
Check whether the queue is empty.
Read the element at FRONT.
If only one element exists, set:
FRONT = REAR = -1
Otherwise set:
FRONT = (FRONT + 1) mod N
A circular queue reuses the empty positions created by deletions.
A priority queue removes elements according to their priority, not simply according to arrival time.
Example:
| Task | Priority |
|---|---|
| Emergency process | 1 |
| System process | 2 |
| User process | 3 |
If a smaller number represents higher priority, the emergency process is removed first.
If two elements have the same priority, FIFO is often used between them.
Ascending priority queue
Descending priority queue
The exact meaning of the numeric priority depends on the implementation. Some systems use smaller numbers for higher priority, while others use larger numbers.
A priority queue is often implemented using a heap, which will be studied with trees.
A deque, pronounced “deck,” means double-ended queue.
It allows insertion and deletion at both ends.
FRONT <-> [A] [B] [C] <-> REAR
Operations include:
| Type | Insertion | Deletion | Main Rule |
|---|---|---|---|
| Simple queue | Rear | Front | FIFO |
| Circular queue | Rear with wrap-around | Front with wrap-around | FIFO with space reuse |
| Priority queue | Based on implementation | Highest or lowest priority | Priority first |
| Deque | Front and rear | Front and rear | Both ends |
| Input-restricted deque | One end | Both ends | Restricted insertion |
| Output-restricted deque | Both ends | One end | Restricted deletion |
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO | FIFO |
| Insertion operation | Push | Enqueue |
| Deletion operation | Pop | Dequeue |
| Active end | Top | Front and rear |
| Removed element | Most recently inserted | Earliest inserted |
| Example | Stack of plates | Waiting line |
| Common applications | Recursion, undo | Scheduling, buffering |
Stack: Last comes out first.
Queue: First comes out first.
| Structure | Insertion | Deletion | Access/Search |
|---|---|---|---|
| Array at known index | O(1) update | Not applicable directly | O(1) |
| Array at beginning | O(n) | O(n) | O(1) access |
| Singly linked list at head | O(1) | O(1) | O(n) |
| Stack | O(1) push | O(1) pop | O(1) top |
| Simple queue | O(1) enqueue | O(1) dequeue | O(1) front |
| Circular queue | O(1) enqueue | O(1) dequeue | O(1) front |
| Deque | O(1) at either end | O(1) at either end | Depends on implementation |
Try each question before reading the answer.
Array A[0...19] begins at address 500. Each element occupies 4 bytes. Find the address of A[12].
Address = 500 + 4 × (12 − 0)
= 548
Answer: 548
Array A[5...25] begins at address 1000. Each element occupies 2 bytes. Find the address of A[18].
Address = 1000 + 2 × (18 − 5)
= 1000 + 26
= 1026
Answer: 1026
Array A[-3...7] starts at address 200. Each element occupies 8 bytes. Find the address of A[4].
Address = 200 + 8 × [4 − (−3)]
= 200 + 8 × 7
= 256
Answer: 256
Array M[0...4][0...5] starts at address 100. Each element occupies 2 bytes. Find the row-major address of M[2][4].
Number of columns = 6
Address = 100 + 2 × [2 × 6 + 4]
= 100 + 32
= 132
Answer: 132
For the same array in Problem 4, find the column-major address of M[2][4].
Number of rows = 5
Address = 100 + 2 × [4 × 5 + 2]
= 100 + 44
= 144
Answer: 144
Array B[1...8][1...10] starts at address 1000. Each element occupies 4 bytes. Find the row-major address of B[5][7].
Number of columns = 10
Address = 1000 + 4 × [(5 − 1) × 10 + (7 − 1)]
= 1000 + 4 × 46
= 1184
Answer: 1184
For the same array in Problem 6, find the column-major address of B[5][7].
Number of rows = 8
Address = 1000 + 4 × [(7 − 1) × 8 + (5 − 1)]
= 1000 + 4 × 52
= 1208
Answer: 1208
Array C[2...6][3...9] starts at address 400. Each element occupies 2 bytes. Find the row-major address of C[5][8].
Number of columns = 9 − 3 + 1 = 7
Address = 400 + 2 × [(5 − 2) × 7 + (8 − 3)]
= 400 + 2 × [21 + 5]
= 452
Answer: 452
For the same array in Problem 8, find the column-major address of C[5][8].
Number of rows = 6 − 2 + 1 = 5
Address = 400 + 2 × [(8 − 3) × 5 + (5 − 2)]
= 400 + 2 × 28
= 456
Answer: 456
Array D[-2...3][4...8] starts at address 600. Each element occupies 4 bytes. Find the row-major address of D[1][7].
Number of columns = 8 − 4 + 1 = 5
Address = 600 + 4 × [(1 − (−2)) × 5 + (7 − 4)]
= 600 + 4 × [15 + 3]
= 672
Answer: 672
For the same array in Problem 10, find the column-major address of D[1][7].
Number of rows = 3 − (−2) + 1 = 6
Address = 600 + 4 × [(7 − 4) × 6 + (1 − (−2))]
= 600 + 4 × [18 + 3]
= 684
Answer: 684
Array E[1...4][0...7] starts at address 800. Each element occupies 8 bytes. Find the row-major address of E[3][5].
Number of columns = 8
Address = 800 + 8 × [(3 − 1) × 8 + 5]
= 800 + 8 × 21
= 968
Answer: 968
For the same array in Problem 12, find the column-major address of E[3][5].
Number of rows = 4
Address = 800 + 8 × [5 × 4 + (3 − 1)]
= 800 + 8 × 22
= 976
Answer: 976
Array F[10...15][20...24] starts at address 1500. Each element occupies 2 bytes. Find the row-major address of F[14][23].
Number of columns = 24 − 20 + 1 = 5
Address = 1500 + 2 × [(14 − 10) × 5 + (23 − 20)]
= 1500 + 2 × 23
= 1546
Answer: 1546
For the same array in Problem 14, find the column-major address of F[14][23].
Number of rows = 15 − 10 + 1 = 6
Address = 1500 + 2 × [(23 − 20) × 6 + (14 − 10)]
= 1500 + 2 × 22
= 1544
Answer: 1544
Infix:
A + B
Postfix:
AB+
Infix:
A + B * C
Postfix:
ABC*+
Infix:
(A + B) * C
Postfix:
AB+C*
Infix:
A * B + C / D
Postfix:
AB*CD/+
Infix:
A + B - C
Because + and - are left-associative:
AB+C-
Infix:
A * (B + C) - D
Postfix:
ABC+*D-
Infix:
(A + B) * (C - D)
Postfix:
AB+CD-*
Infix:
A + B * (C ^ D - E) ^ (F + G * H) - I
Postfix:
ABCD^E-FGH*+^*+I-
Infix:
A ^ B ^ C
Postfix:
ABC^^
Infix:
(A + B / C) * (D - E)
Postfix:
ABC/+DE-*
| Structure | Main Rule | Key Feature |
|---|---|---|
| Array | Index-based | Contiguous memory |
| Linked list | Nodes connected by links | Dynamic size |
| Stack | LIFO | One active end called top |
| Queue | FIFO | Insert at rear, delete at front |
Address of A[i] = B + W × (i − LB)
Address of A[I][J] = B + W × [(I − LR) × N + (J − LC)]
Where:
N = number of columns = UC − LC + 1
Address of A[I][J] = B + W × [(J − LC) × M + (I − LR)]
Where:
M = number of rows = UR − LR + 1
Row-major uses Columns.
Column-major uses Rows.
| Type | Main Feature |
|---|---|
| Singly | One next pointer |
| Doubly | Previous and next pointers |
| Circular | Last node links to first node |
| Condition | Array-Based Test |
|---|---|
| Empty | TOP = -1 |
| Full | TOP = N − 1 |
| Number of elements | TOP + 1 |
| Operator | Precedence | Associativity |
|---|---|---|
^ | Highest operator | Right to left |
*, /, % | Medium | Left to right |
+, - | Lowest | Left to right |
Infix-to-postfix:
( → push) → pop until ((index + 1) mod N(REAR + 1) mod N = FRONT| Stack | Queue |
|---|---|
| LIFO | FIFO |
| Push and pop | Enqueue and dequeue |
| Uses top | Uses front and rear |
| Undo, recursion | Scheduling, buffering |
Which statement correctly defines an array?
A. It stores elements only in random non-contiguous locations
B. It stores same-type elements in contiguous memory locations
C. It always grows automatically
D. It follows only the FIFO rule
The time complexity of accessing A[i] in an array is normally:
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
An array A[0...9] begins at address 200. Each element occupies 4 bytes. What is the address of A[6]?
A. 206
B. 212
C. 224
D. 240
An array B[5...20] begins at address 1000. Each element occupies 2 bytes. What is the address of B[12]?
A. 1012
B. 1014
C. 1024
D. 1034
Which value is used as the main multiplier in the row-major formula?
A. Number of rows
B. Number of columns
C. Element value
D. Base address
Array A[0...2][0...3] begins at address 500. Each element occupies 2 bytes. What is the row-major address of A[2][1]?
A. 510
B. 514
C. 518
D. 522
Array A[0...2][0...3] begins at address 500. Each element occupies 2 bytes. What is the column-major address of A[2][1]?
A. 506
B. 508
C. 510
D. 512
Which language conventionally stores multidimensional arrays in row-major order?
A. C
B. Fortran
C. SQL
D. HTML
A node in a singly linked list normally contains:
A. Only data
B. Data and one next pointer
C. Two data fields and no pointer
D. Only a previous pointer
What does the last node of an ordinary singly linked list contain in its next field?
A. Address of the head
B. Address of the previous node
C. NULL
D. Its own address
Which linked list allows easy forward and backward traversal?
A. Singly linked list
B. Doubly linked list
C. Ordinary array
D. Stack
In a circular singly linked list, the next field of the last node points to:
A. NULL
B. The first node
C. The previous node
D. A random node
What is the time complexity of inserting a node at the beginning of a singly linked list?
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
Which principle is followed by a stack?
A. FIFO
B. LIFO
C. Priority only
D. Random access
If TOP = -1 in an array-based stack, the stack is:
A. Full
B. Empty
C. Circular
D. Sorted
Which operation reads the top stack element without removing it?
A. Push
B. Pop
C. Peek
D. Enqueue
Perform these stack operations:
push(10), push(20), push(30), pop(), push(40)
Which value is now at the top?
A. 10
B. 20
C. 30
D. 40
What is the postfix form of A + B * C?
A. AB+C*
B. ABC*+
C. +A*BC
D. AB*C+
What is the postfix form of (A + B) * C?
A. ABC+*
B. AB*C+
C. AB+C*
D. A+BC*
What is the postfix form of A * B - C / D?
A. AB*CD/-
B. ABCD*/-
C. AB-CD*/
D. A*BC/D-
Evaluate the postfix expression:
6 2 / 3 +
A. 2
B. 3
C. 6
D. 9
Which principle is followed by a simple queue?
A. LIFO
B. FIFO
C. Highest value first
D. Last element never removed
Insertion and deletion in a simple queue normally occur at:
A. Front and front
B. Rear and rear
C. Rear and front
D. Front and middle
For a circular queue of capacity N, which expression gives the next array position?
A. current + N
B. (current + 1) mod N
C. current − N
D. current × N
Which data structure permits insertion and deletion at both the front and rear?
A. Stack
B. Simple queue
C. Deque
D. Singly linked list only
| Q. | Answer | Explanation |
|---|---|---|
| 1 | B | An array stores elements of the same type in consecutive memory locations. |
| 2 | A | The address is calculated directly from the index, so indexed access takes O(1). |
| 3 | C | Address = 200 + 4 × (6 − 0) = 224. |
| 4 | B | Address = 1000 + 2 × (12 − 5) = 1000 + 14 = 1014. |
| 5 | B | Row-major skips complete rows, and each complete row contains the total number of columns. |
| 6 | C | There are 4 columns. Address = 500 + 2 × (2 × 4 + 1) = 518. |
| 7 | C | There are 3 rows. Address = 500 + 2 × (1 × 3 + 2) = 510. |
| 8 | A | C and C++ use row-major storage for multidimensional arrays. |
| 9 | B | A singly linked-list node contains data and a pointer to the next node. |
| 10 | C | The last node of an ordinary singly linked list points to NULL. |
| 11 | B | A doubly linked list has both previous and next pointers. |
| 12 | B | A circular list connects the last node back to the first node. |
| 13 | A | The new node is linked before the current head, requiring constant time. |
| 14 | B | A stack follows Last In, First Out. |
| 15 | B | TOP = -1 is the common initial and empty-stack condition. |
| 16 | C | Peek, also called top, returns the top element without deleting it. |
| 17 | D | Pop removes 30. Push 40 then places 40 at the top. |
| 18 | B | Multiplication is completed before addition, giving ABC*+. |
| 19 | C | First calculate A+B, written AB+, and then multiply by C, giving AB+C*. |
| 20 | A | A*B becomes AB*, C/D becomes CD/, and subtraction gives AB*CD/-. |
| 21 | C | 6 2 / gives 3, and then 3 3 + gives 6. |
| 22 | B | A queue follows First In, First Out. |
| 23 | C | Enqueue inserts at the rear, and dequeue removes from the front. |
| 24 | B | Modulo makes the index return to 0 after reaching the final position. |
| 25 | C | A double-ended queue, or deque, supports operations at both ends. |
Start with an empty stack:
push(5)
push(8)
pop()
push(12)
push(20)
pop()
Final stack from bottom to top:
5, 12
Top element:
12
Start with an empty queue:
enqueue(10)
enqueue(20)
enqueue(30)
dequeue()
enqueue(40)
dequeue()
Removed elements:
10, then 20
Final queue:
FRONT -> 30, 40 <- REAR
Without looking above, write:
Correct answers:
1. B + W × (i − LB)
2. B + W × [(I − LR) × N + (J − LC)]
3. B + W × [(J − LC) × M + (I − LR)]
4. (current + 1) mod N
5. (REAR + 1) mod N = FRONT