第三节 计算机硬件的主要技术指标 1.机器字长 CPU 一次能处理数据的位数 与 CPU 中的 寄存器位数 有关。 2.运算速度 吉普森法：第一种，静态水平：直接拿程序清单里面来计算，不用管实际运算。第二种：程序执行起来，计算一下实际执行中出现的频率，动态水平（更准确）。 3.存储容量

第二节 计算机的基本组成 1.冯诺依曼计算机的特点 （1）计算机由五大部件组成：运算器、存储器、控制器、输入设备、输出设备。 （2）指令和数据以同等地位存于存储器，可按地址寻访； （3）指令和数据用二进制表示； （4）指令由操作码和地址码组成； （5）存储程序； （6）以运算器为中心。 图1 冯诺依曼结构（实线是数据传输，虚线是地址传输） 2.硬件系统的改进 问题1：以运算器为中心，导致运算器成为系统的瓶颈。 问题2：不具有层次化的特征。 改进1：以存储器为中心的计算机硬件框图 图2 以存储器为中心的计算机硬件框图…

第一节 计算机系统简介 1.现代计算机的多态性 物联网系统：把感应器嵌入和装备到电网、铁路、桥梁、隧道、公路、建筑、供水系统、大坝、油气管道等各种物体中，并且被普遍连接，形成所谓“物联网”，然后将“物联网”与现有的互联网整合起来，实现人类社会与物理系统的整合，形成智慧地球。 2.计算机软硬件概念 （1）计算机系统由硬件和软件两部分组成。软件又分为系统软件和应用软件。 3.计算机的层次结构 图1 计算机物理结构 图2 计算机的层次结构 计算机体系结构：程序员（机器语言）所见到的计算机系统的属性。概念性的结构和功能特性…

一、判断题 1-1若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。(2分) F 1-2对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。(2分) F 1-3n!是O(n^n)的。(2分) T 1-4对一棵平衡二叉树，所有非叶结点的平衡因子都是0，当且仅当该树是完全二叉树。(2分) F 1-5无向连通图至少有一个顶点的度为1。(2分) F 二、选择题 2-1 对一组数据{2，12，16，88，5，10}进行排序，若前三趟排序结果如下：第一趟排序结果：…

第十一讲：散列查找 11.1 散列表 11.1.1 散列的基本思路 编译处理时，设计变量及属性的管理： （1）插入：新变量定义。 （2）查找：变量的引用。 编译处理中对变量管理：动态查找问题。 利用查找树进行变量管理，由于两个变量名（字符串）比较效率不高。 我们已知的查找方法： （1）顺序查找，复杂度O(N)； （2）二分查找（静态查找），复杂度O(logN) （3）二叉搜索树，复杂度为O(h)，其中h为二叉查找树的高度； （4）平衡二叉树，复杂度为O(logN)。 如何快速搜索到需要的关键词呢？如果关键词不方便比…

第十讲：排序（下） 10.1 快速排序 10.1.1 算法概述 策略：分而治之。 下面举个例子，假如一组数为13/81/92/43/65/31/57/26/75/0，我们对其进行排序。那么首先选择出一个主元，这里我们选择为65，那么将这组数的其他成员分为了两组，一组是小于主元的13/43/31/57/26/0，一组是大于主元的81/92/75.然后将其递归处理，两边各选一个主元再进行分组……倒数第二步的时候，我们在第一步选择出来的主元左侧已经排好了顺序，右侧也排好了顺序，这样将它们放在同一个数组中，就完成了排序。 …

第九节：排序（上） 9.1 概述 对于之后应用到的一些说明： （1）void X_Sort(ElementType A[], int N) X为排序名称。 ①大多数情况下，为了简单起见，讨论从小到大的整数排序。 ②默认N为正整数。 ③只讨论基于比较的排序（>=<都是有定义的）。 ④只讨论内部排序（一次性可以写入内存，然后只在内存里面的数据排序）。 ⑤稳定性：任意两个相等的数据，排序前后的相对位置不发生改变。 没有一种排序是任何情况下都表现最好的！！！ 9.2 简单排序算法 9.2.1 冒泡排序 在一次排…