1、数据结构导论自考题模拟 7 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.若评价算法的时间复杂度，比较对数阶量级与线性阶量级，通常_（分数：2.00）A.对数阶量级复杂性大于线性阶量级B.对数阶量级复杂性小于线性阶量级C.对数阶量级复杂性等于线性阶量级D.两者之间无法比较2.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则最节省运算时间的存储方式是_（分数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表3.非空带头结点的单循环链表的尾结点*P 满足_（分数：2.00）A.p-next=he
2、adB.p-next=NULLC.p=NULLD.p=head4.设有一个 5 阶上三角矩阵 A15，15，现将其上三角中的元素按列优先顺序存放在一维数组B115中。已知 B1的地址为 100，每个元素占用 2 个存储单元，则 A3的地址为_（分数：2.00）A.116B.118C.120D.1 225.设有一顺序栈 s，元素 s 1 ，s 2 ，s 3 ，s 4 ，s 5 ，s 6 依次进栈，如果 6 个元素出栈的顺序是 s 2 ，s 3 ，s 4 ，s 6 ，s 5 ，s 1 ，则栈的容量至少应该是_（分数：2.00）A.2B.3C.5D.66.设树 T 的度为 4，其中度为 1、2、3
3、和 4 的结点个数分别为 4、2、1、1 则 T 中的叶子数为_（分数：2.00）A.5B.6C.7D.87.下列有关二叉树的说法中正确的是_（分数：2.00）A.二叉树的度为 2B.一棵二叉树的度可以小于 2C.二叉树中至少有一个结点的度为 2D.二叉树中任何一个结点的度都为 28.对一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点，它的父结点的编号为_（分数：2.00）A.24B.25C.98D.999.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的_（分数：2.00）A.先序遍历B.中序遍历C.后序遍历D.层次遍历10.对于一个具有 n 个顶点的无向图。若采用邻
4、接表表示，则存放表头结点的数组的大小为_（分数：2.00）AnB.n+1C.n-1D.n+边数11.采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为_（分数：2.00）A.从第 0 个元素开始往后查找该数据元素B.从第 1 个元素开始往后查找该数据元素C.从第 n 个元素开始往前查找该数据元素D.从第 n+1 个元素开始往前查找该数据元素12.下列查找中，效率最高的查找方法是_（分数：2.00）A.顺序查找B.二分查找C.索引顺序查找D.分块查找13.下面给出的四种排序法中，属于稳定排序法的是_（分数：2.00）A.直接选择排序法B.冒泡排序法C.快速排序法D.堆排序法14.在下述的排
5、序方法中，不属于内部排序方法的是_（分数：2.00）A.插入排序法B.选择排序法C.拓扑排序法D.归并排序法15.以下时间复杂性不是 O(n 2 )的排序方法是_（分数：2.00）A.直接插入排序B.二路归并排序C.冒泡排序D.直接选择排序二、填空题(总题数：13，分数：26.00)16.对所有相同输入数据量的不同输入数据，算法时间用量的平均值是指 1。 （分数：2.00）17.通常从正确性、易读性、 1、时空性等四个方面评价算法的质量。 （分数：2.00）18.已知 p 为单链表中的非首尾结点，在 p 结点后插入 s 结点的语句为： 1。 （分数：2.00）19.判定一个栈 ST(最多元素个
6、数为 m)为空的条件是 1。 （分数：2.00）20.队列的队尾位置通常是随着 1 操作而变化的。 （分数：2.00）21.有一个 10090 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是 1。 （分数：2.00）22.具有 256 个结点的完全二叉树的深度为 1。 （分数：2.00）23.已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为 1。 （分数：2.00）24.将一棵树转换成一棵二叉树，二叉树的根结点没有 1 子树。 （分数：2.00）25.采用邻接表存储的图的广度优先遍历算法类似于
7、树的 1 遍历。 （分数：2.00）26.若在查找的同时对表作修改，则相应的表称为 1。 （分数：2.00）27.对于有 n 个顶点的无向图，所有生成树中都有且仅有 1 条边。 （分数：2.00）28. 1 是指将两个或两个以上的有序表合并成一个新的有序表。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.给定二叉树的中序遍历结果为 abc，请画出能得到此中序遍历结果的二叉树的所有形态。 （分数：6.00）_假设二叉树包含的结点数为 1，3，7，2，12。（分数：6.00）(1).画出两棵高度最大的二叉树。（分数：3.00）_(2).画出两棵完全二叉树，要求每个双亲结点的值大
8、于其孩子结点的值。（分数：3.00）_30.已知关键字序列 R=11，4，3，2，17，30，19，请构造一棵哈夫曼树，并计算出它的带权路径长度WPL。 （分数：6.00）_31.分别写出下图中从 v 5 出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。 （分数：6.00）_32.给定表(39，14，22，8，65，28，88，29，67，13，10)，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。 （分数：6.00）_四、算法设计题(总题数：2，分数：14.00)33.写出计算方阵 Ann与 Bnn乘积 Cnn的算法，分析算法的时间复杂度。
9、 （分数：7.00）_34.修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a，int n)。 （分数：7.00）_数据结构导论自考题模拟 7 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.若评价算法的时间复杂度，比较对数阶量级与线性阶量级，通常_（分数：2.00）A.对数阶量级复杂性大于线性阶量级B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级D.两者之间无法比较解析：2.若某表最常用的操作是在
10、最后一个结点之后插入一个结点或删除最后一个结点，则最节省运算时间的存储方式是_（分数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 解析：考点 本题主要考查的知识点是双循环链表。 双循环链表结构是一种对称结构，既有前向链，又有后向链，这就使得插入和删除的操作都很方便。有头结点的链表：一般链表中每个结点存储一个或者一组数据，但是有头结点的链表的第一个结点是头结点，头结点不存储数据，它的主要作用是方便插入操作。3.非空带头结点的单循环链表的尾结点*P 满足_（分数：2.00）A.p-next=head B.p-next=NULLC.p=NULLD.p=head解析：考点 本
11、题主要考查的知识点为单循环链表。 尾结点的指针域指向头结点。如果是空表则有 head-next=head。4.设有一个 5 阶上三角矩阵 A15，15，现将其上三角中的元素按列优先顺序存放在一维数组B115中。已知 B1的地址为 100，每个元素占用 2 个存储单元，则 A3的地址为_（分数：2.00）A.116 B.118C.120D.1 22解析：5.设有一顺序栈 s，元素 s 1 ，s 2 ，s 3 ，s 4 ，s 5 ，s 6 依次进栈，如果 6 个元素出栈的顺序是 s 2 ，s 3 ，s 4 ，s 6 ，s 5 ，s 1 ，则栈的容量至少应该是_（分数：2.00）A.2B.3 C.5
12、D.6解析：考点 本题主要考查的知识点是顺序栈。 栈的出入原则是后进先出。从出栈顺序可知，在 s 6 出栈前，栈中的元素应为 s 6 、s 5 、s 1 ，此时需3 个位置才能满足需要。所以栈的容量至少应该是 3。6.设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别为 4、2、1、1 则 T 中的叶子数为_（分数：2.00）A.5B.6C.7D.8 解析：考点 本题主要考查的知识点是树中的叶子数。 由树的性质可知，任意一棵树的结点总数等于所有结点的出度之和加 1。可求得此树的出度之和为：1*4+2*2+3*1+4*1=15。设叶子结点的个数为 x，可得 x+4+2+1+1=1
13、5+1，求得 x=8。7.下列有关二叉树的说法中正确的是_（分数：2.00）A.二叉树的度为 2B.一棵二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 2D.二叉树中任何一个结点的度都为 2解析：考点 本题主要考查的知识点是二叉树。 结点没有分叉的二叉树的度是 0。如果二叉树中的结点最多只有一个分叉，则二叉树的度为 1。如果二叉树中某个结点有两个分叉，则二叉树的度为 2。8.对一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点，它的父结点的编号为_（分数：2.00）A.24 B.25C.98D.99解析：9.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的_（分
14、数：2.00）A.先序遍历 B.中序遍历C.后序遍历D.层次遍历解析：10.对于一个具有 n 个顶点的无向图。若采用邻接表表示，则存放表头结点的数组的大小为_（分数：2.00）An B.n+1C.n-1D.n+边数解析：考点 本题主要考查的知识点是无向图的邻接表表示。 如果一个无向图有 n 个顶点，e 条边，那么它的邻接表需要 n 个头结点和 2e 个表结点，故存放表头结点的数组的大小为 n。11.采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为_（分数：2.00）A.从第 0 个元素开始往后查找该数据元素B.从第 1 个元素开始往后查找该数据元素C.从第 n 个元素开始往前查找该数据
15、元素 D.从第 n+1 个元素开始往前查找该数据元素解析：12.下列查找中，效率最高的查找方法是_（分数：2.00）A.顺序查找B.二分查找 C.索引顺序查找D.分块查找解析：13.下面给出的四种排序法中，属于稳定排序法的是_（分数：2.00）A.直接选择排序法B.冒泡排序法 C.快速排序法D.堆排序法解析：考点 本题主要考查的知识点是冒泡排序法。 排序方法的稳定性指的是：若待排序的序列中，存在多个具有相同关键字的记录，经过排序。这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。根据排序的稳定性，排序可以分为稳定排序和不稳定排序。稳定排
16、序法有：冒泡排序、直接插入排序。不稳定排序法有：选择排序、快速排序、堆排序。14.在下述的排序方法中，不属于内部排序方法的是_（分数：2.00）A.插入排序法B.选择排序法C.拓扑排序法 D.归并排序法解析：考点 本题主要考查的知识点是内部排序方法。 题目选项中的四种排序方法中，只有拓扑排序是对图中结点进行排序的方法，不属于内部排序方法，而其他的三种排序方法都属于内部排序方法。15.以下时间复杂性不是 O(n 2 )的排序方法是_（分数：2.00）A.直接插入排序B.二路归并排序 C.冒泡排序D.直接选择排序解析：二、填空题(总题数：13，分数：26.00)16.对所有相同输入数据量的不同输入
17、数据，算法时间用量的平均值是指 1。 （分数：2.00）解析：平均时间复杂度17.通常从正确性、易读性、 1、时空性等四个方面评价算法的质量。 （分数：2.00）解析：健壮性18.已知 p 为单链表中的非首尾结点，在 p 结点后插入 s 结点的语句为： 1。 （分数：2.00）解析：s-next=p-next；p-next=s；19.判定一个栈 ST(最多元素个数为 m)为空的条件是 1。 （分数：2.00）解析：ST-top=020.队列的队尾位置通常是随着 1 操作而变化的。 （分数：2.00）解析：入队21.有一个 10090 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字
18、节，则用三元组表示该矩阵时，所需的字节数是 1。 （分数：2.00）解析：6622.具有 256 个结点的完全二叉树的深度为 1。 （分数：2.00）解析：923.已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为 1。 （分数：2.00）解析：CBEFDA24.将一棵树转换成一棵二叉树，二叉树的根结点没有 1 子树。 （分数：2.00）解析：右25.采用邻接表存储的图的广度优先遍历算法类似于树的 1 遍历。 （分数：2.00）解析：层次26.若在查找的同时对表作修改，则相应的表称为 1。 （分数：2.00）解析：动态查找表27.对于有 n 个顶点的
19、无向图，所有生成树中都有且仅有 1 条边。 （分数：2.00）解析：n-128. 1 是指将两个或两个以上的有序表合并成一个新的有序表。 （分数：2.00）解析：二路归并三、应用题(总题数：5，分数：30.00)29.给定二叉树的中序遍历结果为 abc，请画出能得到此中序遍历结果的二叉树的所有形态。 （分数：6.00）_正确答案：()解析：共有五种不同形态的二叉树如下图所示： 假设二叉树包含的结点数为 1，3，7，2，12。（分数：6.00）(1).画出两棵高度最大的二叉树。（分数：3.00）_正确答案：()解析：两棵高度最大的二叉树如下图所示 (2).画出两棵完全二叉树，要求每个双亲结点的值
20、大于其孩子结点的值。（分数：3.00）_正确答案：()解析：所求完全二叉树如下图所示： 30.已知关键字序列 R=11，4，3，2，17，30，19，请构造一棵哈夫曼树，并计算出它的带权路径长度WPL。 （分数：6.00）_正确答案：()解析：所求哈夫曼树如下图所示： 31.分别写出下图中从 v 5 出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。 （分数：6.00）_正确答案：()解析：深度优先搜索序列为：v 5 v 4 v 3 v 2 v 1 广度优先搜索序列为：v 5 v 3 v 4 v 1 v 2 图的深度优先搜索和广度优先搜索的顶点序列不是唯一的。32.给定表(39，14，2
21、2，8，65，28，88，29，67，13，10)，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。 （分数：6.00）_正确答案：()解析：所求二叉排序树如下图所示： 四、算法设计题(总题数：2，分数：14.00)33.写出计算方阵 Ann与 Bnn乘积 Cnn的算法，分析算法的时间复杂度。 （分数：7.00）_正确答案：()解析：算法描述如下： void matrixmultiply(int An，int Bn，int Cn，int n) /求 n 阶方阵 A 与 B 的乘积 C int i，j； for(i=0；in；i+) for(j=0；jn
22、；j+) cij=0； for(k=0；kn；k+) Cij+=Aik*Bkj； 以方阵阶数 n 作为输入规模。易知第二层循环中的第一条赋值语句共执行 n 2 次，第三层循环体中的乘法和赋值语句共执行 n 3 次，故此算法的计算量为 n 3 +n 2 ，算法时间复杂度 T(n)=O(n 3 )。34.修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a，int n)。 （分数：7.00）_正确答案：()解析：void dbubble(int a，int n) int m=n-1，q=2，j，t，b=1； while(b&(m+1=q) b=0： for(j=q-1；j=m；j+) if(ajaj+1) b=1； t=aj；aj=aj+1；aj+1=t； for(j=m；j=q；j-) if(ajaj-1) b=1；t=aj；aj=aj-1；aj-1=t； m-； q+；
