DOC

# data structure exam

By Jean Spencer,2014-10-16 17:12
12 views 0
data structure exam

CSCI 2320 Data Structure Exam 1

Name:___________________

Question 1.1 (20 pts)

Draw the (1)stack and (2) circular queue data structures in array implementations for “each step” in the following sequence: add(A), remove, add(B), add(C), remove,

add(D), add(E), remove, add(F), add(G). Assume an initial size of 5 for the array

implementation. Remember to show TOP (top of the stack) for stack and both Front and Back for queue. In circular queue implementation, assume we sacrifice one storage space for telling the difference between FULL and EMPTY

STACK:

Circular QUEUE:

Question 2 (10 pts)

Consider the following code, what is the exact output of the following SCROLL

instruction?

#include

#include

using namespace std;

void print_L(vector<int> L)

{

for(int i=0; i

cout<" ";

cout<<"\n";

}

int main()

{

vector<int> L;

L.push_back(10);

L.push_back(20);

print_L(L);

L.push_back(30);

L.erase(L.begin()); 10 20

L.push_back(40); 20 30 40 60

L.push_back(50); 20 30 40 60 70 80

L.pop_back(); 40 60 70

L.push_back(60); 70

print_L(L); 40

L.push_back(70);

L.push_back(80);

print_L(L);

L.erase(L.begin());

L.erase(L.begin());

L.pop_back();

print_L(L);

cout << L.back()<< "\n";

cout << L[0] << "\n";

}

Question3 (20 pts)

Determine the Big O( ) notation for the following:

3231. 8n + 5000n O(n) 4592. 30n( 2n+ 200n) O(n) 2 23533. (n+ n) (10n + 50mn) O(n+ m n) 32324. (0.1 n + 75 k) m O(nm+km) 3345. (m + n)(10kn + 50kn) O(mkn+k n)

Question 4

The Minimum Contiguous Subsequence

Given (possibly negative) integers A1, A2, .., An, find (and identify the sequence

corresponding to) the minimum value of sum of Ak where k = i -> j. The minimum and ndthe 2 minimum contiguous sequence sum is zero if the entire integers are positive.

(Report the minimum subsequence value as well as i and j)

4.1 For the following sequence: {2, -11, 4, -13, 5, -2}, please identify the minimum

subsequence value and i, j. (5 pts)

Min -20

i: 1

j: 3

4.2 Please write the code in C++ for Minimum Contiguous Subsequence, any algorithm is acceptable, but you need to indicate what is your code’s O( ) (15 pts)

2My algorithm is a O ( n ) algorithm

int minSubsequenceSum(int a[]){

int n = a.size();

int minSum = 0;

for( int i = 0; i < n; i++){

int thisSum = 0;

for( int j = i; j < n; j++){

thisSum += a[j];

if( thisSum < minSum){

minSum = thisSum;

seqStart = i;

seqEnd = j;

}

}

}

return minSum;

}

Question 5 (15 pts)

Given a table looks like below, please reconstruct the corresponding tree:

Depth Size Height NODE

2 1 0 2

1 4 3 3

2 3 2 4

1 1 0 5

2 1 0 6

3 2 1 7

4 1 0 8

1 3 1 9

0 9 4 10

Question 6 (15 pts)

Please Show the different traversal output on the following tree:

6.1 Inorder---

13 2 4 * 1 + 7 5 9

6.2 Postorder---

13 4 2 1 * 9 5 7 +

6.3 What’s the result of “Breadth First Search (BFS)”?

+ * 7 1 5 13 2 9 4

Bonus Question 7: (5 pts)

The following code is for non-recursive inorder traversal: Stack S

Initialize all nodes to white

push root onto S

repeat until S is empty

v = pop S

If v is black

visit v

else if v is not NULL

push v’s right child onto S

change v to black

push (black) v onto S

push v’s left child onto S

Based on the above code, please write a code for non-recursive postorder traversal:

Stack S

Initialize all nodes to white

push root onto S

repeat until S is empty

v = pop S

If v is black

visit v

else if v is not NULL

change v to black

push (black) v onto S

push v’s right child onto S

push v’s left child onto S

Report this document

For any questions or suggestions please email
cust-service@docsford.com