Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

1. For each of the following questions find the most appropriate answer: 0) Whic

ID: 3721217 • Letter: 1

Question

1. For each of the following questions find the most appropriate answer: 0) Which of the follwin oerations on a singly-linked list of last names cannot be done in the worst case in linear time? a. insertion at an arbitrary place b. deletion of the last element c. arranging them in alphabetical order d. all of the above (i) What is the time complexity of insertion in a binary heap with n nodes? a. Olog n b. O(n) c. O(n2) d. none of the above (iil) The maximum number of nodes in a binary tree of depth k (assume that the root is at depth 1) is b. 2 c. 24-1 (iv) The worst-case time complexity of the depth-first search of a graph with n nodes is: a. O(n) b. O(n log2 n) c. O(n2) d. O(2) (v) The most popular method of sorting large files on disks is based on: s. insertion sort b. merge sort c. quick sort d. heap sort (vi) The hash function determines a. the address for a given key value b. whether a given key is present or not c. the key value at a given address d. the size of the storage table (vi) Which of the following factors affects the choice of the page size in a B-tree? a. disk seek time b. the internal processing time (e.g., searching) per page c. transmission time per character d. all of the above (vii) Which of the following is the primary advantage of indexed access over sequential access? a. reduced internal fragmentation

Explanation / Answer

1.c. Both insertion and deletion can be done in linear time.But sorting the list in alphabetical order is an O(n log n) operation and comparing 2 strings is an O(n) operation.So,correct choice is c.

2.a.Complexity of inserting an element into a binary heap is O(h) where h is height of tree.Since a binary heap is a complete tree so height of tree = log n.Therefore, complexity =O(logn).

3.a. Maximum number of nodes is 2k - 1.

4.a. O(n).If the number of vertices is e, then time complexity of dfs is O(n+e).

5.b.For sorting large files on disk external sorting method is used which is based on merge sort.

6.a. Hash function is used to calculate the address for a given key value.

7.b.the internal processing time per page

Related Questions

1. For control chart, the lower and upper control limits are usually set at: fiv
Question #3181466
1. For each 1% change in the market portfolio\'s excess return, the investment\'
Question #2629144
1. For each Big Data source listed below, identify an organization that you beli
Question #394363
1. For each CIA concept below, classify each example as having a low, moderate,
Question #3728765
1. For each application below, determine if the particular choice of metal is ap
Question #1042273
1. For each box, circle the appropriate response for if the medium is rich or mi
Question #276387
1. For each case below, choose which is true: a) Bearth> BLocal b) Bearth Brocal
Question #2031341
1. For each case below, tell whether RH and other quantity will increase or decr
Question #113130

Navigate

Previous
1. For each of the following purchases, say whether you would expect the degree
Next
1. For each of the following rate equations, describe what would happen to the r

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.