最新算法与数据结构C语言习题参考答案1-5章讲解学习

国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

数据结构(c语言版)课后习题答案完整版数据结构(C语言版)课后习题答案完整版一、数据结构概述数据结构是计算机科学中一个重要的概念，用来组织和存储数据，使之可以高效地访问和操作。

在C语言中，我们可以使用不同的数据结构来解决各种问题。

本文将提供完整版本的C语言数据结构的课后习题答案。

二、顺序表1. 顺序表的定义和基本操作顺序表是一种线性表，其中的元素在物理内存中连续地存储。

在C 语言中，我们可以通过定义结构体和使用指针来实现顺序表。

以下是顺序表的一些基本操作的答案：（1）初始化顺序表```ctypedef struct{int data[MAX_SIZE];int length;} SeqList;void InitList(SeqList *L){L->length = 0;}```（2）插入元素到顺序表中```cbool Insert(SeqList *L, int pos, int elem){if(L->length == MAX_SIZE){return false; // 顺序表已满}if(pos < 1 || pos > L->length + 1){return false; // 位置不合法}for(int i = L->length; i >= pos; i--){L->data[i] = L->data[i-1]; // 向后移动元素 }L->data[pos-1] = elem;L->length++;return true;}```（3）删除顺序表中的元素```cbool Delete(SeqList *L, int pos){if(pos < 1 || pos > L->length){return false; // 位置不合法}for(int i = pos; i < L->length; i++){L->data[i-1] = L->data[i]; // 向前移动元素 }L->length--;return true;}```（4）查找顺序表中的元素```cint Search(SeqList L, int elem){for(int i = 0; i < L.length; i++){if(L.data[i] == elem){return i + 1; // 找到元素，返回位置 }}return -1; // 未找到元素}```2. 顺序表习题解答（1）逆置顺序表```cvoid Reverse(SeqList *L){for(int i = 0; i < L->length / 2; i++){int temp = L->data[i];L->data[i] = L->data[L->length - 1 - i]; L->data[L->length - 1 - i] = temp;}}```（2）顺序表元素去重```cvoid RemoveDuplicates(SeqList *L){for(int i = 0; i < L->length; i++){for(int j = i + 1; j < L->length; j++){if(L->data[i] == L->data[j]){Delete(L, j + 1);j--;}}}}```三、链表1. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。

阅读使人充实，会谈使人敏捷，写作使人精确。

