《厦门大学数据结构与算法(陈海山)期末习题集标准答案解析.doc》由会员分享，可在线阅读，更多相关《厦门大学数据结构与算法(陈海山)期末习题集标准答案解析.doc（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 Comple
3、xity)：算法占用机器资源的多少，主要有算法运行所需的机器时间和所占用的存储空间。时间复杂度(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=(ai
4、j)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(dou
5、ble 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(i
7、nt 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-ne
11、xt)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 设有
12、6个数据元素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
13、 （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的前面，后面的题目也是一样。原则就是只要后入栈的先出栈，那么这个元素前面入栈的元素一定按照入栈顺序的反序排列2-14 如果进栈序列为123456，能否得到出栈序列435612和135426?435612 不能得到 6的后面不可能出现1,2的出栈顺序135426 能够得到2-15 简述算法的功能(设数据元素类型为int)：void pr
14、oc(LinkQueue *Q)LinkStack S;InitStack(S);while(!EmptyQueue(Q) )DeleteQueue(Q, d);Push(S,d);while(!EmptyStack(S) )Pop(S, d);InsertQueue(Q, d);将链队列中的顺序倒过来如原来ABCDEF，执行完这个算法之后是FEDCBA2-16 按照格式要求给出调用F(3,A,B,C)的运行结果：void F(int n, char x, char y, char z)if (n=1) printf(1 %c %cn, x, z);elseF(n-1, x, z, y);pr
15、intf(%d %c %cn, n, x, z);F(n-1, y, x, z);自己去计算，类似汉诺塔1 A-C2 A-B1 C-B3 A-C1 B-A2 B-C1 A-C2-17 已知一维数组B0.20用于存储一个下三角矩阵A元素。设A中第一个元素的下标为1，1，则数组元素B10对应A中下标为( )的元素。(A) 2，5(B) 4，3(C) 5，1(D) 6，1C因此B中第10个元素，也就是B9对应A44B10对应A中是A512-18 已知Ann为稀疏矩阵。试从时间和空间角度比较，采用二维数组和三元组顺序表两种存储结构计算aij的优缺点。稀疏矩阵为n行n列.1) 采用二维数组存储，其空间复
16、杂度为(nn)；因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为(nn)。2) 采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为(t)。当tnn时，采用三元组顺序表存储可获得较好的时、空性能。2-19 链地址法是Hash表的一种处理冲突的方法，它是将所有哈希地址相同的数据元素都存放在同一个链表中。关于链地址法的叙述，不正确的是( )。(A) 平均查找长度较短 pptP165上面有表述(B) 相关查找算法易于实现 查找的时候只需找到哈希地址的那条链，再顺着那条链遍历下
17、去就可以实现。(C) 链表的个数不能少于数据元素的个数 可以少于，很明显(D) 更适合于构造表前无法确定表长的情况 链表的特点之一C2-20 设哈希(Hash)函数H(k)=(3k)%11，用线性探测再散列法处理冲突，di=i。已知为关键字序列22，41，53，46，30，13，01，67构造哈希表如下：哈希地址012345678910关键字2241300153461367则在等概率情况下查找成功时的平均查找长度是( )。(A) 2(B) 24/11(C) 3(D) 3.5有公式 ASL=1/2(1+1/(1-a) = 1/2(1+1/(1+11/3)=7/3 其中a = 8/11（实际填入的
18、数量/线性表的大小）2-21 有100个不同的关键字拟存放在哈希表L中。处理冲突的方法为线性探测再散列法，其平均查找长度为。试计算L的长度(一个素数)，要求在等概率情况下，查找成功时的平均查找长度不超过3。素数表：101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167。 设线性表L长度ln,有:=100/ln=125,即由题意选择127这个素数 习题3 树 3-1 若深度为5的完全二叉树第5层有3个叶子结点，则该二叉树一共有( )个结点。(A) 8(B) 13(C) 15(D) 18D利用公式 前四层有25-1
19、= 15个节点，总共为15+3=18个。3-2 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为( )。(A) 5(B) 6(C) 7(D) 8一共有1*4+2*2+3+4=15个度，4+2+1+1=8个节点叶子为15-8+1=8解析：节点数=度数+1此题也可用画图法（图略）3-3 已知二叉树T中有50个叶子结点，试计算T的总结点数的最小值。由于是二叉树，那么可知欲使节点数最小，则该二叉树需满足至多存在一个结点的入度为1（即使每两个结点都有一个父节点）。50/2=25, （25-1）/2=12 12/2=6 6/2=3 (3+1)/2=2 2/2=1 红色
20、部分+1为之前25个结点归根时剩下的1个。那么总共有50+25+12+6+3+2+1=99个结点节点数/2+1 =叶子数3-4 已知一棵度为k的树中，有n1个度为1的结点，n2个度为2的结点，nk个度为k的结点。试计算该树的叶子结点数。解析：节点数=度数+1叶子结点为10k0+-kkknmn3-5 对于任意非空二叉树，要设计出其后序遍历的非递归算法而不使用栈结构，最适合的方法是对该二叉树采用( )存储结构。(A) 二叉链表(B) 三叉链表 (C) 索引(D) 顺序B解析：三叉链表比二叉链表多一个指向父结点的指针3-6 一棵二叉树的叶子结点在其先序、中序和后序序列中的相对位置( )。(A) 肯定
21、发生变化(B) 可能发生变化(C) 不会发生变化(D) 无法确定B解析：举例子说明即可3-7 设二叉树T按照二叉链表存储，试分析下列递归算法的主要功能。int F(BiTree T)if (!T) return 0; if (!T-Lchild & !T-Rchild) return 1; return F(T-Lchild)+F(T-Rchild); 求二叉树T的叶子结点数int F(BiTree T)if (!T) return 0; if (!T-Lchild & !T-Rchild) return 1; return F(T-Lchild)+F(T-Rchild)+1; 求二叉树T的结
22、点数3-8 已知二叉树T的先序序列为ABCDEF，中序序列为CBAEDF, 则T的后序序列为( )。(A) CBEFDA(B) FEDCBA(C) CBEDFA(D) 不确定A3-9 简述由先序序列和中序序列构造二叉树的基本操作方法。1）取先序遍历序列的第一个值，用该值构造根结点，然后在中序遍历序列中查找与该元素相等的值，这样就可以把序列分为三部分：左子树（如果有）、根结点和右子树（如果有）。2）将两个序列都分成三部分，这样就分别形成了根结点的左子树和右子树的先序遍历和后序遍历的序列。3）重复1）和2）步骤，直至所有结点都处理完就可以完整构成一颗二叉树了。3-10 已知二叉树的先序序列为eba
23、dcfhgikj，中序序列为abcdefghijk，试画出该二叉树。ebfadhcgikj3-11 已知二叉树T的中序序列和后序序列分别为(中序) 3, 7, 11, 14, 18, 22, 27, 35(后序) 3, 11, 7, 14, 27, 35, 22, 18试画出二叉树T。181422735311273-12 已知二叉树T按照二叉链表存储，设计算法，计算T中叶子结点的数目。int F(BiTree T)if (!T) return 0; if (!T-Lchild & !T-Rchild) return 1; return F(T-Lchild)+F(T-Rchild); 3-13
24、 已知二叉树T按照二叉链表存储，设计算法，交换T的左子树和右子树。递归：Int ExchangeBTree(BiTree T) temp=(BiTree) malloc(sizeof(BiTNode); if(!T) return; if(!T-lchild&!T-rchild) return; temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; ExchangeBTree(T-lchild); ExchangeBTree(T-rchild);3-14 先序后继线索化算法是根据二叉链表建立先序后继线索二叉链表，其基本原则是在前驱空指针域中写入后继线
25、索，即将右子树的( )指针写入左子树的最后一个叶子结点右指针域。(A) 线索(B) 根结点(C) 前驱结点(D) 后继结点C3-15 设计算法，在先序线索二叉树中，查找给定结点p在先序序列中的后继。线索二叉树：根据某次遍历, 在二叉树中的相关空指针域都写入线索(后继线索或前驱线索)，即成为线索二叉树。线索二叉树可理解为已经线索化的二叉树。先序后继：先序遍历中得到的后继(先序前驱, 中序后继, 中序前驱, 后序后继, 后序前驱)。线索二叉树的存储结构typedef struct Node Type data；/数据元素域struct Node *Lchild；/左孩子域struct Node *
26、Rchild；/右孩子域int Tag；/0: 分支结点, 1: 叶子结点 BiTNode，*BiTree；findBirthNode(BiTNode p)If(p-tag=0)/p的左子树非空,指向左子树Return p-Lchild;Else /p为空，后驱则是右子树Return p-Rchild;3-16 设计一种二进制编码，使传送数据 a，act，case，cat，ease，sea，seat，state，tea的二进制编码长度最短。要求描述：(1)数据对象；a,c,t,s,e(2)权值集；8,3,5,5,6(3)哈夫曼树；略(4)哈夫曼编码。00,010,011,10,113-17 按
27、照“逐点插入方法”建立一个二叉排序树，树的形状取决于( )。(A) 数据序列的存储结构(B) 数据元素的输入次序(C) 序列中的数据元素的取值范围(D) 使用的计算机的软、硬件条件B显然D错误，A也错误因为大小是相对的，对于C，1，3,5 和1，10,100相对位置一样，假若插入次序也一样的话，树的形状也不会变得，所以选B3-18 用利用逐点插入法建立序列(50, 72, 43, 85, 75, 20, 35, 45, 65, 30)对应的二叉排序树以后，查找元素35要在元素间进行( )次比较。(A) 3(B) 4(C) 5(D) 8B1502437232045658543575303-19
28、在平衡二叉树中，插入关键字46后得到一颗新的平衡二叉树。在新的平衡二叉树中，关键字37所在结点的左、右孩子结点中保存的关键字是( )。(A) 18，46(B) 25，46(C) 25，53(D) 25，69 C3-20 用依次插入关键字的方法，为序列 5, 4, 2, 8, 6, 9 构造一棵平衡二叉树(要求分别画出构造过程中的各棵不平衡二叉树)。每次都将平衡树平衡3-21 给定n个整数，设计算法实现：(1) 构造一棵二叉排序树；(2) 从小到大输出这n个数。 int SearchBST(BiTree T, int key, BiTree &p)/在T中递归查找关键字值=key的数据元素if
29、(!T) return 0; /查找不成功if (key=T-key) return 1; /查找成功p=T; /p记录双亲结点if (keykey) return SearchBST(T-lchild, key, p);return SearchBST(T-rchild, key, p); /SearchBST/ 二叉排序树的插入算法void InsertBST(BiTree &T, int an) /数组保存n个整数BiTree p=T; /p指向双亲结点Int i;For(i=0;ilchild, ai, p) return 0; /查找成功BiTree s=(BiTree) mallo
30、c(sizeof (BiTnode); /申请结点s-key=ai;s-lchild=s-rchild=NULL;if (!T-lchild) T-lchild=s; /s为根结点else if (aikey) p-lchild=s; /s为p的左孩子else p-rchild=s; /s为p的右孩子 /InsertBST /用中序遍历即可从大到小输出习题4 排序4-1 在下列排序算法中，时间复杂度最好的是( )。(A) 堆排序(B) 插入排序(C) 冒泡排序(D) 选择排序A4-2 如果顺序表中的大部分数据元素按关键字值递增有序，则采用( )算法进行升序排序，比较次数最少。(A) 快速排序(
31、B) 归并排序(C) 选择排序(D) 插入排序D4-3 对关键字序列 56, 23, 78, 92, 88, 67, 19, 34 进行增量为3的一趟希尔排序(Shell升序或降序)的结果为( )。(A) 19, 23, 78, 56, 34, 67, 92, 88(B) 23, 56, 78, 67, 88, 92, 19, 34(C) 19, 23, 34, 56, 67, 78, 88, 92(D) 92, 88, 78, 56, 34, 67, 19, 23D4-4 若一组记录的关键码为46, 79, 56, 38, 40, 84，则利用快速排序方法且以第一个记录为基准，得到的一次划分
32、结果为( )。(A) 38，40，46，56，79，84(B) 40，38，46，79，56，84(C) 40，38，46，56，79，84(D) 40，38，46，84，56，79C4-5 对数据84，47，25，15，21进行排序。如果前三趟的排序结果如下：第1趟：15，47，25，84，21第2趟：15，21，25，84，47第3趟：15，21，25，47，84则采用的排序方法是( )。(A) 冒泡排序(B) 快速排序(C) 选择排序(D) 插入排序C4-6 对数据36，12，57，86，9，25进行排序，如果前三趟的排序结果如下：第1趟：12，36，57，9，25，86第2趟：12，3
33、6，9，25，57，86第3趟：12，9，25，36，57，86则采用的排序方法是( )。(A) 希尔排序(B) 起泡排序(C) 归并排序(D) 基数排序B4-7 根据建堆算法，将关键字序列5，7，10，8，6，4调整成一个大顶堆，最少的交换次数为( )。(A) 1(B) 2(C) 3(D) 4B4-8 在链式基数排序中，对关键字序列369, 367, 167, 239, 237, 138, 230, 139进行第1趟分配和收集后，得到的结果是( )。(A) 167, 138, 139, 239, 237, 230, 369, 367(B) 239, 237, 138, 230, 139, 3
34、69, 367, 167(C) 230, 367, 167, 237, 138, 369, 239, 139(D) 138, 139, 167, 230, 237, 239, 367, 369C4-9 设int r7=5，2，6，4，1，7，3; 则执行for ( i=0; i1)/一趟没有交换记录就弹出i=1;for(j=1;jgetNameSize(Name,j+1)NamejNamej+1;/交换i=j;n=i;/计算每个部门名称的大小int getNameSize(RecordType *Name,int j)int sum=0;for(k=0;k=30;k+)sum = sum +
35、Namejk;return sum;4-15 设计基于顺序表存储结构的树形选择排序算法。/基于顺序表存储结构的完全二叉树的选择排序void Sorting(int L,int n)for (int i=1; i0; k/=2)if (k%2) j=Lk-1;else j=Lk+1;if (jLk) Lk/2=j;else Lk/2=Lk;/Sorting4-16 假设采用链表存储类型：typedef struct RNodeint key; /数据域(也是关键字域) struct RNode *next; /指针域 RNode, *RList; typedef RList RN; /链表类型,
36、 常变量Nn又设R1.n是10, 999之间的随机整数。试设计一个链表基数排序算法，将Rn中的数从小到大排序。排序结果仍存放在Rn中。 习题5 图 5-1 设某个非连通无向图有25条边，问该图至少有( )个顶点。(A) 7(B) 8(C) 9(D) 10 C5-2 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为( )。(A) O(n+e)(B) O(n2)(C) O(ne)(D) O(n3) A5-3 带权有向图G用邻接矩阵R存储，则顶点i的入度等于R中( )。(A) 第i行非(或非0)的元素之和(B) 第i列非(或非0)的元素之和(C) 第i行非(或非0)的元素个数(D) 第i列非(或非0)的元素个数D邻接矩阵 横坐标 头 纵坐标 尾5-4 在关于图的遍历描述中，不正确的是( )。(A) 图的深度优先搜索遍历不适用于有向图(B) 图的深度优先搜索遍历是一个递归过程(C) 图的遍历是从给定的源点出发访问图中每一个顶点一次(D) 遍历的基本算法有两种：深度优先搜索遍历和广度优先搜索遍历A5-5 设计算法，由依次输入的顶点数目、狐的数目、各个顶点元素信息和各条狐信息建立有向图的邻接表。5-6 请给出有向图的(1) 每个顶点的入度和出度；(2) 邻接矩阵；