18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为( C )A. n B .n2 C. (n+1)2 D. (n-1)2
19. 有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为( B )
A. 3512 B .3712 C. 3912 D. 4312
20.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，几次比较后查找成功（ C ）
二、填空题（每空1分，共20分）
1.在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置，决定的；在线性表的链接存储中，元素之间的逻辑关系是通过链域的指针值决定的。2．对于一个具有N个结点的单链表，在已知的结点P后插入一个新结点的时间复杂度为O(1),在给定值为X的结点后插入一个新结点的时间复杂度为 O(N)。 3.有一空桟，现有输入序列1,2,3,4,5,经push,push,pop,push,pop,push,push后，输出序列为 2,3 。
4．在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍 5.对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1。
6. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 6个
7.在霍夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对 4 个字符编码。
8. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 n 和 n-1 。
9. 对20个记录进行归并排序时，共需要进行 5 趟归并，在第三趟归并时是把长度为 4 的有序表两两归并为长度为 8 的有序表。
三、问答题 1. 简述下面算法的功能（栈和队列的元素类型均为int）
void algo3(Queue &Q){
Stack S; int d;
InitStack(S);
while(!QueueEmpty(Q)){