发布时间 : 星期五 文章全国自考数据结构历年试题及部分答案(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->id
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(i while(i 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;i 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;