n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。

(1)【◆题库问题◆】：[填空题] n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。

【◆参考答案◆】：O(n+e)

(2)【◆题库问题◆】：[问答题,简答题] 编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。

【◆参考答案◆】：voidlinklist_c（Lnode*heaD.{Lnode*p；p=head；if（!p）returnERROR；while（p->next!=NULL）p=p->next；p->next=head；}设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。

(3)【◆题库问题◆】：[填空题] 已知栈的基本操作函数：intInitStack（SqStack*S）；//构造空栈intStackEmpty（SqStack*S）；//判断栈空intPush（SqStack*S，ElemTypee）；//入栈intPop（SqStack*S，ElemType*e）；//出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。voidconversion（）{InitStack（S）；scanf（“%d”，&N）；while（N）{（1）；N=N/8；}while（（2））{Pop（S，&e）；printf（“%d”，e）；}}//conversion

【◆参考答案◆】：（1）Push(S,N%8)（2）!StackEmpty(S)

(4)【◆题库问题◆】：[单选] 一个栈的入栈序列为a，b，c，则出栈序列不可能的是（）
A．c，b，a
B．b，a，c
C．c，a，b
D．a，c，

【◆参考答案◆】：C

(5)【◆题库问题◆】：[判断题] 具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的
A．正确
B．错误

【◆参考答案◆】：正确

(6)【◆题库问题◆】：[单选] 散列表的地址区间为0-17，散列函数为H（K）=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是（）。
A．2
B．3
C．4
D．5

【◆参考答案◆】：C

(7)【◆题库问题◆】：[名词解释] 静态查找表

【◆参考答案◆】：
如果一个查找表的操作仅涉及查询某个特定的数据元素是否在查找表中和检索满足条件的某个特定的数据元素的各种属性，则称为静态查找表。

(8)【◆题库问题◆】：[单选] 在下列链队列Q中，元素a出队的操作序列为（）。
A．p=Q.front->next；p->next=Q.front->next
B．p=Q.front->next；Q.front->next=p->next
C．p=Q.rear->next；p->next=Q.rear->next
D．p=Q->next；Q->next=p->next

【◆参考答案◆】：B

(9)【◆题库问题◆】：[判断题] 队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。
A．正确
B．错误

【◆参考答案◆】：正确

(10)【◆题库问题◆】：[名词解释] 折半查找

【◆参考答案◆】：
仅适用于有序的顺序表。将给定的值key与表中间位置元素的关键字比较，相等则查找成功返回位置。若不等则缩小查找范围，重复查找直到找到或者确定表中没有需查找的元素。