2012级计算机基础（理科）复习提纲考试题型：单选题（30题，30分）、填空题（20题，20分）、判断题（15题，15分）、计算题（3题，15分）、简答题（4题，20分），共72题。
考试时间：90分钟第一章 计算机基础知识1．计算机的发展世界上第一台电子计算机ENIAC 1946年诞生于美国。
电子计算机的发展已经历了4代，4代计算机的主要元器件分别是电子管，晶体管，中、小规模集成电路，大规模或超大规模集成电路冯·诺依曼体系结构主要的设计思想：存储程序，并按程序顺序执行用于科学计算的计算机其特点是高速度、大存储量、高自动化和高精度2．数制转换（二、八、十六进制的整数，小数）在计算机内部，数据加工、处理和传送的形式是二进制。
机器指令以二进制形式存放在计算机内部在计算机中，负数是按补码进行存储和参与运算的。
二进制正数的反码、补码和原码一致二进制负数的补码是将其反码的最低位加1 +1111011 0 1111011-1111011 1 1111011 1 0000100 1 0000101计算机中，浮点数是为了表示小数，很小的数或很大的数，它由阶码和尾数两部分组成。
⏹ 二进制、八进制、十六进制的相互转换例. (123.75)10=( 1111011.1100 )2=( 173.6 )8=( 7B.C )16下列四个不同数制表示的数中，数值最大的是( )。
C（A ）二进制数01111111 （B ）十进制数219（C ）八进制数334 （D ）十六进制数DA3．信息在计算机内的表示⏹ 西文字符编码（ASCII ）7位编码，1000100符；在机器内部，一个字符的ASCII 码采用一个字节存储，最高位为0；例.字符A 的ASCII 码为65，则字符D 的ASCII 码为（68） 二进制为（1000100）例：字符中，ASCII 码值最大的是（ ）。
D（A ）字符9 （B ）字符 A （C ）空格 （D ）字符m ⏹ 汉字编码（国标码GB2312-80、机内码、字形码）汉字的处理流程： 汉字的输入、汉字的存储 、汉字的输出。
输入码 国标码 机内码 输出码国标码作为汉字交换码 用2个字节表示 每个字节最高位是0汉字的机内码是将汉字国标码的每个字节的最高位置为1转换而来的。
点阵字形编码存储容量的计算公式（以16×16点阵为例）：图1.4 汉字信息处理的流程图16×16*1/8=256/8=32 B用32×32点阵的汉字字形表示100个汉字，需要的存储空间是（12800 ）B⒋描述存储容量的单位1B=8bit 1KB=1024B=210B 1MB=1024KB=210KB 1GB=1024MB=210MB第二章硬件基础⒈计算机的基本工作原理计算机系统是指硬件系统和软件系统，硬件只能通过软件起作用。
硬件系统的五大部件及其功能输入设备、控制器、运算器、存储器和输出设备。
运算器的功能是进行逻辑运算和算术运算控制器的功能分析指令并发出相应的控制信号2. 常见硬件的常识CPU：主频、字长、MIPS（每秒钟能执行多少百万条指令）CPU包含运算器控制器 . 寄存器等。
微型计算机的核心部件是中央处理器微型机型号：Pentium Ⅲ 800 CPU的主频为800MHZCPU的主频=外频×倍频系数存储器由内存储器和外存储器组成存储器：按存取速度分为Cache(高速缓存)、内存（RAM和ROM）、硬盘、光盘、软盘RAM切断计算机电源后，存储器中的信息会丢失ROM和RAM构成主存储器存储器：存储时间、存储周期、存储容量硬盘容量计算总线：数据总线、地址总线、控制总线3.关于硬件的常见计算⏹硬盘容量计算硬盘记录面上的效记录区域为圆环状，例如圆环的外径（直径）为10cm，内径（直径）为5cm，磁道密度为100道/mm，则磁道数=（10-5）/2*100=250假设一个硬盘有40个盘片，盘片两面可写，每个盘片100个磁道，每个磁道10个扇区，每个扇区512个字节，该磁盘的容量是（）MB。
512B×10扇区×100磁道×2面×40 =40960000B/1024/1024=39.1MB第三章操作系统基础⒈操作系统的基本概念⏹操作系统的概念和功能操作系统的主要功能是管理系统所有的硬件资源和软件资源。
处理机管理、存储器管理、文件管理、设备管理、作业管理、用户接口计算机软件一般包括系统软件和应用软件⒉WindowsXP⏹文档与应用程序的概念⏹常见的文件类型：TXT、EXE、BMP、PPT、WA V、MP3、XLS、DOC、HTML等，并能知道创建这些文件的应用程序：规则：文件名.扩展名、不允许出现的字符 \ / ： * ? “ < > |⏹路径的概念路径是访问某个文件需要经历的子文件夹的顺序集合：路径：<盘符：>\<文件夹>\<子文件夹>\<文件名>⏹文件管理中的操作剪贴板和回收站的区别。
剪贴板是用于临时存放信息的一块内存区间。
回收站是用于存放计算机删除文件信息的一块硬盘区间。
文件查找时通配符（？和*）的用法。
什么是快捷方式在当前文件夹下建立“写字板”应用程序的快捷方式，命名为“写字板”。
磁盘格式化的作用（了解）第四章软件基础⒈算法⏹算法：是指解题方案的准确而完整的描述。
⏹算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
⏹算法的特点：有穷性、确定性、可行性、输入和输出算法的有穷性是指算法必须能在执行有限个步骤之后终止，必有一个(或多个)输出量⏹算法的评价：时间复杂度和空间复杂度算法的时间复杂度是指算法执行过程中所需要的基本运算次数⒉数据结构的基本概念⏹数据结构研究的三个方面：⏹数据的逻辑结构——数据元素之间的逻辑关系（集合、线性结构、树形结构、图形结构）⏹数据的存储结构——数据的逻辑结构在计算机存储器上的存储表示（顺序结构和链式结构）⏹数据的运算⒊线性表⏹线性表是由n（n≥0）个数据元素a1，a2，…，a i，…，a n组成的一个有限序列。
⏹非空线性表的结构特征：⏹且只有一个根结点a1，它无前件；⏹有且只有一个终端结点a n，它无后件；⏹除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
结点个数n称为线性表的长度，当n=0时，称为空表。
⏹线性表的两种存储结构：⏹顺序存储（顺序表）——结构简单，存储密度高，所有元素在逻辑上、物理上均是连续的。
空间大小分配固定。
每个元素的地址可以通过简单的计算获得，可以随机访问，但是插入和删除需要大量平移元素。
⏹链式存储（链表）——增加了指针域，存储密度小，所有元素在逻辑和物理上不一致。
空间大小可变。
只能顺序访问，但是插入和删除不需要平移元素，处理较快。
⒋栈与队列（特殊的线性数据结构）⏹栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
先进后出。
⏹栈的基本运算：①插入元素称为入栈运算；②删除元素称为退栈运算；③读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
⏹栈的应用若进栈序列为1，2，3，4，则（）是可能的出栈序列。
A．3，1，2，4 B．4，1，2，3C．2，4，1，3 D．2，4，3，1 答案：D⏹队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。
Rear指针指向队尾，front指针指向队头。
先进先出。
⏹队列的物理存储结构可以用顺序结构，也可以用链式结构。
⏹队列运算：①入队运算：从队尾插入一个元素；②退队运算：从队头删除一个元素。
⒌二叉树⏹二叉树的基本性质（1）在二叉树的第i层上，最多有2i-1(i>=1)个结点；（2）深度为h的二叉树最多有2h-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的完全二叉树的深度为⎣log2n⎦+1设一棵完全二叉树共有567个结点，该二叉树的叶子结点有（284 ）个。
⏹二叉树的遍历（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
中序序列：EHBACJFD后序序列：HEBJCDFA⒍查找与排序⏹查找⏹顺序查找⏹当线性表为无序表，则无论其采用顺序存储结构或链式存储结构，均可采用顺序查找；⏹无论线性表有序或无序，当其采用链式存储结构，只能采用顺序查找。
⏹顺序查找的比较次数：最少1次，最多n次⏹二分查找⏹只适合顺序存储的有序表；⏹二分查找的比较次数：最少1次，最多⎣⎦1+nlog2⏹排序⏹冒泡排序⏹算法：①扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；②除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；③重复上述过程，直至某一趟冒泡过程中没有发生交换。
对于长度为n的线性表，冒泡排序最多需要对表扫描n-1遍；最坏情况下需要比较的次数为n*(n-1)/2有一数字序列{1，2，3，4, 5}，现要用冒泡排序对其按数字降序排序，试写出每一轮冒泡排序后的结果。
⏹选择排序⏹算法：①扫描整个线性表，从中找出最小的元素，与第一个元素交换；②除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；③重复上述过程，直至子表为空。
对于长度为n的线性表，选择排序最多需要对表扫描n-1遍；需要比较的次数为n*(n-1)/2第五章多媒体基础⒈多媒体技术的主要特性（多样性、交互性、集成性、实时性、数字化）多媒体数据的特点: 数据量大、数据类型多、数据类型间区别大、输入和输出复杂2．图形与图像⏹图形与图像的概念⏹图像的两个属性：分辨率和颜色深度（位深度）图像分辨率是指：用像素表示的数字化图像的实际大小dpi每英寸像素点颜色的三要素包括明度、色调、饱和度⏹静态图像的存储容量计算公式（非压缩）：一个分辨率为640×480的摄像头，我们称它具有30万像素。
表示一个分辨率为640×480的24位真彩色图像，需要存储空间900 KB。
640×480×24（颜色深度）/8=921 600B=900KB⏹多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分类为无损压缩编码，有损压缩编码和混合编码。
一副640×480的JPEG数字图像，颜色深度是24位，文件大小是64KB，该数字图像的压缩比是（14 ）倍。
640*480*24/8/(64*1024)=14⏹常见的数字图像文件格式：JPG、GIF、BMP4．音频信息⏹将模拟音频信号转换为数字音频信号，这个过程主要包括采样、量化和编码。