数据结构习题 树 数据机构c语言版

数据结构（C语言版）课后习题答案目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (43)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构c语言版试题大全(含答案)数据结构C语言版试题大全（含答案）第一章：基本概念与算法设计1.1 数据结构的定义与特点数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括了数据的存储、组织和管理方式。

数据结构的特点包括以下几个方面：- 数据元素之间存在某种关系，构成逻辑结构- 对数据元素的操作对应于对其逻辑结构的操作- 数据结构有存储结构，包括顺序存储结构和链式存储结构- 算法是对数据结构的操作步骤的描述和实现1.2 算法的基本概念算法是解决特定问题或完成特定任务的一系列操作步骤。

算法的基本概念包括以下几个方面：- 有穷性：算法必须能在有限步骤内完成- 确定性：算法的每一步骤必须有确定的含义和结果- 可行性：算法的每一步骤必须可行，能够通过执行有限次数实现- 输入：算法接受的输入数据是原始问题的实例- 输出：算法产生的输出数据与输入有明确的关系1.3 算法的描述方法算法可以用自然语言、伪代码或流程图来描述。

常用的伪代码描述方法包括结构化语言和算法描述语言，结构化语言包括顺序结构、分支结构和循环结构。

第二章：线性结构2.1 线性表的定义与基本操作线性表是n个数据元素的有限序列，其中相邻元素之间存在唯一的前驱和后继关系。

线性表的基本操作包括插入、删除、查找和修改等。

2.2 数组与广义表数组是指具有相同数据类型的一组数据元素的集合，可以通过下标访问元素。

广义表是线性表的推广，其中元素可以是基本数据类型或另一个广义表。

第三章：树与二叉树3.1 树的定义与基本术语树是n（n≥0）个结点的一个有限集合，其中满足以下条件：- 有且仅有一个特定的称为根的结点- 其余结点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树3.2 二叉树的定义与性质二叉树是指每个结点最多有两个子结点的树结构。

二叉树的性质包括以下几个方面：- 深度为k的二叉树最多有2^k-1个结点- 一棵二叉树的第i层最多有2^(i-1)个结点- 在二叉树的第i层上至多有2^(n-i+1)-1个结点（n为树的深度）第四章：图4.1 图的基本概念与术语图是由顶点的有穷非空集合和边的有穷集合组成的。

第一章客观习题1.D2.D3.B4. C5.D6.B7.D8.D9.A 10.C 11. A12.B简答题：1.存储实现是设计数据的存储结构，是建立数据的机内表示，包括数据元素和数据元素之间关系的存储。

运算实现是在某种存储实现的基础上具体实现各种运算，其运算实现的核心(即算法设计)是设计实现某一运算的处理步骤。

2. 算法的时间复杂度反映的是算法执行时间的数量级，并不是绝对执行时间。

两个时间复杂度都为O(n2)的算法，对于相同的问题规模n，它们的绝对执行时间也不一定一定相同。

3. 数据的逻辑结构包含两个要素，分别是数据元素和关系。

其中，关系是指数据元素间的逻辑关系。

根据数据元素之间关系的不同特性，通常有四类基本结构构关系，它们的复杂程度依次递进，如图1.1所示。

1) 集合结构2) 线性结构3) 树结构4) 图结构图1.1 四类基本逻辑结构关系图1) 集合结构：数据元素之间除了“属于同一集合”的关系外，无其他关系。

例如，确定一名学生是否为班级成员，只需要将班级看作一个集合结构；2) 线性结构：数据元素之间存在一对一的关系。

例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，组成一个线性结构；3) 树形结构：数据元素之间存在一对多的关系。

例如，在班级管理体系中，班长管理多个组长，每位组长管理多名组员，从而形成树形结构；4) 图结构/网状结构：数据元素之间存在多对多的关系。

例如，多位朋友之间的朋友关系，任何两位同学都可以是朋友，从而形成图结构或者网状结构。

