CS-211 - DATA STRUCTURES - TEST #1

Name________________________________________

If you have trouble with a question, skip it and come back to it later.

1. Evaluate the following postfix expression: 6 1 6 5 - + * 12 4 / /

2. Give formulas in terms of N where N is the number of elements in the list.

1. On the average how many nodes must be accessed to FIND a particular value in an UNORDERED linked list if the value is in the list? _______
if the value is not in the list? ________
in an ORDERED linked list if the value is in the list? __________
if the value is not in the list? __________

2. B. On the average how many nodes must be accessed to ADD a node to an UNORDERED linked list? _________
3. Explain why a program that solves a game such as a maze using a queue might find a different solution than one using a stack

What would be the probable difference in the solutions?

1. Explain why binary search on a doubly-linked list is no faster than searching the list from one end to another.

1. An upper triangular matrix is an NXN matrix in which all the entries below the diagonal are zero.

Design a data structure UpperDiagonalMatrix, which stores this efficiently  and implement as a C++ class along a function that sets and gets values at location  i, j in matrix

1. Order the following six expressions in n such that fi(n) = O(fi+1(n)) where fi(n) is the expression in the ith box.

2n            n log(n)            5n        n2           3 log(n)                        2n2 + 3

 1 2 3 4 5 6

1. If n is the maximum of the degree of the this polynomial and the degree of the polynomial p, then the average runtime for the following method is O( n ). Under what conditions on this and p will the runtime of this algorithm be O( n2 )?

where

x.getDegree() returns the exponent of the highest order term

x.getCoefficient(i) returns the coefficient of the term whose exponent is i.

public Polynomial add( polynomial p ) {

Polynomial q = new PolynomialAsArray();

Polynomial min, max;

if ( p.getDegree() > this.getDegree() ) {

max = p;

min = this;

} else {

max = this;

min = p;

}

for ( int i = max.getDegree(); i >= 0; i-- ) {

q.setCoefficient( i, max.getCoefficient(i) );

}

for ( int i = min.getDegree(); i >= 0; i-- ) {

q.setCoefficient( i, min.getCoefficient(i) + q.getCoefficient(i));

}

return q;

}

1. addBottom is a methods of the MyStack class and takes 1 parameter, I, an integer. addBottom adds the integer I to the bottom of the stack.

Write C++ code for addBottom using the methods isEmpty(), pop() and push(x) and ordinary C++ comparison operations. addBottom does not need and should not use any knowledge about the implementation of myStack.

`bool`` MyStack::addBottom(int I) {`

1. An abstract data type describes an idea. That idea can be implemented in many different ways. In class, we have seen how various abstract data type may be implemented using arrays and linked lists. In some cases, though, some of the weaknesses of arrays and linked lists may not apply.

a. Normally, withdrawing an object from a linked list is an O(n) operation, where n is the number of objects in the linked list. Give one condition where withdrawing an object from a linked list is an O(1) operation.

b. Normally, given a cursor pointing into an array-based implementation, inserting after the cursor is an O(n) operation. Give one condition on the position cursor for which inserting after the cursor an O(1) operation.

1.  Show that   ∑ 2i3 = O(n4).

1. Determine the following in simplest terms.
O(N3 + 5*N2 - N)        = ___________________________________

O(log(N) + N1/2)          = ___________________________________

O(N2 + N*log(N))       = ____________________________________

1. .
1. Evaluate the following recurrence:  T(n) = 3T(n/2) + n and give big-O

1. Give an example of psuedocode for problem that has above behavior (of part a).