2020 数据结构(JAVA)(桂林电子科技大学信息科技学院) 最新满分章节测试答案

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

第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:数据元素所包含的数据项的个数要相等
答案: 【不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致】

第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:左、右孩子地址
答案: 【下一元素地址】

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

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

3、 问题:实验一 线性表一、实验目的1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。3. 掌握使用 C++面向对象的程序设计技术，设计数据结构源程序的方法。二、实验内容 1. 线性表的顺序存储表示（结构）及实现。阅读下列程序请注意几个问题。（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。顺序存储结构也称“向量（vector）”。在下列类设计中，采用静态一维数组elem[]表示向量,同时用length表示线性表长度。ElemType elem[MAXSIZE]; int length;(2)在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写入源程序。同时用户必须自己编写一段主函数main()，在主函数中创建声明类的具体对象，通过这些对象调用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。l 源称序结构：见本资料的第1页。l 数据结构类定义（包括成员函数的定义）的程序代码对于小型程序，这部分代码可以直接放入源称序之中，如上图所示。对于复杂较大的程序，这部分代码可以生成一个头文件（例如Sqlistc.h）与源程序文件存储在同一个文件夹中。再在源程序之中写入一个语句，如下：#include “Sqlistc.h”;l 主函数在学生没有学习可视化图形界面之前，建议在主函数中简单设计一个“菜单”(do-while循环内嵌套一个 switch结构)。随着学习的深入，应该学会熟练使用“菜单”技术，这样会明显提高编程和运行效率。一个主函数一般样式如下：int main( ){ //声明程序所需要的一般变量int i,k; ElemType e,x; //声明和创建类对象，这个类往往是典型数据结构类 Sqlist as; System.out.print（” ） 线性表顺序存储结构演示”; Scanner s = new Scanner(System.in); do{ //显示菜单内容 System.out.print（”” ） ; System.out.print（” 1. 初步建立一个线性表 ” ） ; System.out.print（” 2. 插入一个数据元素” ） ; System.out.print（” 3. 删除一个元素，返回其值 ” ） ; System.out.print（” 4. 结束程序” ） ; System.out.print（”********” ） ; System.out.print（”请输入你的选择(1,2,3,4)” ） ; Int n = s.nextInt(); //接收用户的选择//根据k值，转向对应的case 分支程序段执行switch(n){ case 1:{ as.SetData(); as.PrintOut(); }break;case 2:{ System.out.print（” 插入的位置，数据 i,e=?”）; Int i = s.nextInt(); Int e = s.nextInt(); as.Insert(i,e); as.PrintOut(); }break; case 3:{ System.out.print（” 删除第几个元i=?”）; Int i = s.nextInt(); x=as.Delet(i); System.out.print（” 元素数值= “）; as.PrintOut(); }break; default:break; } //switch }while(k>=1&&k<4); // System.out.print（” 再见!”）; System.out.print（” 按任意键，返回。”）; _getch(); return 0;}//———————————————– 要求：使用线性表实现一个通讯录，通讯录内容包含学号、姓名、电话三项数据。完成通讯录数据的建立，纪录插入和删除功能。
评分规则: 【 编程实现动态输入原文的内容，动态输入key的值，对于每一个key，在屏幕上产生原文内容及密文内容。
对程序进行测试，分析测试结果，写出总结。
】

第3章 栈 第三章单元测验