5 3 1 2 （2）ASL=(1*1+2*2+3*4+4*3)/10=2.9 13.
给出下图对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度
7 4 6 8 9 10
答案: 邻接矩阵为： A B C D E F
A?0B??1C?0?D?0E?1?F??000100?01000??00111??00000? 10100??10010??其中顶点A的入度为2，出度为1； 其中顶点B的入度为2，出度为2； 其中顶点C的入度为1，出度为3；
14.
已知图5.32如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）
11
b 6 a 3 c 2 5 d 3 2 5 答：
3 f 4 e 终点 b c d e f vj S 15.
阅读下列算法，并回答问题：
6 (a,b) 3 (a,c) ? ? ? c {a,c} 5 (a,c,b) 6 (a,c,d) 7 (a,c,e) ? b {a,c,b} 最短路径求解过程 6 (a,c,d) 7 (a,c,e) ? d {a,c,d} 7 (a,c,e) 9 (a,c,d,f) e {a,c,e} 9 (a,c,d,f) f {a,c,d,f} （1）假设串由合法的英文字母和空格组成，并以’\\0’作结束符。设串s=”??I?am?a???student”(?表示空格符)，写出f30
（s）的返回值；
（2）简述算法f30的功能。 int f30 (char*s) 答案：
(1) 4
(2)算法功能：统计单词的个数。
16.
阅读下列函数,并回答问题：
（1）假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。写出执行函数调用Conv(&q)后的队列q； （2）简述算法Conv的功能。
答案：
（1）
（2）
17.
e，d，c，b，a 将队列里的值反转
阅读下列函数,并回答问题：
已知整形数组L［1..8］中的元素依次为（19，18，15，17，16，13，12，10），阅读下列函数，并写出执行函数调用sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。
12
答案：
（1）第一趟（pass = 0）19 15 18 16 17 12 13 10
（2）第二趟（pass = 1）19 15 16 18 12 17 10 13 18.
已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。 key next void f33 (LinkList L, LinkList H［］, int m) 答案：
（1）NULL （2）p->next=H[j] p=q 19.
下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。
答案：
（1）pre->next=pb （2）pre->next=pa （3）pre->next=pb 20. 答案：
(1）top==-1 （2）top=graph[j].count （3）graph[k].count==0 21.
阅读算法f31，并回答问题：下列算法功能为在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a中各元素的值都不相同。请在空缺处填入合适的内容，使其成为一个完整的算法。 答案：
（1）(i==k) return; （2）i+1 （3）i-1 22.
阅读算法f33，并回答问题：下列算法功能为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。请在空缺处填入合适的内容，使其成为一个完整的算法。
阅读算法f30，并回答问题：下列算法为有向图拓扑排序,请在空缺处填入合适的内容，使其成为一个完整的算法。
答案：
(1)a[i]=t (2)(i=2;i<=n;i+=2) (3)flag
四、算法设计题（本大题共2小题，每小题10分，共20分） 1.
已知单链表的结点类型为Lnode，包含next和data成员。编写算法，实现带头结点单链表的逆置算法。
13
参考答案：
void invent(Lnode *head) {
Lnode *p,*q;
if(!head->next) return ERROR;
p=head->next; q=p->next; p->next =NULL; while(q)
{p=q; q=q->next; p->next=head->next; head->next=p;} } 2.
编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。 其中，栈类型为SeqStack，可以直接使用InitStack(SeqStack**)、 Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函数。 参考答案：
void Inverse(ElemType arr[],int n) { } 3.
二叉树采用链接存储结构，结点类型为Btree，包括left、right和data三个成员，试设计一个算法计算一棵给定二叉树的度为2的结点的个数。
参考答案：
int twochild(Btree *b) { int num1,num2; if (b==NULL) return 0; else
{ num1=twochild1(b->left);
num2=twochild1(b->right);
if ( b->left!=NULL&&b->right!=NULL) return (num1+num2+1); else return (num1+num2); } }
for(i=0;i Pop(s,&arr[i]); InitStack(&s); for(i=0;i Push(s,arr[i]); SeqStack *s; int i; 14 4. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指针 struct node *parent; //指向双亲的指针 } BinTNode; typedef BinTNode *BinTree; 若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。 (1)就后继的不同情况，简要叙述实现求后继操作的方法； 参考答案： （1）分两种情况讨论 ①当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，则该 结点为*px在中序序列中的后继； ②当*px的右孩子为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点 为*px在中序序列中的后继。 (2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。 （2）BinTree f34(BinTree px) { BinTree q=px->rchild; if(q!=NULL){//沿左孩子往下查找 } else{//沿双亲指针链向上查找 while(px!=NULL && px->rchild==q){ } } return px;//返回所找到的中序序列后继结点的指针 } //或者无后继结点时返回空指针 q=px; px=px->parent; px=q; while(px->lchild!=NULL) px=px->lchild; 15