数据结构期末考试

一张没有姓名的卷子。

选择题

Problem

Which statement is not correct among the following four:

In a Binary Search Tree (BST), the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.
The number of empty subtrees in a non-empty binary tree is one more than the number of nodes in the tree.
A general tree can be transferred to a binary tree with the root having only left child.
A heap must be a full binary tree.

Answer and Explanation

The correct answer is (D).

Explanation:

(A) In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.
- Correct. In a Binary Search Tree (BST), for each node, the left child must be less than the parent, and the right child must be greater than the parent. In a heap, however, the heap property (either min-heap or max-heap) only ensures that the parent node is either smaller (min-heap) or larger (max-heap) than its children, but there is no specific order between the left and right child.
(B) The number of empty subtrees in a non-empty binary tree is one more than the number of nodes in the tree.
- Correct. In any binary tree, each node has at most two children (left and right), and for a tree with n nodes, there will be n + 1 empty subtrees (which are the null child references for the leaf nodes).
(C) A general tree can be transferred to a binary tree with the root having only left child.
- Correct. A general tree (where nodes can have more than two children) can be transformed into a binary tree using a method called left-child right-sibling representation, where each node's first child is the left child in the binary tree, and the other children are represented as the right siblings.
(D) A heap must be a full binary tree.
- Incorrect. A heap does not have to be a full binary tree. A heap must be a complete binary tree, meaning that all levels are filled except possibly the last, which is filled from left to right. A full binary tree means every node has either zero or two children, which is not a requirement for heaps.

Hence, the statement (D) is not correct.

Problem

For the following graph, one of the results of Depth-First Traversal (DFS) is:
(A) acbdieghf
(B) abighfcde
(C) abdeigchf
(D) abcdefghi

Answer and Explanation

The correct answer is (C): abdeigchf.

默认按照字典序进行。

复杂度的比较

Problem

Arrange the following expressions by growth rate from slowest to fastest:

$ 3n^2 $
$ _3 n $
$ n! $
$ 10n $
$ 2^n $
20
$ _2 n $
$ $

Answer

The expressions arranged by growth rate from slowest to fastest are:
**20 < $ _3 n $ < $ _2 n $ < $ $ < $ 10n $ < $ 3n^2 $ < $ 2^n $ < $ n! $**

Explanation

Let's break down the growth rates of each expression:

20: This is a constant value, so its growth rate is the slowest (no growth at all).
**$ _3 n $** and **$ _2 n $**: These are logarithmic functions. Both grow slower than any polynomial or exponential function. Between these two, the base of the logarithm doesn't significantly affect the growth rate because both grow very slowly relative to other functions as $ n $ increases. For simplicity, we can consider them equivalent in terms of growth order.
$ $: This is a polynomial function with exponent $ $. Polynomial growth rates increase faster than logarithmic functions but slower than linear or quadratic growth.
$ 10n $: This is a linear function, which grows faster than the previous polynomial function but slower than quadratic or exponential functions.
$ 3n^2 $: This is a quadratic function. Quadratic growth is faster than linear growth but slower than exponential growth.
$ 2^n $: This is an exponential function. Exponential growth eventually outpaces all polynomial and logarithmic functions as $ n $ increases.
$ n! $: Factorial growth is faster than exponential growth. Factorials grow extremely fast, making this the fastest-growing function in the list.