ADS Logs

An array-list wraps a plain array and resizes it automatically; an add into a free slot is $O(1)$, but an add into a full array first copies every element into a bigger one, which is $O(n)$. * The fourth add fits; the fifth finds the array full and pays for copying all four firs...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Oct 13, 2026

An algorithm is a step-by-step instruction that solves a problem in bounded time; its cost is measured by counting primitive operations — the small steps whose duration does not depend on the input size. The definition carries a requirement that is easy to read past: bounded time...

Quiz: ADS / Asymptotic Analysis, O-Notation and Recursion | updated: Oct 13, 2026

Each node stores a reference to its predecessor (prev) as well as its successor (next), so the list can be walked and edited in both directions; the price is one extra reference per node. * Every link has a partner in the opposite direction, so any node can reach both neighbours...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

An ADT describes a data structure by what it does, not how: it specifies the data it stores, the operations on that data, and the error conditions of those operations, while leaving the implementation open. An ADT specification has three parts: Data — what is stored (the attribu...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

dequeue() → 5, dequeue() → 3, first() → 7, dequeue() → 7, and the last dequeue() → null because the queue is empty. * dequeue always takes the oldest element still waiting. * Operation Returns Queue (front … rear) enqueue(5) — (5) enqueue(3) — (5, 3) dequeue() 5 (3)...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

Ancestors are a node's parent, grandparent and so on up to the root; descendants are its children, grandchildren and so on; siblings share the same parent; a subtree is a node together with all of its descendants. Take the tree where A has children B, C, D; B has children E, F; a...

Quiz: ADS / Trees: Structure, Storage and Traversals | updated: Sep 29, 2026

Each node stores four references: its element, its parent, its left child and its right child. The general tree's sequence of children is replaced by exactly two fixed fields. * Solid arrows point down to the children, dashed ones back up to the parent; ∅ marks a missing child....

Quiz: ADS / Trees: Structure, Storage and Traversals | updated: Sep 29, 2026

Preorder A B D E C F · inorder D B E A C F · postorder D E B F C A · breadth-first A B C D E F. * C has only a right child, so F comes after C in inorder. * * Same tree, four orders; the leaves D, E, F keep their relative order in the first three. * Work each one out from its r...

Quiz: ADS / Trees: Structure, Storage and Traversals | updated: Sep 29, 2026

Two dummy nodes that hold no element and permanently sit before the first and after the last real node; because every real node then always has a real predecessor and successor, insertion and removal need no special cases for an empty list or the ends. Without sentinels, head and...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

A stack stores objects in last-in, first-out (LIFO) order: push(o) puts an element on top, pop() removes and returns the top element. Helper operations are top() (look without removing), size() and isEmpty(). Picture a stack of plates: you can only put a plate on top and only tak...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026