aFINALTERM EXAMINATION
Fall 2009
CS301- Data Structures (Session - 4)
Question No: 1 ( Marks: 1 ) - Please choose one
In an array we can store data elements of different types. ► True
► False
Question No: 2 ( Marks: 1 ) - Please choose one
Which one of the following statement is NOT correct . ► In linked list the elements are necessarily to be contiguous
► In linked list the elements may locate at far positions in the memory
► In linked list each element also has the address of the element next to it
► In an array the elements are contiguous
Question No: 3 ( Marks: 1 ) - Please choose one
Doubly Linked List always has one NULL pointer. ► True
► False
Question No: 4 ( Marks: 1 ) - Please choose one
A queue is a data structure where elements are, ► inserted at the front and removed from the back.
► inserted and removed from the top.
► inserted at the back and removed from the front.
► inserted and removed from both ends.
Question No: 5 ( Marks: 1 ) - Please choose one
Each node in doubly link list has, ► 1 pointer
► 2 pointers
► 3 pointers
► 4 pointers
Question No: 6 ( Marks: 1 ) - Please choose one
I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into an EMPTY queue? ► Neither changes
► Only front pointer changes.
► Only rear pointer changes.
► Both change.
Question No: 7 ( Marks: 1 ) - Please choose one
Compiler uses which one of the following to evaluate a mathematical equation, ► Binary Tree
► Binary Search Tree
► Parse Tree
► AVL Tree
Question No: 8 ( Marks: 1 ) - Please choose one
If a complete binary tree has n number of nodes then its height will be,►Log2 (n+1) -1
►2n
►Log2 (n) - 1
►2n - 1
Question No: 9 ( Marks: 1 ) - Please choose one
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
Question No: 10 ( Marks: 1 ) http://allvupastpapers.blogspot.com.com - Please choose one
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
Question No: 11 ( Marks: 1 ) - Please choose one
Binary Search is an algorithm of searching, used with the ______ data. ► Sorted
► Unsorted
► Heterogeneous
► Random
Question No: 12 ( Marks: 1 ) - Please choose one
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
Question No: 13 ( Marks: 1 ) - Please choose one
Use of binary tree in compression of data is known as _______ . ► Traversal
► Heap
► Union
► Huffman encoding
Question No: 14 ( Marks: 1 ) - Please choose one
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
Question No: 15 ( Marks: 1 ) - Please choose one
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.
Question No: 16 ( Marks: 1 ) - Please choose one
Which of the following is a property of binary tree? ► A binary tree of N external nodes has N internal node.
► A binary tree of N internal nodes has N+ 1 external node.
► A binary tree of N external nodes has N+ 1 internal node.
► A binary tree of N internal nodes has N- 1 external node.
Question No: 17 ( Marks: 1 ) - Please choose one
Which of the following statement is correct? ► A Threaded Binary Tree is a binary tree in which every node that does not have a left child has a THREAD (in actual sense, a link) to its INORDER successor.
► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its PREOREDR successor.
► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its INORDER successor.
► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its POSTORDER successor.
Question No: 18 ( Marks: 1 ) - Please choose one
Which of the following statement is correct? ► A Threaded Binary Tree is a binary tree in which every node that does not have a left child has a THREAD (in actual sense, a link) to its INORDER successor.
► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its PREOREDR successor.
► A Threaded Binary Tree is a binary tree in which every node that does not have a left child has a THREAD (in actual sense, a link) to its INORDER predecessor.
► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its POSTORDER predecessor.
Question No: 19 ( Marks: 1 ) - Please choose one
A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its __________ successor. ► levelorder
► Preorder
► Inorder
► Postorder
Question No: 20 ( Marks: 1 ) - Please choose one
Which of the following statement is true about dummy node of threaded binary tree? ► This dummy node never has a value.
► This dummy node has always some dummy value.
► This dummy node has either no value or some dummy value.
► This dummy node has always some integer value.
Question No: 21 ( Marks: 1 ) - Please choose one
A complete binary tree is a tree that is _________ filled, with the possible exception of the bottom level. ► partially
► completely
► incompletely
► partly
Question No: 22 ( Marks: 1 ) - Please choose one
A complete binary tree of height 3 has between ________ nodes. ► 8 to 14
► 8 to 15
► 8 to 16
► 8 to 17
Question No: 23 ( Marks: 1 ) - Please choose one
We can build a heap in ________ time. ► Linear
► Exponential
► Polynomial
► None of the given options
Question No: 24 ( Marks: 1 ) - Please choose one
Suppose that a selection sort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)? ► 21
► 41
► 42
► 43
Question No: 25 ( Marks: 1 ) - Please choose one
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
Question No: 26 ( Marks: 1 ) - Please choose one
Which of the following statement is NOT correct about find operation: ► It is not a requirement that a find operation returns any specific name, just that finds on two elements return the same answer if and only if they are in the same set.
► One idea might be to use a tree to represent each set, since each element in a tree has the same root, thus the root can be used to name the set.
► Initially each set contains one element.
► Initially each set contains one element and it does not make sense to make a tree of one node only.
Question No: 27 ( Marks: 1 ) - Please choose one
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
Question No: 28 ( Marks: 1 ) - Please choose one
A complete binary tree of height ____ has nodes between 16 to 31 . ► 2
► 3
► 4
► 5
Question No: 29 ( Marks: 1 ) - Please choose one
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).
► 0 3 8 9 1 7 5 2 6 4
► 2 6 4 0 3 8 9 1 7 5
► 2 6 4 9 1 7 0 3 8 5
► 0 3 8 2 6 4 9 1 7 5
Question No: 30 ( Marks: 1 ) - Please choose one
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.
By : ADEEL ABBAS
www.allvupastpapers.blogspot.com
AdeelAbbasbk@gmail.com
No comments:
Post a Comment
PLEASE COMMENT ABOUT YOUR VISIT AND MY SITE
Note: Only a member of this blog may post a comment.