数据结构第2阶段测试题

1、江南大学现代远程教育 第二阶段测试卷考试科目:数据结构第五章至第七章（总分100分） 时间：90分钟_学习中心（教学点） 批次： 层次： 专业： 学号： 身份证号： 姓名： 得分： 一、选择题（每题3分，共30分）1、将一个A1.100，1.100的三对角矩阵，按行优先存入一维数组B1.298中，则A中的元素A66，65在数组B中的位置K=（ ）。、195、196、197、1982、广义表(a,(b,(),c)的深度为（ ）。、1、2、3、43、下列叙述中错误的是（ ）。A、树的度与该树中结点的度的最大值相等B、二叉树就是度为2的有序树C、有5个叶子结点的二叉树中必有4个度为2的结点D、满二叉

2、树一定是完全二叉树4、一棵二叉树中第层上最多有（ ）个结点。、5、由树转换而得的二叉树，根结点（ ）。、没有左子树、没有右子树、左右子树都有、视树的形态而定6、一棵高为k的二叉树最少有（ ）个结点。、k-1、k、k+1、2k-1、2k-17、含n个顶点的有向图最多有（ ）条弧。、n、n(n-1)、n(n+1)、n28、设对下图从顶点a出发进行深度优先遍历，则（ ）是可能得到的遍历序列。、acfgdeb、abcdefg、acdgbef、abefgcd9、设图的邻接矩阵A=，则图中共有（ ）个顶点。、1、3、4、910、具有n个顶点的有向强连通图最少有（ ）条弧。、n-1、n、n(n-1)、n(n

3、-1)/2二、（10分）试将下图中的树转化为二叉树。三、（10分）试写出对如下无向图从顶点出发进行广度优先遍历可能得到的所有遍历序列。四、（15分）设有向网如下，试用迪杰斯特拉算法求从顶点出发到其余各顶点的最短路径。五、（15分）一棵深度为的满叉树有如下性质：第层上的结点都是叶子结点，其余各层上每个结点都有棵非空子树。若按层次顺序从开始对全部结点编号，则：第层上有多少个结点？编号为的结点的第个孩子结点（若存在）的编号是多少？编号为的结点的双亲结点（若存在）的编号是多少？六、（20分）试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。答案一、选择题1、A2、C3、B4、C5、B6、B7、B8

4、、A9、B10、B二、试将下图中的树转化为二叉树。答：三、试写出对如下无向图从顶点出发进行广度优先遍历可能得到的所有遍历序列。答：ABCEGHFDABCEHGFDACBGHEDFACBHGEDF四、设有向网如下，试用迪杰斯特拉算法求从顶点出发到其余各顶点的最短路径。答：DPATHDPATHDPATHDPATHA0/0/0/0/B11110ACDB18ACDEBC22AC2/AC2/AC2/ACD37AD35ACD3/ACD3/ACDE4446ACDE4/ACDEF556ACF56ACF56ACFG66613ACDG613ACDGDPATHDPATHDPATHA0/0/0/B18ACDEB1/A

5、CDEG1/ACDEGC2/AC2/AC2/ACD3/ACD3/ACD3/ACDE4/ACDE4/ACDE4/ACDEF5/ACF5/ACF5/ACFG612ACFG610ACFGE6/ACFGE五、一棵深度为的满叉树有如下性质：第层上的结点都是叶子结点，其余各层上每个结点都有棵非空子树。若按层次顺序从开始对全部结点编号，则：第层上有多少个结点？编号为的结点的第个孩子结点（若存在）的编号是多少？编号为的结点的双亲结点（若存在）的编号是多少？答：第1层有1个结点，第i层结点数第i-1层结点数*k（2iH）=个当根结点以及前面的p-1个结点的孩子都编了号之后，才开始为结点p的孩子编号。结点p的第i

6、个孩子的编号为（）。若，则为根结点，无双亲，否则可设双亲结点编号为，由可知结点的孩子结点的编号范围为（）（），即，又由为整数，可得。六、试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。答：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->