Basic Data Structures Flashcards
Given an array whose:
- address is 1000,
- element size is 8
- first index is 0
What is the address of the element at index 6?
a)1040
b)1005
c)1048
d)1006
e)40
f)48
Correct: 1000 + 8(6-0) = 1048
Assume you have a three-dimensional array laid out in column-major order with the first element at indices (1, 1, 1). What are the indices of the next element in memory?
a)(2,1,1)
b)(1,1,2)
c)(1,2,1)
(2,1,1)
Correct! In column-major ordering, the first index changes most rapidly.
You have an empty list, and then do the following operations:
PushBack(a)
PushFront(b)
PushBack(d)
PushFront(c)
PopBack()
What is the contents of the list now?
a) c,b,a
b) c,b,a,d
c) a,b,d
Correct! Here are the list contents after each operation;
PushBack(a) -> a
PushFront(b) -> b, a
PushBack(d) -> b, a, d
PushFront(c) -> c, b, a, d
PopBack() -> c, b, a
If we do a PopBack on a list containing the keys (in order) a, b, c, and d, we’ll execute the following part of the code:
p <- head
while p.next.next != nil:
p <- p.next
The loop will start with p pointing to the node containing key a. How many times will the body of the while loop be executed?
In the first test of the condition, p.next.next will be a pointer to the node containing the key c. After the first time the body of the loop is executed, p will point to the node containing the key b. In the second test of the condition, p.next.next will be a pointer to the node containing the key d. After the second time the body of the loop is executed, p will point to the node containing the key c. In the third test of the condition, p.next.next will be nil, so the body of the while loop won’t be executed any more. p will now point to the next-to-last node.
Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.
Given the unbalanced string “()([]”, what character is on the top of the stack when the for loop is finished?
The stack will contain a single value: ‘(‘, The procedure will push the initial ‘(‘, and then pop it off to match the ‘)’. It’ll then push the next ‘(‘, and the ‘[’, and then pop off the ‘[’ to match the ‘]’. What remains will the the ‘(‘.
What would happen if we used List.PushFront to implement Enqueue and List.TopBack and List.PopBack to implement Dequeue? Check all that apply.
a) The queue would work correctly
b) The queue wouldn’t work right
c) The queue would work correctly if the list were singly-linked with a tailed pointer
d) The queue would work correctly if the list were doubly-linked with a tail pointer
e) The queue would work correctly, buy Dequeue would be O(n) time if the list were singly-linked with a tail pointer
f) The queue would work correctly, buy Dequeue would be O(n) time if the list were doubly-linked with a tail pointer
Is Hugh a child of Fred?
Fred
Kate Sally Jim
Sam Hugh
NO. Although Hugh is a descendant of Fred, he is not a direct child. We could say that he is a grandchild.
If we have an expression tree and we want to evaluate that tree in order to compute the value of the expression, we want to evaluate the children before evaluating the arithmetic operator at an internal node. What traversal method does this mean we should use?
Sample expression tree representing (5-3)+(6*2).
+
- *
5 3 6 2
a) Post-order
b) Pre-order
c) In-order
d) Breadth-first
In a post-order traversal, we evaluate all children fully before evaluating a node itself.
Which of the basic data structures is the most suitable if you need to access its elements by their positions in O(1) time (this is called random access)?
a) Array
b) List
c) Queue
d) Stack
Array
Which of the basic data structures is the most suitable if you want to be able to insert elements in the middle in O(1)
a) Array
b) List
c) Queue
d) Stack
List. Inserting an element after an existing element in a list is O(1) , even if it is in the middle of the list.
Which of the basic data structures is the most suitable if you only need to insert the elements in the back and to extract elements from the front?
a) Array
c) Queue
d) Stack
Queue
Which of the basic data structures is the most suitable if you only need to implement recursion in a programming language? When you make a recursive call, you need to save the function you are currently in and its parameters values in some data structure, so that when you go out of the recursion you can restore the state. When you go out of the recursive call, you will always need to extract the last element that was put in the data structure.
a) Stack
b) Queue
You put the function and its parameters values on the stack when you make recursive call, and you remove the top element of the stack when you go out of the recursive call. Stack is LIFO - last in first out, so you will always extract the last element that was put on the stack.
Which of the basic data structures is the most suitable if you need to store the directory structure on your hard drive?
a) Array
b) List
c) Queue
d) Stack
e) Tree
Tree. The directory structure is a tree, so it is good to store it as a tree data structure.
Which is the complexity of PushFront(Key)? why?
O(1)
Which is the complexity of TopFront()? why?
O(1)
Which is the complexity of PopFront()? why?
O(1)
Which is the complexity of PushBack(Key)? why? and with the tail?
O(n) (no tail)
O(1) (with tail)
Which is the complexity of TopBack()? why?
O(n) (no tail)
O(1) (with tail)
Which is the complexity of PopBack()? why?
O(n)
Which is the complexity of Boolean Find(Key)? why?
Which is the complexity of Erase(Key)? why?
O(n)
Which is the complexity of Boolean Empty()? why?
Which is the complexity of AddBefore(Node,Key)? why?
O(n)
Which is the complexity of AddAfter(Node,Key)? why?
O(1)
Define PushFront
add to front
Define TopFront
Return front item
Define PopFront
remove front item
Define PushBack(Key)
add to back
