Data Structures and Algorithms Quiz # 6

A binary tree, all the levels of which except possibly the last have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as:

Full binary tree

2-Tree

Threaded tree

Complete binary tree

Which of the following operations is more expensive in the dynamically created linked list than it is in the conventional array?

Finding Kth element

Insertion

Deletion

Traversing

In a selection sort algorithm, the number of passes required to perform the sort are ______.

N

N-1

N-2

N^2

Quicksort is run on two inputs shown below to sort them in the ascending order.

i) 1,2,3,...n
ii) n,n-1,n-2,...2,1

If C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively, then

C1

C1>C2

C1=C2

You cannot say anything for arbitrary n

What kind of list is the best to answer questions such as "Which is the item at position n?"

Lists implemented with an array

Doubly-linked lists

Singly-linked lists

Doubly-linked or singly-linked lists are equally good

The breadth-first traversal (BFS) is a method to traverse______

all successors of a visited node before any successors of any of those successors

a single path of the graph as far as it can go

the graph using the shortest path

none of these

Let A be a sorted array of n=10 elements. Assume that only one comparison is required to determine whether the target is equal to, less than, or greater than A[i]. Which of the following denotes the average successful time of finding an arbitrary element x in A using the binary search?

1.6

2.9

4.2

5.5

Which of the following tree traversal techniques reads the root before its children nodes?

In order

Pre-order

Post-order

None of the above

Which of the following operations is more expensive in the array implementation of the linked list than it is in the dynamically created linked list?

Insertion

Traversing

Searching

None

Which of the following stack operations could result in a stack underflow?

is_empty

pop

push

Two or more of the above answers

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

The left sub tree is larger than the right

The right sub tree is larger than the left

The tree is invalid

None of the above

Which statement is true for a B-tree?

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

All leaves are exactly at the same depth

All nodes contain exactly the same number of entries

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

What is the minimum number of nodes in a full binary tree with height 3?

4

7

11

15

Which of these is the correct big -Oh expression for 1+2+3+...+n?

O(log n)

O(n)

O(n log n)

O(n2)

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

log 2 n

n/2

log 2 n – 1

n

What should be added in place of "/ADD A STATEMENT HERE/", so that the function correctly reverses a linked list.

*head_ref = prev;

*head_ref = current;

*head_ref = next;

*head_ref = NULL;

Is it possible to create a doubly linked list using only one pointer with every node.

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

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?

union only

intersection, membership

membership, cardinality

union, intersection

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

Deleting a node whose location is given

Searching an unsorted list for a given item

Inserting a node after the node with a given location

Traversing the list to process each node

The time required to search an element in a linked list of length n is

O (log n)

O (n)

O (1)

O(n2)

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

Insertion Sort

Quick Sort

Heap Sort

Merge Sort

Assume that reference of head of following doubly linked list is passed to above function 1 <--> 2 <--> 3 <--> 4 <--> 5 <-->6. What should be the modified linked list after the function call?

2 <--> 1 <--> 4 <--> 3 <--> 6 <-->5

5 <--> 4 <--> 3 <--> 2 <--> 1 <-->6.

6 <--> 5 <--> 4 <--> 3 <--> 2 <--> 1.

6 <--> 5 <--> 4 <--> 3 <--> 1 <--> 2

Which of the following points is/are true about Linked List data structure when it is compared with array

Arrays have better cache locality that can make them better in terms of performance.

It is easy to insert and delete elements in Linked List

Random access is not allowed in a typical implementation of Linked Lists

The size of array has to be pre-decided, linked lists can change their size any time.

All of the above

A heuristic is a(n) ____.

Analytical technique based on self-knowledge and self-reflection

Precise, step-by-step set of rules that will reliably generate a solution to a problem

Technique to improve memory and mental processing

Shortcut to problem solving, also known as a rule of thumb

A member function that is declared ________ may not access any non-static data members in the class

Private

Public

Static

Inline

None of these

A(n) ________ informs the compiler that a class will be declared later in the program.

Forward declaration

This pointer

Overloaded

Copy constructor

Each object of a class has its own copy of the class's ________.

Member functions

Member variables

Constructor and destructor functions

All of these

None of these

Every element in an array is assigned a unique number known as a ________.

Number

Character

Subscript

Integer

In a truth table, the expression ____ is false.

True OR true

True OR false

False OR false

False OR true.

In a truth table, the expression ____ is true

True and true

True and false

False and false

False and true.

Quiz:	Data Structures and Algorithms Quiz # 6
Total Questions:	30 MCQs
Time:	30 Minutes