华南理工大学计算机软件基础（二）课程考试大纲（课程代码：02365）

目  录

 Ⅰ课程性质与设置目的要求

（一）课程性质和特点

计算机软件基础是工业自动化专业、电力系统及其自动化专业的一门专业基础课，主要叙述计算机软件基本原理及其应用。本课程包括五个部分：计算机软件概论、数据结构、操作系统、数据库及软件工程，每一个部分都是计算机学科中的重要分支。通过本课程的学习，使应考者能对计算机软件知识有一个基本的了解，从而提高使用计算机的能力和掌握正确开发应用软件的方法。

（二）本课程的基本要求

 1.了解计算机软件的基本概念，软件的分离和功能

 2.系统的学习和掌握常用的两类逻辑数据结构（线性表和树），掌握他们的存储结构和基本运算。

 3.了解操作系统的分类，掌握操作系统的主要功能

 4.学习和掌握数据库的基本概念，掌握关系数据库使用的基本方法

 5.了解软件工程的概念，了解结构化系统分析与设计方法

（三）本课程与相关课程的联系

本课程的先修课程为：计算机基础与程序设计、微型计算机原理及应用。

数据结构中存储结构和基本运算的实现需要程序设计的知识及程序编制能力，教材中的实例都是用C++语言编写，因此掌握C++语言的基础知识是学习本课程的前提。

本课程的重点（或难点）章为第二章、第四章、第五章、第七章，次重点章为第三章、第六章，一般章为第一章。

 Ⅱ课程内容与考核目标

一、考试基本要求

要求应考者理解和掌握数据结构、操作系统、数据库、软件工程的基本知识、基本原理和基本技能，能运用计算机软件课程的相关知识进行案例分析及设计，具备分析问题和解决问题的基本能力。

第1章 预备知识

一、学习目的与要求

通过本章的学习，应了解算法的基本概念，领会算法的设计方法，并能够分析算法的复杂度。

二、考试内容

*1.1 集合（注1）

 *1.1.1 集合及其基本运算

 *1.1.2 自然数集与数学归纳法

 *1.1.3 笛卡儿积

 *1.1.4 二元关系

1.2 算法

 1.2.1 算法的基本概念

 1.2.2 算法设计基本方法

 1.2.3 算法的复杂度分析

三、考核知识点

1、算法的基本概念

2、算法设计基本方法

3、算法的复杂度分析

四、考核要求

识记：算法的基本概念。

领会：算法的基本特征、算法的复杂度分析。

简单应用：算法设计的基本方法。

综合应用：能够运用本章所规定的基本知识分析具体的案例。

注1：考试内容部分标*的内容不考核，下同

第2章 基本数据结构及其运算

一、学习目的与要求

通过本章的学习，应了解数据结构的相关概念，数据的逻辑结构和存储结构及相互关系。要掌握数据结构的基本运算，包括插入、删除、查找、修改和排序。掌握线性表和树两类逻辑数据结构，以及它们在不同存储结构上的实现及相应算法。

二、考试内容

2.1 数据结构的基本概念

 2.1.1 什么是数据结构

 2.1.2 数据结构的图形表示

2.2 线性表及其顺序存储结构

 2.2.1 线性表及其运算

 2.2.2 栈及其应用

 2.2.3 队列及其应用

2.3 线性链表

 2.3.1 线性链表的基本概念

 2.3.2 线性链表的插入与删除

 *2.3.3 带链的栈与队列

 *2.3.4 循环链表

 *2.3.5 多项式的表示与运算

2.4 线性表的索引存储结构

 2.4.1 索引存储的概念

 2.4.2 “顺序-索引-顺序”存储方式

 2.4.3 “顺序-索引-链接”存储方式

 *2.4.4 多重索引存储结构

2.5 数组

 2.5.1 数组的顺序存储结构

 2.5.2 规则矩阵的压缩

 2.5.3 一般稀疏矩阵的表示

2.6 树与二叉树

 2.6.1 树的基本概念

 2.6.2 二叉树及其基本性质

 2.6.3 二叉树的遍历

 *2.6.4 二叉树的存储结构

*2.6.5 穿线二叉树

*2.6.6 表达式的线性化

*2.7 图

 *2.7.1 图的基本概念

 *2.7.2 图的存储结构

 *2.7.3 图的遍历

 *2.7.4 图邻接表类

三、考核知识点

1、数据结构的定义，数据结构的图形表示

2、线性表、栈、队列

3、链表的概念、链表的图示方法、链表的基本运算

4、数组、及其运算

5、数、二叉树

四、考核要求