4. 存储结构是由两种种基本的存储方式实现，分别为顺序存储结构和链式存储结构。

1) 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述；2) 链式存储不像顺序存储结构要求所有元素依次存放在一段连续的存储空间中，而是无需占用一整块存储空间。

由于为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址，通常借助程序设计语言的指针类型来描述。

数据结构(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、树形结构不具备这样的特点：（）A. 每个节点可能有多个后继（子节点）B. 每个节点可能有多个前驱（父节点）C. 可能有多个内节点（非终端结点）D. 可能有多个叶子节点（终端节点）2、二叉树与度数为2的树相同之处包括（）。

A. 每个节点都有1个或2个子节点B. 至少有一个根节点C. 至少有一个度数为2的节点D. 每个节点至多只有一个父节点3、一棵完全二叉树有999 个结点，它的深度为（）。

A．9 B．10 C．11 D．124、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）A. s->next=p;p->next=s;B. s->next=p->next;p->next=s;C. s->next=p->next;p=s;D. p->next=s;s->next=p;5、对于一棵具有n个结点、度为5的树来说，（）A. 树的高度至多是n-3B. 树的高度至多是n-4C. 树的高度至多是nD. 树的高度至多是n-56、在顺序队列中，元素的排列顺序（）。

A. 由元素插入队列的先后顺序决定B. 与元素值的大小有关C. 与队首指针和队尾指针的取值有关D. 与数组大小有关7、串是一种特殊的线性表，其特殊性体现在（）。

A．可以顺序存储 B．数据元素是一个字符C．可以链式存储 D．数据元素可以是多个字符若8、顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3和 0，当从队列中删除1个元素，再插入2 个元素后，front和 rear的值分别为（）。

A．5 和1 B．2和4 C．1和5 D．4 和29、一棵完全二叉树上有1001 个结点，其中叶子结点的个数为（）。

A．250 B．500 C．254 D．50110、已知一个有向图如下图所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为（）。

附录习题参考答案习题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的元素。

一、是非题1. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

.......................( T )2. 线性表的逻辑顺序与物理顺序总是一致的........( F )3. 线性表中的每个结点最多只有一个前驱和一个后继。

......( T )4. 线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

.......................( F )5. 栈和队列逻辑上都是线性表。

..........................( T )6. 单链表从任何一个结点出发，都能访问到所有结点........( F )7. 单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

.................................................( T )8. 在用单链表表示的链式队列中，队头在链表的链尾位置。

....( F )9. 多维数组是向量的推广。

..............................( T )10. 栈是一种先进先出的线性表。

....( F )11. 凡是递归定义的数据结构都可以用递归算法来实现它的操作。

......( T )12. 设串S的长度为n,则S的子串个数为n(n+1)/2。

...........( F )13. 一般树和二叉树的结点数目都可以为0。

................( F )14. 按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。

....( T )15. 后序序列和中序序列能唯一确定一棵二叉树。

....( T )16. 对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂度为O(n) .............( T )17. 网络的最小代价生成树是唯一的。

...( T )18. 图的拓扑有序序列不是唯一的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

习题一一、单选题1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B )。

A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ B ）个元素.A. nB.n-1C. n+1D.不确定3.下述哪一条是顺序存储方式的优点？（A ）A．存储密度大 B.插入和删除运算方便C. 获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)DA．658 B．648 C．633 D．6535.下列关于二叉树遍历的叙述中，正确的是( AD ) 。

