发布时间 : 星期三 文章数据结构与算法复习题及参考答案剖析更新完毕开始阅读1e37a09c2dc58bd63186bceb19e8b8f67c1cefe9
2016《数据结构域算法》复习题
typedef struct node { char data;
struct node*lchild, *rchild; ∥左右孩子指针 } *BinTree； 阅读下列程序。 void f13(BinTree T){
InitStack(S); ∥ 初始化一个堆栈S while(T || !StackEmpty(S)){
while(T){
Push(S,T); T=T->lchild; }
if(!StackEmpty(S)){
T=Pop(S);
printf(“%c”,T->data); T=T->rchild; } } }
回答下列问题：
(1)已知以T为根指针的二叉树如图所示， 请写出执行f13(T)的输出结果：
(2)简述算法f13的功能。
14．设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其
中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题： C的结点类型定义如下： （1）对下列二叉树B，执行下列算法traversal(root)，试指出其输出结struct node 果； {char data; （2）假定二叉树B共有n个结点，试分析算法traversal(root)的时间复struct node *lchild, rchild; 杂度。 }; 二叉树B C算法如下： void traversal(struct node *root) A {if (root) B {printf(“%c”, root->data); C traversal(root->lchild); E printf(“%c”, root->data); traversal(root->rchild); } } 9
2016《数据结构域算法》复习题
解：
（1）输出结果：ABCCEEBDFFGG （2）时间复杂度：
15.已知有向图的邻接表如图所示，请回答下面问题： (1)给出该图的邻接矩阵；
(2)从结点A出发，写出该图的深度优先遍历序列。
16. 设要将序列{Q, H, C, Y, P, A, M, S, R, D, F, X}中的关键码按字母序的升序重新排列。简述快速排序的思路，并以第一个元素为轴中心，给出用快速排序对序列一趟扫描的结果。 解：
快速排序的思路：（1）从序列中任意选取一个元素作为枢轴，以枢轴为标准将序列划分成三部分。第一部分的所有元素比枢轴小，第二部分是枢轴自己，第三部分的所有元素比枢轴大。这样处理以后，枢轴的位置已经排好。
（2）对上述划分的第一部分序列和第三部分序列循环执行第（1）步的操作，直到划分的序列中只有一个元素为止。
针对题目给定的序列，快速排序一趟扫描的结果是：F, H, C, D, P, A, M, Q, R, S, Y, X.
四、算法填空
1．假设线性表用不带头结点的单向链表表示，结点数据类型如下： struct node{ int s; node * next;
10
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]; 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 If(a[i]==x) k++; Else a[i-k]=a[i]; } *pNum=n-1; return k; } 2.将顺序存储结构线性表（v1, v2, …, vn）改变成（vk+1,vk+2,…, vn,v1,v2,…, vk）。 答： 11 2016《数据结构域算法》复习题 void ChangeSequence(datatype * v){ datatype a[SIZE]; for(int i=1;i for(i=1;i<=n;i++) v[(k+i)%n]=a[i]; } 3.将顺序存储的线性表（v1, v2, …, vn）改变成（v1, v3, v5,…）。 答： void ChangeSequence(datatype * v){ for(int i=3;i<=n;i+=2) v[i-i/2]=v[i] } 4.从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。 答： int DeleteAllReapeatValue(datatype * a, int * pNum){ int n=*pNum; int i , j ; for(i=0;i for(j=i+1; j if(a[i]!= INFINITY && a[i]==a[j]) a[j]= INFINITY; return DeleteReapeatValue(a,pNum, INFINITY); } 5.从键盘输入一系列整数，建立一个长度为n的、不含重复元素的顺序表。 答： int CreateSequence(){ int a[SIZE]; int i=0, j, k; while(i scanf(“%d”, &k); for(j=0; j<=i ; j++) if(a[j]==k) break; if(j>i) a[++i]=k; } } 6.从键盘输入n个整数，建立带表头结点的单向链表。 答： LinkList CreateList(){ int i=0 , j , k; LinkList head=(Node*)malloc(sizeof(Node)); Node* r=head,*p=NULL; While(i scanf(“%d”, &k); p=head->next; while(p){ if(p->data==k) break; p=p->next; } 12