Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures > Data Structures - Test 2 Review > Flashcards

Data Structures - Test 2 Review Flashcards

1
Q

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

A

examples of O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

example of O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

example of O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

example of O(n^1/2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

example of O(lg n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

A hash table is…

A

a fixed size list of records organized to a unique key

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

The key is…

A

usually one of the data fields in the record

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Each cell in the hash table is called a…

A

bucket

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Buckets may be empty - wasting memory

A

true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A collision occurs when…

A

two keys map to the same hash index

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

One way to solve collisions?

A

Chaining

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

O(k)O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Another category of handling collisions is…

A

Open addressing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Open addressing includes…

A

Linear probingQuadratic probingDouble hashing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Double hashing uses…

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

The secondary hash function d(k) cannot have…

A

zero values

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

The table size N must be a…

A

prime to allow probing of all the cells

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

The possible values for d(k) are…

A

1, 2, …, q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

26 mod 11

A

4

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

21 mod 11

A

10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

21 mod 5

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Stack operations… Last In, First Out

A

push, pop, topthese are all O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

stackADT

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

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

A

|| || || 6 |——-

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

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

A

|| || || |——-

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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

A

|| || || 9 |——-

31
Q

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

A

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

32
Q

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

A

|| || || |——-

33
Q

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

A

|| || ||18|——-

34
Q

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

A

|| || || |——-

35
Q

Queue operations… First In, First Out

A

enqueue, dequeue, frontthese are all O(1)

36
Q

queueADT

A

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

37
Q

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

A

simulation

38
Q

A ________ _____ is a restricted form of a list.

A

priority queue

39
Q

In a priority queue…

A

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

40
Q

A priority queue removes items based on…

A

priority

41
Q

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

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

Two types of PQ’s

A

min PQmax PQ

43
Q

Min PQ

A

minimum key value is the highest priority

44
Q

Max PQ

A

maximum key value is the highest priority

45
Q

In either type of PQ, it must hold a…

A

Total Order Relation(reflexive, antisymmetric, transitive)

46
Q

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

A

4, 5, 2, 3, 1

47
Q

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

A

insertItemremoveItem, min/maxKeymin/maxElement

48
Q

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

A

1, 2, 3, 4, 5

49
Q

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

A

insertItemremoveItem, min/maxKeymin/maxElement

50
Q

Queues vs Priority Queues

A

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

51
Q

Priority Queues are useful for…

A

sorting

52
Q

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

A

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

53
Q

8 mod 6

A

2

54
Q

6 mod 6

A

0

55
Q

12 mod 6

A

0

56
Q

10 mod 6

A

4

57
Q

20 mod 6

A

2

58
Q

16 mod 6

A

4

59
Q

What’s the load factor?

A

(num items) / (table size)

60
Q

Main deque operation - insertFirst(object o):

A

inserts element o at the beginning of the deque

61
Q

Main deque operation insertLast(object o):

A

inserts element o at the end of the deque

62
Q

Main deque operation removeFirst():

A

removes and returns the element at the front of the deque

63
Q

Main deque operation removeLast():

A

removes and returns the element at the end of the deque

64
Q

Main deque operation first():

A

returns the element at the front without removing it

65
Q

Main deque operation last():

A

returns the element at the end without removing it

66
Q

Main deque operation size():

A

returns the number of elements stored

67
Q

Main deque operation isEmpty():

A

returns a Boolean value indicating whether no elements are stored

68
Q

Doubly linked list operation insertFront(e):

A

inserts an element on the front of the list

69
Q

Doubly linked list operation removeFront():

A

returns and removes the element at the front of the list

70
Q

Doubly linked list operation insertBack(e):

A

inserts an element on the back of the list

71
Q

Doubly linked list operation removeBack():

A

returns and removes the element at the end of the list

72
Q

7 mod 7

A

0

73
Q

14 mod 7

A

0

Data Structures (14 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions