Education In Pakistan

Papers, Notes, Books & Help For Students

UPDATED EDUCATIONAL NEWS INTERVIEW HELP FOR ALL JOBS ONLINE BOOKS SCHOLARSHIPS AVAILABLE INTERNSHIP JOBS

Tag: VU. CS301 -. DATA. STRUCTURES .(Session – 3 ). MIDTERM .EXAMINATION. FALL .2006

VU CS301 – DATA STRUCTURES (Session – 3 ) MIDTERM EXAMINATION FALL 2006

.

MIDTERM EXAMINATION

FALL 2006 Marks: 40

CS301 – DATA STRUCTURES (Session – 3 ) Time: 60min

StudentID/LoginID: ______________________________

Student Name: ______________________________

Center Name/Code: ______________________________

Exam Date: Wednesday, December 06, 2006

1. Attempt all questions. Marks are written adjacent to each question.

2. Do not ask any questions about the contents of this examination

from anyone.

a. If you think that there is something wrong with any of the

questions, attempt it to the best of your understanding.

b. If you believe that some essential piece of information is

missing, make an appropriate assumption and use it to solve the

problem.

c. Write all steps, missing steps may lead to deduction of marks.

d. All coding questions should be answered using the C++ syntax.

You are allowed to use the Dev-C++ compiler to write and test your code. If

you do so please remember to copy and paste your code into the examination

solution area. (Do NOT share your code; your colleague could get higher

marks than you!!)

**WARNING: Please note that Virtual University takes serious note of

unfair means. Anyone found involved in cheating will get an `F` grade

in this course.

For Teacher’s use only

Question 1 2 3 4 5 6 7 8 9 Total

Marks

Question No: 1 ( Marks: 2 ) – Please choose one

.

The new operation in C++ for dynamically allocating memory returns a pointer to an object it has

just created.

True

False

Question No: 2 ( Marks: 2 ) – Please choose one

A pointer can be declared without giving it a data type to point to

True

False

Question No: 3 ( Marks: 2 ) – Please choose one

An in-order traversal visits nodes in order of descending keys.

True

False

Question No: 4 ( Marks: 2 ) – Please choose one

An unbalanced tree is one whose root has many more left descendents than right descendants.

True

False

.

Question No: 5 ( Marks: 2 ) – Please choose one

A queue allows access to the first item that was inserted.

True

False

Question No: 6 ( Marks: 10 )

Write a function in C++ that will swap the second and third node in a singly linked list (having 5

nodes) by adjusting only the pointers (and not the data). You can use Node class and List class

methods (such as getNext, setNext, next, get) without writing them. You can assume that the Node

class and List class exists, i.e., do not write the code for these classes. The simple declaration of

Node class and List class is as follow,

class Node

{

public:

int get() { return object; };

void set(int object) { this->object = object; };

Node * getNext() { return nextNode; }; //returns the next node pointer

void setNext(Node * nextNode) { this->nextNode = nextNode; }; // set the next

node pointer

private:

int object;

Node * nextNode;

};

/* The List class */

class List

{

public:

List(); // constructor

void add (int addObject); // add the nodes in list

int get(); // returns the value of the current node

bool next(); // returns true if next node exist otherwise returns false

friend void traverse(List list); // used to print the values of all the nodes in the list

void swap();

private:

int size;

Node * headNode;

Node * currentNode;

.

Node * lastCurrentNode;

};

void List ::swap() // Complete this code

{

}

Question No: 7 ( Marks: 5 )

Write the output for the following

Push the characters ‘c’, ‘d’, ‘m’, ‘a’, ‘b’ into the stack in the given order. Pop two elements from

the stack one at a time. Then push two characters ‘f’, and ‘g’. Now pop all the characters. What is

the result?

Question No: 8 ( Marks: 10 )

Convert the infix expression 2+(9-3 *2) to postfix. Show the trace of the algorithm, i.e., the

stack, the infix expression and postfix expression using the following table pattern.

Stack infix postfix

Question No: 9 ( Marks: 5 )

Consider the following binary tree:

(a) Starting from the root node A, perform an In-order traversal of the binary tree below and write

the letters in the nodes that will result during the visitations.

(b) Write the nodes if a Pre-order traversal is performed starting with node A.

.

A

B C

D E

F G

H

Education In Pakistan © 2016