Practice questions
Q1Which advantage is normally associated with an array over a singly linked list?
A Direct access to the i-th element using its index is efficient.
B Insertion at the beginning is always done without moving or changing any links.
C It can grow indefinitely without reallocation when capacity is full.
D Memory for every element is allocated only when that individual element is inserted.
Explanation Arrays support efficient random access because the location of element i follows from the base address and element size. A singly linked list must traverse nodes sequentially to reach the same position.
Q2For representing a sparse graph, which representation is usually more space-efficient than an adjacency matrix?
A Adjacency list
B Two-dimensional array with one cell for every possible pair of vertices
C Complete binary tree representation
D Single integer counter for number of vertices only
Explanation A sparse graph has relatively few edges compared with the number of possible vertex pairs. An adjacency list records only existing neighbour relationships, whereas an adjacency matrix allocates a cell for every possible pair.
Q3Which condition must hold in a binary search tree for every node?
A All leaf nodes must be stored in a separate array.
B All keys in the left subtree are smaller and all keys in the right subtree are larger than the node key.
C Every internal node must have exactly two children.
D The root key must always be the smallest key in the tree.
Explanation The binary search tree property orders keys around each node: smaller keys go to the left subtree and larger keys go to the right subtree. This ordering allows search to choose one branch at each comparison.
Q4In C, why can an array element a[i] be accessed in constant time when the base address and element size are known?
A Because arrays store every element in a separate randomly chosen block.
B Because every array element stores the address of the next element.
C Because the address is computed directly as base address plus index multiplied by element size.
D Because the array is always sorted before access.
Explanation An array occupies contiguous memory locations for elements of the same size. Therefore the address of a[i] can be computed using the base address and an offset, without scanning earlier elements.
Q5Which statement best describes an Abstract Data Type (ADT) in data structures?
A It specifies data values and operations without fixing a particular implementation.
B It is a sorting method used only for numeric arrays.
C It is always a C structure declared with the keyword struct.
D It stores values only in contiguous memory locations.
Explanation An ADT focuses on what operations are available and what they mean, such as push and pop for a stack. It deliberately separates the logical interface from implementation choices like arrays, linked lists, C structs, or C++ classes.
More questions
6Which comparison between a linked list and an array is generally correct for basic storage?
AA linked list always gives faster random indexing than an array.
BAn array stores each element with a link to the next element.
CA linked list can grow by connecting nodes, while an array is usually better for direct indexed access.
DBoth structures require all elements to be stored contiguously in memory.
7Which statement about searching and sorting is correct?
ALinear search requires the data to be sorted before checking the first element.
BSorting arranges records in a chosen order, and binary search requires sorted data.
CBinary search can be applied directly to any unsorted array.
DA symbol table stores only arithmetic operators and cannot store identifiers.
8In an array, why is accessing A[i] usually faster than searching for an item in an unsorted linked list?
ABecause the index lets the program compute the element position directly.
BBecause array insertion at the beginning is always constant time.
CBecause arrays automatically keep all elements in sorted order.
DBecause linked lists cannot store more than one data item.
9Which C++ Standard Library container is most directly suitable for implementing a key-value symbol table with unique keys?
Astd::stack
Bstd::map
Cstd::bitset
Dstd::queue
10In a queue, insertion and deletion are normally performed at which ends?
AInsertion at rear and deletion at front
BInsertion at middle and deletion at middle
CInsertion at rear and deletion at rear
DInsertion at front and deletion at front
11For a graph with n vertices, which representation uses an n x n table to show whether an edge exists between two vertices?
AAdjacency matrix
BAdjacency list
CLinked stack
DSymbol table
12Which statement best describes an abstract data type (ADT)?
AIt is always a physical memory layout chosen by the compiler.
BIt is a C++ header file containing ready-made classes only.
CIt specifies a set of values and operations without fixing the implementation.
DIt is a sorting method used only for numeric arrays.
13Which condition is true for every node in a binary search tree with distinct keys?
AThe left subtree has smaller keys and the right subtree has larger keys.
BAll nodes must have exactly two children.
CThe left subtree contains only keys greater than the node's key.
DThe right subtree contains only keys smaller than the node's key.
14If values 10, 20 and 30 are pushed in this order on an initially empty stack, which value is returned by the first pop operation?
A10
B30
CNo value, because pop is not allowed after push
D20
15In data structures, which statement best describes an abstract data type (ADT)?
AIt is a compiler rule for converting source code into object code.
BIt is always a C structure stored in contiguous memory.
CIt is a sorting method used only for arrays.
DIt specifies the logical behaviour and operations of data, without fixing the implementation.