识记：数据结构的基本概念、链表的基本概念、索引的基本概念、树和二叉树的基本概念。

领会：各类数据结构的基本运算，树和二叉树的转换，。

简单应用：各类数据结构基本运算的图示方法。

综合应用：图示法描述顺序线性表的插入、删除；链表的插入、删除；二叉树的插入和删除。

第3章 查找与排序技术

一、学习目的与要求

通过本章的学习，应了解基本查找技术、哈希表技术及基本的排序技术；对二叉树的查找也应掌握。

二、考试内容

3.1 基本的查找技术

 3.1.1 顺序查找

 3.1.2 有序表的对分查找

*3.1.3 分块查找

3.2 哈希表技术

 3.2.1 哈希表的基本概念

 3.2.2 几种常用的哈希表

3.3 基本的排序技术

 3.3.1 冒泡排序与快速排序

 3.3.2 简单插入排序与希尔排序

*3.3.3 简单选择排序与堆排序

*3.3.4 其他排序方法简介

3.4 二叉排序树及其查找

 3.4.1 二叉排序树的基本概念

 3.4.2 二叉排序树的插入

 3.4.3 二叉排序树的删除

*3.4.4 二叉排序树查找

*3.5 多层索引树及其查找

 *3.5.1 B-树

 *3.5.2 B+树

*3.6 拓扑分类

三、考核知识点

1、基本的查找方法、顺序查找、有序表达查找

2、哈希表

3、基本冒泡、快速排序

4、插入排序

5、二叉树的概念、查找、插入

四、考核要求

识记：基本查找的方法，哈希表的概念，二叉树的定义及概念。

领会：顺序查找、有序表的对分查找、哈希表。

简单应用：图示法表示冒泡法、快速排序、二叉树的插入删除、二叉树的遍历。

综合应用：能够运用本章的常用的查找及排序方法分析给定的问题和案例。

第4章 资源管理技术

一、学习目的与要求

操作系统是管理计算机资源的一种系统软件，它是对裸机（不配有任何软件的计算机）的首次扩充。它统一管理计算机的各种资源，如处理机、存储器、设备、文件、作业等。

处理机管理、储存管理、文件管理、设备管理和作业管理是操作系统所具有的五个基本功能，考生对操作系统的基本功能能有清晰的理解，掌握每种管理的对象、主要方法和要达到的目的。

二、考试内容

4.1 操作系统的概念

 4.1.1 操作系统的功能与任务

 4.1.2 操作系统的发展过程

 4.1.3 操作系统的分类

4.2 多道程序设计

 4.2.1 并发程序设计

 4.2.2 进程

 4.2.3 进程之间的通信

 4.2.4 多道程序的组织

4.3 存储空间的组织

 4.3.1 内存储器的管理技术

 4.3.2 外存储器中文件的组织结构

三、考核知识点

1、操作系统的功能任务、操作系统的发展历程、操作系统的分类。

2、并发程序设计、进程

3、进程之间的通信、死锁、P/V操作

4、多道程序的组织、作业调度

5、储存空间的组织、界地址管理、分页存储管理、分段管理、段页管理

6.文件的逻辑结构及物理结构

四、考核要求

识记：操作系统的基本概念。

领会：操作系统的功能任务、操作系统的发展历程、操作系统的分类。

简单应用：死锁、P/V操作，分段管理，分页管理，文件的逻辑结构及物理结构。

综合应用：能采用图示法综合应用PV操作解决死锁问题，应用储存空间的组织相关知识解决段页式管理的问题，应用文件管理的相关知识解决文件的逻辑结构和物理结构问题。

第5章 数据库设计技术

一、学习目的与要求

数据库是信息管理中广为使用的数据处理软件，它能实现有组织地动态的储存大量的关联数据，方便用户的使用。数据库与文件系统的重要区别是数据的充分共享、交叉访问、与应用程序的高度独立性。

要了解数据库系统的基本概念以及数据系统库的优点，了解数据库系统的体现结构。其次要求了解关系代数和关系数据库的基本概念。

二、考试内容

5.1 数据库基本概念

 5.1.1 数据库技术与数据库系统

 5.1.2 数据描述

 5.1.3 数据模型

5.2 关系代数

5.3 数据库设计

 5.3.1 数据库设计的基本概念

 5.3.2 数据库设计的过程

 5.3.3 数据字典

三、考核知识点

1、数据的基本概念

2、数据库的三个特点、数据库通常具有的功能、数据库管理系统中主要程序模块的划分。

3、数据库系统的层次结构。

4、数据的描述、三种数据模型、实体

