Deck 9: Searching and Sorting

Question 1

A collection where each node can have from 0 to 2 children is called a ___________.

A) Stack
B) Queue
C) List
D) Binary tree

Answer 1

Binary tree

Question 2

A node that does not have a parent is called the ______ of a tree.

A) foot
B) root
C) leaf
D) top

Answer 2

root

Question 3

A tree is a nonlinear structure whose elements are organized into a __________.

A) stack
B) hierarchy
C) queue
D) list

Answer 3

hierarchy

Question 4

The simulated link strategy allows array positions to be allocated contiguously regardless of the _________ of the tree.

A) size
B) order
C) completeness
D) root

Question 5

In general, a balanced n-ary tree with m elements will have height _______.

A) log_nm
B) log_mm
C) log_mn
D) log_nn

Question 6

There are four basic methods for traversing a tree: preorder, inorder, postorder, and level-order.

A) Top down, bottom up, inorder, and postorder
B) Top down, inorder, postorder, and level-order
C) Bottom up, preorder, in order, and postorder
D) preorder, inorder, postorder, and level-order

Question 7

_________ traversal means visit the node, then the left child, then the right child.

A) preorder
B) postorder
C) inorder
D) level-order

Question 8

_________ traversal means visit the left child, then the node, then the right child.

A) preorder
B) postorder
C) inorder
D) level-order

Question 9

________ traversal means visit the left child, then the right child, then the node.

A) preorder
B) postorder
C) inorder
D) level-order

Question 10

___________ traversal means visit the nodes at each level, one level at at time, starting with the root.

A) preorder
B) postorder
C) inorder
D) level-order

Question 11

In the computational strategy to implement a tree with an array, the children of node n are stored at 2n + 1 and 2(n + 1) respectively.

A) 2n + 1
B) 2n + 2
C) 2(n + 1)
D) A and B
E) A and C
F) B and C

Question 12

A node that does not have a ______ is called the root of a tree.

Question 13

A collection where each node can have from 0 to 2 children is called a ______ Tree.

Question 14

A node that has both a parent and at least one child is called a(n) ______ node.

Question 15

A balanced N-ary tree with n elements will have height ______.

Question 16

-For the tree shown above, list the root.

Question 17

-For the tree shown above, list the leaves.

Question 18

-What is the height of the tree shown above?

Question 19

-For the binary tree shown, list the elements in the order generated by an InOrder traversal.

Question 20

-For the binary tree shown, list the elements in the order generated by an PreOrder traversal.

Question 21

-For the binary tree shown, list the elements in the order generated by an PostOrder traversal.

Question 22

-A ______ is a nonlinear structure whose elements are organized into a hierarchy.

Question 23

-The ______ strategy allows array positions to be allocated contiguously regardless of the completeness of the tree.

Question 24

-In general, a balanced n-ary tree with m elements will have height ______.

Question 25

-There are four basic methods for traversing a tree: ______.

Question 26

-Preorder traversal means ______.

Question 27

-Inorder traversal means ______.

Question 28

-Postorder traversal means ______.

Question 29

-Level-order traversal means ______.

Question 30

-In the computational strategy to implement a tree with an array, the children of node n are stored at _____.

Question 31

The binary tree shown above is balanced.

Question 32

The binary tree shown above is complete.

Question 33

A collection where each node can have from 0 to 3 children is called a Binary Tree.

Question 34

A find operation on a balanced binary search tree is O(logn) where as a find operation for binary search tree without the balance assumption is O(n).

Question 35

A node that has a parent is called the root of a tree.

Question 36

A tree is a nonlinear structure whose elements are organized into a hierarchy.

Question 37

The simulated link strategy does not allow array positions to be allocated contiguously regardless of the completeness of the tree.

Question 38

In general, a balanced n-ary tree with m elements will have height log_nm.

Question 39

Preorder traversal means visit the left child, then the right child, then the node.

Question 40

Inorder traversal means visit the left child, then the node, then the right child.

Question 41

Postorder traversal means visit the node, then the left child, then the right child.

Question 42

Level-order traversal means visit the nodes at each level, one level at at time, starting with the root.

Question 43

In the computational strategy to implement a tree with an array, the children of node n are stored at 2n + 1 and 2(n + 1) respectively.

Question 44

What is a tree?

Question 45

What is a node?

Question 46

What is the root of the tree?

Question 47

What is a leaf?

Question 48

Define the height of a tree.

Question 49

Define the level of a node.

Question 50

What are the advantages and disadvantages of the computational strategy?

Question 51

What are the advantages and disadvantages of the simulated link strategy?

Question 52

What attributes should be stored in the TreeNode class?

Question 53

Which method of traversing a tree would result in a sorted list for a binary search tree?

Question 54

We used a list to implement the iterator methods for a binary tree. What must be true for this strategy to be successful?