2020 算法与数据结构(东莞理工学院)1451147463 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-02-24到2020-06-30
本篇答案更新状态:已完结

【作业】第1章 绪论 第1章绪论作业

1、 问题:【习题1-1】简述数据与数据元素的关系与区别。
评分规则: 【 凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数据的基本单位，是数据的个体。数据元素与数据之间的关系是元素与集合之间的关系。
】

2、 问题:【习题1-2】简述数据逻辑结构与存储（物理）结构的关系。
评分规则: 【 在数据结构中，逻辑结构与计算机无关，存储（物理）结构是数据元素之间的逻辑关系在计算机中的表示（存放）。存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储结构或链式存储结构表示。
】

3、 问题:【习题1-3】简述数据结构中运算描述和运算实现的异同。
评分规则: 【 运算描述是指对逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是设计处理步骤。
】

4、 问题:【习题1-4】数据结构和数据类型有什么区别？
评分规则: 【 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。而数据类型是一个值的集合和定义在这个值集上的一组运算的总称，如C语言中的short int数据类型是由-32768～32767（16位机）的整数和+、-、*、/、%等运算符构成。
】

5、 问题:【习题1-5】填空题（ ）由某一数据对象和该对象中各个数据成员间的关系组成。依据所有数据成员之间关系的不同，（ ）分为两大类：（ ）和（ ）。在（ ）中的各个数据成员依次排列在一个线性序列中；（ ）的各个数据成员不再保持在一个线性序列中，每个数据成员可能与零个或多个其他数据成员发生联系。根据视点的不同，数据结构分为数据的（ ）和（ ）。（ ）是面向问题的，（ ）是面向计算机的。A：数据结构 B：线性结构 C：非线性结构 D：逻辑结构 E：存储结构
评分规则: 【 每个空2分。（A）由某一数据对象和该对象中各个数据成员间的关系组成。依据所有数据成员之间关系的不同，（A）分为两大类：（B）和（C）。在（B）中的各个数据成员依次排列在一个线性序列中；（C）的各个数据成员不再保持在一个线性序列中，每个数据成员可能与零个或多个其他数据成员发生联系。根据视点的不同，数据结构分为数据的（D）和（E）。（D）是面向问题的，（E）是面向计算机的。
】

