CS502 Final Term Solved MCQs by Junaid

Q1. Which method is preferable for dealing with chain matrix multiplication?

•  Divide and conquer strategy

 Dynamic programming formulation

•  Graph theory
•  Greedy Approach

2. Huffman algorithm produces the…….prefix code tree.

•  Better

 Optimal

•  Worst
•  Best

3. A….w is adjacent to vertex v if there is an edge from v to w.

•  Acyclic

 Vertex

•  Loop
•  Cycle

4. Using ASCII standard the string “greedy” will be encoded with

i. 44 bits

ii. 120 bits

iii. 40 bits

iv.

48 bits

5. Find the maximum value of the items which can carry using knapsack weight capacity

=50

Item weight Value

i.

ii.

iii.

iv.

6. In activity scheduling algorithm, each activity is represented by a

i.

Rectangle

ii. Square iii. Circle

iv. Triangle

7. Those problems in which greedy finds good, but not always best is called a greedy…..

i.

Heuristic

ii. Solution

iii. Result

iv. Algorithm

8. The knapsack problem belongs to the domain of…..Problems

i. Searching

ii. Sorting

iii. Linear solution

iv.

Optimization

9. The general coin change problem can be solved using

i. Recursion

ii. Greedy algorithm

iii.

iv.

10. Huffman algorithm produces the…………prefix code tree

i.

Optimal

ii. Better

iii. Best

iv. Worst

11. Huffman algorithm generates an optimum …..code

i. Postfix

ii. Infix

iii. None of the given options

iv.

Prefix

12. …..ways of representing graphics

i.

ii.

iii.

iv.

13. Knapsack word originates from ……language

i.

German

ii. English

iii. French

iv. Norwegian

14. Graphs are important…….model for many application problems

i.

Mathematical

ii. Unpredictable

iii. Haphazard

iv. Unsystematic

Q15. Which type of algorithm is harder to prove the correctness?

i. Dynamic ii. Greedy

iii.

iv. Brute force

16. …..Items are not allowed in 0/1 knapsack problem

i. Fractional

ii.

iii.

iv.

17. Matrix multiplication is a(n)……..operation

i. Nether commutative nor associative

ii. Transitive

iii. Commutative

iv.

Associative

18. For a Diagraph G= (V.E), Sum of in-degree (v) -----------------.

Not equal to sum of out-degree(v)

= sum of out-degree(v) pg#115

< sum of out-degree(v)

> sum of out-degree(v)

19. DFS or BFS yields a-------------of the graph.

Traversed tree

Spanning tree pg#125

Simple tree

Free tree

20. Using ASCII code, each character is represented by a fixed-length code of-------------bits per

character.

21. In Knapsack Problem, the goal is to put items in the Knapsack

such that the value of the items is---------

-------subject to weight limit of the Knapsack. 8 pg#100