当前位置：文档之家 › 南邮数据结构课后习题答案讲解

南邮数据结构课后习题答案讲解

  • 格式：pptx
  • 大小：285.79 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

数据结构_南京邮电大学中国大学mooc课后章节答案期末考试题库2023年

数据结构_南京邮电大学中国大学mooc课后章节答案期末考试题库2023年

数据结构_南京邮电大学中国大学mooc课后章节答案期末考试题库2023年1.对线性表进行对半搜索时，要求线性表必须（）。

答案:以顺序方式存储，且数据元素有序2.已知循环队列A[80]的队头标识front=45，队尾标识rear=10，此时队列还可以再入队最多______个元素。

答案:343.一棵有538个结点的二叉树具备完全二叉树树型，且为森林转换而来，则森林中树的个数为______。

答案:4.已知5阶B树中具有235个失败结点，该树的高度至少为______。

答案:45.设一个栈输入序列是1、2、3、4、5，则下列序列中不可能是栈的输出序列是（）。

答案:145236.二叉树的先序遍历为EFHIGJK，中序遍历序列为HFIEJKG。

该二叉树根结点的左子树的根是（）。

答案:7.具有n 个顶点的无向完全图中，边的总数为（）条。

答案:n（n-1）/28.一棵非空二叉树的中序遍历序列中，根结点的左边（）。

答案:只有左子树上的所有结点9.带表头结点的循环单链表为空的条件是______。

答案:head->next==head10.序列4,6,7,5,3,9是下列______算法两趟排序后的结果答案:直接插入排序11.已知先序遍历和后序遍历序列能唯一确定一棵二叉树。

答案:错误12.序列7,25,89,19,36,17是最小堆。

答案:错误13.一个表示工程的AOE网中的关键路径可以有多条。

答案:正确14.含有20个顶点和10条边的无向图用邻接矩阵存储，矩阵中零元素的数量是390。

答案:错误15.算法的确定性是指算法无论运行多少次，结果都一样。

答案:错误16.高度为6（根的层次为1）的满二叉树有个结点。

答案:6317.设有10阶对称矩阵A，其中矩阵元素用aij表示，i为行下标，i=0,1,...,9，j 为列下标，j=0,1,...,9，将A按照列优先顺序存储下三角元素的方式存储至一维数组B，设每个矩阵元素占4个字节，已知数组B的首地址为50，则，a28的地址是______。

南邮陈慧南版数据结构课后习题答案

南邮陈慧南版数据结构课后习题答案

template <class T> void LinkedStack<T>::SetNull() { Node<T> *q; while (top) { q=top->link; delete top; top=q; } }
i k(循环次数) 2*i 1 1 21<n 2 2 22<n 2k-1 n 2k<n 2k<n, k<log2n, k=log2n
划线语句的执行次数为 log2n。O(log2n) (3) for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) for (int k=1;k<=j;k++) x++;
习题三（第50页）
3.1 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问 能否得到下列序列。若能得到，则给出相应的push和pop序列；若不 能，则说明理由。 1) A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A 答：2）和3）不能。对2）中的E，B，D而言，E最先出栈则表明，此 时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3） 也不能。 (1)能。 push,pop,push,pop,push,pop,push,pop,push,pop (4)能。 push,push,push,push,push,pop,pop,pop,pop,pop
template <class T> bool LinkedStack<T>::IsEmpty() const { return !top; }
template <class T> bool LinkedStack<T>::IsFull() const { return false; }

南邮数据结构课后习题课27页PPT

南邮数据结构课后习题课27页PPT

南邮数据结构Βιβλιοθήκη 后习题课26、机遇对于有准备的头脑有特别的 亲和力 。 27、自信是人格的核心。
28、目标的坚定是性格中最必要的力 量泉源 之一， 也是成 功的利 器之一 。没有 它，天 才也会 在矛盾 无定的 迷径中 ，徒劳 无功。- -查士 德斐尔 爵士。 29、困难就是机遇。--温斯顿．丘吉 尔。 30、我奋斗，所以我快乐。--格林斯 潘。
66、节制使快乐增加并使享受加强。 ——德 谟克利 特 67、今天应做的事没有做，明天再早也 是耽误 了。——裴斯 泰洛齐 68、决定一个人的一生，以及整个命运 的，只 是一瞬 之间。 ——歌 德 69、懒人无法享受休息之乐。——拉布 克 70、浪费时间是一桩大罪过。——卢梭

