Design and Analysis of algorithms Quiz 1 PDF

Preview

Summary

Quiz 1 for Design and Analysis of Algorithms...

Description

Design and Analysis of ALGORITHMS (CS304) 1. How many children does a binary tree have? a. b. c. d.

2 0 or 1 or 2 0 or 1 Any number of children

2. What is/are the disadvantages of implementing tree using normal arrays? a. b. c. d.

difficulty in knowing children nodes of a node difficult in finding the parent of a node have to know the maximum number of nodes possible before creation of trees All of the above

3 . What is the time complexity of searching for an element in a circular linked list? a. b. c. d.

O(n) O(nlogn) O(1) O(n2)

4. Which of the following application makes use of a circular linked list? a. b. c. d.

Undo operation in a text editor Recursive function calls Allocating CPU to resources Implement Hash Tables

5. Which of the following is false about a circular linked list? a. b. c. d.

Every node has a successor Time complexity of inserting a new node at the head of the list is O(1) Time complexity for deleting the last node is O(n) We can traverse the whole circular linked list by starting from any point

6. This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Doubly Linked List” a. b. c. d.

Which of the following is false about a doubly linked list? We can navigate in both the directions The insertion and deletion of a node take a bit longer Implementing a doubly linked list is easier than singly linked list

7. What is a memory efficient double linked list? a. b. c. d.

Each node has only one pointer to traverse the list back and forth The list has breakpoints for faster traversal An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list A doubly linked list that uses bitwise AND operator for storing addresses

8. The main measure for efficiency algorithm area. b. c. d.

Processor and Memory Complexity and Capacity Data and Space Time and space

9. Examples of O(1) algorithms are_____ a. b. c. d.

Multiplying two numbers. Assigning some value to a variable Displaying some integer on console All of the Above

10. How many passes are required to sort a file of size n by bubble sort method? a. b. c. d.

N-1 N/2 N None of the above

11. What does the algorithmic analysis count? a. b. c. d.

The number of arithmetic and the operations that are required to run the program The number of lines required by the program The number of seconds required by the program to execute None of these

12. The time complexity of binary search is a. b. c. d.

O(1) O(log n) O(n) O(n logn)

13. In quick sort, the number of partitions into which the file of size n is divided by a selected record is a. b. c. d.

n n-1 2 n/2

14. How many passes are required to sort a file of size n by bubble sort method? a. b. c. d.

N2 N N-1 N/2

15. The worst-case time complexity of Quick Sort is a. b. c. d.

O(n2) O(log n) O(n) O(n logn)

16. The worst-case time complexity of Merge Sort is a. b. c. d.

O(n2) O(log n) O(n) O(n logn)

17. Which of the following sorting procedures is the slowest? a. b. c. d.

Quick sort Heap sort Shell sort Bubble sort

18. Two main measures for the efficiency of an algorithm are a. b. c. d.

Time and space Processor and memory Complexity and capacity Data and Space

19. Which of the following case does not exist in complexity theory? a. b. c. d.

Best case Worst case Average case Null case

20. Which of the following sorting methods would be most suitable for sorting a list which is almost sorted? a. b. c. d.

Bubble Sort Insertion Sort Selection Sort Quick Sort...