厦门大学数据结构与算法(陈海山)期末习题答案解析

请将答案按序写在学校统一印制的专用答题卷上，写在本卷或自备纸上者一律不得分。

一．单项选择题(本题含25个小题，每个小题2分，计50分)二．综合应用题(含5个小题，每小题10分，计50分)1．设LinkList是链表存储结构，试分析下列算法的时间复杂度，并简述程序的主要功能。

void CrList( LinkList &L, int n ){LinkList p, q=L;for ( i =0; i<n; ++i ){p=( LinkList ) malloc( sizeof( int ) );q->next=p;p->data=rand( ); // rand( )：产生一个随机整数q=p;}p->next=NULL;} // 算法结束[参考答案]该算法的时间复杂度主要由for ( i = 0；i < n；++ i )命令决定(即主要由链表长度决定)，因此算法的时间复杂度为O(n)。

程序的主要功能：创建一个含有n个结点的线性链表L，其中数据元素由随机函数产生。

2．画出与下列两个已知遍历序列对应的一颗二叉树：先序遍历序列：A B G E K C F H J D中序遍历序列：G B K E A H F J C D[参考答案]3．已知无向图如下，试绘制一棵从A 点开始的广度优先生成树。

[参考答案]从A 点开始的一棵广度优先生成树如下(六种情况之一)： A →B →C →D 时：A →C →D →B 时：A →D →B →C 时：A →B →D →C 时：A →C →B →D 时：A →D →C →B 时：4．已知关键字集={ 19，23，55，11，30，47，28，38，15，51，42 }，表长m=7，哈希函数H(key)=key%7+1。

试给出由链表地址法产生的哈希地址和哈希链表示意图。

[参考答案]由链表地址法产生的哈希地址是：6，3，7，5，3，6，1，4，2，3，1哈希链表示意图如下：5．设n个整数存放在数组a中。

数据结构与算法设计课后习题及答案详解1. 习题一：数组求和题目描述：给定一个整数数组，编写一个函数来计算它的所有元素之和。

解题思路：遍历数组，将每个元素累加到一个变量中，最后返回累加和。

代码实现：```pythondef sum_array(arr):result = 0for num in arr:result += numreturn result```2. 习题二：链表反转题目描述：给定一个单链表，反转它的节点顺序。

解题思路：采用三指针法，依次将当前节点的下一个节点指向上一个节点，然后更新三个指针的位置，直到链表反转完毕。

代码实现：```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev```3. 习题三：二叉树的层序遍历题目描述：给定一个二叉树，返回其节点值的层序遍历结果。

解题思路：采用队列来实现层序遍历，先将根节点入队，然后循环出队并访问出队节点的值，同时将出队节点的左右子节点入队。

代码实现：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None): self.val = valself.left = leftself.right = rightdef level_order(root):if not root:return []result = []queue = [root]while queue:level = []for _ in range(len(queue)):node = queue.pop(0)level.append(node.val)if node.left:queue.append(node.left)queue.append(node.right)result.append(level)return result```4. 习题四：堆排序题目描述：给定一个无序数组，使用堆排序算法对其进行排序。

单选题（每题 2 分，共20分）1. 对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 36. 若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。

A．值B．函数C．指针D．引用8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A ）。

A．行号B．列号C．元素值D．非零元素个数10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为(C )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题6 分，共24分）1. 数据结构是指数据及其相互之间的_联系。

当结点之间存在M对N（M：N）的联系时，称这种结构为__图__。

2. 队列的插入操作是在队列的___尾_进行，删除操作是在队列的_首_进行。

3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。

4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___ O（1）__，在表尾插入元素的时间复杂度为___ O（n）___。

作业：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) 在计算机中实现对数据元素的操作(D) 数据元素及其关系在计算机中的表示选D数据的逻辑结构、数据的存储结构、数据的运算1-4 算法包括哪五种特性?2. 算法的五大特性：√⑴输入：一个算法有零个或多个输入。

⑵输出：一个算法有一个或多个输出。

⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。

⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

1-5 简述算法及其时间复杂度。

1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。

算法复杂度(Algorithm Complexity)：算法占用机器资源的多少，主要有算法运行所需的机器时间和所占用的存储空间。

时间复杂度(Time Complexity)：算法运行所需要的执行时间，T(n)= O(f(n))。

空间复杂度(Space Complexity)：算法运行所需要的存储空间度量，S(n)= O(f(n))。

1-6 设数组A中只存放正数和负数。

试设计算法，将A中的负数调整到前半区间，正数调整到后半区间。

分析算法的时间复杂度。

A[n+1]For(int i=n-1,j=0;i>j;i--){If(a[i]>0) continue;Else {A[n]=A[i];A[i]=A[j];A[j]=A[n];J++;}}时间复杂度为O(n)1-7 将上三角矩阵A=(aij)n n 的非0元素逐行存于B[(n*(n+1)/2]中，使得B[k]=aij 且k=f1(i)+f2(j)+c (f1, f2不含常数项)，试推导函数f1, f2和常数c。

第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。

第一章1.数据结构研究的主要内容包括逻辑结构、存储结构和算法。

2.数据元素是数据的基本单位，数据项是数据的最小标示单位。

3.根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、树形、线性、图状。

4.常见的数据存储结构有四种类型：顺序、链式、索引、散列。

5.可以从正确性、可读性、健壮性、高效性四方面评价算法的质量。

6.在一般情况下，一个算法的时间复杂度是问题规模的函数。

7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log2 n）、平方阶O（n²）和指数阶O（2ⁿ）。

通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。

8.时间复杂度排序由大到小（n+2）！>2ⁿ＋²>（n+2）4次方>nlog2 n>100000.问答题：1.什么叫数据元素？数据元素是数据的基本单位，是数据这个集合的个体，也称为元素、结点、顶点、记录。

2.什么叫数据逻辑结构？什么叫数据存储结构？数据逻辑结构：指数据元素之间存在的固有的逻辑结构。

数据存储结构：数据元素及其关系在计算机内的表示。

3.什么叫抽象数据类型？抽象数据类型是指数据元素集合以及定义在该集合上的一组操作。

4.数据元素之间的关系在计算机中有几种表示方法？顺序、链式、索引、散列。

5.数据的逻辑结构与数据的存储结构之间存在着怎样的关系？相辅相成，不可分割。

6.什么叫算法？算法的性质有哪些？算法：求解问题的一系列步骤的集合。

可行性、有容性、确定性、有输入、有输出。

7.评价一个算法的好坏应该从哪几方面入手？正确性、可读性、健壮性、高效性。

第二章1.线性表中，第一个元素没有直接前驱，最后一个元素没有直接后继。

2.线性表常用的两种存储结构分别是顺序存储结构和链式存储结构。

3.在长度为n的顺序表中，插入一个新元素平均需要移动表中的n/2个元素，删除一个元素平均需要移动（n-1）/2个元素。

4.在长度为n的顺序表的表头插入一个新元素的时间复杂度为O（n），在表尾插入一个新元素的时间复杂度为O（1）。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．部结构和外部结构（2）与数据元素本身的形式、容、相对位置、个数无关的是数据的（）。

A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。

A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

2.3 课后习题解答2.3.2 判断题1．线性表的逻辑顺序与存储顺序总是一致的。

（×）2．顺序存储的线性表可以按序号随机存取。

（√）3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

（×）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。

（√）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。

（×）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

（√）7．线性表的链式存储结构优于顺序存储结构。

（×）8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。

（√）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

（×）11．静态链表既有顺序存储的优点，又有动态链表的优点。

所以它存取表中第i个元素的时间与i无关。

（×）12．线性表的特点是每个元素都有一个前驱和一个后继。

（×）2.3.3 算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。

试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。

int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/else {i=*elenum;while (i>=0 && A[i]>x) /*边找位置边移动*/{A[i+1]=A[i];i--;}A[i+1]=x; /*找到的位置是插入位的下一位*/(*elenum)++;return 1; /*插入成功*/}}时间复杂度为O(n)。

1. 数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。

2 何谓算法?它与程序有何区别?算法是解决某一特定类型问题的有限运算序列。

程序＝数据结构＋算法3. 算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和占据空间的大小。

4. 何谓频度、时间复杂度、空间复杂度？说明其含义。

算法中语句的重复次数称为该语句的频度。

时间复杂度是算法执行所需要的时间，也就是算法中每一个语句的执行次数乘以每一次执行所需的时间的总和。

空间复杂度是算法对空间占用的量度。

（一般在考虑空间复杂度时，只估算算法所需增添的辅助空间，而对问题中原始数据所占的空间，由于与算法无关，不予考虑。

）5. 时间复杂度的计算：语句2的频度为n-l，语句4的额度为(n-1)(2n+1)＝2n2-n-l，因此时间复杂度T(n)＝O(n2)。

语句3的频度为n，语句7的频度为n2，因此时间复杂度为T(n)＝O(n2)。

【解】语句3的频度不仅与n有关，而且和x及数组A中各分量的值有关。

这时通常考虑最坏的情况，由于while循环的最大次数为n-1，因此时间复杂度为T(n)＝O(n)。

i=1;while(i<=n)i=i*5;【解】设语句“i=i*5;”的频度为x，则5x<=n，x<=log5n，O(log5n)i=0;s=0;while(s<n){i++; s+=i;}【解】i=1,s=1i=2,s=1+2i=3,s=1+2+3,s就是对等差数列求和，因此s=i(i+1)/2<n，其中i就是循环语句的频度，因此O(n)6. 在一个具有n个结点的有序单链表中插入一个新结点，使得链表仍然有序，该算法的时间复杂度是( )A.O(log2n)B.O(1)C.O(n2)D.O(n)(D)7. 如果某线性表中最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。

A.单链表B.双向链表C.单循环链表D.顺序表（D）8. 写出带头结点的双向循环链表L为空表的条件（假设结点包括data, next, prior三个域）：(L==L->Next) && (L==L->Prior)注：L->Next==L->Prior不行，因为表长为1时该条件也成立。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．部结构和外部结构（2）与数据元素本身的形式、容、相对位置、个数无关的是数据的（）。

A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。

A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。