数据结构(C++版)王红梅版课后答案khdaw

第 2 章线性表课后习题讲解1. 填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。

【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）。

【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

【解答】p->next=head【分析】如图2-8所示。

⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意图如图2-9所示：⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。

【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。

⑻可由一个尾指针唯一确定的链表有（）、（）、（）。

【解答】循环链表，循环双链表，双链表2. 选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。

第1章绪论课后习题讲解1.填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

）、（）、（）和（）。

⑶ 从逻辑关系上讲，数据结构主要分为（【解答】集合，线性结构，树结构，图结构⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为 n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n ，则表示成数量级的形式为（）。

【解答】Ο(1) ，Ο(nlog2n)【分析】用大 O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2.选择题⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】 C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构(c )课后习题答案数据结构(C)课后习题答案在学习数据结构(C)课程时，课后习题是非常重要的一部分。

通过完成这些习题，我们可以加深对数据结构的理解，提高编程能力，并且更好地掌握C语言的运用。

下面我们就来看看一些常见的数据结构(C)课后习题答案。

1. 链表的创建和遍历链表是数据结构中常见的一种，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

在C语言中，我们可以通过动态内存分配来创建链表，并且可以使用指针来进行遍历。

下面是一个简单的链表创建和遍历的示例代码：```c#include <stdio.h>#include <stdlib.h>struct Node{int data;struct Node *next;};void printList(struct Node *node){while (node != NULL){printf("%d ", node->data);node = node->next;}}int main(){struct Node *head = NULL;struct Node *second = NULL;struct Node *third = NULL;head = (struct Node *)malloc(sizeof(struct Node)); second = (struct Node *)malloc(sizeof(struct Node)); third = (struct Node *)malloc(sizeof(struct Node)); head->data = 1;head->next = second;second->data = 2;second->next = third;third->data = 3;third->next = NULL;printList(head);return 0;}```2. 栈的实现栈是一种后进先出（LIFO）的数据结构，可以使用数组或链表来实现。

数据结构(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. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。

数据结构c 版习题答案数据结构是计算机科学中的重要基础课程，它主要研究数据的组织、存储和管理方式。

C语言是一种常用的编程语言，也是学习数据结构的重要工具。

在学习数据结构的过程中，习题是不可或缺的一部分，通过解答习题可以帮助我们巩固所学的知识。

下面是一些常见的数据结构C版习题的答案，供大家参考。

一、线性表1. 实现一个顺序表的插入操作。

答案：```cvoid insert(SeqList *list, int index, int value) {if (index < 0 || index > list->length) {printf("插入位置不合法\n");return;}if (list->length >= MAX_SIZE) {printf("顺序表已满\n");return;}for (int i = list->length - 1; i >= index; i--) {list->data[i + 1] = list->data[i];}list->data[index] = value;list->length++;}```2. 实现一个顺序表的删除操作。

答案：```cvoid remove(SeqList *list, int index) {if (index < 0 || index >= list->length) {printf("删除位置不合法\n");return;}for (int i = index; i < list->length - 1; i++) { list->data[i] = list->data[i + 1];}list->length--;}```二、栈和队列1. 实现一个栈的入栈操作。

第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O 记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

第 2 章线性表课后习题讲解1. 填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。

【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）。

【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

【解答】p->next=head【分析】如图2-8所示。

⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意图如图2-9所示：⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。

【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。

⑻可由一个尾指针唯一确定的链表有（）、（）、（）。

【解答】循环链表，循环双链表，双链表2. 选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。

第7 章查找技术课后习题讲解1. 填空题⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。

【解答】顺序存储和链接存储，顺序存储，按关键码有序⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。

【解答】1，7【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。

⑶对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（）。

若按二叉排序树组织该数列，则查找一个数的平均比较次数为（）。

【解答】8，59/15【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。

⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。

【解答】4【分析】在折半查找判定树中，第3层共有4个结点。

⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。

【解答】62【分析】H(48)= H(62)=6⑹在散列技术中，处理冲突的两种主要方法是（）和（）。

【解答】开放定址法，拉链法⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。

【解答】散列查找【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。

⑻与其他方法相比，散列查找法的特点是（）。

【解答】通过关键码计算记录的存储地址，并进行一定的比较2. 选择题⑴静态查找与动态查找的根本区别在于（）。

A 它们的逻辑结构不一样B 施加在其上的操作不同C 所包含的数据元素的类型不一样D 存储实现不一样【解答】B【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。

第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个元素的地址是（）。

第 3 章特殊线性表——栈、队列和串课后习题讲解1. 填空⑴设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。

【解答】23，1003H⑵栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。

【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间⑶（）可作为实现递归函数调用的一种数据结构。

【解答】栈【分析】递归函数的调用和返回正好符合后进先出性。

⑷表达式a*(b+c)-d的后缀表达式是（）。

【解答】abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。

【解答】后进先出，先进先出，对插入和删除操作限定的位置不同⑹循环队列的引入是为了克服（）。

【解答】假溢出⑺数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。

【解答】（rear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

⑻用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。

【解答】Ｏ(1)，Ｏ(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

⑼串是一种特殊的线性表，其特殊性体现在（）。

【解答】数据元素的类型是一个字符⑽两个串相等的充分必要条件是（）。

第 4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。

【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。

除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。

【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。

⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

【解答】三元组顺序表，十字链表⑸广义表((a), (((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。

【解答】3，4，(a)，((((b),c)),(d))⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。

【解答】Head(Head(Tail(LS)))2. 选择题⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。

A 90B 180C 240D 540E 108F 114G 54H A[8][5] I A[3][10] J A[5][8] K A[4][9]【解答】D，E，K【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则d+j×9+i=d+85，解此方程，得i=4，j=9。