1. 简述计算机软件技术发展历史 答：P13 2. 简述软件发展的三个阶段

3. 答：60年代为高级语言阶段，70年代为程序设计阶段，80年代至今为自动

程序设计阶段！P14

4. 什么是算法的时间复杂度 答：P24中下 5. 什么是算法的空间复杂度 答： P25 6. 基于线性表有哪几种基本运算

答：线性表的主要运算有 插入、删除、查找、和排序。 7. 写出顺序存储线性表的插入删除算法 答：P26下 8. 写出线性链表的插入删除算法 答：P30—31 9. 基于堆栈有哪几种基本运算

答：表达式求值，程序的嵌套和递归调用等，P36（个人理解） 10. 写出顺序栈插入删除算法 答：P35 11. 写出链栈的插入删除算法 答：P36

12. 写出顺序队的插入删除算法 答：P40下 13. 写出链队的插入删除算法 答：P41

14. 写出稀疏矩阵的三元组表示 答：P46下 15. 写出数组的带行指针向量的单链表 答：P49下

16. 阅读线性表、链表操作的伪代码，回答伪代码执行结果，画出伪代码算法程

序流程图。

17. 二叉树后序遍历

答：后序遍历左子树，后序遍历右子树，访问根节点，P56下 18. 基于树有哪几种基本运算 答：二叉树的应用，P58--P64

19. 二叉树中叶子结点的数目与度为2的结点数目之间有什么关系 答：N0=N2+1 P54

20. 满二叉树中树的深度与结点数目之间有什么关系 答：P54下 21. 二叉树中结点的数目与树的分支之间有什么关系

答：一个包含n个分支节点（非叶节点）的非空二叉树，它的叶节点数目最多为 n + 1

21、二叉树中结点的数目与树的分支之间有什么关系 P54 22、二叉树深度与结点数目之间有什么关系

答：P54 深度为h的二叉树至多有2^h个结点 23、二叉树第i层最多有几个结点 答：P54 第i层上至多有2^（i-1）个结点 24、将一般树转换为二叉树 P56

25、画出二叉树先序中序后序遍历的结果 P56 26、画出哈夫曼树 P61 27、画出图的邻接矩阵 P67 28、基于图有哪几种基本运算

答：P72 单源最短路径、拓扑排序、关键路径 29、简述常用的查找算法 答：P80 线性查找：线性查找又称顺序查找，基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结

果与文件中n个记录的关键字都不等，则查找失败。

对分查找：若记录在文件中是按关键字有序排列，则在查找时可采用较快的跳跃式查找，称为对分查找。 分块查找：P82

基本思想：先找到“中间记录”，比较其关键字，如果关键字与给定K值相等，则查找成功；如果关键字小于给定K值，则说明被查找记录必在前半区间中；反之则在后半区间中。这样把搜索区间缩小了一半，继续进行查找。 30、简述几种常用排序算法的特点 答：P91 一、选择排序：1、简单选择排序时间复杂度O（n^2），空间复杂度O （ 1）堆排序：P96

二、插入排序：1、线性插入排序2、对半插入排序 时间复杂度和空间复杂度见P97

三、交换排序：1、冒泡排序2、快速排序P98 31、画出冒泡排序的过程 P98 32、画出堆排序的过程 P95

33、给出冒泡排序法对该序列排序的过程 P98 34、简述冒泡排序算法的特点 P98 35、分析冒泡排序法的特点 P98 36、分别按中序遍历和前序遍历算法遍历下图二叉树，给出遍历后结点字符编号的序列；

37、堆排序的基本方法 P94

38、给出计算表达式计算的算法，画出程序流程图：P37 39、给出不同进制数之间转换的算法，画出程序流程图： 40、

22. 简述操作系统的基本功能

处理器管理；存储管理；设备管理；文件管理；用户接口； 23. 什么是操作系统

操作系统是最接近裸机的软件层，因此它是对硬件的首次扩充，也是其他各种软件的运行基础。 24. 简述操作系统的分类

多道批处理操作系统；分时系统；实时系统； 25. 简述操作系统的定义

操作系统是最接近裸机的软件层，因此它是对硬件的首次扩充，也是其他各种软件的运行基础。

26. 进程在系统中有哪几种状态

就绪状态；运行状态；阻塞状态；

27. 简述实存储管理技术与虚拟存储管理技术的区别

