华中师范大学870计算机基础考研真题——09年

华中师范大学

二00九年研究生入学考试试题

院系、招生专业:教育技术学       考试时间: 元月11日下午

考试科目代码及名称: 853    计算机应用基础

一、填空题(每空2分，共20分)

1.在计算机系统中，输入输出缓冲区常常会用到                         数据结构。

2.一个有n个顶点的有向图最多有                         条弧。

3.有一个n阶三对角矩阵，若用一个一维数组压缩存放该三对角矩阵，则这个一维数组的容量应该是                     。

4.用树结构表示实体及其实体之间联系的数据模型称为                         。

5.在数据库系统的三级模式体系结构中，模式有                    个。

6.给出一组关键字(25，24，21，47，15，27， 68,，35，20)，按照从小到大进行插入排序，则经过第一趟简单插入排序后的序列是                                       。

7.已知8个数据元素为(34，76，45，18，26，54，92， 65)，按照依次插入结点的方法生成一棵二叉排序树，则最后两层上的结点总数为                      。

8.若根据查找表(23，44，36，48，52，73，64，58) 建立线性哈希表，采用H(K)=K%13计算哈希地址，则元素64的哈希地址为                     。

9.在SQL中，实现数据更新功能的命令动词是                              。

10.在数据库设计过程中，________    是概念结构设计的有力工具。

二、简答题(每小题7分，共14分)

1.简述数据的逻辑结构与物理(存储)结构的区别，试举例说明。

2.关系模型数据库与格式化模型比较有哪些主要优点？

三、分析题(每小题8分，共16分)

1.有一个长度为n的顺序存储的有序线性表，要在此线性表中利用对分查找算法查找某元素x，试分析在等概率的情况下该算法的时间复杂度。(8分)

2.设某教学数据库中有三个基本表:学生表Student、课程表Course和选课表SC，其关系模式如下:

Student (Sno,Sname, Age, Sex)

Course (Cno, Cname, Teacher )

SC (Sno, Cno， Score )

分析下列查询要求，写出SQL语句。(8分)

(1)检索出年龄(Age)在18~20岁之间的学生的信息。

(2)检索出选修了课程名(Cname)为“math"的学生学号与姓名。

四、算法设计题(第1小题10分，第2小题20分，共30分)

1.有一个长度为n的以顺序结构存储的线性表，其结点值均为正整数，试编写一个算法，把该线性表分解为两个线性表，其中一个线性表的结点值均为奇数，另一个线性表的结点值均为偶数。(10分)

2.试编写在线性表的链式存储结构下将两个线性单链表首尾相接合并成一个单链表并按关键字由小到大进行排序的算法。(20分)

(要求给出结点结构的定义， 输入参数为待合并的两个线性单链表的头指针，返回值为合并后的线性单链表的头指针)