第二阶段练习题
考试科目:《数据结构》第五章至第七章（总分100分）
______________学习中心（教学点）批次：层次：
专业：学号：身份证号：
姓名：得分：
一、选择题（每题3分，共30分）
1、将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，则A中的元素A[66，65]在数组B中的位置K=（）。
Ａ、195Ｂ、196Ｃ、197Ｄ、198
2、广义表(a,(b,(),c))的深度为（）。
Ａ、1Ｂ、2Ｃ、3Ｄ、4
3、下列叙述中错误的是（）。
A、树的度与该树中结点的度的最大值相等
B、二叉树就是度为2的有序树
C、有5个叶子结点的二叉树中必有4个度为2的结点
D、满二叉树一定是完全二叉树
4、一棵二叉树中第６层上最多有（）个结点。
Ａ、２Ｂ、３１Ｃ、３２Ｄ、６４
5、由树转换而得的二叉树，根结点（）。
Ａ、没有左子树Ｂ、没有右子树Ｃ、左右子树都有Ｄ、视树的形态而定
6、一棵高为k的二叉树最少有（）个结点。
Ａ、k-1Ｂ、kＣ、k+1Ｄ、2k-1Ｅ、2k-1
7、含n个顶点的有向图最多有（）条弧。
Ａ、nＢ、n(n-1)Ｃ、n(n+1)Ｄ、n2
8、设对下图从顶点a出发进行深度优先遍历，则（）是可能得到的遍历序列。
Ａ、acfgdebＢ、abcdefgＣ、acdgbefＤ、abefgcd
9、设图Ｇ的邻接矩阵A=????
??????010101010，则图Ｇ中共有（ ）个顶点。 Ａ、1 Ｂ、3 Ｃ、4 Ｄ、9
10、具有n 个顶点的有向强连通图最少有（ ）条弧。 Ａ、n-1 Ｂ、n Ｃ、n(n-1) Ｄ、n(n-1)/2
二、（10分）
试将下图中的树转化为二叉树。
三、（10分）
试写出对如下无向图从顶点Ａ出发进行广度优先遍历可能得到的所有遍历序列。
四、（15分）
设有向网如下，试用迪杰斯特拉算法求从顶点Ａ出发到其余各顶点的最短路径。
五、（15分）
一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，则：
⑴第ｉ层上有多少个结点？
⑵编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？
⑶编号为ｐ的结点的双亲结点（若存在）的编号是多少？
六、（20分）
试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。
答案
一、选择题
1、A
2、C
3、B
4、C
5、B
6、B
7、B
8、A
9、B
10、B
二、试将下图中的树转化为二叉树。
答：
三、试写出对如下无向图从顶点Ａ出发进行广度优先遍历可能得到的所有遍历序列。
答：
ABCEGHFD
ABCEHGFD
ACBGHEDF
ACBHGEDF
四、设有向网如下，试用迪杰斯特拉算法求从顶点Ａ出发到其余各顶点的最短路径。
答：
A 0 0
B 1 1
C 2 2
D 3 3
E 4 4
F 5 5
G 6 6
A 0 0
B 1 1
C 2 2
D 3 3
E 4 4
F 5 5
G 6 6
五、一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，则：
⑴第ｉ层上有多少个结点？
⑵编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？ ⑶编号为ｐ的结点的双亲结点（若存在）的编号是多少？
答：
⑴第1层有1个结点，第i 层结点数＝第i-1层结点数*k （2≤i ≤H ）=1
-i k
个
⑵当根结点以及前面的p-1个结点的孩子都编了号之后，才开始为结点p 的孩子编号。结点p 的第i 个孩子的编号为（１＋（ｐ－１）＊ｋ）＋ｉ。
⑶若ｐ＝１，则为根结点，无双亲，否则可设双亲结点编号为ｓ，由⑵可知结点ｓ的孩子结点的编号范围为（ｓ－１）＊ｋ＋２～（ｓ－１）＊ｋ＋ｋ＋１，即
k
k p s k p 2
1-+≤
≤-，又由ｓ为整数，可得??
?
???-+=k k p s 2。
六、试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。
答：
int depth(BiTree t){ if (!t) return 0; if(t->lchild)//有左子树
if (t->rchild){ //左、右子树均有 hl=depth(t->lchild); //求左子树高度 hr=depth(t->rchild); //求右子树高度 return hl>hr?hl+1:hr+1; }
else //只有左子树
return depth(t->lchild)+1; else //无左子树
return depth(t->rchild)+1; //有右子树，则返回右子树高度加1 //无右子树，即右子树高度为0，则返回1 }//depth