——培根1.绪论1．将下列复杂度由小到大重新排序：n5D．10 000 E．n*logn!C．n(nA．2)B．25n < nn! < 2 n【答】10 000< *log(n)< 22．将下列复杂度由小到大重新排序：2340.5．n C．2D．n*log(n)B．n + nn + A240.523 n + n + n*log(n【答】2) < < nn< 23．用大“O”表示法描述下列复杂度：5/22/5B．6*log(A．5n + nn) + 9n 223/24+ n* log(n)+ n C．3n D．5n 2425/2)【答】O (nn)C ：O (n)DO (n)：B：O (A：4．按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n , n2/3。

又n！应排在第几位？2/3 2n。

n , n , 3, 20n , 4n【答】按照增长率从低到高依次为：2000, log, logn23n！的增长率比它们中的每一个都要大，应排在最后一位。

5. 计算下列程序片断的时间代价：int i=1;while(i<=n){printf(“i=%d\n”,i);i=i+1;}【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。

所以该程序段总的时间代价为：T(n) = 1 + n + 2n = 3n+ 1 = O(n)6. 计算下列程序片断的时间代价：int i=1;while(i<=n){int j=1;while(j<=n){int k=1;法拉兹·日·阿卜——学问是异常珍贵的东西，从任何源泉吸收都不可耻。

．阅读使人充实，会谈使人敏捷，写作使人精确。

1-5章数据结构作业答案一、设n为整数，利用大“O”记号，求下列程序段的时间复杂度1、i=0;k=0;Do{ k=k*10*i; i++;} while (i<n);// T(n)=O(n)2、i=1; j=0;while(i+j<=n){ if(i>j) j++;else i++;}// T(n)=O(n)3、x=n; //n>1while (x>=(y+1)*(y+1))y++;// T(n)=O(n)4、x=91; y=100;while (y>0)if (x>100) {x=x-10; y- -;}else x++;// T(n)=常数=O(1)二、选择题1、从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（ D ）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串3、在下面的程序段中，对x的赋值语句的频度为（ C ）for (i=1;i<=n;i++)for (j=1;j<=n;j++)x=x+1;n) A． O(2n) B．O(n) C．O(n2) D．O(log24、下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6、静态链表中指针表示的是（ B ）.A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址7、下面的叙述不正确的是（ B、C ）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 0第2章线性表 (4)第3章栈和队列 (12)第4章串、数组和广义表 (25)第5章树和二叉树 (31)第6章图 (39)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

序列。

对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。

学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。

这些学生记录在计算机中的存储表示就是存储结构。

如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。

即相同的逻辑结构，可以对应不同的存储结构。

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

答案：（1）集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。

例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。

（2）线性结构数据元素之间存在一对一的关系。

例如，将学生信息数据按照其入学报到的时间先后顺A．存储结构 B．存储实现C．逻辑结构 D．运算实现答案：C（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

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

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构答案：O(m*n)解释：语句a[i][j]=0;的执行次数为m*n。

（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;答案：O(n2)解释：语句s+=B[i][j];的执行次数为n2。

数据结构(C语言版)习题参考答案数据结构(C语言版)习题参考答案1. 数据结构简介数据结构是计算机科学中重要的概念之一，它关注如何组织和存储数据，以便有效地进行访问和操作。

C语言是一种广泛应用于数据结构实现的编程语言。

本文将提供一些常见数据结构习题的参考答案，帮助读者理解和掌握数据结构的基本概念与实现。

2. 数组数组是一种线性结构，存储具有相同数据类型的元素。

以下是一些数组习题的参考答案：2.1 统计数组中某个元素出现的次数```int countOccurrences(int arr[], int n, int x) {int count = 0;for (int i = 0; i < n; i++) {if (arr[i] == x) {count++;}}return count;}```2.2 查找数组中的最大值和最小值```void findMinMax(int arr[], int n, int* min, int* max) { *min = arr[0];*max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] < *min) {*min = arr[i];}if (arr[i] > *max) {*max = arr[i];}}}```3. 链表链表是一种动态数据结构，每个节点包含数据和指向下一个节点的指针。

以下是一些链表习题的参考答案：3.1 反转链表```Node* reverseLinkedList(Node* head) {Node* prev = NULL;Node* curr = head;while (curr != NULL) {Node* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}```3.2 合并两个有序链表```Node* mergeLists(Node* list1, Node* list2) {if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}if (list1->data < list2->data) {list1->next = mergeLists(list1->next, list2);return list1;} else {list2->next = mergeLists(list1, list2->next);return list2;}}```4. 栈和队列栈和队列是两种重要的线性数据结构，栈支持后进先出（LIFO），队列支持先进先出（FIFO）。

附录习题参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。

数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。

数据类型：是指变量的取值范围和所能够进行的操作的总和。

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<=n;i++)scanf(“%f ”,&a[i]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。

国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

数据结构（C语言版）清华大学出版社课后题1-5章答案第一章选择题1.A2.B3.C4.D5.B6.C第二章选择题1.A2.D3.D4.C5.A6.C7.B8.B9.D 10.D应用题1．应该选用链接存储表示。

如果才用顺序表示法，必须在一个连续的可用空间中为这N 个表分配空间。

初始时候因为不知道哪个表增长得快，必须平均分配空间。

在程序运行过程中，有的表占用的空间增长得快，有的表占用空间增长得慢，有的表很快就使用完了分配给它的空间，有的表才占用了少许空间，在进行元素的插入时候就必须成片的移动其他表的空间，以空出位置进行插入；在元素删除时为填补空白，也可能移动许多元素。

这个处理过程及其繁琐和低效。

如果采用链接存储，一个表的空间可以连续也可以不连续。

表的增长通过动态分配内存得以解决，只要存储器未满，就不会发生表溢出；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储需求，非常灵活方便。

对于N个表（包括表的总数可能变化）共存的情形，处理十分简单快捷，插入、删除时间复杂度为O（1）。

所以才用链接存储表示较好。

2．一般来说，链式存储结构克服了顺序存储结构的三个缺点。

首先，插入、删除操作不需要移动元素，只修改指针；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受到内存空间的限制。

其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

3.顺序结构时ai与ai+1的物理位置相邻，链表结构时两者的位置不要求一定相邻。

7.在顺序表中插入和删除一个节点需平均移动全表一半的节点。

具体的移动次数取决于所插入和删除的节点的位置i和全表的长度n这两个因素。

算法设计题1.分析：遍历整个顺序表，用k记录在x~y之间元素的个数，k的初始值为0。

对于当前遍历到的元素，若其值在x~y之间，则前移k个位置；否则执行++k。

这样每个不在x~y之间的元素仅仅移动一次，所以效率较高。

绪论1．将下列复杂度由小到大重新排序：A．2n B．n! C．n5D．10 000 E．n*log2 (n)【答】10 000< n*log2(n)< n5< 2n < n!2．将下列复杂度由小到大重新排序：A．n*log2(n) B．n + n2 + n3C．24D．n0.5【答】24< n0.5< n*log2 (n) < n + n2 + n33．用大“O”表示法描述下列复杂度：A．5n5/2 + n2/5 B．6*log2(n) + 9nC．3n4+ n* log2(n) D．5n2 + n3/2【答】A：O (n5/2) B：O (n) C：O (n4) D：O (n2)4．按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n , n2/3。

又n！应排在第几位？【答】按照增长率从低到高依次为：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。

n！的增长率比它们中的每一个都要大，应排在最后一位。

5. 计算下列程序片断的时间代价：int i=1;while(i<=n){printf(“i=%d\n”,i);i=i+1;}【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。

所以该程序段总的时间代价为：T(n) = 1 + n + 2n = 3n+ 1 = O(n)6. 计算下列程序片断的时间代价：int i=1;while(i<=n){int j=1;while(j<=n){int k=1;while(k<=n){printf(“i=%d,j=%d,k=%d\n”,I,j,k);k=k+1;}j=j+1;}i=i+1;}【答】循环控制变量i从1增加到n，最外层循环体执行n次，循环控制变量j从1增加到n，中间层循环体执行n次，循环控制变量k从1增加到n，最内层循环体执行n次，所以该程序段总的时间代价为：T(n) = 1 + n + n｛1 + n + n[1 + n + 2n +1] +1 +1｝+ 1= 3n3 + 3n2 +4n +2= O(n3)2. 线性表1.试写一个插入算法int insertPost_seq(palist, p, x )，在palist所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。

抽出时间去学习，凡事从小做起，不怕单调和重复，长期的积累坚持，想不成功，也难。

第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()第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是（）A．110 B．108 C．100 D．120 （2）在n个结点的顺序表中算法的时间复杂度是O(1)的操作是（）A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动的元素个数为（）A．8 B．63.5 C．63 D．7（4）链接存储的存储结构所占存储空间（）A．分两部分一部分存放结点值另一部分存放表示结点间关系的指针B．只有一部分存放结点值C．只有一部分存储表示结点间关系的指针D．分两部分一部分存放结点值另一部分存放结点所占单元数（5）线性表若采用链式存储结构时要求内存中可用存储单元的地址（）A．必须是连续的 B．部分地址必须是连续的C．一定是不连续的 D．连续或不连续都可以（6）线性表Ｌ在（）情况下适用于使用链式结构实现A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂（7）单链表的存储密度（）A．大于1 B．等于1 C．小于1 D．不能确定（8）将两个各有n个元素的有序表归并成一个有序表其最少的比较次数是（）A．n B．2n-1 C．2n D．n-1（9）在一个长度为n的顺序表中在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素A．n-i B．n-i+1 C．n-i-1 D．i(10) 线性表L=(a1a2......an)下列说法正确的是（）A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少有一个元素C．表中诸元素的排列必须是由小到大或由大到小D．除第一个和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继(11) 若指定有n个元素的向量则建立一个有序单链表的时间复杂性的量级是（）A．O(1) B．O(n) C．O(n2) D．O(nlog2n)(12) 以下说法错误的是（）A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B．顺序存储的线性表可以随机存取C．由于顺序存储要求连续的存储区域所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构(13) 在单链表中要将s所指结点插入到p所指结点之后其语句应为（）A．s->next=p+1; p->next=s;B．(*p).next=s; (*s).next=(*p).next;C．s->next=p->next; p->next=s->next;D．s->next=p->next; p->next=s;(14) 在双向链表存储结构中删除p所指的结点时须修改指针（）A．p->next->prior=p->prior; p->prior->next=p->next;B．p->next=p->next->next; p->next->prior=p;C．p->prior->next=p; p->prior=p->prior->prior;D．p->prior=p->next->next; p->next=p->prior->prior;(15) 在双向循环链表中在p指针所指的结点后插入q所指向的新结点其修改指针的操作是（）A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表要求结果链表仍使用原来两个链表的存储空间不另外占用其它的存储空间表中不允许有重复的数据void MergeList_L(LinkList &LaLinkList &LbLinkList &Lc){pa=La->next; pb=Lb->next;Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){if(pa->data<pb->data){ pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} else {// 相等时取La的元素删除Lb的元素pc->next=pa;pc=pa;pa=pa->next;q=pb->next;delete pb ;pb =q;}}pc->next=pa?pa:pb; //插入剩余段delete Lb; //释放Lb的头结点}（2）将两个非递减的有序链表合并为一个非递增的有序链表要求结果链表仍使用原来两个链表的存储空间不另外占用其它的存储空间表中允许有重复的数据void union(LinkList& LaLinkList& LbLinkList& Lc) {pa = La->next; pb = Lb->next; // 初始化Lc=pc=La; //用La的头结点作为Lc的头结点Lc->next = NULL;while ( pa || pb ) {if ( !pa ) { q = pb; pb = pb->next; }else if ( !pb ) { q = pa; pa = pa->next; }else if (pa->data <= pb->data ) { q = pa; pa = pa->next; } else { q = pb; pb = pb->next; }q->next = Lc->next; Lc->next = q; // 插入}delete Lb; //释放Lb的头结点}（3）已知两个链表A和B分别表示两个集合其元素递增排列请设计算法求出A与B的交集并存放于A链表中void Mix(LinkList& LaLinkList& LbLinkList& Lc) {pa=la->next;pb=lb->next;∥设工作指针pa和pb；Lc=pc=La; //用La的头结点作为Lc的头结点while(pa&&pb)if(pa->data==pb->data)∥交集并入结果表中{ pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next; delete u;}else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;}while(pa){ u=pa; pa=pa->next; delete u;}∥释放结点空间while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间pc->next=null;∥置链表尾标记delete Lb; ∥注：本算法中也可对B表不作释放空间的处理（4）已知两个链表A和B分别表示两个集合其元素递增排列请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合）并以同样的形式存储同时返回该集合的元素个数void Difference（LinkedList AB*n）∥A和B均是带头结点的递增有序的单链表分别存储了一个集合本算法求两集合的差集存储于单链表A中*n是结果集合中元素个数调用时为0{p=A->next；∥p和q分别是链表A和B的工作指针q=B->next； pre=A；∥pre为A中p所指结点的前驱结点的指针while（p!=null && q!=null）if（p->data<q->data）{pre=p；p=p->next；*n++；} ∥ A链表中当前结点指针后移else if（p->data>q->data）q=q->next；∥B链表中当前结点指针后移else {pre->next=p->next；∥处理AB中元素值相同的结点应删除u=p； p=p->next； delete u；} ∥删除结点（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C其中B表的结点为A表中值小于零的结点而C表的结点为A表中值大于零的结点（链表A的元素类型为整型要求B、C表利用A表的结点）（6）设计一个算法通过一趟遍历在单链表中确定值最大的结点ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; //假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;（7）设计一个算法通过遍历一趟将链表中所有结点的链接方向逆转仍利用原表的存储空间void inverse(LinkList &L) {// 逆置带头结点的单链表 Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q指向*p的后继p->next=L->next;L->next=p; // *p插入在头结点之后p = q;}}（8）设计一个算法删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数其值可以和表中的元素相同也可以不同）void delete(LinkList &Lint minkint maxk) {p=L->next; //首元结点while (p && p->data<=mink){ pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) {while (p && p->data<maxk) p=p->next;// 查找第一个值≥maxk 的结点q=pre->next; pre->next=p; // 修改指针while (q!=p){ s=q->next; delete q; q=s; } // 释放结点空间 }//if}（9）已知p指向双向循环链表中的一个结点其结点结构为data、prior、next三个域写出算法change(p)交换p所指向的结点和它的前缀结点的顺序知道双向循环链表中的一个结点与前驱交换涉及到四个结点（p结点前驱结点前驱的前驱结点后继结点）六条链void Exchange（LinkedList p）∥p是双向循环链表中的一个结点本算法将p所指结点与其前驱结点交换{q=p->llink；q->llink->rlink=p；∥p的前驱的前驱之后继为pp->llink=q->llink；∥p的前驱指向其前驱的前驱q->rlink=p->rlink；∥p的前驱的后继为p的后继q->llink=p；∥p与其前驱交换p->rlink->llink=q；∥p的后继的前驱指向原p的前驱p->rlink=q；∥p的后继指向其原来的前驱}∥算法exchange结束（10）已知长度为n的线性表A采用顺序存储结构请写一时间复杂度为O(n)、空间复杂度为O(1)的算法该算法删除线性表中所有值为item的数据元素[题目分析] 在顺序存储的线性表上删除元素通常要涉及到一系列元素的移动（删第i个元素第i+1至第n个元素要依次前移）本题要求删除线性表中所有值为item的数据元素并未要求元素间的相对位置不变因此可以考虑设头尾两个指针（i=1j=n）从两端向中间移动凡遇到值item的数据元素时直接将右端元素左移至值为item的数据元素位置void Delete（ElemType A[ ]int n）∥A是有n个元素的一维数组本算法删除A中所有值为item的元素{i=1；j=n；∥设置数组低、高端指针（下标）while（i<j）{while（i<j && A[i]!=item）i++；∥若值不为item左移指针if（i<j）while（i<j && A[j]==item）j--；∥若右端元素值为item 指针左移if（i<j）A[i++]=A[j--]；}[算法讨论] 因元素只扫描一趟算法时间复杂度为O（n）删除元素未使用其它辅助空间最后线性表中的元素个数是j。

数据结构课后习题参考答案第一章绪论1.3 (1) O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/2)(5)(5)执行程序段的过程中，x,y值变化如下：循环次数x y0（初始）91 1001 92 1002 93 100………………9 100 10010 101 10011 91 9912 92 100………………20 101 9921 91 98………………30 101 9831 91 97到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.5 2100 , (2/3)n , log2n , n1/2 ,n3/2, (3/2)n , n log2n , 2 n ,n! , n n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define MAXSIZE 1024typedef int ElemType;// 实际上，ElemType可以是任意类型typedef struct{ ElemType data[MAXSIZE];int last; // last表示终端结点在向量中的位置}sequenlist;（2）链式存储结构（单链表）typedef struct node{ElemType data;struct node *next；}linklist;（3）链式存储结构（双链表）typedef struct node{ElemType data;struct node *prior,*next；}dlinklist;（4）静态链表typedef struct{ElemType data;int next;}node;node sa[MAXSIZE];2.1 头指针：指向链表的指针。

因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。

如：链表的头指针是la，往往简称为“链表la”。

国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

第一章绪论习题练习答案简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

●数据：指能够被计算机识别、存储和加工处置的信息载体。

●数据元素：就是数据的大体单位，在某些情况下，数据元素也称为元素、结点、极点、记录。

数据元素有时可以由若干数据项组成。

课后答案网数据类型：是一个值的集合和在这些值上概念的一组操作的总称。

通常数据类型可以看做是程序设计语言中已实现的数据结构。

●数据结构：指的是数据之间的彼此关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

●逻辑结构：指数据元素之间的逻辑关系。

●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.●线性结构：数据逻辑结构中的一类。

它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，而且所有结点都有且只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

栈、队列、串等都是线性结构。

●非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

答：例如有一张学生体检情况记录表，记录了一个班的学生的身高、体重等各项体检信息。

这张记录表中，每一个学生的各项体检信息排在一行上。

这个表就是一个数据结构。

每一个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来讲，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。

这几个关系就肯定了这个表的逻辑结构是线性结构。

这个表中的数据如何存储到计算机里，而且如何表示数据元素之间的关系呢? 即用一片持续的内存单元来寄存这些记录(如用数组表示)仍是随机寄存各结点数据再用指针进行链接呢? 这就是存储结构的问题。

算法与数据结构C语言版课后习题答案（机械工业出版社）第1章-绪论-习题参考答案第1章概论习题参考答案一、基础知识题1.简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。

【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素是数据的基本单位。

在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。

数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。

每一种计算机程序设计语言都定义有自己的数据类型。

“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。

作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。

而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。

数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。

数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。

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

是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。

逻辑结构与计算机无关。

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

其中每一条指令表示一个或多个操作。

一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。

2.数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。

（也可以分为集合、线性结构、树形结构和图形即网状结构）。

逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。

数据结构c语言版课后习题答案数据结构是计算机科学中的一个重要概念，它涉及到组织、管理和存储数据的方式，以便可以有效地访问和修改数据。

C语言是一种广泛使用的编程语言，它提供了丰富的数据结构实现方式。

对于学习数据结构的C语言版课程，课后习题是巩固理论知识和提高实践能力的重要手段。

数据结构C语言版课后习题答案1. 单链表的实现在C语言中，单链表是一种常见的线性数据结构。

它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

实现单链表的基本操作通常包括创建链表、插入节点、删除节点、遍历链表等。

答案：- 创建链表：定义一个链表结构体，然后使用动态内存分配为每个节点分配内存。

- 插入节点：根据插入位置，调整前后节点的指针，并将新节点插入到链表中。

- 删除节点：找到要删除的节点，调整其前后节点的指针，然后释放该节点的内存。

- 遍历链表：从头节点开始，使用指针遍历链表，直到达到链表尾部。

2. 二叉树的遍历二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点。

二叉树的遍历是数据结构中的一个重要概念，常见的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历。

答案：- 前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

- 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

- 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

- 层序遍历：使用队列，按照从上到下，从左到右的顺序访问每个节点。

3. 哈希表的实现哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。

它提供了快速的数据访问能力，但需要处理哈希冲突。

答案：- 哈希函数：设计一个哈希函数，将键映射到哈希表的索引。

- 哈希冲突：使用链地址法、开放地址法或双重哈希法等解决冲突。

- 插入操作：计算键的哈希值，将其插入到对应的哈希桶中。

- 删除操作：找到键对应的哈希桶，删除相应的键值对。

4. 图的表示和遍历图是一种复杂的非线性数据结构，由顶点（节点）和边组成。

国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。