全国自考数据结构历年试题及部分答案(2009--2013) - 图文

2. 假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：

typedef struct Node {

int id;/*学号*/

int score；/*成绩*/ struct Node *next； } LNode， *LinkList； 阅读算法f31，并回答问题： (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) (2) 答案：

3. 阅读下列算法，并回答问题：

(1)设串s=＂OneWorldOneDream＂，t=＂One＂，pos是一维整型数组，写出算法 f32(s，t，pos)执行之后得到的返回值和pos中的值； (2)简述算法f32的功能。

int strlen(char*s)； /*返回串s的长度*/ int index(char*st，char*t)；

／*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/ int f32(char*s, char*t, int pos［］)

{ int i, j, k, ls, lt;

ls=strlen(s); lt=strlen(t);

if (ls==0||lt==0) return-1; k=0; i=0;

do {

j=index(s+i, t); if (j>=0)

{ pos［k++］=i+j; i+=j+it;

}

}while(i+it<=is && j >=0);

return k;

}

(1) (2)

答案：（1）2；pos［0］=0,pos［1］=8(说明：每个值1分)（3分）

（2）返回串t在s中出现的次数，并将每次出现的位置依次存放在数组pos中。（2分）

4. 二叉排序树的存储结构定义为以下类型：

typedef int KeyType;

typedef struct node {

KeyType key;/*关键字项*/

InfoType otherinfo;/*其它数据项*/

struct node *lchild, *rchild;/*左、右孩子指针*/ } BSTNode, *BSTree；

阅读算法f33，并回答问题：

(1)对如图所示的二叉排序树T，写出f33(T，8)返回的指针所指结点的关键字； (2)在哪些情况下算法f33返回空指针? (3)简述算法f33的功能。

BSTNode *f33(BSTree T, KeyType x)

{ BSTNode *p;

if (T==NULL) return NULL; p=f33(T->lchild, x); if (p!=NULL) return p; if (T->key >x) return T; return f33(T->rchild, x);

}

(1) (2) (3)

答案：（1）10（2分）

（2）T是空树或T中所有结点的关键字均不大于给定值x时，返回空指针。（2分）

（3）如果二叉排序树T中存在含有关键字大于给定值x的结点，则返回指针指向它们中关键字最 小的结点，否则返回空指针。（1分）

五、算法设计题（本题10分）

1. 假设线性表采用顺序存储结构，其类型定义如下：

#define ListSize 100

typedef struct {

int data［ListSize］; int length;

} SeqList, *Table;

编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。 答案：参考答案一：

void f34(Table L)(或者参数说明为：SeqList *L,1分)

{ int i,j,t;

i=0;（初始化，1分） j=L->length-1;

while(i

{ while(idata［i］%2)（1分） i++;

while(idata［j］%2==0)（1分） j--;

if(i

{t=L->data［i］;（交换，2分） L->data［i］=L->data［j］; L->data［j］=t; i++;(i和j,1分) j--;

}

}(其他，如“L->”表达，1分)

}

参考答案二：

void f34(SeqList*L)(或者参数说明为：Table L,1分) { int i,j=0,t;(初始化，1分)

for(i=0;ilength;i++)(循环控制，2分)

if(L->data［i］%2)/*奇数*/（奇数处理框架，1分） { if(i!=j)(避免同一元素交换，1分) { t=L->data［i］;(交换，2分) L->data［i］=L->data［j］; L->data［j］=t;