(二) 算法设计题
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 //将其交换标志设为false isExchange = 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 ; } }
（三）填空题
线性表是一种最常用、最简单，也是最基本的____数据结构________
线性表由n个数据元素所构成的___有限序列_________，且数据类型相同
线性表可以用`顺序存储`和`___链式存储_________`两种存储结构来表示
链表可分为单链表、双向链表、____循环链表________、双向循环链表等
顺序表就是___顺序存储_________的线性表
顺序存储是用一组____地址连续________的存储单元依次存放线性表中各个数据元素的存储结构
线性表地址公式：__Loc(Ai) = Loc(A0) + i * c (第i的地址 = 第一个地址 + 第几个 * 存储单位)__________
在线性表中逻辑上相邻的数据元素，在__物理存储位置__上也是相邻的
算法__时间复杂度 _的高低直接反应算法执行时间的长短
_数据元素__是数据结构中讨论的基本单位，不同场合也叫结点、顶点、记录
__算法______是对特定问题求解步骤的一种描述，是指令的有限序列。其中每条指令表示一个或多个操作
对数据的操作包括：1.初始化：___创建、销毁____；2.数据操作：__增删改_____，3.数据使用：__查找、遍历__
采用链式存储方式存储的线性表称为___链表_________
若一个结点中只包含一个指针域，则称此链表为_____单链表_______
链表中每个结点包含存放元素值的___数据域_________和存放指向逻辑上相邻结点的____指针域________ 。
（四）简答题
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 ; //置顺序表的当前长度为0 listElem = new Object[maxSize]; //为顺序表分配maxSize个存储单元 } //将一个一存在的线性表置为空表 @Override public void clear() { curLen = 0 ; //置顺序表的当前长度为0 } //判断线性表的数据元素的个数是否为0 ，若为0则返回true,反之返回false @Override public boolean isEmpty() { return curLen == 0; } //求线性表中的数据元素的个数并返回值 @Override public int length() { return curLen; } //读取到线性表中的第i个数据元素并有函数返回其值。其中i的取值范围为：0 <= i <= length()-1 //若i 值不在此范围则抛出异常 @Override public Object get(int i) throws Exception { if (i < 0 || i > curLen -1 ) { //i 小于或者大于表长-1 throw new Exception("第"+i+"个元素不存在"); //抛出异常 }else { return listElem[i] ; //返回顺序表中的第i个元素 } } //在线性表的第i个数据元素之前插入一个值为x的数据元素 @Override public 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个数据 @Override public 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 @Override public 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 ; } } //输出线性表中的数据元素 @Override public 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 ; } }
测试结果
