# Data Structures: CS301 Midterm Solved Papers(Mega File)

## CS301- Data Structures Midterm Past Papers(Subjective)

#### Q:1 What is complete binary tree?

Answer: “A complete binary tree is a binary tree with the additional property that every node must have exactly two children if an internal node, and zero children if a leaf node.”

#### Q:2 How single left rotation is performed in AVL tree?

Answer: This rotation is almost similar to the single right rotation. We start from tree node k1. k1 is the root whilet ree node k2 is its right child. Due to the left rotation, the right child k2 of the root k1 will become the root. The k1 will go down to the left child of k2.

#### Q:3 describe the following (i) Height of tree (ii) Balance of Node (i) Height of tree

Answer: The height of a binary tree is the maximum level of its leaves (also called the depth). (ii) Balance of Node Answer: (page 215) The balance of a node in a binary search tree is defined as the height of its left subtree minus height of its right subtree. In other words, at a particular node, the difference in heights of its left and right subtree gives the balance of the node.

#### Q4. what is binary tree brief it?

Answer:- “A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub-trees”.

#### Q5.what is different between binary tree and AVL tree.

Answer:- An AVL tree is identical to a BST, barring the following possible differences:
 Height of the left and right subtrees may differ by at most 1.
 Height of an empty tree is defined to be (–1).

#### Q6. Why queue is linear data structure.

Answer:- A queue is a linear data structure into which items can only be inserted at one end and removed from the other.
In contrast to the stack, which is a LIFO (Last In First Out) structure, a queue is a FIFO (First In First Out) structure.

#### Q7. How we can delete a node with two Childs in a binary search tree using its right sub tree.

Answer:- The node to be deleted has either left child (subtree) or right child (subtree).In this case we bypass the node in such a way that we find the inorder successor of this node and then link the parent of the node to be deleted to this successor node. Thus the node was deleted.

#### Q8. define const keyword, reference variable, Dangling reference

Answer: Const keyword The const keyword is used for something to be constant. The actual meanings depend on where it occurs but it generally means something is to held constant. There can be constant functions, constant variables or parameters etc. Reference variable The references are pointers internally, actually they are constant pointers. You cannot perform any kind of arithmetic manipulation with references that you normally do with pointers. Dangling reference The pointer of the object (when object has already been deallocated or released) is called dangling pointer.

#### Q9. what is complete binary tree?

Answer: The definition of the complete binary tree is A complete binary tree of depth d is the strictly binary tree all of whose leaves are level d.

#### Q10. What is function of length () method in the Queue

Answer:  In Queue length() method, has a single statement i.e. return size ; This method returns the size of the queue, reflecting the number of elements in the queue. It is not the size of the array used internally to store the elements of the queue.

#### Q11. Explain the two cases in which we apply double rotation in An Avl tree.

Answer: Sometimes a single rotation is not sufficient to balance an unbalanced tree. The two cases are following:
1. Insertion into the right subtree of the left child of X node (RL)
2. Insertion into the left subtree of the right child of X node (LR)

#### Q.12 How AVL is different from Binary Search Tree?

Answer: – A binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One common use of binary trees is binary search trees; another is binary heaps. While an AVL tree is a self-balancing binary search tree. In an AVL tree the heights of the two child sub-trees of any node differ by at most one, therefore it is also called height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations.

#### Q.13 What the maximum no of comparisons we have to perform during insertion in BST?

Answer:-  If we have a complete binary tree with n numbers of nodes, the depth d of the tree can be found by the following equation: d=log2 (n + 1) – 1 If the tree is complete binary or near-to-complete, we need log2(n) number of comparison. Whereas in a linked list, the comparisons required could be a maximum of n.

#### Q14. What is Function Call Stack Give short answer?

Answer:- Stacks play a key role in implementation of function calls in programming languages. In C++, for example, the “call stack” is used to pass function arguments and receive return values. The call stack is also used for “local variables”

#### Q15. What are the applications of Binary Tree?

Answer:- The binary tree is a useful data structure for rapidly storing sorted data and rapidly retrieving stored data. It can hold objects that are sorted by their keys. It can represent a structured object, An operating system maintains a disk’s file system as a tree, where file folders act as tree nodes:

#### Q16. Give the names of basic Queue Operations.

Answer:- Queue Operations The queue data structure supports the following operations:

Operation Description

enqueue(X) Place X at the rear of the queue.

dequeue() Remove the front element and return it.

front() Return front element without removing it.

