1、数据结构导论自考题模拟 8 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.算法指的是_（分数：2.00）A.计算方法B.排序方法C.解决某一问题的有限运算序列D.调度方法2.在一个单链表中，若 p 所指结点不是最后结点，s 指向已生成的新结点，则在 p 之后插入 s 所指结点的正确操作是_（分数：2.00）A.s-next=p-next；p-next=s；B.p-next=s-next；s-next=p；C.s-next=p；p-next=s；D.s-next=p-next；p=s；3.下面关于线性表的叙述中，错误的是_（分数：2.0
2、0）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用链接存储，不必占用一片连续的存储单元C.线性表采用顺序存储，便于进行插入和删除操作D.线性表采用链接存储，便于进行插入和删除操作4.设一个栈的输入序列为 ABCD，则所得到的输出序列不可能是_（分数：2.00）A.ABCDB.DCBAC.ACDBD.DABC5.在队列中存取数据的原则是_（分数：2.00）A.后进先出B.先进先出C.先进后D.随意进出6.一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都大于它的左子树上所有结点的值，而小于右子树上所有结点的值。现为得到这棵二叉树所有结点的递增序列，应采用的遍历方式是
3、_（分数：2.00）A.先序遍历B.中序遍历C.后序遍历D.层次遍历7.可以唯一地转化成一棵一般树的二叉树的特点是_（分数：2.00）A.根结点无左孩子B.根结点无右孩子C.根结点有两个孩子D.根结点没有孩子8.设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是_ A.2h B.2h-1 C.2h-1 D.2h+1-1（分数：2.00）A.B.C.D.9.无向图中一个顶点的度是指图中_（分数：2.00）A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数10.任何一个带权的无向连通图的最小生成树_（分数：2.00）A.只有一棵B.
4、一定有多棵C.有一棵或多棵D.可能不存在11.在图 G 卢求两个结点之间的最短路径可以采用的算法是_（分数：2.00）A.迪杰斯特拉(Dijkstra)算法B.克鲁斯卡尔(Kruskal)算法C.普里姆(Prim)算法D.广度优先遍历(BFS)算法12.静态查找表与动态查找表二者的根本区别在于_（分数：2.00）A.它们的逻辑结构不同B.施加在其上的操作不同C.所包含的数据元素的类型不同D.存储实况不一样13.当采用分块查找时，数据的组织方式为_（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数
5、据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同14.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是_（分数：2.00）A.直接插入排序和快速排序B.直接插入排序和归并排序C.直接选择排序和归并排序D.快速排序和归并排序15.一组记录的键值为(12，38，35，25，74，50，63，90)，按二路归并排序方法对该序列进行一趟归并后的结果为_（分数：2.00）A.12，38，25，35，50，74，63，90B.12，38，35，25，74，50，63，90C.12，25，35，38，50，74，63，90D.
6、12，35，38，25，63，50，74，90二、填空题(总题数：13，分数：26.00)16.对相同输入数据量的不同输入数据，算法时间用量的最大值是指 1 。 （分数：2.00）17.在顺序表中插入和删除一个元素，需要移动元素，具体移动的元素个数与 1 有关。 （分数：2.00）18.双向循环链表是一种对称结构，它既有前向链又有后向链，设指针 p 指向某一结点，则双向循环链表结构的对称性可描述为 1。 （分数：2.00）19.向一个不带头结点的栈指针为 lst 的链栈中插入一个*s 所指结点时，则执行语句为 1。 （分数：2.00）20.顺序队列由一个 1 及两个分别指示队列首元素和队列尾元
7、素的变量组成。 （分数：2.00）21.一维数组又称 1，它由一组具有相同类型的数据元素组成。 （分数：2.00）22.每个二叉链表还必须有一个指向 1 结点的指针，该指针具有标识二叉链表的作用。 （分数：2.00）23.若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必须是该子树的后序遍历序列中的 1 个结点。 （分数：2.00）24.哈夫曼树是访问叶结点的外部路径长度 1 的二叉树。 （分数：2.00）25.任何两点之间都有弧的有向图称为 1。 （分数：2.00）26.要完全避免散列所产生的“堆积”现象，通常采用 1 法。 （分数：2.00）27.在最好的情况下，对于具有 n
8、个元素的有序序列，若采用冒泡排序，所需的比较次数为 1 次。 （分数：2.00）28.归并排序的基础是 1。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.将下图所示的森林转换成二叉树。 （分数：6.00）_30.已知二叉树如下： （分数：6.00）_要在0n-1的向量空间中建立两个栈 stack1 和 stack2，请回答：（分数：6.00）(1).应该如何设计这两个栈才能充分利用整个向量空间?（分数：3.00）_(2).若 stack1 的栈项指针为 top1，stack2 的栈顶指针为 top2，如果需要充分利用整个向量空间，则： 栈 stack1 空的条件是：_ ；
9、 栈 stack2 空的条件是：_； 栈 stack1 和栈 stack2 满的条件是：_。（分数：3.00）_31.设散列函数 H(key)=key mod 11，给定键值序列为(13，41，15，44，6，68，17，26，39，46)，试画出以链地址法解决冲突的散列表。 （分数：6.00）_32.已知数据序列为(15，7，6，9，17，24，22)，对该数据序列进行排序，试写出插入排序每趟的结果。 （分数：6.00）_四、算法设计题(总题数：2，分数：14.00)33.试编写在不带头结点的单链表上实现线性表基本运算 LENGTH(L)的算法。 （分数：7.00）_34.写出建立一个有向图
10、的逆邻接表的算法。 （分数：7.00）_数据结构导论自考题模拟 8 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.算法指的是_（分数：2.00）A.计算方法B.排序方法C.解决某一问题的有限运算序列 D.调度方法解析：考点 本题主要考查的知识点是算法。 一个算法规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被求解。2.在一个单链表中，若 p 所指结点不是最后结点，s 指向已生成的新结点，则在 p 之后插入 s 所指结点的正确操作是_（分数：2.00）A.s-next=p-next；p-ne
11、xt=s； B.p-next=s-next；s-next=p；C.s-next=p；p-next=s；D.s-next=p-next；p=s；解析：3.下面关于线性表的叙述中，错误的是_（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用链接存储，不必占用一片连续的存储单元C.线性表采用顺序存储，便于进行插入和删除操作 D.线性表采用链接存储，便于进行插入和删除操作解析：考点 本题主要考查的知识点是线性表。 顺序存储结构的地址在内存中是连续的，所以可以通过计算地址实现随机存取，而链式存储结构的存储地址不一定是连续的，只能通过第一个结点的指针顺序存取。4.设一个栈的
12、输入序列为 ABCD，则所得到的输出序列不可能是_（分数：2.00）A.ABCDB.DCBAC.ACDBD.DABC 解析：考点 本题主要考查的知识点为栈的出栈顺序。 若出栈序列的第一个元素为 D，则出栈序列只能是 DCBA。本题答案为 D。5.在队列中存取数据的原则是_（分数：2.00）A.后进先出B.先进先出 C.先进后D.随意进出解析：6.一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都大于它的左子树上所有结点的值，而小于右子树上所有结点的值。现为得到这棵二叉树所有结点的递增序列，应采用的遍历方式是_（分数：2.00）A.先序遍历B.中序遍历 C.后序遍历D.层次遍历解析：
13、考点 本题主要考查的知识点是二叉树的中序遍历。 此二叉树结点的值大小顺序为：左子树根右子树。若要得到递增序列，访问顺序应为左子树、根、右子树，满足中序遍历方式。7.可以唯一地转化成一棵一般树的二叉树的特点是_（分数：2.00）A.根结点无左孩子B.根结点无右孩子 C.根结点有两个孩子D.根结点没有孩子解析：8.设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是_ A.2h B.2h-1 C.2h-1 D.2h+1-1（分数：2.00）A.B.C.D. 解析：考点 本题主要考查的知识点是满二叉树的结点个数。 由题可得满二叉树的深度为 h+1，根据二叉树性质 2 可得其结点数为
14、2 h+1 -1。9.无向图中一个顶点的度是指图中_（分数：2.00）A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数 C.通过该顶点的回路数D.与该顶点连通的顶点数解析：10.任何一个带权的无向连通图的最小生成树_（分数：2.00）A.只有一棵B.一定有多棵C.有一棵或多棵 D.可能不存在解析：11.在图 G 卢求两个结点之间的最短路径可以采用的算法是_（分数：2.00）A.迪杰斯特拉(Dijkstra)算法 B.克鲁斯卡尔(Kruskal)算法C.普里姆(Prim)算法D.广度优先遍历(BFS)算法解析：12.静态查找表与动态查找表二者的根本区别在于_（分数：2.00）A.它们的逻辑结
15、构不同B.施加在其上的操作不同 C.所包含的数据元素的类型不同D.存储实况不一样解析：考点 本题主要考查的知识点是静态查找表和动态查找表。 静态查找表的基本运算有：建表、查找、读表中元素，而动态查找表除了可以进行查找、读表中元素外还可进行插入、删除、初始化运算。13.当采用分块查找时，数据的组织方式为_（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块 C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同解析：考点 本题主要考
16、查的知识点是分块查找。 分块查找要求把线性表分成若干块，在每一块中结点的存放是任意的，也不严格要求每块中的元素的个数相等，但是，块与块之间必须有序。14.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是_（分数：2.00）A.直接插入排序和快速排序B.直接插入排序和归并排序C.直接选择排序和归并排序 D.快速排序和归并排序解析：考点 本题主要考查的知识点是直接选择排序和归并排序。 选择排序是每一趟从待排序的记录中选出关键字最小的记录，顺序放在已经排好序的记录的后面，直至排序完毕，键值的比较次数与初始序列的顺序无关。而归并排序是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，排
17、序时与初始序列的顺序无关。15.一组记录的键值为(12，38，35，25，74，50，63，90)，按二路归并排序方法对该序列进行一趟归并后的结果为_（分数：2.00）A.12，38，25，35，50，74，63，90 B.12，38，35，25，74，50，63，90C.12，25，35，38，50，74，63，90D.12，35，38，25，63，50，74，90解析：二、填空题(总题数：13，分数：26.00)16.对相同输入数据量的不同输入数据，算法时间用量的最大值是指 1 。 （分数：2.00）解析：最坏时间复杂度17.在顺序表中插入和删除一个元素，需要移动元素，具体移动的元素个数与
18、 1 有关。 （分数：2.00）解析：该元素在表中的位置18.双向循环链表是一种对称结构，它既有前向链又有后向链，设指针 p 指向某一结点，则双向循环链表结构的对称性可描述为 1。 （分数：2.00）解析：p-prior-next=p=p-next-prior19.向一个不带头结点的栈指针为 lst 的链栈中插入一个*s 所指结点时，则执行语句为 1。 （分数：2.00）解析：s-next=1st：lst=s：20.顺序队列由一个 1 及两个分别指示队列首元素和队列尾元素的变量组成。 （分数：2.00）解析：一维数组21.一维数组又称 1，它由一组具有相同类型的数据元素组成。 （分数：2.00
19、）解析：向量22.每个二叉链表还必须有一个指向 1 结点的指针，该指针具有标识二叉链表的作用。 （分数：2.00）解析：根23.若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必须是该子树的后序遍历序列中的 1 个结点。 （分数：2.00）解析：第一24.哈夫曼树是访问叶结点的外部路径长度 1 的二叉树。 （分数：2.00）解析：最短25.任何两点之间都有弧的有向图称为 1。 （分数：2.00）解析：有向完全闭26.要完全避免散列所产生的“堆积”现象，通常采用 1 法。 （分数：2.00）解析：公共溢出区27.在最好的情况下，对于具有 n 个元素的有序序列，若采用冒泡排序，所需的比
20、较次数为 1 次。 （分数：2.00）解析：n-128.归并排序的基础是 1。 （分数：2.00）解析：合并三、应用题(总题数：5，分数：30.00)29.将下图所示的森林转换成二叉树。 （分数：6.00）_正确答案：()解析：转换后的二叉树如下图所示： 30.已知二叉树如下： （分数：6.00）_正确答案：()解析：转换后的森林如下图所示： 要在0n-1的向量空间中建立两个栈 stack1 和 stack2，请回答：（分数：6.00）(1).应该如何设计这两个栈才能充分利用整个向量空间?（分数：3.00）_正确答案：()解析：采用双向栈的形式，stack1 的栈底设置在从数组下标为 0 的元
21、素处，stack2 的栈底设置在数组下标为 n-1 的元素处。(2).若 stack1 的栈项指针为 top1，stack2 的栈顶指针为 top2，如果需要充分利用整个向量空间，则： 栈 stack1 空的条件是：_ ； 栈 stack2 空的条件是：_； 栈 stack1 和栈 stack2 满的条件是：_。（分数：3.00）_正确答案：()解析：top1=0 top2=n-1 top1+1=top231.设散列函数 H(key)=key mod 11，给定键值序列为(13，41，15，44，6，68，17，26，39，46)，试画出以链地址法解决冲突的散列表。 （分数：6.00）_正确答
22、案：()解析：所求散列表如下图所示： 32.已知数据序列为(15，7，6，9，17，24，22)，对该数据序列进行排序，试写出插入排序每趟的结果。 （分数：6.00）_正确答案：()解析：插入排序的每趟的结果： 初始键值序列 15 7 6 9 17 24 22 i=215 7 6 9 17 24 22 i=37 15 6 9 17 24 22 i=46 7 159 17 24 22 i=56 7 9 1517 24 22 i=66 7 9 15 1724 22 i=76 7 9 15 17 2422 排序结果6 7 9 15 1 7 22 24四、算法设计题(总题数：2，分数：14.00)33
23、.试编写在不带头结点的单链表上实现线性表基本运算 LENGTH(L)的算法。 （分数：7.00）_正确答案：()解析：算法描述如下： int length_lklist(LinkList head) LinkList p； int Len； p=head； Len=0； while(p!=NULL) len+； p=p-next； return len； 34.写出建立一个有向图的逆邻接表的算法。 （分数：7.00）_正确答案：()解析：算法描述如下： Create_Inverse_Adjlist(GraphTp*ga) int n，e，i，j，k； ArcNodeTp*p； seanf(“%d%d“，n，e)；/读入顶点数和边数 ga-vexnum=n；ga-arcnum=e； for(i=0；in；i+) ga-adjlisi.vertex=i；/初始化逆邻接表 ga-adjlisi.firstarc=NULL； for(k=0；ke；k+) scanf(“%d%d“，/读入弧i，j p=(ArcNodeTp*)malloc(sizeof(AreNodeTp)； p-adjvex=i： p-nextarc=ga-adjlisj.firstarc； ga-adjlisj.firstarc=p；
