简要叙述栈和队列的特点

(1)【◆题库问题◆】：[问答题] 简要叙述栈和队列的特点

【◆参考答案◆】：
栈和队列都是插入和删除操作的位置受限制的线性表。栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表

(2)【◆题库问题◆】：[填空题] 写出下面算法的功能。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）；}

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

(3)【◆题库问题◆】：[问答题,简答题] 编写算法,将一个头指针为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）。

(4)【◆题库问题◆】：[判断题] 广义表的表示方法主要有：单链表示法和循环链表表示法。
A．正确
B．错误

【◆参考答案◆】：正确

(5)【◆题库问题◆】：[问答题] 试用权集合{12，4，5，6，1，2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

【◆参考答案◆】：WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

(6)【◆题库问题◆】：[单选] 将10个元素散列到100000个单元的哈希表中，则（）产生冲突。
A．一定会
B．一定不会
C．仍可能会
D．以上都不对

【◆参考答案◆】：C

(7)【◆题库问题◆】：[单选] 在有向图中每个顶点的度等于该顶点的（）。
A．入度
B．出度
C．入度与出度之和
D．入度与出度之差

【◆参考答案◆】：C

(8)【◆题库问题◆】：[判断题] 广义表实际上是基本线性表的推广。
A．正确
B．错误

【◆参考答案◆】：正确

(9)【◆题库问题◆】：[名词解释] 平均查找长度（ASL）

【◆参考答案◆】：
为确定数据元素在表中的位置，需和给定值进行比较的关键字个数的数学期望值，成为查找算法在查找成功的平均查找长度。

(10)【◆题库问题◆】：[填空题] 算法时间复杂度的分析通常有两种方法，即（）和（）的方法，通常我们对算法求时间复杂度时，采用后一种方法。

【◆参考答案◆】：事后统计；事前估计