+92 307 41 51 71 8 vuassassins@gmail.com

## CS301 – Data Structures

In CS301 Data Structures, we are providing you digitized Mid and Final Term Papers, Chapter Wise Quiz, Quiz Preparation, Past Papers Quiz, Current Papers, Handouts, Past Paper, Solved Quizzes, Handouts, Search Course Code, Lessons, VU Videos and Slides.

## NOTE: Click on Preparation Tab to take the MCQ’s Tests.

MID TERM
FINAL TERM
##### MID TERM CHAPTER WISE PREPARATION BY JAHAN ZAIB ASHIQ

Quiz Cat: No Quiz found

Quiz Cat: No Quiz found

Quiz Cat: No Quiz found

Quiz Cat: No Quiz found

##### FINAL TERM CHAPTER WISE PREPARATION BY JAHAN ZAIB ASHIQ

Quiz Cat: No Quiz found

Quiz Cat: No Quiz found

Quiz Cat: No Quiz found

Quiz Cat: No Quiz found

##### FINAL CHAPTER WISE PREPARATION BY JAHAN ZAIB ASHIQ

Quiz Cat: No Quiz found

Quiz Cat: No Quiz found

1. Nice Website and very good content

2. SUBJECTIVE QUESTIONS
Question No:1
Name of two divide and conquer algorithm (2 marks)
 Merge Sort
 Quick Sort
 Heap Sort
These three algorithms fall under ‗divide and conquer category‘
Question No:2
Difference between call by value n call by reference (2 marks)
In case of call by value, a copy of object is made and placed at the time of function calling in the activation record. By using the references, we are not making the copy but send the address of the variable that function can use the original value.
Question No:3
Heap and two types of heap(3)
Heap is a data structure of big use and benefit. It is used in priority queue. ―The definition of heap is that it is a complete binary tree that conforms to the heap order‖. Here heap order means the min and max heap. Max heap: In max heap, each node has a value greater than the value of its left and right child nodes. Moreover, the value of the root will be largest and will become lesser at downward levels. Min heap: in a (min) heap for every node X, the key in the parent is smaller than (or equal to) the key in X. This means that the value in the parent node is less than the value on its children nodes.
Question No: 4
Here is an array with exactly 15 elements:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.
Suppose that we are doing a binary search for an element. Indicate any elements that will be found by
examining two or fewer numbers from the array. (Marks: 5)
If there is an array of 15 elements, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
it wants to know which elements can be discovered by examining two or fewer elements. I want assume the divide and conquer aspect of a binary search, so that leads me to think these elements will be found
1, 2, 14, 15, 7, 3
rather; 1, 2, 3, 4, 6, 8, 14, 15
1 and 15 for heads and tails
2, and 14 for next elements (following or preceding)
1/2 of 15 is either 6, or 8, from 7.5
and 1/2 of 6 = 3
1/2 8 = 4
Question No: 4
Write one example of hashing?
Hashing can be used to store the data. Suppose we have a list of fruits. The names of Fruits are in string. The
key is the name of the fruit. We will pass it to the hash Function to get the hash key.
HashCode (“apple”) = 5
We pass it to the string ―apple‖. Resultantly, it returns a number 5.
Question No: 5
How do we carry out degeneration of Complete Binary Tree?
Degeneration of the (original) binary tree is mainly reflected by degeneration of the internal infix trees and less by degeneration of the external height of the PPbin tree.
Question No: 6
How we can generate a maze with the help of union?
How can we generate maze? The algorithm is as follows:
 Randomly remove walls until the entrance and exit cells are in the same set.
 Removal of the wall is the same as doing a union operation.
 Do not remove a randomly chosen wall if the cells it separates are already I the same set.
Question No: 7
Write down the C++ code to implement insertion sort algorithm. ?
Following is the code of the insertion sort in C++.
void insertionSort(int *arr, int N)
{
int pos, count, val;
for(count=1; count = 0; pos–)
if (arr[pos] > val)
arr[pos+1]=arr[pos];
else break;
arr[pos+1] = val;}
}
Question No: 8
What is Table ADT? Discuss any two implementations of table ADT. ?
The table, an abstract data type, is a collection of rows and columns of information.
Implementation of Table
o Unsorted Sequential Array
o Sorted Sequential Array
Question No: 9
What is an Equivalent relation? Give any two examples. ?
A binary relation R over a set S is called an equivalence relation if it has following properties‘:
1. Reflexivity: for all element x ȟ S, x R x
2. Symmetry: for all elements x and y, x R y if and only if y R x
3. Transitivity: for all elements x, y and z, if x R y and y R z then x R z
Example; sets of peoples ,electric circuit domain.
Question No: 10
How heap sort works to set a set of data ?
Min heap and max heap are used to sort the data. Min heap convert the data in ascending sorted order and max heap convert the in descending order.
Question No 11: How can we search an element in skip list? 2Marks
We search for a key x in the following fashion:
We start at the first position of the top list
• At the current position p, we compare x with y �key(after(p))
• x = y: we return element(after(p))
• x > y: we ―scan forward‖
• x object = object; }; // set the value of the element
Node* getNext() { return nextNode; }; // get the address of the next node
void setNext(Node* nextNode) // set the address of the next node
{ this->nextNode = nextNode; };
Node* getPrev() { return prevNode; }; // get the address of the prev node
void setPrev(Node* prevNode) // set the address of the prev node
{ this->prevNode = prevNode; };
private:
int object; // it stores the actual value of the element
Node* nextNode; // this points to the next node
Node* prevNode; // this points to the previous node
};
Question No 27: What you conclude from the running time analysis of disjoint sets.
We conclude that:
 union is clearly a constant time operation
 Running time of find(i) is proportional to the height of the tree containing node i.
 This can be proportional to n in the worst case (but not always).
 Goal: Modify union to ensure that heights stay small.
