华中科技大学2005年博士研究生入学考试——软件基础 rI'kZ0&
Eyh(2 57
第一部分：考试说明 , GMuq_H
7,3 g{8
考试范围：数据结构与数据库系统基础。 F>U*Wy
考试形式与试卷结构： tN_~zP
（一） 答卷形式：闭卷，笔试；所列题目均为必答题。 ~EO=;a_
（二） 答题时间：180分钟。 RY9Ur
（三） 各部分考察比例： NC%)SG \
1） 数据结构部分：40% 8nTdZu
2） 数据库部分：60% 2$O6%0
（四） 题型比例 jF 6[+bW<
填空题：约30% @O|
l A
简答或程序分析题：约30% tRXR/;3O
程序、算法设计或综述性题目：40% p;rT#R&6>
;|.IUXEgcF
第二部分：考察要点 V3[>^ZCA
^f hkWx 4i
A. 数据结构部分 j12khp?
r~sQdf
一、 基本概念： 2@f?yh0
1. 熟悉数据、数据元素等名词术语的基本概念。了解抽象数 t**o<p#)f
据类型的定义、表示和实现方法，熟悉类C语言的书写规范。 FQ w@ @
2. 了解计算语句频度和估算时间算法复杂度的方法 CDGN}Q2 _
?Q/9aqHe;
二、 线性表、栈、队列 YojYb]y+ j
1. 理解线性表的逻辑结构，掌握线性表在顺序存储及链表结构结构上实现基本操作的算法。 LE@`TPg$R
2. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 ]`
}R,'P
3. 掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法。 S1W(]%0/
4. 了解递归算法执行过程中栈的状态变化过程。 O xr?y8C~
5. 了解递归算法到非递归算法的机械转化过程。 /@f3|L<1@V
qJLtqv
三、 串 H8?Kgaj~vf
1. 掌握串的七种基本操作的定义，并能利用这些基本操作实现串的其他各种操作的方法。 }| 4dEao\
2. 了解串的定长顺序存储结构上实现串的各种操作的方法。 /]" 2;e-s+
3. 了解串的堆存储结构以及在其上实现串操作的基本方法。 VU
8 ~hF
4. 了解串匹配的KMP算法。 MYF6tZ*
5. 了解串操作的应用方法和特点。 9Sk?tl
Mwd(?o
四、 数组与广义表 "+:~#&r
1. 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 m@^!?/as
2. 了解特殊矩阵进行压缩存储时的下标变换公式。 k-a3oLCR,
3. 了解稀疏矩阵的两种压缩存储方法的特点和适用范围。 9?# L/
4. 了解广义表的结构特点及其存储表示方法。 -P|st;?#
8^%Nl `_2B
五、 树和二叉树 U> s$}Y:+Z
1． 熟练掌握二叉树的结构特性，了解相应的证明方法。 V+2C!)f(
2． 熟悉二叉树的各种存储结构的特点及适用范围。 ds" q1
3． 熟悉遍历二叉树的基本概念、性质与实现方法。 oN6X]T<
4． 了解树的存储结构及其特点，理解树和森林与二叉树的转 换方法。 =g+Rk+ jn
5． 了解最优树的特性。 qg#|1J6e
c})f&Z@<
六、 图 Kt3 ]r:&J
1. 理解图的各种存储结构及其构造算法。 {*J{1)2
2. 掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。 0xQ="aXE
Z&E!m
七、 动态存储管理 K6l{wyMb|
了解动态存储管理策略和算法，理解各种概念。 :7-2^7z)
@fSBW+
八、 查找与排序 3.?kxac
1. 掌握顺序表和有序表的查找方法。 U4*Q
;A#
2. 了解静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系。 O>H'o k
3. 掌握二叉排序树的构造和查找方法。 ckTk2x
PQ
4. 了解二叉平衡树的维护平衡方法。 x<es1A'u6
5. 了解哈希表的构造方法，理解哈希表与其他结构的表的实质性的差别。 wfXm(RYM
6. 了解描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 hPB^|#}
7. 理解排序的定义和各种排序方法的特点。 !ENDQ?1
8. 了解各种方法的排序过程及其依据的原则。 J*} warf&
9. 了解各种排序方法的时间复杂度的分析方法。 86AZ)UP2D
10. 了解“表排序”和“地址排序”的过程及其适用场合。 %2j R J
11. 理解外部排序的两个阶段和第二阶段——归并的过程。 F
bWcq_
12. 了解外部排序过程中所需进行外存读/写次数计算方法。 iir]M`A.-
HDY2<Hzc
九、 文件 9_
熟悉各类文件的特点、构造方法以及如何实现检索、插入和删除等操作。能构造各种组织方式的文件。 [, )G\
f6r~Ycf,f
^f%hhpV@
B. 数据库部分 DQy<!Wb+
G)G
257K"~
一、 数据库系统概念 qTuQ]*[-
1． 了解数据处理的主要技术与方法：传统的文件方法、文件管理系统方法、数据库方法及它们的主要特点。 Sbp].3^j
2． 熟悉掌握数据库系统的功能特性。 FP_q?=~rFs
3． 熟练掌握三种主要数据模型：层次模型，网状模型与关系模型。 %Y:"5fH
4． 了解语义数据模型，熟悉E-R模型。 9z$fDs }.q
5． 了解面向对象数据模型。 ,|RN?1 ?U
6． 熟悉数据库的多层视图与模式。 MoX~ZewWR
7． 了解数据库与企业信息系统的关系。 {)?:d6"
};Oyv7D+b
二、 数据库存储结构
A 6IrA/b
1． 熟悉数据的外存组织，物理块的概念，组块与解块，块的编址。 Oe~x,=X)
2． 熟悉基本的文件组织形式，主要有顺序文件组织、随机文件组织、链表组织、树结构文件组织。 PptVneujI
3． 了解索引文件组织及B-树与B+树。 [(rT,31cW
J{!U;r!6
三、 数据库管理软件 =f/CBYNw@V
1． 数据库管理软件的主要目标。 8= kwc
2． DBMS的功能与组成。 Mm)yabP
3． 了解几种具有代表性的关系数据库管理软件系统如ORACLE，SQL SERVER。 E#!tXO&,
4． 客户机/服务器结构的基本概念和一些常用的前端开发工具。 -Lhq.Q*a
[p+ -]V
四、 层次数据库系统 NHL9qL"qk
1． 理解IMS的系统结构 9] Fi2M
2． 了解IMS物理数据库（PDB）及其描述（DBDJ）。 J yO2 P
3． 了解IMS逻辑数据库的概念、定义及处理。 ]?6Pt: N2
4． 了解IMS的数据操纵。 1.tAl6]
;l %$-/%
五、 网状数据库系统 48IrC_0j
1． 理解DBTG数据结构，包括数据项、组合项、重复组及系的概念。 dfP4SJqq
2． 了解DBTG数据描述。 0,/I2!dF?
3． 了解DBTG模式描述语言。 hp1+9vEN
4． 了解DBTG数据操纵语言。 ZXIw^!8@/
X- ZZLl#
六、 关系数据库系统 I`f5)iF?0
1． 熟悉关系模式、关系数据库模式、视图等基本概念。 ]t0St~qUL)
2． 了解关系代数。 J= [D'h
3． 了解关系演算。 d9&
/go|r '
七、 SQL语言 *4ido?
1． 熟悉SQL语言的基本概念与特点。 6_s(Kx>j
2． 熟悉并能运用SQL语言完成数据定义与数据操作 eaC%& k
3． 理解SQL语言的安全与授权。 RR+{uSO,t
4． 了解嵌入式SQL语言。 Fw S>V2R
5． 了解关系数据库设计理论。 E<jW; trt_
=C2KHNc
八、 数据库设计 `a%MD>R_Lg
1． 熟悉数据库设计步骤。 >%ovL8F
2． 熟悉需求分析的任务、步骤与内容。 %.m+6
zaF
3． 熟悉概念设计的任务、步骤与方法。 -&CO I-P8
4． 熟悉实现设计的任务与方法。 %q}[ZD/HD
5． 理解物理设计的任务及关系数据库物理设计的目标与内容。 q 3<kr<SP
6． 了解关系规范化，包括函数依赖概念，关系规范化的INF到BCNF的概念与方法。 g ) 5mr:\
7． 理解完整性概念、限制及检验。 ^)wKS]BQ..
8． 理解安全性控制。 Vr|e(e.%
9． 熟悉事务及一致性概念，典型的一致性（并发）控制问题、控制方法及标准。 QgI[#
d{
10． 熟悉并发控制中锁等的基本概念，分类及封锁协议。 p- a{6<h
11． 熟悉恢复的概念、可能的系统故障及其恢复的技术与过程。 8qqN0"{,
{#:31)P
九、 数据库的运行与管理 D<m0G]Ht*
1． 了解数据库运行环境的构成与建立。 @ 5^nrB
2．了解应用程序运行时对数据库存取的系统工作原理。数据库的运行监视与维护。 ei<0,w[V1{
3． 了解数据库管理的职责范围与任务，DBA的组织。 2j: 0!%
4． 了解数据库开发过程的管理。 zs~T u
5Yhcnwdm!
十、 数据库的新发展 zGFD71=#
1． 分布式数据库系统 hbOXR.0z
1）熟悉分布式数据库的基本概念与体系结构。 Kp6 @?
2）了解分布式数据库设计。 K8aqC{
3）理解分布式数据库的事务管理与并发控制。 b,^Gj]7
2． 演绎数据库 d)e mTXB(
1）了解演绎数据库的基本概念与体系结构。 _0jR({\
2）了解的演绎数据库与知识库、智能数据库的联系。 odSPl{. >d
3． 专家数据库系统 z 7ik/> d?
1）了解专家数据库的基本概念。 X+C*+k,z
2）了解人工智能与数据库技术的发展。 ~g\~x
3）了解专家知识库数据模型。 7IkPi?&{
4． 工程数据库系统 X>Vc4n<}
1）了解工程数据库基本概念。 U\p`Y
Z
2）了解工程数据库应用环境与特点要求。 *^uK=CH1?(
VD$5 Djq
2004.7.7
