1、数据结构导论自考题模拟 10及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下面几种算法时间复杂度阶数中，_最小。 A.O(10g2n) B.O(n) C.O(n2) D.O(2n)（分数：2.00）A.B.C.D.2.在一个具有 n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂度为_ A.O(1) B.O(n) C.O(nlog2n) D.O(n2)（分数：2.00）A.B.C.D.3.顺序存储的线性表(a 1 ，a 2 ，a n )，在任一结点前插入一个新结点时所需移动结点的平均次数为_（分数：2.00）
2、AnB.n/2C.n+1D.(n+1)/24.三元组表是稀疏矩阵的一种_（分数：2.00）A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构5.对于 n阶对称矩阵，如果以行序或列序放入内存中，则需要_个存储单元。 A.n(n+1)/2 B.n(n-1)/2 C.n2 D.n2/2（分数：2.00）A.B.C.D.6.二叉树和度为 2的树的相同之处包括_（分数：2.00）A.每个结点都有两个孩子结点B.至少有一个根结点C.至少有一个度为 2的结点D.每个结点至多只有一个双亲结点7.已知一棵含 50个结点的二叉树中只有一个叶子结点，则该树中度为 1的结点个数为_（分数：2.00）A.
3、0B.1C.48D.498.由带权为 9，2，5，7 的 4个叶子结点构成的一棵哈夫曼树的带权路径长度是_（分数：2.00）A.23B.37C.46D.449.下列说法错误的是_（分数：2.00）A.一个图的邻接矩阵表示是唯一的B.一个图的邻接表表示是不唯一的C.一个图的生成树必为该图的极小连通子图D.一个无环有向图的拓扑排序序列必唯一10.已知某图的邻接矩阵为 （分数：2.00）A.0B.1C.2D.311.在有向图 G的拓扑序列中，若顶点 V i 在顶点 V j 之前，则下列情形不可能出现的是_（分数：2.00）A.G中有弧Vi，VjB.G中有一条从 Vi到 Vj的路径C.G中没有弧Vi，
4、vjD.G中有一条从 Vj到 Vi的路径12.设散列函数为 H(k)k mod7,一组关键码为 23、14、9、6、30、12、18，散列表 T的地址空间为06，用线性探测法解决冲突，依次将这组关键码插入 T中，得到的散列表为_ A B C D （分数：2.00）A.B.C.D.13.二叉排序树中任意结点的_（分数：2.00）A.左子树中的结点的键值小于行子树中的结点的键值B.左子树中的结点的键值小于等于右子树中的结点的键值C.右子树中的结点的键值小于左子树中的结点的键值D.右子树中的结点的键值小于等于左子树中的结点的键值14._方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。（
5、分数：2.00）A.快速B.直接选择C.二路归并D.直接插入15.一组记录的键值为(46，74，18，53，14，20，40，38，86，65)，利用堆排序的方法建立的初始堆为_（分数：2.00）A.(14，18，38，46，65，40，20，53，86，74)B.(14，38，18，46，65，20，40，53，86，74)C.(14，18，20，38，40，46，53，65，74，86)D.(14，86，20，38，40，46，53，65，74，18)二、填空题(总题数：13，分数：26.00)16.从数据结构的观点，数据组织通常可分为三个层次：数据、数据元素和 1 。 （分数：2.00）
6、17.线性结构中，有且仅有一个开始结点和一个 1。 （分数：2.00）18.线性表是具有 n个 1 的有限序列。 （分数：2.00）19.链栈的每个结点空间都是 1 产生的，不用预先考虑容量的大小。 （分数：2.00）20.判断链队列 LQ为空的条件是 1。 （分数：2.00）21.一个 1010阶对称矩阵 A，采用行优先顺序压缩存储下三角矩阵，a 0 0 为第一个元素，其存储地址为 0，每个元素占用 1个存储单元，则 a 3 3 的地址为 1。 （分数：2.00）22.一棵二叉树中，双分支的结点数 15，单分支结点数为 30，则叶子结点数为 1。 （分数：2.00）23.已知完全二叉树的第
7、8层有 8个结点，则其叶结点数为 1。 （分数：2.00）24.前序序列为 xyz且后序序列为 zyx的二叉树共有 1 棵。 （分数：2.00）25.设图 G有 n个顶点，采用邻接矩阵作为存储结构，进行深度优先搜索的时间复杂度为 1。 （分数：2.00）26.图的主要存储结构有两种，分别为：邻接矩阵和 1。 （分数：2.00）27.构造散列函数的方法很多，其中 1 是一种简单有效且最常用的构造方法。 （分数：2.00）28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为 1。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.画出下列二叉树的二叉链表表示图。 （分数：6.
8、00）_30.将题下图所示的森林转换为一棵二叉树。 （分数：6.00）_对于下图，试给出： （分数：6.00）(1).邻接矩阵；（分数：3.00）_(2).邻接表。（分数：3.00）_31.求下图中从顶点 V 0 到其余各顶点的最短路径及长度(给出求解的过程)。 （分数：6.00）_32.用插入排序算法对数据序列(47，33，61，82，72，11，25，57)进行排序，写出整个插入排序的每一趟的过程。 （分数：6.00）_四、算法设计题(总题数：2，分数：14.00)33.对于循环队列，试写出求队列含有多少个元素的算法。 （分数：7.00）_34.假设线性表中结点是按键值递增的顺序排列，试写
9、一顺序查找算法，将岗哨设在高下标端。然后分别求出等概率情况下查找成功和不成功时的平均查找长度。 （分数：7.00）_数据结构导论自考题模拟 10答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下面几种算法时间复杂度阶数中，_最小。 A.O(10g2n) B.O(n) C.O(n2) D.O(2n)（分数：2.00）A. B.C.D.解析：2.在一个具有 n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂度为_ A.O(1) B.O(n) C.O(nlog2n) D.O(n2)（分数：2.00）A.B. C.D.解
10、析：3.顺序存储的线性表(a 1 ，a 2 ，a n )，在任一结点前插入一个新结点时所需移动结点的平均次数为_（分数：2.00）AnB.n/2 C.n+1D.(n+1)/2解析：4.三元组表是稀疏矩阵的一种_（分数：2.00）A.顺序存储结构 B.链式存储结构C.索引存储结构D.散列存储结构解析：5.对于 n阶对称矩阵，如果以行序或列序放入内存中，则需要_个存储单元。 A.n(n+1)/2 B.n(n-1)/2 C.n2 D.n2/2（分数：2.00）A. B.C.D.解析：考点 本题主主要考察的知识点的对称矩阵的压缩存储。 只需存放上(或下)三角区和主对角线上的元素，共计 n(n+1)/2
11、个元素。故大题答案为 A。6.二叉树和度为 2的树的相同之处包括_（分数：2.00）A.每个结点都有两个孩子结点B.至少有一个根结点C.至少有一个度为 2的结点D.每个结点至多只有一个双亲结点 解析：考点 木题主要考查的知识点是二叉树干和度为 2的树的异同。 二叉树不同于度为 2的树，但它们都属于树形结构，满足树中每个结点至多有一个双亲结点的树特征。故本题答案为 D。7.已知一棵含 50个结点的二叉树中只有一个叶子结点，则该树中度为 1的结点个数为_（分数：2.00）A.0B.1C.48D.49 解析：考点 本题主要考查的知识点是二叉树的性质。 根据二叉树性质：在任意一棵二叉树中，若终端结点的
12、个数为 n 0 ，度为 2的结点数为 n 2 ，则 n 0 =n 2 +1。可得 n 2 =n 0 -1=0，n 1 =50-n 0 -n 2 =49。8.由带权为 9，2，5，7 的 4个叶子结点构成的一棵哈夫曼树的带权路径长度是_（分数：2.00）A.23B.37C.46D.44 解析：考点 本题主要考查的知识点是哈夫曼树。 构成的哈夫曼树如下图所示，其带权路径长度=(2+5)3+72+91=44 故本题答案为 D。 9.下列说法错误的是_（分数：2.00）A.一个图的邻接矩阵表示是唯一的B.一个图的邻接表表示是不唯一的C.一个图的生成树必为该图的极小连通子图D.一个无环有向图的拓扑排序序
13、列必唯一 解析：10.已知某图的邻接矩阵为 （分数：2.00）A.0B.1 C.2D.3解析：考点 本题主要考查的知识点是有向图中顶点的入度。 对于有向图，顶点 v i 的出度 OD(v i )是邻接矩阵中第 i行元素之和，顶点 v i 的入度 ID(v i )是邻接矩阵中第 i列元素之和。11.在有向图 G的拓扑序列中，若顶点 V i 在顶点 V j 之前，则下列情形不可能出现的是_（分数：2.00）A.G中有弧Vi，VjB.G中有一条从 Vi到 Vj的路径C.G中没有弧Vi，vjD.G中有一条从 Vj到 Vi的路径 解析：考点 本题主要考查的知识点是有向图的拓扑排序序列。 在有向图 G中，
14、若有一条从 v j 到 v i 的路径，则在它的拓扑排序序列中，顶点 v j 必须出现在顶点 v i 之前。12.设散列函数为 H(k)k mod7,一组关键码为 23、14、9、6、30、12、18，散列表 T的地址空间为06，用线性探测法解决冲突，依次将这组关键码插入 T中，得到的散列表为_ A B C D （分数：2.00）A.B. C.D.解析：13.二叉排序树中任意结点的_（分数：2.00）A.左子树中的结点的键值小于行子树中的结点的键值 B.左子树中的结点的键值小于等于右子树中的结点的键值C.右子树中的结点的键值小于左子树中的结点的键值D.右子树中的结点的键值小于等于左子树中的结点
15、的键值解析：考点 本题主要考查的知识点是二叉排序树的性质。 一棵二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树； (1)若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值； (2)若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值； (3)根的左、右子树也分别为二叉排序树。由以上性质可知，二叉排序树左子树中的结点的键值小于右子树中的结点的键值。14._方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。（分数：2.00）A.快速B.直接选择 C.二路归并D.直接插入解析：15.一组记录的键值为(46，74，18，53，14，20，40，38，86，6
16、5)，利用堆排序的方法建立的初始堆为_（分数：2.00）A.(14，18，38，46，65，40，20，53，86，74)B.(14，38，18，46，65，20，40，53，86，74) C.(14，18，20，38，40，46，53，65，74，86)D.(14，86，20，38，40，46，53，65，74，18)解析：二、填空题(总题数：13，分数：26.00)16.从数据结构的观点，数据组织通常可分为三个层次：数据、数据元素和 1 。 （分数：2.00）解析：数据项17.线性结构中，有且仅有一个开始结点和一个 1。 （分数：2.00）解析：终端结点18.线性表是具有 n个 1 的有限
17、序列。 （分数：2.00）解析：数据元素19.链栈的每个结点空间都是 1 产生的，不用预先考虑容量的大小。 （分数：2.00）解析：动态分配20.判断链队列 LQ为空的条件是 1。 （分数：2.00）解析：LQ.front=LQ.rear21.一个 1010阶对称矩阵 A，采用行优先顺序压缩存储下三角矩阵，a 0 0 为第一个元素，其存储地址为 0，每个元素占用 1个存储单元，则 a 3 3 的地址为 1。 （分数：2.00）解析：922.一棵二叉树中，双分支的结点数 15，单分支结点数为 30，则叶子结点数为 1。 （分数：2.00）解析：1623.已知完全二叉树的第 8层有 8个结点，则其
18、叶结点数为 1。 （分数：2.00）解析：6824.前序序列为 xyz且后序序列为 zyx的二叉树共有 1 棵。 （分数：2.00）解析：425.设图 G有 n个顶点，采用邻接矩阵作为存储结构，进行深度优先搜索的时间复杂度为 1。 （分数：2.00）解析：O(n 2 )26.图的主要存储结构有两种，分别为：邻接矩阵和 1。 （分数：2.00）解析：邻接表27.构造散列函数的方法很多，其中 1 是一种简单有效且最常用的构造方法。 （分数：2.00）解析：除留余数法28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为 1。 （分数：2.00）解析：O(n 2 )三、应用题(总题数：5，分数：
19、30.00)29.画出下列二叉树的二叉链表表示图。 （分数：6.00）_正确答案：()解析：所求二叉链表如下图所示： 30.将题下图所示的森林转换为一棵二叉树。 （分数：6.00）_正确答案：()解析：森林对应的二叉树如下图所示： 对于下图，试给出： （分数：6.00）(1).邻接矩阵；（分数：3.00）_正确答案：()解析：(2).邻接表。（分数：3.00）_正确答案：()解析：邻接表： 31.求下图中从顶点 V 0 到其余各顶点的最短路径及长度(给出求解的过程)。 （分数：6.00）_正确答案：()解析：求解过程如下： 32.用插入排序算法对数据序列(47，33，61，82，72，11，2
20、5，57)进行排序，写出整个插入排序的每一趟的过程。 （分数：6.00）_正确答案：()解析：关键字47 33 61 82 72 11 25 57 i=2 33 47 61 82 72 11 25 57 i=3 33 47 61 82 72 11 25 57 i=4 33 47 61 82 72 11 25 57 i=5 33 47 61 72 82 11 25 57 i=6 11 33 47 61 72 82 25 57 i=7 11 25 33 47 61 72 82 57 i=8 11 25 33 47 57 61 72 82四、算法设计题(总题数：2，分数：14.00)33.对于循环队
21、列，试写出求队列含有多少个元素的算法。 （分数：7.00）_正确答案：()解析：假定循环队列的类型定义如下： const int maxsize=； typedef struct cycqueue DataTypemaxsize； int front，rear； CycqueueTp； 解法一：计数器初始化为 0，从队首开始沿着队列顺序搜索，每走过一个元素，计数器加 1，直到队尾，计数器的最终值即队列长度。算法描述如下： int que_length(CycqueueTp*cq) int n，k； n=0；/计数器 k=cq-front; while(k!=cq-rear) n+； k=(k+
22、1)%maxsize； return n； 解法二：利用队首和队尾的关系求出队列的长度。 int que_length(CycqueueTp*cq) return(maxsize+cq-rear-cq- front)%maxsize； 34.假设线性表中结点是按键值递增的顺序排列，试写一顺序查找算法，将岗哨设在高下标端。然后分别求出等概率情况下查找成功和不成功时的平均查找长度。 （分数：7.00）_正确答案：()解析：算法描述如下： int search_sqtable(Sqtable R，KeyType k) /顺序查找算法，将岗哨设在高下标端 int i=0： R.elemR.n.key=k； while(R.elemi.keyk)i+； if(R.elemi.keyk|i=R.n)return-1； else return i： 该方法在等概率情况下查找成功和查找不成功时 ASL都为 O(n)。
