数据结构期末样卷（含答案）

精品

5．设散列表的长度ｍ=13；散列函数为H(K)=K mod m，给定的关键码序列为20，21，14，68，19，23，30，1，84，15，27，79，试画出用线性探测再散列法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法搜索成功时的平均搜索长度。

0

平均搜索长度=40/12=3.3

6. 已知序列{583，87，512，61，908，170，897，275，623，462}，采用基数排序法对该序列作升序排序时的每一趟的结果（10分）。

1 14 2 1 3 68 4 30 5 15 6 19 7 20 8 21 9 84 10 23 11 27 12 79 精品

170 61 462 512 623 583 275 87 897 908

四．算法设计题( 20分)

1．设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

Int Intsert（SqList * va,datatype x）{ If(va->length==MAXSIZE) rerurn ERROR; int k = va->Length;

for(int i=0;iLength;i++){ if(va->data[i]>x) {k=i;break;} }

For(int j=va->length-1;j>k-1;j--){ va->data[j+1]=va->data[j]; }

Va->data[k]= x; Va->length++;

Return OK;

}

2． 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试

编写相应的队列初始化、入队列的算法。

typedef struct N0de {int data;

struct N0de *next; }N0de,*QueuePtr;

typedef struct {QueuePtr rear; }SqList

Void InitalSql(SqList *Q){ //初始化

Q->rear = (QueuePtr)new NOde();

Q->rear->next = Q->rear;

精品 }

Void EnSqlList(Sqlist *Q ，int e){ //插入 QueuePtr p;

p=(QueuePtr)malloc(sizeof(N0de)); p->data=e;

p->next=Q->rear->next; Q->rear->next=p;

return OK;