CS-211 - DATA STRUCTURES - TEST #1

Name________________________________________

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

You may explain your answers if you choose to.

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

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

- 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? __________

B. On the average how many nodes must be accessed to ADD a node to an UNORDERED linked list? _________

an ORDERED linked list? _________- 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?

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

- 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

- Order the following six
expressions in
*n*such that fi(*n*) = O(fi+1(*n*)) where fi(*n*) is the expression in the i*th*

2^{n} *n *log(*n*) 5*n n*^{2} 3 log(*n*) 2*n*^{2} + 3

1. |
2. |
3. |
4. |
5. |
6. |

- If
*n*is the maximum of the degree of thepolynomial and the degree of the polynomial p, then the average runtime for the following method is O(*this**n*). Under what conditions on*this*and p will the runtime of this algorithm be O(*n*^{2})?

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;

}

**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) {

- 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.

- Show
that ∑ 2i
^{3}= O(n^{4}).

- Determine the following in
simplest terms.

O(N^{3}+ 5*N^{2}- N) = ___________________________________

O(log(N) + N^{1/2}) = ___________________________________

O(N^{2}+ N*log(N)) = ____________________________________

- .

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

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