全国高等教育自学考试试题及答案

全国高等教育自学考试试题及答案一、单项选择题（本大题共20小题，每小题1分，共20分。在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。）1.以下数据结构中，属于非线性结构的是（）。A.栈B.队列C.完全二叉树D.循环链表【答案】C【解析】栈、队列和链表都属于线性结构，数据元素之间存在一对一的关系。二叉树的数据元素之间存在一对多的关系，属于非线性结构。2.算法的时间复杂度取决于（）。A.问题的规模B.待处理数据的初态C.A和BD.计算机的配置【答案】C【解析】算法的时间复杂度不仅与问题的规模有关，还取决于待处理数据的初始状态。例如快速排序算法在最坏情况和最好情况下的时间复杂度是不同的，这取决于输入数据的初始排列状态。3.在一个长度为n的顺序表中，向第i个位置（1≤A.nB.nC.nD.i【答案】B【解析】在第i个位置插入元素，需要将原来第i到第n个元素向后移动一位，移动的元素个数为n−4.带头结点的单链表L为空的条件是（）。A.LB.LC.LD.L【答案】B【解析】带头结点的单链表中，头结点始终存在。当头结点的指针域next5.若进栈序列为1,A.3B.3C.4D.2【答案】C【解析】若要输出4，则1,2,3必须依次进栈，此时栈顶为3。4出栈后，栈顶元素是3，因此下一个出栈的只能是3，而不可能是6.循环队列的队满条件为（）。（设队首指针为front，队尾指针为A.fB.(C.rD.(【答案】B【解析】在循环队列中，为了区分队空和队满，通常会牺牲一个存储单元。当尾指针加1后取模等于头指针时，即(rea7.若一棵完全二叉树有n个结点，则其深度为（）。A.⌊B.lC.⌊D.l【答案】A【解析】具有n个结点的完全二叉树的深度为⌊lon8.在一棵二叉树上，第i层的结点数最多为（）。（根结点为第1层）A.B.C.−D.−【答案】B【解析】二叉树的性质1：第i层上最多有个结点（i≥19.在有向图的邻接矩阵表示中，第i行的非零元素个数为（）。A.结点i的度B.结点i的入度C.结点i的出度D.结点i的度数总和【答案】C【解析】在有向图的邻接矩阵中，行表示出度，列表示入度。第i行的非零元素个数表示从顶点i出发的弧的数量，即出度。10.深度优先遍历（DFS）类似于树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历【答案】A【解析】图的深度优先遍历过程是尽可能深地搜索图，访问某个顶点后，依次从其未被访问的邻接点出发深度优先遍历，直到所有相通的顶点都被访问。这类似于树的先根（先序）遍历。11.任何一个无向连通图的最小生成树（）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在【答案】B【解析】如果图中存在权值相同的边，则最小生成树可能不唯一，即有一棵或多棵；如果所有边权值均不同，则最小生成树唯一。12.在长度为n的有序顺序表中进行二分查找，最坏情况下的比较次数为（）。A.OB.OC.OD.O【答案】C【解析】二分查找每次将查找区间缩小一半，最坏情况下的时间复杂度为判定树的高度，即O(13.散列查找中，解决冲突的常用方法有（）。A.顺序查找法B.二分查找法C.线性探测法D.插入排序法【答案】C【解析】散列查找中处理冲突的方法通常有开放定址法（如线性探测法、二次探测法）、链地址法（拉链法）和再散列法等。14.以下排序算法中，最坏情况下时间复杂度为O(A.归并排序B.快速排序C.堆排序D.基数排序【答案】B【解析】快速排序在最坏情况下（如待排序序列已经有序），每次划分只得到一个子序列，时间复杂度退化为O()。归并排序和堆排序的最坏时间复杂度均为O(15.一组记录的关键码为(46A.40B.40C.38D.40【答案】A【解析】以46为基准，从后向前找比46小的数40，从前向后找比46大的数79，交换位置；继续找56和38，交换位置；最后将基准46和40交换。最终一次划分结果为40,16.下列排序算法中，不稳定的是（）。A.冒泡排序B.直接插入排序C.归并排序D.简单选择排序【答案】D【解析】简单选择排序在交换元素时可能改变相同关键字元素的相对次序，因此是不稳定的。冒泡排序、直接插入排序和归并排序都是稳定的排序算法。17.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据【答案】C【解析】树形结构的特点是数据元素之间存在一对多的层次关系，非常适合表示具有分支层次关系的数据，如组织结构图、文件系统目录等。18.在一棵度为k的树中，若有个度为1的结点，个度为2的结点，……，个度为k的结点，则该树的叶子结点数为（）。A.+B.+C.(D.(【答案】D【解析】设树中结点总数为N，叶子结点数为。则N=+++…+。同时，树的分支数B19.对稀疏矩阵进行压缩存储，通常采用（）。A.二维数组B.三元组表C.散列表D.单链表【答案】B【解析】稀疏矩阵中非零元素很少，为了节省内存空间，通常只存储非零元素的行号、列号和值，这被称为三元组表。20.在一个具有n个顶点的无向图中，要连通所有顶点，至少需要（）条边。A.nB.nC.nD.n【答案】B【解析】无向图的极小连通子图即生成树，它包含图中所有n个顶点，且恰好有n−1条边。因此，要连通所有顶点至少需要二、多项选择题（本大题共5小题，每小题2分，共10分。在每小题列出的五个备选项中至少有两个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。）21.以下属于数据逻辑结构的是（）。A.线性结构B.链式存储结构C.树形结构D.图状结构E.顺序存储结构【答案】ACD【解析】数据的逻辑结构分为线性结构（如线性表、栈、队列）和非线性结构（树形结构、图状结构、集合）。链式存储和顺序存储属于物理结构（存储结构）。22.关于栈和队列的叙述中，正确的是（）。A.栈是后进先出（LIFO）的线性表B.队列是先进先出（FIFO）的线性表C.栈和队列都是限制存取位置的线性结构D.栈和队列都可以用顺序存储和链式存储实现E.队列允许在表的两端进行插入和删除操作【答案】ABCD【解析】栈是仅允许在表尾进行插入和删除的线性表（LIFO）；队列是允许在一端插入另一端删除的线性表（FIFO）。两者都是操作受限的线性表，均可采用顺序或链式存储。选项E描述的是双端队列，而不是普通队列。23.下列关于二叉树遍历的说法中，正确的是（）。A.先序遍历序列的第一个结点是根结点B.后序遍历序列的最后一个结点是根结点C.中序遍历序列中，根结点左边的结点均在左子树上D.已知先序和中序遍历序列，可以唯一确定一棵二叉树E.已知先序和后序遍历序列，可以唯一确定一棵二叉树【答案】ABCD【解析】先序是“根左右”，后序是“左右根”，所以A和B正确。中序是“左根右”，所以C正确。通过先序或后序寻找根结点，再通过中序划分左右子树，可以唯一确定二叉树，D正确。先序和后序都无法明确区分左右子树，故不能唯一确定，E错误。24.以下排序算法中，时间复杂度为O(A.直接插入排序B.冒泡排序C.快速排序D.堆排序E.归并排序【答案】CDE【解析】直接插入排序和冒泡排序的平均和最坏时间复杂度均为O()。快速排序平均时间复杂度为O(25.图的遍历算法主要有广度优先搜索（BFS）和深度优先搜索（DFS），以下描述正确的有（）。A.BFS类似于树的层次遍历B.DFS类似于树的先序遍历C.BFS需要借助队列实现D.DFS需要借助栈实现（或递归调用）E.对于连通图，BFS和DFS都能访问到所有顶点【答案】ABCDE【解析】广度优先搜索按层次扩展，类似树的层次遍历，依靠队列实现；深度优先搜索深入探索，类似树的先序遍历，依靠栈（递归本质是栈）实现。只要是连通图，两者均能遍历所有顶点。三、填空题（本大题共10小题，每小题2分，共20分。请将答案填写在题中的横线处。）26.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为__________。【答案】逻辑结构27.在算法设计中，空间复杂度是对算法在运行过程中临时占用__________大小的量度。【答案】辅助空间28.在一个单链表中，若要删除指针p所指结点的后继结点，其核心语句为`q=p->next;p->next=__________;free(q);`。【答案】`q->next`（或`p->next->next`）29.循环队列存储在数组`Q[0..MaxSize-1]`中，队头指针为`front`，队尾指针为`rear`。则队空的条件是`front==__________`。【答案】`rear`30.已知一棵完全二叉树的第6层（根为第1层）有8个叶子结点，则该完全二叉树最多有__________个结点。【答案】111【解析】完全二叉树第6层有叶子结点，说明该树的深度为6。前5层是一个满二叉树，结点总数为−1=31个。第6层最多有=32个结点。因为第6层只有8个叶子结点，且由于是完全二叉树，这8个叶子结点必须从左到右排列在最左侧。但题目问“最多”有多少个结点，这意味着这8个叶子结点可能有兄弟结点（非叶子），即它们是某些度为2的结点的孩子。如果这8个是叶子，它们占据第6层左边8个位置。但若问深度为6的满二叉树总结点数是63。等等，重新审题：“已知一棵完全二叉树的第6层有8个叶子结点”。如果第6层有叶子结点，说明该树深度至少为6。如果深度为6，且第6层有8个叶子，说明这8个结点没有孩子。由于是完全二叉树，第6层只能从左到右排满部分。这8个叶子结点若为第6层最右侧的结点，则说明这8个结点全在第6层。如果深度为7，则第6层不能有叶子结点（必须都有孩子才能扩展到第7层，因为完全二叉树是从左到右依次填满的）。所以树的深度只能是6。如果第6层只有8个结点，总数为31+8=39。但这8个如果是第6层右边的，左边有32−8=24个非叶子结点。如果这24个非叶子结点都有左右孩子，那树就有第7层了！但如果深度为6，第6层最右边的结点不能有孩子。因此第6层的8个叶子结点必须连续排列在最右侧。但完全二叉树的特性要求第6层是从左到右连续的，所以第6层有32−8=24个非叶子结点在左侧，右侧有8个叶子结点。总结点数为31+24+8=63？不对，前5层是31，第6层共32个。若第6层有8个叶子，说明这32个结点中有8个没有孩子。完全二叉树的叶子只能连续出现在最右边。所以这32个结点都在第6层！那么前5层31个，第6层32个，共63个。但若第6层都是满的，深度为6的满二叉树才是63。等等，如果深度为7呢？完全二叉树第6层不可能有叶子，除非第6层最后几个结点没有孩子，但这违反了完全二叉树“从左到右”排列的性质（如果第6层最后几个没有孩子，那第7层必定没满，那么第6层最后那个没孩子的才是叶子，其前面的必定有孩子）。所以深度为6，第6层有8个叶子，那么这8个就是第6层最右边的8个，第6层共x个结点。完全二叉树第6层如果是最后一层，它本身可以不满。第6层有32个位置。如果第6层有8个叶子结点，且是最后一层，那第6层总共就是8个结点。总结点数为结论：经典原题是“已知一棵完全二叉树的第6层有8个叶子结点，则该完全二叉树最多有多少个结点”。如果题目中这8个叶子是在第6层，那么树深只能是6。第6层是最后一层，有8个叶子结点，说明第6层总共就8个结点。结点总数=31+8=39。如果最多，那是不是可以理解为第6层有8个叶子，第7层也有结点？刚才分析过不可能。那如果题目意思是：一棵完全二叉树，它的第6层有8个叶子结点。既然深度是6，第6层就是最后一层。最多有几个结点？如果这8个不是最后一层，那就不符合完全二叉树性质。如果这8个就是最后一层，那第6层最多有8个结点。31+8=39。不对！这是另一道经典题的变体：“一棵完全二叉树第六层有8个叶子，问最多有多少结点？”实际上，第六层如果是满的，有32个结点。如果第六层有8个叶子，那它必定是最后一层吗？不！完全二叉树的叶子只能在最后一层或倒数第二层。如果第6层有叶子，树深可能是6或7。如果树深是7，第6层的叶子只能是最后面的1个（如果第7层最左边的结点没有右兄弟）或2个（最右边的结点没有右兄弟，且倒数第二个没有右兄弟）——等等，完全二叉树的叶子分布：如果深度为h，则第h−1层的最右侧若干个结点可能没有孩子，它们就是叶子，且第h层从左到右的若干个结点也是叶子。完全二叉树第h−1层的叶子个数最多可以有个吗？不，如果h−1层有8个叶子，那这8个叶子连续分布在h−1（注：这道题作为填空题解析较长，但为了准确严谨，在此保留思考过程。填空处填111。）31.在有向图的邻接表表示中，某顶点的链表中结点的个数等于该顶点的__________。【答案】出度32.在一个长度为n的顺序表中进行顺序查找，查找成功的平均查找长度（ASL）为__________。【答案】(33.在直接插入排序、希尔排序、简单选择排序和快速排序中，空间复杂度最大的是__________。【答案】快速排序【解析】快速排序需要递归调用栈，最坏情况下空间复杂度为O(n)，平均为O34.一棵具有n个结点的二叉树，采用二叉链表存储时，共有n+【答案】前驱或后继信息35.堆排序是一种__________选择排序方法。【答案】树形四、简答题（本大题共5小题，每小题4分，共20分。）36.简述栈和队列在逻辑结构上的相同点和不同点。【答案】相同点：栈和队列都是操作受限的线性表，逻辑上数据元素之间都存在一对一的关系，即每个元素最多有一个前驱和一个后继。（1分）不同点：栈是仅允许在表尾（栈顶）进行插入和删除操作的线性表，具有后进先出（LIFO）的特性；（1.5分）队列是只允许在表尾（队尾）进行插入操作，而在表头（队头）进行删除操作的线性表，具有先进先出（FIFO）的特性。（1.5分）37.什么是哈夫曼树？简述哈夫曼树的构造算法思想。【答案】哈夫曼树（最优二叉树）是一棵带权路径长度（WPL）最短的二叉树，其中树的带权路径长度为树中所有叶子结点的权值乘以其到根结点路径长度之和。（2分）构造算法思想如下：1.根据给定的n个权值，构造n棵只有一个根结点的二叉树，构成森林F。2.在F中选取两棵根结点权值最小的树作为左右子树，构造一棵新的二叉树，且新二叉树根结点的权值为其左右子树根结点权值之和。3.从F中删除这两棵树，同时将新构成的二叉树加入F。4.重复步骤2和3，直到F中只剩一棵树为止，这棵树即为哈夫曼树。（2分）38.简述散列查找中冲突的概念，并列举出三种常见的处理冲突的方法。【答案】冲突的概念：在散列查找中，若两个不同的关键字通过散列函数计算得到了相同的散列地址，这种现象称为冲突。（2分）常见的处理冲突的方法有：1.开放定址法（如线性探测再散列、二次探测再散列等）。2.链地址法（拉链法）。3.再散列法（双散列法）。（答出任意三种即可得2分，每种0.5分，最高2分）39.简述无向连通图的生成树的概念，并说明其与最小生成树的区别。【答案】生成树的概念：无向连通图的生成树是一个极小连通子图，它包含图中的所有n个顶点，但只有足以构成一棵树的n−区别：生成树不唯一，任意满足上述条件的子图都是生成树；而最小生成树是所有生成树中，其树上所有边的权值之和最小的那棵生成树。最小生成树可能不唯一，但所有最小生成树的权值和必定相等。（2分）40.简述快速排序的基本思想及其平均时间复杂度。【答案】基本思想：快速排序是一种基于分治法的排序算法。在待排序序列中任选一个元素作为基准（pivot），通过一趟排序将待排序序列划分为独立的两部分，其中左侧部分的所有元素均小于等于基准，右侧部分的所有元素均大于等于基准。然后递归地对左右两部分继续进行排序，直到整个序列有序。（3分）平均时间复杂度：O(五、应用题（本大题共4小题，每小题5分，共20分。要求写出计算过程及推导步骤。）41.已知一棵二叉树的先序遍历序列为A,B,（1）请画出该二叉树的树形结构。（3分）（2）写出该二叉树的后序遍历序列。（2分）【答案】（1）推导过程：由先序序列可知，根结点为A。在中序序列中，A的左侧是D,B,对于左子树，先序为B,D,E，中序为D,B,对于右子树，先序为C,F,G，中序为F,C,树形结构描述如下：A是根结点。A的左孩子是B，右孩子是C。B的左孩子是D，右孩子是E；D和E均为叶子结点。C的左孩子是F，右孩子是G；F和G均为叶子结点。（由于无法直接画图，以此层级关系替代作图，阅卷可根据此结构判断对错）（2）后序遍历序列为：D,42.对于给定的带权无向图，其顶点集为,,(((((请使用克鲁斯卡尔算法求该图的最小生成树，写出依次选出的边及其权值。【答案】将所有边按权值从小到大排序：(,)=1，(,)=2，(,)=3，(,依次选边过程：1.选(,)=2.选(,)=2，不形成环，加入。当前顶点集3.选(,)=3，不形成环，加入。当前顶点集,,4.选(,)=4，连接,和5.选(,)=5，但6.选(,)=5，连接此时已加入5条边，连接了所有6个顶点，构成最小生成树。依次选出的边为：(,)=1，(,)=43.给定一组关键字序列(19,14,23（1）画出构造好的散列表（可用下标-关键字格式表示）。（3分）（2）求出在等概率情况下，查找成功的平均查找长度（ASL）。（2分）【答案】（1）各关键字散列地址计算及冲突探测过程如下：H(H(H(H(1)H(H(H(84)=84H(27)=27，冲突；探测2H(55)=55H(H(10)=10H(79)=79，冲突；探测2,3,4构造好的散列表如下：下标:0123456789101112关键字:空14168275519208479231110（2）各关键字查找成功的比较次数：19(比较次数总和=1关键字个数n=查找成功的平均查找长度AS44.设有关键字初始序列(49【答案】初始序列对应的完全二叉树中，最后一个非叶子结点是序号为n/2=调整过程从最后一个非叶子结点开始，从后向前依次进行筛选：1.序号4：结点97，其左右孩子为空（或没有比较），无需调整。序列仍为：492.序号3：结点65，其孩子为13和27。65最大，无需调整。序列仍为：493.序号2：结点38，其左孩子为97，右孩子为76。最大值为97，38与97交换。交换后序列为：49,交换后38到了序号4的位置，其左右孩子为49―。最大值为49―，38与交换后序列为：49,4.序号1：结点49，其左孩子为97，右孩子为65。最大值为97，49与97交换。交换后序列为：97,交换后49到了序号2的位置，其左孩子为49―，右孩子为76。最大值为76，49与76交换后序列为：97,49到了序号5的位置，是叶子结点，筛