1、全国计算机等级考试三级数据库技术真题 2003 年 9 月及答案解析(总分：98.00，做题时间：90 分钟)一、B选择题/B(总题数：64，分数：58.00)1.在计算机硬件系统的基本组成中，完成解释指令、执行指令的功能部件是 A）运算器 B）控制器 C）存储器 D）输入输出设备（分数：1.00）A.B.C.D.2.利用计算机对指纹进行识别、对图像和声音进行处理属于下列哪一个应用领域？ A）科学计算 B）过程控制 C）辅助设计 D）信息处理（分数：1.00）A.B.C.D.3.多媒体网络应用及实时通信要求网络高速率传输，并且延迟低。下列哪一项技术满足这类应用的要求？ A）ATM B）FDDI
2、 C）FR D）X.25（分数：1.00）A.B.C.D.4.下列协议中，哪一个是在传输层定义的？ A）FTP B）RIP C）TCP D）IP（分数：1.00）A.B.C.D.5.下列哪一（些）项属于询问-应答式协议？ 私钥密码技术 公钥密码技术 A）只有 B）只有 C）和 D）都不是（分数：1.00）A.B.C.D.6.下列关于网络安全服务的叙述中，哪一个是错误的？ A）应提供访问控制服务以防止用户否认已接收的信息 B）应提供认证服务以保证用户身份的真实性 C）应提供数据完整性服务以防止信息在传输过程中被删除 D）应提供保密性服务以防止传输的数据被截获或篡改（分数：1.00）A.B.C.D
3、.7.以下关于数据结构的基本概念的叙述中哪一条是错误的？ A）数据元素是数据的基本单位 B）数据项是有独立含义的数据最小单位 C）数据结构概念包含的主要内容是数据的逻辑结构和数据的存储结构 D）数据的逻辑结构分为线性结构和非线性结构（分数：1.00）A.B.C.D.8.以下关于链式存储结构的叙述中哪一条是错误的？ A）结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B）逻辑上相邻的结点物理上不必邻接 C）可以通过计算直接确定第 i 个结点的存储地址 D）插入、删除运算操作方便，不必移动结点（分数：1.00）A.B.C.D.9.栈结构不适用于下列哪一种应用？ A）表达式求值 B）树的
4、层次次序周游算法的实现 C）二叉树对称序周游算法的实现 D）快速排序算法的实现（分数：1.00）A.B.C.D.10.如下是一个稀疏矩阵的三元组法存储表示和相关的叙述 （分数：1.00）A.B.C.D.11.设根结点的层次为 0，则高度为 k 的二叉树的最大结点数为A）2 k B）2 k-1C）2 k+1 D）2 k+1-1（分数：1.00）A.B.C.D.12.对线性表进行二分法查找，其前提条件是 A）线性表以顺序方式存储，并已按关键码值排好序 B）线性表以顺序方式存储，并已按关键码值的查找频率排好序 C）线性表以链接方式存储，并已按关键码值排好序 D）线性表以链接方式存储，并已按关键码值的
5、查找频率排好序（分数：1.00）A.B.C.D.13.在包含 1000 个元素的线性表中实现如下各运算，哪一个所需的执行时间最长？ A）线性表按顺序方式存储，在线性表的第 10 个结点后面插入一个新结点 B）线性表按链接方式存储，在线性表的第 10 个结点后面插入一个新结点 C）线性表按顺序方式存储，删除线性表的第 990 个结点 D）线性表按链接方式存储，删除指针 P 所指向的结点（分数：1.00）A.B.C.D.14.设有字符序列（Q，H，C，Y，P，A，M，S，R，D，F，X），问新序列（F，H，C，D，P，A，M，Q，R，S，Y，X）是下列哪一个排序算法一趟扫描的结果？ A）起泡排序
6、B）初始步长为 4 的希尔排序 C）二路归并排序 D）以第一元素为分界元素的快速排序（分数：1.00）A.B.C.D.15.下面关于 B 树运算的叙述中，正确的是 A）若插入过程中根结点发生分裂，则 B 树的高度加 1 B）每当进行插入运算，就往 B 树的最下面一层增加一个新结点 C）若要删除的关键码出现在根结点中，则不能真正删除，只能做标记 D）删除可能引起 B 树结点个数减少，但不会造成 B 树高度减小（分数：1.00）A.B.C.D.16.下列关于中断的叙述中，错误的是 A）时间片到时属于时钟中断 B）目态下执行特权指令将产生程序性中断 C）缺页中断属于自愿性中断 D）打印机完成打印将产
7、生输入输出中断（分数：1.00）A.B.C.D.17.采用“不可剥夺优先数“调度算法，进程执行的次序是 A）P2、P1、P5、P3、P4 B）P2、P3、P1、P5、P4 C）P4、P1、P3、P5、P2 D）P4、P3、P1、P5、P2（分数：1.00）A.B.C.D.18.采用“不可剥夺优先数“调度算法，进程在就绪队列中的平均等待时间为 A）6 B）7 C）8 D）9（分数：1.00）A.B.C.D.19.下列各项中哪一个不是虚拟页式存储管理中缺页中断处理所做的工作？ A）通过文件系统将所需页面从外存调入内存 B）调用内存分配程序 C）修改页表 D）调度被中断程序继续执行（分数：1.00）
8、A.B.C.D.20.下列哪一个是引入工作集模型的前提因素？ A）系统效率下降 B）页面淘汰算法选择不合理 C）程序的局部性原理 D）分配给进程的物理页面数太少（分数：1.00）A.B.C.D.21.下列哪一种文件存储设备不支持文件的随机存取？ A）磁盘 B）光盘 C）软盘 D）磁带（分数：1.00）A.B.C.D.22.下列哪一项不是打开文件时所做的工作？ A）填写文件控制块中的文件读写方式项 B）检查文件名所对应的文件控制块是否已调入内存 C）检查操作的合法性 D）返回给用户一个文件描述符（分数：1.00）A.B.C.D.23.下列磁盘调度算法中，哪一个体现了公平性？ A）先来先服务 B）
9、最短寻道时间优先 C）电梯算法 D）单向扫描（分数：1.00）A.B.C.D.24.假设系统处于安全状态，目前系统剩余资源数量为 2。下列哪一个进程序列不是安全序列？ （分数：1.00）A.B.C.D.25.在数据库中可以创建和删除表、视图、索引，可以修改表。这是因为数据库管理系统提供了 A）数据定义功能 B）数据操纵功能 C）数据维护功能 D）数据控制功能（分数：1.00）A.B.C.D.26.数据库系统一般由哪些成分构成？ 数据库 数据库管理员 数据库管理系统及其工具 用户 操作系统 应用系统 A）I、II 和 III B）I、II、III 和 IV C）I、II、III、IV 和 V D
10、）全部（分数：1.00）A.B.C.D.27.在关系数据库中，索引（index）是三级模式结构中的 A）概念模式 B）内模式 C）模式 D）外模式（分数：1.00）A.B.C.D.28.下面所列各项，哪些属于数据库技术的研究领域？ 数据库管理系统软件的研制 数据库设计 数据库理论 操作系统（分数：1.00）A.和B.和C.、 和D.全部29.在关系数据库系统中，当合并两个关系时，用户程序可以不变。这是 A）数据的物理独立性 B）数据的位置独立性 C）数据的逻辑独立性 D）数据的存储独立性（分数：1.00）A.B.C.D.30.在面向对象数据模型中，子类不但可以从其超类中继承所有的属性和方法，而
11、且还可以定义自己的属性和方法，这有利于实现 A）可移植性 B）可扩充性 C）安全性 D）可靠性（分数：1.00）A.B.C.D.31.关系模型有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。定义外键实现的是哪一（些）类完整性？ A）实体完整性 B）参照完整性 C）用户定义的完整性 D）实体完整性、参照完整性和用户定义的完整性（分数：1.00）A.B.C.D.32.设关系 R 与关系 S 具有相同的目，且相对应的属性的值取自同一个域，则 R S 可记作 A）t | t R t S B）t | t R t S C）t | t R t S D）t | t R t （分数：1.00）A.B
12、.C.D.33.在下列关系代数的操作中，哪一个不属于专门的关系运算？ A）自然连接 B）投影 C）广义笛卡尔积 D） 连接（分数：1.00）A.B.C.D.34.结构化查询语言 SQL 在哪年被国际标准化组织（ISO）采纳，成为关系数据库语言的国际标准？ A）1986 B）1987 C）1988 D）1989（分数：1.00）A.B.C.D.35.设有关系 R，S 和 T 如下。关系 T 是由关系 R 和 S 经过哪种操作得到的？ A）R S B）R - S D） （分数：1.00）A.B.C.D.36.下面关于 SQL 语言的说法中，哪一种说法是错误的？ A）一个 SQL 数据库就是一个基本
13、表 B）SQL 语言支持数据库的三级模式结构 C）一个基本表可以跨多个存储文件存放，一个存储文件可以存放一个或多个基本表 D）SQL 的一个表可以是一个基本表，也可以是一个视图（分数：1.00）A.B.C.D.37.下面所列条目中，哪一条不是标准的 SQL 语句？ A）ALTER TABLE B）ALTER VIEW C）CREATE TABLE D）CREATE VIEW（分数：1.00）A.B.C.D.38.把 SQL 语言嵌入主语言使用时必须解决的问题有 区分 SQL 语句与主语言语句 . 数据库工作单元和程序工作单元之间的通信 . 协调 SQL 语句与主语言语句处理记录的不同方式 A）
14、和 B）和 C）和 D）、和（分数：1.00）A.B.C.D.39.至（41）题，基于“学生-选课-课程“数据库中如下三个关系：S（S#，SNAME，SEX，AGE）SC（S#，C#，GRADE）C（C#，CNAME，TEACHER） 查找学生号为“200301188“的学生的“数据库“课程的成绩，至少将使用关系（分数：1.00）A.S 和 SCB.SC 和 CC.S 和 CD.S、SC 和 C_43.查询选修了课程号为C2的学生号和姓名，若用下列 SQL 的 SELECT 语句表达时，哪一个是错误的？（分数：1.00）A.SELECT S#，SNAME FROM S WHERE S# = (
15、SELECT SS# FROM SC WHERE C# = C2 )B.SELECT S#，SNAME FROM S，SCWHERE S# = SS# AND C# = C2C.SELECT S#，SNAME FROM S，SC WHERE S# = SS# AND C# = C2 ORDER BY S#D.SELECT S#，SNAME FROM S WHERE S# IN (SELECT SS# FROM SC WHERE C# =C2 )44.在数据库管理系统的层次结构中，数据存取层处理的对象是 A）字段 B）单个元组 C）数据页 D）系统缓冲区（分数：1.00）A.B.C.D.45.下
16、列哪种数据库系统更适合于在大、中型计算机系统上使用？ A）FoxPro B）Access C）Oracle D）Microsoft SQL Server（分数：1.00）A.B.C.D.46.对数据库数据的删除是由数据库管理系统的哪个功能模块实现的？ A）数据库存取功能模块 B）数据库存储管理功能模块 C）数据库运行处理功能模块 D）数据库维护功能模块（分数：1.00）A.B.C.D.47.Sybase 公司目前的企业级服务器 ASE 支持下述哪些功能？ JAVA 语言和 XML 语言 服务器之间的失败转移 保证分布式事务处理的完整性 A）I 和 II B）II 和 III C）I 和 III
17、 D）全部（分数：1.00）A.B.C.D.48.事务的持久性是由数据库管理系统中的哪个部件负责？ A）恢复管理 B）并发控制 C）完整性约束 D）存储管理（分数：1.00）A.B.C.D.49.数据库系统的日志文件用于记录下述哪类内容？ A）程序运行过程 B）数据查询操作 C）程序执行结果 D）数据更新操作（分数：1.00）A.B.C.D.50.实现数据库的哪个特性能够避免对未提交更新的依赖（“脏数据“的读出）？ A）完整性 B）并发性 C）安全性 D）可移植性（分数：1.00）A.B.C.D.51.下列说法错误的是 A）ROLLBACK 表示事务不成功结束 B）无级联调度是不可恢复的 C）
18、共享锁又称为S 锁或读锁 D）排它锁又称为 X 锁或写锁（分数：1.00）A.B.C.D.52.下述哪一条不属于数据库设计的内容？ A）设计数据库管理系统 B）设计数据库概念结构 C）设计数据库逻辑结构 D）设计数据库物理结构（分数：1.00）A.B.C.D.53.下述哪一条是由于关系模式设计不当所引起的问题？ A）丢失修改 B）更新异常 C）读脏数据 D）数据被非法读取（分数：1.00）A.B.C.D._57.设 U 是所有属性的集合，X、Y、Z 都是 U 的子集，且 Z=UXY。下面关于多值依赖的叙述中，哪个（些）是正确的？ 若 X Y，则 X Y 若 X Y，则 X Y 若 X Y，且
19、，则 X 若 X Y，则 X Z A）只有 B）只有 C）和 D）和（分数：1.00）A.B.C.D.58.设有关系模式 R（A，B，C），根据语义有如下函数依赖集：F=AB,（B,C）A 。关系模式 R 的规范化程度最高达到 A）1NF B）2NF C）3NF D）BCNF（分数：1.00）A.B.C.D.59.下面有关模式分解的叙述中，正确的是 A）若一个模式分解具有无损连接性，则该分解一定保持函数依赖 B）若一个模式分解保持函数依赖，则该分解一定具有无损连接性 C）若只要求分解保持函数依赖，那么模式分解一定可以达到 BCNF D）若只要求分解具有无损连接性，那么模式分解一定可以达到BCN
20、F（分数：1.00）A.B.C.D.60.下述哪一条不是局部 E-R 图集成为全局 E-R 图时可能存在的冲突？ A）模型冲突 B）结构冲突 C）属性冲突 D）命名冲突（分数：1.00）A.B.C.D.61.下列哪个工具是 Oracle 数据库管理系统提供的 CASE 工具？ A）Developer/2000 B）PowerBuilder/2000 C）Discoverer/2000 D）Designer/2000（分数：1.00）A.B.C.D.62.下面所列的条目中，哪些是新一代数据库开发工具应具有的特征？ 支持开发人员对各种数据对象（字符、数字、图形、声音等）的处理 支持基于 INTER
21、NET 应用的开发 支持面向对象的程序设计 A）I 和 II B）I 和 III C）II 和 III D）都是（分数：1.00）A.B.C.D.63.在对象-关系数据库系统中，创建新的基本数据类型需要说明的信息包括 类型名 类型的存储信息 类型的地址 类型与 ASCII 码之间的转换 A）I、II 和 III B）I、II和 IV C）II、III 和 IV D）全部（分数：1.00）A.B.C.D.64.OLAP 的基本概念不包括 A）度量属性 B）维 C）数据分析 D）事务处理（分数：1.00）A.B.C.D.二、B填空题/B(总题数：20，分数：40.00)65.网络中的计算机之间为了
22、能正确交换数据，必须遵守事先约定好的通信规则。这些规则明确规定了所交换数据的U 【1】 /U和时序。（分数：2.00）填空项 1:_66.网络攻击者设法涂改一个网站的主页，使得该网站的 WWW 服务不能正常工作，这种网络攻击称为U 【2】 /U。（分数：2.00）填空项 1:_67.在有 n 个结点的二叉树的 llink-rlink 法存储表示中，n 个结点所含有的 2n 个指针中，必有U 【3】 /U个为空指针。（分数：2.00）填空项 1:_68.对于给出的一组权 w = 5，6，8，12，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为U【4】 /U。（分数：2.00）填空项 1:_6
23、9.对 n 个记录的文件进行快速排序，最坏情况下的执行时间为 【5】 。（分数：2.00）填空项 1:_70.操作系统有两个重要的作用，一个是管理系统中的各种软硬件资源；另一个是向用户提供良好的 【6】 。（分数：2.00）填空项 1:_71.线程是进程中的一个执行实体，每个线程有惟一的标识符和一张U 【7】 /U。（分数：2.00）填空项 1:_72.系统中有 N 个进程，则某个进程等待队列中最多可有 【8】 个进程。（分数：2.00）填空项 1:_73.数据库管理系统是位于用户和U 【9】 /U系统之间的一个数据管理软件 。（分数：2.00）填空项 1:_74.数据模型用来描述数据的静态特
24、征、动态特征和数据的完整性约束。对数据结构和数据间联系的描述，这是描述数据的U 【10】 /U。（分数：2.00）填空项 1:_75.关系代数是一种关系操纵语言，它的操作对象和操作结果均为 【11】 。（分数：2.00）填空项 1:_76.SQL 语言集数据查询、数据操纵、数据定义和数据控制功能为一体，其中语句 GRANT，REVOKE 是实现U 【12】 /U功能。（分数：2.00）填空项 1:_77.对数据库结构的描述和定义存储在 【13】 中，它是 DBMS 运行的基本依据。（分数：2.00）填空项 1:_78.Microsoft SQL Server 2000 和 Commerce S
25、erver 2000 集成使用，可以创建 B2B 和 B2C 网站，并支持U 【14】 /U数据分析。（分数：2.00）填空项 1:_79.数据库中，每个事务都感觉不到系统中其他事务在并发地执行，这一特性称为事务的U 【15】 /U。（分数：2.00）填空项 1:_80.两阶段封锁协议下，将多个事务根据它们的封锁点进行排序，这个顺序就是事务的一个U 【16】 /U次序。（分数：2.00）填空项 1:_81.在关系数据库规范化理论的研究中，在函数依赖的范畴内， 【17】 达到了最高的规范化程度。（分数：2.00）填空项 1:_82.设在关系模式 R（A，B，C，D，E，F，G）中，根据语义有如下
26、函数依赖集F=AB，CD，CF，（A，D）E，（E，F）G 。关系模式 R 的码是U 【18】 /U。（分数：2.00）填空项 1:_83.分布式数据库系统是用通信网络连接起来的节点集合，每个节点是一个独立的 【19】 节点。（分数：2.00）填空项 1:_84.面向对象技术的复杂对象构造能力，突破了关系模型的U 【20】 /U不可再分的限制。（分数：2.00）填空项 1:_全国计算机等级考试三级数据库技术真题 2003 年 9 月答案解析(总分：98.00，做题时间：90 分钟)一、B选择题/B(总题数：64，分数：58.00)1.在计算机硬件系统的基本组成中，完成解释指令、执行指令的功能部
27、件是 A）运算器 B）控制器 C）存储器 D）输入输出设备（分数：1.00）A.B. C.D.解析：【解析】冯诺依曼提出的存储程序工作原理决定了计算机硬件系统的 5 个基本组成部分，即运算器、控制器、存储器、输入设备和输出设备。运算器是计算机中执行各种算术运算和逻辑运算的部件，也叫算术逻辑单元。存储器是计算机中具有记忆能力的部件，它能根据地址接收和保存指令或数据，并能根据命令提供有关地址的指令或数据。 控制器的主要作用是使整个计算机能够自动地执行程序，并控制计算机各功能部件协调一致地动作。执行程序时，控制器先从主存中按顺序取出程序中的一条指令，解释该指令并形成数据地址，取出所需的数据，然后向其
28、他功能部件发出执行该指令所需的各种时序控制信号。然后再从主存中取出下一条指令执行，如此循环，直到程序完成。计算机自动工作的过程就是逐条执行程序中指令的过程。 输入设备的主要功能是将数据、程序等用户信息变换为计算机能识别和处理的信息形式。 输出设备的主要功能是将计算机中的二进制信息变换为计算机用户所需要并能识别的信息形式。2.利用计算机对指纹进行识别、对图像和声音进行处理属于下列哪一个应用领域？ A）科学计算 B）过程控制 C）辅助设计 D）信息处理（分数：1.00）A.B.C.D. 解析：【解析】数据和信息处理是计算机的重要应用领域，当前的数据也有了更加广泛的含义，如图、文、声、像 等多媒体数
29、据，它们都已成为计算机的处理对象。3.多媒体网络应用及实时通信要求网络高速率传输，并且延迟低。下列哪一项技术满足这类应用的要求？ A）ATM B）FDDI C）FR D）X.25（分数：1.00）A. B.C.D.解析：【解析】异步传输模式 ATM 是新一代的数据传输与分组交换技术。促进 ATM 技术发展的因素主要有 以下几个方面：用户对网络带宽与对带宽高效、动态分配需求的不断增长；对网络实时应用需求 的提高；网络的设计与组建进一步走向标准化的需要。关键还是在于 ATM 技术能保证用户对 数据传输的服务质量的需求。在多媒体网络应用中需要同时传输语音、数字、文字以及图形信息 等多种类型的数据，并
30、且不同类型的数据对传输的服务要求不同，对数据传输的实时性要求越来 越高。所以，多媒体网络应用及实时通信要求网络高速率传输，并且延迟低，而 ATM 技术能满 足这类应用的要求。4.下列协议中，哪一个是在传输层定义的？ A）FTP B）RIP C）TCP D）IP（分数：1.00）A.B.C. D.解析：【解析】TCPIP 参考模型在网络层定义了 IP 协议，在传输层定义了传输控制协议(TCP)与用户数据报 协议(UDP)。5.下列哪一（些）项属于询问-应答式协议？ 私钥密码技术 公钥密码技术 A）只有 B）只有 C）和 D）都不是（分数：1.00）A.B.C. D.解析：【解析】目前已有识别协议
31、，大多数为询问-应答式协议，其基本原理是验证者提出问题，通常是随机的选 择一些称为口令的随机数，由识别者回答，然后由验证者验证其真实性。询问一应答式协议分为 两类：一类基于私钥密码技术，在这类协议中，验证者知道识别者的秘密；另一类是基于公钥密码 技术，在这类协议中，验证者不知道识别者的秘密。6.下列关于网络安全服务的叙述中，哪一个是错误的？ A）应提供访问控制服务以防止用户否认已接收的信息 B）应提供认证服务以保证用户身份的真实性 C）应提供数据完整性服务以防止信息在传输过程中被删除 D）应提供保密性服务以防止传输的数据被截获或篡改（分数：1.00）A. B.C.D.解析：【解析】一个功能完备
32、的网络系统应提供以下基本的安全服务功能： 保密性：保密性服务是针对网络传输数据的保护而提出的，它的目标是防止传输的数据被截 获与修改。 认证：认证服务是要解决网络中信息传送的源结点用户与目的结点用户的身份的真实性，防 止出现假冒、伪装等问题。 数据完整性：数据完整性服务是用来保证发送信息与接收数据的一致性，防止信息在传输过 程中被插入或删除。 防抵赖：防抵赖服务是用来保证源结点用户与目的结点用户不能对已发送或已接收的信息予 以否认的。 访问控制：访问控制服务是用来控制与限定网络用户对主机、应用、数据及网络服务的访问类 型。7.以下关于数据结构的基本概念的叙述中哪一条是错误的？ A）数据元素是数
33、据的基本单位 B）数据项是有独立含义的数据最小单位 C）数据结构概念包含的主要内容是数据的逻辑结构和数据的存储结构 D）数据的逻辑结构分为线性结构和非线性结构（分数：1.00）A.B.C. D.解析：【解析】数据结构的概念包含的主要内容是数据的逻辑结构、数据的存储结构和数据的运算。8.以下关于链式存储结构的叙述中哪一条是错误的？ A）结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B）逻辑上相邻的结点物理上不必邻接 C）可以通过计算直接确定第 i 个结点的存储地址 D）插入、删除运算操作方便，不必移动结点（分数：1.00）A.B.C. D.解析：【解析】链式存储方式的主要特点如下：
34、 结点除自身信息外，还有表示连接信息的指针域，因此存储密度小于顺序存储结构，存储空间 利用率低。 逻辑上相邻的结点物理上不必相邻，可用于线性表、树、图等多种逻辑结构的存储表示。 插入、删除操作方便灵活，只要改变结点中的指针域即可，不必移动结点。 其缺点也主要有以下两个方面： 每个结点增加了一个后继指针域，要花费更多的存储空间。 不能随机的直接访问线性表的任一结点。9.栈结构不适用于下列哪一种应用？ A）表达式求值 B）树的层次次序周游算法的实现 C）二叉树对称序周游算法的实现 D）快速排序算法的实现（分数：1.00）A.B. C.D.解析：【解析】树的层次次序周游算法的实现用栈结构不合适。10
35、.如下是一个稀疏矩阵的三元组法存储表示和相关的叙述 （分数：1.00）A.B.C. D.解析：【解析】稀疏矩阵指具有大量 0 元素的矩阵，对于稀疏矩阵可以采用压缩存储，只存储非零元素。三元组存储方法是用线性表来表示稀疏矩 阵。上述稀疏矩阵的三元组存储表中只有 6 个非零元素。11.设根结点的层次为 0，则高度为 k 的二叉树的最大结点数为A）2 k B）2 k-1C）2 k+1 D）2 k+1-1（分数：1.00）A.B.C.D. 解析：【解析】可用数学归纳法证明二叉树第 k 层的结点数目为 2k。归纳基础：k=0 时，只有一个根结点，命题成立。k=1 时，最多有 2 个结点，命题也成立。归纳
36、假设：假设 k=1 时命题成立。归纳步骤：高度为 k-1 的二叉树最大结点数为 2k-1，由于二叉树的每个结点最多有 2 个孩子，第 k 层的结点数目最大为第 k-l 的最大结点数的 2 倍，即 22k-1=2k命题成立。在有相同深度的二叉树中，仅当每一层都含有最大结点数时二叉树中结点数最多，故根结点的层次为0，则高度为 k 的二叉树的最大结点数为：2 0+21+2k=2k+1-1。12.对线性表进行二分法查找，其前提条件是 A）线性表以顺序方式存储，并已按关键码值排好序 B）线性表以顺序方式存储，并已按关键码值的查找频率排好序 C）线性表以链接方式存储，并已按关键码值排好序 D）线性表以链接
37、方式存储，并已按关键码值的查找频率排好序（分数：1.00）A. B.C.D.解析：【解析】二分法查找是一种效率较高的线性表查找方法，要进行二分法查找，线性表结点必须是按关键 码值排好序，且线性表以顺序方式存储。13.在包含 1000 个元素的线性表中实现如下各运算，哪一个所需的执行时间最长？ A）线性表按顺序方式存储，在线性表的第 10 个结点后面插入一个新结点 B）线性表按链接方式存储，在线性表的第 10 个结点后面插入一个新结点 C）线性表按顺序方式存储，删除线性表的第 990 个结点 D）线性表按链接方式存储，删除指针 P 所指向的结点（分数：1.00）A. B.C.D.解析：【解析】线
38、性表按顺序方式存储，在线性表的第 10 个结点后面插入一个新结点，需要将第111000 个 结点都向后移动一个位置；线性表按链接方式存储，在线性表的第 10 个结点后面插入一个新结 点，只需从第一个结点开始找到第 10 个结点在其后插入即可。删除道理相同。14.设有字符序列（Q，H，C，Y，P，A，M，S，R，D，F，X），问新序列（F，H，C，D，P，A，M，Q，R，S，Y，X）是下列哪一个排序算法一趟扫描的结果？ A）起泡排序 B）初始步长为 4 的希尔排序 C）二路归并排序 D）以第一元素为分界元素的快速排序（分数：1.00）A.B.C.D. 解析：【解析】起泡排序的基本思想是将表中两个
39、相邻元素依次比较，若不符合排序要求，则交换位置，这样经 过 n-1 次比较后，将确定出最大(或最小)元素的位置，这称为一趟扫描。经过 n-1 次扫描后， 就完成了整个表的排序。希尔(Shell)排序法的基本思想是第一步是将数据分成 n1(n1 为初始步长)个组，所有距离为 n 的倍数的元素分在一个组中，各组内用插入法排序。然后让第二个步长 n2(n2快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然 后用递归的方法处理这两个子表，直到完成整个表的排序。不难看出，上述的新序列是按快速排序的思想扫描的结果。15.下面关于 B 树运算的叙述中，正确的是 A）若插入过程
40、中根结点发生分裂，则 B 树的高度加 1 B）每当进行插入运算，就往 B 树的最下面一层增加一个新结点 C）若要删除的关键码出现在根结点中，则不能真正删除，只能做标记 D）删除可能引起 B 树结点个数减少，但不会造成 B 树高度减小（分数：1.00）A. B.C.D.解析：【解析】在 B 树里插入一个关键码的方法是很简单的。对于叶结点处于第 i 层的 B 树，插入的关键码总是进入第 i-l 层的结点。插入可能导致 B 树朝着根的方向生长。如果要插入的那个结点包含的关键码是满的，不能再往里插了，在这种情况下，要把这个结点分裂为两个，并把中间的一个关键码拿出来插到结点的双亲结点里去。双亲结点也可能
41、是满的，就需要再分裂，再往上插。最坏的情况，这个过程可能一直传到根，如果需要分裂根，由于根是没有双亲的，这时就建立一个新的根结点。整个 B 树增加了一层。 删除的过程与之类似，但要稍微复杂。如果删除的关键码不在第 i-1 层，则先把此关键码与它在 B 树里的后继对换位置，然后再删除该关键码。如果删除的关键码在第 i-1 层，则把它从它所在的结点里去掉，这可能导致此结点所包含的关键码的个数小于m2-1。这种情况下，考查该结点的左或右兄弟，从兄弟结点移若干个关键码到该结点中来，使两个结点所含关键码个数基本相同。只有在兄弟结点的关键码个数也很少，刚好等于m2-1 时，这个移动才不能进行。这种情况下，
42、要把删除了关键码的结点、它的兄弟结点及它们的双亲结点中的一个关键码合并为一个结点。从双亲结点中包含一个关键码有时也可能导致进一步的合并，甚至这种合并一直传到根结点。在根结点只包含一个关键码的情况下，将发生直到根结点的合并，使结点和它的两个子女进行合并，形成新的根结点，从而使整个树减少一层。16.下列关于中断的叙述中，错误的是 A）时间片到时属于时钟中断 B）目态下执行特权指令将产生程序性中断 C）缺页中断属于自愿性中断 D）打印机完成打印将产生输入输出中断（分数：1.00）A.B.C. D.解析：【解析】一个进程占有处理器运行时，由于自身或外界的原因使运行被打断，让操作系统处理所出现的 事件，
43、到适当的时候再让被中断的进程继续运行，这个过程称为“中断”。从中断事件的性质来 说，中断可分为两大类：强迫性中断(包括硬件故障中断、程序性中断、外部中断、输入输出中 断)和自愿性中断。强迫性中断是正在运行程序所不期望的，自愿性中断是正在运行程序有意 识安排的。缺页中断事件是一种程序性中断，属于强迫性中断。17.采用“不可剥夺优先数“调度算法，进程执行的次序是 A）P2、P1、P5、P3、P4 B）P2、P3、P1、P5、P4 C）P4、P1、P3、P5、P2 D）P4、P3、P1、P5、P2（分数：1.00）A.B. C.D.解析：【解析】进程调度总是让具有最高优先数的进程先使用处理器。如果进
44、程具有相同的优先数，则这些具有相同优先数的进程再按先来先服务的次序分配处理器。 一个高优先数的进程占用了处理器后，系统可以用两种方式对待它：第一种方式是“非抢占式”的，一旦有某个高优先数的进程占用了处理器，就一直让它运行下去，直到该进程由于自身的原因主动让出处理器或进程执行结束而让出处理器，此时，进程调度重新再按优先数选择另一个占用处理器的进程。第二种方式是“可抢占”的，这种方式是严格保证任何时刻，总是让具有最高优先数的进程在处理器上运行。也就是说，当某一进程在处理器上运行时，一旦有另一个更高优先数的进程就绪，进程调度就要剥夺正在处理器上运行的进程使用处理器的权力，抢回分配给它的处理器，而把处
45、理器让具有更高优先数的进程使用。这种抢占式的优先数调度算法在实时系统中很有用。 通过分析以上调度顺序可知，选项 B)是正确的。18.采用“不可剥夺优先数“调度算法，进程在就绪队列中的平均等待时间为 A）6 B）7 C）8 D）9（分数：1.00）A.B. C.D.解析：【解析】平均等待时间为每个进程的等待时间的和除以进程总数，即(0+1+3+13+18)5=7。19.下列各项中哪一个不是虚拟页式存储管理中缺页中断处理所做的工作？ A）通过文件系统将所需页面从外存调入内存 B）调用内存分配程序 C）修改页表 D）调度被中断程序继续执行（分数：1.00）A.B.C.D. 解析：【解析】虚拟页式存储管理的基本思想是，在进程开始执行前，不是装入全部页面，而只是装入 1个(甚 至 0 个)页面，然后根据进程执行的需要，动态地装入其他页面。缺页中断处理把所需的页面从 外存调入内存，并把物理号填入页表，更改驻留位，然后再返回继续执行被中断的进程。20.下列哪一个是引入工作集模型的前提因素？ A）系统效率下降 B）页面淘汰算法选择不合理 C）程序的局部性原理 D）分配给进程的物理页面数太少（分数：1.00）A.B.C. D.解析：【解析】对于给定的进程访问序列，从时刻(t-)到时刻 t 之间所访问页面的集合，称为该进程的工作 集。其
