大学计算机复习大纲-课件

期末复习－及考试相关关于考试1.考试时间：星期三8:00-9:502.答案全部写在答题纸上，否则不得分，并写明任课教师、班级、学号和姓名。3.考试成绩占总成绩60%4.考试题型：

选择、填空、判断、综合答疑和上机时间：12月24日3、4和5、6节；地点：原上机实验机房复习大纲基础知识部分知识点计算工具的发展历史；计算机的发展历史；（第一台？按什么定的四个阶段？每个阶段的特点？……）图灵、冯.诺依曼在计算机发展史上的贡献（图灵机？程序存储思想？）；计算机的应用有哪些方面？（天气预报？人机对战如国际象棋）计算机的发展趋势数和进制（重点二进制）字符编码（ASCII码）、汉字编码（P70）数据的存储单位计算机的基本组成及工作原理（存储程序和程序控制P75）微机的主要性能指标（字长、运算速度、内/外存容量等）计算机指令的概念（操作码、地址）（P80）存储器的原理及其种类及各自特点（地址？内存－寄存器和cache？外存？）计算机系统的组成（计算机的五大部件？）操作系统的概念、功能（P89）和常见操作系统；复习大纲问题求解及算法问题求解的思路（第一步是什么？数学建模）和策略什么是算法？P121，算法的特征和描述方式。从哪些方面可对算法进行评价分析（首先是正确性，时间复杂性—O阶表示，空间复杂性）典型算法及其思想穷举法、递推法、递归法、贪心法搜索问题的要素及计算机搜索中的思想典型的查找方法及思想 顺序查找、折半查找（衡量查找算法的好坏是平均查找长度）排序算法的思想选择排序和冒泡排序复习大纲数据及数据结构1.数和数据的概念2.数据类型的概念3.数据结构的概念4.数据的逻辑结构及其种类（集合、线性、树状、图）5.数据的物理结构及其种类（又叫逻辑结构：顺序和链式）6.数据结构和算法的关系7.典型线性结构及其特点：队列和栈复习大纲计算机程序计算机程序的概念P223计算机语言分类（P220，机器、汇编、高级；助记符？面向硬件？）；程序基本结构（顺序、分支、循环）数据类型的概念在程序中的作用；P232数据管理技术的发展历史数据库的概念数据库管理系统中常用的数据模型（P260，关系、层次、网状）数据库管理系统的功能典型的数据库管理系统（ACCESS、SQLServer、Oracle、MySQL、FoxPro和Sybase等）了解结构化查询语言SQL（P262）复习大纲计算机网络知识点计算机网络定义和基本功能（P284）计算机网络的分类（按规模划分局域网、城域网、广域网）网络体系结构：OSI、TCP/IPOSI的七层（注意顺序）TCP/IP中应用层的常用协议IP地址编码方案：IPv4、IPv6（32，128）域名命名机制、常用顶级域名常用网络设备的名称及功能（网卡、交换机、路由器）网络应用模式（C/S、B/S，P309，316或P275）信息安全的概念什么是病毒及其特征？什么是木马？（P330）信息安全技术：防火墙（P328）……什么是数据加密技术？了解云计算（P349）、物联网（P355）和大数据（P358）等相关知识互联网常识（电子邮件地址格式，互联网通信使用的协议，传输介质，黑客？）一、模拟题：单项选择1.在计算机内部，所有信息都是以（）表示的。 A.ASCII B.机内码 C.十六进制 D.二进制2.计算机的硬件主要包括中央处理器（CPU）、存储器、输出设备和（）。 A.键盘 B.鼠标 C.输入设备 D.显示器3.在计算机运行时，把程序和数据一样存放在内存中，这是1946年由（）领导的小组正式提出并论证的。（P54页） A.图灵 B.冯•诺依曼 C.布尔 D.爱因斯坦4.计算机存储容量的基本单位是（） A.二进制位 B.字节 C.字 D.汉字5.在微型计算机中，下列设备属于输入设备的是（） A．打印机 B.显示器 C.键盘 D.硬盘6.在下列设备中，属于输出设备的是（） A.硬盘 B.键盘 C.鼠标 D.打印机控制器、运算器7.计算机从其诞生至今已经历了四个时代，划代的原则是根据（） A.计算机所采用的的电子器件 B.程序设计语言 C.计算机的存储量 D.计算机的运算速度8.一台计算机的字长为16位，说明它()。 A．可一次进行运算或传送的二进制数的最大位数是16位 B．可表示的最大数值是2 C．能处理最多为16位的十进制数 D．能处理的字符串最多由16个英文字母组成9下列关于ASCII码说法错误的是()。 A.8位扩展ASCII码可表示128个不同字符 B.ASCII码有7位ASCII码和8位ASCII码两种 C.7位标准ASCII码规定其最高位为0 D.ASCII码是AmericanStandardCodeforInformationInterchange的缩写7位标准ASCII码规定其最高位为0；278位扩展ASCII码规定其最高位为1；2810.计算机能够应用于各个领域，体现了计算机的()。 A.通用性强 B.存储容量大 C.运算速度快 D.工作自动化11.下列程序段的时间复杂度为（）。 i=1; sum=0; for(i=1;i<=n;i++)

