CS $2413-$ Data Structures $-$ Exam $1-$ Sample

$(6$ Points$)$ For the following infix expressions, give the postfix expression.

a$)\frac{a}{b}-c+d^{**}e-a**c$

b$)(\frac{a}{b-c+d}{)}^{**}(e-a{)}^{**}c$

$(8$ Points$)$ Write an algorithm to evaluate a postfix expression

$(8$ Points$)$ Write the C$++$ class definition for a stack data structure that is based on an array.

Ensure that your class is templated.

$(4$ Points$)$ Give two advantages of an array implementation of a stack over a linked list implementation of a stack.

$($b$)$ Write the copy constructor the linked list class.

$7.(10$ Points$)$ Write a non$-$recursive algorithm to perform binary search on an array A$.$

$8.(4$ Points$)$ What is the time$-$complexity of binary search?

$9.(4$ Points$)$ Given the following sorted set of integers, the number of comparisons that are made to locate the integer $100$ using the Binary Search is:

$10,20,60,90,100,120,140,180,200,300,350$

$(10$ Point$)$ How many ways a matrix can stored? Describe each one.

$(5$ Points$)$ Write the formal definition of big$-$oh$.$

$(6$ Points$)$ Given the following program in C$++,$ how many times is the copy constructor

called and the Destructor is called Assume that there is a Point class that was already

created.

Point& createAPoint $($Point one$)\{$

Point$*$ X $=$ new Point $($one$)$;

return $*$X;

$\}$

int main $()\{$

Point Z $(10,20)$;

Point Y $=$ createAPoint $($Z$)$;

$\}$

$(5$ Points$)$ What will be the object declaration for a variable called $x($based on the below

diagram$)$ using type ArrayClass and using templates for storing integer elements?

$(10$ Points$)$ What is the best and the worst case for a vector insert operation? Given the

vector is of length $n$ and there are $n-1$ elements already present?