7. 在有向图中，以顶点v为终点的边的数目称为v的___。
答案：入度
8. 当关键字的取值范围是实数集合时，无法进行箱排序和___排序。
答案：基数
9. 产生冲突现象的两个关键字称为该散列函数的___。
答案：同义词
10. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时
，该桶中___。
答案：已有m个同义词的记录（或：已有m个记录；或：已满）
三、解答题（本大题共4小题，每小题5分，共20分）
1. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循
环队列中队尾元素的位置和元素的个数。 (1)写出队满的条件表达式； (2)写出队空的条件表达式；
(3)设m=40,rear=13,quelen=19,求队头元素的位置； (4)写出一般情况下队头元素位置的表达式。 答案：（1）quelen=m(1分) （2）quelen=0(1分) （3）35(1分)
（4）(rear-quelen+1+m)%m(2分)
2. 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。
答案：(每错一个结点扣1分，扣完5分为止)
3. 画出下图所示有向图的所有强连通分量。
答案：该图的强连通分量分别为：
4. 对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。
(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快速排序，写出排序过程。 答案：（1）4713652(3分)
（2）初始关键字4713652
一次划分后得（231）4（657）(1分)
继续划分后得（1）2（3）（5）6（7）(1分)
（说明：答案不唯一，只要满足题目要求均得分。）
四、算法阅读题（本大题共4小题，每小题5分，共20分）
1. 阅读下列算法，并回答问题：
(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L； (2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L； (3)简述算法的功能。
void f30(SeqList*L, DataType x)
{
int i =0, j;
while (i
} else {
for(j=L->length;j>i;j--)
L->data［j］=L->data［j-1］; L->data［i］=x; L->length++;
} }
答案：（1）（3，7，11，14，15，20，51）(2分) （2）（4，7，14，20，51）(1分)
（3）当非递减顺序表中存在元素x时，从表中删除该元素；否则将x保序插入到顺序表中。(2分)
2. 已知图的邻接表表示的形式说明如下：
#define MaxNum50//图的最大顶点数
typedef struct node {
intadjvex;//邻接点域
struct node *next; //链指针域 } EdgeNode;//边表结点结构描述
typedef struct {
char vertex;//顶点域
EdgeNode *firstedge;//边表头指针 } VertexNode;//顶点表结点结构描述
typedef struct {
VertexNode adjlist［MaxNum］;//邻接表 int n, e;//图中当前的顶点数和边数 } ALGraph;//邻接表结构描述
下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使 其成为一个完整的算法。
typedef enum {FALSE, TRUE} Boolean;
Boolean visited［MaxNum］;
void DFSForest(ALGraph *G){
int i;
for(i=0;i
for(i=0;i
}
void DFSTree(ALGraph *G, int i) {
EdgeNode *p;
visited［i］=TRUE;
p=G->adjlist［i］. firstedge;
while(p!=NULL){
if(!visited［p->adjvex］){
printf(″<%c,%c>″,G->adjlist［i］. vertex, G->adjlist［p->adjvex］. vertex); ___;
}
___;
} }
答案：FALSE(1分)
DFSTree(G,P->adjvex)(2分) p=p->next(2分)
3. 阅读下列算法，并回答问题：
(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L； (2)写出上述函数调用过程中进行元素交换操作的总次数。 void f32(int R［］,int n){ int i,t;
for (i=0;i R［R［i］］=R［i］; R［i］=t; } } 答案：(1)L［8］={0,1,2,3,4,5,6,7,}(3分) (2)共进行5次元素交换。(2分) 4. 答案：（1）NULL(1分) （2）p->next=H［j］(2分) （3）p=q(2分) 五、算法设计题（本大题10分） 1. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType;