isEmpty() Return TRUE if queue is empty, FALSE otherwise

#### Q16. Give one benefit of using Stack.

Answer:-  In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop.the data structure itself enforces the proper order of calls.

#### Q17. Why List wastes less memory as compared to Arrays?

Answer:- 1. Linked lists do not need contiguous blocks of memory; extremely large data sets stored in an array might not be able to fit in memory. 2. Linked list storage does not need to be preallocated (again, due to arrays needing contiguous memory blocks). 3. Inserting or removing an element into a linked list requires one data update, inserting or removing an element into an array requires n (all elements after the modified index need to be shifted). Array is a collection of same data type. In linked list there are two field one is address and other is pointer. In array elements are arranged in a specific order.

#### Q18. Why we can change the size of list after its creation when we can not do that in simple arrays?

Answer:- Some how the answer will be same as part 1 because Inserting or removing an element into a linked list requires one data update, inserting or removing an element into an array requires n (all elements after the modified index need to be shifted). Array is a collection of same data type. The size of array is mentioned with its declaration. in arrays the elements are in contiguous position. One must after another. While in linked list we gave the address of next element in the next part of node.

#### Q20. Describe any two uses of priority queues?

Answer:-  Priority queue being used at many places especially in the operating systems. In operating systems, we have queue of different processes. If some process comes with higher priority, it will be processed first. Here we have seen a variation of queue. We will use the priority queue in the simulation. The events will be inserted in the queue and the event going to occur first in future, will be popped.

#### Q21. Describe the Use of Queues?

Answer:-  Use of Queues: Out of the numerous uses of the queues, one of the most useful is simulation. A simulation program attempts to model a real-world phenomenon. Many popular video games are simulations, e.g., SimCity, Flight Simulator etc. Each object and action in the simulation has a counterpart in the real world. Computer simulation is very powerful tool and it is used in different high tech industries, especially in engineering projects. For example, it is used in aero plane manufacturing. Actually Computer Simulation is full-fledged subject of Computer Science and contains very complex Mathematics, sometimes. For example, simulation of computer networks, traffic networks etc.

#### Q22. How we evaluate postfix expressions?

o Each operator in a postfix expression refers to the previous two operands.
o Each time we read an operand, we push it on a stack.
o When we reach an operator, we pop the two operands from the top of the stack, apply the operator and push the result back on the stack.

#### Q23. What is meant by an empty stack?

Answer:  Empty stack means that there is no element on the stack. IsEmpty() boolean function returns true if stack is empty, false otherwise.

#### Q24. Is the following statement correct? If your answer is No, then correct it. “A tree is an AVL tree if at least half of the nodes fulfill the AVL condition”

Answer:  Statement is wrong, Correct statement is: A tree is an AVL tree if all the nodes fulfill the AVL condition.

#### Q25.Which process places data at the back of the queue?

Answer: “ enqueue(X) “ Place X at the rear/back of the queue.

#### Q26. How we can delete a node with two Childs in a binary search tree using its right sub tree.

Answer:-  The node to be deleted has either left child (sub-tree) or right child (sub-tree).In this case we bypass the node in such a way that we find the in-order successor of this node and then link the parent of the node to be deleted to this successor node. Thus the node was deleted.

#### Q27. Why we use Reference Variables. Give one example.

Answer:- Click here for detail C++ references allow you to create a second name for the a variable that you can use to read or modify the original data stored in that variable.

#include main()

{

int x;

int& foo = x;

// foo is now a reference to x so this sets x to 56 foo = 56;

std::cout << x <<std::endl;

}

#### Q28. Define Reference Variable, Dangling Reference & Const

Answer:- In the C++ programming language, a reference is a simple reference datatype that is less powerful but safer than the pointer type inherited from C. The name C++ reference may cause confusion, as in computer science a reference is a general concept datatype, with pointers andC++ references being specific reference datatype implementations Dangling Reference & Const
Dangling pointers and wild pointers in computer encoding are pointers that do not point to a valid object of the suitable type. These are special cases of violations of memory safety

#### Q29. What is the use of Reference Variable, Give example?

Answer:- A reference variable is used to refer a particular object Location which resides on a garbage collectable heap. c++ supports one more type of variable called reference variable. In addition to pointer variable and value variable of reference variable behaves similar to both value variable and pointer variable. Reference variable has all access that variable has.

#### Q30. How we can avoid the problem of Dangling reference

Answer:- To avoid dangling reference, don’t return the reference of a local variable (Transient) from a function.