TCS_Digital_D2.pptx for computer science

Tech based questions

1. Topic/Course Sub-Topic (Example: name of college) TCS - Digital MCQs

2. What is the search complexity in direct addressing? A) B) C) D) O(n) O(log n) O(n log n) O(1) Question 1

3. Question 2 What will be the output of the program? #include< stdio.h > int main() { int k=5,*p=&k,**m =&p; printf ("% d%d%d \ n",k ,*p,**p); } D) Error A) 555 B) 55junk C) 5junkjunk

4. In simple chaining, what data structure is appropriate? A) B) C) D) Singly linked list Doubly linked list Circular linked list Binary trees Question 3

5. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is A) B) C) D) log 2n log 2n-1 n/2 n Question 4

6. Question 5 What will be the output of the program? #include< stdio.h > int main() { int k=5,*p=&k,**m =&p; printf ("% d%d%d \ n",k ,*p,**p); }

7. A) B) C) D) Prints all nodes of linked lists Prints all nodes of linked list in reverse order Prints alternate nodes of Linked List Prints alternate nodes in reverse order Question 5

8. A complete n- ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n- ary tree. If L = 41, and I = 10, what is the value of n? A) B) C) D) 6 3 4 5 Question 6

9. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest? A) B) C) D) Union only Intersection, membership Membership, cardinality Union , intersection Question 7

10. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table A) B) C) D) 8, _, _, _, _, _, 10 1, 8, 10, _, _, _, 3 1, _, _, _, _, _,3 1, 10, 8, _, _, _, 3 Question 8

11. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i . 9679, 1989, 4199 hash to the same value ii. 1471, 6171 hash to the same value iii. All elements hash to the same value iv. Each element hashes to a different value A) B) C) D) i only ii only i and ii only iii or iv Question 9

12. Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions? A) B) C) D) (97 × 97 × 97)/100^3 (99 × 98 × 97)/100^3 (97 × 96 × 95)/100^3 (97 × 96 × 95)/(3! × 100^3) Question 10

13. Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020? A) B) C) D) h(i) =i^2 mod 10 h(i) =i^3 mod 10 h(i) = (11 ∗ i^2) mod 10 h(i) = (12 ∗ i) mod 10 Question 11

14. Question 12 What is the output of following function for start pointing to first node of following linked list? 1->2->3->4->5->6 void fun(struct node* start) { if(start == NULL) return; printf ("%d ", start->data); if(start->next != NULL ) fun(start->next->next); printf ("%d ", start->data); }

15. 1 4 6 6 4 1 Question 12 A) 1 3 5 1 3 5 B) 1 2 3 5 C) 1 3 5 5 3 1 D)

16. What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8. A) B) C) D) O(1) and O(n) O(1) and O(1) O(n) and O(1) O(n) and O(n) Question 13

17. Is it possible to create a doubly linked list using only one pointer with every node. A) B) C) D) Not possible Yes, possible by storing XOR of addresses of previous and next nodes Yes, possible by storing XOR of current node and next node Yes, possible by storing XOR of current node and previous node Question 14

18. The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used? A) B) C) D) Singly linked list Circular linked list Doubly linked list Array implementation of list Question 15

19. In a doubly linked list, the number of pointers affected for an insertion operation will be A) B) C) D) 4 1 None of these Question 16

20. Question 17 The following steps in a linked list result in which type of operation? p = getnode () info (p) = 10 next (p) = list list = p

21. Pop operation in stack Question 17 A) Removal of a node B) Insertion of a node C) Modifying an existing node D)

22. The time required to search an element in a linked list of length n is A) B) C) D) O(n) O(log n) O(n^2) Question 18 O(1)

23. The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is A) B) C) D) 284 142 71 Question 19 213

24. Suppose a stack is to be implemented with a linked list instead of an array. What would be the effect on the time complexity of the push and pop operations of the stack implemented using linked list (Assuming stack is implemented efficiently)? A) B) C) D) O(1) for insertion and O(n) for deletion O(n) for insertion and O(1) for deletion O(n) for insertion and O(n) for deletion Question 20 O(1) for insertion and O(1) for deletion

