1、高等教育自学考试数据结构导论真题 2014 年 4 月及答案解析(总分：100.00，做题时间：150 分钟)一、课程代码：02142(总题数：1，分数：0.00)二、单项选择题(本大题共 15 小题，每小题 2 分(总题数：15，分数：30.00)1.下列几种算法时间复杂度中，最小的是 （分数：2.00）A.O(log2n)B.O(n)C.O(n2)D.O(1)2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有 （分数：2.00）A.索引存储方式和树形存储方式B.线性存储方式和散列存储方式C.线性存储方式和索引存储方式D.索引存储方式和散列存储方式3.表长为 n 的顺序表中做删除运
2、算的平均时间复杂度为 （分数：2.00）A.O(1)B.O(log2n)C.O(n)D.O(n2)4.顺序表中定位算法(查找值为 x 的结点序号最小值)的平均时间复杂度为 （分数：2.00）A.O(1)B.O(log2n)C.O(n)D.O(n2)5.元素的进栈次序为 A，B，C，D，E，出栈的第一个元素为 E，则第四个出栈的元素为 （分数：2.00）A.DB.CC.BD.A6.带头结点的链队列中，队列头和队列尾指针分别为 front 和 rear，则判断队列空的条件为 （分数：2.00）A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL7.深度
3、为 5 的二叉树，结点个数最多为 （分数：2.00）A.31 个B.32 个C.63 个D.64 个8.如果结点 A 有 2 个兄弟结点，结点 B 为 A 的双亲，则 B 的度为（分数：2.00）A.1B.3C.4D.59.将题 9 图所示的一棵树转换为二叉树，结点 C 是 （分数：2.00）A.A 的左孩子B.A 的右孩子C.B 的右孩子D.E 的右孩子10.n 为图的顶点个数，e 为图中弧的数目，则图的拓扑排序算法的时间复杂度为 （分数：2.00）A.O(n)B.O(e)C.O(n-e)D.O(n+e)11.无向图的邻接矩阵是 （分数：2.00）A.对角矩阵B.稀疏矩阵C.上三角矩阵D.对
4、称矩阵12.在具有 101 个元素的顺序表中查找值为 x 的元素结点时，平均比较元素的次数为 （分数：2.00）A.50B.51C.100D.10113.构造散列函数的方法很多，常用的构造方法有 （分数：2.00）A.数字分析法、除留余数法、平方取中法B.线性探测法、二次探测法、除留余数法C.线性探测法、除留余数法、链地址法D.线性探测法、二次探测法、链地址法14.就平均时间性能而言，快速排序方法最佳，其时间复杂度为 （分数：2.00）A.O(n)B.O(nlog2n)C.O(n2)D.O(1og2n)15.下述算法中，不稳定的排序算法是 （分数：2.00）A.直接插入排序B.冒泡排序C.堆排
5、序D.归并排序三、填空题(本大题共 13 小题，每小题 2 分，共(总题数：13，分数：26.00)16.数据的基本单位是 1。（分数：2.00）填空项 1:_17.双向循环链表中，在 p 所指结点的后面插入一个新结点*t，需要修改四个指针，分别为 t-prior=P；t-next=p-next；_；p-next=t；。（分数：2.00）填空项 1:_18.在带有头结点的循环链表中，尾指针为 rear，判断指针 P 所指结点为首结点的条件是 1。（分数：2.00）填空项 1:_19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是_。（分数：2.00）填
6、空项 1:_20.不含任何数据元素的栈称为 1。（分数：2.00）填空项 1:_21.稀疏矩阵一般采用的压缩存储方法是 1。（分数：2.00）填空项 1:_22.100 个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有 1 个。（分数：2.00）填空项 1:_23.已知完全二叉树的第 5 层有 5 个结点，则整个完全二叉树有 1 个结点。（分数：2.00）填空项 1:_24.n 个顶点的有向图 G 用邻接矩阵 A1n，1n存储，其第 i 列的所有元素之和等于顶点 Vi 的_。（分数：2.00）填空项 1:_25.具有 10 个顶点的有向完全图的弧数为 1。（分数：2.00）填
7、空项 1:_26.要完全避免散列所产生的“堆积现象，通常采用_解决冲突。（分数：2.00）填空项 1:_27.在长度为 n 的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为 1。（分数：2.00）填空项 1:_28.归并排序算法的时间复杂度是_。（分数：2.00）填空项 1:_四、应用题(本大题共 5 小题，每小题 6 分，共 3(总题数：5，分数：30.00)29.稀疏矩阵 A 如题 29 图所示，写出该稀疏矩阵 A 的三元组表示法。 （分数：6.00）_30.设二叉树的中序遍历序列为 BDCEAFHG，后序遍历序列为 DECBHGFA，试画出该二叉树。 （分数：6.00
8、）_31.写出题 31 图所示无向图的邻接矩阵，并写出每个顶点的度。 （分数：6.00）_32.已知散列表的地址空间为 0 至 13，散列函数 H(k)=kmod11，(mod 为求余运算)，待散列序列为(26，61，38，84，49)，用二次探测法解决冲突，构造该序列的散列表，要求写出处理冲突的过程。 （分数：6.00）_33.将一组键值(80，50，65，13，86，35，96，57，39，79，59，15)应用二路归并排序算法从小到大排序，试写出各趟的结果。（分数：6.00）_五、算法设计题(本大题共 2 小题，每小题 7 分，(总题数：2，分数：14.00)34.设单链表及链栈 S 的
9、结构定义如下： （分数：7.00）_35.以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。（分数：7.00）_高等教育自学考试数据结构导论真题 2014 年 4 月答案解析(总分：100.00，做题时间：150 分钟)一、课程代码：02142(总题数：1，分数：0.00)二、单项选择题(本大题共 15 小题，每小题 2 分(总题数：15，分数：30.00)1.下列几种算法时间复杂度中，最小的是 （分数：2.00）A.O(log2n) B.O(n)C.O(n2)D.O(1)解析：2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有 （分数：2.00）A.索引存储方式和树
10、形存储方式B.线性存储方式和散列存储方式C.线性存储方式和索引存储方式D.索引存储方式和散列存储方式 解析：3.表长为 n 的顺序表中做删除运算的平均时间复杂度为 （分数：2.00）A.O(1)B.O(log2n)C.O(n) D.O(n2)解析：4.顺序表中定位算法(查找值为 x 的结点序号最小值)的平均时间复杂度为 （分数：2.00）A.O(1)B.O(log2n)C.O(n) D.O(n2)解析：5.元素的进栈次序为 A，B，C，D，E，出栈的第一个元素为 E，则第四个出栈的元素为 （分数：2.00）A.DB.CC.B D.A解析：6.带头结点的链队列中，队列头和队列尾指针分别为 fro
11、nt 和 rear，则判断队列空的条件为 （分数：2.00）A.front=rear B.front!=NULLC.rear!=NULLD.front=NULL解析：7.深度为 5 的二叉树，结点个数最多为 （分数：2.00）A.31 个 B.32 个C.63 个D.64 个解析：8.如果结点 A 有 2 个兄弟结点，结点 B 为 A 的双亲，则 B 的度为（分数：2.00）A.1B.3 C.4D.5解析：9.将题 9 图所示的一棵树转换为二叉树，结点 C 是 （分数：2.00）A.A 的左孩子B.A 的右孩子C.B 的右孩子D.E 的右孩子 解析：10.n 为图的顶点个数，e 为图中弧的数目
12、，则图的拓扑排序算法的时间复杂度为 （分数：2.00）A.O(n)B.O(e)C.O(n-e)D.O(n+e) 解析：11.无向图的邻接矩阵是 （分数：2.00）A.对角矩阵B.稀疏矩阵C.上三角矩阵D.对称矩阵 解析：12.在具有 101 个元素的顺序表中查找值为 x 的元素结点时，平均比较元素的次数为 （分数：2.00）A.50 B.51C.100D.101解析：13.构造散列函数的方法很多，常用的构造方法有 （分数：2.00）A.数字分析法、除留余数法、平方取中法B.线性探测法、二次探测法、除留余数法C.线性探测法、除留余数法、链地址法D.线性探测法、二次探测法、链地址法 解析：14.就
13、平均时间性能而言，快速排序方法最佳，其时间复杂度为 （分数：2.00）A.O(n)B.O(nlog2n) C.O(n2)D.O(1og2n)解析：15.下述算法中，不稳定的排序算法是 （分数：2.00）A.直接插入排序B.冒泡排序C.堆排序 D.归并排序解析：三、填空题(本大题共 13 小题，每小题 2 分，共(总题数：13，分数：26.00)16.数据的基本单位是 1。（分数：2.00）填空项 1:_ （正确答案：数据项）解析：17.双向循环链表中，在 p 所指结点的后面插入一个新结点*t，需要修改四个指针，分别为 t-prior=P；t-next=p-next；_；p-next=t；。（分
14、数：2.00）填空项 1:_ （正确答案：p-next-prior=t）解析：18.在带有头结点的循环链表中，尾指针为 rear，判断指针 P 所指结点为首结点的条件是 1。（分数：2.00）填空项 1:_ （正确答案：P=rear-next-next）解析：19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是_。（分数：2.00）填空项 1:_ （正确答案：顺序表）解析：20.不含任何数据元素的栈称为 1。（分数：2.00）填空项 1:_ （正确答案：空栈）解析：21.稀疏矩阵一般采用的压缩存储方法是 1。（分数：2.00）填空项 1:_ （正确答案
15、：三元组）解析：22.100 个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有 1 个。（分数：2.00）填空项 1:_ （正确答案：N-1）解析：23.已知完全二叉树的第 5 层有 5 个结点，则整个完全二叉树有 1 个结点。（分数：2.00）填空项 1:_ （正确答案：20）解析：24.n 个顶点的有向图 G 用邻接矩阵 A1n，1n存储，其第 i 列的所有元素之和等于顶点 Vi 的_。（分数：2.00）填空项 1:_ （正确答案：入度）解析：25.具有 10 个顶点的有向完全图的弧数为 1。（分数：2.00）填空项 1:_ （正确答案：90）解析：26.要完全避免散列所
16、产生的“堆积现象，通常采用_解决冲突。（分数：2.00）填空项 1:_ （正确答案：公共溢出区）解析：27.在长度为 n 的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为 1。（分数：2.00）填空项 1:_ （正确答案：N+1）解析：28.归并排序算法的时间复杂度是_。（分数：2.00）填空项 1:_ （正确答案：O(NLOG2N)）解析：四、应用题(本大题共 5 小题，每小题 6 分，共 3(总题数：5，分数：30.00)29.稀疏矩阵 A 如题 29 图所示，写出该稀疏矩阵 A 的三元组表示法。 （分数：6.00）_正确答案：( )解析：30.设二叉树的中序遍历序列为
17、 BDCEAFHG，后序遍历序列为 DECBHGFA，试画出该二叉树。 （分数：6.00）_正确答案：( )解析：31.写出题 31 图所示无向图的邻接矩阵，并写出每个顶点的度。 （分数：6.00）_正确答案：( )解析：32.已知散列表的地址空间为 0 至 13，散列函数 H(k)=kmod11，(mod 为求余运算)，待散列序列为(26，61，38，84，49)，用二次探测法解决冲突，构造该序列的散列表，要求写出处理冲突的过程。 （分数：6.00）_正确答案：( )解析：33.将一组键值(80，50，65，13，86，35，96，57，39，79，59，15)应用二路归并排序算法从小到大排序，试写出各趟的结果。（分数：6.00）_正确答案：( )解析：五、算法设计题(本大题共 2 小题，每小题 7 分，(总题数：2，分数：14.00)34.设单链表及链栈 S 的结构定义如下： （分数：7.00）_正确答案：( )解析：35.以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。（分数：7.00）_正确答案：( )解析：
