抽象数据类型与计算机内部表示和实现无关

(1)【◆题库问题◆】：[判断题] 抽象数据类型与计算机内部表示和实现无关
A．正确
B．错误

【◆参考答案◆】：正确

(2)【◆题库问题◆】：[单选] 广义表（（a），a）的表尾是（）。
A．a
B．A.
C．（）
D．（A.）

【◆参考答案◆】：B

(3)【◆题库问题◆】：[单选] 已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（）次。
A．1
B．2
C．3
D．4

【◆参考答案◆】：A

(4)【◆题库问题◆】：[填空题] 每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做（）排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（）排序。

【◆参考答案◆】：插入；选择

(5)【◆题库问题◆】：[判断题] 在线索二叉树中每个结点通过线索都可以直接找到它的前驱和后继。
A．正确
B．错误

【◆参考答案◆】：正确

(6)【◆题库问题◆】：[判断题] 在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p－＞next；
A．正确
B．错误

【◆参考答案◆】：正确

(7)【◆题库问题◆】：[判断题] 在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1
A．正确
B．错误

【◆参考答案◆】：正确

(8)【◆题库问题◆】：[单选] 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（）次元素，包括开始把支点元素移动到临时变量的一次在内。
A．n/2
B．n-1
C．n
D．n+1

【◆参考答案◆】：D

(9)【◆题库问题◆】：[填空题] 写出下面算法的功能。Bitree*function（Bitree*bt）{Bitree*t，*t1，*t2；if（bt==NULL）t=NULL；else{t=（Bitree*）malloc（sizeof（Bitree））；t->data=bt->data；t1=function（bt->left）；t2=function（bt->right）；t->left=t2；t->right=t1；}return（t）；}

【◆参考答案◆】：交换二叉树结点左右子树的递归算法

(10)【◆题库问题◆】：[问答题,简答题] 设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。

【◆参考答案◆】：voidassending（Lnode*heaD.{Lnode*p，*q，*r，*s；p=head->next；q=p->next；p->next=NULL；while（q）{r=q；q=q->next；if（r->data<=p->datA.{r->next=p；head->next=r；p=r；}else{while（!p&&r->data>p->datA.{s=p；p=p->next；}r->next=p；s->next=r；}p=head->next；}}