文章图片
(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 ; //# }

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为数组的长度。 }

package data.linear_table.csdn; public class Demo02_desc { public static void main(String[] args) { int[] value = https://www.it610.com/article/{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 ; } }

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.影响一个程序的执行时间的主要因素有如下几个方面
文章图片
算法本身所用的策略

文章图片
问题规模即处理问题时所处理的数据元素的个数

文章图片
程序设计所采用的语言工具

文章图片
编译程序所产生的机器代码质量

文章图片
计算机执行指令的硬件速度

文章图片
程序运行的软件环境

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 ; } }

推荐阅读

• 

  为什么许多发烧友认为beats耳机性价比并不高,还有许多人想买呢？
• 

  迪士尼可以带罐装饮料吗
• 

  有个性的个性签名短句 个性网个性签名短句
• 

  减肥时期选择什么食物更合理？
• 

  为什么陌陌、百合等同城婚恋网站上有那么多诈骗的人？
• 

  女性灵活就业人员55岁退休，个人账户余额10万，养老金有多少？
• 

  看门狗Win10玩一会闪退怎么解决 看门狗闪退解决方案Win10
• 

  油焖小龙虾的正确做法
• 

  柜门铰链价格多少钱？如何选购柜门铰链？
• 

  好看的迪士尼动画电影 好看的动画电影排行榜
• 

  陡坡缓降是什么意思 陡坡缓降的解释
• 

  仙人掌的花语和传说 仙人掌的花语和传说有哪些
• 

  荒野大镖客2如何找女人 大镖客2怎么找妞
• 

  封丘直播设备，封丘直播设备维修电话
• 

  软件测试自动化难度分析,简述软件测试自动化的意义和作用
• 

  mongodb的安装配置 mongodb安装安装
• 

  儿童牛奶哪个牌子营养丰富？推荐几款好吸收儿童牛奶
• 

  多肉植物都有哪些品种呀,怎么样？
• 

  小商家有必要开叶子类目定向 叶子类目定向什么意思
• 

  ios14王者荣耀闪退解决方法

• 数据结构|数据结构— 数组、特殊矩阵、稀疏矩阵
• 数据结构|数据结构—栈的应用举例【算术表达式求值转换、后缀表达式求值计算】
• 被LeetCode锤爆的日子|【LeetCode】 梦的开始---两数之和
• leetcode|【LeetCode】set集合+哈希表+快慢指针
• 图解数据结构排序全面总结(下)
• dbcp|这份新年豪礼面试锦囊，真舍不得给你们！
• c语言|哈夫曼树和哈夫曼编码
• hash|这一篇，带你十分钟深入理解HashMap源码
• 散列表|leetcode哈希表java