1、计算机学科专业基础综合数据结构-5 及答案解析(总分：100.00，做题时间：90 分钟)一、综合应用题(总题数：10，分数：100.00)一棵高度为 h 的满 m 叉树有如下性质：第 h 层上的结点都是叶结点，其余各层上每个结点都有 m 棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从 1 开始对全部结点进行编号，试问：（分数：20.00）(1).各层的结点个数是多少?（分数：4.00）_(2).编号为 i 的结点的父结点(若存在)的编号是多少?（分数：4.00）_(3).编号为 i 的结点的第 k 个子女结点(若存在)的编号是多少?（分数：4.00）_(4).编号为 i 的结点有右兄
2、弟的条件是什么?其右兄弟结点的编号是多少?（分数：4.00）_(5).若结点个数为 n，则高度 h 是 n 的什么函数关系?（分数：4.00）_针对二叉树 BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。（分数：24.00）(1).int size(BiTNode * t)； /返回以 * t 为根的二叉树中所有结点个数（分数：4.00）_(2).int leaves(BiTNode * t)； /返回以 * t 为根的二叉树的叶结点个数（分数：4.00）_(3).int height(BiTNode * t)； /返回以 * t 为根的二叉树的高度（分数：4.00）_(4).i
3、nt level(BiTNode * t，BiTNode * p)；/返回二叉树指定结点 * p 在以 * t 为根的子树中的层次（分数：4.00）_(5).void reflect(BiTNode * t)； /交换以 * t 为根的二叉树中每个结点的两个子女（分数：4.00）_(6).void defoliate(BiTNode * /访问(输出)根结点 Preorder(t-lchild); /前序遍历根的左子树 Preorder(t-rchild); /前序遍历根的右子树 （分数：8.00）(1).改写 PreOrder 算法，消去第二个递归调用 PreOrder(t-rchild)；
4、（分数：4.00）_(2).利用栈改写 PreOrder 算法，消去两个递归调用。（分数：4.00）_请回答下列关于图的一些问题：（分数：15.00）(1).有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?（分数：5.00）_(2).表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?（分数：5.00）_(3).对于一个有向图，不用拓扑排序，如何判断图中是否存在环?（分数：5.00）_4.在有关图的算法中常用到两个图的操作： int getFirstNeighbor (Graph G,int v); /取顶点 v 的第一个邻接顶点 int
5、 getNextNeighbor(Graph G,int v,int w); /取邻接顶点 w 的下一邻接顶点 试分别给出在邻接矩阵和邻接表为存储结构的情形下它们的实现。 （分数：5.00）_计算机学科专业基础综合数据结构-5 答案解析(总分：100.00，做题时间：90 分钟)一、综合应用题(总题数：10，分数：100.00)一棵高度为 h 的满 m 叉树有如下性质：第 h 层上的结点都是叶结点，其余各层上每个结点都有 m 棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从 1 开始对全部结点进行编号，试问：（分数：20.00）(1).各层的结点个数是多少?（分数：4.00）_正确答案：
6、()解析：可以参照二叉树的性质，将其扩展到 m 叉树。 因为第 1 层有 1 个结点，第 2 层有 m 个结点，第 3 层有 m 2 个结点一般地，第 i 层有 m i-1 个结点(1ih)。(2).编号为 i 的结点的父结点(若存在)的编号是多少?（分数：4.00）_正确答案：()解析：在 m 叉树的情形，结点 i 的第 1 个子女编号为 j=(i-1)m+2。反过来，结点 i 的双亲的编号是，根结点没有双亲，所以以上计算式要求 i1。如果考虑对于 i=1 也适用(根的双亲设为 0)，可将上式改为(3).编号为 i 的结点的第 k 个子女结点(若存在)的编号是多少?（分数：4.00）_正确答
7、案：()解析：因为结点 i 的第 1 个子女编号为(i-1)m+2，若设该结点子女的序号为 k=1，2，m，则第 k 个子女结点的编号为(i-1)m+k+1(1km)。(4).编号为 i 的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?（分数：4.00）_正确答案：()解析：当结点 i 不是其双亲的第 m 个子女时才有右兄弟。若设其双亲编号为 j，可得 j= (5).若结点个数为 n，则高度 h 是 n 的什么函数关系?（分数：4.00）_正确答案：()解析：若结点个数为 n，则有 针对二叉树 BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。（分数：24.00）(1).in
8、t size(BiTNode * t)； /返回以 * t 为根的二叉树中所有结点个数（分数：4.00）_正确答案：()解析：返回以 * t 为根的二叉树中所有结点个数： int size(BinTreeNode * t) if(t=NULL)return 0; return 1+size(t-lchild)+size(t-rchild); (2).int leaves(BiTNode * t)； /返回以 * t 为根的二叉树的叶结点个数（分数：4.00）_正确答案：()解析：返回以 * t 为根的二叉树中叶结点个数： int leayes(BiTNode * t) if(t=NULL) r
9、eturn 0; if(t-lchild=NULL return leayes(t-lchild)+leayes(t-rchild); (3).int height(BiTNode * t)； /返回以 * t 为根的二叉树的高度（分数：4.00）_正确答案：()解析：返回以 * t 为根的二叉树的高度： int height(BiTNode * t) if(t=NULL)return 0; int h1=height(t-lchild); int hr=height(t-rchild); if(h1hr)return h1+1; else return hr+1; (4).int level
10、(BiTNode * t，BiTNode * p)；/返回二叉树指定结点 * p 在以 * t 为根的子树中的层次（分数：4.00）_正确答案：()解析：返回以 * t 为根的二叉树中指定结点 * p 所在层次： int level(BiTNode * t,BiTNode * p,int d) if(t=NULL) return 0; if(t=p) return(d); int level; if(level=level (t-lchild,p,d+1) return (level1); else return (level (t-rchild,p,d+1); (5).void reflec
11、t(BiTNode * t)； /交换以 * t 为根的二叉树中每个结点的两个子女（分数：4.00）_正确答案：()解析：交换以 * t 为根的二叉树中每个结点的两个子女： void reflect(BiTNode * t) if(t=NULL)return; reflect(t-lchild); reflect(t-rchild); BiTNode * p=t-lchild;t-lchiId=t-rchild;t-rchild=p; (6).void defoliate(BiTNode * if(t-lchild=NULLt=NULL; else defoliate(t-lchild); d
12、efoliate(t-rchild); 1.已知一棵二叉树的前序遍历序列为 ABECDFGHIJ，中序遍历序列为 EBCDAFHIGJ，试画出这棵二叉树并写出它的后序遍历序列。 （分数：4.00）_正确答案：()解析：当前序序列为 ABECDFGHU，中序序列为 EBCDAFHIGJ 时，逐步形成二叉树的过程如下图所示。 设二叉树根结点在第 1 层，树的深度 d 为距离根最远的叶结点所在层次，试给出：（分数：8.00）(1).深度为 d 的完全二叉树的不同二叉树棵数。（分数：4.00）_正确答案：()解析：深度为 d 的完全二叉树的 1 到 d-1 层都是满的，第 d 层有多少结点就有多少种选
13、择。第 d 层最多有2d-1 个结点，所以不同二叉树的棵数有 2d-1 棵。(2).深度为 d 的满二叉树的不同二叉树棵数。（分数：4.00）_正确答案：()解析：深度为 d 的不同的满二叉树只有 1 棵。2.画出一个二叉树，使得它既满足大根堆的要求又满足二叉排序树的要求。 （分数：4.00）_正确答案：()解析：大根堆要求根结点的关键字值既大于或等于左子女的关键字值又大于或等于右子女的关键字值，二叉排序树要求根结点的关键字值大于左子女的关键字值同时小于右子女的关键字值。两种的交集是：根结点的关键字值大于左子女的关键字值。这意味着是一棵左斜单枝树。但大根堆要求其是完全二叉树，因此最好得到的是如
14、下图所示的只有两个结点的二叉树。 3.给定一个关键字集合25，18，34，9，14，27，42，51，38，假定查找各关键字的概率相同，请画出其最佳二叉排序树。 （分数：4.00）_正确答案：()解析：当各关键字的查找概率相等时，最佳二叉排序树应是高度最小的二叉排序树。构造过程分两步走：首先对各关键字值从小到大排序，然后仿照折半查找的判定树的构造方法构造二叉排序树。这样得到的就是最佳二叉排序树，如下图所示。 已知一棵树的先根次序遍历的结构与其对应二叉树表示(子女-兄弟链表表示)的前序遍历结果相同，树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。请回答以下问题：（分数：8.00）(1)
15、.利用树的先根遍历结果和后根遍历结果能否唯一确定一棵树?举例说明。（分数：4.00）_正确答案：()解析：因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树，因此，根据题目给出的条件，利用树的先根次序遍历结果和后根次序遍历结果能够唯一地确定一棵树。例如，对于下图中左图所示的树，对应二叉树的前序序列为 1，2，3，4，5，6，8，7，中序序列为 3，4，8，6，7，5，2，1。原树的先根遍历序列为 1，2，3，4，5，6，8，7，后根遍历序列为 3，4，8，6，7，5，2，1。 (2).n 个结点的不同形状的树有多少种?（分数：4.00）_正确答案：()解析：确定 n 个结点的不
16、同树的数目可以归结到确定其对应二叉树的计数。因为树转化为二叉树后，根结点没有右子女，该二叉树的计数归结到对应二叉树根下左子树可能有多少种不同构造。可以利用 n-1 个结点的 catalan 函数来计算。下面是一个二叉树的前序遍历的递归算法。 void PreOrder(BiTNode * t) if(t!=NULL) /递归结束条件 coutt-data; /访问(输出)根结点 Preorder(t-lchild); /前序遍历根的左子树 Preorder(t-rchild); /前序遍历根的右子树 （分数：8.00）(1).改写 PreOrder 算法，消去第二个递归调用 PreOrder(
17、t-rchild)；（分数：4.00）_正确答案：()解析：消去第二个递归语句时，视第一个递归语句为一般语句，按尾递归处理。 void preOrder(BiTNode * t) while(t!=NULL) /按尾递归改为循环 coutt-data; PreOrder(t-lchild); t=t-rchild; /向右子树循环 (2).利用栈改写 PreOrder 算法，消去两个递归调用。（分数：4.00）_正确答案：()解析：定义一个栈，在访问某一个结点时保存其右、左子女结点的地址。下一步将先从栈中退出右子女结点，对其进行遍历，然后从栈中退出左子女结点，对其进行遍历。 void PreO
18、rder(BiTNode * t) BiTNode * p; Stack S;initStack(S);push(S,t); while (!IsEmpty(s) pop (S,p); coutp-data; if(p-rchild!=NULL)push(S,p-rchild); if(p-lchild!=NULL)push(S,p-ichild); 请回答下列关于图的一些问题：（分数：15.00）(1).有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?（分数：5.00）_正确答案：()解析：有 n 个顶点的有向强连通图最多有 n(n-1)条边，最少有 n 条边。(2).表示一个有
19、 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?（分数：5.00）_正确答案：()解析：有 1000 个顶点、1000 条边的有向图的邻接矩阵有 1000000 个矩阵元素，其中只有 1000 个非零元素，是一个稀疏矩阵。注意，它不一定是对称的。(3).对于一个有向图，不用拓扑排序，如何判断图中是否存在环?（分数：5.00）_正确答案：()解析：对一个有向图，还可以用以下方法判断图中是否存在环：如果图中所有顶点的出度至少为 1，入度也至少为 1，则图中存在环。这个条件太强。如果对图进行深度优先搜索，从某个顶点出发，又走到以前已经访问过的顶点，则图中存在环。
20、4.在有关图的算法中常用到两个图的操作： int getFirstNeighbor (Graph G,int v); /取顶点 v 的第一个邻接顶点 int getNextNeighbor(Graph G,int v,int w); /取邻接顶点 w 的下一邻接顶点 试分别给出在邻接矩阵和邻接表为存储结构的情形下它们的实现。 （分数：5.00）_正确答案：()解析：(1)用邻接矩阵做存储结构的场合。 为了找到顶点 v 的第一个临界顶点，顺序地检测邻接矩阵的第 v 行，最先遇到的非零元素(带权图情形是小于 maxValue 的元素)就是顶点 v 的第一个邻接顶点。从这个矩阵元素继续向后找，就可以
21、以类似的判断找到下一个邻接顶点。 int getFirstNeighbor(GraphmtxcolG.numvertices;col+) if(G.Edgevcol0 return-1; int getNextNeighbor(Graphmtx colG.numVertices;col+) if(G.Edgevcol0 return-1; (2)用邻接表作存储结构的场合。 为了找到顶点 v 的第一个邻接顶点，检测邻接表第 v 个边链表，如果链表非空，第一个边结点中 dest 域存放的顶点(号)就是顶点 v 的第一个邻接顶点。在此链表中该边结点的下一个边结点就是下一个邻接顶点。int getFirstNeighbor(Graphlnk /对应边链表第一个边结点 if(p!=NULL)return p-dest; /存在,返回第一个邻接顶点 Return-1; /第一个邻接顶点不存在 int getNextNeighbor(Graphlnk /对应边链表第一个边结点 while (p!=NULL /寻找邻接顶点 w if (p!=NULL /返回下一个邻接顶点 return-1; /下一邻接顶点不存在
