Question

Question 1 (Mandatory) (1 point) Saved Modern software systems are blurring the distinction between local files and web pages, which may be stored on a remote computer, so the amount of data that we might wish to search is virtually unlimited. Remarkably, the methods that we shall study can support search and insert operations on symbol tables containing trillions of items or more using only four or five references to small blocks of data. 1) True 2) False Question 2 (Mandatory) (1 point) Saved Data storage mechanisms vary widely and continue to evolve, so we use a simple model to capture the essentials. We use the term probe to refer to a contiguous block of data and the term page to refer to the first access to a probe. 1) True 2) False

Are my answers correct?

Answer 1

Answers:

QUESTION1 :TRUE

QUESTION 2: FALSE

QUESTION 3: FALSE

QUESTION 4: TRUE

QUESTION 5: A

QUESTION 6: A

QUESTION 7: A

QUESTION 8: A

QUESTION 9: TRUE

QUESTION 10: False

Question 1:

Modern software systems are blurring the distinction between local files and web pages, which may be stored on a remote computer, so the amount of data that we might wish to search is virtually unlimited. Remarkably, the methods that we shall study can support search and insert operations on symbol tables containing trillions of items or more using only four or five references to small blocks of data. - TRUE

Question 2:

Data storage mechanisms vary widely and continue to evolve, so we use a simple model to capture the essentials. We use the term probe to refer to a contiguous block of data and the term page to refer to the first access to a probe. - FALSE

Question 3:

We avoid making specific assumptions about the page size and about the ratio of the time required for a probe to the time required, subsequently, to access items within the block. In typical situations, these values are likely to be on the order of 100 or 1,000 or 10,000; we do not need to be more precise because the algorithms are not highly sensitive to differences in the values in the ranges of interest. - FALSE

Question 4:

In the B-tree cost model, when studying algorithms for external searching, we count page accesses, the number of times a page is accessed (for reads, not writes). - TRUE

Question 5:

B-trees extend the 2-3 tree data structure with a crucial difference which enables us to more easily separate the index from the table itself, much like the index in a book:

A. rather than store the data in the tree, we build a tree with copies of the keys, each key copy associated with a link.

B. rather than store the data in the link, we build a tree with copies of the keys, each key copy associated with a tree.

C. rather than store the data in the keys, we build a tree with copies of the tree, each key copy associated with a link.

D. rather than store the data in the tree, we build a tree with a link, each key copy associated with copies of the keys.

Question 6:

Multiway balanced search trees with a fixed page size specify the value of M by using the terminology "B-tree of order M."

A. In a B-tree of order 4, each node has at most 3 and at least 2 key- link pairs in a B-tree of order 6, each node has at most 5 and at least 3 link pairs (except possibly the root, which could have 2 key-link pairs), and so forth

B. In a B-tree of order 4, each node has at most 5 and at least 3 link pairs (except possibly the root, which could have 2 key-link pairs), and so forth in a B-tree of order 6, each node has at most 3 and at least 2 key- link pairs

C. In a B-tree of order 4, each node has at most 4 and at least 4 key- link pairs in a B-tree of order 6, each node has at most 6 and at least 6 link pairs (except possibly the root, which could have 2 key-link pairs), and so forth

D. In a B-tree of order 4, each node has at most 2 and at least 1 key- link pairs in a B-tree of order 6, each node has at most 2 and at least 1 link pairs (except possibly the root, which could have 2 key-link pairs), and so forth

Question 7:

B-trees, as with 2-3 trees, we enforce upper and lower bounds on the number of key-link pairs that can be in each node, we choose a parameter M (an even number, by convention) and build multiway trees where A. every node must have at most M - 1 key-link pairs and at least M/2 key-link pairs except possibly the root, which can have fewer than M/2 key-link pairs but must have at least 2

B. every node must have at least M - 1 key-link pairs and at most M/2 key-link pairs except possibly the root, which can have fewer than M/2 key-link pairs but must have at least 2

C. every node can have fewer than M/2 key-link pairs but must have at least 2 except possibly the root, which must have at most M - 1 key-link pairs and at least M/2 key-link pairs

D. every node must have at most M - 1 key-link pairs and at least M/2 key-link pairs except possibly the root, which can have fewer than 2 but must have at least M/2 key-link pairs

Question 8:

B-trees use two different kinds of nodes:

A. Internal nodes, which associate copies of keys with pages External nodes, which have references to the actual data

B. Internal nodes, which have references to the actual data External nodes, which associate copies of keys with pages

c. Internal nodes, which associate copies of keys with actual data External nodes, which have references to the pages

D. Internal nodes, which have references of keys with pages External nodes, which associate copies to the actual data

Question 9:

A search or an insertion in a B-tree of order M with n items requires between logM N and logM/2 N probes -a constant number, for practical purposes. - TRUE

Question 10:

The space usage of B-trees is also of interest in practical applications. By construction, the pages are at least half full, 30, in the worst case, B-trees use about half the space that is absolutely necessary for keys, plus extra space for links. - FALSE