These multiple choice questions related to computer science. These Mcqs are given from the Data structure book which will helps to prepare you for the test and learn basic knowledge about data stucture.
3.The initial configuration of a queue is a,b,c,d (a in the front end).To get the configuration d,c,b,a, one need a minimum of
(a) 2 deletions 3 addtions
(b) 3 deletions 2 addtions
(c) 3 deletions 3 addtions
(d) 3 deletions 4 addtions
4.The number of possible ordered tree with 3 nodes A,B,C is
5.The number of swappings needed to sort the number 8,22,7,9,31,19,5,13 in ascending order,bubble sort is
6.Given two sorted list of size ‘m’ and ‘n’ respectively.The number of comparisons needed in the worst case by the merge sort algorithm will be
(a) m x n
(b)maximum of m,n
(c)minimum of m,n
(d)m + n-1
7.If the sequence of operations push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop are perform on a stack, the sequence of popped out value are
9.A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves
(a)cannot have more than 19 nodes
(b)has exactly 19 nodes
(c)has exactly 17 nodes
(d) cannot have more than 17 nodes
10.The depth of complete binary tree with ‘n’ nodes is (log is to the base two)
(d) log(n) +1
11.Preorder is same as
(a)depth first order
12.Which of the following traversal techniques list the nodes of a binary search tree in ascending order
(d) None of the above
13.The average successful search time taken by binary search on a sorted array of 10 items is
14.A hash function f defined as f(key)=key mod 7, with linear probing, is used to insert the keys 37,38,72,48,98,11,56, into a table indexed from 0 to 6.What will be the location of the key 11?
15.The average successful search time for sequential search on ‘n’ items is
16.The running time of an algorithm T(n),where ‘n’ is the input size is given by
T(n)=8T(n/2)+qn, if n>1
p, if n=1
Where p,q are constants.The order of this algorithm is.
17.Let m,n be positive integers.Define Q(m,n)as
Q(m,n)=0 if m<n
Q(m-n,n)+p, if m> or = n
Then Q(m,3) is (a div b,gives the quotient when a is divided by b)
(b)p x (m mod 3)
(c)p x (m div 3)
18.Six files F1,F2,F3,F4,F5, and F6 have 100,200,50,80,120,150 number of records respectively. In what order should they be stored so as to optimized access time? Assume each file is accessed with the same frequency.
(d)Ordering is immaterial as all files are accessed with the same frequency
19.In Qn, ///18, the average access time wiil be
20.An algorithm is made up od 2 modules M1, M2. If order M1 is f(n) and M2 is g(n) than the order of the algorithm is
(c)f(n) + g(n)
(d)f(n) x g(n)
21.The concept of order (Big O) is important because
(a)It can be used to decide the best algorithm that solves a given problem
(b)it determined the maximum size ofa problem that can be solved in a given system,in a given amount of time
(c)it us the lower bound of the growth rate of the algorithm
(d)none of the above
22.The running time T(n), where ‘n’ is the input size of a recursive algorithm is given as
The order of the algorithm is
23.There are 4 different algorithms A1,A2,A3,A4 to solve a given problem with the order log(n), log(log(n)), nlog(n), n/log(n) respectively.which is the best algorithm
24.The number of the possible binary tree with 3 nodes is
25.The number of the possible binary tree with 4 nodes is
26.The time complexity of an algorithm T(n),where n is the input size is given by
T(n)=T(n-1)+1/n, if n>1 otherwise
The order of the algorithm is
27.Sorting is useful for
(b)minimizing the storage needed
(c)making searching easier and efficient
(d) responding to queries easily
28.Choose the correct statement.
(a)Internal sorting is used if the number of itmes to be sorted is very large
(b)External sorting is used if the number of itmes to be sorted is very large
(c)External sorting needs auxiliary storage
(d)Internal sorting needs auxiliary storage
29.A sorting technique that guarantees, that records with the same primary key occure in the same order in the sorted lis as in the orignal unsorted is list is said to be
30.A tax is made up of the characters a,b,c,d,e each occurring with the probability 12, 4, 15, 08, and 25 respectively.The optimal coding technique will have the average length of
31.In the previous question, which of the following character will have codes of length 3?
(c)b and c
32.The running time of an algorithm is given is
T(n)=T(n-1)+T(n-2)-T(n-3), if n>3
The order of this algorithm is
33.What should be the relation between T(1),T(2) and T(3), so that Qn.32 gives an algorithm whose order is constant?
34.The Ackermann’s function
(a)has quadratic time complixity
(b)has exponential time complexity
(c)can’t be solved iteratively
(d)has algorithm time complexity
35.The order of algorithm that finds whether a given boolean function of ‘n’ variables, produces a 1 is
37.The way card game player arranges his card as he picks them up one by one, is example of
38.You want a check whethere a given set of items is sorted. Which of the following sorting methods will be the most efficient if it is already in sorted order?
39.The average number of comparisons performed by the merge sort algorithm, in merging two sorted lists of length 2 is
40.Which of the following sorting methods will be the best if the number of swappings done,is theonly measure of effeciency?
41.You are asked to sort 15 randomly generated number. You should prefer
42.A part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in propper order, at the end of each day. The ideal choise will be
43.The maximum number of comparisons needed to sort 7 items using radix sort is (assume each itmes is a 4 digit decimal number)
44.Which of the following algorithm exhibits the unnatural behavior that, maximum number of comparison are needed if the list to be sortd is in the reverse order and maximum number of comparisons are needed if they are already in sorted order?
(c)Binary insertion sort
(d)There can’t be any such sorting method
45.Which of the following sorting algorithm has the worst time complexity of nlog(n)?
46.Which of the following sorting methods sorts a given set of items that is already in sorted order or in reverse sorted order with equal speed?
47.Which of the following algorithm solves the all-pair shortest path problem?
53.The information about an array that is used in a program will be stored
54.Which of the following expression accesses the (i,j)entry of a (m x n) matrix stored in column major form?
(a)n x (i-1) + j
(b)m x (j-1) + i
(c)m x (n-j) + j
(d)n x (m-i) + j
55.Sparse matrices have
(a)many zero entries
(b)many non-zero entries
(d)non of the above
81. The postfix expression for the infix expression A + B* (C+ D) / F + D*E is:
(a) AB + CD + *F / D + E*
(b) ABCD + *F / + DE* +
(c) A*B + CD / P*DE + +
(d) A + *BCD / F*DE + +
82. Which of the following statements is true?
1. As the number of entries in the hash table increases, the number of collisions increases.
2 Recursive programs are efficient.
3 The worst time complexity of quick sort is 0(n2).
4. Binary search implemented using a linked list is efficient.
(a) I and II
(b) II and III
(c) I and IV
(d) 1 and III
83. The number of binary trees with 3 nodes which when traversed in post-order gives the sequence A, B, C is
84. The minimum number of colors needed to color a graph having n (>3) venicn and 2 edges is
85. Which of the following file organizations is preferred for secondary key processing?
(a) Indexed sequential file organization
(b) Two-way linked list
(c) Inverted file organization
(d) Sequential file organization
86. Mr. Pool designed a crazy language called STUPID that included the following features.
+ has precedence over /
/ has precedence over – (binary)
– (binary) has precedence over *
* and ^ (exponentiation) have the same precedence.
+ and * associate from right to left.
The rest of the mentioned operators associate from left to right. Choose the correct stack priorities Mr. Fool should assign to +, * , ^ / respectively, for correctly convening an arithmetic expression in infix form to the equivalent postfix form.
(a) 5. 1. 2, 4
(b) 5. 5. 2.4
(c) 1. 1, 2.4
(d) 5. 4. 3. 1
87. The infix priorities of +, * , ^, / could be
(a) 5, 1, 2. 7
(b) 7.5. 2. 1
(c) 1. 2. 5. 7
(d) 5.2. 2.4
88. Mr. Fool’s STUPID language will evaluate the expression 2 • 2 ^ 3 * 4 to
89. The expression 1* 2 ^ 3*• 4 ^ 5 * 6 will be evaluated to
(a) 32^30 (b) 162^30 (c) 49152
90. In a circularly linked list organization, insertion of a record involves the modification of
(a) no pointer
(b) 1 pointer
(c) 2 pointers
(d) 3 pointers
91. Stack is useful for implementing
(a) radix sort
(b) breadth first search
(d) depth first search
92. To store details of an employee, a storage space of 100 characters is needed. A magnetic tape with a density of 1000 characters per inch and an inter-record gap of 1 inch is used to store information about all employees in the company. What should be the blocking factor so that the wastage does not exceed one-third of the tape?
93. A machine needs a minimum of 100 sec to sort 1000 names by quick sort.na.1The minimum time needed to sort 100 names will be approximately
(a) 50.2 sec
(b) 6.7 sec
(c) 72.7 sec
(d) 11.2 sec
94. A machine took 200 sec to sort 200 names, using bubble sort. in 800 sec. it can approxi-mately sort
(a) 400 names
(b) 800 names
(c) 750 names
(d) 800 names
95. The correct order of arrangement of the names Bradman, Lamb, May, Boon, Border, Underwood and Boycott, so that the quicksort algorithm makes the least number of com-parisons is
(a) Bradman, Border, Boon, Boycott. May, Lamb, Underwood
(b) Bradman, Border, Boycott, Boon, May, Underwood, Lamb
(c) Underwood, Border, Boon Boycott, May, Lamb, Bradman
(d) Bradman, May, Lamb, Border, Boon, Boycott, Underwood
96. Which of the following is useful in traversing a given graph by breadth first search?
97. Which of the following is useful in implementing quick sort?
98. Queue can be used to implement
(a) radix sort
(b) quick sort
(d) depth first search
100. A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the m^th record is the first record to result in collision is
(a) (x-1) (x-2)…(x-(m-2))(m-1)/ x^m-1
(b) (1-1) (x-2)…(x-(m-1)Xm–1)/ x^m-1
(c) (x-1) (x-2)…(x-(m-2))(m-1)/ x^m
(d) (x-1) (x-2)…(x-(m-1)(m-1)/ x^m
101. The process of accessing data stored in a tape is similar to manipulating data on a
102. If the hashing function is the remainder on division. then clustering is more likely to occur if the storage space is divided into 40 sectors rather than 41. This conclusion is
(a) more likely to be false
(b) more likely to be true
(c) is always false
(d) none of the above
103. Unrestricted use of goto is harmful, because it
(a)makes debugging difficult
(b)increases the running time of programs
(c)increases memory requirement of programs
(d)results in the compiler generating longer machine code
104.The maximum degree of any vertex in a simple graph with n vertices is
105.The recurrence relation that arises in relation with the complexity of binary search is
(a)T(n) = T(n/2) + k, where k is a constant
(b)T(n) = 2T(n/2) + k, where k is a constant
(c)T(n)=T(n/2) + log(n)
(4)T(n) = T(n/2) + n
106.An item that is read as input can be either pushed to a stack and later popped and printed, or printed directly. Which of the following will be the output if the input is the sequence of items – 1,2,3,4,5?
(a) 3, 4, 5, 1, 2
(b) 3, 4, 5, 2, 1
(c) 1, 5, 2, 3, 4
(d) 5, 4, 3, 1, 2
107.Which of the following algorithm design technique is used in the quick sort algorithm?
(a) Dynamic programming
(c) Divide and conquer
(d) Greedy method
108.Linked lists are not suitable for implementing
(a) insertion sort
(b) binary search
(c) radix sort
(d) polynomial manipulation
109.Which one of the following statements is false?
(a)Optimal binary search tree construction can be performed efficiently using dynamic programming.
(b)Breadth-first search cannot be used to find connected components of a graph.
(c)Given the prefix and postfix walks of a binary tree, the binary tree cannot be uniquely reconstructed.
(d)Depth-first search can be used to find the connected components of a graph.
110.The number of edges in a regular graph of degree d and n vertices is
(a) maximum of n, d
111. Consider the following two (unctions.
f (n) n3, if 0<or=to n < 10,000
g (n)=n„if O<or=to n <100
Which of the following is/are true?
(a) f(n) is 0(n3)
(b)g(n) is 0(n3)
(c) O(f(n)) is same as 0(g(n)) (d) g(n) is 0(n2)
112. A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will be
113. The concatenation of two lists is to be performed in 0(1) time. Which of the following implementations of a list could be used?
(a) Singly linked list
(b) Doubly linked list
(c) Circular doubly linked list
(d) Any implementation of list
114. The correct matching for the following pain is
(A)All pairs shortest path (1) Greedy
(B)Quick sort (2) Depth-first search
(C)Minimum weight spanning tree (3) Dynamic programming
(D)Connected Components. (4)Divide and conquer
(a) A-2, B-4, C-1, D-3 (b) A-3, B-4, C-I, D-2
(c) A-3, B-4, C-2, D-1 (d) A-4, B-1, C-2, D-3
115. Which of the following is essential for converting an infix expression to the postfix form efficiently?
(a) An operator stack
(b) An operand stack
(c) An operator stack and an operand stack
(d) A parse tree
•116. A binary search tree contains the values – 1, 2. 3. 4, 5. 6. 7, and 8. The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output?
118.Which of the following need not be a binary tree?
(a) Search tree
*119. Assume 5 buffer pages are available to sort a file of 105 pages. The cost of sorting using m-way merge son is
Check Also: Database Management Systems MCQS
Source link : https://books.google.com.pk/books?id=5tatBaRplIgC&pg