Courses

# Miscellaneous Topics (Basic Level) - 1

## 10 Questions MCQ Test Question Bank for GATE Computer Science Engineering | Miscellaneous Topics (Basic Level) - 1

Description
This mock test of Miscellaneous Topics (Basic Level) - 1 for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Miscellaneous Topics (Basic Level) - 1 (mcq) to study with solutions a complete question bank. The solved questions answers in this Miscellaneous Topics (Basic Level) - 1 quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Miscellaneous Topics (Basic Level) - 1 exercise for a better result in the exam. You can find other Miscellaneous Topics (Basic Level) - 1 extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

### If a node has K children in B tree, then the node contains exactly keys.

Solution:

If, a node has K children in B-tree, then the node contains exactly K - 1 keys

QUESTION: 2

### The time complexity of the following C function is, (assume n> 0) int recursive (int n ) { if ( n = = 1) return (1); else return (recursive ( n - 1) + recursive ( n - 1)); }

Solution:

T(n) = T ( n - 1) + T ( n - 1)+1
[recursive (n - 1) = T( n - 1)]
= 2T( n - 1)+1 = O(2n [using substitution method]

QUESTION: 3

### The number of spanning trees for a complete graph with seven vertices is

Solution:

Number of spanning tree possible with n-node = nn-2
Given, n = 7
Total number of spanning trees = 75

QUESTION: 4

if one uses straight two-way merge sort algorithm to sort the following elements in ascending order:
20, 47, 15, 8, 9, 4, 40, 30, 12, 17
Then the order of these elements after second pass of the algorithm is

Solution:

Given array:

So, the order of elements after second pass of the algorithm is 8,15,20,47, 4,9,30,40,12,17

QUESTION: 5

Consider the following sorting algorithms:
1. Quicksort
2. Heapsort
3. Mergesort

Which of them perform in least time in the worst case?

Solution:

Worst case time complexity of Quick sort
= O(n2) when input is already sorted,
Worst case time complexity of Heap sort = O(n log n).
Worst case time complexity of Merge sort = O(n log n).

QUESTION: 6

The number of articulation points of the following graph is:

Solution:

An articulation point (or cut vertex) is that vertex removing which (along with its edges) disconnects the graph.

Therefore number of articulation points is 3.

QUESTION: 7

Consider the following tree:

If the post order traversal gives ab - cd* + then the label of the nodes 1,2, 3, ... will be

Solution:

Post order traversal = a b - cd*+. As we know that post order traversal goes in the order of LEFT CHILD - RIGHT CHILD - PARENT  (ROOT)

Hence, Label of 4,5,2 will be a, b, - respectively
Label of 6,7,3 will be c, d, - respectively

Label of 1 will be +

QUESTION: 8

The expression tree given in figure evaluates to 1, if

1. a = - b and e = 0
2. a = - b and e = 1
3. a = b and e = 0
4. a = b and e = 1

Solution:

The corresponding expression is - (- a - b) + e!
This is 1 if a = - b and e is either 1 or 0, since 1! = 0! = 1

QUESTION: 9

Match List-I with List-ll and select the correct answer using the codes given beiow the lists:
List-I
A. All pairs shortest path
B. Quick sort
C. Minimum weight spanning tree
D. Connected Components
List-ll
1. Greedy
2. Depth-first search
3. Dynamic programming
4. Divide and conquer

Solution:

All pairs shortest path is find using Floyd Warshall algorithm, which is an example of dynamic programming.

• Quick sort and merge sort are example of “divide and conquer” algorithms.
• MST or minimum weight spanning tree is a tree with a subset of edges such that it connects all vertices and summation of edge weight is minimum Prim’s algo and Kruskal’s algorithm are used for this, which are examples of greedy approach.
• By using Depth First Search (DFS) one can easily find set of connected components.
QUESTION: 10

Consider the following tree:

If this tree is used for sorting, then a new number 8 should be place as the

Solution:

Since the tree is used for sorting hence taking INORDER TRAVERSAL (Left-Root-Right) we have 8 placed at the left child of the node labeled 10.