5、关系代数

6.数据库的设计基本概念、设计过程、数据字典。

四、考核要求

识记：数据的基本概念、数据库的设计基本概念。

领会：数据库的三个特点、数据库通常具有的功能、数据库管理系统中主要程序模块的划分。数据的描述、三种数据模型。数据库的逻辑结构和物理结构

简单应用：关系代数，ER图。

综合应用：能够运用本章所规定的知识分析一些实际问题和案例。

第6章 编译技术概述

一、学习目的与要求

编译程序是将源代码翻译成等价的目标程序的一种翻译程序。通过本章的学习，应了解编译程序的工作及基本组成。

二、考试内容

6.1 编译程序的工作过程及其基本组成

 6.1.1 编译程序的工作过程

 6.1.2 编译程序的基本组成

*6.2 状态矩阵法的编译过程

 *6.2.1 状态矩阵法的基本原理

 *6.2.2 状态矩阵的压缩

*6.3 词法分析

 *6.3.1 词法分析的任务

 *6.3.2 读字符程序

 *6.3.3 状态矩阵法的词法分析过程

 *6.3.4 算术常数的识别和翻译

*6.4 中间语言表示

 *6.4.1 波兰表示

 *6.4.2 三元组表示

*6.5 语法的分析与加工

三、考核知识点

1、编译程序的工作过程

2、编译程序的基本组成

四、考核要求

识记：编译技术的基本概念。

领会：编译程序的工作过程、编译程序的基本组成。

简单应用：无。

综合应用：无。

第7章应用软件设计与开发技术

一、学习目的与要求

软件工程的最终目的是以最科学的方法获取高质量的软件产品，它研究如何应用一些科学理论和工程技术指导大型软件的开发，在促进计算机的推广应用及加快软件产业的发展具有十分重要的作用。

首先要了解软件工程的基本概念及软件详细设计的表达，其次要领会结构化分析与设计方法，测试与调试的基本方法，还有了解软件开发的新技术。

二、考试内容

7.1 软件工程概述

 7.1.1 软件工程的概念

 7.1.2 软件生命周期

 7.1.3 软件支援环境

7.2 软件详细设计的表达

 7.2.1 程序流程图

 7.2.2 NS图

*7.2.3 问题分析图PAD

*7.2.4 判定表

*7.2.5 过程设计语言PDL

7.3 结构化分析与设计方法

 7.3.1 应用软件开发的原则和方法

 7.3.2 结构化分析方法

 7.3.3 结构化设计方法

7.4 测试与调试基本技术

 7.4.1 测试

 7.4.2 调试

7.5 软件开发新技术

 7.5.1 原型方法

 7.5.2 瀑布模型

 7.5.3 面向对象技术

三、考核知识点

1、软件生命期

2、程序流程图、ns流程图

3、软件开发的原则和方法、结构化分析方法及设计方法

4、软件测试

5、瀑布模型、原型方法

四、考核要求

识记：软件生命期的基本概念，应用软件开发的原则和方法分类。

领会：程序流程图，NS图，结构化分析方法（SA法），数据流图，数据字典，SD法，结构图，。

简单应用：测试的方法、白箱法、黑箱法、五类调试技术、瀑布模型。

综合应用：能够运用本章所规定的基本知识分析一些实际问题和案例。

 Ⅲ有关说明与实施要求

一、本课程的性质及其在专业考试计划中的地位

计算机软件基础是工业自动化专业、电气工程及其自动化专业的一门专业基础课，主要叙述计算机软件基本原理及其应用。通过本课程的学习，使应考者能对计算机软件知识有一个基本的了解，从而提高使用计算机的能力和掌握正确开发应用软件的方法。

二、本课程考试的总体要求

本课程的考试，既要考核知识，又要考核能力。因此，在系统掌握本课程的基础知识和基本原理的基础上，注重运用基础知识和基本理论分析和解决实际问题，做到理论联系实际，提高分析和解决实际问题的能力。

本课程的基本知识和基本原理包括本大纲所列出的考核点，在自学中注意各知识点、基本原理的比较，综合和归纳，及其之间的联系和区别。同时要注意分析实际问题。

本大纲规定的考试内容每章先概述全篇的自学要求、考试内容，然后列出本章的考核知识点，再对考核知识点提出不同认识能力层次要求。本大纲各章规定的自学要求、考核知识及考核知识点的知识细目都是考试内容。

本大纲的考核要求分为“识记”、“领会”、“简单应用”、“综合应用”四个层次，具体含义为：

