|
MIDTERM EXAMINATION
FALL 2006
CS301 - DATA STRUCTURES (Session - 3 )
Marks: 40
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.
http://ping.fm/ZadkX
FALL 2006
CS301 - DATA STRUCTURES (Session - 3 )
Marks: 40
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.
http://ping.fm/ZadkX