1、以下算法是求取某带头结点的单链表的长度，请补充完整代码。 int LinkLength（LinkList L) { Node* p=L-＞next; int i=0; ...... //补充此处代码 return i; //返回链表长度 }

●试题四

阅读下列程序说明，将在空缺处填入正确的内容。

【程序说明】

定义一个多边形结构：struct polygon实现以下内容： (1) 建立该结构的链表：create函数是创建链表，每输入一个结点的数据，就把该结点加入到链表当中，它返回创建的链表的头指针。 (2) 显示链表的各个结点数据：结点数据包括：多边形顶点数、各顶点的纵横坐标、当多边形顶点数为0时，链表创建结束。 (3) 编写一个函数disp，删除链表中的所有结点。需要注意的是：要先释放结点数据内存，再删除结点，如果在释放结点数据内存单元之前删除结点，则无法找到结点数据内存单元的地址，也就无法释放数据的内存单元。

【程序】

#include"iostream.h"

#include"iomanip.h"

struct polygon

{

int n；

int *x；

int *y；

polygon *next；

}；

void Push(polygon*& head，int n)

{

polygon*newNode=new polygon；

newNode=new polygon；

newNode－>next= (1) ；

newNode－>x=new int[n]；newNode－>y=new int[n]；newNode－>n= (2) ；

for(int i=0；i<= (3) ；i++){

cout<<"请输入多边形各顶点x、y坐标，坐标值之间用空格分隔："；

cin>>newNode->x[i]>>newNode->y[i]；}

(4) =head；// 在head前不需要额外的*

head=newNode；

}

polygon *create()

{

polygon*head=NULL；

polygon*tail；

int n；

cout<<"请输入多边形顶点的个数(顶点个数为0时结束)："；

cin>>n；

if(n==0)return (5) ；

Push(head， (6) ；

tail=head；

cout<<"请输入多边形顶点的个数(顶点个数为0时结束)："；

cin>>n；

while(n!=0)

{

Push(tail－>next， (7) ；//在tail－>next增加结点

tail=tail－>next；//advance tail to point to last node

cout<<"请输入多边形顶点的个数(顶点个数为0时结束)："；

cin>>n；

}

return head；

}

void disp(polygon*head)

{

int i，No=1；

cout<<setw (10) <<"x"<<setw (6) <<"y"<<endl；

while(head!=NULL)

{

cout<<"第"<<No<<"结点："<<endl;

for(i=0；i<=head－>n－１；i++)

cout<<setw (10) <<head－>x[i]<<setw (6) <<head－>y[i]<<endl；

(8) ；

head= (9) ;

}//Match while statement

}

void del(polygon*head)

{

polygon*p；

while(head!=NULL)

{

p= (10) ；

head=head－>next；

delete p－>x；

delete P－>y；

deletep；

}//Match while statement

}

void main()

{

polygon*head；

head=create()；

disp(head)；

del(head)；

}

阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

本题给出四个函数，它们的功能分别是：

1．int push(PNODE*top，int e)是进栈函数，形参top是栈顶指针的指针，形参e是入栈元素。

2．int pop(PNODE*top，int*e)是出栈函数，形参top是栈顶指针的指针，形参e作为返回出栈元素使用。

3．int enQueue(PNODE*tail，int e)是入队函数，形参tail是队尾指针的指针，形参e是入队元素。

4．int deQueue(PNODE*tail，int*e)是出队函数，形参tail是队尾指针的指针，形参e作为返回出队元素使用。

以上四个函数中，返回值为。表示操作成功，返回值为-1表示操作失败。

栈是用链表实现的；队是用带有辅助结点(头结点)的单向循环链表实现的。两种链表的结点类型均为：

typedef struct node {

int value;

struct node * next;

} NODE, * PNODE;

【函数1】

int push(PNOOE * top,int e)

{

PNODE p = (PNODE) malloc (sizeof (NODE));

if (! p) return-1;

p-＞value=e;

(1);

*top=p;

return 0;

}

【函数2】

int pop (PNODE * top,int * e)

{

PNODE p = * top;

if(p == NULL) return-1;

* e = p-＞value;

(2);

free(p);

return 0;

}

【函数3】

int enQueue (PNODE * tail,int e)

{ PNODE p,t;

t= *tail;

p = (PNODE) malloc(sizeof(NODE));

if(!p) return-1;

p-＞value=e;

p-＞next=t-＞next;

(3);

* tail = p;

return 0;

}

【函数4】

int deQueue(PNODE * tail,int * e)

{ PNODE p,q;

if(( * tail)-＞next == * tail) return-1;

p= (* tail)-＞next;

q = p -＞next;

* e =q -＞value;

(4)=q-＞next;

if(,tail==q) (5);

free(q);

return 0;

}

阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。

[说明1]

L为一个带头结点的循环链表。函数LinkList deletenode(LinkList L,int c)的功能是删除L中数据域data的值大于C的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。

[C函数1]

LinkList deletenode(LinkList L,int c)

{LinkList Lc,P,pre;

pre=L;

p=(1);

Lc=(LinkList)malloc(sizeof(Listnode));

Lc-＞next=Lc;

while(P!=L)

if(p-＞data＞C){

(2);

(3);

Lc-＞next=p;

p=pre-＞next;

}

else{

pre=p;

p=pre-＞next;

}

return Lc;

}

[说明2]

递归函数dec_to_k_2(int n,int k)的功能是将十进制正整数n转换成k(2≤k≤9)进制数，并打印。

[C函数2]

dec to k 2(int n,int k)

{ if(n!=O){

dec to k 2( (4) ,k);

printf("%d", (5) );

}

}

链表题：一个链表的结点结构

struct Node

{

int data ;

Node *next ;

};

typedef struct Node Node ;

(1)已知链表的头结点head,写一个函数把这个链表

逆序( Intel)

下列给定程序中，是建立一个带头结点的单向链表，并用随机函数为各结点数据域赋值。函数fun的作用是求出单向链表结点(不包括头结点)数据域中的最大值，并且作为函数值返回。

请改正程序指定部位的错误，使它能得到正确结果。

[注意] 不要改动main函数，不得增行或删行，也不得更改程序的结构。

[试题源程序]

include＜stdio.h＞

include＜stdlib.h＞

typedef struct aa

{

int data;

struct aa *next;

}NODE;

fun(NODE *h)

{

int max=-1;

NODE *p;

/***********found************/

p=h;

while(p)

{

if(p-＞data＞max)

max=p-＞data;

/************found************/

p=h-＞next;

}

return max;

}

outresult(int s, FILE *Pf)

{

fprintf(pf, "\nThe max in link: %d\n", s);

}

NODE *creatlink(int n, int m)

{

NODE *h, *p, *s, *q;

int i, x;

h=p=(NODE *)malloc(sizeof(NODE));

h-＞data=9999;

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;

}

p-＞next=NULL;

return h;

}

outlink(NODE *h, FILE *pf)

{

NODE *p;

p=h-＞next;

fprintf(Pf, "\nTHE LIST:\n\n HEAD");

while(P)

{

fprintf(pf, "-＞%d", P-＞datA); p=p-＞next;

}

fprintf(pf, "\n");

}

main()

{

NODE *head; int m;

head=cteatlink(12,100);

outlink(head, stdout);

m=fun(head);

printf("\nTHE RESULT"\n");

outresult(m, stdout);

}

阅读以下代码，回答问题：1至问题3 ，将解答填入答题纸的对应栏内。 【代码1】 include<stdio.h > void swap(int x, int y) { int tmp =x; x= y; y= tmp; } int maim() { int a= 3, b= 7; printf("a1= %d b1=%d\n",a,b); Swap( a, b); Printf("a2 = %d b2=%d\n”,a,b)； return 0; } 【代码2】 include<stdio.h> define SPACE " //空格字符 Int main() { char str[128] =" Nothing is impossible! "; int i,num =0,wordMark=0; for(i=0;str[i];i++) If(str[i]==SPACE) WordMark=0; else If(wordMark=0){ wordMark=1; num++; } Printf(“%d/n”,num) return 0; } 【代码3】 include<stdio.h> define SPACE " //空格字符 int countStrs(char *); int main() { char str[128] = " Nothing is impossible! "; Printf("%d/n",（1）(str)) return 0; } int countStrs(char *p) { int num=0, wordMark= 0; for(;（2）; p++) { If(（3）==SPACE) wordMark= 0; else if( !wordMark ) { wordMark = 1; ++num } } return （4） ; }

【问题1】（4分） 写出代码1运行后的输出结果。 【问题2】（3分） 写出代码2运行后的输出结果。 【问题3】（8分） 代码3的功能与代码2完全相同，请补充3中的空缺，将解答写入答题纸的对应栏内。

int AA(LNode *HL , ElemType x)

{

int n=0; LNode *p=HL;

while (p!=NULL)

{

if (p->data= =x) n++;

p=p->next; }

return n;

}

对于结点类型为LNode的单链表，以上算法的功能为：()

已知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)；}

函数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=【 】)

if(p-＞data＜m ) re=p-＞data;

return m;

}

阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明2.1】

L为一个带头结点的循环链表。函数deletenode(LinkList L, int c)的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。

【函数2.1】

LinkList deletenode(LinkList L, int c)

{

LinkList Lc,p,pre;

pre=L;

p=(1);

Lc=(LinkList)malloc(sizeof(ListNode) );

Lc-＞next=Lc

while(p!=L)

if(p-＞data＞c)

{

(2);

(3);

Lc-＞next=p;

p=pre-＞next;

}

else

{

pre=p;

p=pre-＞next;

}

return Lc;

}

【说明2.2】

递归函数dec_to_k_2(int n, int k)的功能是将十进制正整数n转换成k＜2≤k≤9)进制数，并打印。