南邮_数据结构课后习题答案讲解

南邮_数据结构课后习题答案讲解
（2）void Search_Delete(List *lst, T x,T y)
前置条件： x<y
后置条件：删除有序表中元素值在 x和y之间（ 含x和y）的所有元素。
2020/2/8
12
void Search_Delete(List *lst, T x, T y)
{
if (lst->Size==0) { printf(“The list is empty”); return -1; }
sum=j-i; lst[i++]=lst[j++]; while(ej<lsne) lst[i++]=lst[j+//+小];于等于//删y的除元su素m删个除元素 n=n-sum; { j++; n--; }
}
2020/2/8
13
4.6 给出下列稀疏矩阵的行优先和列优先顺序存 储的行三元组和列三元组表示。
?
?
?1 4 7 ?
?
?
?4 4 9 ?
?4 4 9 ?
4.7 求对题图4-1的稀疏矩阵执行矩阵转置时数组
num[]和k[]的值。

num[col] 1
0
2
1
2
k[col]
0
1
1
3
4
2020/2/8
14
第六章 习题讲解
6-2. 对于三个结点 A，B和C，可分别组成多少不同 的无序树、有序树和二叉树？
}
2020/2/8
4
2-12.设计一个算法，将单链表中结点以逆序排列。逆序的 单链表中的结点均为原表中的结点。 Node* pInvert(Node* first) { Node *p=first, *q; first=NULL; while (p) { q=p->Link; p->Link=first; first=p; p=q; } return first; }

(完整版)数据结构课后习题答案

(完整版)数据结构课后习题答案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构课程课后习题集答案解析

数据结构课程课后习题集答案解析

《数据结构简明教程》练习题及参考答案练习题11. 单项选择题（1）线性结构中数据元素之间是（）关系。

A.一对多B.多对多C.多对一D.一对一答：D（2）数据结构中与所使用的计算机无关的是数据的（）结构。

A.存储B.物理C.逻辑D.物理和存储答：C（3）算法分析的目的是（）。

A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C（4）算法分析的两个主要方面是（）。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A（5）计算机算法指的是（）。

A.计算方法B. 排序方法C.求解问题的有限运算序列D.调度方法答：C（6）计算机算法必须具备输入、输出和（）等5个特性。

A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2. 填空题（1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。

答：①逻辑结构②存储结构③运算（2）数据结构按逻辑结构可分为两大类，它们分别是①和②。

答：①线性结构②非线性结构（3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。

答：①数据元素②关系数据结构简明教程（4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。

答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。

答：①前驱 ②1 ③后继 ④任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。

答：任意多个（7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。

答：①顺序 ②链式 ③索引 ④哈希（8）一个算法的效率可分为 ① 效率和 ② 效率。

南邮数据结构答案

第1 章绪论一、基础题1. A2. C3. C4. A5. C二、扩展题1.数据是计算机加工处理的对象；数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；数据项是组成数据元素的、不可分割的最小单位。

2.数据结构是按某种逻辑关系组织起来的数据元素的集合，使用计算机语言描述并按一定的存储方式存储在计算机中，并在其上定义了一组运算。

3.集合结构、线性结构、树形结构和图形结构。

集合结构中，元素之间没有关系；线性结构中，元素之间存在一对一的关系；树形结构中，元素之间存在一对多的关系，其中最多只有一个元素没有前驱元素，这个元素就是根；图形结构中，元素之间存在多对多的关系。

4.顺序存储、链式存储、索引存储和散列存储。

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

其特征包括：➢输入：算法有零个或多个输入➢输出：算法至少产生一个输出➢确定性：算法的每一条指令都有确切的定义，没有二义性。

➢能行性/可行性：可以通过已经实现的基本运算执行有限次来实现➢有穷性：算法必须总能在执行有限步之后终止6.联系：程序是计算机指令的有序集合，是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。

