________。（2008年9月）
A)O(log2n) B)O(nlog2n) C)O(n) D)O(n)2
解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2 n次，而顺序查找需比较n次。
答案：A疑难解答→http://www.51pass.org/xuwzwx
-23-【真题7】在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为________。（2006年9月） A)6 B)7
C)63 D)64
解析：在长度为64的有序线性表中，其中的64个数据元素是按照从大到小或 从小到大的顺序排列有序的。在这样的线性表中进行顺序查找，最坏的情况就 是查找的数据元素不在线性表中或位于线性表的最后按照线性表的顺序查找算 法。
首先用被查找的数据和线性表的第一个数据元素进行比较，若相等，则查找成 功，否则，继续进行比较，即和线性表的第二个数据元素进行比较。
同样，若相等，则查找成功，否则，继续进行比较。依次类推，直到在线性表 中查找到该数据或查找到线性表的最后一个元素，算法才结束。
因此，在长度为64的有序线性表中进行顺序查找，最坏的情况下需要比较64 次。
答案：D疑难解答→http://www.51pass.org/qdzzmc
【真题8】下列数据结构中，能用二分法进行查找的是________。（2005年9月） A)二叉链表
B)有序线性链表
C)顺序存储的有序线性表 D)线性链表
解析：二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中 的元素按值非递减排列(即从小到大，但允许相邻元素值相等)的。
答案：C疑难解答→http://www.51pass.org/mftzxg 【真题9】对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为________。（2005年4月） A)n B)n+1
C)log2n D)n/2
解析：在长度为n的线性表中进行顺序查找，最坏情况下需要比较n次。 答案：A疑难解答→http://www.51pass.org/cudzwr
【真题10】下列叙述中正确的是________。（2010年3月）
A)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为 (log2n)
16
-24-B)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为 (nlog2n)
C)对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
D)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2) 解析：二分查找要求线性表中的结点必须按关键字值的递增或递减的顺序排 序。它首先把要查找的关键字K与中间位置的结点关键字相比较，若相等，则 查找成功；若不相等，则缩小范围。根据关键字与中间结点关键字的比较大小 确定下一步查找哪个子表，这样一直递归下去，直到找到满足条件的结点或者 确认表中没有这样的结点为止。对分查找即二分法查找，二分法查找只能适用 于顺序存储的有序表。
答案：C疑难解答→http://www.51pass.org/mrazwv
【真题11】在长度为n的线性表中，寻找最大项至少需要比较__【2】__次。（2010年9月） 解析：本题我们分两种情况说明：一种是无序的线性表。在这种情况下，要找 n个数据中值最大的数据，应该要和其他所有元素进行一次比较才能确定其值是 最大的。如果有一个元素没比较，那么也不能确定当前元素是值最大的元素， 因此至少需要比较的次数是n-1次。另一种是有序的线性表，在这种情况下， 不管是升序还是降序线性表，其最大值的位置都是确定的，无须比较。当然本 题考查的应该是第一种情况，因此答案为n-1。 答案：n-1疑难解答→http://www.51pass.org/wcezls
第2天：软件工程与数据库设计
Point1：数据模型 出题趋势
考试日期05-406-406-907-307-908-408-909-309-910-9出题次数2411212222 考点精讲
1、数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。
2、数据模型分为三种：
(1)概念数据模型：简称概念模型，是对客观世界复杂事物的结构描述及它们之间的内在联系的刻画。主要有：E-R模型、扩充的E-R模型、面向对象模型及谓词模型等。(2)逻辑数据模型：又称物理模型，是一种面向数据库系统的模型，该模型着重于在数据库系统一级的实现。主要有：层次模型、网状模型、关系模型、面向对象模型等。(3)物理数据模型：又称物理模型，它是一种面向计算机物理表示的模型，此模型给出 -25-了数据模型在计算机上物理结构的表示。 3、E-R模型
(1)E-R模型的基本概念 ①实体：现实世界中的事物； ②属性：事物的特性；
③联系：现实世界中事物间的关系。
(2)实体集的关系有一对一（一个学校和一个校长）、一对多（学生和宿舍）、多对多（老师与学生）的联系。两个实体集间联系可分为： ①一对一联系(onetoonerelationship)简记为1:1。
②一对多联系(onetomanyrelationship)简记为1:m或m:1。
17
③多对多联系(monytomanyrelationship)简记为m:n。
(3)E-R模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。 (4)E-R模型的图示法：
①实体集表示法：在矩形内写上实体集的名字； ②属性表示法：在椭圆形内写上属性的名称； ③联系表示法：用菱形内写上联系的名称；
④实体集与属性的联接关系：用无向线段来表示；
⑤实体集与联系间的联接关系；E-R模型由实体、属性、联系这三个基本概念细成。只有实体、联系、属性三者结合起来才能表示一个现实世界。 4、关系模型
(1)在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。表中的每一列称为一个属性，相当于记录中的一个数据项，对属性的命名称为属性名，表中的一行称为一个元组，相当于记录值。
(2)在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。 (3)关系中的数据约束：
①实体完整性约束：约束关系的主键中属性值不能为空值； ②参照完全性约束：是关系之间的基本约束；
③用户定义的完整性约束：它反映了具体应用中数据的语义要求。
(4)关系模型的数据操作即是建立在关系上的数据操作，一般有查询、增加、删除和修改四种操作。 真题分析
【真题1】在E-R图中，用来表示实体联系的图形是________。（2009年9月） A)菱形 B)三角形 C)椭圆形 D)矩形
-26-解析：在E-R图中，用矩形表示实体集，用椭圆形表示属性，用菱形(内部写 上联系名)表示联系。
答案：A疑难解答→http://www.51pass.org/hbfzpz
【真题2】在E-R图中，图形包括矩形框、菱形框、椭圆框、其中表示实体联系的是__【5】__框。（2009年3月） 解析：在E-R图中，用菱形框来表示实体之间的联系。矩形框表示实体集，椭 圆形框表示属性
答案：菱形疑难解答→http://www.51pass.org/lzfzve
【真题3】将E—R图转换为关系模式时，实体和联系都可以表示为________。（2009年3月） A)关系 B)域
C)属性 D)键
解析：将E—R图转换为关系模式时，实体和联系都可以表示为关系。
18
答案：A疑难解答→http://www.51pass.org/vwwzzm
【真题4】一间宿舍可住多个学生，则实体宿舍和学生之间的联系是________。（2008年9月）
A)多对一 B)多对多 C)一对一 D)一对多
解析：两个实体集间的联系可以有下面几种：一对一的联系、一对多或多对一 联系、多对多。由于一个宿舍可以住多个学生，但一个学生只能住在一个宿 舍，所以它们的联系是一对多联系。
答案：D疑难解答→http://www.51pass.org/rrozah
【真题5】在E-R图中，矩形表示__【5】__。（2007年9月） 解析：矩形表示实体，椭圆形表示属性，菱形表示联系。 答案：实体疑难解答→http://www.51pass.org/banzkx
【真题6】在E-R图中，用来表示实体之间联系的图形是________。（2007年3月） A)菱形 B)平行四边形 C)矩形 D)椭圆形
-27-解析：E—R图具有三个要素：①实体用矩形框表示，框内为实体名称。②属性 用椭圆形来表示，并用线与实体连接。属性较多时也可以将实体及其属性单独 列表。③实体间的联系用菱形框表示。用线将菱形框与实体相连，并在线上标 注联系的类型。
答案：A疑难解答→http://www.51pass.org/jitzxf
【真题7】在E-R图中，用来表示实体的图形是________。（2006年4月） A)菱形 B)三角
C)矩形 D)椭圆形
解析：在E-R图中，用三种图框分别表示实体、属性和实体之间的联系，其规 定如下：用矩形框表示实体，框内标明实体名；用椭圆状框表示实体的属性， 框内标明属性名；用菱形框表示实体问的联系，框内标明联系名。
答案：C疑难解答→http://www.51pass.org/hjpzio
【真题8】在二维表中，元组的__【5】__是不能再分成更小的数据项的。（2008年9月） 解析：元组分量的原子性是指二维表中元组的分量是不可分割的基本数据项。 答案：分量疑难解答→http://www.51pass.org/carzkw
【真题9】在关系数据库中，用来表示实体之间联系的是__【4】__。（2008年4月） 解析：在关系数据库中，用关系来表示实体之间的联系。 答案：关系疑难解答→http://www.51pass.org/ncizqs
【真题10】下列叙述中正确的是________。（2007年9月） A)一个关系的属性名表称为关系模式
B)一个关系可以包括多个二维表
C)为了建立一个关系，首先要构造数据的逻辑结构
D)表示关系的二维表中各元组的每一个分量还可以分成若干个数据项
19
解析：二维表中元组的分量是不可分割的基本数据项，这就是元组分量的原 子性；二维表中元组的分量是不可分割的基本数据项，这就是元组分量的原 子性；
关系的框架称为关系模式；二维表中元组的分量是不可分割的基本数据 项，这就是元组分量的原子性；
关系的框架称为关系模式；
一个满足“元组个数有限性、元组的唯一性、元组的次序无关性、元组分量的 原子性、属性名唯一性、属性的次序无关性、分量值域的同一性”7个性质的二 维表称为关系。
-28-答案：C疑难解答→http://www.51pass.org/rjfzhy
【真题11】一个关系表的行称为__【3】__。（2006年9月）
解析：关系是关系数据模型的核心。关系可以用一个表来直观地表示，表的每 一列表示关系的一个属性，每一行表示一个记录。 答案：记录疑难解答→http://www.51pass.org/mfxzkd
【真题12】在关系模型中，把数据看成是二维表，每一个二维表称为一个__【3】__。（2006年4月）
解析：在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。 因此，本题的正确答案是关系。
答案：关系疑难解答→http://www.51pass.org/xfizzk
【真题13】用树形结构表示实体之间联系的模型是________。（2005年4月） A)层次模型
B)三个都是 C)关系模型 D)网状模型
解析：在数据库系统中，由于采用的数据模型不同，相应的数据库管理系统 (DBMS)也不同。目前常用的数据模型有三种：层次模型、网状模型和关系模 型。在层次模型中，实体之间的联系是用树结构来表示的，其中实体集(记录型)
是树中的结点，而树中各结点之间的连线表示它们之间的关系。 答案：A疑难解答→http://www.51pass.org/jtuzfb
【真题14】在关系数据库中，把数据表示成二维表，每一个二维表称为__【4】__。（2005年4月）
解析：在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。 表中的每一列称为一个属性，相当于记录中的一个数据项，对属性的命名称为 属性名表中的一行称为一个元组，相当于记录值。
答案：关系疑难解答→http://www.51pass.org/dfzzfb
【真题15】在数据库技术中，实体集之间的联系可以是一对一、一对多或多对多的，那么“学生”和“可选课程”的联系为__【4】__。（2009年9月）
解析：学生与可选课程之间是多对多的关系。学生与可选课程之间是多对 多的关系。
一个学生可以选择多个“可选课程”，一个“可选课程”又可以有多个学生。所以 为多对多的关系。
答案：多对多疑难解答→http://www.51pass.org/qoyzyo
-29-【真题16】“商品”与“顾客”两个实体集之间的联系一般是________。（2006年4月）
20