25. What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree? A) B) C) D) O(n) for all O( Logn ) for search and insert, and O(n) for delete O( Logn ) for search, and O(n) for insert and delete Question 21 O( Logn ) for all

26. We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree? A) B) C) D) n! (1/(n+1)).2nCn Question 22 1

27. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree? A) B) C) D) 2 4 6 Question 23 3

28. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the post-order traversal sequence of the same tree? A) B) C) D) 10, 20, 15, 23, 25, 35, 42, 39, 30 15, 20, 10, 23, 25, 42, 35, 39, 30 15, 10, 23, 25, 20, 35, 42, 39, 30 Question 24 15, 10, 25, 23, 20, 42, 35, 39, 30

29. Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined? A) B) C) D) {10, 75, 64, 43, 60, 57, 55} {9, 85, 47, 68, 43, 57, 55} {79, 14, 72, 56, 16, 53, 55} Question 25 {90, 12, 68, 34, 62, 45, 55}

30. When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60? A) B) C) D) 35 128 5040 Question 26 64

31. Which one of the following is an application of Queue Data Structure? Question 27

32. A) B) C) D) When a resource is shared among multiple consumers. When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes Load Balancing All of the above Question 27

33. Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct? A) B) C) D) d(r, u) < d (r, v) d(r, u) <= d (r, v) None of the above Question 28 d(r, u) > d(r, v)

34. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ? A) B) C) D) n(n-l)/2 n! 2^(n(n-1)/2) Question 29 2^n

35. Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three? A) B) C) D) 1/8 7 8 Question 30 1

36. Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is A) B) C) D) E V 2V Question 31 2E

37. Consider a directed graph with n vertices and m edges such that all edges have same edge weights. Find the complexity of the best known algorithm to compute the minimum spanning tree of the graph? A) B) C) D) O( m+n ) O(mn) O(n log m) Question 32 O(m log n)

38. Question 33 Consider the following C program segment. What is the value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as an argument? struct CellNode { struct CelINode * leftchild ; int element; struct CelINode * rightChild ; }

39. Question 33 int Dosomething (struct CelINode * ptr ) { int value = 0; if ( ptr != NULL) { if ( ptr -> leftChild != NULL) value = 1 + DoSomething( ptr -> leftChild ); if ( ptr -> rightChild != NULL) value = max(value, 1 + DoSomething( ptr -> rightChild )); } return (value); }

40. The number of leaf nodes in the tree Question 33 A) The number of leaf nodes in the tree B) The number of internal nodes in the tree C) The height of the tree D)

41. Which data structure is most efficient to find the top 10 largest items out of 1 million items stored in file? A) B) C) D) Min Heap BST Sorted array Question 34 Max Heap

42. The most appropriate matching for the following pairs is X : DFS 1 : Heap Y : BFS 2 : Queue Z : Sorting 3 : Stack A) B) C) D) X - 1 Y - 2 Z-3 X - 3 Y - 2 Z-1 X - 2 Y - 3 Z-1 Question 35 X - 3 Y - 1 Z-2

43. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? A) B) C) D) Circular linked list Stack Priority Queue Question 36 Queue

44. Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is A) B) C) D) 80 8000 1.25 Question 37 0.0125

45. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below. Which one of the following choices gives a possible order in which the key values could have been inserted in the table? A) B) C) D) 46, 42, 34, 52, 23, 33 34, 42, 23, 52, 33, 46 34, 42, 23, 52, 33, 46 42, 46, 33, 23, 34, 52 Question 38

46. What is the time complexity of Build Heap operation. Build Heap is used to build a max(or min) binary heap from a given array. Build Heap is used in Heap Sort as a first step for sorting. A) B) C) D) O(n Log n) O(Log n) O(n) Question 39 O(n^2)

47. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap? A) B) C) D) 25,12,16,13,10,8,14 25,14,16,13,10,8,12 25,14,12,13,10,8,16 Question 40 25,12,16,13,10,8,14

48. In a binary max heap containing n numbers, the smallest element can be found in time ? A) B) C) D) O(n) O(log log n) O(1) Question 41 O(log n)

49. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0. A) B) C) D) 2 4 5 Question 42 3

