《高等教育自学考试数据结构导论真题2014年4月》由会员分享，可在线阅读，更多相关《高等教育自学考试数据结构导论真题2014年4月（6页珍藏版）》请在金锄头文库上搜索。
1、高等教育自学考试数据结构导论真题 2014年 4月( 总分： 100.00 ，做题时间： 150 分钟 )一、课程代码： 02142( 总题数： 1，分数： 0.00)30.00)二、单项选择题 (本大题共 15小题，每小题 2 分，共 30分) ( 总题数： 15，分数：1. 下列几种算法时间复杂度中，最小的是(分数： 2.00 )A. O(log2n)VB. O(n)C. O(n2)D. O(1)解析：2. 数据的存储方式中除了顺序存储方式和链式存储方式之外，还有 (分数： 2.00 )A. 索引存储方式和树形存储方式B. 线性存储方式和散列存储方式C. 线性存储方式和索引存储方式D. 索
2、引存储方式和散列存储方式 V解析：3. 表长为 n 的顺序表中做删除运算的平均时间复杂度为 (分数： 2.00 )A. O(1)B. O(log2n)C. O(n)VD. O(n2)解析：4. 顺序表中定位算法 ( 查找值为 x 的结点序号最小值 ) 的平均时间复杂度为 (分数： 2.00 )A. O(1)B. O(log2n)C. O(n)VD. O(n2)解析：5. 元素的进栈次序为 A, B, C, D, E,出栈的第一个元素为E,则第四个出栈的元素为(分数： 2.00 )A. DB. CC. B VD. A解析：6. 带头结点的链队列中,队列头和队列尾指针分别为 front 和 rea
3、r ,则判断队列空的条件为 (分数： 2.00 )A. front=rearVB. front!=NULLC. rear!=NULLD. front=NULL解析：7. 深度为5的二叉树，结点个数最多为（分数:2.00 ）A. 31 个 VB. 32 个C. 63 个D. 64 个解析：8. 如果结点A有2个兄弟结点，结点 B为A的双亲，贝U B的度为（分数:2.00 ）A. 1B. 3 VC. 4D. 5解析:9. 将题9图所示的一棵树转换为二叉树，结点C是|（分数：2.00 ）A. A的左孩子B. A的右孩子C. B的右孩子D. E的右孩子V解析：10. n为图的顶点个数，e为图中弧的数目
4、，则图的拓扑排序算法的时间复杂度为 （分数：2.00 ）A. O（n）B. O（e）C. O（n-e）D. O（n+e）V解析：11. 无向图的邻接矩阵是（分数：2.00 ）A. 对角矩阵B. 稀疏矩阵C. 上三角矩阵D. 对称矩阵 V解析：12. 在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为（分数：2.00 ）A. 50 VB. 51C. 100D. 101解析:13. 构造散列函数的方法很多，常用的构造方法有（分数：2.00 ）A. 数字分析法、除留余数法、平方取中法B. 线性探测法、二次探测法、除留余数法C. 线性探测法、除留余数法、链地址法D. 线性探测法、
5、二次探测法、链地址法V解析：14. 就平均时间性能而言，快速排序方法最佳，其时间复杂度为 （分数： 2.00 ）A. O（n）B. O（nlog2n）VC. O（n2）D. O（1og2n）解析：15. 下述算法中，不稳定的排序算法是 （分数： 2.00 ）A. 直接插入排序B. 冒泡排序C. 堆排序 VD. 归并排序解析：三、填空题 （本大题共 13小题，每小题 2分，共 26分）（总题数： 13，分数： 26.00）16. 数据的基本单位是 1 。 （分数： 2.00 ）填空项 1: （正确答案：数据项）解析：17. 双向循环链表中，在 p 所指结点的后面插入一个新结点 *t ，需要修改四
6、个指针，分别为 t-prior=Pt-next=p-next ；p-next=t ；。（分数： 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: （正确答
7、案：空栈）解析：21. 稀疏矩阵一般采用的压缩存储方法是 1 。 （分数： 2.00 ）填空项 1: （正确答案：三元组）解析：22.100 个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有1 个（分数： 2.00 ）填空项 1: （正确答案： N-1 ）解析：23. 已知完全二叉树的第 5层有 5 个结点，则整个完全二叉树有 1 个结点。 （分数： 2.00 ）填空项 1: （正确答案： 20）解析：24. n个顶点的有向图G用邻接矩阵A1.n ,1.n存储，其第i列的所有元素之和等于顶点 Vi的（分数:2.00）填空项1： （正确答案：入度）解析：25. 具有10个顶点的
8、有向完全图的弧数为1。（分数：2.00）填空项1: （正确答案：90）解析：26. 要完全避免散列所产生的“堆积现象，通常采用 解决冲突。（分数：2.00）填空项1: （正确答案：公共溢岀区）解析：27. 在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为1。（分数：2.00 ）填空项1: （正确答案：N+1）解析：28. 归并排序算法的时间复杂度是 _。（分数：2.00 ）填空项1: （正确答案：0（NL0G2N）解析：四、应用题（本大题共5小题，每小题6分，共30分）（总题数：5,分数：30.00）29. 稀疏矩阵A如题29图所示，写出该稀疏矩阵 A的二兀组表示
9、法（分数：6.00 ）30. 设二叉树的中序遍历序列为 BDCEAFH，后序遍历序列为 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分，共14分）（总题数：2,分数：14.00）34. 设单链表及链栈S的结构定义如下:)（分数：7.00 ）正确答案：（解析：35. 以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。 （分数：7.00 ）
