 |
|
#1
11-27-2011, 08:20 AM
|
||||
|
||||
cs502 midterm 2011***
MCQ’s
Q What type of instructions Random access machine can execute? Choose best answer. Geometric and arithmetic Algebraic and logic Arithmetic and logic Parallel and recursive Q Due to left complete nature of binary tree, the heap can be stored in • Arrays • Structures • Link Lis • Stack Q What type of instructions Random Access Machine (RAM) can execute? Choose best answer Algebraic and logic Geometric and arithmetic Arithmetic and logic Parallel and recursive Q For Chain Matrix Multiplication we can not use divide and conquer approach because, We do not know the optimum k We use divide and conquer for sorting only We can easily perform it in linear time Q knapsack problem is called a “0-1” problem, because ????????????????????? Each item must be entirely accepted or rejected ????????????????????? ??????????????????????? Q word Algorithm comes from the name of the muslim author Abu Ja’far Mohammad ibn Musa al-Khowarizmi. Q al-Khwarizmi’s work was written in a book titled al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah Q What is the total time to heapify? • O(log n) • O(n log n) • O(n2 logn) • O(log2n) Subjective Q Consider the case of 3 matrices: A1 is 5 × 4, A2 is 4 × 6 and A3 is 6 × 2 The multiplication can be carried out as ((A1A2)A3) The cost of the two ? 3 marks Q Consider the case of 3 matrices: A1 is 5 × 4, A2 is 4 × 6 and A3 is 6 × 2 The multiplication can be carried out either as ((A1A2)A3) or (A1(A2A3)). The cost of the two ? 5 marks Q We covered radix sort briefly in the lectures. Carry out radix sort on the following 3-digit numbers in order to sort them in ascending order. 114 243 563 871 334 442 765 Show the result after the first pass. 5 marks 
|
|
Linear Mode