实存储管理是作业运行时整个作业的地址空间必须全部装入内存的一个连续空间中；虚拟存储管理技术是一种不存在的虚假存储器给用户提供一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制。 28. 简述虚拟存储管理技术的特点

虚拟存储提供了一个大容量存储系统集中管理的手段 29. 简述静态重定位与动态重定位的区别 p113 30. 什么是静态重定位

它是在程序装入时进行，一般通过处理机中一对界地址寄存器来实现。界地址寄存器分为下界和上界寄存器，分别存放该作业在内存中的起始和终止地址，程序中的逻辑地址相加得到物理地址。 31. 动态重定位图3.13 p118 32. 图3.16分页管理 p121 33. 简述分页管理的特点

不要求作业在内存中连续存放，较好地解决了碎片问题；作业地址空间不受内存的限制，对一些不常用的部分不必常驻内存，为用户提供足够大的存储空间，从而更有利于多道程序作业。 34. 简述分段管理的特点

便于程序模块化处理；便于处理变化的数据；便于共享分段； 35. 什么是作业、程序和进程

作业：作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做工作的集合。

36. 程序：程序可以看作对一系列动作的执行过程的描述。 37. 进程：是在指定内存区域中的一组指令序列的执行过程。 38. 简述作业的四种状态

提交状态；收容状态；执行状态；完成状态； 39. 简述进程的三种状态

就绪状态；运行状态；阻塞状态； 40. 什么是进程间的同步与互斥

41. 同步是指两个事件的发生存在某种时序上的关系，如果系统中有若干个

进程要共同完成某一任务，那么他们相互之间必须协调配合，这样就需要有

一种工具使它们同步运行。

42. 互斥是当多个进程要求共享系统中某些硬件或软件资源，而这些资源却

又要求排他性使用时，这样往往引起由于多个进程竞争统一资源使运行结果出现问题。 43. 什么是P/V操作

44. 解决同步与互斥的工具有多种，可以由硬件实现，也可以由软件实现。

P-V操作是用同步原语对某信号量进行操作以实现同步互斥的方法。 45. 进程间通信的方式有哪些 直接通信；信箱通信；

46. 什么是死锁？简述死锁的原因和必要条件

47. 死锁是指计算机系统中进程所处的一种状态。 48. 原因：系统资源不足；进程推进的顺序不当；

49. 必要条件：所涉及的资源是非共享的；进程在等待新资源时，继续占用

分配到的资源；一个进程占有的资源不能被别的进程强行抢占；一个进程获得的资源同事被另一个进程所请求，从而形成一个进程的循环链； 50. 简述设备管理的功能 p149

51. 简述操作系统为用户提供的两类接口 p165 52. 什么是文件系统

53. 简述软件工程的基本原则 p237 54. 什么是软件？有哪些不同类型的软件？ 55. 简述软件工程的基本原则 p237 56. 什么是类，什么是聚合

57. 什么是软件生命周期 p237

58. 什么是软件开发模型？有哪些主要的模型？ P238

59. 软件设计分为哪几个阶段，每个阶段的主要任务是什么 （需求分析、概要

分析、详细设计、软件编码、软件测试、软件维护。）

60. 软件开发过程分为哪几个阶段，每个阶段的主要任务是什么 61. 需求分析基本技术有哪些 p240 62. 简述概要设计的两个主要任务 p241 63. 简述模块划分的原则 p243

64. 简要叙述详细设计的两种常用的表示工具 p244 65. 结构化程序的三种基本结构是什么

66. 软件测试的基本技术有哪些 p247 67. 给出某一软件开发任务（图书管理、表达式计算、游戏设计）的解决方案（包

含初试需求列表，DFD，概要设计和详细设计） 68. 什么是类，类之间的几种基本关系是什么

答：类是定义同一类所有对象的变量和方法的蓝图或原型。类与类之间的关系分为：关联关系、单向关联、双向关联、自身关联 69. 什么是对象，对象之间的几种基本关系是什么

对象是类的实例，类是是对具有相似特征的食物的抽象！ 70. 什么是对象，类与对象是什么关系

71. 类是指定义对象的代码, 所有对象都是根据一个类创建的. 72. 面向对象程序设计中类之间的基本关系有哪几种

73. 查阅MFC类CFileDialog，阅读程序，说明程序功能，画出程序流程图 74. 查找资料，研究5种小游戏的设计文档