【函数2.2】

dec_to_k_2(int n, int k)

{ /*将十进制正整数n转换成k(2≤k≤9)进制数*/

if(n!=0)

{

dec_to_k_2((4),k);

printf("%d",(5));

}

}

执行下列语句后指针及链表的示意图为(43)。

L = (LinkList) malloc ( sizeof (LNode) );

P = L;

for(i =0;i ＜=3;i ++) {

P→next = (LinkList) malloc (sizeof (LNode));

P = P→next;

P→data = i * i + 1;

}

A．

B．

C．

D．

阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第i个元素。若找到，则返回指向该结点的指针，否则返回空指针。 函数DelListElem(LinkList L，int i，ElemType *e) 的功能是删除含头结点单链表的第 i个元素结点，若成功则返回 SUCCESS ，并由参数e 带回被删除元素的值，否则返回ERROR 。 例如，某含头结点单链表 L 如图 4-1 (a) 所示，删除第 3 个元素结点后的单链表如 图 4-1 (b) 所示。图4-1

define SUCCESS 0 define ERROR -1 typedef int Status; typedef int ElemType; 链表的结点类型定义如下: typedef struct Node{ ElemType data; struct Node *next; }Node ,*LinkList; 【C 代码】 LinkList GetListElemPtr(LinkList L ，int i) { /* L是含头结点的单链表的头指针，在该单链表中查找第i个元素结点: 若找到，则返回该元素结点的指针，否则返回NULL */ LinkList p; int k; /*用于元素结点计数*/ if (i<1 ∣∣ !L ∣∣ !L->next) return NULL; k = 1; P = L->next; / *令p指向第1个元素所在结点*/ while (p && （1） ) { /*查找第i个元素所在结点*/ （2） ; ++k; } return p; } Status DelListElem(LinkList L ，int i ，ElemType *e) { /*在含头结点的单链表L中，删除第i个元素，并由e带回其值*/ LinkList p，q; /*令p指向第i个元素的前驱结点*/ if (i==1) （3） ； else p = GetListElemPtr(L ，i-1); if (!p ∣∣ !p->next) return ERROR; /*不存在第i个元素*/ q = (4) ； /*令q指向待删除的结点*/ p->next = q->next; /*从链表中删除结点*/ (5) ； /*通过参数e带回被删除结点的数据*/ free(q); return SUCCESS; }

