2020 数据结构(本)(青岛理工大学琴岛学院) 最新满分章节测试答案

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

【作业】第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章 线性表 单元测试 – 顺序存储结构

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

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

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

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

6、 问题:【2-2】下面算法的功能是：从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，当顺序表为空则显示出错信息并退出运行。请在空白处填入正确的语句。

int deleteMin(SqList &L, ElemType &x)
{
//删除顺序表 L 中具有最小值的元素。 如果删除成功， 则函数返回 1并通过引用
//型参数 x 返回其值， 否则函数返回 0。
if (__①_) {
printf(“这是空表！”);
return 0;
}
int i, _②_; //假定0号元素的值最小
for (i = ③; i <= L.length; i++) //循环，寻找具有最小值的元素
if (L.elem[i – 1] < L.elem[mini])
min_i = ④__; //min_i 记忆当前具最小值元素的位置
x = L.elem[min_i];
_⑤__;
L.elem[min_i] = L.elem[L.length];
return 1;
}
答案: 【答案：
1、L.length == 0
2、min_i = 0
3、2
4、i – 1
5、L.length–】

7、 问题:【2-3】下面算法的功能是：从顺序表中删除具有给定值x的所有元素。请在空白处填入正确的语句。

void deleteValue(SqList &L, ElemType x)
{
// 在顺序表 L 中删除所有具有值 x 的元素
int i,__ ①_;
for(i = 0; i < ②__; i++) // 检测表中所有元素
if(L.elem[i] != x) { // 若元素不具有 x 值
if(_③__) //该元素前移
_④_ = L.elem[i];
k++;
}
_⑤__;
}
答案: 【答案：
1、k = 0
2、L.length
3、i != k
4、L.elem[k]
5、L.length = k】

8、 问题:【2-4】下面算法的功能是：从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。请在空白处填入正确的语句。

int deleteSame(SqList &L)
{
if(__①_)
return 0;
int i, _②_;
for(i = 1; i < L.length; i++)
if(__③_ != L.elem[i]) { //L.elem[i]与前一个不重复
if(k != i) // 把 L.elem[i]前移
_④__ = L.elem[i];
k++;
}
_⑤_;
return 1;
}
答案: 【答案：
1、L.length == 0
2、k = 1
3、L.elem[i – 1]
4、L.elem[k]
5、L.length = k】

第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)的操作是（ ）。