CS502 my final exam MCQs

[Amna]

file attached

1.       Money change

·         O(k)

2.       AscII abacdaacac

3.       Adjacy list

4.       Asymptotic growth (4n cube+15nsquare+11n/n power 6)

·         Theta(4ncube+15nsquare+11n/6)

·         Theta(4ncube+n square+ n)

·         Theta( 1500 n square)

·         Theta ( n power 6)

5.       Quick sort, don’t control over size of recursive call

6.       Quick sort is based on divide and conquer paradigm. In the combine step of divide and conquer process

·         Work is needed to combine sub-arrays, the array is already sorted

·         No Work is needed to combine sub-arrays, the array is already sorted

·         Merging the arrays

·         Dividing the arrays

7.       Counting sort assumes that the number to be stored are in the range_________

·         1 to k where k is small

·         K to n where k is small

·         K to n where n is small

·         K to n where n is large

8.       Catalan for

9.       If we encode and compress text using ASCII standard each character is represented by

·         Fixed length code word of 4 bits

·         Variable length code word up to 4 bits

·         Fixed length code word of 8 bits

·         Variable length code word up to 8 bits

10.   Huffman algorithm finds

·         Some time optimal some time non-optimal solution

·         Space wise optimal and time wise non optimal solution

·         A non-optimal solution

·         An optimal solution

11.   The Huffman algorithm belongs to

·         The class of exponential algorithm

·         Class of non-polynomial algorithm

·         Space wise to polynomial algorithm but time wise exponential algorithm

·         Space and time wise polynomial algorithm

12.   Huffman algorithm time complexity

·         Can be improved up to O(nlogn)

·         Can be improved up to O( underroot n log n)

·         Is always O( n square)

·         Is always O( n cube)

13.   An adjacy matrix for a graph

·         Always square in shape

·         It is not necessary for it to be square in shape

·         Is square in shape for directed graph but not for undirected graphs

·         Is always diagonal matric

14.   In digraph

·         Is in degree attach to the vertex

·         Is out degree attach to the vertex

·         is a degree attach to the vertex

·         both in and out degree attached to the vertex

15.   in undirected graphs there

·         are no cross edge but forward and back edge

·         are only forward edge

·         is convention of only back edges

·         is convention of forward edges

16.   precedence constraint graph is

·         non-acyclic directed graph

·         non-acyclic undirected graph

·         acyclic undirected graph

·         acyclic directed graph

17.   kurskal’s algorithm

·         choose best non-cycle edge

·         choose the best tree edge

·         choose the vertex that gives the lightest weight

·         follow the DP rules for choosing edges

18.   in prim’s algorithm, the additional information maintained by the algorithm is

·         the length of the shortest path from vertex V to the vertex u

·         the length of the shortest edge from vertex v to point already in tree

·         the DP rules

·         the information about all adjacent vertices

19.   Adding any edge to free tree

·         Keep it free tree and increase the size of the tree

·         Create a unique cycle

·         Not allow to add edge to free tree

·         Create multiple cycles

20.   G power T for graph can be computed in

·         Theta(VE)

·         Theta(V log E)

·         Theta(E log V)

·         Theta (V + E)

21.   Which of the following not true about dijkstra algorithm

·         The length of shortest path to start vertex is always zero

·         It can find the shortest path to all other vertices in the same worst case time that it need to find the shortest path to a single vertex

·         It will work on any weighted graph with positive weights

·         Running time of bell algorithm is greater than dijkstra algorithm

22.   Kruskal is used for

·         Calculating shortest path problem

·         Calculating MST

·         Both can be calculated by it

·         Single source shortest path problems

23.   Shortest path information is propagated sequentially along each shortest path in

·         Prims algorithm

·         Dijsktra algorithm

·         Bell algorithm

·         Kruskal algorithm

24.   Complexity wise the  comparison based merge and quick sort algorithm fall in

·         Deterministic polynomial class

·         Non-deterministic polynomial class

·         Quick in P class and merge in NP class

·         Quick in NP class and merge in P class

25.    

[+ خان آفریدی +]

Thanks ... Amna...