下载文档原格式
2015年硕士复试专业综合笔试复习大纲010 计算机科学与信息工程学院081203 计算机应用技术复试科目：专业综合（含操作系统、计算机网络）复习大纲：Ⅰ．考查目标自命题计算机学科专业基础综合考试涵盖操作系统、计算机网络二门学科专业基础课程。
要求考生系统地掌握上述专业基础课程的概念、基本原理和基本方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
Ⅱ．试卷结构及题型操作系统占50%计算机网络占50%单项选择题简答题综合应用题Ⅲ．考查内容操作系统[考查目标]1．掌握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。
2．掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。
3．能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法。
一、操作系统概述（一）操作系统的概念、特征、功能和提供的服务（二）操作系统的发展与分类（三）操作系统的运行环境1．内核态与用户态2．中断、异常3．系统调用（四）操作系统体系结构二、进程管理（一）进程与线程1．进程概念2．进程的状态与转换3．进程控制4．进程组织5．进程通信共享存储系统；消息传递系统；管道通信。
6．线程概念与多线程模型（二）处理机调度1．调度的基本概念2．调度时机、切换与过程3．调度的基本准则4．调度方式5．典型调度算法先来先服务调度算法，短作业（短进程、短线程）优先调度算法，时间片轮转调度算法，优先级调度算法，高响应比优先调度算法，多级反馈队列调度算法。
（三）同步与互斥1．进程同步的基本概念2．实现临界区互斥的基本方法软件实现方法，硬件实现方法。
3．信号量4．管程5．经典同步问题生产者-消费者问题，读者-写者问题，哲学家进餐问题。
（四）死锁1．死锁概念2．死锁处理策略3．死锁预防4．死锁避免系统安全状态，银行家算法。
5．死锁检测和解除三、内存管理（一）内存管理基础1．内存管理概念程序装入与链接，逻辑地址与物理地址空间，内存保护。
2015年计算机学科专业基础综合考试考研大纲I 考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。
II 考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。
要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
III 考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。
二、答题方式答题方式为闭卷、笔试。
三、试卷内容结构数据结构 45分计算机组成原理 45分操作系统 35分计算机网络 25分四、试卷题型结构单项选择题 80分 (40小题，每小题2分)综合应用题 70分IV 考查内容数据结构【考查目标】1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C 或C++语言设计与实现算法的能力。
一、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储三、树与二叉树(一)树的基本概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造(三)树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼(Huffman)树和哈夫曼编码四、图(一)图的基本概念(二)图的存储及基本操作1.邻接矩阵法2.邻接表法3.邻接多重表、十字链表(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用1.最小(代价)生成树2.最短路径3.拓扑排序4.关键路径五、查找(一)查找的基本概念(二)顺序查找法(三)分块查找法(四)折半查找法(五)B树及其基本操作、B+树的基本概念(六)散列(Hash)表(七)字符串模式匹配 (八)查找算法的分析及应用六、排序(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)气泡排序(bubble sort) (四)简单选择排序(五)希尔排序(shell sort) (六)快速排序(七)堆排序(八)二路归并排序(merge sort)(九)基数排序(十)外部排序(十一)各种内部排序算法的比较(十二)排序算法的应用计算机组成原理【考查目标】1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。
中科院研究生院硕士研究生入学考试《计算机技术基础》考试大纲本《计算机技术基础》考试大纲适用于中国科学院研究生院计算机科学与技术等专业的硕士研究生入学考试。
计算机技术基础是计算机科学与技术及相关学科的重要基础，主要内容包括数据结构和操作系统两大部分。
要求考生对计算机科学与技术及和关学科的基本概念有较深入、系统的理解，掌握各种数据结构的定义和实现算法，掌握操作系统所涉及的关键内容，并具有综合运用所学知识分析问题和解决问题的能力。
—、考试内容数据结构1、绪论（1）数据结构的基本概念，数据的逻辑结构、存储结构。
（2）算法的定义、算法的基本特性以及算法分析的基本概念.2、线性表（1）线性关系、线性表的定义，线性表的基本操作。
（2）线性农的顺序存储结构与链式存储结构（包括单链农、循环链表和双向链表）的构造原理。
在以上两种存储结构上对线性表实施的最主要的操作（包括三种链表的建立、插入和删除、检索等）的算法设计。
3、堆栈与队列（1）堆栈与队列的基本概念、基本操作。
（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理。
（3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。
4、串（1）串的基本概念、串的基本操作和存储结构。
（2）串的模式匹配算法和改进的KMP算法5、数组和广义表（1）数细的概念、多维数组的实现（2）对称矩阵和稀疏矩阵的压缩存储（3）广义表的基本概念6、树与二叉树（1）树的定义和性质（2）二叉树的概念、性质和实现（3）遍历二叉树和线索二叉树（4）树和森林（5）赫夫曼树及其应用（6）树的计数7、图（1）图的定义，基本概念，图的分类，常用名词术语。
（2）图的邻接矩阵存储方法、邻接农存储方法的构造原理。
（3）图的遍历操作。
（4）最小生成树，最短路径，AOV网与拓扑排序。
8、文件及查找（1）数据文件的基本概念和基本术语，数据文件的基本操作。
（2）顺序文件、索引文件、散列（Hash戊件。
《计算机原理及系统结构》练习题A答案一、单项选择（每小题有四个备选答案，只有一个是正确的）1. A2. D3. B4. B5. A二、填空1．存储容量存取时间2.操作码，地址码3．传送前预处理，传送后处理4．指令周期、布尔代数、门电路和触发器5.主存储器三、简答题1.答：（1）中断源：引起中断的来源。
（2）中断分类目的：中断源很多，若都形成单独程序入口，则硬件复杂，代价大，故进行分类。
（3）中断分类方法：把性质相近的中断源归为一类。
2.答：（1）部件级流水是指构成处理机部件内各子部件之间的流水，如运算器内浮点加运算的流水（2）处理机级流水是指构成处理机各个部件之间的流水，如取指、分析和执行操作的流水（3）系统级流水是指系统的多个处理机之间的流水，如宏流水3.答：设读写一块信息所需总时间为Tb ，平均找到时间为Ts，平均等待时间为TL，读写一块信息的传输时间为Tm ，则：Tb=Ts＋TL＋Tm。
假设磁盘以每秒r的转速率旋转，每条磁道容量为N个字，则数据传输率=rN个字/秒。
又假设每块的字数为n，因而一旦读写头定位在该块始端，就能在Tm≈（n / rN）秒的时间中传输完毕。
TL 是磁盘旋转半周的时间，TL=（1/2r）秒，由此可得： Tb=Ts＋1/2r＋n/rN 秒4.答：DRAM存储元是通过栅极电容存储电荷来暂存信息。
由于存储的信息电荷终究是有泄漏的，电荷数又不能像SRAM存储元那样由电源经负载管来补充，时间一长，信息就会丢失。
为此必须设法由外界按一定规律给栅极充电，按需要补给栅极电容的信息电荷，此过程叫“刷新”。
5.答：（1）耦合度反映多机系统中各机间物理连接的紧密度和交叉作用能力的强弱。
（2）耦合度有三种：最低耦合、松散耦合和紧密耦合。
（3）最低耦合系统的特点：各计算机之间除通过某种存储介质外无物理连接，也无共享的联机硬件资源。
（4）松散耦合系统的特点：多台计算机通过通道或通信线路实现互连，共享某些如磁盘、磁带等外围设备。
计算机考研专业课大纲——专业学位第一部分概述一、考查目标计算机学科专业综合考试包括《数据结构》和《高级语言程序设计》学科专业基础课程。
要求考生比较系统地掌握上述专业基础课程的概念，理论、技能和方法，能够运用所学的知识判断和解决相关的理论问题和实际问题。
二、考试形式和试卷结构试卷满分及考试时间本试卷满分为150分，考试时间为180分钟答题方式：闭卷、笔试三、试卷内容结构数据结构75分高级语言程序设计75分四、试卷题型结构第二部分《数据结构》第三部分《高级语言程序设计》第二部分《数据结构》考查目标1. 熟悉数据结构的相关概念及其分类，数据结构与算法的关系。
掌握线性表、堆栈和队列，数组和字符串等数据结构的存储、操作和应用，树与二叉树的性质与应用算法，图的存储结构和相关算法，排序与查找的典型算法。
2. 掌握算法时空复杂性分析和正确性验证的基本方法。
3．能够综合运用数据结构、算法、数学等多种知识，对问题进行分析、建模，选择或构建合适的数据结构，设计较优算法。
题型结构：包括问答题与算法设计题具体内容：一、绪论（1）数据、数据元素、数据逻辑结构和存储结构的定义及其关系；（2）数据逻辑结构及其分类；（3）算法的定义和特征；（4）算法的正确性证明方法；（5）算法的时间和空间复杂性分析方法及复杂性函数的渐进表示。
二、线性表、堆栈和队列（1）线性结构的概念和特点；（2）顺序存储和链式存储线性表的基本操作；（3）堆栈的定义和两种存储结构下堆栈的基本操作；（4）堆栈在括号匹配和递归中的应用；（5）队列的定义和两种存储结构下队列的基本操作；（6）队列的应用。
三、数组和字符串（1）二维及多维数组的存储原理及寻址方式；（2）矩阵的存储及基本操作；（3）三元组表和十字链表存储的稀疏矩阵的基本操作；（4）字符串的存储及基本操作；（5）模式匹配算法。
四、树与二叉树（1）树的概念、相关术语和表示方法；（2）二叉树的定义和性质；（3）二叉树的顺序存储结构和链接存储结构；（4）二叉树遍历的递归与非递归算法；（5）线索二叉树的定义和操作；（6）树与二叉树的转换；（7）树的链接存储结构，树和森林的遍历算法；（8）树的顺序存储结构；（9）树在并查集实现中的应用。
吉林省考研计算机科学与技术复习资料重点知识点总结与解析计算机科学与技术是一个广泛而深入的学科，涉及到众多的知识点和技术。
在准备吉林省考研的过程中，掌握重点的知识点是至关重要的。
本文将针对吉林省考研计算机科学与技术的复习资料，总结并解析其中的重点知识点。
一、数据结构与算法分析数据结构与算法是计算机科学与技术的基础，也是考研中的重点内容。
以下是一些重要的知识点和解析：1. 数组：数组是一种线性数据结构，具有固定大小和连续内存空间的特点。
它可以高效地访问任何位置的元素，但插入和删除操作较为耗时。
在算法分析中，我们需要了解数组的时间复杂度和空间复杂度，以便分析算法的性能。
2. 链表：链表是另一种常见的线性数据结构，它的每个元素都包含一个指向下一个元素的指针。
链表可以灵活地进行插入和删除操作，但在访问元素时需要遍历整个链表，因此访问操作的时间复杂度较高。
3. 树：树是一种非线性的数据结构，它具有层次结构和递归定义的特点。
在考研中，我们需要掌握二叉树、二叉搜索树、平衡二叉树等的概念和性质，并了解它们在算法中的应用。
4. 图：图是一种更为复杂的非线性数据结构，它由节点和边组成。
在考研中，我们需要了解图的表示方法、遍历算法、最短路径算法等，并且掌握基本的图论知识。
5. 排序算法：排序算法是计算机科学与技术中的经典问题之一。
我们需要了解常见的排序算法，如冒泡排序、插入排序、选择排序、快速排序、归并排序等，并对它们的时间复杂度和空间复杂度进行分析。
二、操作系统原理与应用操作系统是计算机科学与技术领域中非常重要的一门学科。
以下是一些操作系统的重点知识点和解析：1. 进程与线程：进程和线程是操作系统中的核心概念，我们需要理解它们的定义、特点、状态转换等，并且了解多线程编程和多进程编程的区别。
2. 调度算法：调度算法是操作系统中实现进程调度的关键。
我们需要了解常见的调度算法，如先来先服务调度、最短作业优先调度、优先级调度、轮转调度等，并能够分析其优缺点和适用场景。
2015年计算机学科专业基础综合考试大纲来源:万学海文发布时间：2014-09-13•·2015考研大纲公布名师解析及下载入口•·2015考研时间公布：2014年12月27-28日摘要：2015年计算机学科专业基础综合考试考研大纲2015年计算机学科专业基础综合考试考研大纲已经公布，详细信息如下：I 考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。
II 考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。
要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
III 考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。
二、答题方式答题方式为闭卷、笔试。
三、试卷内容结构数据结构 45分计算机组成原理 45分操作系统 35分计算机网络 25分四、试卷题型结构单项选择题 80分 (40小题，每小题2分)综合应用题 70分IV 考查内容数据结构【考查目标】1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
一、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储三、树与二叉树(一)树的基本概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造(三)树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼(Huffman)树和哈夫曼编码四、图(一)图的基本概念(二)图的存储及基本操作1.邻接矩阵法2.邻接表法3.邻接多重表、十字链表(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用1.最小(代价)生成树2.最短路径3.拓扑排序4.关键路径五、查找(一)查找的基本概念(二)顺序查找法(三)分块查找法(四)折半查找法(五)B树及其基本操作、B+树的基本概念(六)散列(Hash)表(七)字符串模式匹配(八)查找算法的分析及应用六、排序(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)气泡排序(bubble sort) (四)简单选择排序(五)希尔排序(shell sort) (六)快速排序(七)堆排序(八)二路归并排序(merge sort)(九)基数排序(十)外部排序(十一)各种内部排序算法的比较(十二)排序算法的应用计算机组成原理【考查目标】1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。
吉林省考研计算机应用技术复习资料操作系统原理梳理吉林省考研计算机应用技术复习资料：操作系统原理梳理操作系统是计算机系统中的核心组成部分之一，它负责管理计算机硬件和软件资源，提供给其他应用程序一个可控制和可管理的环境。
在吉林省考研计算机应用技术的复习过程中，对于操作系统原理的梳理将是非常重要的一部分。
本文将围绕操作系统原理展开论述，帮助读者梳理相关知识点，为复习工作提供参考。
一、操作系统简介操作系统是一种软件，它是计算机系统中最基本的系统软件，也是用户与计算机硬件之间的桥梁。
操作系统主要功能包括进程管理、内存管理、文件系统和设备管理等。
这些功能相互配合，共同完成对计算机系统的管理与控制。
1.1 进程管理进程是指计算机中正在运行的一个程序，它是计算机分配资源和调度的最小单位。
进程管理的主要任务包括进程的创建、切换、调度和终止等。
1.2 内存管理内存管理是指操作系统对内存进行分配和实施管理的过程。
内存管理的关键是要保证每个进程都能得到所需的内存空间，并在进程运行过程中进行合理的动态管理。
1.3 文件系统文件系统是指操作系统用于组织和管理磁盘上的文件和目录的一种机制。
文件系统提供文件的访问、共享和保护等功能，使得用户可以方便地管理和使用存储在磁盘上的数据。
1.4 设备管理设备管理是指操作系统对计算机系统中的硬件设备进行管理和控制。
包括设备的分配、调度、存储和数据的传输等。
二、操作系统的体系结构操作系统的体系结构是指操作系统的内部组织和设计方式。
常见的操作系统体系结构有单体式、层次式、微内核式和客户-服务器式等。
2.1 单体式体系结构单体式体系结构是最早出现的操作系统体系结构，其核心是一个庞大的内核，负责管理和控制系统的各个组成部分。
这种体系结构的优点是功能强大且性能高效，但缺点是结构复杂，扩展性较差。
2.2 层次式体系结构层次式体系结构是将操作系统按功能划分为若干层次，每一层次只与相邻的两层次进行通信。
吉大979考研大纲吉大（吉林大学）是我国一所著名的高等学府，考研888是该校考研大纲的全称，它是考生备战研究生入学考试的重要指导资料。
下面我将以简体中文为您介绍吉大979考研大纲。
吉大979考研大纲是指吉大（吉林大学）研究生招生考试的大纲要求，也是考生备考的重要依据。
吉林大学作为全日制普通高等教育正式机构，考研大纲的制定是根据国家教育部的相关要求和学校的特点而形成的。
吉大的考研大纲主要包含以下几个方面的内容：一是招生学科目录，二是报名与录取工作。
招生学科目录包括人文学科、理工学科、医学科目和艺术学科，涵盖了众多学科的考试内容。
报名与录取工作则对考生的报名条件、材料和录取办法进行具体规定。
吉大979考研大纲中的招生学科目录是考生备考的重点内容，其中包括人文学科、理工学科、医学科和艺术学科等多个学科的要求。
在备考过程中，考生需要了解自己所报考的学科的考试科目、考试内容和考试形式，并根据大纲要求进行复习。
无论是考研初试还是复试，吉大979考研大纲都是考生备考的指导方针。
考研初试主要包括两个部分，一是全国研究生入学考试共同科目，另一个是学校或研究所自主命题的专业科目。
而复试则根据各学科的具体要求进行考核。
除了考试科目外，吉大979考研大纲还对报名与录取工作进行了详细规定。
报名条件包括学历要求、专业要求和成绩要求等；报名材料则包括个人基本信息、学业成绩和科研成果等；录取办法则是根据考生初试和复试的成绩综合评定进行录取。
总的来说，吉大979考研大纲是吉大研究生招生考试的重要指导资料，它对于考生备考的科目要求、考试形式及报名材料等方面进行了具体规定。
考生在备考过程中需要结合考研大纲进行有针对性的复习和准备，以提高自己的考试成绩和录取机会。
虽然吉大979考研大纲的要求是对考生具有一定的挑战性，但只要考生在备考过程中严格遵循大纲要求，制定科学的复习计划，并付出努力和坚持，相信考生一定能够在考研的道路上取得好成绩。
Chapter 1 Computer and DataKnowledge point:1.1The computer as a black box.1.2von Neumann model1.3The components of a computer: hardware, software, and data.1.4The history of computers.REVIEW QUESTIONS1.How is computer science defined in this book?A：Issues related to the computer.2.What model is the basis for today’s computers? ( Knowledge point 1.2)A：The von Neumann model.3.Why shouldn’t you call a computer a data processor? ( Knowledge point 1.1)A：Computer is general-purpose machine. it can do many different types of tasks.4.What does a programmable data processor require to produce output data? ( Knowledgepoint 1.1)A：The input data and the program.5.What are the subsystems of the von Neumann computer model? ( Knowledge point 1.2) A：Memory, arithmetic logic unit, control unit, and input/output.6.What is the function of the memory subsystem in von Neumann’s model? ( Knowledgepoint 1.2)A：Memory is the storage area. It is where programs and data are stored during processing.7.What is the function of the ALU subsystem in von Neumann’s model? ( Knowledge point1.2)A：ALU is where calculation and logical operations take place.8.What is the function of the control unit subsystem in von Neumann’s model? ( Knowledgepoint 1.2)A：It controls the operations of the memory, ALU, and the input/output subsystem.9.What is the function of the input/output subsystem in von Neumann’s model?( Knowledge point 1.2)A：The input subsystem accepts input data and the program from outside the computer; the output subsystem sends the result of processing to the outside.pare and contrast the memory contents of early computers with the memory contentsof a computer based on the von Neumann model? ( Knowledge point 1.2)A：Computer based on the von Neumann model stores both the program and its corresponding data in the memory. Early computers only stored the data in the memory.11.How did the von Neumann model change the concept of programming? ( Knowledgepoint 1.2)A：A program in the von Neumann model is made of a finite number of instructions. The instructions are executed one after another.12.The first electronic special-purpose computer was called c( Knowledge point1.4)a. Pascalb. Pascalinec. ABCd. EDV AC13.One of the first computers based on the von Neumann model was called d( Knowledge point 1.4)a. Pascalb. Pascalinec. ABCd. EDV AC14.The first computing machine to use the idea of storage and programming was calledd( Knowledge point 1.4)a. the Madelineb. EDV ACc. the Babbage machined. the Jacquard loom15.d separated the programming task from the computer operation tasks.( Knowledge point 1.3)a. Algorithmsb. Data processorsc. High-level programming languagesd.Operating systems30. According to the von Neumann model, can the hard disk of today be used as input or output? Explain. ( Knowledge point 1.2)A：Yes. When the hard disk stores data that results from processing, it is considered an output device; when you read data from the hard disk, it is considered an input device. 32. Which is more expensive today, hardware or software? ( Knowledge point 1.3)A：Software.Chapter 2 Data RepresentationKnowledge point:2.1 Data Types.2.2 Data inside the Computer.2.3 Representing Data.2.4 Hexadecimal and Octal notation.REVIEW QUESTIONS five types of data that a computer can process. ( Knowledge point2.1)A：Numbers, text, images, audio, and video.2.How does a computer deal with all the data types it must process? ( Knowledge point 2.2) A：All data types are transformed into bit pattern.3.4.What is the difference between ASCII and extended ASCII? ( Knowledge point 2.3)A：ASCII is a bit pattern made of 7 bits and extended ASCII is a bit pattern made of 8 bits.5.What is EBCDIC? ( Knowledge point 2.3)A：Extended Binary Coded Decimal Interchange Code.6.How is bit pattern length related to the number of symbols the bit pattern can represent?( Knowledge point 2.3)A：The relationship is logarithmic.7.8.9.What steps are needed to convert audio data to bit patterns? ( Knowledge point 2.3)A：Sampling, Quantization, and Coding.10.What is the relationship between image data and video data? ( Knowledge point 2.3)A：Video is a representation of images in time.34. A company has decided to assign a unique bit pattern to each employee. If the company has 900 employees, what is the minimum number of bits needed to create this system of representation? How many patterns are unassigned? If the company hires another 300employees, should it increase the number of bits? Explain your answer. ( Knowledge point 2.3)A：log2900≈10,210-900=124,Yes, 900+300>210Chapter 3 Number RepresentationKnowledge point:3.1 Convert a number from decimal, hexadecimal, and octal to binary notation and vice versa.3.2 Integer representation: unsigned, sign-and-magnitude, one’s complement, and two’s complement.3.3 Excess system.3.4 Floating-point representation.REVIEW QUESTIONS5. What are three methods to represent signed integers? (Knowledge point 3.2)A：Sign-and-Magnitude, One’s Complement, and Two’s Complement.9. Name two uses of unsigned integers. ( Knowledge point 3.2)A：Counting and Addressing.10. What happens when you try to store decimal 130 using sign-and-magnitude representation with an 8-bit allocation? ( Knowledge point 3.2)A：Overflow.11. Compare and contrast the representation of positive integers in sing-and-magnitude, one’s complement, and two’s complement. ( Knowledge point 3.2)A：The representation of positive integers in sing-and-magnitude, one’s complement, and two’s complement is the same.14. Compare and contrast the range of numbers that can be represented in sign-and-magnitude, one’s complement, and two’s complement. ( Knowledge point 3.2)A：Sign-and-Magnitude range –(2N-1-1)～+(2N-1-1)One’s Complement range –(2N-1-1)～+(2N-1-1)Two’s Complement range –(2N-1)～+(2N-1-1)16. What is the primary use of the Excess_X system? ( Knowledge point 3.3)A：The primary use of the Excess_X system is in storing the exponential value of a fraction.17. Why is normalization necessary? ( Knowledge point 3.4)A：A fraction is normalized so that operations are simpler.Chapter 4 Operation On BitsKnowledge point:4.1 Arithmetic operations.4.2 Logical operations.4.3 Mask.4.4 Shift operations.REVIEW QUESTIONS3. What happens to a carry form the leftmost column in the final addition? ( Knowledge point4.1)A：The carry is discarded.5. Define the term overflow. ( Knowledge point 4.1)A：Overflow is an error that occurs when you try to store a number that is not within the range defined by the allocation.8. Name the logical binary operations. ( Knowledge point 4.2)A：NOT, AND, OR, and XOR.10. What does the NOT operator do? ( Knowledge point 4.2)A：It inverts bits.(it changes 0 to 1 and 1 to 0)11. When is the result of an AND operator true? ( Knowledge point 4.2)A：Both bits are 1.12. When is the result of an OR operator true? ( Knowledge point 4.2)A：Neither bit is 0.13. When is the result of an XOR operator true? ( Knowledge point 4.2)A：The two bits are not equal.17. What binary operation can be used to set bits? What bit pattern should the mask have? ( Knowledge point 4.3)A：OR. Use 1 for the corresponding bit in the mask.18. What binary operation can be used to unset bits? What bit pattern should the mask have? ( Knowledge point 4.3)A：AND. Use 0 for the corresponding bit in the mask.19. What binary operation can be used to flip bits? What bit pattern should the mask have? ( Knowledge point 4.3)A：XOR. Use 1 for the corresponding bit in the mask.Chapter 5 Computer OrganizationKnowledge point:5.1. three subsystems that make up a computer5.2. functionality of each subsystem5.3. memory addressing and calculating the number of bytes5.4. addressing system for input/output devices.5.5. the systems used to connect different components together.Review questions:1. What are the three subsystems that make up a computer?(Knowledge point 5.1) Answer: the CPU, main memory, and the input/output (I/O) subsystem.2. What are the parts of a CPU? (Knowledge point 5.1)Answer: The CPU performs operations on data and has a ALU, a control unit, and a set of registers.3. What‘s the function of the ALU? (Knowledge point 5.2)Answer: The ALU performs arithmetic and logical operations.Exercises:78. A computer has 64MB of memory. Each word is 4 bytes. How many bits are needed toaddress each single word in memory? (Knowledge point 5.3)Solution:The memory address space is 64 MB, that is 2 raised to the power 26. The size of each word in bytes is 2 raised to the power 2. So we need 24(subtract 2 from 26) bits to address each single word in memory.79. How many bytes of memory are needed to store a full screen of data if the screen is made of 24 lines with 80 characters in each line? The system uses ASCII code, with each ASCII character store as a byte. (Knowledge point 5.3)Solution:The quantity of bytes in a full screen is 1920 (24*80) while the system uses ASCII code with each ASCII character store as a byte. So we need 1920 bytes of memory to store the full screen of data.87. A computer uses isolated I/O addressing. Memory has 1024 words. If each controller has 16 registers, how many controllers can be accessed by this computer? (Knowledge point 5.4) Solution:Memory has 1024 words. So the address space is 1024. Each controller has 16 registers. Then we get 64 (divide 16 by 1024)controllers which can be accessed by this computer.88. A computer uses memory-mapped I/O addressing. The address bus uses 10 lines. If memory is made of 1000 words, how many four-register controllers can be accessed by this computer? (Knowledge point 5.4)Solution:The address bus uses 10 lines. So, the address space is 1024(2 raised to the power 10). The memory is made of 1000 words and each controller has four registers. Then we get (1024-1000)/4 = 6 four-register controllers which can be accessed by this computer.Chapter 6 Computer NetworksKnowledge point:6.1. OSI model6.2. TCP/IP protocol6.3. three types of networks6.4. connecting devices6.5. client-server modelReview questions:2. Name the layers of the OSI model? (6.1)Answer: Physical layer, Data link layer, Network layer, Transport layer, Session layer, Presentation layer and Application layer.3. Name the layers of the TCP/IP protocol suite. (6.2)Answer: The layers of the TCP/IP protocol suite are: physical and data-link layers network layer, transport layer, and application layer.8. What are the three common topologies in LANs? Which is the most popular today? (6.3) Answer: bus topology, star topology, ring topology, star topology9. Name four types of network connecting devices. (6.4)Answer: the four types of network connecting devices are repeater, bridge, router and gateway.Chapter 7 Operating SystemsKnowledge point:7.1. the definition of an operating system7.2. the components of an operating system7.3. Memory Manager7.4. Process manager7.5. deadlockReview questions:4. What are the components of an operating system? (7.2)Answer: An operating system includes: Memory Manager, Process Manager, Device Manager and File Manager13. What kinds of states can a process be in? (7.4)Answer: ready state, running state, waiting state.15. If a process is in the running state, what states can it go to next? (7.4)Answer: ready state, waiting state.What’s the definition of an operating system? (7.1)Answer: An operating system is an interface between the hardware of a computer and user(programs or humans) that facilitates the execution of other programs and the access to hardware and software resources.What are the four necessary conditions for deadlock? (7.5)Answer: mutual exclusion, resource holding, no preemption and circular waiting.51. A multiprogramming operating system uses paging. The available memory is 60 MB divided into 15 pages, each of 4MB. The first program needs 13 MB. The second program needs 12MB. The third program needs 27 MB. How many pages are used by the first program? How many pages are used by the second program? How many pages are used by the third program? How many pages are unused? What is the total memory wasted? What percentage of memory is wasted? (7.3)Answer:Each page is 4MB. The first program needs 13 MB. It is obviously that 4*3<13<4*4. So the first program uses 4 pages and wastes 3(16-3) MB. The second program needs 12 MB. It is obviously that 12=4*3. So the second program uses 3 pages and wastes 0 MB. The third program needs 27 MB. It is obviously that 4*6<27<4*7. So the first program uses 7 pages and wastes 1(28-27) MB. There are 1(15-4-3-7) page unused. There are totally 4(3+0+1) MB memory wasted. The percent of memory wasted is 4/(60-4*1)=7%.Chapter 8 AlgorithmsKnowledge point:8.1. the concepts of an algorithm and a subalgorithm8.2. three constructs for developing algorithms8.3. basic algorithms8.4. tools for algorithm representation8.5. recursionReview questions:1. What is the formal definition of an algorithm? (8.1)Answer: An ordered set of unambiguous steps that produces a result and terminates in a finite time.2. Define the three constructs used in structured programming. (8.2)Answer: The three constructs in structured programming are Sequence, Decision and Repetition.10. What are the three types of sorting algorithms? (8.3)Answer: bubble sort, selection sort and insertion sort.12 What is the purpose of a searching algorithm? (8.3)Answer: The purpose is to find the location of a target among a list of objects.13. What are the two major types of searches? How are they different? (8.3)Answer: sequential search and binary search. The difference is whether the list is ordered or not.55. A list contains the following elements. Using the binary search algorithm, trace the steps followed to find 20. At each step, show the values of first, last and mid.3, 7, 20, 29, 35, 50, 88, 200 (8.3)Solution:index 0---1---2---3---4---5---6---73, 7, 20, 29, 35, 50, 88, 200First=0, Last=7, Mid=(0+7)/2=3The data is D(3)=29, 20 smaller than the D(3), so remove the data from index 3 to 7. Change the new point First=0, Last= mid-1=2, and Mid=(0+2)/2=1The data is D(1)=7, 20 bigger than the D(1), so remove the data from index 0 to 1. Change the new point First=mid+1=2, Last=2, and Mid=(2+2)/2=2The data is D(2)=20, we find the data 20 in index=258. Write a recursive algorithm to find the combination of n objects taken k at a time using following definition.C(n,k)=1 , if k=0 or n=kC(n,k)=C(n-1,k)+(n-1,k-1) , if n>k>0 (8.5)Solution:A: CInput : n and kIf(k==0 or n==k)Then return 1End ifIf(n>k and k>0)Then Return C(n-1,k)+(n-1,k-1)End ifEnd。
