CS301 Assignments of Spring 2012
CS301-Data Structure Solved MCQs from Finalterm Papers
Solved & Shared by Moaaz Siddiq
Attachment:
Showing posts with label CS301. Show all posts
Showing posts with label CS301. Show all posts
CS301 Finalterm Subjective Paper July 2012
Saturday, 4 August 2012
CS301 - Data Structure Finalterm Subjective Paper July 2012
Total 52 questions
4o mcqs
4 questions of 2 marks
4 questions of 3 marks
4 questions of 5 marks
Questions of 2 marks:
In the array representation of union what represents -1?
For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply." Justify why?
If we want to delete the node from BST which has left and right child then which rotation is applied ?
Collision in hashing definition?
4o mcqs
4 questions of 2 marks
4 questions of 3 marks
4 questions of 5 marks
Questions of 2 marks:
In the array representation of union what represents -1?
For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply." Justify why?
If we want to delete the node from BST which has left and right child then which rotation is applied ?
Collision in hashing definition?
Question of 3 marks:
Algorithm union by weight?
One tree is given question is it heap or not if it is heap then write its type?
Which data structure is best for priority queue?
Questions of 5 marks:
Some numbers are given and using those make BST?
One array is given we require to sort it using bubble sort and write only 2 iterations?
One tree is given which not the heap but after minimum changes it becomes max heap make it?
Algorithm union by weight?
One tree is given question is it heap or not if it is heap then write its type?
Which data structure is best for priority queue?
Questions of 5 marks:
Some numbers are given and using those make BST?
One array is given we require to sort it using bubble sort and write only 2 iterations?
One tree is given which not the heap but after minimum changes it becomes max heap make it?
Another Paper:
Question 1: Write min heap after removal of root. 3 marks.
1 3 2 5 4 8 9 10 7
Question 2: Write In order and preorder traversal. 3 marks
Question 3: show steps of merge sort. 5 marks.
11 12 13 21 22 23 31 33 41 42
Question 4: correct the following code.
int isPresent(int *arr, int val, int N)
{ int low = 0;
int high = N - 1;
int mid;
while ( low >= high )
{ mid = ( low-high )/2;
if (arr[mid] == val)
return 1; // found!
else if (arr[mid] > val)
low = mid - 1;
else
high = mid + 1;
}
return 0; // not found
}
Question 5: Correct the code.5 marks
/* The inorder routine for threaded binary tree */
TreeNode* nextInorder(TreeNode* p){
if(p->RTH == thread)
return(p->R);
else {
p = p->R;
while(p->LTH == child)
p = p->L;
return p;
}
}
Question 6:
for telephone directory which is best linear or non-linear array. 2 marks
Question 7:
how to cope with collision. 2 marks
Question 1: Write min heap after removal of root. 3 marks.
1 3 2 5 4 8 9 10 7
Question 2: Write In order and preorder traversal. 3 marks
Question 3: show steps of merge sort. 5 marks.
11 12 13 21 22 23 31 33 41 42
Question 4: correct the following code.
int isPresent(int *arr, int val, int N)
{ int low = 0;
int high = N - 1;
int mid;
while ( low >= high )
{ mid = ( low-high )/2;
if (arr[mid] == val)
return 1; // found!
else if (arr[mid] > val)
low = mid - 1;
else
high = mid + 1;
}
return 0; // not found
}
Question 5: Correct the code.5 marks
/* The inorder routine for threaded binary tree */
TreeNode* nextInorder(TreeNode* p){
if(p->RTH == thread)
return(p->R);
else {
p = p->R;
while(p->LTH == child)
p = p->L;
return p;
}
}
Question 6:
for telephone directory which is best linear or non-linear array. 2 marks
Question 7:
how to cope with collision. 2 marks
CS301 Final Term Solved Subjective Papers by Moaaz
CS301-Data Structure Final Term Solved Subjective Papers
Solved by Moaaz Siddiq
 CS301-Finalterm-solved-subjective | [ ] | 500 Kb |
