中国石油大学《数据结构》复习题及答案

n++;

}

else if (s[i]==’?’&& inword==1) inword=0; return n; }

16.

阅读下列函数,并回答问题：

（1）假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。写出执行函数调用Conv(&q)

后的队列q；

（2）简述算法Conv的功能。

void Conv (Queue *Q) { Stack S; InitStack(&S); while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); } 17.

阅读下列函数,并回答问题：

已知整形数组L［1..8］中的元素依次为（19，18，15，17，16，13，12，10），阅读下列函数，并写出执行函数调用sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。

void sort (int R[],int n) { int pass = 0, k, exchange, x; do { k=pass%2+1; exchange = 0; while (kR[k+1]) { x = R[k]; R[k] = R[k+1]; R[k+1] = x; exchange =1; }

K+=2;

11

} pass ++; }while (exchange = = 1|| pass <=1); } 18.

已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的key next 结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。 void f33 (LinkList L, LinkList H［］, int m)

{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在 int i,j;

LinkList p,q; for (i=0;i

H［i］= (1) ; p=L->next; while(p) {

q=p->next; j=p->key%m;

(2) ; H［j］=p;

(3) ; }

free(L); } 19.

下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。

void union (LinkList La, LinkList Lb) {

//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb);

while (pa && pb) { if (pa -> data data) { pre = pa; pa = pa -> next;}

12

20.

else if (pa -> data > pb ->data) { (1) ; pre = pb; pb = pb -> next; (2) ; } else { q = pb; pb = pb -> next; free (q); } }

if (pb) (3) ; }

阅读算法f30，并回答问题：下列算法为有向图拓扑排序,请在空缺处填入合适的内容，使其成为一个完整的算法。

void f30 (hdnodes graph [],int n) {

int i,j,k,top; node_pointer ptr ; top=-1;

for (i=0; i

{ fprintf(stderr, \ has a cycle \\n\ else

{ j=top; _ (2)__;

printf( \ \

for (ptr=graph[j].link; ptr; ptr=ptr->link) {

k=ptr->vertex; graph[k].count--;

if( (3) ) {graph[k].count=top; top=k; } } } }

21. 阅读算法f31，并回答问题：下列算法功能为在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a中各元素的值都不相同。请在空缺处填入合适的内容，使其成为一个完整的算法。

13

#define MAXN 100 int a[MAXN],n,k;

int f31(int a[], int n, int k) {

int low, high, i, j, m, t;

k--,;low=0 ;high=n-1; do {

i=low; j=high ; t=a[low];

do{

while (i

while (i=a[i]) i++ if (i

a[i]=t;

if (1) ;

if (i

22. 阅读算法f33，并回答问题：下列算法功能为奇偶交换排序，思路如下：第一趟对所

有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。请在空缺处填入合适的内容，使其成为一个完整的算法。 void f33 (int a[n]) {

int flag,i,t; do {

flag=0;

for(i=1;ia[i+1])

{ flag=1; t=a[i+1]; a[i+1]=a[i]; _ (1)___; }

for _ (2)___

if (a[i]>a[i+1])

{ flag=1;t=a[i+1]; a[i+1]=a[i]; a[i]=t; } }while ( (3) _ ); }

四、算法设计题（本大题共2小题，每小题10分，共20分）

1. 已知单链表的结点类型为Lnode，包含next和data成员。编写算法，实现带头结点单

14

链表的逆置算法。

2. 编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。

其中，栈类型为SeqStack，可以直接使用InitStack(SeqStack**)、 Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函数。

3. 二叉树采用链接存储结构，结点类型为Btree，包括left、right和data三个成员，试设

计一个算法计算一棵给定二叉树的度为2的结点的个数。

4. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所

示：

typedef char DataType; typedef struct node { DataType data;

struct node *lchild, *rchild; //左右孩子指针 struct node *parent; //指向双亲的指针 } BinTNode;

typedef BinTNode *BinTree;

若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

(1)就后继的不同情况，简要叙述实现求后继操作的方法；

(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。

5. 已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则

印出该路径上的顶点。

6. 已知有n个顶点的有向图邻接表，编写一个函数求出该图中指定顶点的出度。已知边类

型edgenode，包含next和adjvex（序号）成员。类型adjlist表示顶点数组类型，每个数组元素包含link和vex成员。

15