Get premium membership and access revision papers, questions with answers as well as video lessons.

Got a question or eager to learn? Discover limitless learning on WhatsApp now - Start Now!

Ins320:Data Structures And Algorithms Question Paper

Ins320:Data Structures And Algorithms

Course:Bachelor Of Science In Information Science

Institution: Moi University question papers

Exam Year:2015

MOI UNIVERSITY
OFFICE OF THE CHIEF ACADEMIC OFFICER
UNIVERSITY EXAMINATIONS
2014/2015 ACADEMIC YEAR
THIRD YEAR FIRST SEMESTER EXAMINATION
FOR THE DEGREE OF
BACHELOR OF SCIENCE
IN
INFORMATION SCIENCES
COURSE CODE: INS 320
COURSE TITLE: DATA STRUCTURES AND ALGORITHMS
DATE: 17TH APRIL, 2015 TIME: 2.00 P.M. – 4.15 P.M.

INSTRUCTION TO CANDIDATES
• SEE INSIDE

THIS PAPER CONSISTS OF (2) PRINTED PAGES PLEASE TURN OVER
MOI UNIVERSITY
SCHOOL OF INFORMATION SCIENCES
DEPARTMENT OF INFORMATION TECHNOLOGY
FIRST SEMESTER 2014/2015 ACADEMIC YEAR EXAMINATIONS
COURSE CODE: INS 320
COURSE TITLE: DATA STRUCTURES AND ALGORITHMS TIME: 2 Hrs 15 Mins
==============================================================================
INSTRUCTIONS TO CANDIDATES:
• Answer question ONE and any other TWO questions
• If required to express an algorithm, use pseudo-code or a programming language

Question 1 Compulsory (30 Marks)
1. In the following tree:
1
2 3
4 5 6 7
If post order traversal generates sequence xy-zw*+, then label of nodes 1, 2, 3, 4, 5, 6, 7 will be:
A. x, -, y, +, z, *, w
B. +, -, *, x, y, z, w
C. x, y, z, w, -, *, +
D. -, x, y, +, *, z, w
2. In a doubly linked list
A. The last node has a link to the first node and vice versa
B. Every node has a link to the first node
C. Every node has a link to its successor and predecessor
D. All of the above
3. To represent a binary tree of height h using an array, the size of the array must be greater than
A. 2h
B. 2h+1
C. 2h-1
D. 2h – 1
4. What is true about a binary search tree?
A. The key in a right sibling is always greater than the key on its left sibling
B. The key in a node is always greater than the key in the children nodes
C. The largest key is stored in the root
D. All of the above
5. The node in a linked list from which every node can be accessed is known as the
A. Head
B. Root
C. Front
D. First
6. The depth of a complete binary tree with n nodes is ___
A. log2 (n+1) – 1
B. log2 n
C. log2 (n – 1) + 1
D. log2 n+1
7. The memory address of the first element of an array is called
A. head address
B. base address
C. root address
D. first address
8. Which of the following is not the required condition for binary search algorithm?
A. The list must be sorted
B. There must be mechanism to delete and/or insert elements in list
C. There should be a direct access to the middle element in any sublist
D. None of the above
9. In the given binary tree, using array you will store the node 4 at which location?
/1\
2 /3
4\
5
A. 3
B. 4
C. 5
D. 6
10. If the height of a complete tree is 2, then what us the minimum size of the tree?
A. 4
B. 2
C. 7
D. 6
11. The operation of processing each element in a data structure is known as
A. Sorting
B. Visiting
C. Inserting
D. Traversing
12. Linked lists are best suited
A. For relatively permanent collections of data
B. For the size of the structure and the data in the structure are constantly changing
C. For both of above situations
D. For none of the above situations
13. Which of the following arrays have the heap property?
A. 90 80 60 40 30 50 70 30
B. 90 80 40 70 20 30 50 60
C. 90 80 70 60 50 40 30 20
D. 90 80 60 70 20 30 40 50
14. In linked lists there are no NULL links in:
A. Single linked list
B. Linear doubly linked list
C. Circular linked list
D. None of the above
15. In array representation of binary tree, the right child of the root will be at location
A. 2
B. 5
C. 3
D. 0
16. Finding the location of the element with a given value is:
A. Traversal
B. Search
C. Locate
D. A and B
17. A binary tree has 9 nodes. Given the following as the inorder and preorder traversals of the tree, what will be the postorder traversal of the tree?
Inorder: E A C K F H D B G
Preorder: F A E K C D F G B
A. A B C D E F G H K
B. F D G B H A K C E
C. E C K A H B G D F
D. K H G F E D C B A
18. The first item to be removed from a priority queue is always
A. The greatest
B. The smallest
C. A or B
D. None of the above
19. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree, what is the post-order traversal sequence of the resulting tree?
A. 7, 5, 1, 0, 3, 2, 4, 6, 8, 9
B. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
C. 0, 2, 4, 3, 1, 6, 5, 9, 8, 7
D. 9, 8, 6, 4, 2, 3, 0, 1, 5, 7
20. If the post order traversal of a binary search tree gives BDEFCA as the order of the nodes visited, what order will the pre order traversal of this give?
A. ABCDEF
B. ADBFEC
C. ACBEDF
D. ACBFED
21. Which of the following statements is true about binary heaps
A. A heap is efficiently implemented as an array
B. The shape of a heap depends on the order in which its elements are inserted
C. The left child element is always smaller than the right child element
D. The value in a node is always greater than the values in its two children
22. In a binary search tree, the largest element must
A. Be the root
B. Be a leaf
C. Have no child
D. Have at most one child
23. If the address of the 8th element in a singly linked list of integers is 1022, the address of the 9th element is
A. Less than 1022
B. Greater than 1022
C. 1026
D. Either [A] or [B]
24. A hash table implemented by closed hashing contains 10 slots and uses linear probing toresolve collisions. The key values are integers and the hash function used is: H(x) = x mod 10
If the values 43, 165, 62, 123, 142 are inserted in the table, in what location will the key value 142 be inserted?
A. 2
B. 3
C. 4
D. 6
25. The following numbers are inserted into an empty binary search tree in the given order
10, 1, 3, 5, 15, 12, 16
What is the height of the binary tree?
A. 2
B. 3
C. 4
D. 6
26. Which of the following is true of the open hashing (separate chaining)?
A. All data are stored in the table array directly
B. The algorithm probes different table cells until an empty one is found
C. Many elements can be stored at the same table cell
D. None of the above
27. Which of the following is a good characteristic of a hash function
A. Easy to compute
B. Uniform distribution of key over the hash table
C. Infrequent collisions
D. None of the above
28. Consider a hash table of size seven with starting index 0, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the content of the table when the sequence 8,1 3, 10 is inserted into the table using closed hashing using linear probing for collision resolution? Note that “__” denotes an empty location in the table:
A. 8, 1, 10, __, __, __, 3
B. 8, 1, __, __, 3, 10, __
C. 1, 8, __, __, __, 10, 3
D. 1, 10, 8, __, __, __, 3
29. The breadth-first traversal of a max-heap is 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The breadth-first traversal of the heap after these insertions is:
A. 10, 8, 7, 5, 3, 2, 1
B. 10, 8, 5, 3, 2, 1, 5
C. 10, 8, 7, 1, 2, 3, 5
D. 10, 8, 7, 3, 2, 1, 5
30. Which of the following about the binary tree below is NOT true
5
3/ \8
2/ \ 4 7/ \9
1/ 6/
A. Its height is 4
B. The height will be increased if we insert 10
C. The pre-order traversal is 5, 3, 2, 1, 4, 8, 7, 6, 9
D. 8 was inserted earlier than 5

