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