1. 在双向循环链表中，在p指针所指的节点后插入一个指针q所指向的新节点，修改指针的操作是（）

A p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D q->next=p->next;q->prior=;p->next=q;p->next=q;
答案：C
解析：

1. 双向链表插入首先将新加入的结点的两个指针指向正确位置即q->prior=p;q->next=p->next;
2. 然后将原链表后面的那个结点前去指向新节点， p->next->prior=q;
3. 将原链表前面的结点指向新节点 p->next=q;
   注意： 最重要的顺序是：在q与原链表后面那个结点建立双向连接之前不可以改变p->next否则原链表断掉无法找到后面那个结点
   

2. 采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）

A 递归次数与初始数据的排列次序无关
B 每次划分后，先处理较长的分区可以减少递归次数
C 每次划分后，先处理较短的分区可以减少递归次数
D 递归次数与每次划分后得到的分区处理顺序无关
答案：D
解析：递归次数，取决于递归树，而递归树取决于轴枢的选择。树越平衡，递归次数越少。
而对分区的长短处理顺序，影响的是递归时对栈的使用内存，而不是递归次数

3. 一棵完全二叉树第六层有9个叶结点（根为第一层），则结点个数最多有（）

A 112
B 111
C 107
D 109
答案：D
解析：第六层有9个叶子结点，则可推测该二叉树最多有七层，结点总数为：
1+2+4+8+16+32+2*（32-9）=109

4. 已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（）

A 1.5
B 1.7
C 2.0
D 2.3
答案：C
解析：

平均查找长度=总的查找次数/元素数
总的查找次数： 38%7=3 （第1次出现3，无冲突，放在位置3，查找次数为1）
25%7=4（第1次出现4，无冲突，放在位置4，查找次数为1）
74%7=4（第2次出现4，有冲突，放在位置5，查找次数为2）
63%7=0（第1次出现0，无冲突，放在位置0，查找次数为1）
52%7=3（第2次出现3，有冲突，发现冲突3,4,5，故只能放到6，查找次数为4）
48%7=6 （第1次出现6，有冲突，发现冲突6,0，故只能放到1，查找次数为3）
1+1+2+1+4+3=12
元素数=6
所以：平均查找长度=12/6=2

5. 以30为基准，设一组初始记录关键字序列为 (30,15,40,28,50,10,70)，则第一趟快速排序结果为（）

A 10，28，15，30，50，40，70
B 10，15，28，30,50，40，70
C 10，28，15，30，40，50，70
D 10，15，28，30，40，50，70
答案：B
解析：
初始化左指针为1，右指针为6
从右指针开始比较，右指针自减，到10的时候发现比30小，两者交换得到：10,15,40,28,50,30,70
从左指针开始比较，左指针自增，到40的时候发现比30大，两者交换得到：10,15,30,28,50,40,70
从右指针开始比较，右指针自减，到28的时候发现比30小，两者交换得到：10,15,28,30,50,40,70
此时完成第一趟排序，已经满足30的左边都比30小，右边都比30大