I need some help answering these questions. I\'m not sure of some the answers. -
ID: 3691579 • Letter: I
Question
I need some help answering these questions. I'm not sure of some the answers.
--------------------------------------------------------------------------------------------------------
The element being searched for is in an array of size N that is in random order. What is the average number of comparisons needed to find the element?
If a heap element that is at position index in the array has a left child then that child is position _________ in the array
Define a complete graph, in terms of a graph.
Describe the order property of a heap.
A Heap is based on a complete binary tree.
True
False
What would be the order of the following list after two iterations of the Selection Sort algorithm?
13 4 16 19 2 15 12 3 23 20
The goal of a successful hashing scheme is an O(1) search.
True
False
Priority Queues may not hold duplicate elements.
True
False
The efficiency of the Bubble sort is O(N log2 N) where N is the size of the list being sorted.
True
False
We can represent a graph using ___________________________, linked lists that identify all the vertices a partular vertex is connected to
The element being searched for is in an array of size N that is in random order. What is the minimum number of comparisons needed to find the element?
The element being searched for is NOT in an array of size N that is in increasing order. What is the average number of comparisons needed to determine
Explanation / Answer
1.The element being searched for is in an array of size N that is in random order. What is the average number of comparisons needed to find the element?
Ans. logn
2.If a heap element that is at position index in the array has a left child then that child is position 2*index in the array
3. Define a complete graph, in terms of a graph.
Ans. a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges
4.Describe the order property of a heap.
Ans.
5. A Heap is based on a complete binary tree.
True
6. What would be the order of the following list after two iterations of the Selection Sort algorithm?
13 4 16 19 2 15 12 3 23 20
Ans. 2 3 16 19 13 15 12 4 23 20
7. The goal of a successful hashing scheme is an O(1) search.
True
8. Priority Queues may not hold duplicate elements.
True
9.The efficiency of the Bubble sort is O(N log2 N) where N is the size of the list being sorted.
True
10. We can represent a graph using array , linked lists that identify all the vertices a partular vertex is connected to
11. The element being searched for is in an array of size N that is in random order. What is the minimum number of comparisons needed to find the element?
Ans. if array is sorted than O(logn)
if array is unsorted than O(n-1)
12. The element being searched for is NOT in an array of size N that is in increasing order. What is the average number of comparisons needed to determine