威廉希尔硕士研究生入学考试

《软件技术基础》复试大纲

第一部分  考试说明

一、 考试性质

本考试为开卷考试。

二、 考试内容范围

1. 数据结构。

2. 操作系统。

3. 软件工程。

4. 数据库原理及技术。

三、 评价目标

1. 掌握数据结构、线性表、栈、队列、二叉树等概念，了解和掌握顺序表的插入算法、单链表的插入运算算法、二叉树的有关操作、图的有关操作、查找与排序算法等。

2. 掌握操作系统的概念和功能、进程、作业概念，掌握进程调度的过程、作业调度过程以及存储管理和设备管理中的常用技术。

3. 掌握软件、软件生存周期概念，掌握软件工程方法的各个阶段的任务和工作流程。

4. 掌握数据库系统概念和数据模型的种类，掌握主要的SQL语句。

四、 课程涉及的相关书目

1. 《软件技术基础》，李廷元 何元清 付茂洺。中国铁道出版社，2018年7月。

第二部分  考查要点

1. 数据结构中的基本概念。数据、数据元素、数据项、数据结构、线性结构、非线性结构。数据的存储方法可分为：顺序存储、链式存储、索引存储、散列存储。

2. 线性表的概念。线性结构的基本特点是数据元素有序并有限。线性表是n（n≥0）个相同类型的元素a1，a2，an所构成的有限线性序列。

3. 顺序表。在顺序表的存储结构中，数据元素按其逻辑次序依次存放在一组地址连续的存储单元里。

4. 线性链表。采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零散分布在内存中的任何位置上。

5. 循环链表。循环链表是一种首尾相接的链表。

6. 栈是限制仅在表的一端进行插入和删除运算的线性表，它的特点是后进先出。

7. 队列是允许在线性表的一端进行数据元素插入操作而在另一端才能进行数据元素删除操作的线性表。

8. 树结构及其基本概念。树结构是结点之间有分支、层次关系的结构。

9. 二叉树是n个结点的有限集合（n≥0），它或者是空集（n=0）或者由一个根结点及两棵互不相交的、分别称做这个根的左子树和右子树的二叉树组成。

10. 图。图G由两个集合V和E组成，记为G=(V,E)，其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。

11. 图的遍历及算法。深度优先搜索（dfs）、广度优先搜索（bfs）；最短路径、最小生成树、拓扑排序。

12. 查找。查找分为简单查找方法（顺序查找、二分查找、分块查找）、树表查找和哈希查找。

13. 排序。排序分为简单排序、快速排序以及归并排序。

14. 操作系统的概念和功能。操作系统主要有五大功能：处理机、存储器管理、设备管理、文件管理和作业管理。

15. 操作系统的特征。操作系统具有以下特征：并发行、共享性、虚拟性和不确定性。

16. 操作系统的分类。操作系统的基本类型有:批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统。

17. 进程的概念。进程是可并发执行的程序在给定数据集合上的一次执行过程；是系统进行资源分配合调度的一个独立的基本单位和实体；是指执行一个映象程序的总环境。

18.进程控制与进程调度。进程控制是对进程在其生命期的各种活动及状态转变实施有效的控制；进程调度的任务是协调和控制各进程对CPU的使用，按照某种策略动态地将处理机分配给处于就绪状态的某个进程。

19. 进程互斥与同步。进程的互斥是由多个进程竞争同一共享资源而产生的相互制约的关系；进程之间通过执行时序上的某种限制而达到相互合作，这种因相互合作而产生的制约关系称为进程的同步。

18.进程的通信。目前常用的进程通信的高级方式有消息缓冲通信，管道通信和信箱通信。

19. 死锁。对资源的管理使用不当，在一定条件下会导致系统发生随机故障，出现进程被阻塞的现象，即若干进程彼此互相等待对方所拥有且又不放的资源，其结果是谁也无法得到继续运行所需的全部资源，因而永远等待下去。这种现象称为死锁。

20. 作业的概念。作业，就是用户请求计算机系统执行的一次独立的上机任务，是能共享公共资源区域的一族有关进程（进程家族）。

21. 作业控制。作业控制包括两方面含义：从用户角度看，作业控制是用户通过作业控制级接口，组织和控制其作业在计算机上的运行的全过程。从系统管理的角度看，作业控制是系统接受、分析并执行用户发出的控制命令，为作业的每个发展阶段提供必要的系统服务。

22. 作业调度。作业从用户提交开始到真正占有处理机而被执行，要经过多级调度才能实现。

23. 存储管理的功能。存储管理主要有五个方面的功能：内存分配和回收、内存空间的共享、存储保护、地址映射、内存空间的扩充。

24. 分区存储管理。分区存储管理的基本思想是把内存划分成若干个大小不等的连续区域，称为分区。每个作业可占用一个或多个分区。

25. 数据传送控制方式。外设与内存间常用的数据传送方式有：中断控制方式、DMA方式和通道方式。

26. 缓冲技术。缓冲技术的基本思想是：在内存中开辟一个或多个专用的区域，即缓冲区，作为CPU与I/O设备之间信息传送的集散地。

27. 设备分配。设备分配的原则由设备特性及用户请求、系统中设备使用情况而定。

28. 软件工程及软件工程学的概念。软件工程学主要包括软件开发技术和软件工程管理两方面的内容。一个软件从用户提出开发要求，到废弃不用为止的全过程，称为软件的生存周期。

29. 需求分析的主要内容有：技术可行性、经济可行性和操作可行性。

30. 数据流图。对数据流图中包含的所有元素的定义的集合构成了数据词典。

31. 数据词典。对数据流图中包含的所有元素的定义的集合构成了数据词典。

32. 软件设计准则。软件设计准则涉及软件结构的准则、模块化的准则以及模块独立性的准则几个方面的问题。

33. 软件测试策略。软件的测试过程是按单元测试、组装测试、确认测试和系统测试四个步骤进行的。常用的测试方法有黑盒测试和白盒测试两种。

34. 软件维护的步骤与方法。具体的维护工作需要经过理解分析、修改和重新验证现有软件系统三个过程。

35. 数据、信息与数据处理。数据是一种物理符号序列，它的内容是事物特性的反映；信息是经过加工处理的数据，是人们消化理解了的数据，是数据的具体含义；数据处理是指将数据转换成信息的过程。

36. 数据管理技术的发展。数据库管理技术的发展大致经历四个阶段：手工管理阶段、文件系统阶段、数据库系统阶段以及分布式数据库系统阶段。

37. 数据库系统的组成。数据库系统由五个部分组成：硬件系统、数据库集合、数据库管理系统及相关软件、数据库管理员（DBA）和用户。

38. 非关系模型和关系模型。非关系模型有层次模型、网状模型和面向对象模型。关系模型是以二维表格结构作为基础的由若干个关系模式组成的集合。

39. 关系运算。从集合论的观点来定义关系，关系是一个元数为K的元组集合，即这个关系有若干个元组，每个元组有K个属性值。

40. 数据库的基本查询。查询是从数据库中提取出满足用户需要的数据，查询是由SELECT命令实现的。