2016年10月高等教育自学考试全国统一命题考试
数据结构导论试卷
课程代码02142
本试卷共4页，满分l00分，考试时间l50分钟。考生答题注意事项：1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间。超出答题区域无效。
第一部分选择题共30分
一、单项选择题本大题共10小题，每小题2分，共30分在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。1．已知问题规模为
，则下列程序片段的时间复杂度是C
2．若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是
A．栈
B．队列
C．树
D．图
3．若线性表采用链式存储结构，则适用的查找方法为
A．随机查找
B．散列查找
C．二分查找
D．顺序查找
4．已知指针P和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，
则在S所指结点之后插入上述单链表应执行的语句为
A．q→
ext；s→
ext；s→
ext2P；
B．s→
extP；q→
exts→
ext；
C．p→
exts→
ext；s→
extq；
D．s→
ext2q；p→
ext2s→
ext；
5．栈的运算特点是先进后出，元素a、b、c、d依次入栈，则不能得到的出栈序列是
A．abed
B．dcba
C．cabd
D．bcda
6．在实现队列的链表结构中，其时间复杂度最优的是
A．仅设置头指针的单循环链表
B．仅设置尾指针的单循环链表
C．仅设置头指针的双向链表
D．仅设置尾指针的双向链表
7．任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是
A．不一定相同
B都相同
C．都不相同
D．互为逆序
8．若某棵树的存储结构采用双亲表示法，如题8图所示，则该树的高度是
fA．2
B．3
C．4
D．5
9．无向图的邻接矩阵一定是
A．对称矩阵
B．对角矩阵
C．稀疏矩阵
D．三角矩阵
10．根据连通图的深度优先搜索的基本思想，如题10图所示的连通图的一个深度优先搜索的结果序列是
A．123456
B．123465
C126345
D．162543
11．用顺序查找方法对含有
个数据元素的顺序表按从后向前查找次序进行查找，现假设查找
其中每个数据元素的概率不相等，那么
A．该顺序表按查找概率由低到高的顺序来存储数据元素，其ASL最小
B．该顺序表按查找概率由高到低的顺序来存储数据元素，r