2016年10月高等教育自学考试全国统一命题考试
数据机构导论
试卷及解析
(课程代码 02142)
一、单项选择题(本大题共15小题，每小题2分，共30分。在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。)
第1题 已知问题规模为n，则下列程序片段的时间复杂度是（ ）
　　　　i=1；j=0；　　
　　　　while(i+j<=n){if(i＞j)j++；else i++；｝
A．O(nc)
B．O(log2n)
C．O(n)
D．O(2n)
 【正确答案】  C
 【答案解析】 (P28~30)
第2题 若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是（ ）
A．栈
B．队列
C．树
D．图
 【正确答案】  B
 【答案解析】 (P70)队列是有限个同类型数据元素的线性序列，是一种先进先出（First In First Out）的线性表，新加入的数据元素插在队列尾端，出队列的数据元素在队列首部被删除。银行客户排队等待办理业务是按"先进先出"的原则进行的，故可采用队列这一数据结构来实现。
第3题 若线性表采用链式存储结构，则适用的查找方法为（ ）
A．随机查找
B．散列查找
C．二分查找
D．顺序查找
 【正确答案】  D
 【答案解析】 (P163)
第4题 已知指针p和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述单链表应执行的语句为（ ）
A．q-＞next=s-＞next；s-＞next=p；
B．s-＞next=p；q-＞next=s-＞next；
C．p-＞next=s-＞next；s-＞next=q；
D．s-＞next=q；p-＞next=s-＞next；
 【正确答案】  A
 【答案解析】 (P46)
第5题 栈的运算特点是先进后出，元素a、b、c、d依次入栈，则不能得到的出栈序列是（ ）
A．abcd
B．dcba
C．cabd
D．bcda
 【正确答案】  C
 【答案解析】 (P59~65)选项C中，若要c先出栈，则a、b都要先入栈，所以c出栈后b在a的上面，不可能a先出栈。
第6题 在实现队列的链表结构中，其时间复杂度最优的是（ ）
A．仅设置头指针的单循环链表
B．仅设置尾指针的单循环链表
C．仅设置头指针的双向链表
D．仅设置尾指针的双向链表
 【正确答案】  B
 【答案解析】 (P75~78)
第7题 任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是（ ）
A．不一定相同
B．都相同
C．都不相同
D．互为逆序
 【正确答案】  B
 【答案解析】 (P102~103)