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
