cs301 data structures

Welcome to Virtually helps.
www.vuhelp.com

Question No. 1 Marks : 02

Queue is the LIFO structure.

o True

o False

Question No. 2 Marks : 02

In binary search tree (BST) every node has two or zero node.

o True

o False

Question No. 3 Marks : 02

In Stack we can access elements from both ends

o True

o False

Question No. 4 Marks : 02

Each node of linked list contains data element and pointer.

o True

o False

Question No. 5 Marks : 02

Every AVL is binary search tree (BST).

o True

o False

Question No. 6 Marks : 15

This question concerns trees containing character data. When two characters need

to be compared, use normal alphabetic comparison, so that for example 'a' < 'g'.

[15 pts]

a) Suppose the characters 'f', 'a', 'r','t', 'z', 'h', 'p', 'e', 'u', 'o' are stored in a

Binary Search Tree (BST). draw a BST that contains these characters.

b) What will be the resulting tree after deleting the 'z', 't', 'h' in the given

sequence.

c) Draw a BST that is as short as possible and contains the characters 'g', 'v',

'q', 'm', 'b'.

Question No. 7 Marks : 10

Insert 55, 35, 57, 25, 37, 56, 41, 39 elements into AVL tree that is initially empty;

perform necessary rotation during insertion of elements. [10 pts]

Question No. 8 Marks : 10

Consider the following class definition for a binary tree of integers. [10

pts]

class binTree {

public:

btnode* root; // root of the bintree

btnode* current; // current node in the bintree

binTree();

bool isEmpty();

int CountInterior(); //count the number of

interior nodes

};

class btnode {

friend binTree;

int value;

binTree left; // left subtree

binTree right; // right subtree

public:

btnode(int value); // Constructor

bool isLeaf(); // True if this node is a leaf;

false otherwise

};

Complete the C++ code that examine whether a tree is complete tree or not.

(A binary tree is strictly binary tree or balance tree or complete tree if its

every node has two children nodes (i.e. left node and right node) or zero

child.)

bool completeTree(BinaryNode * rootNode)

{

}

Question No. 9 Marks : 10

A long sequence of vowels needs to be transmitted efficiently so a programmer

decides to use Huffman encoding to encode the vowels. A distribution count study of

typical data yielded the following frequency table.

[10 pts]

Frequency Table

character frequency Huffman code

A 30676 _ _ _ _ _ _ _

E 45000 _ _ _ _ _ _ _

I 11552 _ _ _ _ _ _ _

O 25814 _ _ _ _ _ _ _

U 10324 _ _ _ _ _ _ _

Y 4975 _ _ _ _ _ _ _

A) Create a Huffman tree to determine the binary codes for each character.

B) Fill the codes into the table above.

Question No. 10 Marks : 10

Using modulo 9 as the hash function "h(x) = x mod 9", show the contents of the hash

table (indexed by 0...10) after the following values are stored in order: 5,11,25,40,

23. Use separate chaining to handle collisions. [10 pts]

Question No. 10 Marks : 15

a. Remove the smallest element from the following array which represents a

min-heap. [15 pts]

b. Draw a min-heap tree of the elements 67, 98, 115, 23, 45.

Contact vuhelps@gmail.com
Regards
Vuhelps