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
