一、填空
1．传统的集合“并、交、差”运算施加于两个关系时，这两个关系的属性个数必须相等，相对应的属性值必须取自同一个域。
2．指出下列缩写的含义：DBMS DBMS数据库管理系统、DBA DBA 数据库管理员。
5．数据库在运行过程中可能产生的故障有①Transaction failure②System crash③Disk failure
3．关系数据库中基于数学上两类运算是关系代数和关系演算。
4．数据库设计的几个步骤是需求分析，概念设计，逻辑设计，物理设计，编码和调试、实施运行和维护。
7．关系操作的特点是集合操作。
5．在关系数据库的规范化理论中，在执行“分解”时，必须遵守规范化原则：保持原有的函数依赖和无损连接。6．SQL语言的数据定义功能包括定义数据库、定义基本表、定义视图和定义索引。
二、判断
1.view可串行化的调度(schedule)一定也是冲突(conflict)可串行化的调度。错
2.在确定关系的候选码时，如果属性X在函数依赖的左右都不出现，则候选码中必不包含X。错
三、简答
2．什么是关系的外码？并举例说明。
答：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R 的外部码，也称外码。学生数据库中有关系STUDENT（SNO，SNAME，SEX，AGE）、关系COURSE
（CNO，CNAME）和关系SC（SNO，
CNO，GRADE），SC关系中SNO
是外码，其参照关系是
STUDENT；CNO也是外码，其参
照关系是COURSE。
3．如何通过定义视图和存取
控制保证数据库的安全性？
并用SQL语言举例说明。
视图能够对机密数据提供安
全保护。有了视图机制，就可
以在设计数据库应用系统时，
对不同的用户定义不同的视
图，使机密数据不出现在不应
看到这些数据的用户视图上，
这样就由视图的机制自动提
供了对机密数据的安全保护
功能。例如Student表涉及三
个系的学生数据，可以在其上
定义三个视图，每个视图只包
含一个系的学生数据，并只允
许每个系的学生查询自己所
在系的学生视图。
例：建立信息系学生的视图。
CREATE VIEW IS_Student
AS
SELECT Sno, Sname,
Sage
FROM Student
WHERE Sdept='IS';
数据库的安全性是指保
护数据库，防止不合法的使用
所造成的数据泄露和破坏。数
据库系统中保证数据安全性
的主要措施是进行存取控制，
即规定不同用户对于不同数
据对象所允许执行的操作，并
控制各用户只能存取他有权
存取的数据。不同的用户对不
同的数据应具有何种操作权
力，是由DBA和表的建立者（即
表的属主）根据具体情况决定
的，SQL语言则为DBA和表的
属主定义和回收这种权力提
供了手段。
例：把查询Student表权限授
给用户U1。
GRANT SELECT ON TABLE
Student TO U1;
1．什么是数据库？
答：数据库是长期存储在计算
机内、有组织的、可共享的数
据集合。数据库是按某种数据
模型进行组织的、存放在外存
储器上，且可被多个用户同时
使用。因此，数据库具有较小
的冗余度，较高的数据独立性
和易扩展性。
2．什么是数据库的数据独立
性？
答：数据独立性表示应用程序
与数据库中存储的数据不存
在依赖关系，包括逻辑数据独
立性和物理数据独立性。
逻辑数据独立性是指局
部逻辑数据结构（外视图即用
户的逻辑文件）与全局逻辑数
据结构（概念视图）之间的独
立性。当数据库的全局逻辑数
据结构（概念视图）发生变化
（数据定义的修改、数据之间
联系的变更或增加新的数据
类型等）时，它不影响某些局
部的逻辑结构的性质，应用程
序不必修改。
物理数据独立性是指数据的
存储结构与存取方法（内视
图）改变时，对数据库的全局
逻辑结构（概念视图）和应用
程序不必作修改的一种特性，
也就是说，数据库数据的存储
结构与存取方法独立。
数据独立性的好处是，数据的
物理存储设备更新了，物理表
示及存取方法改变了，但数据
的逻辑模式可以不改变。数据
的逻辑模式改变了，但用户的
模式可以不改变，因此应用程
序也可以不变。这将使程序维
护容易，另外，对同一数据库
的逻辑模式，可以建立不同的
用户模式，从而提高数据共享
性，使数据库系统有较好的可
扩充性，给 DBA维护、改变数
据库的物理存储提供了方便。
3．叙述等值连接与自然连接
的区别和联系。
答：等值连接表示为R A=B S，
自然连接表示为R S；自然
连接是除去重复属性的等值
连接。两者之间的区别和联系
如下：
自然连接一定是等值连接，但
等值连接不一定是自然连接。
等值连接不把重复的属性除
去；而自然连接要把重复的属
性除去。
等值连接要求相等的分量，不
一定是公共属性；而自然连接
要求相等的分量必须是公共
属性。
等值连接不把重复的属性除
去；而自然连接要把重复的属
性除去。
2．数据库管理系统有哪些功
能？
答：数据库管理系统（DBMS）
是位于操作系统与用户之间
的一个数据管理软件，它主要
功能包括以下几个方面：
·数据定义功能 DBMS提
供数据描述语言（DDL），用户
可通过它来定义数据。
·数据操纵功能 DBMS还
提供数据操纵语言（DML），实
现对数据库的基本操作：查
询、插入、删除和修改。
·数据库的运行管理这
是DBMS运行时的核心部分，
它包括开发控制，安全性检
查，完整性约束条件的检查和
执行，数据库的内容维护等。
·数据库的建立和维护功能
它包括数据库初始数据的输
入及转换，数据库的转储与恢
复，数据库的重组功能和性能
的监视与分析功能等。
3．事务中的提交和回滚是什
么意思？
答：事务中的提交（COMMIT）
是提交事务的所有操作。具体
说就是将事务中所有对数据
库的更新写回到磁盘上的物
理数据库中去，事务正常结
束。
事务中的回滚（ROLLBACK）是
数据库滚回到事务开始时的状态。具体地说就是，在事务运行的过程中发生了某种故障，事务不能继续执行，系统将事务中对数据库的所有已完成的更新操作全部撤消，使数据库回滚到事务开始时的状态。
五应用题
1.已知 R
U={ A,B,C,D,E }
F={AB →C, C →D,D →E}
R的一个分解ρ={ R1( A,B,C )，R2(C,D)，R3(D,E) }
判断ρ是否为无损连接？
1.构造一个初始二维表如下图
2.运用函数依赖后，
二维表最终变为如下表所示
因此该分解是无损连接的。
3 由Armstrong公理证明：
合并规则：若X->Z , X->Y, 则X->YZ
证明：因为 X→Y
所以 X→XY （增广律）
因为 X→Z
所以 XY→ZY （增广律）
所以 X→YZ （传递律）
六、综合题：
1.．设工厂里有一个记录职工每天日产量的关系模式：
R（职工编号，日期，日产量，车间编号，车间主任）。
如果规定：每个职工每天只有一个日产量；
每个职工只能隶属于一个车间；
每个车间只有一个车间主任。试回答下列问题：⑴根据上述规定，写出模式R
的基本FD和关键码；
⑵说明R不是2NF的理由，
并把R分解成2NF模式集；
⑶进而再分解成3NF模式集，
并说明理由。
1．解：①基本的FD有3个：
（职工编号，日期）→日产
量职工编号→车间编
号
车间编号→车间主
任R的关键码为（职
工编号，日期）。
② R中有两个这样的
FD：（职工编号，日期）→（车
间编号，车间主任）
职工编号→（车间编号，车
间主任）可见前一个FD是局
部依赖，所以R不是2NF模式。
R应分解成R1（职工编号，车
间编号，车间主任）
R2（职工编号，日期，日产量）
此处，R1和R2都是2NF模式。
③ R2已是3NF模式。在R1中，
存在两个FD：职工编号→车
间编号车间编号→车间
主任
因此，“职工编号→车
间主任”是一个传递依赖，R1
不是3NF模式。
R1应分解成R11（职工编
号，车间编号）
R12（车间编号，车间主任）
这样，ρ= { R11，R12，R2 }
是一个3NF模式集。
2．设有关系S、SC、C，试用
关系代数、元组关系演算表达
式和SQL完成下列操作。（15
分，每小题5分）
S(S#,SNAME,AGE,SEX) 例：
（001,'李强',23,’男'）
SC(S#,C#,SCORE)例：
（003,'C1',83）
C(C#,CNAME,TEACHER)例：
（'C1','数据库原理','王华
'）
（1）试用关系代数检索选修
了“程军”老师所授课程之
一的学生姓名。
∏SNAME (S SC TEACHER='程军'(C))
（2）试用元组关系演算表达
式检索选修了“程军”老师
所授课程之一的学生姓名。
{T(1)|(?U)(?V)(?W)(S(U)∧
SC(V)∧C(W)∧T[1]=U[1]∧
U[1]=V[1]∧V[2]=W[1]∧
W[3]='程军')}
（2）试用元组关系演算表达
式检索选修了“程军”老师
所授课程之一的学生学号。
{T(1)| (?V)(?W)( SC(V)∧C(W)
∧T[1]=V[1]∧V[2]=W[1]∧
W[3]='程军')}
（3）找出“程序设计”课程
成绩在90分以上的学生姓名。
SELECT SNAME
FROM S,SC,C
WHERE S.S#=SC.S# AND
SC.C#=C.C# AND SCORE>=90
AND CNAME='程序设计'
或者
SELECT SNAME
FROM S
WHERER S.S# IN (SELECT S#
FROM SC
WHERE SCORE>=90 AND C.C#
IN (SELECT C# FROM C
WHERE CNAME='程序设计')
2．设有关系S、SC、C，试用
关系代数、元组关系演算表达
式和SQL完成下列操作。（15
分，每小题5分）
S(S#,SNAME,AGE,SEX) 例：
（001,'李强',23,’男'）
SC(S#,C#,SCORE) 例：
（003,'C1',83）
C(C#,CNAME,TEACHER) 例：
（'C1','数据库原理','王华
'）
（1）用关系代数检索既选修
了C1课程，又选修了C2课程
的学生学号。
(∏SNAME
(S C#='C1'
（SC）))∩(∏SNAME
(S C#='C2'
（SC）))
（2）用元组关系演算表达式
检索年龄大于21的男生的学
号和姓名。
{t(2)|(?r)(S(r)∧t[1]=r[1]
∧t[2]=r[2]∧r[3]>21∧
r[4]='男')}
（3）用SQL找出“程序设计”
课程成绩在90分以上的学生
姓名。
解：
SELECT SNAME
FROM S,SC,C
WHERE S.S#=SC.S# AND
SC.C#=C.C# AND SCORE>=90
AND CNAME='程序设计'
或者
SELECT SNAME
FROM S
WHERER S.S# IN (SELECT S#
FROM SC
WHERE SCORE>=90
AND SC.C# IN (
SELECT C#
FROM C WHERE CNAME='程序设
计')
2．设有关系S、SC、C，试用
关系代数、元组关系演算表达
式和SQL完成下列操作。（15
分，每小题5分）
S(S#,SNAME,AGE,SEX) 例：
（001,'李强',23,’男'）
SC(S#,C#,SCORE) 例：
（003,'C1',83）
C(C#,CNAME,TEACHER) 例：
（'C1','数据库原理','王华
'）
（1）用关系代数检索选修课
程号（C#）为C1和 C2的学生
学号（S#）。
ΠS＃，C＃（SC）÷ΠC＃（σC＃=’C1’∨
C＃=’C2’（C））-σC#≠’C1’ ∨C#≠’C2’
（ΠS＃，C＃（SC）÷ΠC＃（σC＃=’C1’∨
C＃=’C2’（C）））
（2）用元组关系演算表达式
检索选修了“程军”老师所
授课程之一的学生姓名。
{T(1)|(?U)(?V)(?W)(S(U)∧S
C(V)∧C(W)∧T[1]=U[1]∧U[
1]=V[1]∧V[2]=W[1]∧W[3]= '程军')}
（2）用元组关系演算表达式检索选修了“程军”老师所
授课程之一的学生学号。
{T(1)|
(?V)(?W)( SC(V)∧C(W)∧T[ 1]=V[1]∧V[2]=W[1]∧W[3]= '程军')}
3．设有关系模式R（U，F），其中：（10分）
U={A，B，C，D，E}，F = { A →BC，CD→E，B→D，E→A}。
⑴计算B+。（2分）
⑵求R的所有候选码。（8分）
解：
⑴令X={B}，X(0)=B，X(1)=BD，X(2)=BD，故B+=BD。
⑵根据候选码的定义，R的候选码只可能由F中各个函数依赖的左边属性组成，即A，B，C，D，E，由于A→BC（A→B，A→C），B→D，E→A，故：
可除去A，B，C，D，?组成候选码的属性可能是E。
计算可知：E+=ABCDE，即E→U，? E是一个候选码。
可除去A，B，E，?组成候选码的属性可能是CD。
计算可知：(CD)+=ABCDE，即CD→U，但C+=C，D+=D，? CD 是一个候选码。
可除去B，C，D，E，?组成候选码的属性可能是A。
计算可知：A+=ABCDE，即A→U，? A是一个候选码。
可除去A，D，E，?组成候选码的属性可能是BC。
计算可知：(BC)+=ABCDE，即CD→U，但B+=BD，C+=C，? BC 是一个候选码。
R的所有候选码是A，BC，CD，E。
4.设有关系STUDENT(S#,SNAME,SDEPT,MN AME,CNAME,GRADE)，S#,CNAME 为候选码，设关系中有如下函数依赖：（10分）
S#,CNAME→SNAME,SDEPT,MNAME
S#→SNAME,SDEPT,MNAME
S#,CNAME→GRADE
SDEPT→MNAME
试求下列问题：
（1）关系STUDENT属于第几范式？（5分）
（2）如果关系STUDENT不属于BCNF，请将关系STUDENT逐步分解为BCNF。（5分）
要求：写出达到每一级范式的分解过程，并指明消除什么类型的函数依赖。
解：（1）关系STUDENT是1NF。
（2）首先消除部分函数依赖
{S#,CNAME}→
{SNAME,SDEPT,MNAME}
将关系分解为：
R1(S#,SNAME,SDEPT,MNAME)
R2(S#,CNAME,GRADE)
在关系R1中存在非主属性对候
选码的传递函数依赖S#→
SDEPT，SDEPT→MNAME，所以以
上关系模式还不是BCNF，进一
步分解R1：
R11(S#,SNAME,SDEPT)
R12(SDEPT,MNAME)
R11,R12都是3NF。
关系模式：
R2(S#,CNAME,GRADE)
R11(S#,SNAME,SDEPT)
R12(SDEPT,MNAME)
R2,R11,R12关系模式存在的
函数依赖
S#,CNAME→GRADE S#→
SNAME,SDEPT SDEPT→MNAME
上述函数依赖都是非平凡的，
并且决定因素是候选码，所以
上述关系模式是BCNF.
3．设有函数依赖集 F = { D
→G，C→A，CD→E，A→B}，
计算闭包D+，(AC)+，(ACD)+。
解：令X={D}，X(0)= D，X(1)= DG，
X(2)=DG，故D+=DG。
令X={AC}，X(0)= AC，X(1)=ABC，X(2)=ABC，故(AC)+=ABC。
令X={ACD}，X(0)= ACD，
X(1)=ABCD，X(2)=ABCDG，
X(3)=ABCDEG，故(ACD)+=ABCDEG
4．设有关系R和函数依赖F
R（W，X，Y，Z），F = { X→Z，
WX→Y }。
试求下列问题：（1）关系R
属于第几范式？（5分）
（2）如果关系R不属于BCNF，
请将关系R逐步分解为BCNF。
（5分）
要求：写出达到每一级范式的
分解过程，并指明消除什么类
型的函数依赖。
解：R是1NF。侯选码为WX，
则Y，Z为非主属性，又由于X
→Z，因此F中存在非主属性
对侯选码的部分函数依赖。
将关系分解为：
R1（W，X，Y），F1 = { WX→
Y }
R2（X，Z），F2 = { X→Z }
消除了非主属性对码的部分
函数依赖。
F1和F2中的函数依赖都是非
平凡的，并且决定因素是候选
码，所以上述关系模式是
BCNF。
3．设有关系模式R（U，F），
其中：
U={E，F，G，H}，F={E→G，
G→E，F→EG，H→EG，FH→E}
求F的最小依赖集。
解：
⑴将F中右部属性单一化：
（2分）
F1= {E→G，G→E，F→E，F
→G，H→E，H→G，FH→E}
⑵去掉冗余的函数依赖。对
于FH→E，由于有F→E，则为
多余的。
F2= {E→G，G→E，F→E，F
→G，H→E，H→G} （2分）
(3) F2中的F→E和F→G，以
及H→E，H→G之一是冗余的，
则： F3= {E→G，G→E，F→G，
H→G}
1、选修了全部课程的学生姓
名
SLELECT Sname FROM
Student WHERE NOT EXISTS
(SELECT *FROM Course
WHER NOT EXISTS
(SELECT *FROM SC
WHERE Sno=Student.Sno
AND Cno=https://www.doczj.com/doc/1215090819.html,o));
2、至少选修了学生‘2005’
选修的全部课程的Sno。
SELECT Sno FROM SC SCX
WHERE NOT
EXISTS(SELECT*FROM SC
SCY WHERE
SCY.Sno=’2005’AND NOT
EXISTS(SELECT*FROM SC
SCZ WHERE
SCZ.Sno=SCX.Sno AND
https://www.doczj.com/doc/1215090819.html,o=https://www.doczj.com/doc/1215090819.html,o));
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
数据结构期末考试题及标准答案
————————————————————————————————作者：————————————————————————————————日期：
2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。
s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。
2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序
第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长
引言 用计算机解决问题一般步骤： 一般来说，用计算机解决一个具体问题时，大致经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整知道的到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 三种经典的数学模型 图书书目自动检索系统——线性关系 博弈问题——树 城市道路问题——图 数据结构（data structure ） 简单的解释：相互之间存在一种或多种特定关系的数据元素的集合。 数据间的联系有逻辑关系、存储联系，通常的数据结构指的是逻辑结构。 前面提到的三种经典的数学模型体现了数据结构的基本结构，数据结构通常有如下四种关系：（1）集合结构 （2）线性结构 （3）树形结构 （4）图状结构 ☆ 线性表（一） N 个数据元素的有限序列 存储结构：顺序存储结构、链式存储结构 当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。删除元素呢？ ☆ 线性表（二） 链式存储 插入新元素的时候只需要改变指针所指向的地址。 ☆ 二维数组与线性表 如果某一线性表，它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用二维数组。 二维数组的一个形象比喻—— 多个纵队形成的方块 m * n ☆ 数组地址计算问题 题目描述：已知N*(N+1) / 2个数据，按行的顺序存入数组b[1],b[2],…中。其中第一个下标表示行，第二个下标表示列。若aij (i>=j ,j=1,2,…,,n)存于b[k]中，问：k,i,j 之间的关系如何表示？给定k 值，写出能决定相应i,j 的算法。 具体问题 数学 模型 算法 编程、调试 得到答案
2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.
数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7.
自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j
广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构
D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1数据结构期末考试试题及答案
大学数据结构期末知识点重点总结
相关主题
文本预览