子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，问：1第ｉ层上有多少个结点？2编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？3编号为ｐ的结点的双亲结点（若存在）的编号是多少？参考答案：
1ki1个
2（１＋（ｐ－１）＊ｋ）＋ｉ
p3
kk

2

（ｐ≠１）
】
2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。参考答案：
本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表
f达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括
号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或右子树）根结
点运算符时，就需要加括号。
i
tPrecedecharoptr1charoptr2比较运算符级别高低，optr1级别高于optr2时返回1，相等时返回0，低于时返回1
switchoptr1case‘’case‘’ifoptr2‘’optr2‘’retur
0elseretur
1case‘’case‘’ifoptr1‘’optr2‘’retur
0elseretur
1


voidI
orderExpBiTreebt输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名
i
tbracket
ifbt
ifbtlchild
ull
bracketPrecedebtdatabtlchilddata比较双亲与左子女运算符优先级
ifbracket1pri
tf‘’
I
orderExpbtlchild
输出左子女表示的算术表达式
ifbracket1pri
tf‘’加上右括号
pri
tfbtdataifbtrchild
ull
输出根结点输出右子树表示的算术表达式
bracketPrecedebtdatabtrchilddataifbracket1pri
tf“”右子女级别低，加括号
I
orderExpbtrchildifbracket1pri
tf“”
结束I
orderExp
4．有
个结点的完全二叉树存放在一维数组A1
中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。参考答案：方法一：BiTreeCreatElemTypeAi
ti
个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树
BiTreetreeifi
treeBiTreemallocsizeofBiNodetreedataAi
if2i
treelchild
ullelsetreelchildCreatA2iif2i1
treerchild
ullelsetreerchildCreatA2i1retur
treeCreat初始调用时i1。
f图的部分习题答案
5．
个结点的完全有向图含有边的数目（）。
A．

Ｂ．
（
1）C．
／2
参考答案：D
D．
（
1）
15．设图如右所示，
，在下面的5个序列中，符合深度优先遍历的序列
有（）个。
aebdfcA．5个
参考答案：D
acfdeb
aedfcbB．4个
aefdcbC．3个
aefdbcD．2个
21．已知有向图GVr