Deck 15: External Methods

Question 1

In a B-tree,all leaves must be at the same level.

Answer 1

True

Question 2

In the external mergesort algorithm,how many buffers are needed to merge runs?

A)one
B)two
C)three
D)four

Answer 2

C

Question 3

When deleting a key value from a B-tree,what happens if this results in its node becoming empty?

A)A new root node must be created.
B)A new child node must be created.
C)The empty node must merge with another node.
D)The empty node must split into two nodes.

Answer 3

C

Question 4

Which of the following information is not necessary in order to perform (i.e.invoke)a readBlock operation?

A)buffer
B)file
C)block number
D)the data contained in the block

Question 5

Which ADT operation(s)on an external file require us to transfer information to/from internal memory?

A)removals only
B)insertions only
C)insertions and removals only
D)insertions,removals and retrievals

Question 6

What type of tree is best used for indexing external data?

A)B-tree
B)binary search tree
C)2-3-4 tree
D)AVL tree

Question 7

The technique of referencing an employee table with either a Social Security Number or a name as the key value is ______.

A)double hashing
B)random access
C)sequential access
D)multiple indexing

Question 8

When we access external data,a location that temporarily stores data between one process and another is called a ______.

A)block
B)buffer
C)file
D)record

Question 9

Random access file organization behaves like a linked list in the way we access its data.

Question 10

Suppose a B-tree of order 5 contains the key values 20,40,60 and 70.What happens when we insert the key value 80?

A)All 5 key values can reside at the root node.
B)The root becomes 80.
C)The root becomes 60.
D)The root becomes 40.

Question 11

The maximum number of records in a B-tree of degree 5 and height 2 is ______.

A)10
B)20
C)24
D)30

Question 12

An index file consists of index records.An index records consists of two parts: a key and a ______.

A)hash value
B)node
C)pointer
D)value

Question 13

A file is typically partitioned into individual ______ which are the smallest unit of transfer between internal and external memory.

A)blocks
B)disks
C)keys
D)lines

Question 14

In a 2-3 tree,if a node has two key values,then the node has two children.

Question 15

A 2-3 tree is a type of B-tree.

Question 16

In the external version of mergesort,if we begin by performing 16 sorted runs with 1 block each,what is the next step?

A)1 sorted run,16 blocks each
B)2 sorted runs,8 blocks each
C)4 sorted runs,4 blocks each
D)8 sorted runs,2 blocks each

Question 17

Let N be a node in a B-tree.If N has m subtrees S0,S1,S2,…,Sm-1,and N's key values are K1,K2,K3,…,Km-1,then which of the following statements is true?

A)All values in subtree S0 are greater than K1.
B)All values in subtree S1 are less than K1.
C)All values in subtree Sm-2 are greater than Km-2.
D)All values in subtree Sm-1 are less than Km-1.

Question 18

In a B-tree,the key values at each node are always in sorted order (i.e ascending or descending order).

Question 19

Which statement is true about B-trees?

A)Traversals of a table can be done in sorted order more efficiently than a hash table.
B)All nodes are children of the root.
C)The root node contains either the largest or smallest key value.
D)If there are n nodes in the B-tree,then the height of the tree is log2 n.

Question 20

In a binary search tree,if a node has two children,then how many key values does the node itself contain?

A)none
B)one
C)two
D)the number may vary

Question 21

How does a search of a key value in a B-tree differ from a search in a binary search tree?

Question 22

What is the maximum number of nodes in a B tree of height 3 and degree 10?

Question 23

What is the advantage of using a B-tree instead of a 2-3 tree for indexing external data?

Question 24

Why is random access preferable over sequential access for supporting external tables?

Question 25

Mergesort requires us to store the entire array of key values in internal memory before we can begin the merge operation.

Question 26

Inserting a single key value into a B-tree can result in more than one node splitting operation.

Question 27

If a B-tree of order 5 contains the key values 20,40,50,60,80,90 and 100,and the root contains only the key value 60,then deleting the key 20 will require us to merge the two child nodes.

Question 28

External mergesort begins by merging sorted runs.

Question 29

When we perform external hashing,we hash the data file instead of the index file.

Question 30

Name two advantages to storing a data structure in external storage.