.
A[10,5]的存储地址是1000，则元素A[18,9]的地址是 。
4．有一个10阶对称矩阵A，采用压缩存储方式（以行序为主序存储，且元素A[0,0]地址为1），则元素A[8,5]的地址是 。
5．设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[] 是函数的符号，给出下列广义表的运算结果： HEAD[(a，b，c)]的结果是 。 TAIL[(a，b，c)]的结果是 。 HEAD[((a)，(b))]的结果是 。 TAIL[((a)，(b))]的结果是 。 HEAD[TAIL[(a，b，c)]的结果是 。 TAIL[HEAD((a，b)，(c，d))]的结果是 。 HEAD[HEAD[(a，b)，(c，d))]]的结果是 。 TAIL[TAIL[(a，(c，d))]]的结果是 。
①a；②(b，c)；③(a)；④((b))；⑤b；⑥(b)；⑦a；⑧( ) 1. 1100 2. 332 3. 1208 4. 42
5. ① ② ③ ④ ⑤ ⑥ ⑦ ⑧
第6章 树和二叉树
选择题
1． 以下说法错误的是 。
A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种\分支层次\结构
2. 如图6-2所示的 4 棵二叉树中， 不是完全二叉树。
Word 资料
.
图6-2 4 棵二叉树
3. 以下说法错误的是 。
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好
4. 如图6-3所示的 4 棵二叉树， 是平衡二叉树。
图6-3 4 棵二叉树
5. 如图6-4所示二叉树的中序遍历序列是 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc
abcdgef
图6-4 1 棵二叉树
6. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
7. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为 。 A.42 B.40 C.21 D.20
8. 一棵二叉树如图6-5所示，其后序遍历的序列为 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh
Word 资料
.
abcdefgh 图6-5 1 棵二叉树
9. 深度为 5 的二叉树至多有 个结点。 A. 16 B. 32 C.31 D.10
10. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数至少有 个。
A.k+1 B.2k C.2k-1 D.2k+1
11. 对含有 B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A.0 B.1 C.2 D.不存在这样的二叉树
1-5 ACDBB 6-10 填空题
1. 有一棵树如图6-7 所示，回答下面的问题：
k1DDCCC
k2k3k4k5k6k7 图6-7 1 棵二叉树
（1）这棵树的根结点是 ； （2）这棵树的叶子结点是 ； （3）结点 k3 的度是 ； （4）这棵树的度为 ；
Word 资料
.
（5）这棵树的深度是 ； （6）结点 k3 的孩子是 ； （7）结点 k3 的双亲结点是 。
2. 深度为 k 的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从 1 开始），则编号最小的叶子结点的编号是 。 答：①2
k?1
②2-1 ③2
kk?2+1
3. 一棵二叉树的第 i（i≥1）层最多有 个结点；一棵有 n（n>0）个结点的满二叉树共有 个叶子和 个非终端结点。 答：① 2
4. 具有n个结点的完全二叉树的深度为 。
5. 哈夫曼树是带权路径度_______的树，通常权值较大的结点离根_______。 ①最短 ②较近
6．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
1.答：① k1 ② k2 k5 k7 k4 ③ 2 ④ 3 ⑤ 4 ⑥ k5，k6 ⑦ k1 2. ① ② ③ 3. ① ② ③ 4.floor(log2n)+1 5. ① ② 6. 先根 例题解析
【例6-1】由如图 6-1 所示的二叉树，回答以下问题。 （1）其中序遍历序列为 ① ； （2）其前序遍历序列为 ② ； （3）其后序遍历序列为 ③ ；
（4）该二叉树的中序线索二叉树为 ④ ； （5）该二叉树的后序线索二叉树为 ⑤ ； （6）该二叉树对应的森林是 ⑥ 。
i?1 ②
2?logn? ③ 2?logn??1
Word 资料