Programming in Python, and the Data Structures: Stack, Queue, Linked List, BST, Heap and Graph

The last two sub-headings of Section A.2 are Programming — flowcharts and pseudo code, then Python: data types, operators, expressions, conditional statements (if, elif, else, case), loops (while, for), loop control (break, continue), functions, arrays, dictionaries, strings and recursion — and Data Structures: stack, queue, linked list, binary search tree, binary heap and graph. They share one chapter because GATE asks them the same way: trace a short program and state what it prints, or trace a sequence of operations on a structure and state what it holds. Every snippet below has been traced by hand, and the traps are the ones Python itself sets.

1. Flowcharts and pseudo code

A flowchart draws an algorithm with standard symbols: an oval terminal for start and end, a rectangle for a process, a parallelogram for input/output, a diamond for a decision with one arrow per outcome, and arrows for the flow of control. Pseudo code writes the same algorithm in structured plain language — IF … THEN … ELSE, WHILE … DO, FOR … TO — with no language’s syntax. Both are built from three control structures only: sequence, selection and iteration; any algorithm can be expressed with those three.

2. Python: types, operators and control flow

Python’s built-in types are int (unbounded), float, bool, str, and the containers list (mutable, ordered), tuple (immutable), dict (key → value, keys must be hashable) and set. Strings and tuples are immutable: s[0] = "x" raises an error. Assignment binds a name to an object, so after b = a on a list both names refer to the same list, and b.append(4) changes a too; a copy needs a[:] or list(a).

