2020 数据结构(山东交通学院)1451230466 最新满分章节测试答案

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

第1章 数据结构概述 数据结构概述

1、 问题:一个算法应该是（）
选项：
A:程序
B:问题求解步骤的描述
C:要满足五个基本特性
D:A和C
答案: 【问题求解步骤的描述】

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:运算实现
答案: 【逻辑结构】

7、 问题:以下说法正确的是（ ）
选项：
A:数据元素是数据的最小单位
B:数据项是数据的基本单位
C:数据结构是带有结构的各数据项的集合
D:数据结构是带有结构的数据元素的集合
答案: 【数据结构是带有结构的数据元素的集合】

8、 问题:通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )
选项：
A:数据元素具有同一特点
B:不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C:每个数据元素都一样
D:数据元素所包含的数据项的个数要相等
答案: 【不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致】

【作业】第1章 数据结构概述 数据结构概述-作业

1、 问题: 简述下列术语。 数据元素、 数据项、 数据结构、数据逻辑结构、数据存储结构、算法、抽象数据类型。
评分规则: 【 数据元素：数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
数据项：数据项是组成数据元素的基本单位，一个数据元素可以由若干个数据项组成
数据结构：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作的学科
数据逻辑结构：数据的逻辑结构是从逻辑的角度（即数据间的联系和组织方式）来观察数据，分析数据，与数据的存储位置无关。
数据存储结构：数据的存储结构是数据的逻辑结构在计算机中的实现形式，也称为物理结构。它包括数据元素的表示和关系的表示。
算法：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作
抽象数据类型：抽象数据类型（abstract data type，ADT）是一个数据结构和定义在该数据结构上的操作。抽象数据类型的定义仅取决于一组逻辑特性，而与其在计算机内部如何表示和实现无关，开发者们通过抽象数据类型的操作方法来访问抽象数据类型中的数据结构，而不管这个数据结构内部各种操作是如何实现的
】

2、 问题:分析下面语句段执行的时间复杂度。（1）for (int i=0; i (1) for (int i=0; i x<= log3(n) 即循环结束时，最多进行了log3(n)次运算。 按照大O表示法定义，它的复杂度为 O(log3(n)), 即O(lgn/lg3)
(4) int i = 1; int k = 0; do { k = k+10*i; ++i;} while(i!=n); 答：T(n)=O(n) 解析： 以上各语句的频度为：T(n)=1+1+(n-1)+(n-1)+(n-1)=3n+2,所以时间复杂度为T(n)= O(n)
】

3、 问题:用户与计算机一起做猜拳游戏，用户与计算机统称为玩家。玩家有三个战略：石头、剪刀、布。游戏胜负规则为：石头胜剪刀，剪刀胜布，布胜石头，如二人出手相同则不分胜负，不加分、不减分；二人不同，胜者加1分,负者减1分。人机猜拳输赢组合矩阵如表所示。编写程序实现人机猜拳游戏。具体要求如下：1．计算机由程序代码随机猜拳，用户键入数字猜拳，数字 1代表石头，2代表剪刀，3代表布。2．程序记录用户的姓名、得分及猜拳输赢信息。3.对实验结果进行分析，总结心得。
评分规则: 【 数据结构和算法实现设计
调试过程及实验结果
对实验结果进行分析，总结心得
】

第2章 线性表 线性表-单元测验

1、 问题:线性表是（ ）
选项：
A:一个有限序列，可以为空
B:一个有限序列，不能为空
C:一个无限序列，可以为空
D:一个无序序列，不能为空
答案: 【一个有限序列，可以为空】

2、 问题:对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素
选项：
A:n/2
B:(n+1)/2
C:(n –1)/2
D:n
答案: 【n/2】

3、 问题:用链表表示线性表的优点( )
选项：
A:便于随机存取
B:花费的存储空间较顺序存储少
C:便于插入和删除
D:数据元素的物理顺序与逻辑顺序相同
答案: 【便于插入和删除】

4、 问题:循环链表的主要优点是( )
选项：
A:不再需要头指针了
B:已知某个结点的位置后，能够容易找到他的直接前趋
C:在进行插入、删除运算时，能更好的保证链表不断开
D:从表中的任意结点出发都能扫描到整个链表
答案: 【从表中的任意结点出发都能扫描到整个链表】

5、 问题:若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间?
选项：
A:单链表
B:仅有头指针的单循环链表
C:双链表
D:仅有尾指针的单循环链表
答案: 【仅有尾指针的单循环链表】

6、 问题:给定有n个结点的向量，建立一个有序单链表的时间复杂度是: ( )
选项：
A:O(1)
B:O(n）
C:O(n2)
D:O(nlog2n)
答案: 【O(n）】

7、 问题:下面关于线性表的叙述中，错误的是哪一个？（ ）
选项：
A:线性表采用顺序存储，必须占用一片连续的存储单元
B:线性表采用顺序存储，便于进行插入和删除操作
C:线性表采用链接存储，不必占用一片连续的存储单元
D:线性表采用链接存储，便于插入和删除操作
答案: 【线性表采用顺序存储，便于进行插入和删除操作】

8、 问题:线性表是具有n个（ ）的有限序列（n>0）
选项：
A:表元素
B:字符
C:数据元素
D:数据项
答案: 【数据元素】

9、 问题:静态链表中指针表示的是（ ）
选项：
A:内存地址
B:数组下标
C:下一元素地址
D:左、右孩子地址
答案: 【下一元素地址】

【作业】第2章 线性表 线表表-单元作业

1、 问题:试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
评分规则: 【 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
】

2、 问题:线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：其中指针X，Y，Z的值分别为多少？
评分规则: 【 X= 116 Y= 0 Z= 100
】

3、 问题:对某电文（字符串）进行加密，形成密码文（字符串）。假设原文为C1C2C3…Cn，加密后产生的密文为S1S2S3…Sn。首先读入一个正整数key(key.>1)作为加密钥匙，并将密文字符位置按顺时针方向连成一个环。加密时从S1位置起顺时针方向计数，当数到第key个字符位置时，将原文中的字符C1放入该密文字符位置，同时从密文环中除去该字符位置。接着，从密文环中下一个字符位置起继续计数，当再次数到第key个字符位置时，将原文中的C2放入其中并从密文环中除去该字符位置，依此类推，直至n个原文字符全部放入密文环中。由此产生的S1S2S3……Sn即为原文的密文。 请按下面的要求，完成电文加密的编程问题:（1）编程实现动态输入原文的内容，动态输入key的值，对于每一个key，在屏幕上产生原文内容及密文内容。 （2）对程序进行测试，分析测试结果，写出总结。
评分规则: 【 编程实现动态输入原文的内容，动态输入key的值，对于每一个key，在屏幕上产生原文内容及密文内容。
对程序进行测试，分析测试结果，写出总结。
】

第3章 栈 栈-单元测验