1．阅读下面的算法

LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针

if(L&&L->next){

q=L; L=L－>next; p=L; S1: while(p－>next) p=p－>next;

p－>next=q; q－>next=NULL;} return L;} 请回答下列问题： 1）说明语句S1的功能；

答：查询链表的尾结点

2）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表________（a2,a3,……,an,a1）_______________________。

2. 阅读下面算法：

void ABC(BTNode * BT) { if （BT） {

ABC (BT->left); cout<data<<’’; ABC (BT->right); } }

该算法的功能是：____递归地后序遍历链式存储的二叉树。____________。

3．阅读下面算法

void conversion(){

Stack s; int n; SElemType e; initstack(s); printf(\ scanf(“%d”,&n);

while(n){

push(s,n%6); n=n/6;

}

while(!stackempty(s)){

pop(s,e); printf(“%d”,e);

}}

1) 指出该算法的功能。

答：十进制转六进制

2) 若输入数据为10，则输出结果为____14_____________。

4. 阅读下列函数

int arrange(int a[], int 1, int h, int x) { //1和h分别为数据区的下界和上界 int i,j,t； i=1；j=h； while(i

while(i=x)j--； while(i=x)i++； if(i

t=a[j]；a[j]=a[i]；a[i]=t； }}

if(a[i]

答：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x 的元素均落在a[i＋1..h]上。

5. 阅读下列算法

void quickpass(int r[], int s, int t){ int i=s,j=t,x=r[s]; while(i

while (i

答：所有奇数移到所有偶数之前 6. 阅读下面算法： void myMethod(List *L) { int m,i,j,flag=1; RecordType x; m=n-1;

while((m>0)&&(flag==1)) { flag=0;

for(j=1;j<=m;j++)

if(L->r[j].key>L->r[j+1].key) { flag=1;

x=L->r[j]; L->r[j]=L->r[j+1]; L->r[j+1]=x; } m--; }

}该算法的功能是：___冒泡排序_______________________。

7. 阅读下列算法

int arrange(int a[], int 1, int h, int x) {

int i,j,t； i=1；j=h；//1和h分别为数据区的下界和上界 while(i

while(i=x)j--； while(i=x)i++；

if(i

答: 调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x 的元素均落在a[i＋1..h]上。 8. 阅读下列算法 typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head){ lklist *p,*q,*s;

for(p=head;p!=0;p=p->next){ for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;}}} 指出该算法的功能。

答：在单链表中删除值相同的多余结点

9. 阅读以下二叉树操作算法，指出该算法的功能。

Template void BinTree ：： unknown(BinTreeNode *t) {

BinTreeNode *p = t, *temp; if (p!=NULL) {

temp = p→leftchild;

p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); unknown(p→rightchild); } }

该算法的功能是：_________左右子树交换________________________。

1.用克鲁斯卡尔算法分析下列无向网，画出最小生成树。

2．已知一个图G的顶点集V各边集E，当它用邻接矩阵或邻接表表示时，分析按深度优先和广度优先搜索遍历得到的顶点序列。

3.散列表为HT，散列函数为H（key）= key % d，用线性探查法解决冲突，求散列表。

4. 用prim算法画出下图的最小生成树（假设从V1开始计算）。

50

45 52 42 V4 V2 V7 50 40 V5 V6 65 V1 60 V3