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
Define TopBack()
return back item
Define PopBack()
remove back item
Define Find(Key)
is key in list?
Define Erase(Key)
remove key from list
Define Empty()
empty list?
Define AddBefore(Node, Key)
adds key before node
Define AddAfte(Node, Key)
adds key after node
Which is the complexity of Adding at the beginning, middle and end in an array? why?
Add:
O(n) Beginning
O(n) Middle
O(1) End
Which is the complexity of Remove at the beginning, middle and end in an array? why?
Remove:
O(n) Beginning
O(n) Middle
O(1) End
Which is the complexity of PushFront(Key) in a Doubly-Linked list? why?
O(1)
Which is the complexity of TopFront() in a Doubly-Linked list? why?
O(1)
Which is the complexity of PopFront() in a Doubly-Linked list? why?
O(1)
Which is the complexity of PushBack(Key) in a Doubly-Linked list? why? and with a tail?
O(n) (no tail)
O(1) (with tail)
Which is the complexity of TopBack() in a Doubly-Linked list? why?
O(n) (no tail)
O(1) (with tail)
Which is the complexity of PopBack() in a Doubly-Linked list? why?
O(1) and that is the benefit of a doubly-linked list over a singly-linked list
Which is the complexity of Find(Key) in a Doubly-Linked list? why?
O(n)
Which is the complexity of Erase(Key) in a Doubly-Linked list? why?
O(n)
Which is the complexity of Empty(Key) in a Doubly-Linked list? why?
O(1)
Which is the complexity of AddBefore(Node, Key) in a Doubly-Linked list? why?
O(1)
Which is the complexity of AddAfter(Node, Key) in a Doubly-Linked list? why?
O(1)
Define Stack
Abstract data type with three properties:
1-Push(Key)
2-Key top()
3-Key Pop()
What does Push(key) do?
adds key to collection
What does Key Top() do?
returns most recently-added key
What does Key Pop() do?
removes and returns most recently-added key
Stacks are FIFO?
no, is LIFO (Last In First Out)
Complexity of Push, Pop, Top, Empty
O(1)
What is the benefit of implementing a Stack with a linked-list instead of with an array?
There’s no wasted space, you can keep adding elements to the list. The array has a fixed amount of available memory space
Main benefits of doubly linked-list
1-Constant time to insert/remove from the front
2-doubly-linked list with tail O(1) to insert/remove from the back
3- O(n) time arbitrary element
4-List of elements needs not be contiguous
Define Queue
Abstract data type with the following properties:
1-Enqueue(Key)
2-Key Dequeue()
3-Boolean Empty()
Defines Enqueue(Key)
Adds key to collection
Defines Dequeue()
removes and returns least recently-added key
Defines Boolean Empty()
are there any elements?
Queue is FIFO?
First-In, First-Out
Can a queue be implemented without a tail pointer?
Complexity of Enqueue, Dequeue, Empty
O(1)
Define Root of a tree
top node in the tree
Define Child of a tree
has a line down directly from a parent
Define Ancestor of a tree
Parent, or parent of parent, etc
Define Descendant of a tree
child, or child of child, etc
Define Sibling of a tree
sharing the same parent
Define Leaf of a tree
no with no children
Define Interior node of a tree
non-leaf
