2020 数据结构（信安1901-1902）(长春建筑学院) 最新满分章节测试答案

文章目录[隐藏]

【作业】第1章绪论第1章绪论作业
第2章线性表【Test】单元测试 – 链式存储结构
【作业】第2章线性表顺序存储结构习题
【作业】第3章栈和队列【Exercise】栈与队列习题

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

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

1、问题:【2-1-1】在下列关于线性表的叙述中正确的是（）。
选项：
A:A.线性表的逻辑顺序与物理顺序总是一致的
B:B.线性表的顺序存储表示优于链式存储表示
C:C.线性表若采用链式存储表示时所有存储单元的地址可连续可不连续
D:D.除数组外，每种数据结构都应具备3种基本运算：插入、删除和查找
答案: 【D.除数组外，每种数据结构都应具备3种基本运算：插入、删除和查找】

2、问题:【2-1-2】数据结构反映了数据元素之间的结构关系。单链表是一种（）。
选项：
A:A.顺序存储线性表
B:B.非顺序存储非线性表
C:C.顺序存储非线性表
D:D.非顺序存储线性表
答案: 【D.非顺序存储线性表】

3、问题:【2-1-3】单链表又称为线性链表，在单链表上实施插入和删除操作（）。
选项：
A:A.不需移动结点，不需改变结点指针
B:B.不需移动结点，只需改变结点指针
C:C.只需移动结点，不需改变结点指针
D:D.既需移动结点，又需改变结点指针
答案: 【B.不需移动结点，只需改变结点指针】

4、问题:【2-1-4】已知单链表中结点q是结点p的直接前趋，若在q与p之间插入结点*s，则应执行以下（）操作。
选项：
A:A.s->next=p->next;p->next=s;
B:B.q->next=s;s->next=p;
C:C.p->next=s->next;s->next=p;
D:D.p->next=s;s->next=q;
答案: 【B.q->next=s;s->next=p;】

5、问题:【2-1-5】已知单链表中结点p不是链表的尾结点，若在p之后插入结点*s，则应执行以下（）操作。
选项：
A:A.s->next=p;p->next=s；
B:B.p->next=s；s->next=p;
C:C.s->next=p->next;p=s;
D:D.s->next=p->next;p->next=s;
答案: 【D.s->next=p->next;p->next=s;】

6、问题:【2-1-6】已知L是带头结点的单链表，则摘除首结点的语句是（）。
选项：
A:A.L=L->next;
B:B. L->next=L->next->next;
C:C.L=L->next->next;
D:D.L->next=L;
答案: 【B. L->next=L->next->next;】

7、问题:【2-1-7】已知单链表A长度为m，单链表B长度为n，若将B链接在A的末尾，在没有链尾指针的情形下，算法的时间复杂度应为（）。
选项：
A:A.O(1)
B:B.O(m)
C:C.O(n)
D:D.O(m+n)
答案: 【B.O(m) 】

8、问题:【2-1-8】给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是（）。
选项：
A:A.O(1)
B:B.O(n)
C:C.O(n^2)
D:D.O(nlog2n)
答案: 【C.O(n^2)】

9、问题:【2-2】下面算法的功能是：统计带头结点的单链表中具有给定值x的所有元素个数。请在空白处填入正确的语句。(每空5分)int Count(LinkList &L, ElemType x)
{
int count = 0;
LinkList p = _①__;
while(p != NULL) {
if(②)
__③_;
p = p->next;
}
_④____;
}
答案: 【答案：
1、L->next
2、p->data == x
3、count++
4、return count】

10、问题:【2-3】下面算法的功能是：根据一维数组A[n]建立一个带头结点的单链表，使单链表中各元素的次序与A[n]中各元素的次序相同。请在空白处填入正确的语句。(每空5分)void CreateList(LinkList &L, ElemType A[], int n)
{
LinkList rear;
L = __①__;
for(int i = 0; ②_; i++) {
rear->next = (LinkList)malloc(sizeof(LNode));
rear = rear->next;
_③_;
}
rear->next = _④;
}
答案: 【答案：
1、rear = (LinkList)malloc(sizeof(LNode))
2、i < n
3、rear->data = A[i]
4、NULL】

11、问题:【2-4】下面算法的功能是：对一个表头指针为h的单链表，通过遍历一趟链表，将链表中所有结点的链接方向逆转（将结点中的值倒转，如1→2→3→4变为4→3→2→1）。请在空白处填入正确的语句。(每空5分)void Reverse(LinkList &L)
{
LinkList p = _①, pr;
L->next = _②_;
while(p != NULL) {
③__;
p = p->next;