A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为( A ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.对线性表进行二分法查找，其前提条件是( B ).A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空为Cn） B. O（n） C. O（1） D. O（n2）A. O（1og29.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（ D ）个，A．1 B．2 C．3 D．410.下列关于数据结构的叙述中，正确的是( D ).A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法二、填空题1.数据的逻辑结构被分为_集合结构、__线性结构、_树结构和_图结构四种。

数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率B．复杂性C．现实性D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所1998 二、1 （2分）】A．问题的规模B．待处理数据的初态C．A和B D．都不是3．计算机算法指的是（①C ），它必须具备（② B ）这三个特性。

①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（B ）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（ D ）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（Ａ）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（Ｃ）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（Ｄ）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（Ｄ）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（Ａ）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（Ｃ）是非线性数据结构。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构(C语言版)(第2版)课后习题答案数据结构(C语言版)(第2版)课后习题答案1. 简介数据结构是计算机科学领域中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。

本文将针对《数据结构(C语言版)(第2版)》的课后习题提供答案，帮助读者更好地理解和应用数据结构。

2. 第一章: 绪论在第一章中，主要介绍了数据结构的基本概念、分类和基本操作。

以下是部分习题的答案：2.1 习题1习题描述：什么是数据结构？答案：数据结构是指数据对象中元素之间的关系，以及对这些关系进行操作的方法和技术的集合。

2.2 习题2习题描述：数据结构的分类有哪些？答案：数据结构可以分为线性结构和非线性结构。

线性结构包括线性表、栈、队列等；非线性结构包括树、图等。

3. 第二章: 线性表第二章介绍了线性表的定义、分类和实现。

以下是部分习题的答案：3.1 习题1习题描述：什么是线性表？答案：线性表是由n个数据元素a1, a2, ..., an组成的有限序列，其中元素之间存在着一一对应的关系。

3.2 习题2习题描述：线性表的分类有哪些？答案：线性表可以分为顺序表和链表。

顺序表是用一段地址连续的存储单元一次存储线性表的所有元素，而链表是采用链式存储结构，通过每个元素存储其后继元素的地址来实现元素之间的逻辑关系。

4. 第三章: 栈与队列第三章讲解了栈和队列的定义、特性和实现。

以下是部分习题的答案：4.1 习题1习题描述：栈和队列有什么区别？答案：栈是一种后进先出的线性表，只能在表尾进行插入和删除操作；队列是一种先进先出的线性表，只能在表的一端进行插入和删除操作。

4.2 习题2习题描述：栈的应用有哪些？答案：栈在计算机科学中有广泛的应用，如函数的调用和返回、括号匹配、表达式求值等。

5. 第四章: 串第四章讲解了串的定义、模式匹配和实现。

以下是部分习题的答案：5.1 习题1习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。

一、选择题1．一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE2．算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++3. 在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点。

则树T的叶结点个数是( )。

A. 41B. 82C. 113D. 1224. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A．5 B．6 C．7 D．85. 在下述结论中，正确的是（）①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定7．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A．M1 B．M1+M2 C．M3 D．M2+M39．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A． 250 B． 500 C．254 D．505 E．以上答案都不对10. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )。

A．不确定 B．2n C．2n+1 D．2n-111．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。

习题11.1选择题。

(1)计算机识别、存储和加工处理的对象统称为。

A．数据B.数据元素C.数据结构D.数据类型(2)数据结构通常是研究数据的及它们之间的联系。

A．存储和逻辑结构B.存储和抽象C.理想和抽象D.理想和逻辑(3)下列不是数据的逻辑结构的是。

A．散列结构 B.线性结构 C.树形结构 D.图状结构(4)数据结构被形式地定义<D,R>，其中D是的有限集，R是___的有限集。

A．算法 B.数据元素C.数据操作 D.逻辑结构(5)组成数据的基本单位是。

A．数据项 B.数据类型 C.数据元素 D.数据变量(6)设数据结构A=(D,R),其中，D={1,2,3,4},R={r},r={<1,2>,<2,3 >,<3,4>,<4,1>},则数据结构A是。

A．线性结构 B.树形结构 C.图状结构 D.集合(7)数据在计算机存储器中表示时，若物理地址与逻辑地址相同并且是连续的，则称为。