sum=sum+i; A.O(1) B.O(log2n) C.O(n) D.O(n2)12.计算机求解问题过程中，算法策略设计要解决的问题是（）。 A.将问题抽象为一个数学问题 B.选择较优的算法策略 C.设计算法具体如何执行的控制结构 D.用某种程序设计语言编写实现算法的程序13.若有如下图所示的四个城市及其路径长度，旅行商从城市A出发，到每个城市旅行，途中只能经过每个城市一次，最后回到城市A，则采用贪心算法时，求得的路径长度是（）。 A.13 B.14 C.13或14 D.19穷举法所有路径组合（n-1）!每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短。14.问题求解过程中的第一步就是要（）。 A.数学建模 B.算法设计 C.数据结构设计 D.控制结构设计15.若要对某个序列按升序排序，则使用冒泡排序时，若依次从前往后比较，则第一趟被排出的数是（）。 A.最小数 B.最大数 C.中间数 D.以上都不对冒泡排序：对排序数组元素中相邻的两个元素进行比较，将大的放前，小的放后--递减排序(或者是将小的放前，大的放后--递增排序)。再重复上述过程，一直进行到数组最后一个元素。时间复杂度为O(n2)12，8，5，98，12，5，98，5，12，98，5，9，12如果有n个数，就要进行n-1次比较；每次比较，小数上升，大数下沉。16.下面关于线性表的叙述中，错误的是（）。 A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于插入和删除操作17.栈的插入删除操作必须在表的（）进行 A．一端 B．两端 C．中间 D.任意位置18.程序设计中的sum=sum+i中等号代表的是（） A.判断相等的运算 B.赋值运算 C.求和运算 D.读写操作19.循环结构最适合解决下面哪一类问题？ A.各种选择性问题 B.跳跃性问题 C.真伪判断问题 D.重复性问题20.将计算机用于天气预报，是在（）方面的应用。 A.计算机辅助 B.数值计算 C.自动控制 D.人工智能21.IP地址是由小数点隔开的四个十进制数组成，下列属于IP地址的是（）栈是一种只在表尾进行插入删除操作的线性表，队列只能表的一端进行插入，另一端进行删除操作。22.防火墙（Firewall）是（） A.用于预防计算机被火灾烧毁 B.对计算机房采取的防火设施 C.是Internet（因特网）与Intranet（内部网）之间所采取的一种安全措施 D.用于解决计算机使用者的安全问题23.计算机能直接执行（） A.英语程序 B.机器语言程序 C.十进制程序 D.高级语言源程序24.（）语言是用助记符代替操作码、地址符号的面向机器的语言。 A.程序 B.汇编 C.机器 D.高级25.计算机的应用领域包括（）计算机辅助系统和计算机网络与通信。 A.高速运算、网络管理 B.科学计算、信息管理 C.过程控制、人工智能 D.卫星发射、导弹控制26.程序的开发步骤中不包括()。 A.编辑（编写代码） B.编译链接 C.运行程序 D.撰写文档27.关于计算机语言，下列说法不正确的是()。 A.所谓“高级语言”和“低级语言”是指其和机器硬件的相关程度，不涉及机器硬件的语言为高级语言，而与机器硬件相关的语言则为低级语言。 B.高级语言编程效率高是因为其可用大粒度积木块来构造程序，比一行行语句、一条条指令来编程效率高出很多。 C.所有源程序最后都需被转换为汇编语言程序，机器才能够执行。 D.低级语言程序执行效率高是因为低级语言直接面向硬件。28.以下关于算法的描述中不正确的是（）。 A.算法中每一个步骤的含义都应该是确定的。 B.算法中每一个步骤都应该能有效的执行。 C.正确的算法应在有限的步骤内结束。 D.正确的算法都必须有输入和输出。29.网上“黑客”是指（）的人。 A.总在晚上上网 B.匿名上网 C.不花钱上网 D.在网上私闯他人计算机系统二、模拟题：填空题汉诺塔问题中，如果要把5个盘子按要求从a柱移动到c柱，则共需要移动_____次盘子。设n为圆盘数目，移动次数是f(n)，则：f(1)=1f(2)=3f(3)=7……f(n)=2^n-1。abcabc2.电子计算机能够自动地按照人们的意图进行工作的最基本思想是_______。P743.通常将计算机程序设计语言分为机器语言、___________、高级语言三种类型。4.已知a=-1，则执行下列语句后b的值为____________。 b=-1; if(a>-2) b=1; elseb=0;5.数据管理经历了人工管理阶段、__________阶段和__________阶段。P2586.数据库管理系统通常由数据定义语言、________________、______________和通信功能程序组成。P2607.传统的计算机网络，按照计算机分布的地理位置划分，一般分为：___________、____________和城域网。P2868.IPV4的地址长度是_____位的，采用了点分十进制表示法。IPV6的地址长度是_____位的。9.域名系统的结构是一种分层次结构。每个域名是由几个域组成的，域与域之间用小圆点“.”分开，最末的域叫___________，其它域的叫子域。P31110.若有序列{2，5，6，10，15，21，26，30，56，78}，若用折半查找算法找30，则需要比较________次。25610152126305678

