Cse 100

Front 1

A treap is a binary tree

Back 1

TRUE

Front 2

A huffmancode tree is a binary Trie

Back 2

TRUE

Front 3

In Huffman code tree, there are never more internal nodes than leaves

Back 3

TRUE

Front 4

The height of a randomized search tree is always less than 2N, where N is the number of leaves on the tree

Back 4

FALSE

Front 5

In a red a black with N nodes, any path from the root to another node contains no more then 2log2(N+1)

Back 5

TRUE

Front 6

In a red and black tree, every path from the root to a null reference contains the same number of red nodes

Back 6

FALSE

Front 7

considered as a tree, a heap always satisfies the avl balance property

Back 7

TRUE

Front 8

In an AVL, the levels of any two leaves can differ by at most 1

Back 8

FALSE (2)

Front 9

every subtree of a treap is itself a treap

Back 9

TRUE

Front 10

Every subtree of a heap is itself a heap

Back 10

TRUE

Front 11

Every subtree of a AVL tree is itself an AVL tree

Back 11

TRUE

Front 12

Red-black trees and binary heaps have the same big-o worst-case time cost for insert operations

Back 12

TRUE

Front 13

Skip lists and randomized search trees have the same big-O worse-case time cost for find operations

Back 13

TRUE

Front 14

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

Back 14

FALSE

Front 15

An AVL double rotation consist of two AVL single rotations

Back 15

TRUE

Front 16

Any AVL rotation in a BST always produces a BST

Back 16

TRUE

Front 17

The C++ class hierarchy is a tree whose root is the object class

Back 17

FALSE

Front 18

AVL trees are considered to be more difficult to implement than randomized search trees

Back 18

TRUE

Front 19

In C++, an iterator for the std::set container will iterate over the elements in the set in sorted order

Back 19

TRUE

Front 20

because of its writeBit() method, the c++ ofstream class is a good choice when you want to write individual bits to a file

Back 20

FALSE

Front 21

in C++, the end() method of the std::vector class returns an iterator pointing at the last element in the vector

Back 21

FALSE(points at the null space after the last space)

Front 22

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

Back 22

FALSE( no garbage collector)

Front 23

in C++, "*" is a pointer dereference operator

Back 23

TRUE

Front 24

An AVL tree is a balanced binary tree

Back 24

TRUE

Front 25

In a red-black tree, there can be more internal nodes than leaves

Back 25

TRUE

Front 26

The height of a randomized search tree is never more then N, where N is the number of nodes in a tree

Back 26

TRUE

Front 27

In a binary tree with N>0 nodes, there are exactly N-1 non-nulll child pointers

Back 27

TRUE

Front 28

In a red-black tree, every path from the root to a null reference contains the same number of red nodes

Back 28

FALSE (number of white nodes)

Front 29

considered as a binary tree, a heap always satisfies the AVL balance property

Back 29

TRUE

Front 30

Every subtree of a binary search tree is itself a binary search tree

Back 30

TRUE

Front 31

The worst case time cost of finding the successor of a node in a red-black tree with N nodes is O(log N)

Back 31

TRUE

Front 32

Red-black trees and randomized search trees have the same big-O worst case time cost for insert operation

Back 32

FALSE

Front 33

Skip lists and binary search trees have the same big-O worst-case time costs for find operations

Back 33

TRUE

Front 34

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

Back 34

FALSE

Front 35

Any AVL single rotation in a BST preserves the BST ordering property

Back 35

TRUE

Front 36

Any AVL single rotation in a heap preservers the heap ordering property

Back 36

FALSE

Front 37

C++ allows primitive type(such as int) function arguments to be passed by reference

Back 37

TRUE

Front 38

red-black trees are considered to be more difficult to implement than randomized search trees

Back 38

TRUE

Front 39

By default the std::set container uses operation< to perform comparisons between keys

Back 39

TRUE

Front 40

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;}

Back 40

TRUE

Front 41

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;}

Back 41

FALSE

Front 42

in C++, "." is a pointer dereference operator

Back 42

FALSE

Front 43

B-tree's are balanced search trees

Back 43

TRUE

Front 44

B-tree's are binary trees

Back 44

FALSE

Front 45

all B-tree nodes are on the same level

Back 45

TRUE

Front 46

What data structure has the biggest difference between averge-case and worst case find operation time cost

Back 46

Hash table

Front 47

Uses a binary Trie

Back 47

Huffman Code

Front 48

Acts like a pointer in C++

Back 48

Iterator

Front 49

such a problem is intractable (impossible to do on current computers)

Back 49

NP Complete

Front 50

Store nodes in Depth First Search

Back 50

Stack

Front 51

Usually has a fixed MAXLEVEL

Back 51

Skiplist

Front 52

Makes find constant time

Back 52

Path Compression

Front 53

Every Tree is one of these but not every one of these is a tree

Back 53

DAG

Front 54

simulates randomness

Back 54

Linear congruence

Front 55

space efficient for dense graph

Back 55

adjacency matrix

Front 56

Red and black trees are used for this

Back 56

std::map

Front 57

shows whether self adjusting finds are worth it

Back 57

Amortized analysis

Front 58

using in high performance disk filesystems

Back 58

B-tree

Front 59

Randomized search trees randomized this

Back 59

Priority

Front 60

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

Back 60

3

Front 61

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

Back 61

1

Front 62

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

Back 62

4

Front 63

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

Back 63

2

Front 64

The maximum number of distinct symbols codeable with a huffman code tree with 7 nodes is

Back 64

4