《厦门大学数据结构与算法(陈海山)期末习题答案解析》由会员分享，可在线阅读，更多相关《厦门大学数据结构与算法(陈海山)期末习题答案解析（26页珍藏版）》请在金锄头文库上搜索。
1、作业：1-1,7,8 2-1，2,4,7,9,11,13，19 3-2,3，7,8,13,144-3,9,13 5-1,2,6,8 5-1,2,6,7，8，12,14,17习题1 绪论 1-1 名词解释：数据结构。数据结构：相互之间存在一定关系的数据元素的集合1-2 数据结构的基本逻辑结构包括哪四种? 集合：数据元素之间就是“属于同一个集合” 线性结构：数据元素之间存在着一对一的线性关系 树结构：数据元素之间存在着一对多的层次关系 图结构：数据元素之间存在着多对多的任意关系1-3 数据结构一般研究的内容不包括( )。(A) 集合的基本运算(B) 数据元素之间的逻辑关系(C) 在计算机中实现对数
2、据元素的操作(D) 数据元素及其关系在计算机中的表示选D数据的逻辑结构、数据的存储结构、数据的运算1-4 算法包括哪五种特性?2. 算法的五大特性： 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1-5 简述算法及其时间复杂度。1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。算法复杂度(Algorithm Complex
3、ity)：算法占用机器资源的多少，主要有算法运行所需的机器时间和所占用的存储空间。时间复杂度(Time Complexity)：算法运行所需要的执行时间，T(n)= O(f(n)。空间复杂度(Space Complexity)：算法运行所需要的存储空间度量，S(n)= O(f(n)。1-6 设数组A中只存放正数和负数。试设计算法，将A中的负数调整到前半区间，正数调整到后半区间。分析算法的时间复杂度。An+1 For(int i=n-1,j=0;ij;i-)If(ai0) continue;Else An=Ai;Ai=Aj;Aj=An;J+;时间复杂度为O(n)1-7 将上三角矩阵 A=(aij
4、)nn 的非0元素逐行存于B(n*(n+1)/2中，使得 Bk=aij 且 k=f1(i)+f2(j)+c (f1, f2不含常数项)，试推导函数f1, f2和常数c。k+1=1+2+3+(i-1)+jk=1/2*i*(i-1)+j-1;1-8 描述下列递归函数的功能。int F(int m, int n) if (nm) return F(n, m); else if (n=0) return m; elser=m%n;return F(n, r);求 m与n的最大公约数1-9 编写递归算法： 0，m=0且n0 g(m, n)= g(m-1, 2n)+n，m0且n0double g(doub
5、le m,double n)If(m=0&n=0)return 0;elsereturn g(m-1,2*n)+n;1-10 将下列递归过程改写为非递归过程。void test(int &s) int x; scanf (“%d”, &x); if (x=0) s=0; elsetest(s);s+=x;习题2 表 2-1 如果长度为n的线性表采用顺序存储结构存储，则在第i (1in+1)个位置插入一个新元素的算法的时间复杂度为( )。(A) O(1)(B) O(n)(C) O(nlog2n)(D) O(n2)B 需要让线性表移动n+1-i个2-2 在一个有127个元素的顺序表中插入一个新元素
6、，要求保持顺序表元素的原有(相对)顺序不变，则平均要移动( )个元素。(A) 7(B) 32(C) 64(D) 127C n/2+12-3 将关键字2，4，6，8，10，12，14，16依次存放于一维数组A0.7中，如果采用折半查找方法查找关键字，在等概率情况下查找成功时的平均查找长度为( )。(A) 21/8(B) 7/2(C) 4(D) 9/2 A3,2,3,1,3,2,3,4公式法 1*20+2*21+3*22+i*2(n-1);2-4 已知顺序表L递增有序。设计一个算法，将a和b插入L中，要求保持L递增有序且以较高的效率实现。先用折半查找法查询位置，然后移动void insert(in
7、t L,int a,int b)/ab int i=0,p,q; n= length(L);/L现有长度 /查找确定a、b的位置 for(;in;i+) if( Li=a&(aLi+1|i=n-1) ) p = i+1; /a的最终位置 n+; break; for(;in;i+) if( Li=b&(bq;i-) Li = Li-2; Lq = b;/插入b for(i=q-1;ip;i-) Li = Li-1; Lp = a;/插入a2-5 简单描述静态查找和动态查找的区别。A 静态查找表只查找 B、静态查找表不改变数据元素集合内的数据元素 C、动态查找表不只查找 D、动态查找表还插入或删
8、除集合内的数据元素2-6 综合比较顺序表和链表。(1)存储空间利用率高只存储元素值。(2)随机存取可以通过计算来确定顺序表中第i个数据元素的存储地址 Li = L0+(i-1)*m,其中，L0为第一个数据元素的存储地址，m为每个数据元素所占用的存储单元数。(3)插入和删除数据元素会引起大量结点移动.顺序表：内存中地址连续 长度不可变更 支持随机查找 可以在O(1)内查找元素 适用于需要大量访问元素的 而少量增添/删除元素的程序 链表 ：内存中地址非连续 长度可以实时变化 不支持随机查找 查找元素时间复杂度O（n） 适用于需要进行大量增添/删除元素操作 而对访问元素无要求的程序2-7 解释链表的
9、“头指针、头结点和首元素结点”三个概念。“头指针”是指向头结点的指针。 头结点是为了操作的统一、方便而设立的，放在首元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。 “首元结点”也就是第一元素结点，它是头结点后边的第一个结点。2-8 描述下列算法的主要功能是( )。 构造头结点L，取q=L; 产生1个结点p; qnext=p; 输入pdata的值; 取q=p; 重复执行至n次; pnext=NULL; (A) 通过输入n个数据元素构建链表L (B) 采用前插法，在链表L中输入n个数据元素(C) 通过产生n个结点构建链栈L，q为栈顶指针(D) 在链队列L中输
10、入n个数据元素，q为队尾指针A2-9 设L是不带头结点的单链表的头指针，k是一个正整数，则下列算法的主要功能是( )。LinkSearch (LinkList L, int k)k0=0;p=L-next; / next为单链表的指针域q=p;while ( p )if (k0next;p=p-next;q-next=0;(A) 计算单链表L的长度(B) 查找单链表L中倒数第k个结点(C) 删除单链表L中最后面的k个结点(D) 将单链表L中第k个结点q的指针置0只遍历一次的高效算法（排除法）B2-10 设链表L不带头结点，试分析算法的功能。A(Linklist &L)if (L & L-nex
11、t)Q=L;L=L-next;P=L;while (P-next) P=P-next;P-next=Q;Q-next=NULL; /A算法结束将链表的第一个结点接到最后一个结点后面2-11 设两个循环链表的长度分别为n和m，则将这两个循环链表连接成一个循环链表，最好的时间复杂度为( )。(A) O(1)(B) O(n)(C) O(m)(D) O(min(n，m)A首先取一个指针p指向la的第一个节点（不包括头节点，头节点是空），然后让la头指针指向lb的第二个节点，接着用lb的第一个节点填充lb的头节点，最后将la头节点next指向p如下图：还是不明白请自己看ppt第二章P652-12 设有6
12、个数据元素A，B，C，D，E，F依次进栈。如果6个数据元素的出栈顺序为B，C，D，F，E，A，则该栈的最小容量为( )。(A) 2(B) 3(C) 4(D) 5B操作栈内元素出栈顺序A，B入栈A,BB出栈ABC入栈A,CC出栈AB,CD入栈A,DD出栈AB,C,DE,F入栈A,E,FF出栈A,EB,C,D,FE出栈AB,C,D,F,EA出栈B,C,D,F,E,A因此栈的最小容量只需32-13 设进栈序列为123，试给出所有可能的出栈序列。所有可能的出栈序列为：1,2,3 （1入栈，1出栈，2入栈，2出栈，3入栈，3出栈） 1,3,2 （1入栈，1出栈，2,3,入栈，3出栈，2出栈）2,1,3 （1,2入栈，2出栈，1出栈，3入栈，3出栈）2,3,1 （1,2入栈，2出栈，3入栈，3出栈，1出栈）3,2,1 （1,2,3入栈，3出栈，2出栈，1出栈）注意：唯一只有3,1,2不可能出现，因为3要先出栈，前面1,2,3要按顺序一起入栈，因此不可能出现1在2的前面，后面的题目也是一样。原则就是只要后入栈的先出栈，那么这
