1、数据结构导论自考题模拟 14 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.算法指的是_（分数：2.00）A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列2.下面程序段的时间复杂度是_ for(i=0;in;i+) for(j=1;jm;j+) Aij=0;（分数：2.00）A.O(m*n)B.O(m+n+1)C.O(m+n)D.O(n)3.队和栈的主要区别是_（分数：2.00）A.逻辑结构不同B.限定插入和删除的位置不同C.所包含的运算个数不同D.存储结构不同4.设 p 指向单链表中的一个结点，s 指向待插
2、入的结点，则下述程序段的功能是_ s-next=p-next;p-next=s; t=p-data;p-data=s-data;s-data=t;（分数：2.00）A.结点*p 与结点*s 的数据域互换B.在 p 所指结点的元素之前插入元素C.在 p 所指结点的元素之后插入元素D.在结点*p 之前插入结点*s5.队列用链接方式存储，在进行删除运算时_（分数：2.00）A.头、尾指针可能都要修改B.仅修改头指针C.仅修改尾指针D.头、尾指针都要修改6.根据定义，树的叶子结点其度数_（分数：2.00）A.必大于 0B.必等于 1C.必等于 0D.必等于 27.二维数组 A1218采用列优先的存储方
3、法，若每个元素各占 3 个存储单元，且第 1 个元素的地址为150，则元素 A97的地址为_（分数：2.00）A.432B.429C.435D.4388.下图所示二叉树的中序遍历序列是_ （分数：2.00）A.abcdgefB.dbaefcgC.dfebageD.defbagc9.在含 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为_ A.e B.2e C.n2-e D.n2-2e（分数：2.00）A.B.C.D.10.已知一个图如下所示，从顶点 a 出发进行广度优先遍历可能得到的序列为_ （分数：2.00）A.acefbdB.acbdefC.acbdfeD.acdbfe11.对
4、n 个关键字的序列进行快速排序，平均情况下的时间复杂度为_（分数：2.00）A.O(nlog2n)B.O(log2n)C.O(n)D.O(1)12.利用散列技术实现动态查找表的基本出发点是_（分数：2.00）A.查找过程中不再需要比较操作B.增加查找过程中的比较次数C.减少查找过程中的比较次数D.节省存储空间13.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为_（分数：2.00）A.堆排序B.归并排序C.冒泡排序D.插入排序14.排序趟数与序列的原始状态有关的排序方法是_（分数：2.00）A.插入排序法B.冒泡排序法C.二路归并排序
5、法D.选择排序法15.下列排序方法中，属于不稳定的排序方法是_（分数：2.00）A.选择排序B.冒泡排序法C.基数排序法D.直接插入排序法二、填空题(总题数：13，分数：26.00)16.从逻辑关系上讲，数据结构主要分为两大类，分别是 1 和 2。 （分数：2.00）17.队列的修改是按 1 的原则进行的。 （分数：2.00）18.栈下溢是指在 1 时进行出栈操作。 （分数：2.00）19.设某非空双链表，其结点形式为 （分数：2.00）20.已知循环队列的存储空间大小为 m，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是
6、1。 （分数：2.00）21.已知完全二叉树 T 的第 5 层只有 7 个结点，则该树共有 1 个叶子结点。 （分数：2.00）22.n 个顶点的无向图 G 用邻接矩阵 Ann存储，其中第 i 列的所有元素之和等于顶点 V i 的 1。 （分数：2.00）23.n 个顶点且含有环路的无向连通图中，至少含有 1 条边。 （分数：2.00）24.已知一组关键字为15，36，28，97，24，78，47，52，13，86，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是 1。 （分数：2.00）25.在一般情况，下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次
7、数最少的是 1。 （分数：2.00）26.二分查找的时间复杂度为 1。 （分数：2.00）27.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 1 结构也无特殊要求。 （分数：2.00）28.依次插入关键字 37，50，42，18，48，12，56，30，23，构造一棵二叉排序树，并计算平均查找长度 1。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.在栈的输入端，元素的输入顺序为 1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1 和 1，5，4，6，2，3?若能，写出进栈、退栈过程；若不能，简述理由(用 push(
8、x)表示 x 进栈，pop(x)表示 x 退栈)。 （分数：6.00）已知一个无向图 G=(V，E)，其中 V=A，B，C，D，E，F，邻接矩阵表示如下图所示。 （分数：6.00）(1).请画出对应的图 G。（分数：3.00）(2).画出图 G 的邻接表存储结构。（分数：3.00）30.一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为 CBDAEGF，试构造出该二叉树。 （分数：6.00）31.用冒泡排序法对数据序列(49，38，65，97，76，134，27，49)进行排序，写出排序过程，并说明冒泡排序是否为稳定排序。 （分数：6.00）32.下述矩阵表示一个无向连通网，试画出它所
9、表示的连通网及该连通网的最小生成树。 （分数：6.00）四、算法设计题(总题数：2，分数：14.00)33.若循环单链表长度大小 1，q 为指向链表中某结点的指针，试编写一算法，删除 q 结点的前驱结点。 （分数：7.00）_34.试写出二分查找的递归算法。 （分数：7.00）_数据结构导论自考题模拟 14 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.算法指的是_（分数：2.00）A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列 解析：考点 算法的定义 解析 算法是为了某一特定问题而制定的求解步骤的一种描述，
10、它是有限的指令序列。它的特性有零个或多个输入，一个或多个输出，确定性，有穷性，有效性。2.下面程序段的时间复杂度是_ for(i=0;in;i+) for(j=1;jm;j+) Aij=0;（分数：2.00）A.O(m*n) B.O(m+n+1)C.O(m+n)D.O(n)解析：考点 时间复杂度的计算 解析 第一重循环 n，嵌套循环 m，时间复杂度为 mn。3.队和栈的主要区别是_（分数：2.00）A.逻辑结构不同B.限定插入和删除的位置不同 C.所包含的运算个数不同D.存储结构不同解析：考点 栈和队列的区别 解析 栈后进先出，队列先进先出。4.设 p 指向单链表中的一个结点，s 指向待插入的
11、结点，则下述程序段的功能是_ s-next=p-next;p-next=s; t=p-data;p-data=s-data;s-data=t;（分数：2.00）A.结点*p 与结点*s 的数据域互换B.在 p 所指结点的元素之前插入元素C.在 p 所指结点的元素之后插入元素D.在结点*p 之前插入结点*s 解析：考点 链表的插入 解析 根据指针的修改，确定选项 D 正确。5.队列用链接方式存储，在进行删除运算时_（分数：2.00）A.头、尾指针可能都要修改 B.仅修改头指针C.仅修改尾指针D.头、尾指针都要修改解析：考点 队列用链接方式存储时的删除运算 解析 队列用链接方式存储，在进行删除运算
12、时，头尾指针可能都要修改。6.根据定义，树的叶子结点其度数_（分数：2.00）A.必大于 0B.必等于 1C.必等于 0 D.必等于 2解析：考点 树的叶子结点的度 解析 树的叶子结点的度是 0。7.二维数组 A1218采用列优先的存储方法，若每个元素各占 3 个存储单元，且第 1 个元素的地址为150，则元素 A97的地址为_（分数：2.00）A.432B.429 C.435D.438解析：考点 数组元素地址是运算 解析 对于，nn 的数组采取列优先存储时，Loci,j=Loc0,0+(jm+i)*k=150+(712+9)3=429。8.下图所示二叉树的中序遍历序列是_ （分数：2.00）
13、A.abcdgefB.dbaefcgC.dfebage D.defbagc解析：考点 二叉树的中序遍历 解析 二叉树的中序遍历顺序是、左子树、根、右子树。9.在含 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为_ A.e B.2e C.n2-e D.n2-2e（分数：2.00）A.B.C.D. 解析：考点 无向图的邻接矩阵存储 解析 无向图邻接矩阵的对称性，0 元素的个数为 n 2 -2e。10.已知一个图如下所示，从顶点 a 出发进行广度优先遍历可能得到的序列为_ （分数：2.00）A.acefbdB.acbdef C.acbdfeD.acdbfe解析：考点 图的广度优先遍历 解
14、析 图的广度优先遍历算法。11.对 n 个关键字的序列进行快速排序，平均情况下的时间复杂度为_（分数：2.00）A.O(nlog2n) B.O(log2n)C.O(n)D.O(1)解析：考点 快速排序的空间复杂度 解析 快速排序的 3 个步骤：找到序列中用于划分序列的元素；用元素划分序列；对划分后的两个序列重复 1，2 两个步骤指导序列无法再划分。所以对于 n 个元素其排序时间为： T(n)=2*T(n/2)+n(表示将长度为 n 的序列划分为两个子序列，每个子序列需要 T(n/2)的时间，而划分序列需要 n 的时间)；而 T(1)=1(表示长度为 1 的序列无法划分子序列，只需要 1 的时间
15、即可)； T(n)=2log 2 n+log 2 n*n，n 被不断二分最终只能二分 logn 次(最优的情况，每次选取的元素都均分序列)=n+nlog 2 n。 因此 T(n)=O(nlog 2 n)。12.利用散列技术实现动态查找表的基本出发点是_（分数：2.00）A.查找过程中不再需要比较操作B.增加查找过程中的比较次数C.减少查找过程中的比较次数 D.节省存储空间解析：考点 用散列技术实现动态查找的基本出发点 解析 用散列技术实现动态查找的基本出发点是减少查找过程中的比较次数。13.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法
16、称为_（分数：2.00）A.堆排序B.归并排序C.冒泡排序D.插入排序 解析：考点 插入排序算法 解析 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为插入排序。14.排序趟数与序列的原始状态有关的排序方法是_（分数：2.00）A.插入排序法B.冒泡排序法 C.二路归并排序法D.选择排序法解析：考点 冒泡排序算法 解析 排序趟数与序列的原始状态有关的排序方法是冒泡排序，交换类的排序，其趟数与元素的原始状态有关。直接插入排序、选择排序，排序的趟数不变，为 m-1。基数排序的排序的趟数为 d。15.下列排序方法中，属于不稳定的排序方法是_
17、（分数：2.00）A.选择排序 B.冒泡排序法C.基数排序法D.直接插入排序法解析：考点 排序算法的稳定性 解析 (1)稳定的排序：冒泡排序；直接插入排序；归并排序；基数排序。 (2)不稳定的排序：希尔排序；选择排序；快速排序；堆排序。二、填空题(总题数：13，分数：26.00)16.从逻辑关系上讲，数据结构主要分为两大类，分别是 1 和 2。 （分数：2.00）解析：线性结构 非线性结构 考点 数据的分类 解析 从逻辑上讲，数据结构主要分为两类，分别是线性结构和非线性结构。17.队列的修改是按 1 的原则进行的。 （分数：2.00）解析：先进先出 考点 队列的修改原则 解析 队列的修改是按先
18、进先出的原则进行的。18.栈下溢是指在 1 时进行出栈操作。 （分数：2.00）解析：栈空 考点 栈的操作容易出现的现象 解析 栈下溢是指在栈空时进行出栈操作。19.设某非空双链表，其结点形式为 （分数：2.00）解析：p-next-prior=p-prior 考点 双链表的删除操作 解析 注意双链表的 prior 和 next 都要修改。20.已知循环队列的存储空间大小为 m，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 1。 （分数：2.00）解析：(rear-front+m)%m 考点 循环队列长度的求取 解析 循环
19、队列长度(rear-front+m)%m。21.已知完全二叉树 T 的第 5 层只有 7 个结点，则该树共有 1 个叶子结点。 （分数：2.00）解析：11 考点 完全二叉树的性质 解析 完全二叉树第 5 层最多应有 2 (5-1) =16 个结点7，所以此完全二叉树深度为 5，叶子结点个数为：2 3 +7/2=11。22.n 个顶点的无向图 G 用邻接矩阵 Ann存储，其中第 i 列的所有元素之和等于顶点 V i 的 1。 （分数：2.00）解析：度 考点 用无向图邻接矩阵求取某顶点的度数 解析 n 个顶点的无向图 G 用邻接矩阵 Ann存储，其中第 i 列的所有元素之和等于顶点 V i 的
20、度。23.n 个顶点且含有环路的无向连通图中，至少含有 1 条边。 （分数：2.00）解析：n 考点 有环无向图的特征 解析 n 个顶点且含有环路的无向连通图中，至少含有 n 条边。24.已知一组关键字为15，36，28，97，24，78，47，52，13，86，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是 1。 （分数：2.00）解析：15，28，36，97，24，47，52，78，13，86 考点 二路归并排序算法 解析 二路归并排序算法的运用。25.在一般情况，下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 1。 （分数：2.00）
21、解析：选择排序 考点 排序算法的比较 解析 在一般情况下，用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是选择排序。26.二分查找的时间复杂度为 1。 （分数：2.00）解析：O(log 2 n) 考点 二分查找的时间复杂度 解析 二分查找的时间复杂度为 O(log 2 n)。27.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 1 结构也无特殊要求。 （分数：2.00）解析：存储 考点 二分查找 解析 和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对存储结构也无特殊要求。28.依次插入关键字 37，50，42，18，48，12，56，
22、30，23，构造一棵二叉排序树，并计算平均查找长度 1。 （分数：2.00）解析：25/9 考点 二叉排序树的平均查找长度 解析 平均查找长度：(1+2*2+3*4+4*2)/9=25/9。三、应用题(总题数：5，分数：30.00)29.在栈的输入端，元素的输入顺序为 1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1 和 1，5，4，6，2，3?若能，写出进栈、退栈过程；若不能，简述理由(用 push(x)表示 x 进栈，pop(x)表示 x 退栈)。 （分数：6.00）解析：能排成序列 3，2，5，6，4，1。 过程：push(1)；push(2)；pu
23、sh(3)；pop(3)；pop(2)；push(4)；push(5)；pop(5)；push(6)；pop(6)；pop(4)；pop(1)。不能排成序列 1，5，4，6，2，3。 理由：在 2，3 依次进栈后，根据栈结构的特征不能产生排列 2，3。 考点 栈存取的原则，即后进先出已知一个无向图 G=(V，E)，其中 V=A，B，C，D，E，F，邻接矩阵表示如下图所示。 （分数：6.00）(1).请画出对应的图 G。（分数：3.00）解析：图 G 如下所示： (2).画出图 G 的邻接表存储结构。（分数：3.00）解析：图 G 的邻接表存储结构如下所示： 30.一棵二叉树的先序遍历序列为 A
24、BCDEFG，中序遍历序列为 CBDAEGF，试构造出该二叉树。 （分数：6.00）解析：结果见下图： 31.用冒泡排序法对数据序列(49，38，65，97，76，134，27，49)进行排序，写出排序过程，并说明冒泡排序是否为稳定排序。 （分数：6.00）解析：初始关键字 49 38 65 97 76 134 27 第一趟 38 48 65 76 97 27 32.下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。 （分数：6.00）解析：连通网的最小生成树如下图所示： 四、算法设计题(总题数：2，分数：14.00)33.若循环单链表长度大小 1，q 为指向链表中某结
25、点的指针，试编写一算法，删除 q 结点的前驱结点。 （分数：7.00）_正确答案：()解析：算法描述如下： Node * delete(q) Node * q; Node * P,*r; p=q; while(p-next!=q)p=p-next; r=p; while(r-next!=p)r=r-next; r-nest=q; free(p); return(q); 考点 循环链表的删除操作34.试写出二分查找的递归算法。 （分数：7.00）_正确答案：()解析：int binsearch_2(Sqtable R,KeyType k,int low,int high) int mid=(low+high)/2; if(R.elemmid.key=k) return mid; else if(R.elemmid.keyk) return binsearch_2(R,k,low,mid-1); else return binseareh_2(R,k,mid+1,high); 考点 二分查找算法递归实现