Operators whose results surprise
ExpressionValueWhy
7 / 23.5/ is always true division.
7 // 2, -7 // 23, −4// floors towards −∞, not towards zero.
7 % 3, -7 % 21, 1% takes the sign of the divisor, so a == (a // b) * b + a % b.
the power operator chained as 2, 3, 2512The power operator is right-associative: 2 raised to (3 squared) = 2⁹ = 512, not (2³)² = 64.
1 < 3 < 2FalseChained: 1 < 3 and 3 < 2.
0 or "x", 0 and 5"x", 0and/or short-circuit and return an operand, not True/False.

Selection is if / elif / else; Python 3.10 added match / case for matching a value against patterns, with case _ as the default. while repeats while a condition holds; for iterates over any sequence, and range(a, b) yields a, a + 1, …, b − 1. break leaves the innermost loop; continue skips to its next iteration; a loop’s else block runs only if the loop ended without a break.

🧠 Trace, don’t guess
Write the loop variable and every changing name in columns and step through one iteration per row. For the loop of the third quiz question below — skip multiples of 3, stop at 8, add the rest — the rows give s = 1, 3, 7, 12, 19 and the loop stops at i = 8, so it prints 19.

3. Functions, strings, arrays, dictionaries and recursion

A function is defined with def, returns None if it reaches the end without return, and may take default arguments — evaluated once, when the function is defined, so a mutable default such as def f(x, acc=[]) keeps its contents between calls. Strings index from 0 and from −1 at the end, and slice as s[start:stop:step]: "robot"[::-1] is "tobor", "robot"[1:3] is "ob". Python’s list serves as the dynamic array (the array module and NumPy provide typed ones). A dict looks up by key; d[k] raises KeyError for a missing key while d.get(k, 0) returns 0.

A recursive function calls itself on a smaller input and must reach a base case. Its cost is counted by its calls: for f(n) = f(n − 1) + f(n − 2) with f(0) and f(1) returning directly, the number of calls C(n) = 1 + C(n − 1) + C(n − 2) with C(0) = C(1) = 1 gives C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15 — exponential growth, which memoisation removes. Each call occupies a stack frame, so deep recursion can exceed Python’s recursion limit where a loop would not.

4. Stack, queue and linked list

A stack is last-in, first-out: push and pop at the top, both O(1) — the structure behind function calls, undo, expression evaluation and depth-first search. After push 5, push 8, pop, push 2, push 7, pop, the stack holds 5, 2 with 2 on top. A queue is first-in, first-out: enqueue at the rear, dequeue at the front, used by breadth-first search and task buffers; in Python collections.deque gives O(1) at both ends, whereas list.pop(0) is O(n). A singly linked list stores each element with a pointer to the next: inserting or deleting at the head is O(1), but reaching the kth element is O(k), with no random access.

5. Binary search tree, binary heap and graph

In a binary search tree every key in a node’s left subtree is smaller and every key in its right subtree larger, so an in-order traversal visits the keys in sorted order. Search, insertion and deletion take O(h) for height h — O(log n) when balanced, O(n) in the worst case, when sorted input builds a chain. Inserting 50, 30, 70, 20, 40, 60, 80 builds a perfect tree whose pre-order is 50 30 20 40 70 60 80 and post-order 20 40 30 60 80 70 50.

A binary heap is a complete binary tree stored in an array: with 0-based indexing the children of index i are at 2i + 1 and 2i + 2 and its parent at ⌊(i − 1)/2⌋. In a max-heap each parent is at least its children, so the maximum is at index 0. Insertion appends and sifts up, O(log n); extracting the maximum moves the last element to the root and sifts down, O(log n); building a heap from n items bottom-up is O(n). Inserting 10, 20, 15, 30, 40 into an empty max-heap gives the array [40, 30, 15, 10, 20].

A graph of V vertices and E edges is stored as an adjacency matrix, V × V entries, O(V²) space with O(1) edge lookup, or as adjacency lists, O(V + E) space, better for sparse graphs. Breadth-first search uses a queue and finds shortest paths in edges from the source; depth-first search uses a stack, or recursion, and underlies cycle detection and topological sorting. Both take O(V + E) with adjacency lists.

Key takeaways

  • Flowcharts and pseudo code use only sequence, selection and iteration.
  • // floors towards −∞ and % takes the divisor’s sign; is right-associative; and/or return an operand.
  • Lists are mutable and shared by assignment; strings and tuples are immutable; a loop’s else runs only without break.
  • Stack LIFO, queue FIFO, linked-list head insertion O(1); BST in-order is sorted and its worst case is O(n).
  • Heap children at 2i + 1, 2i + 2; build is O(n), insert and extract O(log n); BFS uses a queue, DFS a stack.

Practice questions (14)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. What does the Python statement print(7 // 2, 7 % 3) output?

    1. 3 1
    2. 3.5 1
    3. 3 2
    4. 4 1
    Show answer

    Answer: A — 3 1

    // is floor division, 7 // 2 = 3; % is the remainder, 7 % 3 = 1. 3.5 is 7 / 2, true division.

  2. In Python, the values of -7 // 2 and -7 % 2 are, respectively:

    1. −4 and 1
    2. −3 and −1
    3. −4 and −1
    4. −3 and 1
    Show answer

    Answer: A — −4 and 1

    // floors towards minus infinity: −3.5 floors to −4. The remainder then follows from a = (a // b) × b + a % b: −7 = (−4)(2) + 1, so it is 1, taking the divisor’s sign. −3 and −1 is what C’s truncating division gives.

  3. What does this Python code print?
    s = 0
    for i in range(1, 10):
        if i % 3 == 0:
            continue
        if i == 8:
            break
        s += i
    print(s)

    Numerical answer — type the value.

    Show answer

    Answer: 19

    i = 1, 2 add to 3; 3 is skipped; 4, 5 bring it to 12; 6 is skipped; 7 brings it to 19; at i = 8 the loop breaks before adding. Treating break like continue would add 8 and then stop at 9, a multiple of 3, printing 27.

  4. def f(n):
        if n <= 1:
            return n
        return f(n - 1) + f(n - 2)
    Counting the initial call, the total number of calls made to f when f(5) is evaluated is ____.

    Numerical answer — type the value.

    Show answer

    Answer: 15

    C(n) = 1 + C(n − 1) + C(n − 2), with C(0) = C(1) = 1: C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 1 + 9 + 5 = 15. The value returned, f(5) = 5, is a different number.

  5. a = [1, 2, 3]
    b = a
    b.append(4)
    print(len(a))
    The output is:

    1. 4
    2. 3
    3. an error, because a was not changed
    4. 7
    Show answer

    Answer: A — 4

    b = a makes b another name for the same list object, so appending through b changes the list a names: its length is 4. A separate copy needs b = a[:] or list(a).

  6. d = {"x": 1, "y": 2}
    d["x"] += 5
    print(d.get("z", 0) + d["x"])
    The output is:

    1. 6
    2. KeyError
    3. 8
    4. 1
    Show answer

    Answer: A — 6

    d["x"] becomes 6; d.get("z", 0) returns the default 0 for the missing key instead of raising KeyError, as d["z"] would; 0 + 6 = 6.

  7. What is the value of "robot"[::-1] in Python?

    1. "tobor"
    2. "robot"
    3. "t"
    4. "obor"
    Show answer

    Answer: A — "tobor"

    A step of −1 with the start and stop omitted walks the whole string backwards. "t" would be s[-1], the last character alone.

  8. for n in [3, 5, 7]:
        if n % 2 == 0:
            break
    else:
        print("none even")
    This code:

    1. prints none even
    2. prints nothing
    3. is a syntax error, since else must follow if
    4. prints none even three times
    Show answer

    Answer: A — prints none even

    A for loop’s else clause runs once when the loop finishes without a break. No element is even, so break never executes and the else prints once. It would print nothing if the list contained an even number.

  9. Starting with an empty stack, the operations push(5), push(8), pop(), push(2), push(7), pop() are performed. The element now on top of the stack is ____.

    Numerical answer — type the value.

    Show answer

    Answer: 2

    After push 5, 8 the stack is [5, 8]; pop removes 8; push 2, 7 gives [5, 2, 7]; pop removes 7, leaving [5, 2] with 2 on top. A queue would have removed 5 and 8 instead.

  10. A binary heap is stored in an array with 0-based indexing. The index of the right child of the node at index 4 is ____.

    Numerical answer — type the value.

    Show answer

    Answer: 10

    Children of i are at 2i + 1 (left) and 2i + 2 (right): 9 and 10. With 1-based indexing the rule is 2i and 2i + 1, which would give 9 for the right child of node 4.

  11. The keys 50, 30, 70, 20, 40, 60, 80 are inserted in that order into an empty binary search tree. Its post-order traversal is:

    1. 20 40 30 60 80 70 50
    2. 20 30 40 50 60 70 80
    3. 50 30 20 40 70 60 80
    4. 80 70 60 50 40 30 20
    Show answer

    Answer: A — 20 40 30 60 80 70 50

    The tree has 50 at the root, 30 (with 20, 40) on the left and 70 (with 60, 80) on the right. Post-order visits left, right, then root at every node: 20 40 30, 60 80 70, 50. The sorted list is the in-order traversal and 50 30 20 40 70 60 80 the pre-order.

  12. The keys 10, 20, 15, 30, 40 are inserted in that order into an initially empty max-heap stored in an array with 0-based indexing, each insertion sifting up. After all five insertions, the element at index 4 is ____.

    Numerical answer — type the value.

    Show answer

    Answer: 20

    10 → [10]; 20 swaps with 10 → [20, 10]; 15 → [20, 10, 15]; 30 at index 3 swaps with 10 then 20 → [30, 20, 15, 10]; 40 at index 4 swaps with 20 (index 1) then 30 → [40, 30, 15, 10, 20]. Index 4 holds 20.

  13. Which statements are true?

    1. Breadth-first search is implemented with a queue
    2. An adjacency matrix for a graph of V vertices needs O(V²) storage
    3. Searching an unbalanced binary search tree of n keys takes O(log n) time in the worst case
    4. Inserting at the head of a singly linked list takes O(1) time
    Show answer

    Answer: A — Breadth-first search is implemented with a queue; B — An adjacency matrix for a graph of V vertices needs O(V²) storage; D — Inserting at the head of a singly linked list takes O(1) time

    (A) BFS visits vertices in order of distance, which a FIFO queue gives. (B) One entry per ordered pair of vertices. (C) False: an unbalanced tree can be a chain of height n, so the worst case is O(n). (D) A new node points to the old head and becomes the head — constant work.

  14. Which statements about Python are true?

    1. Tuples are immutable
    2. Strings are mutable, so s[0] = "x" changes a string in place
    3. Dictionary keys must be hashable, so a list cannot be a key
    4. In x and y, y is not evaluated when x is false
    Show answer

    Answer: A — Tuples are immutable; C — Dictionary keys must be hashable, so a list cannot be a key; D — In x and y, y is not evaluated when x is false

    (A) A tuple’s elements cannot be reassigned. (B) False: strings are immutable, and item assignment raises TypeError; a new string must be built. (C) Keys are located by hash, and a mutable list has none. (D) and short-circuits, returning x itself.