Question 2 (20 Marks)
a. Because a heap is a complete tree, it is often implemented using an array. Using a zero-based array, what is the index of 87 of the min-heap shown below? [4 marks]
5
14/ \23
32/ \41 87/ \90
50/ \64 53/

b. Generally what is the index of the parent of anode whose index is m? [4 marks]
c. Generally what is the index of the right child of a node whose index is m? [4 marks]
d. A priority queue can be implemented using a heap. Show how the tree in a. above looks after
i) two dequeue operations in succession [4 marks]
ii) 11 and 14 have been enqueued in succession [4 marks]

Question 3 (20 Marks)
a. Write an algorithm that receives the head of a singly linked list and returns the size of the list (i.e the number of elements in the list). [10 marks]
b. How many comparisons are performed when performing linear/sequential/serial search for the key value “intimidate” on the following list is the list is first ordered in ascending lexicographic (alphabetic) order. [5 marks]
introspective
intro
intelligent
into
intellectual
intimate
intensive
interesting
internal
in

c. How many comparisons are performed when performing linear/sequential/serial search for the key value “intimidate” on the list in b. above if the list is first ordered in descending lexicographic (alphabetic) order. [5 marks]

Question 4 (20 Marks)
a. Show the structure of the BST each time the following items are added in the order given, starting with an empty structure. [10 marks]
introspective
intro
intelligent
into
intellectual
intimate
intensive
interesting
internal
in
b. If the BST you have constructed in a. above were to be stored in an array, what percentage of the array element would be unused? [5 marks]
c. If searching an item in a BST requires displaying the node in each node encountered during the search, what would be displayed when searching for the value “interval” in the BST you constructed in a. above? [5 marks]

Question 5 (20 Marks)
a. A group of street children are given a chance to pick any items of their choice in a supermarket provided a child does not pick the same item twice and a child picks only items that fit their carton box. The capacity of each carton box is 93 and the following items are in abundance in the supermarket.
Item t0 t1 t2 t3 t4 t5 t6 t7 t8 t9
Size 9 11 13 14 16 17 10 7 13 12
Value 6.4 9.6 8 0.7 0.6 8.5 5.9 0.6 6.6 0.3

Each child attempts to get the most valuable loot. When it is time to pick an item, one of the children picks the smallest item among the ones they have not picked in order to pack their carton boxes with the most items. Another child however decides to straight away pick the most valuable item that they have not yet picked.
Of these two children, determine which child ends with the most valuable loot and how much their loot is more in value than the loot of the other child. [20 marks]

Ins320:Data Structures And Algorithms Question Paper

More Question Papers

Popular Exams