数据结构自考2009年10月真题及答案解析

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

#define ListSize 100

typedef struct {

int data[ListSize];

int length;

} SeqList, *Table;

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

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

typedef int KeyType;

typedef struct node

 {KeyType key; /*关键字项*/

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

struct node *1child, *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->1child, x);

if (p!=NULL)return p;

if (T->key>x)return T;

return f33(T->rchild, x);

}

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

(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);

1t=strlen(t);

if (ls= =0||1t= =0) return-1;

k=0;

i=0;

do {

j=index(s+i, t);

if (j>=0)

{ pos[k++]=i+j;

i+=j+1t;

}

}while(i+1t<=1s j="">=0);

return k;

}

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

(1)无向图G如图所示，写出算法f30(&G)的返回值;

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

#define MaxNum 20

int visited[MaxNum];

void DFS(Graph *g，int i);

/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited[j]为1*/

int f30(Graph *g)

{ int i，k;

for (i=0; in; i++)/*g->n为图g的顶点数目*/

visited[i]=0;

for (i=k=0; in; i++)

if (visited[i]= =0)

{k++;

DFS(g，i);

}

return k;

}

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

typedef struct Node

{int id; /*学号*/

int score; /*成绩*/

struct Node *next;

} LNode， *LinkList;

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

(1)设结点结构为，成绩链表A和B如图所示，画出执行算法f31(A，B)后A所指的链表;

(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;

}

}

}

已知无向图G的邻接表如图所示，

(1)画出该无向图;

(2)画出该图的广度优先生成森林。

对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。

由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

如图所示，在n×n矩阵A中，所有下标值满足关系式i+jij的值均为0，现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a₁，n存储在sa［0］。

（1）设n=10，元素a₄，9存储在sa[p]，写出下标p的值;

(2)设元素a_i，j存储在sa[k]中，写出由i,j和n计算k的一般公式。

常用的索引顺序文件是________文件和________文件。