A．maze（16,2,2）的返回值是8B．maze（160,10,5）的返回值是25C．maze（160,10,5）的返回值是40D．以上三种叙述都不对
（17）已知广义表L=（（x,y,x）,a,（u,t,w））,从L中取出元素项t的运算是（A）。
A．head（tail（tail（tail（L））））B．tail（head（head（tail（L））））
C．head（tail（head（tail（L））））D．head（tail（head（tail（tail（L）））））
（18）某二叉树的前序遍历结点序列为abcdefg，中序遍历结点序列为cbdaefg，则它的后序遍历结点序列为（D）。
A．debfgcaB．cdbfgeaC．dcbgfeaD．cdbgfea
（19）具有127个结点的满二叉树，叶子节点的数量是（A）。
A．64B．32C．16D．8
（20）设有关键字序列（16,9,4,25,15,2,11,18,14,5,8,20），按关键码值递增的次序排序，采用二路归并排序法，下面（B）
A（9,16,4,25,2,15,11,18,5,14,8,20）B．（4,9,16,25,2,11,15,18,5,8,14,20）C（2,4,5,8,9,11,14,15,16,18,20,25）D（2,4,9,15,16,25,5,8,11,14,18,20）
（21）数据库管理系统DBMS是（B）。
A．一组硬件B．一组系统软件
C．一个完整的数据库应用系统D．既包含软件，又包含硬件
（22）在数据库技术发展过程中，文件系统和数据库系统的本质区别是数据库系统具有（A）。
A．数据结构化B．数据无冗余C．数据共享D数据独立性
（23）数据库系统中，用户使用的数据视图用（A）描述，该视图是用户与数据库系统之间的接口。
A．外模式B．内模式C．存储模式D．概念模式
（24）E－R方法的三要素是（A）。
A．实体、属性和联系B．实体、属性和实体集
C．实体、属性和码D．实体、码和联系
（25）（B）不属于关系完整性约束。
A．学生的学号必须唯一B．关系中的每一列都是不可再分的
C．性别只能是男或女D．学生所选课程必须是已开设课程
（26）已知关系R和S如表6.1和6.2所示，R的属性A是主码，属性B是外码，S的属性B是主码。
如果要在R中插入一个元组，则（A）不能插入。
A．（a5,b5,7）B．（a6,b4,1）C．（a7,b3,3）D．（a8,b2,1）
（27）设关系R和S有相同的目，且它们对应的属性的值取自同一个域，则R-（R-S）等于（B）。
A．R∪SB．R∩SC．R×SD．R÷S
（28）有两个关系R（A,B,C）和S（B,C,D），经过自然连接运算后得到的关系的属性个数是（B）。
A．3B．4C．5D．6
（29）关系数据库规范化是为了解决关系数据库中的（B）问题而引入的。
A．提高查询速度B．插入异常、删除异常和数据冗余
C．减少数据操作的复杂性D．保证数据的完整性和安全性
（30）在关系数据库中，任何二元关系模式的最高范式必定是（D）。
A．1NFB．2NFC．3NFD．BCNF
（31）～（40）选择题基于以下关系：
某关系数据库已建立学生表S、课程表C和选课表SC，它们的结构如下：
S（SNO，SNAME，AGE，SEX，DEPT）：
主码为SNO；属性含义为学号、姓名、年龄、性别、系别。
C（CNO，CNAME）：
主码为CNO；属性含义为课程号、课程名。
SC（SNO，CNO，GRADE）；主码为（SNO，CNO）；属性含义为学号、课程号、成绩。
（31）检索所有姓王的学生信息。
正确的SQL语句是（C）。
A．SELECT*FROMSWHERESNAME='王%';
B．SELECT*FROMSWHERESNAME='王_';
C．SELECT*FROMSWHERESNAMELIKE'王%';
D．SELECT*FROMSWHERESNAMELIKE'王_';
（32）检索“信息系”年龄在20岁以下的男生的姓名和年龄。
正确的SQL语句是（D）。
A．SELECT*FROMSWHEREAGE<20ANDSEXIN（'男'）ANDDEPTIN（'信息系'）;
B．SELECTSNAME,AGEFROMSWHEREAGE<20ORSEX='男'ORDEPT='信息系';
C．SELECTSNAME,AGEFROMSWHEREAGE<20ANDSEX=男ANDDEPT=信息系;
D．SELECTSNAME,AGEFROMSWHEREAGE<20ANDSEX='男'ANDDEPT='信息系';
（33）检索张华同学选修的所有课程名和成绩，应使用关系（D）。
A．S和SCB．C和SCC．S和CD．S、C和SC
（34）统计“数据结构”这门课程的补考人数。
正确的SQL语句是（A）。
A．SELECTCOUNT（*）FROMC,SCWHERECNAME='数据结构'ANDC.CNO=SC.CNOANDGRADE<60;
B．SELECTCOUNT（*）FROMC,SCWHERECNAME='数据结构'ANDGRADE<60;
C．SELECTCNAME,GRADEFROMC,SCWHERECNAME='数据结构'ANDGRADE<60;
D．SELECTSUM（*）FROMC,SCWHERECNAME='数据结构'ANDC.CNO=SC.CNOANDGRADE<60;
（35）检索选课人数少于4人的课程号。
正确的SQL语句是（B）。
A．SELECTCNOFROMSCWHERECOUNT（*）<4;
B．SELECTCNOFROMSCGROUPBYCNOHAVINGCOUNT（*）<4;
C．SELECTDISTINCTCNOFROMSCORDERBYCNO;
D．SELECTCNOFROMSCWHERECOUNT（CNO）<4;
（36）将学生的学号及其所选课程的平均成绩定义一个视图。
正确的SQL语句是（D）。
A．CREATEVIEWSSASSELECTSNO,AVG（GRADE）FROMSC;
B．CREATEVIEWSSASSELECTSNO,AVG（GRADE）FROMSCGROUPBYSNO;
C．CREATEVIEWSS（SNO,AVERAGE）ASSELECTSNO,AVG（GRADE）FROMSC;
D．CREATEVIEWSS（SNO,AVERAGE）ASSELECTSNO,AVG（GRADE）FROMSCGROUPBYSNO;
（37）修改课程表C，增加授课教师姓名TA，数据类型为字符型。
正确的SQL语句是（A）。
A．ALTERTABLECADDTACHAR（8）;B．UPDATECADDTACHAR（8）;
C．ALTERTABLECNEWTACHAR（8）;D．UPDATECSETTA=CHAR（8）;
（38）如果采用嵌套查询方式查询选修李修平老师授课的学生名单。
正确的SQL语句是（B）
A．SELECTSNAMEFROMSWHERESNOIN（SELECTSNO,CNOFROMSC,CWHERETA='李修平'ANDSC.CNO=C.CNO）;
B．SELECTSNAMEFROMSWHERESNOIN（SELECTSNOFROMSCWHERECNOIN
（SELECTCNOFROMCWHERETA='李修平'））;
C．SELECTSNAMEFROMSWHERECNOIN（SELECTCNOFROMCWHERETA='李修平'）;
D．SELECTSNAMEFROMSWHERESNOIN（SELECTSNOFROMSC,CWHERETA='李修平'ANDSC.SNO=S.SNO）;
（39）在学生表S中增加一条记录。
不正确的SQL语句是（C）。
A．INSERTINTOSVALUES（'1007','刘沙沙',21,'男','生物系'）;
B．INSERTINTOS（SNO,SNAME,DEPT）VALUES（'1007','刘沙沙','生物系'）;
C．INSERTINTOSVALUES（'1007','刘沙沙','生物系'）;
D．INSERTINTOSVALUES（'1007','刘沙沙',NULL,NULL,'生物系'）;
（40）将学号为1005号学生的年龄改为19岁。
正确的SQL语句是（A）。
A．UPDATESSETAGE=19WHERESNO='1005';
B．UPDATEAGE=19FROMSWHERESNO='1005';
C．ALTERTABLESSETAGE=19WHERESNO='1005';
D．UPDATETABLESSETAGE=19WHERESNO='1005';
2．综合应用（共30分）
（1）算法填空（每空3分，共12分）
L是一个带头结点的单链表，编写一个算法Delete_Repeat，实现将L中值重复的结点删除。
请将该算法补充完整。
提示：
本算法的思路是先取单链表中第1个结点的值，将它与其后所有结点的值一一比较，发现相同的就删除；然后再取第2个结点的值，重复上述过程直到最后一个结点。
voidDelete_Repeat（LinkList&L）
{LNode*p,*q;q=L;
while（q->next!
=NULL）
{q=q->next!
;p=q;
while（p->next!
=NULL）
{if（p->next->data==q->data）{p->next=p->next->next;}
if（p->next!
=NULL&&p->next->data!
=q->data）p=p->next;}}}
（2）数据库设计（共18分）
设某商业集团数据库中有3个实体集，一是“商店”实体集，属性有商店号、商店名、地址等；二是“商品”实体集，属性有商品号、商品名、规格、单价等；三是“员工”实体集，属性有工号、姓名、性别、生日、业绩等。
商店和员工之间存在聘用联系：
每个商店聘用多名员工、每个员工只能在一个商店工作；商店聘用员工有聘期和工资。
商店和商品之间存在销售联系：
每个商店销售多种商品、每种商品可以在多个商店销售；每个商店销售的每种商品有月销售额。
请完成以下任务：
（1）设计满足上述要求的E－R图。
（6分）
（2）将该E－R图转换成关系模式，并指出每一个关系的主码和外码。
（8分）
（3）写出创建“员工”关系模式对应的基本表的T-SQL语句。
（4分）
解答：
（1）E-R图如图6.2所示。
（2）关系模式如下（下划线部分为主码）：
商店（商店号，商店名，地址）。
商品（商品号，商品名，规格，单价）。
销售（商店号，商品号，月销售额）；外码：
商店号、商品号。
员工（工号，姓名，性别，出生年月，业绩，商店号，聘期，工资）；外码：
商店号。
（3）CREATETABLE员工（工号CHAR（6）PRIMARYKEY,姓名CHAR（8）,性别CHAR
（2）,
生日DATE,业绩INT,商店号CHAR（6）,工资INT,聘期INT,
FOREIGNKEY（商店号）REFERENCES商店（商店号））;。
2009年春浙江省高等学校
计算机等级考试试卷（三级数据库技术及应用）
试题1判断题用√和×表示对和错（每小题1分，共10分）
1．数据结构主要研究数据元素及其关系和施加在数据上的运算实现。
√
2．从逻辑上可以把数据结构分为线性结构和非线性结构。
√
3．算法分析的目的是找出高效的算法，为此，算法时间效率分析是算法分析中最重要而且是唯一要考虑的因素。
x
4．在决定选取何种存储结构时，一般要考虑结点的取值和结点之间的关系。
x
5．顺序表可随机访问任一结点，链表可顺序存储，所以也可随机访问。
x
6．同一个关系模型的任意两个元组值不能全同。
√
7．在关系代数运算中，从关系中取出满足条件的元组的运算称为选择运算。
√
8．对关系模式来说，范式级别越高，实际应用效果越好。
x
9．SQL中LIKE子句可以使用三个字符串匹配的通配符（“*”、“%”、“_”）x
10．模式/内模式为数据库提供了逻辑数据独立性。
x
试题2选择题（每小题2分，共40分）
1．数据结构是相互之间存在的一种或多种特定关系的
（1）的集合。
A．数据元素√B．数据项C．数据对象D．数据映像
2．对给出的一组关键字{14,5,17,20,11,19}.若按关键字非递减排序，第1趟排序结果为{14,5,17,20,11,19},问采用的排序算法是
（2）。
A．简单选择排序B．快速排序C．希尔排序√D．二路归并排序
3．带头结点的单链表head为空的判定条件是（3）。
（不带--A）
A．head==NullB．head->next==Null√
C．head->next==headD．head!
=Null
4．某实际应用中最常用的操作是取第i个结点及其前驱，则采用（4）存储方式最节省时间。
A．单链表B．双链表C．单循环链表D．顺序表√
5．在一个循环双向链表的p所指结点之前插入s所指结点的操作是（5）。
A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior
B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior
C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;
D．s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;√
6．在一个包含n个结点的有序单链表中插入一个新结点并仍保持有序的时间复杂度是（6）。
A．O（n）√B．O
（1）C．O（nlog2n）D．O（n2）
7．已知某二叉树先序序列为：
ABDEGHCF，中序序列为DBGEHAFC,则该二叉树的子树B有（7）个右子女。
A．5B．4C．3√D．2
8．用一个大小为6的一维数组实现的环形队列，若当前rear和front的值分别为0和3.当从该队列中删除一个元素，再插入两个元素后，rear和front的值分别是（8）。
A.1和5B√.2和4C.4和2D.5和1
9．一组记录的排序码为（46,79,56,38,40,84），则利用快速排序方法，以第一个记录为基准得到的一次划分结果为（9）。
A.38,40,46,56,79,84B.40,38,46,79,56,84
C.40,38,46,56,79,84√D.40,38,46,84,56,79
10．已知某栈中进栈序列为a,b,c,d,e,则出栈不可能的序列是（10）。
A.edcbaB.decbaC.dceab√D.abcde
11．随着数据库技术的发展，各种新的数据库应用模型不断推出。
目前数据库系统中最常用的一种主流数据模型是（A）。
A.关系模型B.层次模型C.网状模型D.面向对象模型
12．利用ER模型进行数据库的概念设计，可以分成三步：
首先设计局部ER模型，然后把各个局部ER模型综合成一个全局的模型，最后对全局ER模型进（D）得到最终的ER模型。
A.简化B.结构化C.最小化D.优化
13．关系代数运算是以（D）为基础的运算。
A.代数运算B.关系运算C.谓词运算D.集合运算
14．数据库是存储在一起的相关数据的集合，能为各种用户所共享，且（B）。
A.消除了数据冗余B.降低了数据冗余度
C.具有不相容性D.由用户控制物理数据的存储方式
15．在关系数据库中，若数据库的存储结构改变了，而用户的应用程序可以不变,这体现的是数据库系统中（A）。
A．数据的物理独立性B．数据的逻辑独立性
C．数据的位置独立性D．数据的语义独立性
16．需要安装一个新的SQLServer2005服务器，该服务器有四个CPU，应该选择（D）版本的SQLServer2005才能最大限度地发挥该服务器的作用。
A.SQLServerExpressEditionB.SQLServerWorkgroupEdition
C.SQLServerDeveloperEditionD.SQLServerStandardEdition
17．关系数据模型的三个要素是（D）。
A.关系数据结构、关系操作集合和关系规范化理论
B.关系数据结构、关系规范化理论和关系完整性约束
C.关系规范化理论、关系操作集合和关系完整性约束
D.关系数据结构、关系操作集合和关系完整性约束
18．在关系代数中有八种关系代数运算，其中五种基本运算是（D）。
A.并、差、选择、投影、除B.并、差、交、选择、投影
C.并、差、交、除、笛卡儿积D.并、
升级会员 