一、数据结构基础（30分）1. 树的固有特性是( )A、嵌套B、顺序C、递归D、选择2. 在一个单链表中，已知q结点是p结点的前驱结点，删除p结点的语句( )A p→next=p→next→next；B q→next= p→next；C q→next=nil；delete（p）D q = p→next；3. 一个初始为空的栈，S是入栈，P是出栈，操作序列合法的是( )A、PSSSPPB、SSPPPPC、SSPPSPD、PSPSPS4. 循环队列用数组A[m]存放元素，头尾指针为front和rear，则当前队列中有的元素个数为( )A．rear – front + 1 B．(rear – front + 1 + m ) mod mC．rear – front - 1 D．rear – front5. 算法的查找效率一般是一平均查找代价来衡量的，比如线性查找是O（N），二分查找是O（logN），那么Hash查找的期望代价是( )A O (㏒n)B O(n)C O (1)D (n㏒n)6. 树型结构中父子之间的联系是( )A 1：1B 1：NC M：ND N：17. 设a，b是一二叉树的两结点，在中序遍历时a在b前面的条件是( )A a在b右边B a在b左边C a是b的祖先D a是b的子孙8. 对线性表进行二分查找时，要求线性表必须是( )A顺序存储B链式存储C 顺序存储且元素有序D 链式存储且元素有序9. 下列数据哪一组符合最大值堆的定义( )A、（42，40，45，55，80，85）B、（85，55，80，45，40，42）C、（85，45，80，55，40，42）D、（42，55，45，40，80，85）10. 在内部排序中，排序时不稳定的是( )A 插入排序B 冒泡排序C 快速排序D 归并排序11. n个结点的树边数最多是( )A．n B．n*(n-1)C．n-1D．n*(n-1)/212. 对（541，132，984，，746，518，181，946，314，205，827）进行从大到小排序，用直接选择法，先选最大元素，第一趟的结果是( )A (181,132,314,205,541,518,946,827,746,984)B (541,132,827,746,518,181,946,314,205,984)C (205,132,314,181,518,746,946,984,541,827)D (541,132,984,746,827,181,946,314,205,518)13. 对（541，132，984，，746，518，181，946，314，205，827）进行从大到小排序，用快速排序法（以中间元素518为基准），第一趟的结果是( ) (选项同上题)14. 哈夫曼树中，外部结点的个数比内部结点的个数( )A．相等B．多1 C．少一D．无法确定15. 在查找数中插入一个新结点，总是插入到( )结点下面。
A、根B、左子树C、右子树D、叶16. n个结点的单链表中查找值为x的结点，在查找成功的情况下，需要平均比较()个结点。
A．n/2B．n C．（n+1）/2D．(n-1)/217. 一棵顺序存储的完全二叉树每个结点占用2个存储单元，已知第三个结点的地址为1000，若其左子女存在，其地址最可能是( )A．2000B．1006C．2004D．200818. 数据结构（D，R），D={di |1<=I<=7}，R={<d4,d2>,<d2,d1>,<d2,d3>,<d4,d6>,<d6,d5>,<d6,d7>}则此结构的图形是( )A．线性表B．图C．二叉树D．队列19. 对上题图形采用( )遍历方法，可得到序列（d1,d2,d3,d4,d5,d6,d7）？A．先序B．中序C．后序D．深度优先搜索20. 已知一棵数的2种遍历结果，哪个组合能唯一确定一棵二叉树( )？A．先序，中序B．先序，后序C．层次，后序D．层次，先序二、数据库基础（45分）1. 目前最常用的一种数据模型是( )A.关系模型B．层次模型C．网状模型D．面向对象模型2. ER模型中，联系可以同( )个实体有关。
A．0个B．1个或多个C．1个D．多个3. 实体与实体之间的联系可以有( )A．1：1和1：n B．1：1和n：n C．1：n和n：n D．1：1，1：n和n：n4. 利用ER模型进行数据库的概念设计，可以分为三步：首先设计局部ER模型，然后把各个局部ER模型综合成一个全局的模型，最后对全局ER模型进行( )得到最终的ER模型。
A．简化B．结构化C．最小化D．优化5. 传统的数据库基本上是有( )组成的。
A．对象B．文件C．元组D．过程6. ( )在技术和理论上已经成熟，成为当前商用数据库的主流。
A．关系数据库B．层次数据库C．网状数据库D．空间数据库7. ( )数据库技术是在80年代中期引入的。
A．关系数据库B．层次数据库C．网状数据库D．面向对象数据库8. 关系代数运算是以( )为基础的运算。
A．代数运算B．关系运算C．谓词运算D．集合运算9. 关系代数运算的五种基本运算是并、差、( )、投影和选择。
A．交B．连接C．笛卡尔积D．自然连接10. 规范化理论研究中分解( )主要是消除其中多余的相关性。
A．内模式B．视图C．外模式D．关系模式11. 数据库是存储在一起的相关数据的集合，能为各种用户所共享，且( )。
A.消除了数据冗余B．降低了数据度C．具有不相容性D．由用户控制物理数据的存储方式12. 每个关系属性值均是不可分解的关系模式属于( )NF。
A．1B．2C．3D．BC13. 基本SQL语句，不可实现的是( )A．定义视图B．定义基表C．查询视图和基表D．并发控制14. ( )是位于用户和操作系统之间的一层数据管理软件。
A．数据库管理系统B．数据库C．数据库系统D．数据库应用系统15. 在SQL中，与关系代数σ运算对应的是( )子句。
A．SELECT B．FROM C．GROUP BY D．WHERE16. 在数据库系统中，数据的安全性是指保护数据以防止( )的蓄意或者无意使用。
A．所有用户B．授权用户C．未被授权用户D．超级用户17. ER模型向关系模型转换，实体转换为关系模式，联系可以转换为( )。
A．联系模式B．数据模式C．关系模式D．逻辑模式18. 上题中，联系的各端实体的键与联系的属性转换为( )？A．联系模式B．关系的属性C．数据属性D．关系的候选键19. ( )完整性规则是主关键字值的任何组成部分都不可以取空值。
A．数据B．数据库C．引用D．实体20. ( )的完整性是指数据的正确性和有效性。
A．数据B．数据库C．引用D．实体21. 事务是数据库运行的基本单位，它保证了数据库的( )A．一致性B．完整性C．正确性D．可靠性22. 实体完整性和参照完整性是可应用于所有( )数据库的两条完整性约束？A．层次B．网状C．空间D．实体23. 设有一图书管理系统，其关系模式是R0（R#，B#，BNAME，BPRICE，BPUB），其属性分别表示个人借书证号、书号、书名、书价、图书出版社。
该关系属于( )NF。
A.属于1但不属于2 B．属于2但不属于3 C．属于3D．不是范式24. 上题中，对R0分解，为R1（R#，B#），R2（B#，BNAME），R3（B#，BNAME，BPRICE，BPUB），R4（BNAME，BPRICE，BPUB），试问下列组合中都符合3NF的是( )？A. R1，R2，R3，R4 B．R1，R2，R3 C．R1，R2，R4 D．R2，R3，R425. 连接运算是中的iθj中θ是( )运算符号？A．算术运算符，如+，—B．逻辑运算符，如∧，∨C．算术比较运算符，如=，＜D．集合运算符，如∩，∪26. 关系代数运算中，关系R和关系S的运算R×S，其中的―×‖表示是( )运算A．算术B．笛卡尔积C．矢量D．逻辑27. 多用户使用数据库系统要如单用户使用，DBMS必须进行( )A．同步控制B．并发控制C．异步控制D．安全性控制28. 嵌入式SQL中主语言与数据子语言之间的( )机制在两种语言中起桥梁作用。
A．控制B．安全C．游标D．嵌套29. 用户程序按所对应的( )使用数据库中的数据。
A．子模式B．概念模式C．存储模式D．模式30. 概念模式改变，( )不必变，因而用户程序不必改写。
A．内模式B．子模式C．存储模式D．模式三、数据库应用设计（25分）某高校要开运动会，请代为开发一个简单的高校运动会管理系统，已知实体有2类：运动员基本信息（简称运动员）、比赛项目基本信息（简称项目），主要属性分别为：运动员（运动员号，姓名，性别，队名）；其对应的英文名为ATHLEFE（ANO，ANAME，ASEX，ATEAM）项目（项目号，项目名，比赛时间，比赛场地）；其对应的英文名为ITEM（INO，INAME，ITIME，IPLACE）两个实体之间存在参赛关系：参赛（成绩）；其对应的英文名为GAMES（SCORE）其中：运动员号是运动员唯一标识号码，项目号是项目唯一标识运动员号是运动员唯一标识，为简单起见，约定在ER图中，矩形表示实体，圆形表示属性，双圆表示关键字属性，菱形表示联系。
要求完成如下设计工作：1、数据库设计（15分）（1）建立概念数据模型：画出系统的ER模型图，包括实体及实体间的联系；（2）建立关系模型：把ER模型转换为关系表（标明主关键字），并用SQL语言建立基本表。
2、用SQL语言实现如下功能（10）（1）统计参加比赛的男、女运动员人数（2）查某运动员参加的所有项目及其比赛时间场地（如100801运动员）（3）查参加某项目的所有运动员名单（如10005项目）（4）建立运动员成绩视图。