FDS-questions

#notes

这是 FDS 的一些理论题的题库，多为 PTA 上的 HW 获得，也有一些前人的题库，在此也一并感谢。

主要是选择判断题，每题答案在最后给出；对于函数体和编程题，给出了 PTA 链接，但是不清楚是否只有我自己能访问，有待确认。

Attention

为了作为复习性资料而具有可做性，我将所有题干部分放在了注释栏内，将每一道题的答案放在了最后面；截图中的答案仅为我提交的答案，不代表最终结果。

I Algorithm Complexity Analysis

I.1 判断题

O 的含义是小于或等于。

递归计算斐波那契数列，其时间复杂度依旧是一个斐波那契数列，为 $O (2^{N})$ 。

time complexity	space complexity
recursively	$O (F_{N}) \sim O (2^{N})$	O(N)
lteratively	O(N)	O(1)

(1-4)

$n^{0.01}$ is $O (\log n)$

一开始没搞懂啥意思（听说在离散数学里面学了）在 math.stackexchange.com 上找到了解答。

两个回答，其一说明如何判断，其二指出如何计算

（也就是说当 $α > 0$ 时， $n^{α} = Ω (\log n)$ ）

注意点：

别把 N*2 看成了 N^2 问就是我一开始看错了……
else 中当 i > N 之后后面的循环都不会进行了，不用统计
最低上限，取较小者。

An algorithm may or may not require input, but each algorithm is expected to produce at least one result as the output.

没说实现方式，数组还是链表？

I.2 选择题

递归：主定理

简单来说记住下面就够了：

\begin{aligned} If T (n) = a T (⌈ \frac{n}{b} ⌉) + O (n^{d}) (for constants a > 0, b > 1, d \geq 0), then : \\ T (n) = {\begin{cases} O (n^{d}) & if d > \log_{b} a \\ O (n^{d} \log n) & if d = \log_{b} a \\ O (n^{\log_{b} a}) & if d < \log_{b} a \end{cases} \end{aligned}

或者我们使用更加简单的方法，手动递归，发现：

对于 P1: $T (\frac{N}{3^{k}}) = T (1) + k = T (1)$ ，P2 同理，就可以获得答案。

矩阵压缩储存自行搜索

不难发现 $m_{30, 30}$ 是第 $2 + 28 * 3 + 2 = 88$ 个数，但是数组 N 从 0 开始

II DS:List/Stack/Queue

II.1 判断题

链表的节点数是可变的。

For a sequentially stored linear list of length N, the time complexities for random query and inserting the first element are O(N) and O(1), respectively.

顺序/连续储存的线性表一般指数组实现的形式，查询为 O(1)，插入为 O(N)

II.2 选择题

Infix to postfix convertion，我们只是把操作符在 stack 中进行了操作。对于操作符压栈和出栈的决定，比较当前栈顶操作符 A 和当前决定的操作符 B 的优先级，如果 $A \geq B$ 则 A 出栈，继续向下比，直到 A < B 或者栈空的时候，将 B 压栈。若左括号，一定加入；并直到右括号出现才把左括号连带栈顶的操作符弹出。

不知道当时怎么想的……常见结构及操作复杂度如下；这里插入和删除只在最后面，所以略有不同。

后面俩不用说，前面三个 o 看似 $A_{3}^{3} = 6$ ，但是在栈中是不一样滴。

5 种：123,132,231,213,321 （数字表示为入栈顺序）

判断一个循环队列QU（最多元素为MaxSize）为空的条件是（）。

A.QU.front == QU.rear

B.QU.front != QU.rear

C.QU.front == (QU.rear + 1) % MaxSize

D.QU.front != (QU.rear + 1) % MaxSize

由于我们一般初始化 front = rear = 0 ，所以 A 为空，C 为满。

这里不一样，只说了 $f r o n t = r e a r$ ，所以我们通过内部元素个数来判断较好。

II.3 函数/编程题

Reverse Linked List

Pop Sequence

III Tree

III.1 判断题

It is always possible to represent a tree by a one-dimensional integer array.

There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child.

看下一题就懂了。

For any nonempty binary tree, if we set $n_{i}$ as the number of nodes with i children, then we get that $n_{0} = n_{2} + 1$

设 e 表示边的数量，n 表示总结点数，则有

{\begin{cases} n = n_{0} + n_{1} + n_{2} \\ e = n - 1 \\ e = n_{1} + 2 * n_{2} \end{cases} ⟹ n_{0} = n_{2} + 1

III.2 选择题

in the process，最终确实是 5 个没动，但是过程中只有 4 个。

线索二叉树左右指针空了就连前驱和后驱，无论和前驱后驱之间本来是否直接连接。

符号同前，有：

{\begin{cases} e = n_{3} + n_{2} + n_{1} + n_{0} - 1 \\ e = 3 n_{3} + 2 n_{2} + n_{1} \end{cases} ⟹ n_{0} = 2 n_{3} + n_{2} + 1

这个……感觉一个一个推吧，做结论记一记也可以。

IV Binary (Search) Tree

IV.1 判断题

For binary heaps with N elements, the BuildHeap function (which adjust an array of elements into a heap in linear time) does at most N - log(N+1)comparisons between elements.

应该是 2N-2 次，证明见 StackExchange 。

There are more NULL pointers than the actual pointers in the linked representation of any binary tree.

The number of leaf nodes in a ternary tree (三叉树) is only related to the number of degree 2 nodes and that of degree 3 nodes, i.e it has nothing to do with the number of degree 1 nodes.

Note

完全二叉树的叶子节点数为总节点数 N/2 向上取整
In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order.

In a binary search tree which contains several integer keys including 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent.

根据上面的判断题可以知道 4 肯定在 5 左子树中，6 在 5 右子树中，但是不一定直接连在 5 上，也就是说不一定是 parent 。

Given a binary search tree with 20 integer keys which include 10, 11, and 12, if 10 and 12 are on the same level, then 11 must be their common ancestor.

注意是common ancestor，不一定是parent

If a complete binary tree with 137 nodes is stored in an array (root at position 1), then the nodes at positions 128 and 137 are at the same level.

换我这道题就问 127，万一有人不记得完全二叉树的数列从 1 开始用呢(bushi)

IV.2 选择题

看最后一个数定 root 。

差不多就是在问：能够形成的二叉树的层数是多少？

和前面那题一样。

感觉就记住吧，考场上容易乱。

Given a binary search tree with its preorder traversal sequence { 8, 2, 15, 10, 12, 21 }. If 8 is deleted from the tree, which one of the following statements is FALSE?

A.One possible preorder traversal sequence of the resulting tree may be

B.One possible preorder traversal sequence of the resulting tree may be

C.One possible preorder traversal sequence of the resulting tree may be

D.It is possible that the new root may have 2 children

删除搜索二叉树根节点，需要用中序遍历的前驱或后继替代根节点，对应AB两种情况