Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
64 Cards in this Set
- Front
- Back
A treap is a binary tree
|
TRUE
|
|
A huffmancode tree is a binary Trie
|
TRUE
|
|
In Huffman code tree, there are never more internal nodes than leaves
|
TRUE
|
|
The height of a randomized search tree is always less than 2N, where N is the number of leaves on the tree
|
FALSE
|
|
In a red a black with N nodes, any path from the root to another node contains no more then 2log2(N+1)
|
TRUE
|
|
In a red and black tree, every path from the root to a null reference contains the same number of red nodes
|
FALSE
|
|
considered as a tree, a heap always satisfies the avl balance property
|
TRUE
|
|
In an AVL, the levels of any two leaves can differ by at most 1
|
FALSE (2)
|
|
every subtree of a treap is itself a treap
|
TRUE
|
|
Every subtree of a heap is itself a heap
|
TRUE
|
|
Every subtree of a AVL tree is itself an AVL tree
|
TRUE
|
|
Red-black trees and binary heaps have the same big-o worst-case time cost for insert operations
|
TRUE
|
|
Skip lists and randomized search trees have the same big-O worse-case time cost for find operations
|
TRUE
|
|
In a skip list, the values of the priorities associated with the keys that have been inserted determine which key is in the first node of the list
|
FALSE
|
|
An AVL double rotation consist of two AVL single rotations
|
TRUE
|
|
Any AVL rotation in a BST always produces a BST
|
TRUE
|
|
The C++ class hierarchy is a tree whose root is the object class
|
FALSE
|
|
AVL trees are considered to be more difficult to implement than randomized search trees
|
TRUE
|
|
In C++, an iterator for the std::set container will iterate over the elements in the set in sorted order
|
TRUE
|
|
because of its writeBit() method, the c++ ofstream class is a good choice when you want to write individual bits to a file
|
FALSE
|
|
in C++, the end() method of the std::vector class returns an iterator pointing at the last element in the vector
|
FALSE(points at the null space after the last space)
|
|
in C++, storage for objects created dynamically using new is automatically reclaimed by the grabage collector when the objects can longer be accessed in your program
|
FALSE( no garbage collector)
|
|
in C++, "*" is a pointer dereference operator
|
TRUE
|
|
An AVL tree is a balanced binary tree
|
TRUE
|
|
In a red-black tree, there can be more internal nodes than leaves
|
TRUE
|
|
The height of a randomized search tree is never more then N, where N is the number of nodes in a tree
|
TRUE
|
|
In a binary tree with N>0 nodes, there are exactly N-1 non-nulll child pointers
|
TRUE
|
|
In a red-black tree, every path from the root to a null reference contains the same number of red nodes
|
FALSE (number of white nodes)
|
|
considered as a binary tree, a heap always satisfies the AVL balance property
|
TRUE
|
|
Every subtree of a binary search tree is itself a binary search tree
|
TRUE
|
|
The worst case time cost of finding the successor of a node in a red-black tree with N nodes is O(log N)
|
TRUE
|
|
Red-black trees and randomized search trees have the same big-O worst case time cost for insert operation
|
FALSE
|
|
Skip lists and binary search trees have the same big-O worst-case time costs for find operations
|
TRUE
|
|
In a skip list, the levels of nodes associated with keys that have been inserted determine which key is in the first node of the list
|
FALSE
|
|
Any AVL single rotation in a BST preserves the BST ordering property
|
TRUE
|
|
Any AVL single rotation in a heap preservers the heap ordering property
|
FALSE
|
|
C++ allows primitive type(such as int) function arguments to be passed by reference
|
TRUE
|
|
red-black trees are considered to be more difficult to implement than randomized search trees
|
TRUE
|
|
By default the std::set container uses operation< to perform comparisons between keys
|
TRUE
|
|
Calling the following C++ function creates a string object, and storage for the string object is reclaimed when the functions returns: void f() {std:: string s;}
|
TRUE
|
|
Calling the following C++ function creates a string object, and storage for the string object is reclaimed when the function returns: void f() {std::string* s;}
|
FALSE
|
|
in C++, "." is a pointer dereference operator
|
FALSE
|
|
B-tree's are balanced search trees
|
TRUE
|
|
B-tree's are binary trees
|
FALSE
|
|
all B-tree nodes are on the same level
|
TRUE
|
|
What data structure has the biggest difference between averge-case and worst case find operation time cost
|
Hash table
|
|
Uses a binary Trie
|
Huffman Code
|
|
Acts like a pointer in C++
|
Iterator
|
|
such a problem is intractable (impossible to do on current computers)
|
NP Complete
|
|
Store nodes in Depth First Search
|
Stack
|
|
Usually has a fixed MAXLEVEL
|
Skiplist
|
|
Makes find constant time
|
Path Compression
|
|
Every Tree is one of these but not every one of these is a tree
|
DAG
|
|
simulates randomness
|
Linear congruence
|
|
space efficient for dense graph
|
adjacency matrix
|
|
Red and black trees are used for this
|
std::map
|
|
shows whether self adjusting finds are worth it
|
Amortized analysis
|
|
using in high performance disk filesystems
|
B-tree
|
|
Randomized search trees randomized this
|
Priority
|
|
Suppose T is a completely filled binary search tree with 7 nodes, the worst case number of comparisons for a successful find operation in T is
|
3
|
|
Suppose T is a completely filled binary search tree with 7 nodes. the best case number of comparisons for a successful find operation in T is
|
1
|
|
Suppose T is a binary search tree with 7 nodes, only one of which is a leaf. suppose all keys are equally likely, the integer closest to the average case number of comparisons for a successful find operation in T is
|
4
|
|
suppose T is a completely filled binary search tree with 7 nodes. suppose all keys are equally likely. The integer closest to the average case number of comparisons for a successful find operation in T is
|
2
|
|
The maximum number of distinct symbols codeable with a huffman code tree with 7 nodes is
|
4
|