PART I$)(25$ points$)$ Answer the following multiple choice questions,

Which of the following operations is performed more efficiently by doubly linked list than by singly linked list?

$($A$)$ Deleting a node whose location is given

$($B$)$ Searching of an unsorted list for a given item

$($D$)$ Traverting a node after the node with given location

A

A characteristic of the data that the binary search uses but the linear search ignores is

$($A$)$ Type of elements of the list

$($B$)$ Length of the list

$($C$)$ Maximum value in list

$($D$)$ Order of the elements of the list

D

Which data structure is used for implementing recursion?

$($A$)$ Queue

$($B$)$ Arrays

$($C$)$ Stack

$($D$)$ List

C

In the binary search algorithm, the average number of comparisons required for searching an element in a list of $n$ numbers scales as

$($A$)lo{g}_{2}n$

$($B$)\frac{n}{2}$

$($C$)n$

$($D$)n-1$

A

In the Quicksort algorithm, the average number of comparisons required for sorting a list n numbers scales as

$($A$)lo{g}_{2}n$

$($B$)nlo{g}_{2}n$

$($C$)$ n

$($D$)n^2$

B