[简答题]

已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为：。请在空缺处填入适当内容，使其成为一个完整算法。
void f33(LinkList L,LinkList H[],int m)
{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在
int i,j;
LinkList p,q;
for(i=0;i＜m;i++)
H[i]=[ (1) ];
p=L—＞next;
while(p)
{
q=p—＞next
j=p—＞key%m;
[ (2) ];
H[j]=p;
[ (3) ];
}
free(L);
}

[简答题]

[填空题]已知bead指向一个带头结点的单向链表，链表中每个结点包含数据域(data)和指针域(next)，数据域为整型。以下函数求出链表中所有连接点数据域的和值作为函数值返回。请在横线处填入正确内容。
int data； struct link *next；
main（　）
struct link *head；
sam(______)；
stmct link *p；int s=0；
p=head-＞next；
while(p)s+=p-＞data；p=p-＞next；
return(s)；

[简答题]设某带头结点的单链表的结点结构说明如下：
typedef struct nodel

int data;
struct nodel*next;
node;
试设计一个算法：void copy(node*head1, node*head2)，将以head1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。

[填空题]已知链表结点定义如下： typedef struct node{ char data［16］； struct node *next; } LinkStrNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。

[简答题]设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。

[填空题]以下程序段的功能是统计链表中结点的个数，其中first为指向第一个结点的指针(链表带头结点)。请在下划线内填入正确内容。 struct link { char data； struct link*next；}； … struct link*p，*first； int c=0； p=first； while( 【19】 ) { c++； p= 【20】 ；}

[填空题]对于一个具有n个结点的单链表，在已知p结点后插入一个新结点的事件的时间复杂性为______，在给定值为x的结点后插入一个新结点的时间复杂性为______。

[填空题]函数main（　）的功能是：在带头结点的单链表中查找数据域中值最小的结点。请填空
#include
struct node
int data;
struct node *next;int main(struct node *first) /*指针first为链表头指针*/
struct node *p; int m;
p=first-＞next; m=p-＞data; p=p-＞next;
for(; p!=NULL;p=______)
if(p-＞data＜M)＆NBSP;＆NBSP;＆NBSP;M=P-＞data;
return m;

[简答题]

给定程序MODI1.C中的函数Creatlink的功能是创建带头结点的单向链表, 并为各结点数据域赋0到m-1的值。
请改正函数Creatlink中指定部位的错误, 使它能得出正确的结果。
注意: 不要改动main函数, 不得增行或删行, 也不得更改程序的结构!
给定源程序：
#include
#include
typedef struct aa
{ int data;
struct aa *next;
} NODE;
NODE *Creatlink(int n, int m)
{ NODE *h=NULL, *p, *s;
int i;
p=(NODE )malloc(sizeof(NODE));
h=p;
p->next=NULL;
for(i=1; i<=n; i++)
{ s=(NODE *)malloc(sizeof(NODE));
s->data=rand（　）%m; s->next=p->next;
p->next=s; p=p->next;
}
return p;
}
outlink(NODE *h)
{ NODE *p;
p=h->next;
printf("/n/nTHE LIST :/n/n HEAD ");
while(p)
{ printf("->%d ",p->data);
p=p->next;
}
printf("/n");
}
main（　）
{ NODE *head;
head=Creatlink(8,22);
outlink(head);
}

[单项选择]设rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( )
A. s=rear;
B. rear=rear—＞next;
C. rear=rear—＞next—＞next;
D. s=rear—＞next—＞next;

[填空题]给定程序MODI1.C中函数Creatlink的功能是创建带头结点的单向链表，并为各结点数据域赋0～(m-1)的值。
请改正程序中的错误，使它能得出正确的结果。
注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。
文件MODI1.C内容如下：
#include＜stdio.h＞
#include＜stdlib.h＞
typedef struet aa
int data；
struct aa *next；
NODE；
NODE *Creatlink(int m)
NODE *h=NULL，*p，*s；
int i；
/**********found**********/
P=(NODE)malloc(sizeof(NODE))；
h=p；
p-＞next=NULL；
for(i=0；i＜m；i++)
s=(NODE *)malloc(sizeof(NODE))；
s-＞data=i：
s-＞next=p-＞next;
p-＞next=s;
p=p-＞next;

/**********found**********/
return p；

void outlink(NODE *h)
NODE *p；
p=h-＞next；
printf("/n/nTHE LIST: /n/n HEAD")；
while(p)
printf("-＞%d"，p-＞data)；
p=p-＞next;

printf("/n");

void main（　）
NODE *head；
head=Creatlink(8)；
outlink(head)；

[填空题]

函数min（　）的功能是：在带头结点的单链表中查找数据域中值最小的结点。请填空
#include ＜stdio.h＞
struct node
{ int data;
struct node *next;
};
int min(struct node *first)/*指针first为链表头指针*/
{ struct node *p; int m;
p=first-＞next; re=p-＞data; p=p-＞next;
for( ;p!=NULL;p= 【20】 )
if(p-＞data＜m ) re=p-＞data;
return m;
}

[填空题]函数main（　）的功能是：在带头结点的单链表中查找数据域中值最小的结点。请填空。
#include＜stdio.h＞
struct node
int data；
struct node * next；

int main(struct node * first)/*指针first为链表头指针*/
struct node * p；int m；
p=first-＞next；m=p-＞data；p=p-＞next；
for(; p!=NULL；p=______)
if(p-＞data＜m)m=p-＞data；
return m；