阅读以下说明和 C 函数，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 Combine(LinkList La，LinkList Lb)的功能是:将元素呈递减排列的两个含头结 点单链表合并为元素值呈递增(或非递减)方式排列的单链表，并返回合并所得单链表 的头指针。例如，元素递减排列的单链表 La 和 Lb 如图 4-1 所示，合并所得的单链表如图 4-2 所示。图 4-1 合并前的两个链表示意图图 4-2 合并后所得链表示意图

设链表结点类型定义如下： typedef struct Node{ int data; struct Node *next; }Node ,*LinkList; 【C 函数】 LinkList Combine(LinkList La ，LinkList Lb) { //La 和 Lb 为含头结点且元素呈递减排列的单链表的头指针 //函数返回值是将 La 和 Lb 合并所得单链表的头指针 //且合并所得链表的元素值呈递增（或非递减)方式排列 （1） Lc ,tp ,pa ,pb;; //Lc 为结果链表的头指针 ，其他为临时指针 if (!La) return NULL; pa = La->next; //pa 指向 La 链表的第一个元素结点 if (!La) return NULL; pa = La->next; //pb 指向 Lb 链表的第一个元素结点 Lc = La; //取 La 链表的头结点为合并所得链表的头结点 Lc->next = NULL; while ( （2） ){ //pa 和 pb 所指结点均存在(即两个链表都没有到达表尾) //令tp指向 pa 和 pb 所指结点中的较大者 if (pa->data > pb->data) { tp = pa; pa = pa->next; } else{ tp = pb; pb = pb->next; } （3） = Lc->next; //tp 所指结点插入 Lc 链表的头结点之后 Lc->next = （4） ; } tp = (pa)? pa : pb; //设置 tp 为剩余结点所形成链表的头指针 //将剩余的结点合并入结果链表中， pa 作为临时指针使用 while (tp) { pa = tp->next; tp->next = Lc->next; Lc->next = tp; （5） ; } return Lc; }