Data structures worksheet with answers

In a singly linked list, what does the next pointer of the last node contain?

1. AThe number of nodes in the list
2. BNull (no node)
3. CThe address of the previous node
4. DThe address of the first node

How are the elements of an array stored in memory?

1. AIn a tree of memory pages
2. BScattered, linked by pointers
3. CIn random locations chosen by a hash
4. DIn one contiguous block, one after another

What is the root of a tree?

1. AA node with no children
2. BAny node in the middle
3. CThe top node with no parent
4. DThe node with the largest value

What is true of the adjacency matrix of an undirected graph?

1. AIts main diagonal always contains ones
2. BIt is always upper triangular
3. CEach row has exactly one 1
4. DIt is symmetric about the main diagonal

Which data structure does a running program use to keep track of active function calls and their local variables?

1. AA hash table of functions
2. BThe call stack
3. CThe heap memory queue
4. DA binary search tree of frames

Which data structure is used to check whether the brackets in "{[()]}" are balanced?

1. AA binary search tree
2. BA hash table
3. CA queue
4. DA stack

What is the main advantage of a skip list over a sorted linked list?

1. AExpected O(log n) search by using several levels of forward pointers
2. BGuaranteed O(1) search because every node stores a pointer to every other node
3. CIt stores keys without order
4. DIt uses no extra memory

Which data structure supports an LRU (least recently used) cache with O(1) get and put?

1. AA single sorted array
2. BA binary search tree only
3. CA stack only
4. DA hash map combined with a doubly linked list