1、数据结构自考题分类模拟 2 及答案解析(总分：76.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.顺序表便于_（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点2.对于二叉树 T，其度数为 1 的结点数为 4，终端结点数为 5，那么该二叉树共有_个结点。（分数：2.00）A.9B.12C.13D.143.采用分治法进行排序的方法是 _（分数：2.00）A.快速排序B.插入排序C.堆排序D.希尔排序4.下面的程序在执行时，S 语句共被执行了 _ 次。 i=1; while(i=n) for(j=i;jn;j+) S ; i=i+1; （
2、分数：2.00）A.B.C.D.5.指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 _（分数：2.00）A.pnext=r; qnext=rnext; rnext=q;B.pnext=r; rnext=q; qnext=rnext;C.rnext=q; qnext=rnext; pnext=r;D.rnext=q; pnext=r; qnext=rnext;6.非空的循环单链表 head 的尾结点(由指针 p 所指)满足 _（分数：2.00）A.pnext=NULLB.p=NULLC.pnext=headD.p=head7.栈一般情况下
3、常采用以下两种存储方式 _（分数：2.00）A.顺序结构和散列结构B.散列结构和链式结构C.线性结构和非线性结构D.顺序存储结构和链式结构8.栈中有 a、b 和 c 三个元素，a 是栈底元素，c 是栈顶元素，元素 d 等待进栈，则不可能的出栈序列是_（分数：2.00）A.dcbaB.cbdaC.cadbD.cdba9.若已知一个栈的输入序列为 1,2,3,n，其输出序列为 P 1 ，P 2 ，P n 。若 P 1 =n，则 P 1 为 _（分数：2.00）AiB.n=iC.n-i+lD.不确定10.树的后序遍历等价于该树对应二叉树的_（分数：2.00）A.层次遍历B.前序遍历C.中序遍历D.后
4、序遍历二、填空题(总题数：8，分数：16.00)11.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 1 的数目正相关。 （分数：2.00）12.对任何一棵二叉树，若其终端结点数为 m 0 ，度数为 2 的结点数为 m 2 ，那么 m 0 和 m 2 之间的关系是 1。 （分数：2.00）13.文件的记录均存放在数据集中，数据集中的一个结点称为 1，它是一个 2 操作的基本单位。 （分数：2.00）14.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。 （分数：2.00）15.对于一个具有 n 条边和 e 个顶点的图来说，如果采用邻接表表示，则其空间
5、复杂度为 1，若采用邻接矩阵表示，则其空间复杂度为 2。 （分数：2.00）16.已知一棵哈夫曼树含有 60 个叶子结点，则该树中共有 1 个非叶子结点。 （分数：2.00）17.就文件而言，按用户的观点所确定的基本存储单元称为 1。按外设的观点所确定的基本存储单元称为 2。 （分数：2.00）18. 1 的有向图，其全部顶点有可能排成一个拓扑序列。 （分数：2.00）三、解答题(总题数：3，分数：15.00)19.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数：5.00）_20.画出下图所示有向图的所有强连通分量。 （分数：5.00）_21.对序列(48,37,63
6、,96,22,31,50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。 初始堆： 第 1 趟： 第 2 趟： （分数：5.00）_四、算法阅读题(总题数：2，分数：15.00)22.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x * =2;count+; return(count) （分数：5.00）_假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int
7、score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(A,B)后 A 所指的链表； （分数：10.00）_五、算法设计题(总题数：1，分数：10.00)23.二叉树的存储结构类型定义如下： typedef struct node int data; struct node *lchild, *rchild; BinNode; typedef BinNode *BinTree; 编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的
8、和。 函数的原型为：void f34(BinTree T, int *count, int *sum) *count 和*sum 的初值为 0。 （分数：10.00）_数据结构自考题分类模拟 2 答案解析(总分：76.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.顺序表便于_（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点 解析：考点 顺序表的特征 解析 顺序表便于按序号查找结点。2.对于二叉树 T，其度数为 1 的结点数为 4，终端结点数为 5，那么该二叉树共有_个结点。（分数：2.00）A.9B.12C.13 D.14解析：考点
9、 二叉树中度数为 2 的结点个数与终端结点个数之间的关系 解析 根据终端结点有 5 个，可推知度数为 2 的结点有 4 个，所以此二叉树共有 13 个结点。3.采用分治法进行排序的方法是 _（分数：2.00）A.快速排序 B.插入排序C.堆排序D.希尔排序解析：4.下面的程序在执行时，S 语句共被执行了 _ 次。 i=1; while(i=n) for(j=i;jn;j+) S ; i=i+1; （分数：2.00）A. B.C.D.解析：5.指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 _（分数：2.00）A.pnext=r; qne
10、xt=rnext; rnext=q; B.pnext=r; rnext=q; qnext=rnext;C.rnext=q; qnext=rnext; pnext=r;D.rnext=q; pnext=r; qnext=rnext;解析：6.非空的循环单链表 head 的尾结点(由指针 p 所指)满足 _（分数：2.00）A.pnext=NULLB.p=NULLC.pnext=head D.p=head解析：7.栈一般情况下常采用以下两种存储方式 _（分数：2.00）A.顺序结构和散列结构B.散列结构和链式结构C.线性结构和非线性结构D.顺序存储结构和链式结构 解析：8.栈中有 a、b 和 c
11、三个元素，a 是栈底元素，c 是栈顶元素，元素 d 等待进栈，则不可能的出栈序列是_（分数：2.00）A.dcbaB.cbdaC.cadb D.cdba解析：考点 栈的操作 解析 根据栈的操作原则，不可能的出栈序列是 cadb。9.若已知一个栈的输入序列为 1,2,3,n，其输出序列为 P 1 ，P 2 ，P n 。若 P 1 =n，则 P 1 为 _（分数：2.00）AiB.n=iC.n-i+l D.不确定解析：10.树的后序遍历等价于该树对应二叉树的_（分数：2.00）A.层次遍历B.前序遍历C.中序遍历 D.后序遍历解析：考点 树的遍历与二叉树遍历的关系 解析 树的后序遍历等价于该树对应
12、的二叉树的中序遍历。二、填空题(总题数：8，分数：16.00)11.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 1 的数目正相关。 （分数：2.00）解析：边12.对任何一棵二叉树，若其终端结点数为 m 0 ，度数为 2 的结点数为 m 2 ，那么 m 0 和 m 2 之间的关系是 1。 （分数：2.00）解析：m 0 =m 2 +1 考点 二叉树中，终端结点的个数和度数为 2 的结点的个数之间的关系 解析 终端结点的个数和度数为 2 的结点的个数之间的关系为 m 0 =m 2 +1。13.文件的记录均存放在数据集中，数据集中的一个结点称为 1，它是一个 2 操作的基本单位
13、。 （分数：2.00）解析：控制区间 I/014.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。 （分数：2.00）解析：稳定15.对于一个具有 n 条边和 e 个顶点的图来说，如果采用邻接表表示，则其空间复杂度为 1，若采用邻接矩阵表示，则其空间复杂度为 2。 （分数：2.00）解析：O(n+c) O(n 2 )16.已知一棵哈夫曼树含有 60 个叶子结点，则该树中共有 1 个非叶子结点。 （分数：2.00）解析：5917.就文件而言，按用户的观点所确定的基本存储单元称为 1。按外设的观点所确定的基本存储单元称为 2。 （分数：2.00）解析：逻辑记录 物理记录
14、18. 1 的有向图，其全部顶点有可能排成一个拓扑序列。 （分数：2.00）解析：存在入度为 O 的结点且没有回路三、解答题(总题数：3，分数：15.00)19.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数：5.00）_正确答案：()解析：从三元组表还原稀疏矩阵时，首先根据表的第 1 行得出稀疏矩阵的行数和列数，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1)，(2)所示。 20.画出下图所示有向图的所有强连通分量。 （分数：5.00）_正确答案：
15、()解析：该图的强连通分量分别为： 21.对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。 初始堆： 第 1 趟： 第 2 趟： （分数：5.00）_正确答案：()解析：初始堆：(96,55,63,48,22,31,50,37,11) 第 1 趟：(63,55,50,48,22,3l,11,37,96) 第 2 趟：(55,48,50,37,22,31,11,63,96)四、算法阅读题(总题数：2，分数：15.00)22.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int T
16、ime int n count=0;x=2; while(xn/2) x * =2;count+; return(count) （分数：5.00）_正确答案：()解析：count=log 2 n假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(A,B)后 A 所指的链表； （分数：10.00）_正确答
17、案：()解析：_正确答案：()解析：对于表 A 中成绩低于 60 的学生，如果在表 B 中也有成绩记录，则将表 A 中的成绩修改为其在表 B中的成绩；但若其在表 B 中的成绩高于 60 分，则只改为 60 分。五、算法设计题(总题数：1，分数：10.00)23.二叉树的存储结构类型定义如下： typedef struct node int data; struct node *lchild, *rchild; BinNode; typedef BinNode *BinTree; 编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。 函数的原型为：void f34(BinTree T, int *count, int *sum) *count 和*sum 的初值为 0。 （分数：10.00）_正确答案：()解析：void f34(BinTree T, int *count, int *sum) if(T) if(T-lchild *sum+=T-data; f34(T-lchild, count, sum); f34(T-rchild, count, sum); 考点 求只有一个孩子结点的结点总数，并计算这些结点的数据值的和的算法
