数据结构 期末考试试卷

一般地，要解决队列的上溢现象可有以下几种方法：

（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。

（2）要避免出现“假溢出”现象可用以下方法解决：

第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位臵，假定空余空间足够。 第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位臵。

第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。

8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 四、算法设计题 1．算法思想为：

（1）应判断删除位臵的合法性，当i<0或i>n-1时，不允许进行删除操作；

（2）当i=0时，删除第一个结点：

（3）当０

{ //在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(i<0)

printf(\ else if(i= =0) { s=q; q=q->next; free(s); } else

{ j=0; s=q;

while((jnext; j++; }

if (s= =NULL) printf(\ delete\ else

{ p->next=s->next; free(s);

} } }

2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下： int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L;

while ( p->next!=NULL ) { p=p->next; len++; }

return (len); }

3．设单循环链表的头指针为head，类型为LinkList。逆臵时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下： void invert(LinkList *head)

{ //逆臵head指针所指向的单循环链表

linklist *p, *q, *s; q=head; p=head->next;

while (p!=head) //当表不为空时，逐个结点逆臵 { s=q; q=p; p=p->next; q->next=s; }

p->next=q; }

4．定义类型LinkList如下： typedef struct node { int data;

struct node *next,*prior; }LinkList;

此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位臵将p结点链入。算法描述如下： insert (LinkList *head) { LinkList *p,*s,*q;

p=head->next; //p指向待插入的结点，初始时指向第一个结点 while(p!=NULL)