CS301 Data Structure Final Term Subjective
CS301 Data Structure Final Term Subjective
Shared by Abdul Manan. CS301-Finalterm-Subjective | [ ] | 43 Kb |
CS301Final Term Subjective Questions Jan-2012
CS301 Data Structure Final Term Subjective Questions Jan-2012
Q 41: Where is hashing suitable? 2 Marks
Q.42 When Hashing is not Suitable? 2 Marks
Q.45 How many parameters used in following operation? write their names,
0. Find,
1. Add
3. Remove 3 Marks
Q.46 Forgot
Q.49 Union by size tree formation, Assignment no4 was asked 5 Marks
Q.50 Code for Union and find operation in disjoints sets. 5Marks
Q.51 A function Hash(x) = (x*2)/ tablesize and is given index from 0 to 11, to find out the contents of tables of values in order 11, 29, 36, 22, 27 5Marks
Q.42 When Hashing is not Suitable? 2 Marks
Q.45 How many parameters used in following operation? write their names,
0. Find,
1. Add
3. Remove 3 Marks
Q.46 Forgot
Q.49 Union by size tree formation, Assignment no4 was asked 5 Marks
Q.50 Code for Union and find operation in disjoints sets. 5Marks
Q.51 A function Hash(x) = (x*2)/ tablesize and is given index from 0 to 11, to find out the contents of tables of values in order 11, 29, 36, 22, 27 5Marks
Total Number 80
Time 120 minutes
Total Question 52
40 MCQs from Past Papers
2 four-long questions
3 four-long questions
5 four-long questions
Q1. How we can implement Table ADT using Linked List (2)
Q2. What is hashing? (2)
Q3. Describe the conditions for second case of deletion in AVL Trees. (2)
Q4. What is an Equivalent relation? Give any two examples. (2)
Q1. Write down the parameter name of the following:- (3)
1. Delete
2. Insert
3. Find
Q2. Where Inorder Predecessor of a non leaf node is is present in a Binary Search Tree? :- (3)
Q3. How we can search an element in Skip List. (3)
Q4. Convert the given infix form to postfix form. Y-Z*X-Q^P-(3)
Q1. 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.? (5)
Q2. Here is an array of ten integers:
5 3 8 9 1 7 0 2 6 4
The array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest)? (5)
Q3. Consider the following array as input
Time 120 minutes
Total Question 52
40 MCQs from Past Papers
2 four-long questions
3 four-long questions
5 four-long questions
Q1. How we can implement Table ADT using Linked List (2)
Q2. What is hashing? (2)
Q3. Describe the conditions for second case of deletion in AVL Trees. (2)
Q4. What is an Equivalent relation? Give any two examples. (2)
Q1. Write down the parameter name of the following:- (3)
1. Delete
2. Insert
3. Find
Q2. Where Inorder Predecessor of a non leaf node is is present in a Binary Search Tree? :- (3)
Q3. How we can search an element in Skip List. (3)
Q4. Convert the given infix form to postfix form. Y-Z*X-Q^P-(3)
Q1. 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.? (5)
Q2. Here is an array of ten integers:
5 3 8 9 1 7 0 2 6 4
The array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest)? (5)
Q3. Consider the following array as input
| 13 | 4 | 6 | 8 | 9 | 7 | 10 | 15 | | | |
Prove that it is a heap and also explain what type of heap it is.? Draw the final NOT for all?
Q4. Draw the following sequence of union commands on the set of elements {1,2,3,4, 5}:
union(4,2)
union(3,1)
union(5,4)
union(5,3)
Show the result when the unions are performed. We need only Final results of union NOT for all.?
Q4. Draw the following sequence of union commands on the set of elements {1,2,3,4, 5}:
union(4,2)
union(3,1)
union(5,4)
union(5,3)
Show the result when the unions are performed. We need only Final results of union NOT for all.?
CS301 Final term paper Solved 2011
FINALTERM EXAMINATION
Spring 2011
CS301: Data Structure
1. Whatever is the size of the tree, the search is performed after traversing up to ………………. Maximum level. (log2n)
Which one of the following is NOT the property of equivalence relation?
► Reflexive
► Symmetric
► Transitive
► Associative
Binary Search is an algorithm of searching, used with the ______ data.
► Sorted
► Unsorted
► Heterogeneous
► Random
If one pointers of the node in a binary tree are NULL then it will be a/an _______ .
► Inner node
► Leaf node
► Root node
► None of the given options
Suppose we are sorting an array of eight integers using quick sort, and we have just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10
Which statement is correct?
► The pivot could be either the 7 or the 9.
► The pivot could be the 7, but it is not the 9.
► The pivot is not the 7, but it could be the 9.
► Neither the 7 nor the 9 is the pivot. (the pivot value will be 1 or 5)
Which one of the following algorithms is least efficient,
► Quick Sort
► Insertion Sort
► Merge Sort
► Bubble Sort (NOT Confirmed)
Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
► Elements in the first half of the array are less than or equal to elements in the second half of the array.
► None of the given options.
► The array elements form a heap.
► Elements in the second half of the array are less than or equal to elements in the first half of the array.
The data of the problem is of 2GB and the hard disk is of 1GB capacity, to solve this problem we should
► Use better data structures
► Increase the hard disk space
► Use the better algorithm
► Use as much data as we can store on the hard disk
If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value?
data[1]
data[n-1]
data[n]
data[2*n+1]
Union is a _______ time operation.
► Constant
► Polynomial
► Exponential
► None of the given options
Which of the following is NOT a correct statement about Table ADT.
► In a table, the type of information in columns may be different.
► A table consists of several columns, known as entities.
► The row of a table is called a record.
► A major use of table is in databases where we build and use tables for keeping information.
Consider a min heap, represented by the following array:
3,4,6,7,5
After calling the function deleteMin().Which of the following is the updated min heap?
► 4,6,7,5
► 6,7,5,4
► 4,5,6,7
► 4,6,5,7
What requirement is placed on an array, so that binary search may be used to locate an entry?
► The array elements must form a heap.
► The array must have at least 2 entries.
► The array must be sorted.
► The array’s size must be a power of two.
A binary relation R over S is called an equivalence relation if it has following property(s)
►Reflexivity
►Symmetry
►Transitivity
►All of the given options
If there are N elements in an array then the number of maximum steps needed to find an element using Binary Search is _______ .
► N
► N2
► Nlog2N
► log2N
While building Huffman encoding tree the new node that is the result of joining two nodes has the frequency.
► Equal to the small frequency
► Equal to the greater
► Equal to the sum of the two frequencies
► Equal to the difference of the two frequencies
Which of the following statements is correct property of binary trees?
► A binary tree with N internal nodes has N+1 internal links.
► A binary tree with N external nodes has 2N internal nodes.
► A binary tree with N internal nodes has N+1 external nodes.
► None of above statement is a property of the binary tree
A complete binary tree is a tree that is _________ filled, with the possible exception of the bottom level.
► partially
► completely
► incompletely
► partly
Consider the following infix expression:
x – y * a + b / c
Which of the following is a correct equivalent expression(s) for the above?
► x y -a * b +c /
► x *y a - b c / +
► x y a * - b c / +
► x y a * - b/ + c
CS301 Final term Paper 2010 - 2
FINALTERM EXAMINATION
Spring 2010
CS301- Data Structures
Time: 90 min
M - 58
CS301 - Data Structures - Q.No. 1 ( M - 1 )
Here is a small function definition:
void f(int i, int &k)
{
i = 1;
k = 2;
}
Suppose that a main program has two integer variables x and y, which are given the value 0. Then the main program calls f(x,y); What are the values of x and y after the function f finishes?
► Both x and y are still 0.
► x is now 1, but y is still 0.
► x is still 0, but y is now 2.
► x is now 1, and y is now 2.
CS301 - Data Structures - Q.No. 2 ( M - 1 )
A binary tree with N internal nodes has _____ links, _______ links to internal nodes and ________ links to external nodes
► N+1, 2N, N-1
► N+1, N-1, 2N
► 2N, N-1, N+1
► N-1, 2N, N+1
CS301 - Data Structures - Q.No. 3 ( M - 1 )
Each node in doubly link list has,
► 1 pointer
► 2 pointers
► 3 pointers
► 4 pointers
CS301 - Data Structures - Q.No. 4 ( M - 1 )
If you know the size of the data structure in advance, i.e., at compile time, which one of the following is a good data structure to use.
► Array
► List
► Both of these
► None of these
CS301 - Data Structures - Q.No. 5 ( M - 1 )
Which one of the following is not an example of equivalence relation:
► Electrical connectivity
► Set of people
► <= relation
► Set of pixels
CS301 - Data Structures - Q.No. 6 ( M - 1 )
If a complete binary tree has height h then its no. of nodes will be,
► Log (h)
► 2h+1- 1
► Log (h) - 1
► 2h - 1
CS301 - Data Structures - Q.No. 7 ( M - 1 )
If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value?
► data[1]
► data[n-1]
► data[n]
► data[2*n+1]
CS301 - Data Structures - Q.No. 8 ( M - 1 )
Which one is a self-referential data type?
► Stack
► Queue
► Link list
► All of these
CS301 - Data Structures - Q.No. 9 ( M - 1 )
There is/are ________ case/s for rotation in an AVL tree,
► 1
► 3
► 2
► 4
CS301 - Data Structures - Q.No. 10 ( M - 1 )
Which of the following can be the inclusion criteria for pixels in image segmentation.
► Pixel intensity
► Texture
► Threshold of intensity
► All of the given options
CS301 - Data Structures - Q.No. 11 ( M - 1 )
Consider te following array
23 15 5 12 40 10 7
After the first pass of a particular algorithm, the array looks like
15 5 12 23 10 7 40
Name the algorithm used
► Heap sort
► Selection sort
► Insertion sort
► Bubble sort
CS301 - Data Structures - Q.No. 12 ( M - 1 )
In a perfectly balanced tree the insertion of a node needs ________ .
► One rotation
► Two rotations
► Rotations equal to number of levels
► No rotation at all
CS301 - Data Structures - Q.No. 13 ( M - 1 )
If there are N elements in an array then the number of maximum steps needed to find an element using Binary Search is _______ .
► N
► N2
► Nlog2N
► log2N
CS301 - Data Structures - Q.No. 14 ( M - 1 )
Which of the following is NOT a correct statement about Table ADT.
► In a table, the type of information in columns may be different.
► A table consists of several columns, known as entities.
► The row of a table is called a record.
► A major use of table is in databases where we build and use tables for keeping information.
CS301 - Data Structures - Q.No. 15 ( M - 1 )
If both pointers of the node in a binary tree are NULL then it will be a/an _______ .
► Inner node
► Leaf node
► Root node
► None of the given options
CS301 - Data Structures - Q.No. 16 ( M - 1 )
Suppose we are sorting an array of eight integers using quick sort, and we have just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10
Which statement is correct?
► The pivot could be either the 7 or the 9.
► The pivot could be the 7, but it is not the 9.
► The pivot is not the 7, but it could be the 9.
► Neither the 7 nor the 9 is the pivot.
CS301 - Data Structures - Q.No. 17 ( M - 1 )
What is the best definition of a collision in a hash table?
► Two entries are identical except for their keys.
► Two entries with different data have the exact same key
► Two entries with different keys have the same exact hash value.
► Two entries with the exact same key have different hash values.
CS301 - Data Structures - Q.No. 18 ( M - 1 )
For a perfect binary tree of height h, having N nodes, the sum of heights of nodes is
► N – (h – 1)
► N – (h + 1)
► N – 1
► N – 1 + h
CS301 - Data Structures - Q.No. 19 ( M - 1 )
A binary tree with 33 internal nodes has _______ links to internal nodes.
► 31
► 32
► 33
► 66
CS301 - Data Structures - Q.No. 20 ( M - 1 )
Suppose you implement a Min heap (with the smallest element on top) in an array. Consider the different arrays below; determine the one that cannot possibly be a heap:
► 16, 18, 20, 22, 24, 28, 30
► 16, 20, 18, 24, 22, 30, 28
► 16, 24, 18, 28, 30, 20, 22
► 16, 24, 20, 30, 28, 18, 22
CS301 - Data Structures - Q.No. 21 ( M - 1 )
Which of the following is not true regarding the maze generation?
► Randomly remove walls until the entrance and exit cells are in the same set.
► Removing a wall is the same as doing a union operation.
► Remove a randomly chosen wall if the cells it separates are already in the same set.
► Do not remove a randomly chosen wall if the cells it separates are already in the same set.
CS301 - Data Structures - Q.No. 22 ( M - 1 )
Which formula is the best approximation for the depth of a heap with n nodes?
► log (base 2) of n
► The number of digits in n (base 10), e.g., 145 has three digits
► The square root of n
► n
CS301 - Data Structures - Q.No. 23 ( M - 1 )
In threaded binary tree the NULL pointers are replaced by ,
► preorder successor or predecessor
► inorder successor or predecessor
► postorder successor or predecessor
► NULL pointers are not replaced
CS301 - Data Structures - Q.No. 24 ( M - 1 )
The _______ method of list will position the currentNode and lastCurrentNode at the start of the list.
► Remove
► Next
► Start
► Back
CS301 - Data Structures - Q.No. 25 ( M - 1 )
Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
► Elements in the first half of the array are less than or equal to elements in the second half of the array.
► None of the given options.
► The array elements form a heap.
► Elements in the second half of the array are less than or equal to elements in the first half of the array.
CS301 - Data Structures - Q.No. 26 ( M - 1 )
Suppose we had a hash table whose hash function is “n % 12”, if the number 35 is already in the hash table, which of the following numbers would cause a collision?
► 144
► 145
► 143
► 148
CS301 - Data Structures - Q.No. 27 ( M - 2 )
Convert this tree representation of a heap into the corresponding array representation
CS301 - Data Structures - Q.No. 28 ( M - 2 )
What are different applications of Hashing?
CS301 - Data Structures - Q.No. 29 ( M - 2 )
Give the operation names that we can perform on Table abstract data type.
CS301 - Data Structures - Q.No. 30 ( M - 2 )
Give your comments on the statement:
"Efficiently developed data structures decrease programming effort"
CS301 - Data Structures - Q.No. 31 ( M - 3 )
When Hashing is NOT suitable?
CS301 - Data Structures - Q.No. 32 ( M - 3 )
Give any three characteristics of Union by Weight method.
CS301 - Data Structures - Q.No. 33 ( M - 3 )
Consider the following Max Heap add node 24 in it and show the resultant Heap,
CS301 - Data Structures - Q.No. 34 ( M - 5 )
Heapify the elements of the following array (reading from left to right ) into a Min Heap and show that Min Heap contents in the form of array as shown below,
original array | 6 | 5 | 3 | 9 | 1 | 2 | 10 | 8 | - |
Heapified array |
CS301 - Data Structures - Q.No. 35 ( M - 5 )
Here is an array of ten integers:
5 3 8 9 1 7 0 2 6 4
Show the first three merging steps for Merge sort on this array.
CS301 - Data Structures - Q.No. 36 ( M - 5 )
Consider the following sequence of union commands on the set of elements
{1,2,3,4, 5}:
union(4,2)
union(3,1)
union(5,4)
union(5,3)
Show the result when the unions are performed
Subscribe to:
Posts (Atom)
