# Data Structures Test

**A simple graph with n vertices and k components can have at the most _______.**

a. n edges

b. n-k edges

c. (n-k)(n-k-1)/2 edges

**d. (n-k)(n-k+1)/2 edges**

**In an AVL tree, if the balance factor of a node is -1, which of the following statement/s is/are true?**

a. The left sub tree is larger than the right

b. The right sub tree is larger than the left

c. The tree is invalid

d. None of the above

**How many real links are required for a sparse matrix having 10 rows, 10 columns and 15 non-zero elements? (Pick the nearest answer)**

**a. 15**

b. 20

c. 50

d. 100

**Which statement is true for a B-tree?**

a. All entries of a node are greater than or equal to the entries in the node’s children

b. All leaves are exactly at the same depth

c. All nodes contain exactly the same number of entries

d. All non-leaf nodes have exactly the same number of children

**Which of the following is false?**

a. A binary search begins with the middle element in the array

b. A binary search continues halving the array either until a match is found or until there are no more elements to search

**c. If the search argument is greater than the value located in the middle of the array/sub-array, the binary search continues in that half of the array/sub-array whose all elements are smaller than the middle element.**

**Which of the following sorting algorithms yield approximately the same worst-case and average-case running time behavior in O(n*log(n))?**

a. Bubble sort and selection sort

**b. Heap sort and merge sort**

c. Quick sort and radix sort

d. Tree sort and Median-of-3 quicksort

**In which data structure do the insertion and deletion take place at the same end?**

a. Linked list

b. Tree

**c. Stack**

d. Linked list of stack

**Which queue allows insertion and deletion at both ends?**

a. Simple queue

**b. Circular queue**

c. Dequeue

d. Special queue

**What will happen if in data structure a pop operation on the stack causes the stack pointer to move past the origin of the stack?**

a. Overflow

**b. Underflow**

c. Null

d. Garbage collection