数据结构练习题及答案

{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++)

{ x=DeQueue(&Q2) ;

EnQueue( &Q1, x) ; EnQueue( &Q2, x);}

(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。

4. 为什么在单循环链表中设置尾指针比设置头指针更好?

得分 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找

链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。

5．已知下列程序，Ls指向带头结点的单链表。

得分 Typedefstruct node {

DataType data; struct node * next; } * LinkList;

void f30( LinkList Ls ) { LinkList p, q; q = Ls->next;

if ( q && q->next ) { Ls->next = q->next; p=q

while ( p->next ) p = p->next; p->next = q;

q->next = NULL; }}

请回答下列问题：

(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。

(2)请简述算法的功能。

（1）Ls -> 头节点 -> 2 -> 3 -> 4 -> 5 -> 1

（2）把首节点移至末端

6．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义

得分 如下：

typedef struct Node { int id; /*学号*/

int score； /*成绩*/

第 5 页 共 6 页

struct Node *next； } LNode， *LinkList； 阅读算法f31，并回答问题： (1)设结点结构为

f31(A，B)后A所指的链表；

，成绩链表A和B如图所示，画出执行算法

(2)简述算法f31的功能。

void f31(LinkList A, LinkList B) { LinkList p, q; p=A->next; q=B->next; while (p && q)

{ if (p->idid) p=p->next; else if (p->id>q->id) q=q->next; else

{ if (p->score<60) if (q->score<60)

p->score=q->score; else p->score=60; p=p->next; q=q->next; } } }

（1）A -> 头节点 -> 1,70 -> 2,38 -> 3,90 -> 4,60 -> 5,60

（2）将链表A中与链表B中id值相同的节点，按照参照链表B中的score值不小于60取60，否则取原值的规则来更新链表A中的score值

第 6 页 共 6 页