Question 1

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

Accepted Answer

The answer of 
-For the binary tree shown, list the...

Question 2

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

Accepted Answer

The answer of 
-A ______ is a nonlinear structure whose...

Question 3

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

Accepted Answer

The answer of 
-The ______ strategy allows array positions to...

Question 4

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

Accepted Answer

The answer of 
-In general, a balanced n-ary tree with...

Question 5

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

Accepted Answer

The answer of 
-There are four basic methods for traversing...

Question 6

-Preorder traversal means ______.

Accepted Answer

The answer of 
-Preorder traversal means ______....

Question 7

-Inorder traversal means ______.

Accepted Answer

The answer of 
-Inorder traversal means ______....

Question 8

-Postorder traversal means ______.

Accepted Answer

The answer of 
-Postorder traversal means ______....

Question 9

-Level-order traversal means ______.

Accepted Answer

The answer of 
-Level-order traversal means ______....

Question 10

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

Accepted Answer

The answer of 
-In the computational strategy to implement a...

Question 11

The binary tree shown above is balanced.

Accepted Answer

Without a specific binary tree provided, I cannot directly assess its balance. However, a binary tree is considered balanced if the height difference between the left and right subtrees of any node in the tree does not exceed one. This definition helps in ensuring that operations like insertions, deletions, and lookups can be performed efficiently.

Question 12

The binary tree shown above is complete.

Accepted Answer

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all the nodes are as far left as possible. In the given binary tree, all the levels are completely filled, and all the nodes are as far left as possible. Therefore, the given binary tree is a complete binary tree.

Question 13

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

Accepted Answer

A Binary Tree is a type of data structure where each node can have at most two children, not up to three.

Question 14

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).

Accepted Answer

A balanced binary search tree maintains a height of O(logn), ensuring that operations like find, insert, and delete take O(logn) time. However, a binary search tree without the balance guarantee can degenerate into a linked list in the worst case, making the find operation take O(n) time.

Question 15

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

Accepted Answer

The root of a tree is the topmost node, which does not have a parent. Nodes with parents (other than the root) are typically referred to as child nodes.

Question 16

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

Accepted Answer

A tree is indeed a nonlinear data structure where elements are arranged in a hierarchical manner, with a single root element and subsequent child elements branching out, forming a tree-like structure.

Question 17

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

Accepted Answer

The simulated link strategy, often used in implementing binary trees, typically involves using an array where elements (nodes) are placed in specific positions based on their level and order in the tree, allowing for contiguous allocation of array positions. This method does not depend on the completeness of the tree to allocate positions contiguously.

Question 18

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

Accepted Answer

The height of a balanced n-ary tree (where each node can have up to n children) with m elements is indeed given by the logarithm base n of m, denoted as log base n of m. This is because, in a perfectly balanced scenario, each level of the tree fully utilizes all n possible children before adding a new level, leading to a height that grows logarithmically with the number of elements.

Question 19

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

Accepted Answer

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

Question 20

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

Accepted Answer

Inorder traversal in binary trees means visiting the left subtree first, then the current node, and finally the right subtree.

Quiz 9: Searching and Sorting