数据结构—算法概念与设计、学生成绩管理系统【习题篇】

• 💂 个人网站: 路遥叶子
• 🤟 版权: 本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主
• 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
• 💅 想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

 

目录

一、习题篇​

    ​(一) 概念题

    (二) 算法设计题

  （三）填空题

  （四）简答题

                1.什么是数据？

                2.算法的五种性质

                3.算法设计的目标

                4.算法的描述方式

                5.多项式时间算法的时间复杂度有哪些形式？

                6.按照数据元素之间逻辑关系的特性可分为哪几类(作简要说明)？

                7.顺序表的插入操作

                8.顺序表的查找操作

                9.列举几个常见的链表？

                10.顺序表与链表的比较

                11.算法的时间复杂度分析

                12.影响一个程序的执行时间的主要因素有如下几个方面

 (五) 线性表的应用举例

        学生成绩管理系统

                ​ 线性表接口

                ​线性表接口实现类

                ​学生成绩类

                主函数，功能调试；测试类

               ​ 测试结果 

章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！

 如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟

一、习题篇

        (一) 概念题

                 1. 试述数据结构研究的3个方面的内容。

                          解析：数据结构研究的3个方面分布是：

                                数据的逻辑结构 

                                数据的存储结构

                                数据的运算(操作)

                  2. 试述集合、线性结构、树形结构和图形结构4种常见的数据结构的特性。

                        集合结构

                                集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其他关系，它们之间的关系称为是松散性的

                        线性结构

                                线性结构中数据元素之间存在“一对一”的关系。

                                若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前驱但有一个后继。终端结点没有后继但有一个前驱。其余结点有其仅有一个前驱和后继。

                        树形结构

                                树形结构中数据元素之间存在“一对多”的关系。

                                若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可能有多个后继。

                        图形结构

                                图形结构中数据元素之间存在“多对多”的关系。

                                若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。

                3. 设有数据的逻辑结构的二元组定义形式为B=(D,R), 其中D = {a1,a2,a3,......an} ,  R={< ai,a i+1 > | i = 1,2,3.......n -1},请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。

                        顺序存储结构示意图:

                        链式结构示意图：

               4. 设一个数据结构的逻辑结构如下图，请写成它的二元组定义形式。

                        解析：由于二元组的定义形式为B= (D,R) ; 如图可知：

                                D = {k1,k2,k3,k4,k5,k6,k7,k8,k9} ；

                                则R = {ROW,COL} 【{行,列}】。故：R = { , , , , , , , , , , }

                  5. 试确定下列程序段中有标记符号 ‘ # ’ 的语句行的语句频度(其中n为正整数)

(1)  语句频度：n-1

i = 1 ; k = 0 ;
while ( i <= n -1 ) {k += 10*i ;             // #i++ ;
}

(2)  语句频度：当n <= 1 时频度为 1 ， 当n > 1 时语句频度 为 n-1

i = 1 ; k = 0 ;
do {k += 10 * i ;        //#i++ ;
}while (i <= n-1 )；

(3)  语句频度：n-1

i = 1 ; k = 0 ;
while ( i <= n -1 ) {i++ ;k += 10*i ;             // #
}

(4)  语句频度：n(n+1)/2

