PPSC QUIZ

Algorithm Analysis and Design Solved Quizes

Question:- which of the following operations is performed more efficiently by doubly linked list than by linear linked list?

(A) Deleting a node whose location is given

(B) searching an unsorted list for a given item

(D) Traversing the list to process each node

Question:- the five items: A,B,C,D and E are pushed in a stack, one after the other starting from A. The stack is popped four items and each element is inserted in a queue. Then two elements are deleted from the queue and pushed back on the stack. Now on item is popped from the stack. The popped item is

(A) A

(B) B

(D) D

Question:- the time required to search an element in a binary search tree having n elements is

(A) O(1)

(B) O( log n)

(D) O(n log n)

Question:- for a linear search in an array of n elements the time complexity for best, worst and average case are …., and …respectively.

(A) O(n) , O(1) and O(n/2)

(B) O(1) , O(n) and O(n/2)

(D) ) O(1) , O(n) and O((n-1)/2)

Question:- the number of comparisons required by binary search of 100000 elements is

(A) 15 (B) 20 (C) 25 (D) 30

Question:- Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <5,4,6,2,7>

(A) 156 (B) 154 (C) 158 (D) 157

Question:- Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <5,10,3,12, 5, 50, 6>

Question:- Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <4,10,3,12,20,7>

(A) 1334 (B) 1324 (C)1344 (D)1354

Question:- Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <5,4,3> (for three matrices)

(A) 125 (B) 130 (C) 135 (D) 140

Question:- Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <30,35,15,5,10,20,25> (for six matrices)

(A)7130 (B) 7125 (C) 7145 (D) 7135

Question:- there are 5 items as follows

Items	w_i	v_i
Item1	5 pounds	30$
Item2	10 pounds	20$
Item3	20 pounds	100$
Item4	30 pounds	90$
Item5	40 pounds	160$

The knapsack can hold 60 pounds find the optimal solution

(A) 250$ (B) 260 $ (C) 270 $ (D) 290$

Question:- there are 5 items as follows

Items	w_i	v_i
Item1	5 pounds	30$
Item2	10 pounds	20$
Item3	20 pounds	100$
Item4	30 pounds	90$
Item5	40 pounds	160$

The knapsack can hold 60 pounds find the solution by greedy technique

(A) 230$ (B) 260 $ (C) 220 $ (D) 250$

Question:- what is an optimal Huffman code for alphabeta of the following set of frequencies a: 05, b:48, c:07, d:17, e:10, f:13

(A) 1010 (B)0101 (C) 1001 (D) 1100

(134) the total running time of Huffman on the set of n characters is

(A) O(n) (B) O(n log n) (C) O(n²) (D) O(log n)

Question:- the total running time of matrix chain multiplication of n matrices

(A) ϴ (n⁴) (B) ϴ (n³) (C) ϴ (n²) (D) ϴ (n)

(136) which of the following is true

(A) P is subset of NP (B) NP is subset of P

(Question:- the total running time of optimal binary search tree of n nodes

(A) O(n²) (B) O(n) (C) O(n³) (D) O(n log n)

Question:- If every square of the board is visited, then the total number of knight moves of n-queen problem is

(A) n³-1 (B) n-1 (C)n²-1 (D) log n-1

Question:- If every square of the board is visited, then the total number of knight moves of 4-queen problem is

(A) 14 (B) 15 (C) 16 (D) 12

Question:- If every square of the board is visited, then the total number of knight moves of 8-queen problem is

(A) 64 (B) 62 (C) 61 (D) 63

Question:- In which of the following cases n-queen problem does not exist

(A) n=2 and n=4 (B) n=4 and n=6 (C) n=2 and n=3 (D) n=4 and n=8

Question:- the total running time of knapsack problem for a simple approach

(A) O(n) (B) O( log n) (C) O(2ⁿ log n) (D) O(2ⁿ)

Question:- what is an optimal Huffman code for alphabeta of the following set of frequencies a: 01, b:01, c:02, d:03, e:05, f:8, g:13, h:21

(A) 001010 (B) 001111 (C) 111100 (D) 101010

Question:- what is an optimal Huffman code for alphabet b of the following set of frequencies a: 45, b:13, c:12, d:16, e:9, f:5

(A) 100 (B) 111 (C) 001 (D) 101

Question:- what is an optimal Huffman code for alphabete of the following set of frequencies a: 29, b:25, c:20, d:12, e:05, f:09

(A) 100 0 (B) 1110 (C) 0010 (D) 1011

Question:- Which of the following method is taking overcharge for some operations in amortized analysis?

(A) Aggregate method (B) accounting method

Question:- Which of the following method is most flexible in amortized analysis?

(A) Aggregate method (B) accounting method

(C) potential method (D) both (A) and (B)

Question:- Which of the following method is taken different operations different charges in amortized analysis?

(A) Aggregate method (B) accounting method

Question:- Which of the following method is computing total cost of an algorithm in amortized analysis?

(A) Aggregate method (B) accounting method

Question:- which of the following method is credit as the potential energy to pay for future operations?

(A) Aggregate method (B) accounting method

(C) potential method (D) both (A) and (B)

Question:- If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.

(a)  O(n log n)
(b)  O(n³)
(c)  O(n²)
(d)  O(log n)
(e)  O(n⁴).

Question:- The following is a weighted binary tree, then what is the weighted array for the TVS problem?

(a) [9, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4]
(b) [9, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 6]

(e) [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0]

Question:- The upper bound on the time complexity of the nondeterministic sorting algorithm is

(a) O(n)
(b) O(n log n)
(c) O(1)
(d) O( log n)

Question:- The worst case time complexity of the nondeterministic dynamic knapsack algorithm is

(a) O(n log n)
(b) O( log n)
(c) O(n²)
(d) O(n)

Question:- The time complexity of the normal quick sort, randomized quick sort algorithms in the worst case is

(a) O(n²), O(n log n) (b) O(n²), O(n²)

PPSC Quiz

Breaking News

Algorithm Analysis and Design Solved Quizes

SID

2 comments: