scanf（“％d”，&a[i][j]）；
max=findmax（a）；
printf（“％d”．max）；}
36．下面程序找出100～200之间的全部素数。
#include
#include
voidmain（）
{intnq，k，i；
for（m=101；m<=200；m=m+2）
{k=sqrt（m）；
for（i=2；i<=k；④）
if（m％i==0）⑤;
if（i>k）printf（“％d”，m）；}}
第二部分数据结构（共100分）
一、单项选择题（本大题共12,qJ、题，每小题2分：
．共24分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将正确答案代码填写在答题纸相应位置上。
1．要表示高校的校、系、班级的有关数据及其关系，选择比较合适。
A．线性结构B．树结构C．图结构D．集合结构
2．下列函数中渐近时间复杂度最小的是。
3．已知一个栈s以及一个输入序列（A，B，C，D，E），每个元素按照A，B，C，D，E顺序进栈一次，进栈后可立即出栈，也可在栈中停留一段时间后再出栈，则不能得到序列。
A．A,B,C,D,EB．B．A,E,D,CC．C,B,A,D,ED．D,C,A,B,E
4．平均排序效率最好的排序方法是。
A．直接插入排序B．快速排序C．简单选择排序D．冒泡排序
5．某链表中最常用的操作是在已知的一个结点之前插入一个新结点和删除其之前一个结点，则采用存储方式最节省运算时间。
A．双向链表B．带头指针的单向链表C．带尾指针的单向链表D．单向循环链表
6．在逻辑结构不变的情况下，不是导致一个图的遍历序列不唯一的因素是
A．出发点不同B．存储（物理）结构不同C．遍历方法不同D．画法不同
7．散列函数有一个共同的要求，即函数值应当尽量以取其值域的每个值。
A．最大概率B．最小概率C．正态分布概率D．均等概率
8．下面方法可以判断出一个图中是否存在环（回路）。
A排序B．深度和广度遍历C．求最短路径D．求关键路径
9．最佳二叉搜索（排序）树是。
A．关键码个数最小的二叉搜索树B．退化为线性的二叉搜索树
C．搜索中平均比较次数最小的二叉搜索树D．任何结点的度数为0或2的二叉搜索树
10.是数据的基本单位，即数据集合（对象）中的个体。
A数据结构B．数据项C．数据元素D．数据对象
11．（线性）表是一个。
A有限序列，可以为空B有限序列，不能为空C无限序列，可以为空D．无限序列，不能为空
12．树是结点的集合，它根结点。
A有0个或1个B有0个或多个C有且只有1个D有1个或1个以上
二、填空题（本大题共7小题，每空2分，共16分）请将答案写在答题纸相应的位置上。
13．在有n个顶点的有向图中，每个顶点的度最大可达。
14．以下程序段的时间复杂度是。
i=0；j=o；
while（i+j<=n）
{if（i>j）j++；
elsei++；}
15．右图所示的二叉树后序遍历的结果是
16．在一个双向链表中P所指结点之前插入一个由指针s所指的新结点，写出可执行的操作序列：
。
（前指和后指的指针域分别为prior和next）
17．（线性）表有两种存储结构：
顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：
存储密度较大，可以随机存取；不可以随机存取，插入和删除操作比较方便。
18．递归的程序执行时使用来保存各层递归调用时的现场信息，以保证可以正确返回。
19．设数组a[M]（M为最大空间个数）作为循环队列Q的存储空间，front为队头指针（指向第一个存放数据的位置），rear为队尾指针（指向最后一个存放数据位置的下一个），则判定Q队列的队满条件是
三、应用题（本大题共4小题，每小题10分，共40分）请将答案写在答题纸相应的位置上。
20．设字符集D={A，B，C，D，E），各字符使用频率W={10，2，5，6，4）。
画出对字符进行哈夫曼编码时所对应的哈夫曼树，并给出各字符的编码。
21．用普里姆（Prim）算法从右图中的顶点1开
始逐步构造最小支撑（代价生成）树，要求
画出构造的每一步。
22．给定待排关键字集合为{23，14，48，25，5，19}，按关键字非递减（从小到大）排序，写出采用冒泡排序的每一趟（最外层循环的每一次）排序结果。
23．
（1）图示表示右边有向图的邻接表。
（4分）
（2）写出从顶点1开始分别进行深度
优先和广度优先遍历的顶点序列各一种。
（6分）
四、算法设计题（本大题共2小题，每小题10分，共20分）
请将答案写在答题纸相应的位置上c
24．假定用一个有头结点循环链表来存储一个有序的线性表，线性表从头到尾为非递减（从小到大）有序（如下图）。
用指针（如下图）。
用指针current从head开始搜索数据域等于key的元素在线性表中位置，如果搜索成功则current指向搜索到的结点，函数返回该指针；如果搜索不成功，函数返回空指针NULL。
请在函数SortedlistLocate（head，key）内填空，完成下列算法以实现这种搜索，并使得搜索不成功的平均比较次数小于链表长度。
typedefstructnode{elemtypedata；／／数据域
structnode*next；／／指针域
}1node，术linklist；
linklistSortedlistLocate（1inklisthead，elerntypekey）
{linklistcurrent；
if（
（1））returnERROR；／／错误提示
current=
（2）；
while（（3）&&（4））
current=current-->next；／／循链搜索其值等于key的结点
if（（5））
returncurrent；／／找到，返回结点地址
elsereturnNULL；／／未找到，返回空指针}
25．r[]为一维数组，其中r[0]到r[n-]为待排序的n个元素，排序好的元素仍在r[0]到r[n-1]中。
请写出对该数组进行非递减排序的直接插入排序算法取名为InsertSort（etemtyper[]，intn）。
第三部分关系数据库与SQL语言（共100分）
一、单项选择题（本大题共20小题，每小题2分，共40分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将正确答案代码写在答题纸相应位置上。
1.数据库（DB），数据库系统（DBS）和数据库管理系统（DBMS）之间的关系是。
A．DBS包括DB乖DBMSB．DBMS包括DB和DBS
C．DB包括DBS和DBMSD．DBS就是DB，也就是DBMS
2.下面列出的数据库管理技术发展的三个阶段中，没有专门的软件对数据进行管理的是I．人工管理阶段II．文件系统阶段III．数据库阶段。
A．I帮IIB．只有IC．II帮IIID．只有II
3.下面的选项不是关系数据库基本特征的是。
A．不同的列应有不同的数据类型B．不同的列应有不同的列名
C．与行的次序无关D．与列的次序无关
4.从一个数据库文件中取出满足某个条件的所有记录形成一个新的数据库文件的操作是操作。
A．投影B．连接C．选择D．复制
5.现有如下关系：
患者（患者编号，患者姓名，性别，出生日期，所在单位），医疗（患者编号，医生编号，医生姓名，诊断日期，诊断结果），在此两个表的逻辑关系中，医疗关系中的外码是。
A．医生编号和患者编号B．患者姓名C．患者编号和患者姓名D．患者编号
6.SOL语言中，删除一个视图的命令是。
A．DELETEB．DROPC．CLEARD．REMOVE
7.在SQI二语言中，修改数据结构应使用的命令是。
A．CHANGEB．CREATEC．ALTERD.DEI,EFE
8．下述SQL命令中，允许用户定义新关系时，引用其他关系的主码作为外码的是。
A．INSERTB．REFERENCESC．DELETED．SELECT
9．规范化理论是关系数据库进行逻辑设计的理论依据，第一范式是指关系中的每一个属性都是。
A．长度不变的B．互不相关的C．互相独立的D．不可分解的
10．若用如下的SQL语句创建了一个表SC：
CREATETABLESC（SCHAR（6）NOTNULL，CCHAR（3）NOTNULL，SCOREINTEGER，NOTECHAR（20））；向SC表插入如下行时，行可以被插入。
A．（‘200823’，’101’，NULL，NULL）B．（’201009’，’111’，60，必修）
C．（NULL，’103’，80，’选修’）D．（’201132’，NULL，86，’’）
11．规范化理论是数据库阶段的指南和工具。
A．需求分析B．概念设计C．逻辑设计D．物理设计
12．候选码的属性有。
A．多个B．0个C．1个D．1个或多个
13．关系模式中，满足3NF的模式。
A．可能是2NFB．必定是4
升级会员 