A．存储结构B.逻辑结构C．顺序存储结构D.链式存储结构(8)在数据结构的讨论中把数据结构从逻辑上分。

A．内部结构与外部结构B.静态结构与动态结构B．线性结构与非线性结构 D.紧凑结构与非紧凑结构(9)对于一个算法的评价，不包括以下方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时间空间复杂度(10)算法分析的两个方面是。

A．空间复杂性和时间复杂性B.正确性和简明性C．可读性和文档性 D.数据复杂性和程序复杂性1.2填空题(1)数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

(2)数据结构包括数据的结构和结构。

(3)数据结构从逻辑上划分为3种基本类型，即、和。

(4)数据的物理结构被分为、、和种类型。

(5)一种抽象数据结构类型包括和两个部分。

(6)数据的逻辑结构是指数据的存储结构是指(7)数据结构是指指数数据及其相互之间的当结点之间存在M对N(M:N)的联系时，称这种结构为当结点之间存在1对N(1：N)的联系时，称这种结构为(8)对算法从时间和空间两个方面进行衡量，分别称为分析。

第一章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义、抽象数据类型的定义、表示和实现方法、描述算法的类C语言、算法设计的基本要求。

二、学习要点1、熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。

分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2、了解抽象数据类型的定义、表示和实现方法。

3、熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。

4、理解算法五个要素的确切含义。

1.1 基础知识一、填空题1、数据的逻辑结构包括①，②，③和④四种类型，树型结构和图型结构合称为⑤，数据的存储结构即物理结构包括：⑥，⑦等两种基本类型。

2、在线性结构中元素之间存在①关系，树形结构中元素间存在②关系，图形结构中元素间存在③关系。

3、一个数据结构用二元组表示时，它包括①集合D和D上②的集合S。

4、一个算法应具有①，②，③，④和⑤这五个特性。

5、在图形结构中，每个节点的前驱节点和后继节点可以有①个。

6、一个抽象数据类型用三元组（D，S，P）表示时，D是①，S是②，P是③。

7、数据元素在计算机中的映象是①。

8、算法的设计取决于①，算法的实现取决于②。

二、选择题1、数据元素是数据的单位。

(A)基本(B)最小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)哈夫曼树解答：一、 填空题1、①线性 ②集合 ③树 ④图或网 ⑤非线性结构 ⑥顺序存储 ⑦链式存储2、①1：1 ②1：n ③m ：n3、①数据元素 ②关系4、①有穷性 ②确定性 ③可行性 ④输入 ⑤输出5、①多个6、①数据对象 ②D 上的关系集合 ③对D 的基本操作集合7、①元素或结点8、①数据（逻辑）结构 ②采用的存储结构二、 选择题1、A2、B3、C4、B5、B6、Al.2 应用知识1、什么是算法？算法的特性是什么？算法设计的要求是什么?解答: （略）2、设有数据结构USER_STRU 表示如下：USER_STRU =（D ，S ）D = { a1，a2，…，a9 }S = { <a1，a3>，<a1，a8>，<a2，a3>，<a2，a4>，<a2，a5>，<a3，a9>，<a5，a6>，<a8，a9>，<a9，a7>，<a4，a7>，<a4，a6> }画出这个数据结构的图示，并确定其类型。

第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

（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．选择题babadbcabdcddac2．算法设计题（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;}}（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

1.设二叉树bt 的存储结构如下，其中bt为树根结点指针，left，right分别为结点的左、右孩子指针，dada为结点的数据域。

请完成下列各题：1）画出二叉树bt的逻辑结构2）写出按先序、中序、后序遍历二叉树所得到的结点序列3）画出二叉树bt的后序线索化树1 2 3 4 5 6 7 8 9 102.二叉树结点数值采用顺序存储结构，如图所示，1）画出二叉树表示2）写出前序遍历，中序遍历和后序遍历的结果3）写出结点值c的父结点，其左、右孩子。