k = 0 ;
for(int i = 1 ; i <= n ; i++ ) {for( int j = 1; j <= i ; j++ ) {k++ ;         // #}
}

  (5)  语句频度：n

i = 1 ; j = 0 ;
while (i + j <= n) {if(i > j ) {j ++ ;      //#}else {i ++ ;}
}

(6)  语句频度：根号n 取整

x = n ; y = 0 ;        //n 是不小于1 的整数
while (x >= (y+1) * (y+1) ) {y ++ ;            //#
}

(7)   语句频度：1100

x = 91 ; y = 100 ;
while( y > 0 ) {if(x > 100 ) {x -= 10 ; y -- ;        //#}else {x++ ;}
}

(8)  语句频度：log3 n 【3 为下标】

a = 1 ; m = 1 ;
while(a < n) {m += a ;a *= 3 ;         //# 
}

            (二) 算法设计题

                  1. 有一个包括100个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数据元素的值及其下标的算法；并分析算法的时间复杂度。

    public void max(double[] list) {//初始化最大值为数组的第一个元素double max = list[0] ;int index = 0 ;   //记录索引for (int i = 0; i < list.length; i++) {if (max < list[i]) {max = list[i] ;index = i ;}}System.out.println("最大的实数为:"+max+"\n其在数组中的小标为："+ index);//此算法的时间复杂度为O(n), 其中n为数组的长度。}

                  2. 编写一个实现将整数数组中的数据元素按值递增的顺序进行排序的java程序。

package data.linear_table.csdn;public class Demo02_desc {public static void main(String[] args) {int[] value = {49,38,65,97,76,13,27,49} ;System.out.print("排序前的数组中的数据元素： ");for (int i = 0; i < value.length; i++) {System.out.print(value[i]+"\t");}System.out.println();System.out.print("降序排序后的数组中的数据元素:");int[] arr = bubbleSort(value);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+"\t");}}public static int[] bubbleSort(int[] arr) {    //arr为待排序的整数数组int length = arr.length ;   //数组的长度boolean isExchange = true ;         //判断是否交换位置的标志//如果i 小于最大索引，并且交换标志为true 。for (int i = 0 ; i < length - 1 &&  isExchange ; i++) {     //最多可遍历的索引为数组长度-1//将其交换标志设为falseisExchange = false ;//如果j 小于当前元素索引位置for (int j = 0 ; j < length - i -1 ; j++ ) {    //当前无序区进行排序if (arr[j] > arr[j+1]) {    //如果前一个数，比后一个数大；交换数据元素//满足交换条件，进行交换，定义一个变量视为中间变量。记录要交换的值int temp = arr[j] ;arr[j] = arr[j+1] ;arr[j+1] = temp ;isExchange = true ;}}if (!isExchange) {break;}}return arr ;}
}

         （三）填空题

1. 线性表是一种最常用、最简单，也是最基本的____数据结构________
2. 线性表由n个数据元素所构成的___有限序列_________，且数据类型相同
3. 线性表可以用`顺序存储`和`___链式存储_________`两种存储结构来表示
4. 链表可分为单链表、双向链表、____循环链表________、双向循环链表等
5. 顺序表就是___顺序存储_________的线性表
6. 顺序存储是用一组____地址连续________的存储单元依次存放线性表中各个数据元素的存储结构
7. 线性表地址公式：__Loc(Ai) = Loc(A0) + i * c (第i的地址 = 第一个地址 + 第几个 * 存储单位)__________
8. 在线性表中逻辑上相邻的数据元素，在__物理存储位置__上也是相邻的
9. 算法__时间复杂度 _的高低直接反应算法执行时间的长短
10. _数据元素__是数据结构中讨论的基本单位，不同场合也叫结点、顶点、记录
11. __算法______是对特定问题求解步骤的一种描述，是指令的有限序列。其中每条指令表示一个或多个操作
12. 对数据的操作包括：1.初始化：___创建、销毁____；2.数据操作：__增删改_____，3.数据使用：__查找、遍历__
13. 采用链式存储方式存储的线性表称为___链表_________
14. 若一个结点中只包含一个指针域，则称此链表为_____单链表_______
15. 链表中每个结点包含存放元素值的___数据域_________和存放指向逻辑上相邻结点的____指针域________ 。

           （四）简答题

1.什么是数据？

所有能被输入到计算机中，且能被计算机处理的符号的总称。如：实数、整数、字符（串）、图形和声音等。

是计算机操作对象的集合。

是计算机处理信息的某种特定的符号表示形式。

-----------------------------------------------------------------------------

2.算法的五种性质

有穷性                确定性

有效性                输入

输出

-----------------------------------------------------------------------------

3.算法设计的目标

正确性                可读性

健壮性                高效率（时间与空间）

-----------------------------------------------------------------------------

4.算法的描述方式：

自然语言                程序设计语言

伪代码                  流程图

-----------------------------------------------------------------------------

5.多项式时间算法的时间复杂度有哪些形式？

常量阶:O(1)                线性阶:O(n)

平方阶:O(n2)              立方阶：O(n3)

对数阶 : O(log2n【2为下标】)            

线性对数阶: O(n log2n【2为下标】) 

-----------------------------------------------------------------------------

6.按照数据元素之间逻辑关系的特性可分为哪几类(作简要说明)？

集合

        集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其他关系，它们之间的关系称为是松散性的

线性结构

        线性结构中数据元素之间存在“一对一”的关系

树形结构

        树形结构中数据元素之间存在“一对多”的关系

图形结构

        图形结构中数据元素之间存在“多对多”的关系

-----------------------------------------------------------------------------

7.顺序表的插入操作：

将第i个数据元素及其之后的所有的数据元素，后移一个存储位置，再将新元素插入到i处

public void insert(int i, Object x) {//0.1 满校验：存放实际长度 和 数组长度 一样if(curLen == listEle.length) {throw new Exception("已满");}//0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素if(i < 0 || i > curLen) {throw new Exception("位置非法");}//1 将i及其之后后移for(int j = curLen ; j > i; j --) {listEle[j] = listEle[j-1];}//2 插入i处listEle[i] = x;//3 记录长度curLen ++;
}

---

8.顺序表的查找操作

循环遍历已有数据，进行判断，如果有返回第一个索引号，如果没有返回-1

public int indexOf(Object x) {for(int i = 0; i < curLen ; i ++) {if(listEle[i].equals(x)) {return i;}}return -1;
}

使用变量记录没有匹配到索引

public int indexOf(Object x) {int j = 0; //用于记录索引信息while(j < curLen && !listElem[j].equals(x)) {j++;}// j记录索引小于数量if(j < curLen ) {return j;} else {return -1}
}

---

9.列举几个常见的链表？

单链表                循环链表

双向链表            双向循环链表

---

10.顺序表与链表的比较

链表比较灵活，插入和删除操作效率较高，但空间利用率低，适用于实现动态的线性表；

顺序表实现比较简单，并且空间利用率也较高，可高效的进行随机存取，但顺序表不易扩充，插入和删除操作效率较低，适合于实现相对“稳定”的静态线性表。

---

11.算法的时间复杂度分析

    算法时间复杂度的高低直接反应算法执行时间的长短，而算法的执行时间需要通过依据该算法编写的程序在计算机上执行所消耗的时间来度量
 

---

12.影响一个程序的执行时间的主要因素有如下几个方面

    算法本身所用的策略
    问题规模即处理问题时所处理的数据元素的个数
    程序设计所采用的语言工具
    编译程序所产生的机器代码质量
    计算机执行指令的硬件速度
    程序运行的软件环境

        (五) 线性表的应用举例

                学生成绩管理系统

                        编程实现学生成绩管理系统。此系统具有查询、修改、删除、增加和求全班各门课平均分的功能。要求采用顺序存储结构。

                         分析：由学生成绩表可知数据元素是由学号、姓名、性别、大学英语、高等数学5个数据项所构成。故可将数据元素描述为学生成绩类如下：

                         程序代码：

        线性表接口

package data.linear_table;//线性表接口
public interface IList {public void clear() ;  //清空public boolean isEmpty();  //判断是否为空public int length();   // 表的长度public Object get(int i) throws Exception; //获取元素的值public void insert(int i , Object x) throws Exception; //在指定位置，插入指定元素public void remove(int i ) throws Exception; //删除指定元素public int indexOf(Object x) ;  //查找指定元素第一次出现的位置public void display() ;  //输出元素的值
}

        线性表接口实现类

package data.linear_table;//线性表接口实现类
public class SqList implements IList {private Object[] listElem ;    //线性表的存储空间private int curLen ;          //线性表的当前长度//顺序表类的构造函数，构造一个存储空间容量为maxSize的线性表public SqList(int maxSize) {curLen = 0 ;  //置顺序表的当前长度为0listElem = new Object[maxSize];  //为顺序表分配maxSize个存储单元}//将一个一存在的线性表置为空表@Overridepublic void clear() {curLen = 0 ;   //置顺序表的当前长度为0}//判断线性表的数据元素的个数是否为0 ，若为0则返回true,反之返回false@Overridepublic boolean isEmpty() {return curLen == 0;}//求线性表中的数据元素的个数并返回值@Overridepublic int length() {return curLen;}//读取到线性表中的第i个数据元素并有函数返回其值。其中i的取值范围为：0 <= i <= length()-1//若i 值不在此范围则抛出异常@Overridepublic Object get(int i) throws Exception {if (i < 0 || i > curLen -1 ) {  //i 小于或者大于表长-1throw new Exception("第"+i+"个元素不存在");  //抛出异常}else {return listElem[i] ;  //返回顺序表中的第i个元素}}//在线性表的第i个数据元素之前插入一个值为x的数据元素@Overridepublic void insert(int i, Object x) throws Exception {//0.1 满校验：存放实际长度 和 数组长度 一样if(curLen == listElem.length) {throw new Exception("已满");}//0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素if(i < 0 || i > curLen) {throw new Exception("位置非法");}//1 将i及其之后后移for(int j = curLen ; j > i; j --) {listElem[j] = listElem[j-1];}//2 插入i处listElem[i] = x;//3 记录长度curLen ++;}//删除并返回线性表中的第i个数据@Overridepublic void remove(int i) throws Exception {// 0.1 校验非法数据if(i < 0 || i > curLen - 1 ) {throw new Exception("位置非法");}// 1 将i之后向前移动for(int j = i ; j < curLen - 1 ; j ++ ) {listElem[j] = listElem[j+1];}// 2 长度减一curLen--;}//返回线性表在首次出现指定的数据元素的位序号，若线性表在不包括此元素，则返回-1@Overridepublic int indexOf(Object x) {for(int i = 0; i < curLen ; i ++) {if(listElem[i].equals(x)) {return i;}}return -1;}/*** 使用变量记录没有匹配到索引* @param x  要查找的数据* @return*/public int indexOf2(Object x){int j = 0 ;  //用于记录索引信息//while循环，循环条件是：j 小于线性表的长度，// 并且第j个数不等于要查找的数据，都满足才可进行循环。while (j < curLen && !listElem[j].equals(x)){//进行循环对其j进行++j ++ ;}// j 记录索引的数量if (j < curLen) {return j ;}else {return  -1 ;}}//输出线性表中的数据元素@Overridepublic void display() {for (int i = 0; i < curLen; i++) {//输出System.out.println(listElem[i]+" ");}}
}

        学生成绩类

package data.linear_table.test;import java.util.Scanner;//学生成绩表的系统中的数据，作为顺序表的数据元素listElem[i]
//学生成绩类
public class StudentNode {public int number ;     //编号public String name ;    //姓名public String sex ;     //性别public double english ; //大学英语public double math ;    //高等数学//无参时的构造函数public StudentNode() {this(0,null,null,0.0,0.0);}//有参数时的构造函数public StudentNode(int number, String name, String sex, double english, double math) {this.number = number;this.name = name;this.sex = sex;this.english = english;this.math = math;}//用于手动输入学生对应信息public StudentNode(Scanner sc) {this(sc.nextInt(),sc.next(),sc.next(),sc.nextDouble(),sc.nextDouble());}}

        主函数，功能调试；测试类

package data.linear_table.test;import data.linear_table.SqList;import java.util.Scanner;public class Student extends SqList {//主函数，用于功能调试public static void main(String[] args) throws Exception {int maxSize = 1000 ;        //设定最大存储空间Scanner sc = new Scanner(System.in);System.out.println("------------- 建立学生成绩顺序表--------------------");System.out.println("请输入学生的总数：");int n = sc.nextInt();                   //表示线性表的长度System.out.println("请按照学号、姓名、性别、大学英语、高等数学的顺序输入学生信息：");Student student = new Student(maxSize, n);          //建立顺序表while (true) {System.out.println("------------- 学生成绩管理系统--------------------");System.out.println("现有学生列表信息：");student.display();                                  //输出学生信息System.out.println("[1]查询\t[2]添加\t[3]删除\t[4]求平均分");int temp = sc.nextInt();switch (temp){case 1 :System.out.println("请输入要查询的学生的学号：");student.displayNode(student.get(sc.nextInt()));     //取出成功，则输出该学生的信息break;case 2:System.out.println("请输入需要增加的学生信息：");student.insert(new StudentNode(sc));                //在顺序表插入指定的信息break;case 3:System.out.println("请输入要删除的学生的学号：");student.remove(sc.nextInt());                       //删除指定学生的学号break;case 4:System.out.println("请输入你要查询全部平均分的科目名称：");String s = sc.next();double avg = student.avg(s);System.out.println(s+"的全班平均分为："+avg);}}}//按照顺序构造顺序表，其中参数maxSize指的是顺序表的最大存储容量public Student(int maxSize, int n) throws Exception {super(maxSize);Scanner sc = new Scanner(System.in);//创建含有n个数据元素的顺序表for (int i = 1; i <= n; i++) {StudentNode node = new StudentNode(sc);if (node != null) {//将录入的学生数据元素插入顺序表的表尾insert(node);} else {//若不成功就不计数i--;}}}//覆盖父类的get方法; 从顺序表中取出指定学号的学生信息public StudentNode get(int number) throws Exception {//遍历顺序表for (int i = 0; i < length(); i++) {//强转数据类型StudentNode node = (StudentNode) super.get(i);    //调用父类的get方法if (node.number == number) {return node;   //包含指定的学号，返回该学生的信息}}//否则抛出异常throw new Exception("学号" + number + "不存在");}//重载父类的insert方法，在顺序表的表尾插入一个学生信息public void insert(StudentNode node) throws Exception {//调用父类的insert方法。在顺序表尾部插入try {super.insert(this.length(), node);System.out.println("添加成功");} catch (Exception e) {e.printStackTrace();}}//覆盖了父类的remove方法public void remove(int number) throws Exception {//遍历顺序表for (int i = 0; i < length(); i++) {//取出第i项//强转数据类型StudentNode node = (StudentNode) super.get(i);if (node.number == number) {//找到了:进行删除super.remove(i);System.out.println("删除成功");return;}}//抛出异常throw new Exception("学号" + number + "不存在");}//重载父类的display()方法，输出顺序表中所有数据元素public void display() {//遍历顺序表for (int i = 0; i < length(); i++) {//强转数据类型try {StudentNode node = (StudentNode) super.get(i);displayNode(node);} catch (Exception e) {e.printStackTrace();}}}//输出一个数据元素信息public void displayNode(StudentNode node) {System.out.println("编号 =" + node.number +", 姓名 = " + node.name  +", 性别 = " + node.sex  +", 大学英语 = " + node.english +", 高等数学 = " + node.math +'}');}//求各门科的平均分public double avg(String name) throws Exception {//记录分数double sum = 0 ;//记录个数int num = 0 ;//判断是计算英语还是数学的全班平均分if (name.equals("大学英语")){//记录英语的平均分for (int i = 0; i < length(); i++) {//调用get方法取出指定学号的学生信息StudentNode node = (StudentNode) super.get(i);sum += node.english ;num++ ;}}else if (name.equals("高等数学")){for (int i = 0; i < length(); i++) {//调用get方法取出指定学号的学生信息StudentNode node = (StudentNode) super.get(i);//加全班的数学成绩sum += node.math ;num++ ;}}return sum/num ;}
}

           测试结果 

章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！

 如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！