浙江省计算机3级考试大纲

浙江省高校非计算机专业学生计算机等级考试（三级）大纲 基本要求： (1) 掌握典型微型机的组成及工作原理；(2) 具有一般微机接口技术；(3) 具有用汇编语言进行程序设计的能力；(4) 掌握数据结构与算法的基础知识；(5) 熟悉操作系统的基本知识；(6) 熟悉数据库的基本知识；(7) 了解计算机网络的初步知识；(8) 掌握软件工程的基本方法；(9) 能解决偏软或偏硬方面的基本应用问题。 以下一、二、三部分为必考内容，四至八部分由考生任选两部分：一、微机系统组成与工作原理1. 算术运算与逻辑运算基础；* 计算机中数的表示方法及算术运算（带符号数表示方法，定点数与浮点数，定点数补码运算，二进制数编码）；* 逻辑运算（基本逻辑功能，复合逻辑功能，逻辑部件）；* 逻辑电路（组合逻辑电路，时序逻辑电路）。2. 典型微处理器组成及工作原理；* CPU结构与功能（运算器ALU，通用和专用寄存器，控制器）；* 指令系统（指令格式及常用指令类型，寻址方式，指令的执行过程）；* 80i86系列处理器组成及原理（内部功能结构，寄存器结构，工作过程（指令流水概念）等）；* 80i86系列微处理器指令系统（具体指令格式，种类，寻址方式，（实地址，保护方式）及物理地址形成）。3. 存储器；* 内存储器（半导体存储器基本结构，动态存储器，刷新，静态存储器，CACHE，只读存储器（PROM，EPROM，EEPROM），存储器控制电路地址译码）；* 外存储器（磁盘存储器，磁记录方式，软盘及硬盘驱动器，光盘存储器）；* 存储层次(二级存储层次，cache、内存、硬盘三级存储层次)。4. 微机总线；* 总线结构，总线连接方式，总线类型* 总线仲裁5. 输入输出传送方式及基本接口；* I/O寻址方式；* I/O传输方式：寻址，无条件；* 中断INT（中断处理基本过程，内中断，中断控制器8529）；* 直接存储器存取DMA（DMA传输方式基本概念，DMA传输控制，DMA传输过程，DMA控制器8327）；*输入输出接口控制电路（I/O译码；读、写控制；等待(READY)电路）。二、数据结构与算法1. 数据结构的基本概念及有关术语数据、数据元素、数据的逻辑结构、数据的存储结构、数据类型、算法和算法分析、算法复杂度。2. 基本数据结构及其操作基本数据结构：线性表、数组、串、栈、队列、树和图：* 线性表的定义、逻辑结构特征、存储结构（顺序存储、链式存储）、插入、删除、顺序查找算法；* 数组的定义、逻辑结构的特征、数组的顺序存储；* 串的定义、逻辑结构的特征、赚的顺序存储；* 栈的定义、逻辑结构特征、存储结构、进栈、出栈算法；* 队列的定义、逻辑结构特征、存储结构、循环队列、进队、出队算法；* 二叉树的定义、性质、存储结构、二叉树的遍历，二叉排序树，哈夫曼树；* 图的定义、存储结构、图的遍历。3. 检索方法顺序查找、二分查找、索引查找、Hash查找。4. 排序方法选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、快速排序、堆排序；三、操作系统1. 操作系统的类型和功能（批处理系统、分时系统和实时系统）；2. 进程管理：进程的描述、进程控制、进程同步和通信、进程调度；3. 作业管理：作业调度、作业控制；4. 存储管理：连续分配、离散分配、虚拟存储器；5. 设备管理：缓冲管理、设备分配、设备处理；6. 文件管理：文件和文件系统、文件的结构、文件存储空间的管理、目录管理；7. 典型操作系统介绍（DOS 、WINDOWS、 UNIX / LINUX）。四、计算机网络1. 计算机网络的分类与功能：星型、树型、总线型、环型和网络型网络拓扑结构；2. 数据通信基础：传输介质、多路转换器、调制解调器、交换器；3. 计算机网络体系结构：层次结构和协议的基本概念OSI?RM；OSI 7层协议（物理层，链路层，网络层，传输层，会话层，表示层，应用层）；4. 局域网概念：CSMA/CD总线网、令牌传送总线网、令牌环、FDDI 100BASE-T100VG-AnyLAN；5. 网络互连：网络互连设备（网桥、路由器、集线器），网络互连协议TCP/IP（telnet,ftp,http,smtp,pop）；6. 典型局域网络操作系统介绍（Novell，Windows NT）。五、接口技术1. 简单I/O接口（缓冲器、锁存器）；2. 总线；* 计算机三总线结构：DBUS ABUS CBUS；* 常用微机总线标准：STD IEEE-488 ISA(PC AT)RS-232C等。3. 并行接口（简单并行接口，可编程并行接口，Centronics并行接口标准）；4. 串行接口（一般串行接口，可编程串行接口，RS-232 C串行接口标准）；5. 人-机接口（键盘显示接口，CRT控制器接口）；6. D/A及A/D转换器接口（工作原理，芯片及其与处理器的接口）；7. 传感器基本知识（工作原理，类型，与微机的接口）。六、汇编语言1. 汇编语言的功能和特点；汇编语言的功能和特点，汇编语言程序上机开发过程。2. 指令格式；无操作数指令，单操作数指令，双操作数指令，三操作数指令，单字节指令，双字节指令，多字节指令。3. 典型微机指令系统（8086/8088）；* 8086/8088指令系统寻址方式：立即寻址，直接寻址，寄存器寻址，寄存器间接寻址，变址寻址，基址加变址寻址；* 8086/8088指令系统指令分类：数据传送和输入输出指令，算术运算指令，逻辑运算指令，控制转移指令，串操作指令和处理器控制指令。4. 汇编语言与汇编程序（8086/8088）；* 汇编语言语句格式：指令性语句，指示性语句（伪操作语句）；* 基本伪操作：符号定义，数据定义，段定义，过程定义，模块外部调用（模块通信）；* 宏指令和宏汇编：宏定义，宏扩展，带参数的宏，嵌套宏定义和宏调用，基本宏操作伪指令和操作等。5. 汇编语言程序设计基本方法：顺序结构，分支结构，循环结构，子程序。七、数据库系统1. 数据库的基本概念数据、数据模型、数据库、数据库系统、数据库管理系统；2. 关系数据库基础知识关系数据模型、关系运算、关系数据标准语言SQL；3. 关系数据库规范化：1NF、2NF、3NF、BCNF；4. 应用数据库的设计技术概念结构设计（E-R方法）、逻辑设计、物理设计；5. 典型DBMS介绍SQL SERVER、ORACLE、SYBASE 等。八、软件工程1. 软件工程的目的与意义软件危机、软件生命周期、软件工程；2. 结构化分析（SA）方法系统逻辑模型、数据流程图、数据字典；3. 结构化设计（SD）方法* SD方法的概念和原理（模块化、抽象、信息隐蔽、模块独立性）；* 图形工具（层次图、HIPO图）；* 面向数据流的设计方法（变换分析、事务分析）。4. 详细设计* 结构化程序设计方法；* 详细设计工具（程序流程图、N_S图、PAD图、判定表、判定树、伪码等）；* Jackson程序设计方法。5. 软件测试。* 软件测试的目的；* 软件测试方法（黑盒法、白盒法）；* 软件测试的步骤（模块测试、系统测试、验收测试等）；* 设计测试方案（逻辑覆盖、等价划分、边界值分析、错误推测等）。6. 软件维护软件维护的定义、可维护性。7. 原型法的基本概念。8.面向对象方法的基本概念和三种模型（对象模型、动态模型、功能模型）。9.软件质量的主要因素。 明：（1）考生应将一至二题的答案涂写在答题卡上，将第三题答案写在答卷纸上，否则作无效处理； （2）所有题目均为必答题； （3）请将你的准考证号的后四位填写在答卷的右下角指定位置内； （4）考试时间为120分钟。 一、数据结构基础（30分） 1、树的固有特性是（C） A、嵌套 B、顺序 Ｃ、递归 Ｄ、选择 2、在一个单链表中，已知q结点是p结点的前驱结点，删除p结点的语句（B） A p→next= p→next→next； B q→next= p→next； C q→next=nil；delete（p） D q = p→next； 3、一个初始为空的栈，S是入栈，P是出栈，操作序列合法的是（C） A、PSSSPP B、SSPPPP C、SSPPSP D、PSPSPS 4、循环队列用数组A[m]存放元素，头尾指针为front和rear，则当前队列中有的元素个数为（B） A． rear – front + 1 B． (rear – front + 1 + m ) mod m C． rear – front - 1 D． rear – front 5、算法的查找效率一般是一平均查找代价来衡量的，比如线性查找是O（N），二分查找是O（logN），那么Hash查找的期望代价是（C） A O (㏒ n) B O(n) C O (1) D (n㏒ n) 6、树型结构中父子之间的联系是（B） A 1：1 B 1：N C M：N D N：1 7、设a，b是一二叉树的两结点，在中序遍历时a在b前面的条件是（B） A a在b右边 B a在b左边 C a是b的祖先 D a是b的子孙 8、对线性表进行二分查找时，要求线性表必须是（C） A顺序存储 B链式存储 C 顺序存储且元素有序 D 链式存储且元素有序 9、下列数据哪一组符合最大值堆的定义（B） A、（42，40，45，55，80，85） B、（85，55，80，45，40，42） C、（85，45，80，55，40，42） D、（42，55，45，40，80，85） 10、在内部排序中，排序时不稳定的是（C） A 插入排序 B 冒泡排序 C 快速排序 D 归并排序 11、n个结点的树边数最多是（C） A．n　　Ｂ．n*(n-1)　　Ｃ．n-1　　Ｄ．n*(n-1)/2 12、对（541，132，984，746，518，181，946，314，205，827）进行从大到小排序，用直接选择法，先选最大元素，第一趟的结果是（B） A (181,132,314,205,541,518,946,827,746,984) B (541,132,827,746,518,181,946,314,205,984) C (205,132,314,181,518,746,946,984,541,827) D (541,132,984,746,827,181,946,314,205,518) (荣珏注解：按此题含义，应该是从左边开始从小到大排序，然后选B) 13、对（541，132，984，746，518，181，946，314，205，827）进行从大到小排序，用快速排序法（以中间元素518为基准），第一趟的结果是（C） (选项同上题) (荣珏注解：按此题含义，应该是从左边开始从小到大排序，然后选C) 14、哈夫曼树中，外部结点的个数比内部结点的个数（B）A．相等　 Ｂ．多1 Ｃ．少一 Ｄ．无法确定 (荣珏注解：按此题含义，外部结点的含义应该是叶子结点) 15、在查找数中插入一个新结点，总是插入到（A）结点下面。 A、根 B、左子树 C、右子树 D、叶 （荣珏注解：查找数应该是查找树。此题含义不清，非要选择，只能选择A） 16、n个结点的单链表中查找值为x的结点，在查找成功的情况下，需要平均比较（C）个结点。 A．n/2　　Ｂ．n　　Ｃ．（n+1）/2　　Ｄ．(n-1)/2 17、一棵顺序存储的完全二叉树每个结点占用2个存储单元，已知第三个结点的地址为1000，若其左子女存在，其地址最可能是（B） A．2000　　Ｂ．1006　　Ｃ．2004　　Ｄ．2008 18、数据结构（D，R），D={di |1<=I<=7}，R={,,,,,}则此结构的图形是（C） A．线性表　　Ｂ．图　　Ｃ．二叉树　　Ｄ．队列 （荣珏注解：最准确的答案应该是度为2的树，但根据下一个小题的意思，应该是二叉树） 19、对上题图形采用（B）遍历方法，可得到序列（d1,d2,d3,d4,d5,d6,d7）？ A．先序　　Ｂ．中序　　Ｃ．后序　　Ｄ．深度优先搜索 20、已知一棵数的2种遍历结果，哪个组合能唯一确定一棵二叉树（A）？ A．先序，中序　　Ｂ．先序，后序　　Ｃ．层次