区别：在语言描述上不同，程序必须是用规定的程序设计语言来写，而算法的描述形式包括自然语言、伪代码、流程图和程序语言等；算法所描述的步骤一定是有限的，而程序可以无限地执行下去，比如一个死循环可以称为程序，但不能称为算法。

7.正确性：算法的执行结果应当满足功能需求，无语法错误，无逻辑错误简明性：思路清晰、层次分明、易读易懂，有利于调试维护健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果效率：有效使用存储空间和有高的时间效率最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法可使用性：用户友好性8(1)执行次数为n-1（n>=2），n=1时执行1次；时间复杂度为O(n)。

(2）执行次数为⌈log3n⌉；时间复杂度为O(logn)(3) 执行次数为n2；时间复杂度为O(n2)(4）执行次数为⌊√n⌋ + 1；时间复杂度为O(√n)第2 章线性表1．A2．D3．B4．C5．B6．D7．D8．C9．A10．D1.编写程序实现对顺序表逆置。

南京邮电大学数据库系统课后习题答案


R2(CNO, TNAME, TADDR) } F2={CNO→TNAME,TNAME→TADDR}, KEY=(CNO)
ρ中R1、R2的所有属性都是原子的，且没有非
主属性对候选键的部分函数依赖，达到2NF;
2021/4/14
28
(3) 试把R分解成3NF模式集，并说明理由;
2021/4/14
数据库系统
习题课二
8
第四章习题
4.21设有关系模式R(ABC )，其上的FD集为 F={ B→C，C→A }， 那么分解ρ＝{AB, AC}
相对于F是否是无损分解和保持FD？说明理由
解 (1) ρ中有R1(AB)， R2(AC)
R1∩R2=A， R1－R2=B， R2－R1=C 在F中推导不出 A→B或A→C，ρ有损 (2) F1 ={B→A } , F2 = {C→A } （F1∪F2）＋ ≠F＋,丢失了B→C 分解ρ不保持函数依赖
2021/4/14
数据库系统
习题课二
9
第四章习题
第五章参考答案
• PP.180 5.14
• 某商业集团有三个实体集。一个是“公司”实体集， 属性有公司编号、公司名、地址等。二是“仓库”实 体集，属性有仓库编号、仓库名、地址等。三是“职 工”实体集，属性有职工编号、姓名、性别等。公司 与仓库间存在“隶属”关系，每个公司管辖若干个仓 库，每个仓库只属于一个公司管辖；仓库与间存在 “聘用”联系，每个仓库可聘用多个职工，每个职工 只能在一个仓库工作，仓库聘用职工有聘期和工资。 画出ER图，并在图上注明属性、联系的类型。转换成 关系模式集，并指出每个关系模式的主键和外键。
也可用域约束或断言
①在基表S的定义中，用检查子句
CHECK(AGE BETWEEN 16 AND 25) ②在基表SC的定义中，做以下说明：

(完整版) 《数据结构》教材课后习题+答案

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

南邮 数据结构A 习题3参考答案

(4)能，操作序列:push(A),push(B),push(C),push(D),push(E),pop() ,pop(),pop(),pop(),pop()
3.4
(1)(a+b)/(c+d)ab+cd+/
(2)b^2-4*a*cb2^4a*c*-
(3)a*c-b/c^2ac*-bc2^/-
(4)(a+b)*c+d/(e+f)ab+c*def+/+
this->Pop();
sq.EnQueue(temp);
}
while (!sq.IsEmpty())
{
sq.Front(temp);
sq.DeQueue();
this->Push(temp);
}
}
3.15
(1)
void max(int a[],int n,int &num)
{
if (n>0)
{
if (a[n-1]>num) num=a[n-1];
(5)(a+b)*(c*d+e)-a*cab+cd*e+*ac*-
3.13
t template <class T>
void SeqStack<T>::Invert(void)
{
SeqQueue<T> sq(maxTop + 1);
T temp;
while (top != -1)
{
this->rn 0;
}
main()
{
int a[10],s,av;
int n=10;
……
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2020/10/24
6
第三章 习题讲解
3-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得 到，则给出相应的push和pop序列；若不能，则 说明理由。 （2）A，C，E，B，D
（2）不能得到该序列，在E出栈时，B和D在栈 中，B比D先进栈，所以D应比B先出栈。
前置条件：x<y
后置条件：删除有序表中元素值在x和y之间（ 含x和y）的所有元素。
2020/10/24
12
void Search_Delete(List *lst, T x, T y)
{
if (lst->Size==0)
{ printf(“The list is empty”); return -1; }Biblioteka 2020/10/249
第四章 习题讲解
4-1. 设线性表采用顺序表示方式，并假定顺序表是 有序的（设表中元素已按非递减次序排列）。编写 函数，实现线性表的如下运算： （1）int Search_Insert(List *lst,T x)
后置条件：在有序的顺序表中搜索元素x。 •若x在表中，则返回x在表中的位置。 •否则，若表未满，则在表中插入新元素x，并且插 入后，线性表仍然是有序的，返回新元素x的位置； •若表已满，无法插入新元素，则返回-1。
第一章 习题讲解
1-19.确定下列各程序段的程序步，确定划线语句的执行次数， 计算它们的渐近时间复杂度。 (1) i=1; k=0; do { k=k+10*i; i++; } while(i<=n-1) 划线语句的执行次数为 n-1 ,渐近时间复杂度为O(n)
(2）i=1; x=0; do{ x++; i=2*i; } while （i<n）;
(4）x=n;y=0; while(x>=(y+1)*(y+1)) y++;
划线语句的执行次数为 n1/2 ,渐近时间复杂度为O(n1/2)
2020/10/24
2
第二章 习题讲解
2-4．Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2
2020/10/24
3
2-9. 设有长度为n 的一维整型数组A，设计一个算法，将原数 组中的元素以逆序排列
lst.Size++;
return i;
//插入新元素并返回该元素的位置
}
2020/10/24
11
4-1. 设线性表采用顺序表示方式，并假定顺序表是 有序的（设表中元素已按非递减次序排列）。编写 函数，实现线性表的如下运算：
（2）void Search_Delete(List *lst, T x,T y)
2020/10/24
7
3-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得到 ，则给出相应的push和pop序列；若不能，则说 明理由。 （3）C，A，B，D，E
（3）不能得到该序列，在C出栈时，A和B在栈中 ，A比B先进栈，所以B应比A先出栈。
2020/10/24
2020/10/24
5
第三章 习题讲解
3-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得 到，则给出相应的push和pop序列；若不能，则 说明理由。 （1）A，B，C，D，E
（1）能得到该序列。 相应的push和pop序列为：push(A); pop(); push(B); pop(); push(C); pop(); push(D); pop(); push(E); pop();
划线语句的执行次数为 log2n ,渐近时间复杂度为O(log2n)
2020/10/24
1
(3) for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) for (int k=1;k<=j;k++) x++;
划线语句的执行次数为n(n+1)(n+2)/6 ,渐近时间复杂度为O(n3)
}
2020/10/24
4
2-12.设计一个算法，将单链表中结点以逆序排列。逆序的单 链表中的结点均为原表中的结点。 Node* pInvert(Node* first) { Node *p=first, *q; first=NULL; while (p) { q=p->Link; p->Link=first; first=p; p=q; } return first; }
void Invert(T elements[], int length) //length数组长度 //elements[]为需要逆序的数组
{ T e; for (int i=1;i<length/2;i++) { e=elements[i-1]; elements[i-1]=elements[length-i]; elements[length-i]=e; }
8
3-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得到 ，则给出相应的push和pop序列；若不能，则说 明理由。 （4）E，D，C，B，A
（4）能得到该序列。 相应的push和pop序列为：push(A); push(B); push(C); push(D); push(E); pop(); pop(); pop(); pop(); pop();
② if (IsFull(lst)) //或if(lst->Size==lst->maxList) return -1; //表已满时，无法插入，返回-1
for (j=lst->Size-1; j>=i; j--)
lst->Element[j+1]=lst->Element[j];
③ lst->Element[i]=x; //新元素即插入位置i处
2020/10/24
10
int Search_Insert(List *lst, T x)
{ int i,j;
for(i=0; (x>lst->Elements[i])&&(i<lst->Size);i++);
// 查找首个大于等于x的元素位置，并记录在i中
① if (lst->Elements[i]==x) return i; //x在表中时，返回x的位置