发布时间 : 星期一 文章自考数据结构历年试题及答案更新完毕开始阅读7e7bb987e53a580216fcfe68
{
//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd) {
if (pa -> data
(1) ; pre = pb; pb = pb -> next; (2) ; } else {
q = pb; pb = pb -> next; free (q); } } if (pb)
(3) ; }
(1) pre->next = pb (2) pre->next = pa (3) pre->next = pb
31．已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并回答问题： （1）写出执行函数调用 strc (s, r)的返回结果，其中s=〃aba〃, r=〃abababa〃; （2）简述函数strc的功能。
int strc (HString * sub, HString * str) {
int i=0, j, k, count =0;
while (i < str -> length – sub -> length +1) {
j=i; k=0;
while (k length && str -> ch[j] = =sub -> ch[k] ) {
j++; k++; }
if (k = = sub -> length)
{count ++; i=j-sub -> length +1;} else i++; }
return count; } (1) 3
(2) 求串str中子串sub的个数
32．下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。 #define MaxMun 20 //图的最大顶点数 typedef struct {
char vexs [MaxNum]; //字符类型的顶点表 int edges [MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数 }MGraph; //图的邻接矩阵结构描述 typedef enum {FALSE, TRUE} Boolean; Boolean visited [MaxNum];
void MDFSTree (MGraph *G, int i); void MDFSForest (MGraph *G) {
int i, k;
for (i=0; i
visited [i] = (1) ; for (k = 0; k
if (!visited [k]) MDFSTree (G,k); }
void MDFSTree (MGraph *G, int i) { int j;
visited [i]=TRUE; for (j=0; j
if ( (2) ) {
printf (〃<%c, %c>〃G -> vexs [i], G -> vexs [j]); (3) ; } } ｝
1) FALSE //初始化,所有结点未访问
2) !visited[ j ] && G->edge[ i ][ j ] == 1 // 结点j未访问且i到j有边 3) MDFSTree( G, j ) //从j结点继续,深度优先搜索
33.已知整形数组L［1..8］中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用 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 (k if (R[k]>R[k+1]) { x = R[k]; R[k] = R[k+1]; R[k+1] = x; exchange =1; } K+=2 } pass ++; }while (exchange = = 1|| pass <=1); } 第一趟（pass = 0）: 8 9 5 7 3 6 1 2 第二趟（pass = 1）: 8 5 9 3 7 1 6 2 五、算法设计题（本大题共10分） 34．已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为： void find( BT * root, int x, int * count ) { if( !root ) return; if( root->key >= x ){//因为是排序树,只有当key>=x时，才需要查找其左子树 if( root-> lchild ) find( root->lchild, x , count ); (*count)++; printf(\ } if( root-> rchild ) find( root->rchild, x, count ); } 全国2004年10月卷答案 一、单项选择题 DABAC CCBDA ABABD // 5.可以简单的计算，空域为3->7，总共5个，对长则为21 - 5 = 16 7.c//BDBABDABDAB BDA 123失败，比较3次 BDBABDABDAB BDA 1失败，比较1次 BDBABDABDAB BDA 12失败，比较2次 BDBABDABDAB BDA 1失败，比较1次 BDBABDABDAB BDA 123成功，比较3次 10.d A / B / | \\ C D F | E 二、填空题 16.（一组）运算 17. 直接前驱 18. SXSSXXSSXSSXXX 19. 模式匹配 20. 5n - 6 共计10次