Fichas
DSA Lecture 3
Fichas del conjunto (54)
- 1What is a tree and what does it consist of?A tree is an abstract model of a hierarchical structure.
It consists of nodes with a parent-child relation. - 2What are the 3 applications of a tree?Organization charts
File systems
Programming environments - 3What are the 8 types of node terminology? Describe them.Root: node without a parent
Descendant of a node: child, grandchild...
Internal node: node with at least 1 child
External node: node with 0 children
Ancestors: nodes that are parents, grandp
Depth of a node: number of ancestors
Height of a tree: maximum depth
Subtree: tree consisting of node + descendants - 4Accessor methods of Tree ADTroot()
parent()
children() - 5Query methods of Tree ADTisInternal()
isExternal()
isRoot() - 6Update methods of Tree ADTswapElements()
replaceElement() - 7Give 2 functions of Pre-order TraversalVisits nodes of a tree in symmetrical manner,
A node is visited BEFORE its descendants - 8Give an application of pre-order traversalPrinting a structured document
- 9Give a function of Post-order TraversalA node is visited AFTER its descendants
- 10Application of post-order traversalComputing space used by files in a directory and its sub-directories
- 11Properties of a binary treeEach internal node has two children,
Children of a node are an ordered pair. - 12Applications of binary treesArithmetic expressions,
decision processes,
searching. - 13What is an arithmetic expression tree?Binary tree associated with an arithmetic expression
- 14What is a decision tree?Binary tree associated with a decision process
- 15Pseudocode for in-order traversalAlgorithm inOrder(v){
if isInternal(v)
inOrder(leftChild(v))
visit(v)
if isInternal(v)
inOrder(rightChild(v)) - 16Features of Euler Tour TraversalGeneral traversal of binary tree,
walks around tree and visits each node 3 times - 17What is a node represented by?An object storing:
Element
Parent node
Left + Right children nodes - 18What do Node objects implement?Position ADT
- 19What is a priority queue?A queue that stores a collection of items
- 20What is an item in this context?A pair (key, element)
- 21What are the main methods of a PriorityQueue ADT? Explain them.insertItem(k,o) --- inserts an item with key k and element o
removeMin() --- removes item with smallest key and returns its element - 22What can two distinct items in a priority queue have?The same key
- 23What are the 4 properties of the mathematical concept of total order relation?Reflexive property: x <= x
Antisymmetric property: x<=y ^ y<=x --> x=y
Transitive property: x<=y ^ y<=z --> x<=z
Total:
x<=y OR y<=x - 24What does a Comparator do?Encapsulates the action of comparing two objects according to a given total order relation
- 25What does a generic priority queue use/An auxiliary comparator
- 26When is a comparator used in a priority queue?When two keys need to be compared
- 27What are the 6 Comparator methods?isLessThan(x,y)
isLessThanOrEqualTo(x,y)
isEqualTo(x,y)
isGreaterThan(x,y)
isGreaterThanOrEqualTo(x,y)
isComparable(x,y) - 28What do the Comparator methods have in common?They all have a Boolean return type
- 29How does sorting with a priority queue work?1. Insert the elements one by one with a series of insertItem(e,e) operations
2. Remove the elements in sorted order with a series of removeMin() operations - 30What does the running time of the sorting method depend on?The priority queue implementation
- 31Try to write the entire pseudocode for PriorityQueue-Sorting.Include input, output and necessary methods.
- 32What will the performance be in an unsorted list?insertItem --> O(1)
removeMin, minKey, minElement --> O(n) - 33What will the performance be in a sorted list?insertItem --> O(n)
removeMin, minKey, minElement --> O(1) - 34What is Selection-Sort?Same as PQ-sort, but the priority queue is implemented with an unsorted sequence
- 35What is the running time of selection-sort/O(n^2)
- 36What is insertion-sort?Same as PQ-sort, but implemented with a sorted sequence
- 37What is the running time of insertion sort?O(n^2)
- 38What is a Heap?A binary tree storing keys at its internal nodes and satisfying Heap-Order (key(v) >= key(parent(v)) and Complete Binary Tree
- 39What are the properties of a Complete Binary Tree?h = height of heap
for i=0; h-1, there are 2^i nodes of depth i
at depth h-1, internal nodes are to the left of the external nodes
Last node of a heap is the rightmost internal node of depth h-1 - 40What is the height of the heap?h <= logn+1
(n = amount of keys) - 41How do we use a heap to implement a priority queue?Store a (key, element) item at each internal node,
keep track of position of the last node. - 42What are the 3 steps of the insertion algorithm of inserting into a heap?Find insertion node z (new last node)
Store k at z and expand z into an internal node
Restore the heap-order property - 43What does Upheap do?Restores heap-order property by swapping k along an upward path from the insertion node.
Terminates when key k reaches root of a node whose parent has a key <= k - 44What's upheap's running time?O(log n)
- 45What 3 steps does the removal algorithm consist of?1. Repace root key with key of last node w
2. Compress w and its children into a leaf
3. Restore heap-order property with downheap - 46How do you update the last node?Go up until a left child or root is reached,
If left child = reached, go to sibling (right child)
Go down left until leaf = reached - 47What are the running times of heap sort and its methods?Space used --- O(n)
insertItem + removeMin --> O(log n)
size, isEmpty, minKey, minElemtn --> O(1) - 48What can you sort in O( n log n) time with heap sort?Sequence of n elements
- 49How do you merge two heaps?Create a new heap with the root node storing key k and with two heaps as subtrees,
Perform downheap to restore heap-order property - 50Look at example of this in 3b slidesk
- 51What is the worst case for heap-sort?When every downheap reaches bottom of tree
- 52What type of construction is faster?Bottom-up heap
- 53What does bottom-up heap construction run in?O(n) time
- 54DO THE HOMEWORKSK
Información
- Descripción
- Fichas sobre DSA Lecture 3, creado por krisbraz el 20/03/2015.
- Creado por
- krisbraz
- Visitas
- 0
- Valoración