树的先根遍历

(1)【◆题库问题◆】：[名词解释] 树的先根遍历

【◆参考答案◆】：
若树非空，则先访问根结点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这棵树对应的二叉树的线序遍历顺序相同。

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(2)【◆题库问题◆】：[填空题] 线性表（a1，a2，…，an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC（ai）为（）。

【◆参考答案◆】：LOC（a1）+(i-1)*L

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(3)【◆题库问题◆】：[单选] 对一个满二叉树，m个树叶，n个结点，深度为h，则（）
A．n=h+m
B．h+m=2n
C．m=h-1
D．n=2h-1

【◆参考答案◆】：D

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(4)【◆题库问题◆】：[名词解释] 拓扑排序

【◆参考答案◆】：
由一个有向无环图的顶点组成的序列，当且仅当满足下列条件，称为该图的一个拓扑排序——1，每个顶点出现且仅出现一次。2若顶点a在b之前，不存在b到a的路径。

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(5)【◆题库问题◆】：[名词解释] 分块查找（索引查找）

【◆参考答案◆】：
分块查找以前两个为基础，将待查记录分成若干块，每块的关键字无序，但每块的关键字的最大值有序，查找时，先查找到待查记录所在的块，再在块内进行顺序查找。找块时，即可以用折半查找，也可用顺序查找。

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(6)【◆题库问题◆】：[单选] 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（）。
A．R[2i-1]
B．R[2i+1]
C．R[2i]
D．R[2/i]

【◆参考答案◆】：B

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(7)【◆题库问题◆】：[单选] 在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（）。
A．O（log2n）
B．O（1）
C．O（n）
D．O（nlog2n）

【◆参考答案◆】：B

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(8)【◆题库问题◆】：[判断题] 在非递归调用的情况下，数据区的分配方法采用动态分配。
A．正确
B．错误

【◆参考答案◆】：正确

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(9)【◆题库问题◆】：[判断题] 对稀疏矩阵进行压缩存储是为了便于进行矩阵运算。
A．正确
B．错误

【◆参考答案◆】：正确

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(10)【◆题库问题◆】：[单选] 当利用大小为N的数组存储循环队列时，该队列的最大长度是（）。
A．N-2
B．N-1
C．N
D．N+1

【◆参考答案◆】：C