识记：能正确认识和表述科学事实、原理、术语和规律，知道该课程的基础知识，并能进行正确的选择和判断。

领会：能将所学知识加以解释、归纳，能领悟某一概念或原理与其他概念或原理之间的联系，理解其引申意义，并能做出正确的表述和解释。

简单应用：能用所学的概念、原理、方法正确分析和解决较简单问题，具有分析和解决一般问题的能力。

综合应用：能灵活运用所学过的知识，分析和解决比较复杂的问题，具有一定解决实际问题的能力。

三、关于自学教材

指定使用教材：《计算机软件技术基础》（第三版），徐士良、葛兵编著，清华大学出版社，2010年9月第3版。

参考习题集：《计算机软件技术基础》（第三版）习题解答，徐士良、葛兵编著，清华大学出版社，书号ISBN 978-7-302-23408-1。

四、自学方法指导

 1、本课程自学对自学者来说是一门较难的课程。本课程考试内容覆盖较广，因此自学应考者必须注意全面、系统地学习，切忌猜题、押题。

 2、本课程的每一章基本上是一门学科的内容，因此各章的内容学习方法有所区别。第二章数据结构及其运算是通过数据的逻辑结构、每种逻辑结构在计算机中的存储结构以及在该种存储结构上的相应算法这样一套组织体系来学习的。要熟练掌握用图示的方法来表明数据的逻辑结构、存储结构及其基本运算。第三章查找与排序，要掌握图示的方法来表示各种查找、排序的步骤及结果。第四章操作系统的主要工作是管理计算机的硬件资源，考生要注意这条主线。第六章数据库技术要了解数据库的基本概念，掌握数据库与其他文件系统的区别，从而对数据库技术有深入的理解。第七章软件设计与开发应用主要是学习软件开发的过程，要对软件开发的阶段的划分、各个阶段需要对达到的目的以及采用的方法要有一个完整的了解。需要结合自己熟悉的实例来进线思考。

 3、自学考试是终结性考试，自学应考者应具有一定的综合应用知识的能力。本大纲对考核知识点及知识点下的知识细目所提出的具体要求，不要以为一道试题只考核一个知识点，有时还可能综合考核多个知识点。因而在学完各章后，应及时对概念、基础知识和基本理论进行归纳，注意它们之间的联系和区别，并注意综合应用的训练。

 4、本大纲分考试大纲说明、各章考试内容、考核知识点、考核要求，自学应考者必须全面阅读。

五、关于命题考试的若干要求

 1、本课程的命题考试，应根据本大纲所规定的考试内容和考试目标来确定考试范围和考核要求，不要任意扩大或缩小考试范围，提高或降低考核要求。考试命题要覆盖到大纲所列各章，并适当突出重点章节，体现本课程的内容重点。

 2、本课题在试题中对不同能力层次要求的分数比例，一般为：识记占20%，领会占30%，简单应用占30%，综合应用占20%。

 3、试题要合理安排难度结构，试题难易度可分为易、较易、较难、难四个等级，每份试卷中，不同难易度试题的分数比例，一般为：易占20％，较易占30％，较难占30％，难占20％。必须注意，难题的难易度与能力层次不是一个概念。

 4、本课程考试试卷采用的题型，一般有：单项选择题、填空题、名词解释、简答题、应用题。各种题型的具体形式可参加本大纲附录。

 5、本课程的考试形式为闭卷笔试，考试时间为150分钟

附录：题型举例

一、单项选择题

1. 线性表在采用链式存贮时，其地址（       ）

 A．必须是连续的B．一定是不连续的

 C．连续不连续都可以D．部分是连续的

2.深度为5的二叉树的结点最多有（       ）

 A．10个B．16个

 C．31个D．32个

二、填空题

1．软件系统生存的漫长周期称为_____。

 2．有一个长度为n的顺序表，在该表第i(1≤i≤n)个元素之后插入一个元素，需向后移动的元素个数为____。

三、名词解释

1．线性结构

2．树的定义

四、简答题

1．有一棵二叉树如题1图所示，试写出该二叉树的先序遍历和后序遍历序列。

题1图

五、应用题

 1．采用图示法描述一个在头指针为head的单链表中第i(i≥0)个结点之后插入一个元素为x结点的算法。

 2．在采用连续结构的文件系统中，有一文件df.c的大小是2988字节，磁盘物理块的大小是1024字节。文件占用的第1个物理块号是200。

  （1）试画出文件df.c的物理结构图；（4分）

  （2）从文件的第2000个字节开始读200个字节，将要读该文件的哪些物理块（写出分    析过程，给出物理块号）。（4分）