浙江大学远程教育学院 《数据结构与算法》课程离线作业
姓名： 年级：
陈翠 2013秋
学 号： 学习中心：
713009014001 金华学习中心
————————————————————————————— 一、填空题：（【序号，章，节】。。。。。。）
【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。
【2，1，2】为了最快地存取数据元素，物理结构宜采用 顺序存储 结构。
【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序存储结构___， 链式存储结构___。
【4，1，3】度量算法效率可通过 时间复杂度___来进行。
【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是 n(n+1)/2 。
for (i=0; i @ a[i][j]=0; } 【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度: (1) i=1; k=0; while (i<=n-1){ i++; @ k+=10 * i; // 语句的频度是_________n-1_______________。 } (2) k=0; 1 for (i=1; i<=n; i++){ for (j=i; j<=n; j++) @ k++; // 语句的频度是_________n(n+1)/2________________。 } 【7，3，2】线性表(a1，a2，…，an)有两种存储结构： 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充： ___顺序_ 存储密度较大；___顺序____存储利用率较高；___顺序____可以随机存取；__链式_____不可以随机存取；__链式____插入和删除操作比较方便。 【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动 n-i 个元素。 【9，3，2】带头结点的单链表Head为空的条件是___ Head->next=NULL _ ______。 【10，3，2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ p->next ___;和p->next=___ s_ _____的操作。 【11，3，2】在一个单链表中删除p所指结点时，应执行以下操作： q= p->next; p->data= p->next->data; p->next= p->next->next _ ; free(q); 【12，3，2】带头结点的单循环链表Head的判空条件是_ Head->next == Head ____； 不带头结点的单循环链表的判空条件是_ Head == NULL ____。 【13，3，2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接前驱结点的语句序列是__10 12 8 11 4 14___。 b. 删除结点P的语句序列是__10 12 7 3 14______。 c. 删除尾元结点的语句序列是____9 11 3 14_____。 (1) P = P->next; (2) P->next = P; (3) P->next = P->next ->next; (4) P = P->next ->next; (5) while (P != NULL) P = P->next; (6) while (Q->next != NULL){P = Q; Q = Q->next}; (7) while (P->next != Q) P = P->next; (8) while (P->next->next != Q) P = P->next; 2 (9) while (P->next->next != NULL) P = P->next; (10) Q = P; (11) Q = P->next; (12) P = L; (13) L = L->next; (14) free (Q); 【14，3，3】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有 不可能得到的输出序列有CAB 。 【15，3，3】.在栈顶指针为HS的链栈中，判定栈空的条件是 head->next==NULL 。 【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。 void conversion10_16() { InitStack(&s); scanf(“%d”,&N); while(N){ ① ________Push(s, N)______ ; N = N/16; } while(!StackEmpty(s)){ ② _______ Pop(s, e)_ _______ ; if(e<=9)printf(“%d”,e); else printf(“%c”,e-10+’A’); } } /* conversion */ 【17，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。 【18，3，4】堆栈和队列都是线性表, 堆栈是______后进先出_______的线性表, 而队列是____先进先出_______的线性表。 【19，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3 。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。 【20，4，2】已知一棵树边的集合是{ 3 。那么根结点是 e ，结点b的双亲是 d ，结点a的子孙有 bcdj ，树的深度是 4 ，树的度是 3 ，结点g在树的第 3 层。 【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是 树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题 。 【22，4，3】满三叉树的第i层的结点个数为 3i-1 ，深度为h时该树中共有 3 -1h 结点。 【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。则该完全二叉树总共结点有___111_____个；有__7__层；第91号结点的双亲结点是___45__号；第63号结点的左孩子结点是____32_____号。 【24，4，3】下列表示的图中，共有___5____个是树；有___3____个是二叉树；有__2____个是完全二叉树。 【25，4，4】n个结点的二叉排序树的最大深度是 n ，最小深度为 [log2n]+1 。 【26，4，3】如果某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG 4 ，则其先序遍历序列的第一个字母是 I ，最后一个字母是 G 。 【27，4，3】下列二叉树的中序遍历序列是_DBNGOAEC__;后序遍历序列是_____DNIGBECA________。 【28，5，4】设HASH表的大小为 n (n=10), HASH函数为 h(x)=x % 7, 如果二次探测再散列方法Hi=(H(key)+di) mod 10 (di = 12,22,32,…,)解决冲突，在HASH表中依次插入关键字{1,14,55,20,84,27}以后，关键字1、20和27所在地址的下标分别是 1 、__7__和 5 。插入上述6个元素的平均比较次数是 2 。 【29，6，3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i][j]等于 1 ，22、设无向图G的邻接矩阵为A，若A[i][j]等于0，则A[j][i]等于 0 。 【30，6，3】若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是 矩阵第 i 行全部置为零 。 1 【31，6，2】设一个图 G={V,{A}},V={a,b,c,d,e,f},A={ 【32，7，1】排序过程一般需经过两个基本操作，它们是 比较 和 移动 。 【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较 3 次。 5 【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序 、 快速排序 、 堆排序 。 6 二、综合题（选自教材《数据结构》各章习题，采用word文件格式上传） 【1，1，3】试分析下面一段代码的时间复杂度： if ( A > B ) { for ( i=0; i for ( j=N*N; j>i; j-- ) A += B;//A=A+B } else { for ( i=0; i Answer： if A>B为真，则for语句的外循环N次，内循环为N（N-1）次，因此时间复杂度为O(N* N（N-1）)，也就是N的三次方。 if A>B为假，则for语句的外循环2N次，内循环为N次，因此时间复杂度为O（2N*N），也就是N的平方。 【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。令f(x)?1??i?1xi/i，计算f(1.1)的值。利用clock()函数得到两种算法在同一机器上的运行时间。 Answer： f(1.1)=137797.40625 【3，1，3】 试分析最大子列和算法1.3的空间复杂度。 100 7 【4，1，3】试给出判断N是否为质数的O(N)的算法。 Answer： int sushu(int N) { int i; int flag=1; if (N==1) return false;//1既不是合数也不是质数 if (N==2) return true; for (i=2;i<=sqrt(N);i++) { if (N%i==0) { flag=0 break; } } return flag; } 【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+…＋aa…a(n个a)的结果。 Answer： #include\ int main() { int a,b,n,i,s=0; 8 scanf(\ b=a; for(i=1;i<=n;i++) { s+=a; a=a*10+b; } printf(\ } 【6，2，3】请编写递归函数，输出123..n的全排列（n小于10）,并观察n逐步增大时程序的运行时间。 Answer： #include { void permutation(int* a, int b, int e) { int i; if (b == e) { for (i = 0; i < e; ++i) { int t = a;\\ a = b;\\ b = t;\\ } printf(\ 9 } } printf(\ else { for (i = b; i < e; ++i) { } int main(void) { } int a[4] = {1,2,3,4}; permutation(a, 0, 4); /*system(\return 0; } } swap(a[b], a[i]); permutation(a, b + 1, e); swap(a[b], a[i]); 【7，3，2】 给定一个顺序存储的线性表L = (a1, a2, ?, an)，请设计一个算法删除所有值大于min而且小于max的元素。 #include { ElemType data; /* 数据子域 */ 10 struct LNode *next; /* 指针子域 */ }LNode; /* 结点结构类型 */ LNode *L; /* 函数声明 */ LNode *creat_L(); void delete_L(LNode *L,int i); //返回值格式变为空 /* 建立线性链表*/ LNode *creat_L() { LNode *h,*p,*s; ElemType x; h=(LNode *)malloc(sizeof(LNode)); /* 分配头结点 */ h->next=NULL; p=h; printf(\输入一串数字（以-1结束）:\\ndata= \ scanf(\ /* 输入第一个数据元素 */ while( x!=-1) /* 输入-1，结束循环 */ { s=(LNode *)malloc(sizeof(LNode)); /* 分配新结点 */ s->data=x; s->next=NULL; p->next=s; p=s; printf(\ scanf(\ /* 输入下一个数据*/ } return(h); } /* creat_L */ /* 输出单链表中的数据元素*/ void out_L(LNode *L) { LNode *p; p=L->next; printf(\数据是:\ 11 while(p!=NULL) { printf(\ p=p->next; } } /* out_link */ /* 删除大于x小于y的值*/ void delete_L(LNode *L,int a,int b) { LNode *p,*q; p=L; q=p; p=p->next; if(p==NULL) printf(\链表为空\ while(p!=NULL) { if((p->data >a) && (p->data } /* delete_L */ void main() { int a,b; 12 L=creat_L( ); out_L(L); printf(\请输入你要删除的元素的范围min和max:\\n\ scanf(\ delete_L(L,a,b); out_L(L); printf(\} /* main */ 【8，3，2】给定一个顺序存储的线性表L = (a1, a2, ?, an)，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 #include #define MAXN 1003 int A[MAXN]; int dp[MAXN]; // 动态规划思想O(n^2) int main() { int n, i, j, k; cin >> n; for (i=1; i<=n; i++) cin >> A[i]; dp[1] = 1; // 有n个阶段 for (i=2; i<=n; i++) { dp[i] = 1; // 每个阶段只有1个状态 // 每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度 for (j=i-1; j>=0; j--) { if (A[i]>A[j]) dp[i] = max(dp[i], dp[j]+1); } 13 } int maximum = dp[1]; for (i=2; i<=n; i++) maximum = max(maximum, dp[i]); cout << maximum; } 【9，3，3】 如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop, push）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？ Answer： 共有34种不同的输出序列 12345 12354 12435 12543 13245 13254 14325 15432 21345 21435 21543 23145 23154 23415 23451 23541 24315 24351 24531 25431 32145 32154 32415 32451 32541 34215 34251 34521 35421 43215 43251 43521 45321 54321 【10，3，2】请编写程序将中缀表达式转换为后缀表达式。 #include if(op=='+'||op=='-') return 1; if(op=='*'||op=='/') return 2; return 0; } string middletolast(string middle) { 14 stack for(int i=0;i char c=middle[i]; if(c>='0'&&c<='9') { ans.append(1,c); } else { if(c=='(') op.push('('); else { if(c==')') { while(op.top()!='(') { ans.append(1,op.top()); op.pop(); } op.pop(); } else { if(op.empty()) { op.push(c); } else { if(prior(c)>prior(op.top())) op.push(c); else { while(!op.empty()&&prior(c)<=prior(op.top())) { ans.append(1,op.top()); 15 op.pop(); } op.push(c); } } } } } } while(!op.empty()) { ans.append(1,op.top()); op.pop(); } return ans; } int main() { string mdata,res; cin>>mdata; res=middletolast(mdata); for(int i=0;i if(i==0) cout< cout<<' '< cout< 【11，4，3】设二叉树的存储结构如下： Lchild data Rchild 1 0 J 0 2 0 H 0 3 2 F 0 4 3 D 9 5 7 B 4 16 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 其中根结点的指针值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为数据域。 （1） 画出二叉树的逻辑结构。 （2） 写出该树的前序、中序和后序遍历的序列。 Answer (1) A B C D F G I E H (2)前序：ABDFECGHI 中序：DBEFAGHCI 后序：DEFBHGICA 【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意4个。 17 答：可以生成如上二叉排序树的关键字的初始排列有30种 任写4个序列如下： （5， 7， 6，4，2，1，3） （5， 7， 6，4，2，3，1） （5， 4， 2，3，7，6，1） （5， 4， 2，1，7，6，3） 【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答： （1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）； （2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）； ANSWER 11 7 16 4 22 13 5 【14，4，6】 假设一个文本使用的字符集为{a,b,c,d,e,f,g}, 字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。 （1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符； （2）若这些字符在文本中出现的频率分别为：{3,35,13,15,20,5,9}，求该哈夫曼树的带权路径长度。 ANSWER: 74 / \\ 42 32 18 / \\ / \\ 23 19 12 20 / \\ / \\ 15 8 9 10 / \\ 8 7 / \\ 3 5 编码：A（010）B（00000）C（00001）D（001）E（10）F（11）G（0001）H（011） 带权路径长度值为：（3+5）*5+7*4+（8+9+10）*3+（12+20）*2=213 【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。 Answer:924300 【16，5，4】设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为：H(key) = key % 17，采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。 ANSWER: 首先将各个数除以17取余数：（6,2,7,1,2,7,7,6）可见20,85与46冲突，58与71冲突。将7+1再对13取余，直到无冲突，类似的6+1对13取余，最后可得H(71)=6；H（28）=2；H（46）=7；H(14)=1；H(2)=3；H(20)=8；H(85)=9；H(58)=10；哈希表存储结构： 0 1 2 3 4 5 6 7 8 9 10 14 28 2 71 46 20 85 58 平均查找长度=（1×4+2×2+3×1+4×1）/8=15/8 19 【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key×3）mod TableSize，要求装入因子为0.7。 Answer: 关键字 散列地址 7 8 30 0 11 3 18 4 9 7 14 2 1 4 线性探测法构建列表的过程 插入7 插入8 插入30 插入11 插入18 插入9 插入14 0 30 1 7 2 14 3 11 4 8 20 5 5 6 7 9 8 9 d1=1 【18，6，3】已知一个无向图的顶点集为{V0，V1，…，V7}，其邻接矩阵如下所示： V0 0 1 0 1 1 0 0 0 V1 1 0 1 0 1 0 0 0 V2 0 1 0 0 0 1 0 0 V3 1 0 0 0 0 0 1 0 V4 1 1 0 0 0 0 1 0 V5 0 0 1 0 0 0 0 0 V6 0 0 0 1 1 0 0 1 V7 0 0 0 0 0 0 0 1 (1) 画出该图的图形； (2) 给出从V0出发的深度优先遍历序和广度优先遍历序。 【19，6，3】已知有向图如右图所示，请给出该图的 （1） 每个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 各个强连通分量。 答：（1）各顶点的入/出度如下：顶点1:3/0；顶点2:2/2； 顶点3:1/2；顶点4:1/2；顶点5:2/1；顶点6:2/3。 （2）邻接矩阵如下： 1 0 1 0 0 1 1 3 4 5 2 0 0 1 0 0 3 0 0 0 1 0 21 4 0 1 0 0 0 5 0 0 0 1 0 6 0 0 1 1 0 6 1 （3）邻接表如下： 1 ^ 1 0 0 1 0 2 1 4 3 6 2 4 3 5 6 5 1 6 1 2 5 （4）逆邻接表如下： 1 2 5 6 2 3 6 3 4 4 2 5 4 6 6 3 4 (5)有意向3个强连通分量 6 ○1 ○5 ○2 ○4 ○ ○3 【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。 22 Answer： 1 c:2 2 c:2 f:6 3 c:2 f:6 e:10 4 c:2 f:6 e:10 d:11 5 c:2 f:6 e:10 d:11 g:14 6 c:2 f:6 e:10 d:11 g:14 b:15 【21，6，3】给出如下图所示的具有7个结点的网G。请： （1） 画出该网的邻接矩阵； （2） 采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法 的执行过程及最小生成树的生成示意图）。 1 4 3 7 2 1 6 0 5 6 2 5 1 3 5 3 2 4 4 【22，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。 Answer 简单选择排序过程如下： 步骤 1 2 48 6 6 25 48 17 6 25 48 90 90 25 17 17 90 84 84 84 62 62 62 48 48 48 27 27 27 96 96 96 49 49 49 72 72 72 17 17 17 23 3 4 5 6 7 8 9 10 11 12 6 6 6 6 6 6 6 6 6 6 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 48 25 25 25 25 25 25 25 25 25 25 48 27 27 27 27 27 27 27 27 90 90 48 48 48 48 48 48 48 48 84 84 90 90 48 48 48 48 48 48 62 62 84 84 90 49 49 49 49 49 48 48 62 62 84 90 62 62 62 62 27 27 48 48 62 84 90 72 72 72 96 96 96 96 96 62 84 90 84 84 49 49 49 49 49 96 96 84 90 90 72 72 72 72 72 72 72 96 96 96 冒泡排序过程如下： 步骤 1 2 3 4 5 6 24 48 25 25 6 6 6 6 25 48 6 25 17 17 17 6 6 48 17 25 25 17 90 90 17 48 48 27 25 17 17 84 48 48 48 27 84 84 48 62 27 48 48 62 48 48 62 62 27 27 49 49 62 49 17 48 49 27 27 49 72 17 62 62 96 49 72 17 72 72 72 49 72 17 84 84 84 84 72 17 90 90 90 90 90 17 96 96 96 96 96 96 【23，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请分别用堆排序、快速排序和归并排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。 Answer： 快速排序 步骤 1 2 3 【24，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请用3种不同的增量序列分别进行希尔排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。 Answer 增量序列{5,3,1} 第一步：{48,84,49}、{25,62,72}、{6,48,17}，{90,27}、{17,96} 48, 49，84 ，25,62,72，6, 17，48，27，90 ，17,96 25 48 48 6 6 25 17 17 6 6 17 17 90 17 25 25 17 27 27 27 84 17 48 48 62 48 48 90 48 49 48 49 27 84 84 62 96 62 62 72 49 96 72 84 72 49 90 90 17 72 96 96