抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机

(1)【◆题库问题◆】：[判断题] 抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现
A．正确
B．错误

【◆参考答案◆】：正确

(2)【◆题库问题◆】：[判断题] 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O（n）。
A．正确
B．错误

【◆参考答案◆】：正确

(3)【◆题库问题◆】：[问答题] 阅读下列算法，并回答问题：设顺序表L=（3，7，11，14，20，51），写出执行f30（&L，15）之后的L。

【◆参考答案◆】：
L->next

(4)【◆题库问题◆】：[填空题] 函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i){int k;if(iL->length) return ERROR;for(k=i-1;klength-1;k++) L->slist[k]=（1）; （2） ; return OK;}

【◆参考答案◆】：（1）L->slist[k+1] （2） --L->Length

(5)【◆题库问题◆】：[单选] 折半查找法适用于（）。
A．有序顺序表
B．有序单链表
C．有序顺序表和有序单链表都可以
D．无限制

【◆参考答案◆】：A

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

【◆参考答案◆】：正确

(7)【◆题库问题◆】：[问答题] 写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。

【◆参考答案◆】：输入：长度为n的线性表数组A（1：n）输出：逆转后的长度为n的线性表数组A（1：n）。C语言描述如下（其中ET为数据元素的类型）：invsl(n,a)int n;ET a[];{int k;ET t;for (k=1; k<=n/2; k++){t=a[k-1]; a[k-1]=a[n-k]; a[n-k]=t;}return; }

(8)【◆题库问题◆】：[单选] 对于一个有向图，若一个顶点的入度为k1，、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）。
A．k1
B．k2
C．k1+k2
D．k1-k2

【◆参考答案◆】：B

(9)【◆题库问题◆】：[单选] 设S为C语言的语句，计算机执行下面算法时，算法的时间复杂度为（）。for（i=n-1；i>=0；i--）for（j=0；j
A．n2
B．O（nlgn）
C．O（n）
D．O（n2）

【◆参考答案◆】：D

(10)【◆题库问题◆】：[判断题] 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。
A．正确
B．错误

【◆参考答案◆】：正确