25610152126305678哪些数需要查找1次、2次、3次或4次？二分查找又称折半查找，要求待查表为有序表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。11.若使用冒泡排序对n个数降序排序，则最多需要排________趟（轮）。在最好的情况下整个排序只进行一轮，比较n-1次。在最坏情况下，需要比较n-1轮，每轮比较的次数分别是n-1,n-2,…3,2,1，总的比较次数为：n(n-1)/2时间复杂度为O(n2)12．已知斐波那契数列的递推公式如下，则第20项的值为_______。

13.如果用穷举法来猜测由8位数字组成的银行卡密码，则有_______种解。14.若用穷举法求解0-1背包问题，则对于有7个物品的问题，所有可能解决方案共有_______种。10827－1三、模拟题：判断题N-S图是一种用流程线表示执行顺序的算法描述方法。2.数学建模是问题求解的第一个步骤。3.一个优秀的算法应该对于一切合法的输入数据，算法得到的结果都是正确的。4.计算数列时，由第一项开始一直求到第n项的过程称为递归。5.折半查找算法的效率与顺序查找算法相当。折半查找的速度比顺序查找要快，若n=127，顺序查找的平均查找长度为64，而折半查找的平均查找长度为6。1973年，美国学者I.Nassi和B.Shneiderman提出了一种在流程图中完全去掉流程线，全部算法写在一个矩形阵内，在框内还可以包含其他框的流程图形式。即由一些基本的框组成一个大的框，这种流程图又称为N-S结构流程图（以两个人的名字的头一个字母组成）。N-S图包括顺序、选择和循环三种基本结构。6.折半查找算法要求被查找的序列必须是有序的。7.选择排序时，总是相邻的两个数不断的比较，逆序则交换顺序。如果是1000个数则需要比较：999+998+997+996+……+1＝499500次时间复杂度为O(n2)

首先在所有数据（保存于数组中）中找出最小值，与第一个数组元素交换；接着在余下的数组元素中（不包含第一个数组元素）再找出最小值的元素，与第二个数组元素交换；如此循环，一直到排完最后一个元素。8.线性表在物理存储空间中一定是连续的。9.线性表在使用链式存储时逻辑上相邻的元素未必在存储的物理位置次序上相邻。10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种先进后出型结构。11.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。12.排队买票属于栈的实例。错误。线性表有两种存储方式，顺序存储和链式存储（不需要连续的）。正确。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也一定相邻。但链式存储不一定。正确。栈是一种只在表尾进行插入删除操作的线性表，队列在表的一端进行插入，另一端进行删除操作。错误。后半句不对，与栈不同，队列是一种先进先出的线性表。错误。属于队列13.资源共享可以分为硬件资源，软件资源和数据资源三个方面。（P285）14.网络协议是一种特定的数据格式，两个通讯的主机或者程序，要支持同样的网络协议才能通信。（P290）15.云存储和云安全都是云计算概念的应用。（P349）16.普适计算是指无所不在，随时随地进行，与环境融为一体的计算。（P349）四、模拟题：综合题1.简述计算机发展的历程，及每一代计算机的主要特点。2.什么是操作系统？它在计算机中的主要功能有哪些？3.什么是人工智能？能否举例说明人工智能在生活中的应用。4.衡量计算机的主要性能指标有哪些？5.公元5世纪末，我国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何。请写出该问题所建的数学模型（请写出解决该问题的算法，表达方式不限）。（P132）穷举对象：公鸡x、母鸡y、小鸡z穷举范围：x、y、z都必须是整数； 0<x<20，0<y<33，3≤z<99并且zmod3=0判定条件： 5x+3y+z/3=100 x+y+z=100四、综合题6.一