4）画出将此二叉树还原成森林的图3.已知一棵二叉树的中序序列为cbedahgijk，后序序列为cedbhjifa，画出该二叉树的先序线索二叉树。

4.有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），求出每个字符的Huffman编码。

5.设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。

6.假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。

7.假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的结点。

编写一个求出从根结点到p所指结点之间路径的函数。

8.在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假设值为x的结点不多于1个。

9.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有结点数。

10.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩子结点数。

数据结构c语言版试题及答案一、选择题（每题2分，共20分）1. 在C语言中，以下哪个关键字用于定义结构体？A. structB. unionC. enumD. typedef答案：A2. 若定义了一个结构体变量，下列哪个语句是正确的？A. struct Student stu;B. struct Student stu[];C. struct Student stu[10];D. Student stu;答案：A3. 在C语言中，下列哪个函数用于创建链表节点？A. mallocB. freeC. callocD. realloc答案：A4. 下列哪个选项不是线性表的顺序存储结构的特点？A. 存储空间连续B. 可以快速地存取任一元素C. 空间利用率高D. 插入和删除操作复杂答案：D5. 在C语言中，以下哪个函数用于释放动态分配的内存？A. mallocB. freeC. callocD. realloc答案：B6. 下列哪个选项不是栈的基本操作？A. pushB. popC. topD. clear答案：D7. 在C语言中，以下哪个关键字用于定义联合体？A. structB. unionC. enumD. typedef答案：B8. 下列哪个选项是二叉树的遍历方式？A. 前序遍历B. 中序遍历C. 后序遍历D. 所有选项答案：D9. 在C语言中，以下哪个关键字用于定义枚举类型？A. structB. unionC. enumD. typedef答案：C10. 下列哪个选项是队列的基本操作？A. enqueueB. dequeueC. peekD. 所有选项答案：D二、填空题（每题2分，共20分）1. 结构体定义的关键字是______。

答案：struct2. 动态内存分配的函数是______。

答案：malloc3. 在C语言中，链表的头节点通常定义为______类型。

答案：指针4. 顺序存储结构的存储空间是______的。

数据结构题集c语言版考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构是指（）。

A. 用一组地址连续的存储单元依次存储线性表的元素B. 用一组地址不连续的存储单元依次存储线性表的元素C. 用数组来存储线性表的元素D. 用链表来存储线性表的元素答案：A2. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动（）个元素。

A. i-1B. n-iC. n-i+1D. i答案：B3. 对于一个有n个结点的线性表，采用链式存储结构时，进行查找第i个元素（1≤i≤n）的时间复杂度为（）。

A. O(1)B. O(n)C. O(log2n)D. O(n^2)答案：B4. 在二叉树的遍历过程中，若一个结点的左子树为空，则该结点的右子树（）。

A. 一定为空B. 一定不为空C. 可能为空，也可能不为空D. 以上说法都不对答案：C5. 在二叉排序树中，若某结点的左子树非空，则左子树中的所有结点的值（）。

A. 都小于该结点的值B. 都大于该结点的值C. 都等于该结点的值D. 都大于等于该结点的值答案：A6. 一个具有n个顶点的连通图，其边数最少为（）。

A. n-1B. nC. n+1D. 2n答案：A7. 在图的遍历中，深度优先搜索算法所对应的数据结构是（）。

A. 栈B. 队列C. 链表D. 数组答案：A8. 哈希表的冲突解决方法中，开放定址法的特点是（）。

A. 装填因子较大B. 装填因子较小C. 装填因子不受限制D. 以上说法都不对答案：B9. 快速排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 用链表表示线性表的优点是（）。

A. 插入和删除操作不需要移动元素B. 节省存储空间C. 可以方便地随机访问D. 可以动态分配存储空间答案：A二、填空题（每题2分，共20分）1. 在顺序表中，若p是指向第i个元素的指针，则p+5表示指向第（）个元素的指针。