Data Structures - Test 2 Review

Question 1

cout &laquo_space;value int sum = 0; if (count < 20) { total = total + current; area = (1.0 / 2.0) * base * height;

Answer 1

examples of O(1)

Question 2

“for (int j = 1; j<= n; j++) { cout &laquo_space;"”this prints n times”” &laquo_space;endl; }”

Answer 2

example of O(n)

Question 3

“for (int j = 1; j<= n; j++) { for (int k = 1; k<= n; k++) { cout &laquo_space;"”this prints n^2 times”” &laquo_space;endl; } }”

Answer 3

example of O(n^2)

Question 4

“for (int j = 1; j<= sqrt(n); j++) { cout &laquo_space;"”this prints sqrt(n) times”” &laquo_space;endl; }”

Answer 4

example of O(n^1/2)

Question 5

“for (int j = n; j> 0; j /= 2) { cout &laquo_space;"”this prints lg n times”” &laquo_space;endl; }”

Answer 5

example of O(lg n)

Question 6

A hash table is…

Answer 6

a fixed size list of records organized to a unique key

Question 7

The key is…

Answer 7

usually one of the data fields in the record

Question 8

Each cell in the hash table is called a…

Answer 8

bucket

Question 9

Buckets may be empty - wasting memory

Answer 9

true

Question 10

The hash function maps the record’s key to an integer called the…

Answer 10

hash index(this indicates into which bucket to put the record)

Question 11

If every key maps to a unique hash index, then the hash table operations are fast

Answer 11

Search, Insert, and Delete are all O(1)

Question 12

A collision occurs when…

Answer 12

two keys map to the same hash index

Question 13

One way to solve collisions?

Answer 13

Chaining

Question 14

Let k = max # of records stored in one bucket. If using vectors then: Search and Delete are… Insert is…

Answer 14

O(k)O(1)

Question 15

Another category of handling collisions is…

Answer 15

Open addressing

Question 16

Open addressing includes…

Answer 16

Linear probingQuadratic probingDouble hashing

Question 17

Double hashing uses…

Answer 17

a secondary hash function d(k) and handles collisions by placing an item in the first available cell of the seriesh(k,i) = (h(k) + i*d(k)) mod Nfor i = 0, 1, …, N - 1

Question 18

The secondary hash function d(k) cannot have…

Answer 18

zero values

Question 19

The table size N must be a…

Answer 19

prime to allow probing of all the cells

Question 20

Common choice of compression map for the secondary hash function:…

Answer 20

d(k) = q - (k mod q)where:q < Nq is a prime

Question 21

The possible values for d(k) are…

Answer 21

1, 2, …, q

Question 22

26 mod 11

Answer 22

4

Question 23

21 mod 11

Answer 23

10

Question 24

21 mod 5

Answer 24

1

Question 25

Stack operations... Last In, First Out

Answer 25

push, pop, topthese are all O(1)

Question 26

stackADT

Answer 26

+ push(Type Item) : void+ pop() : void+ top() : Type+ size() : int+ empty() : bool

Question 27

Expression: 6 3 + 2 * = Push 6 into stack

Answer 27

| || || || 6 |-------

Question 28

Expression: 6 3 + 2 * = Push 3 into stack

Answer 28

| || || 3 || 6 |-------

Question 29

Expression: 6 3 + 2 * = + Pop stack twice op2 = 3; op1 = 6;

Answer 29

| || || || |-------

Question 30

Expression: 6 3 + 2 * = op1 + op2 = 9 Push 9 into stack

Answer 30

| || || || 9 |-------

Question 31

Expression: 6 3 + 2 * = Push 2 into stack

Answer 31

| || || 2 || 9 |-------

Question 32

Expression: 6 3 + 2 * = * Pop stack twice op2 = 2; op1 = 9;

Answer 32

| || || || |-------

Question 33

Expression: 6 3 + 2 * = op1 + op2 = 18 Push 18 into stack

Answer 33

| || || ||18|-------

Question 34

Expression: 6 3 + 2 * = = Pop stack and print: 18

Answer 34

| || || || |-------

Question 35

Queue operations... First In, First Out

Answer 35

enqueue, dequeue, frontthese are all O(1)

Question 36

queueADT

Answer 36

+ enqueue(Type Item)+ dequeue()+ front() :Type+ rear() :Type

Question 37

A technique in which one system models the behavior of another system is called...

Answer 37

simulation

Question 38

A ________ _____ is a restricted form of a list.

Answer 38

priority queue

Question 39

In a priority queue...

Answer 39

items are arranged according to their priorities (or keys)the keys may or may not be uniqueunlike a queue which is FIFO

Question 40

A priority queue removes items based on...

Answer 40

priority

Question 41

Each item in a PQ is a composition of 2 objects:

Answer 41

- the key (priority)- the datathis gives us a pair (key, data)which we can use to implement using a linked list

Question 42

Two types of PQ's

Answer 42

min PQmax PQ

Question 43

Min PQ

Answer 43

minimum key value is the highest priority

Question 44

Max PQ

Answer 44

maximum key value is the highest priority

Question 45

In either type of PQ, it must hold a...

Answer 45

Total Order Relation(reflexive, antisymmetric, transitive)

Question 46

Implementation: Priority Queue Unsorted list implementation: store the items of the priority queue in a list-based sequence, in arbitrary order

Answer 46

4, 5, 2, 3, 1

Question 47

Implementation: Priority Queue Unsorted list implementation Performance: _______ takes O(1) time since we can insert the item at the beginning or end of the sequence _______, _______ and _______ take O(n) time since we have to traverse the entire sequence to find the smallest key

Answer 47

insertItemremoveItem, min/maxKeymin/maxElement

Question 48

Implementation: Priority Queue Sorted list implementation: store the items of the priority queue in a sequence, sorted by key

Answer 48

1, 2, 3, 4, 5

Question 49

Implementation: Priority Queue Sorted list implementation Performance: _______ takes O(n) time since we have to find the place where to insert the item _______, _______, and _______ take O(1) time since the smallest key is at the beginning of the sequence

Answer 49

insertItemremoveItem, min/maxKeymin/maxElement

Question 50

Queues vs Priority Queues

Answer 50

Queue: structure ensures items processed in the order receivedPriority queues: customers (jobs) with higher priority pushed to the front of the queue

Question 51

Priority Queues are useful for...

Answer 51

sorting

Question 52

Sorting using a priority queue: Given a sequence of N items, a PQ can be used to sort the sequence:

Answer 52

Step 1: Insert N items into the PQ via insertItem (key, data)Step 2: Remove the items by calling removeItem() N timesthe first removes the largest item, the second call the second largest, ..., the last removes the smallest item

Question 53

8 mod 6

Answer 53

2

Question 54

6 mod 6

Answer 54

0

Question 55

12 mod 6

Answer 55

0

Question 56

10 mod 6

Answer 56

4

Question 57

20 mod 6

Answer 57

2

Question 58

16 mod 6

Answer 58

4

Question 59

What's the load factor?

Answer 59

(num items) / (table size)

Question 60

Main deque operation - insertFirst(object o):

Answer 60

inserts element o at the beginning of the deque

Question 61

Main deque operation insertLast(object o):

Answer 61

inserts element o at the end of the deque

Question 62

Main deque operation removeFirst():

Answer 62

removes and returns the element at the front of the deque

Question 63

Main deque operation removeLast():

Answer 63

removes and returns the element at the end of the deque

Question 64

Main deque operation first():

Answer 64

returns the element at the front without removing it

Question 65

Main deque operation last():

Answer 65

returns the element at the end without removing it

Question 66

Main deque operation size():

Answer 66

returns the number of elements stored

Question 67

Main deque operation isEmpty():

Answer 67

returns a Boolean value indicating whether no elements are stored

Question 68

Doubly linked list operation insertFront(e):

Answer 68

inserts an element on the front of the list

Question 69

Doubly linked list operation removeFront():

Answer 69

returns and removes the element at the front of the list

Question 70

Doubly linked list operation insertBack(e):

Answer 70

inserts an element on the back of the list

Question 71

Doubly linked list operation removeBack():

Answer 71

returns and removes the element at the end of the list

Question 72

7 mod 7

Answer 72

0

Question 73

14 mod 7

Answer 73

0