3、先估计所需存储空间大小C．插入与删除时不必移动元素结点D．所需空间与线性表长度成正比3）有向图的边集为{,,,,,,}，下面正确的拓扑排序是（）A．aebdcfB．acefbdC．aecdcfD．acefbd4）二分查找法适用于存储结构为（）且按关键字排序的线性表A.顺序存储B.链接存储C.顺序存储或链接存储D.索引存储5）对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（）方法。A.归并排序B.直接插入排序C.
4、直接选择排序D.快速排序第6页共6页三、分析与算法设计题（4小题，共45分）1）采用长度为7的一维数组（下标是0..6）表示哈希表。采用双散列函数解决哈希冲突，h(key)=(h1(key)+i*h2(key))mod7，i=0,1,2，…。其中h1(key)=keymod7，h2(key)=(1+k)mod5。如果到达的键值分别是8,1,15,4，16，请（a）请构造哈希表（5分）（b）计算上述哈希表在等概率情况下成功检索时的平均检索长度（5分）2）下面的算法对一个由非零整数组成的序列进行重排列，将负数排在前面，正数排在后
5、面void swap(int array[], int i, int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}void Sort (int array[], int n) { int i, j; i = 0; j = n-1; while (i < j) { while(array[i]<0) ; （S1） while(array[j]>0) ;（S2） if () break; （S3） swap(array, i, j); i++;
6、j--; } }（a）请将空白处的代码补充完整（6分）（b）若有数组int a[]={10,-6,-3,20,-18,5,9,-16}，则执行Sort(a, 8)后，请给出数组a的值（4分）3）图G={V1,V2,V3,V4,V5,V6,V7,V8}，其邻接表存储如图1所示。请基于该邻接表存储结构：（a）给出从顶点V4出发的广度优先遍历序列（请注意该答案唯一，5分）（b）给出从顶点V2出发的深度优先遍历序列（请注意该答案唯一，5分）第6页共6页图1邻接表4）下面代码的主要功能是借助于栈的作用，将循环队列的内容倒置，循环队列和
7、栈均采用数组存储（假设队列和栈的存储空间均足够大），图2给出了将队列进行倒置的示意图。请根据上述要求将下面的代码补充完整。（15分）图2队列内容逆置示意图#defineMAXSIZE100//队列定义typedefstructQueue{DataTypedata[MAXSIZE];intfront,rear;//队头指针和队尾指针，队头指针始终指向队列第一个元素的前一个位置，队尾指针始终指向队列的最后一个元素}Queue;第6页共6页//栈定义typedefstructStack{DataTypedata[MAXSIZE];
8、inttop;//栈顶指针，其始终指向栈顶元素}Stack;Queue*Reverse(Queue*q){Stack*s=(Stack*)malloc(sizeof(Stack));s->top=-1;while((a)){(b);(c);s->data[s->top]=q->data[q
