鏁版嵁缁撴瀯涓庣畻娉曞�嶄範棰樺�?- 鐧惧害鏂囧簱

2016《数据结构域算法》复习题

解：

（1）输出结果：ABCCEEBDFFGG （2）时间复杂度：

15.已知有向图的邻接表如图所示，请回答下面问题： (1)给出该图的邻接矩阵；

(2)从结点A出发，写出该图的深度优先遍历序列。

16. 设要将序列{Q, H, C, Y, P, A, M, S, R, D, F, X}中的关

25

2016《数据结构域算法》复习题

键码按字母序的升序重新排列。简述快速排序的思路，并以第一个元素为轴中心，给出用快速排序对序列一趟扫描的结果。 解：

快速排序的思路：（1）从序列中任意选取一个元素作为枢

轴，以枢轴为标准将序列划分成三部分。第一部分的所有元素比枢轴小，第二部分是枢轴自己，第三部分的所有元素比枢轴大。这样处理以后，枢轴的位置已经排好。

（2）对上述划分的第一部分序列和第三部分序列循环执

行第（1）步的操作，直到划分的序列中只有一个元素为止。

针对题目给定的序列，快速排序一趟扫描的结果是：F, H,

C, D, P, A, M, Q, R, S, Y, X.

四、算法填空

1．假设线性表用不带头结点的单向链表表示，结点数据类型如下： struct node{ int s; node * next; }

下面的算法用于求线性表的长度。请在方框中填入适当的

26

2016《数据结构域算法》复习题

内容，将算法补充完整。 int GetLinkLen(node *h){ int s; s=0; while(h) { s=s+1; h=h->next ; } return(s); }

2．设有n个顺序表元素存放在数组v[1]~v[n]中，数组v的最大下标为n0，元素类型为TElem. 下面的算法用于删除顺序表中第一个值为x的元素。请在方框中填入适当内容，将算法补充完整。 void DeleValue (TElem x){ int i, j; i=1;

While( v[i]!=x && i<=n ) i=i+1; if(i<=n){

for(j=n;j>i;j--) v[j-1]=v[j];

27

2016《数据结构域算法》复习题

n-- ; } }

五、算法设计题

1.从顺序表中删除值为x的元素。

答：假定顺序表为a，有效元素个数为n，下标从0开始。 int DeleteReapeatValue(datatype * a, int * pNum, datatype x){ int i, k, n; n=*pNum; k=0;

for(i=0;i

*pNum=n-1; return k; }

2.将顺序存储结构线性表（v1, v2, …, vn）改变成（vk+1,vk+2,…, vn,v1,v2,…, vk）。

答：

void ChangeSequence(datatype * v){ datatype a[SIZE];

28