6、 问题:【习题1-6】判断下列叙述的对错。如果正确，在题前打“√”，否则打“×”。(1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。(2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。(3) 数据的逻辑结构与数据元素本身的内容和形式无关。(4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。(5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。
评分规则: 【 每道小题2分。(1) √ (2) × (3) √ (4) × (5) √
】

7、 问题:【习题1-7】算法的时间复杂度与（ ）有关。A．问题规模 B．计算机硬件的运行速度C．源程序的长度 D．编译后执行程序的质量
评分规则: 【 选A。算法的具体执行时间与计算机硬件的运行速度、编译产生的目标程序的质量有关，但这属于事后测量。算法的时间复杂度的度量属于事前估计，与问题的规模有关。
】

8、 问题:【习题1-8】以下关于数据结构的说法正确的是（ ）。A．数据结构的逻辑结构独立于其存储结构B．数据结构的存储结构独立于该数据结构的逻辑结构C．数据结构的逻辑结构唯一地决定了该数据结构的存储结构D．数据结构仅由其逻辑结构和存储结构决定
评分规则: 【 选 A。数据的逻辑结构是面向问题的，是从应用的需求出发而建立的，至于如何在计算机上存储，这是设计时再考虑的内容，所以数据的逻辑结构可独立于存储结构来组织。反之，数据的存储结构是逻辑结构在计算机中的映像，它不能独立于逻辑结构存在；此外，同一逻辑结构在计算机上如何存储，要看是否易于访问，是否易于修改或增删，是否利于安全保密等，相应地可有不同存储结构可以选用；数据结构不是孤立的，不但要考虑数据的组织，还要考虑作用在数据结构上的操作，即数据对象的行为，因此数据结构不是仅由其逻辑结构和存储结构决定的。
】

9、 问题:【习题1-9】某算法的时间复杂度是O(n^2)，表明该算法（ ）。A．问题规模是n^2 B．问题规模与n^2成正比C．执行时间等于n^2 D．执行时间与n^2成正比
评分规则: 【 选D。算法的的时间复杂度是O(n^2)，这是设定问题规模为n的分析结果，所以A、B都不对；它也不表明执行时间等于n^2，它只表明算法的执行时间T(n)≤ k×n^2（k为比例常数）。有的算法，如n×n矩阵的转置，时间复杂度为O(n^2)，不表明问题规模是n^2。
】

10、 问题:【习题1-10】指出下列各算法的功能并求出其时间复杂度。(1) int Prime( int n ){ int i = 2, x = (int)sqrt(n); // sqrt(n)为求n的平方根 while ( i <= x ) { if ( n % i == 0 ) break; i++; } if ( i > x ) return 1; else return 0;}(2) int sum1( int n ){ int p = 1, s = 0; for ( int i = 1; i <= n; i++ ) { p = i; s += p; } return s;}(3) int sum2( int n ){ int s = 0; for ( int i = 1; i <= n; i++ ) { int p = 1; for ( int j = 1; j <= i; j++ ) p = j; s += p; } return s;}(4) int fun( int n ){ int i = 1, s = 1; while ( s < n ) s += ++i; return i;}
评分规则: 【 (1) 判断整数n是否素数，如果是则函数返回1，否则返回0。算法时间复杂性T(n)=O(sqrt(n))。
(2) 计算1,12,123,1234,…,123…n的和。算法时间复杂性T(n)=O(n)。
(3) 同样计算123…i。算法时间复杂性T(n)=O(n2)。这是因为没有像上题那样保留计算的中间结果，每次都重新计算12…*i，程序步数达到n(n+1)/2。
(4) 求出满足不等式1+2+3+…+i≥n的最小i值。例如，n=100，当i=14时，满足1+2+…+13=91＜100，1+2+…+14=105≥100。从i(i-1)/2＜n可得，i2-i-2n＜0，用代数法求解得i<(1±sqrt(1+8n))/2。因此可知，算法时间复杂性为O(sqrt(n))。
】

【作业】第2章 线性表 【Exercise】链式存储结构习题

1、 问题:【EX-2-1-1】带头结点的单链表L为空的判定条件是（ ）。A.L==NULL B.L->next==NULL C.L->next==L D.L!=NULL
评分规则: 【 本题答案为B。在带头结点的单链表L中，L指向头结点，由头结点的next域指向第1个元素结点，L->next==NULL表示该单链表为空。
】

2、 问题:【EX-2-1-2】对于一个具有n个元素的线性表，建立其单链表的时间复杂度为（ ）。A.O(log2n) B.O(1) C.O(n^2) D.O(n)
评分规则: 【 本题答案为D。在建立单链表时需建立n个结点以存放线性表中的元素。
】

3、 问题:【EX-2-1-3】在单链表中查找指定值的结点的时间复杂度是（ ）。A.O(log2n) B.O(1) C.O(n^2) D.O(n)
评分规则: 【 本题答案为D。需要从第1个数据结点出发逐一查找每个结点。
】

4、 问题:【EX-2-1-4】以下关于单链表的叙述中，不正确的是（ ）。A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的元素物理上不必相邻C.可以通过头结点直接计算第i个结点的存储地址D.插入、删除运算操作方便，不必移动结点
评分规则: 【 本题答案为C。单链表不具有随机存取特性，即不能在O(1)的时间内找到第i个结点。
】

5、 问题:【EX-2-1-5】在单链表中，增加一个头结点的目的是为了（ ）。A.使单链表至少有一个结点B.标识链表中重要结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储结构
评分规则: 【 本题答案为C。在单链表中增加一个头结点的主要目的是使删除和插入结点操作更简单，方便运算的实现。
】

6、 问题:【EX-2-1-6】在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。A.O(1) B.O(n) C.O(n^2) D.O(nlog2n)
评分规则: 【 本题答案为B。假设有序单链表是递增有序，在插入数据域为x的结点之前，先要在单链表中找到一个其数据域值刚好大于x的结点的前驱结点p，在p之后插入该结点。査找过程的时间复杂度为O(n)，插入过程的时间复杂度为O(1)，整个过程的时间复杂度为O(n)。
】

7、 问题:【EX-2-1-7】将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度是（ ）。A.O(1) B.O(n) C.O(m) D.O(m+n)
评分规则: 【 本题答案为C。在长度为m的单链表中找到尾结点，将长度为n的单链表的第一个数据结点作为其后继结点。
】

8、 问题:【EX-2-1-8】已知一个长度为n的单链表中所有结点是递增有序的，以下叙述中正确的是（ ）。A.插入一个结点使之有序的算法的时间复杂度为O(1)B.删除最大值结点使之有序的算法的时间复杂度为O(1)C.找最小值结点的算法的时间复杂度为O(1)D.以上都不对
评分规则: 【 本题答案为 C。该递增有序单链表中第一个结点值最小，找到该结点的算法的时间复杂度为O(1)。
】

9、 问题:【EX-2-2】下面算法的功能是：删除单链表L中第一个值为x的结点。请在空白处填入正确的语句。int delx(LinkList &L, ElemType x)
{
LinkList pre = L, __①_; //pre 指向p 的前驱结点
while(p != NULL && p->data != x) {
②_;
p = p->next; //pre、 p 同步后移一个结点
}
if(p != NULL) { //找到值为 x的p结点
__③__;
_④___;
return 1;
}
else
return 0; //未找到值为 x 的结点
}
评分规则: 【 答案：1、p = pre->next2、pre = p3、pre->next = p->next4、free(p)
】

10、 问题:【EX-2-3】下面算法的功能是：删除单链表L含两个或两个以上的数据结点中第一个值为x的结点的前驱结点。请在空白处填入正确的语句。int delfirstx(LinkList &L, ElemType x)
{
LinkList prepre = L, pre = prepre->next, p;
if(_①_)
return 0;
p = _②_;
while(p != NULL && __③__) { // 找到值为x结点
__④_;
pre = p;
p = p->next; //prepre、 pre、 p 同步后移一个结点
}
if(p != NULL) { // 找到值为 x的p 结点
prepre->next = p; //删除pre 结点
_⑤______; //释放pre 结点空间
return 1; //成功删除返回 1
}
else
return 0; //未找到值为 x 的结点， 返回 0
}
评分规则: 【 答案：1、pre->data == x2、pre->next3、p->data != x4、prepre = pre5、free(pre)
】

11、 问题:【EX-2-4】下面算法的功能是：判定单链表L是否是递增的。请在空白处填入正确的语句。int increase(LinkList L)
{
LinkList __①, p; //pre 指向第一个数据结点
p = pre->next; //p 指向pre 结点的后继结点
while (②__) {
if (p->data >= pre->data) { //若正序则继续判断下一个结点
__③_; //pre、 p 同步后移
_④_;
}
else
__⑤_;
}
return 1;
}
评分规则: 【 答案：1、pre = L->next2、p != NULL3、pre = p4、p = p->next5、return 0
】

第2章 线性表 【Test】单元测试 – 顺序存储结构

1、 问题:【TEST-2-1-1】下列关于线性表的叙述中正确的是（ ）。
选项：
A:A.每个元素最多有一个直接前趋和一个直接后继
B:B.每个元素最少有一个直接前趋和一个直接后继
C:C.每个元素有且仅有一个直接前趋，有且仅有一个直接后继
D:D.线性表中每个元素都是不可再分解的数据元素，且数据类型必须相同
答案: 【A.每个元素最多有一个直接前趋和一个直接后继】

2、 问题:【TEST-2-1-2】在二维表格（线性表）中的每一个表元素都是不可再分的（ ）。
选项：
A:A.数据项
B:B.记录
C:C.数据元素
D:D.字段
答案: 【C.数据元素】

3、 问题:【TEST-2-1-3】以下关于顺序表的说法中，正确的是（ ）。
选项：
A:A.顺序表可以利用一维数组表示，因此顺序表与一维数组在结构上是一致的，它们可以通用
B:B.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻
C:C.顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问
D:D.在顺序表中每一元素的数据类型还可以是顺序表
答案: 【C.顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问】

4、 问题:【TEST-2-1-4】设线性表有n个元素且采用顺序存储表示，算法的时间复杂度为O(1)的操作是（ ）。
选项：
A:A.访问第i个元素和求第i个元素的直接前趋(2≤i≤n)
B:B.在第i(1≤i≤n)个元素后面插入一个新元素
C:C.删除数组第i个元素
D:D.顺序查找与给定值k相等的元素
答案: 【A.访问第i个元素和求第i个元素的直接前趋(2≤i≤n)】

5、 问题:【TEST-2-1-6】在以下有关顺序表的叙述中正确的是（ ）
选项：
A:A.顺序表的优点是存储密度高
B:B.集合与顺序表的区别在于集合中的元素不能相等
C:C.线性表就是顺序存储的表
D:D.取顺序表第i个元素的时间与i的大小有关
答案: 【A.顺序表的优点是存储密度高】

6、 问题:【TEST-2-2】下面算法的功能是：从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，当顺序表为空则显示出错信息并退出运行。请在空白处填入正确的语句。(每空5分)int deleteMin(SqList &L, ElemType &x)
{
//删除顺序表 L 中具有最小值的元素。 如果删除成功， 则函数返回 1并通过引用
//型参数 x 返回其值， 否则函数返回 0。
if (__①____) {
printf(“这是空表！”);