Question No 28:what is c++ template.
A template is a function or class that is written with a generic data type. when a programmer uses this function or class the generic data type is replaced with the data type needed to be used in the template function or in the template class. We only give the data type of our choice while calling a template function or creating an object of the template class. The compiler automatically creates a version of that function or class with that specified data type.
Question No:29
which three basic operations are performed on AVL trees (mark 3)
 Insert
 Delete
 search
Question No: 30
Write the applications of heap.
The stack and heap are used in function calls. When we allocate memory dynamically in our programs, it is allocated from the heap. The use of priority queue with the help of heap is a major application. The priority queue is itself a major data structure, much-used in operating systems. Similarly priority queue data structure is used in network devices especially in routers. Heap data structure is also employed in sorting algorithms.
Question No: 31 Which is Dynamic Equivalence Problem with an example? (5)
We are using sets to store the elements. For this purpose, it is essential to remember which element belongs to which set. We know that the elements in a set are unique and a tree is used to represent a set. Each element in a tree has the same root, so the root can be used to name the set. The item (number) in the root will be unique as the set has unique values of items. We use this root as the name of set for our convenience. Otherwise, we can use any name of our choice. So the element in the root (the number) is used the name the set.
The find operation will return this name. Due to the presence of many sets, there will be a collection of trees. In this collection, each tree will be representing one set. If there are ten elements, we will have ten sets initially. Thus there will be ten trees at the beginning. In general, we have N elements and initially there will be N trees. Each tree will have one element. Thus there will be N trees of one node. Now here comes a definition for this collection of trees, which states that a collection of trees is called a forest.
The trees used for the sets are not necessarily binary trees. That means it is necessary that each node should have a maximum of two children nodes. Here a n may have more than two children nodes. To execute the union operation in two sets, we merge the two trees of these sets in such a manner that the root of one tree points to the root of other. So there will be one root, resulting in the merger of the
trees. In the find operation, when we call find (x), it helps us to know which set this x belongs to. Internally, we find this x in a tree in the forest. When this x is found in a tree the find returns the number at root node (the name of the set) of that tree.
Question No 32: “is a sibling of” set of all human beings is equivalence relation or not? Explain.
Yes it is an equivalence relation
First rule is reflexive i.e. for all element x �S, x R x. Suppose that x is Haris so Haris R Haris. This is true because everyone is related to each other. Second is Symmetry: for all elements x and y, x R y if and only if y R x. Suppose that y is Saad. According to the rule, Haris R Saad if and only if Saad R Haris. If two persons are related, the relationship is symmetric i.e. if I am cousin of someone so is he. Therefore if Haris is brother of Saad, then Saad is certainly the brother of Haris. The family relationship is symmetric. This is not the symmetric in terms of respect but in terms of relationship. The transitivity is: ‗for all elements x, y and z. If x R y and y R z, then x R z‘. Suppose x is Haris, y is Saad and z is Ahmed. If Haris ―is related to‖ Saad, Saad ―is related to‖ Ahmed. We can deduce that Haris
―is related to‖ Ahmed. This is also true in relationships. If you are cousin of someone, the cousin of that person is also related to you. He may not be your first cousin but is related to you.
Linked memory is a memory in which the various cells of memory are not located continuously. In this process, each cell of the memory not only contains the value of the element but also the information where the next element of the list is residing in the memory. It is not necessary that the next element is at the next location in the memory. It may be anywhere in the memory. We have to keep a track of it.
Thus, in this way, the first element must explicitly have the information about the location of the second element.

3. kia ye question past papers me se liye gye hen ???

• g kuch 2,4

## SPIN TO WIN!

• Try your lucky to get discount coupon
• 1 spin per email
• No cheating
Never
Remind later
No thanks