50. Which of the following is a self-adjusting or self-balancing Binary Search Tree ? A) B) C) D) Splay Tree Red Black Tree All of the above Question 43 AVL Tree

51. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the reversal ordering on natural numbers i.e. 9 is assumed to be smallest and 0 is assumed to be largest. The in-order traversal of the resultant binary search tree is. A) B) C) D) 9, 8, 6, 4, 2, 3, 0, 1, 5, 7 0, 2, 4, 3, 1, 6, 5, 9, 8, 7 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 Question 44 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

52. Question 45 Consider the following function to traverse a linked list. Which of the following is FALSE about above function? void traverse(struct Node *head) { while (head->next != NULL) { printf ("%d ", head->data); head = head->next; } }

53. The function may crash when the linked list is empty. Question 45 A) The function doesn't print the last node when the linked list is not empty. B) The function is implemented incorrectly because it changes head. C) None of the above D)

54. In Linear Probing of hash table, consider a simple hash function as “key mod 8” and sequence of keys as 55, 77, 78, 15, 92, 81,19, 29 is inserted in hash table, Three insertion is already happen, Where will be the 4th insertion happen? A) B) C) D) 7 th index 1 st index 6 th index Question 46 th index

55. Consider a hash table of size seven, with starting index zero, and a hash function (4x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table. A) B) C) D) 1, 3, 8, 10, _, _, _ _, 1, 3, 8, 10, _, _ 1, 10, 8, _, _, _, 3 Question 47 1, 8, 10, _, _, _, 3

56. A hash function h defined h(key)=key mod 7, with quadratic probing, is used to insert the keys 76, 93, 40, 47 into a table indexed from 0 to 6. What will be the location of key 47? A) B) C) D) 6 3 Question 48 5

57. A hash function h defined h(key)=key mod 7, with double hashing, is used to insert the keys 76, 93, 40, 47, 10, 55 into a table indexed from 0 to 6. What will be the location of key 55? A) B) C) D) 6 1 Question 49 4

58. The maximum number of binary trees that can be formed with two unlabeled nodes is: A) B) C) D) 1 4 2 Question 50 3

59. Which one of the following is an application of Graph Data Structure? A) B) C) D) Facebook Google maps All of the mentioned options Question 51 World wide web

60. The number of elements in the adjacency matrix of a graph having 8 vertices is ______________ A) B) C) D) 8 36 64 Question 52 16

61. What would be the number of zeros in the adjacency matrix of the given graph? A) B) C) D) 7 18 25 Question 53 17

62. Consider the following graph starting at node 0. In the given graph, what order will the nodes be visited using a Breadth First Search?  Question 54 B) 0 2 1 3 5 4 C ) 0 1 3 4 5 2 A) 1 2 3 4 5 D) 0 1 2 3 5 4

63. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are A) B) C) D) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT Question 55 Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

64.  In a circular queue, how do you increment the rear end of the queue? A) B) C) D) rear++ ( rear%MAX_SIZE )-1 rear-- Question 56 (rear+1)%MAX_SIZE

65. Consider the following operations are performed on a stack of size 5. Push(5); Push(6); Pop(); Push(5); Push(6); Pop(); Pop(); Pop(); Push(6); Pop() After the completion of all operations, which of the following is the sequence of popped out values. Question 57

66. 6, 6, 5, 6, 6 Question 57 A) 6, 6, 5, 5, 6 B ) 5, 5, 6, 6, 6 C) 6, 6, 5, 6, 5 D )

67. Which of the following is prefix notation of ABC/-AK/L-* ? A) B) C) D) -*/ABC-/AKL *-A/BC-/AKL None of the mentioned options Question 58 *-/-/ABCAKL

68. Which of the following sorting algorithms has the highest best case time complexity using array data structure ? A) B) C) D) Heap sort Bubble sort Selection sort Question 59 Insertion sort

69. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is: A) B) C) D) n / 2 (n – 1) / 2 (2n + 1) / 3 Question 60 (n – 1) / 3

70. Which of the following is not an in-place algorithm? A) B) C) D) Insertion sort Merge sort Heap sort Question 61 Selection sort

71. Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals? A) B) C) D) Preorder and Inorder Inorder and Postorder None of the mentioned options Question 62 Preorder and Postorder

72. Given a binary-max heap. The elements are stored in an arrays as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations? A) B) C) D) 14, 13, 8, 12, 10 14, 13, 12, 10, 8 14, 12, 13, 10, 8 Question 63 14, 13, 12, 8, 10

73. Eesha is developing a word processor in which she want to implement “auto complete” feature. With this feature as and when we start typing a word, the word processor will suggest the rest of the word to implement this, what data structure is most suitable? A) B) C) D) Array Trie Stack Question 64 List

74. The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is: A) B) C) D) 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12 Question 65 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12

75. A binary search tree is generated by inserting in order the following integers : 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24 The number of nodes in the left subtree and right subtree of the root respectively is A) B) C) D) (4, 7) (8, 3) (3, 8) Question 66 (7, 4)

76. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree? A) B) C) D) (1 2 (4 5 6 7)) (1 (2 3 4)(5 6 7)) (1 (2 3 NULL) (4 5)) Question 67 ( 1 ((2 3 4) 5 6) 7)

77. The maximum number of binary trees that can be formed with three unlabeled nodes is: A) B) C) D) 1 4 3 Question 68 5

78. A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted? A) B) C) D) 2 4 6 Question 69 3

79. Among the following, which of these are applications of a double ended queue? A) B) C) D) Steal scheduling algorithm Remove the entries after some time All of the mentioned options Question 70 Undo list of activities

80. The inorder and preorder traversal of a binary tree are d b e a f c g and  a b d e c f g, respectively. The post-order traversal of the binary tree is:  d e b f g c a Question 71 A) d e f g b c a B ) e d b f g c a C) e d b g f c a D )

81. Riyaz has a book of tickets and wants to store ticket numbers in a data structure. New tickets are added to the end of the booklet. Ticket at the top of the stack is issued to the customer. Which data structure should Riyaz use to represent the ticket booklet? Question 72 B) Queue C ) Array A) Stack D) Linked List

82. A is an empty stack. The following operations are done on it. PUSH(1) PUSH(2) POP PUSH(5) PUSH(6) POP What will the stack contain after these operations? Question 73 B) 1 6 C ) 1 5 A) 5 6 D) 2 6

83. A queue is implemented as a singly-linked-list for easy addition and deletion of elements. Each node has an element and a pointer to another node. Which node will point to empty/no location? Question 74 B) Front C ) Both A and B A) Rear D) None of the mentioned

84. What is common in three different types of traversals ( Inorder , Preorder and Postorder )? Root is visited before right subtree Question 75 A) Left subtree is always visited before right subtree B ) Root is visited after left subtree C) None of the mentioned D )

85. Choose the correct answer. Afzal writes a piece of code, where a set of three lines occur around 10 times in different parts of the program. What programming concept can he use to shorten his program code length? Question 76

86. Use for loops A) Use functions B ) Use arrays C) Use classes D )

87. Question 77 Choose the correct answer. function g( int n) { if (n > 0) return 1; else return -1; } function f( int a, int b) { if (a > b) return g(b-a); if (a < b) return g(a-b); return 0; }

88. If in the given program f(a, b ) is called, what is returned? A) Always -1 B ) 1 if a>b, -1 if a<b, 0 otherwise C) -1 if a>b, 1 if a<b, 0 otherwise D ) 0 if a equals b, -1 otherwise

89. Ravi and Rupali are asked to write a program to sum the rows of 2X2 matrices stored in the array A . Ravi writes the following code ( CodeA ): for n=0 to 1 sum Row1[n]=A[n][1]+A[n][2] end Rupali writes the following code ( CodeB ): sum Row1[0]=A[0][1]+A[0][2] Sum Row1[1]=A[1][1]+A[1][2] Comment upon these codes ( Assume no loop¬ unrolling done by compiler): Question 78

90. Which of the following is/are complete binary tree? Question 79

91. A) B) C) D) None of the mentioned options

92. Which of the following is a max-heap?  Question 80

93. A) B) C) D)

94. THANK YOU