四川大学数据库技术复习题 一选择题

可编辑修改精选全文完整版数据库题库及答案数据库技术是计算机科学中重要的一部分，广泛应用于各个领域。

为了更好地学习和理解数据库知识，题库是一个非常有用的资源。

本文提供一些常见的数据库题目及其答案，希望对读者的学习和实践有所帮助。

一、选择题1. 在关系数据库中，用于描述记录之间的关系的是：a) 表格b) 行c) 列d) 键答案：a) 表格2. 数据库管理系统(DBMS)的主要功能包括：a) 数据的存储和管理b) 数据的查询和分析c) 数据的备份和恢复d) 数据的安全性控制答案：a) 数据的存储和管理、b) 数据的查询和分析、c) 数据的备份和恢复、d) 数据的安全性控制3. 关系数据库中，用于唯一标识一条记录的属性被称为：a) 主键b) 外键c) 候选键d) 索引答案：a) 主键4. 数据库的范式用于描述数据库的结构是否符合某种规范。

以下哪一项不是数据库的范式：a) 一范式b) 二范式c) 三范式d) 四范式答案：d) 四范式5. 在SQL语句中，用于插入新记录的关键字是：a) SELECTb) UPDATEc) INSERTd) DELETE答案：c) INSERT二、填空题1. 在关系数据库中，每一行都代表一个________。

答案：记录2. 数据库中具有相同属性的记录集合被称为____________。

答案：表3. 在关系数据库中，用于检索某一部分记录的语句是________。

答案：SELECT4. 数据库设计中常用的三个范式依次是一范式、二范式和__________。

答案：三范式5. 数据库表中，用于唯一标识一条记录的属性被称为________。

答案：主键三、应用题1. 请列举至少三种数据库管理系统(DBMS)的类型，并简要描述它们的特点。

答案：关系型数据库管理系统(RDBMS)：采用表格的形式组织数据，具有高度结构化和强一致性的特点。

常见的关系型数据库管理系统有MySQL、Oracle、SQL Server等。

四川⼤学数据库技术复习题⼀选择题数据库技术试题⼀、选择题1. 单个⽤户使⽤的数据视图的描述称为A. 外模式B. 概念模式C. 内模式D. 存储模式2. ⼦模式DDL⽤来描述A. 数据库的总体逻辑结构B. 数据库的局部逻辑结构C. 数据库的物理存储结构D. 数据库的概念结构3. 在DBS中，DBMS和OS之间的关系是A. 相互调⽤B. DBMS调⽤OSC. OS调⽤DBMSD. 并发运⾏4. 当关系R和S⾃然联接时，能够把R和S原该舍弃的元组放到结果关系中的操作是A. 左外联接B. 右外联接C. 外部并D. 外联接5. 下列聚合函数中不忽略空值 (null) 的是A. SUM(列名)B. MAX(列名)C. COUNT( * )D. AVG(列名)6. 设关系模式R (A，B，C)，F是R上成⽴的FD集，F = {B→C}，则分解ρ = {AB，BC}相对于FA. 是⽆损联接，也是保持FD的分解B. 是⽆损联接，但不保持FD的分解C. 不是⽆损联接，但保持FD的分解D. 既不是⽆损联接，也不保持FD 的分解B. 逻辑设计阶段C. 概念设计阶段D. 物理设计阶段8. SQL中，下列涉及空值的操作，不正确的是A. AGE IS NULLB. AGE IS NOT NULLC. AGE = NULLD. NOT (AGE IS NULL)9. ⼀个关系中的候选关键字。

A ．⾄多⼀个B ．可多个C ．必须多个D ．⾄少 3 个10. DBMS中实现事务持久性的⼦系统是A. 安全性管理⼦系统B. 完整性管理⼦系统C. 并发控制⼦系统D. 恢复管理⼦系统11. SQL的全局约束是指基于元组的检查⼦句和A. ⾮空值约束B. 域约束⼦句C. 断⾔D. 外键⼦句12. 分布式数据库系统中分⽚模式和分配模式均是A. 全局的B. 局部的C. 分布的D. 集中的13. 属性类型允许是基本数据类型、结构类型和集合类型的模型是A. 平⾯关系模型B. 嵌套关系模型C. 复合对象模型D. 分布式关系模型14. ⽤树型结构表⽰实体之间联系的数据模型称为D．层次模型15. 数据库系统的核⼼是A．数据库B．数据库管理系统C．数据模型D．软件⼯具16. 在SQL语⾔中，与X BETWEEN 10 AND 20等价的表达式是A．X＞10 AND X＜20B．X＞=10 AND X＜20C．X＞10 AND X＜=20D．X＞=10 AND X＜=2017. 某个E-R图中有5个实体型，2个1∶n联系和2个m∶n联系，则该E-R图转换的关系模式个数⾄少是A．5个B．7个C．8个D．9个18. 若关系模式R（V，F）中的每⼀个决定属性集都包含候选码，则R属于A．2NFB．3NFC．BCNFD．4NF19. 若事务T对数据R已加X锁，则其他事务对数据RA．可以加S锁不能加X锁B．不能加S锁可以加X锁C．可以加S锁也可以加X锁D．不能加任何锁20．在⽬前的并⾏数据库体系结构中，可扩充性最⾼的是A．SMB．SDC．SND．SK21．数据的正确性和相容性是指数据库的A．完整性22．下列不属于事务的特性的是A．隔离性B．⼀致性C．完整性D．原⼦性23．系统在运⾏过程中，由于某种硬件故障，使存储在外存上的数据部分损失或全部损失，这种情况属于A．事务故障B．系统故障C．介质故障D．运⾏故障24．E-R图是数据库设计的常⽤⼯具之⼀，它适⽤于建⽴数据库的A．概念模型B．逻辑模型C．结构模型D．物理模型25．数据库逻辑结构设计的主要任务是A．建⽴E-R图B．把数据送⼊数据库C．建⽴数据流图和需求说明书D．将E-R图转换为某个DBMS所⽀持的数据模型26.下⾯不是SQL语⾔优点的是。

大学数据库试题及答案一、单项选择题（每题2分，共20分）1. 在关系数据库中，关系是指（）。

A. 表B. 行C. 列D. 数据库2. SQL语言中，用于查询数据的关键字是（）。

A. SELECTB. INSERTC. UPDATED. DELETE3. 在数据库设计中，为了减少数据冗余，通常采用（）。

A. 规范化B. 反规范化C. 索引化D. 压缩4. 数据库管理系统（DBMS）的主要功能不包括（）。

A. 数据定义B. 数据操纵C. 数据存储D. 数据加密5. 在关系数据库中，主键是用来（）。

A. 唯一标识每个元组B. 存储数据C. 索引数据D. 排序数据6. 数据库的完整性约束包括（）。

A. 实体完整性B. 参照完整性C. 用户定义完整性D. 所有以上7. 以下哪个不是数据库的三级模式结构（）。

A. 外模式B. 概念模式C. 内模式D. 物理模式8. 在SQL中，用于创建新表的语句是（）。

A. CREATE TABLEB. ALTER TABLEC. DROP TABLED. TRUNCATE TABLE9. 以下哪个选项不是事务的特性（）。

A. 原子性B. 一致性C. 隔离性D. 可逆性10. 数据库中的视图是（）。

A. 存储在磁盘上的物理表B. 存储在内存中的临时表C. 基于SQL查询的虚拟表D. 存储在数据库中的索引二、多项选择题（每题3分，共15分）1. 在数据库设计过程中，以下哪些步骤是必要的？（）A. 需求分析B. 概念设计C. 逻辑设计D. 物理设计2. 以下哪些是数据库系统的主要组成部分？（）A. 数据库B. 数据库管理系统C. 应用程序D. 用户3. 关系数据库中，以下哪些操作是合法的？（）A. 插入新行B. 删除现有行C. 更新现有行D. 删除整个表4. 在数据库中，以下哪些措施可以提高查询性能？（）A. 使用索引B. 增加数据冗余C. 使用视图D. 优化查询语句5. 数据库的安全性措施包括（）。

（b）等值连接不把重复属性去掉，而自然连接要把重复属性去掉。

3、为什么将SQL 中的视图称为“虚表”？答：在SQL中创建一个视图时，系统只是将视图的定义存放在数据字典中，并不存储视图对应的数据，在用户使用视图时才去求对应的数据，因此，我们将视图称为“虚表”。

这样处理的目的是为了节约存储空间，因为视图对应的数据都可从相应的基本表中获得。

4、列出3条查询优化的启发式规则。

答：3 条启发式优化规则是：尽可能早地执行选择运算，尽可能早地执行投影运算，把笛卡尔积与附近的一连串选择和投影合并起来做。

5、试叙述“串行调度”与“可串行化调度”的区别。

答：事务的执行次序称为调度。

如果多个事务依次执行，则称为事务的串行调度。

如果利用分时的方法，同时处理多个事务，则称为事务的并发调度。

如果一个并发调度的结果与某一串行调度的执行结果等价，那么这个并发调度称为是可串行化的调度。

三、设计题（共8分）在学术论文完成过程中，一位学者可以撰写多篇论文，一篇论文也可由多位学者合著，每篇论文的作者都有一个排序。

一篇论文只能发表一次，学术刊物的某一辑（卷号、期号）发表多篇论文在。

设学者的属性有：身份证号、姓名、单位、通讯地址；论文的属性有：论文题目、主题、术语；学术刊物的属性有：ISBN号、名称、影响因子。

试完成以下两题：（1）根据这段话的意思，画出其E-R 图。

（4分）（2）将这个E-R 图转换为满足3NF的关系模式，并给出各关系模式中的主码。

（4分）（3）SELECT DISTINCT X.SnoFROM SC X, SC YWHERE X.Sno=Y.Sno AND o!=o;（4）SELECT DISTINCT SnoFROM SC XWHERE NOT EXISTS(SELECT *FROM CWHERE Teacher='张' AND NOT EXISTS(SELECT *FROM SC YWHERE Y.Sno=X.Sno AND o=o));五、查询优化（共10分）给定“学生-课程”数据库的关系模式如三大题4小题：S(Sno，Sname，Sgender，Sage)SC(Sno，Cno，Grade)C(Cno，Cname，Teacher)对查询“检索选修“信息系统”课程的学生姓名与年龄。

数据库期末考试试题及答案一、单项选择题（每题2分，共20分）1. 数据库管理系统（DBMS）是（）。

A. 一组软件B. 一个数据库C. 一组硬件D. 一个操作系统答案：A2. 在关系数据库中，关系是指（）。

A. 行的集合B. 列的集合C. 行和列的有序对集合D. 行和列的无序对集合答案：C3. SQL是（）。

A. 数据定义语言B. 数据控制语言C. 数据操纵语言D. 结构化查询语言答案：D4. 数据库系统的核心是（）。

A. 数据模型B. 数据库管理系统C. 数据库D. 应用程序答案：C5. 数据库设计中，视图设计属于（）。

A. 概念性设计B. 逻辑设计C. 物理设计D. 实体-关系模型设计答案：B6. 在关系数据库中，一个关系至少有一个候选键，一个候选键可以有（）个属性。

A. 一个B. 多个C. 零个D. 任意个答案：B7. 数据库管理系统能提供数据的（）。

A. 物理独立性B. 逻辑独立性C. 数据独立性D. 以上都是答案：D8. 数据库中，存储数据的基本单位是（）。

A. 记录B. 字段C. 表D. 文件答案：C9. 数据库系统与文件系统相比，数据库系统能够提供（）。

A. 数据共享B. 数据独立性C. 数据完整性D. 以上都是答案：D10. 在数据库中，数据的完整性约束不包括（）。

A. 实体完整性B. 参照完整性C. 用户定义的完整性D. 数据冗余答案：D二、填空题（每题2分，共20分）1. 数据库系统由数据库、数据库管理系统和_________组成。

答案：数据库应用程序2. 数据库系统的核心是_________。

答案：数据库3. 数据库管理系统的主要功能包括数据定义、数据操纵、数据控制和_________。

答案：事务管理4. 在关系数据库中，关系模式的每一个分量称为_________。

答案：属性5. 数据库设计分为概念性设计、_________设计和物理设计三个阶段。

答案：逻辑6. 在数据库中，_________是指关系中的列。

数据库应用技术试题及答案一、选择题（共10题，每题2分，共20分）1. 下列哪个是关系型数据库管理系统（RDBMS）？A. MongoDBB. RedisC. MySQLD. Cassandra正确答案：C2. 在数据库中，下列哪种约束用于保证关系完整性？A. 主键约束B. 唯一约束C. 外键约束D. 默认约束正确答案：A3. 在SQL语句中，用于查询数据的关键字是：A. SELECTB. INSERTC. UPDATED. DELETE正确答案：A4. 下列哪种SQL语句可以用于创建数据库表？A. INSERTB. DELETEC. CREATED. UPDATE正确答案：C5. 下面哪种数据库设计范式是最低级的范式？A. 第一范式B. 第二范式C. 第三范式D. BCNF范式正确答案：A6. 在数据库中，用于限定字段值的数据类型是：A. 约束B. 视图C. 索引D. 数据类型正确答案：D7. 下列哪种关系型数据库管理系统（RDBMS）属于开源软件？A. OracleB. SQL ServerC. PostgreSQLD. DB2正确答案：C8. 在关系型数据库中，用于表示表之间关系的是：A. 主键B. 外键C. 索引D. 视图正确答案：B9. 下列哪个SQL函数用于计算记录的数量？A. COUNT()B. AVG()C. MAX()D. MIN()正确答案：A10. 下列哪种数据库对象用于提高查询效率？A. 视图B. 存储过程C. 索引D. 触发器正确答案：C二、简答题（共5题，每题10分，共50分）1. 请简要说明关系型数据库与非关系型数据库的区别。

答案：关系型数据库是以表为基础的数据库系统，数据存储在表中，并且具有严格定义的结构。

它支持事务处理和SQL查询语言。

非关系型数据库是一种灵活的数据库系统，数据以键值对的形式存储，没有严格的结构定义，不需要使用SQL语言进行查询。

关系型数据库适用于结构化数据，非关系型数据库适用于半结构化或非结构化数据。

数据库试题及答案一、选择题（每题2分，共20分）1. 数据库管理系统（DBMS）的主要功能是______。

A. 数据存储B. 数据管理C. 数据保护D. 数据备份答案：B2. 在关系数据库中，数据是按照______存储的。

A. 记录B. 表格C. 索引D. 视图答案：B3. SQL语言中的“SELECT”语句用于执行______。

A. 数据更新B. 数据查询C. 数据删除D. 数据插入答案：B4. 以下哪个不是数据库设计中的范式？A. 第一范式（1NF）B. 第二范式（2NF）C. 第三范式（3NF）D. 第四范式（4NF）答案：D5. 在数据库中，事务的ACID属性不包括以下哪一项？A. 原子性（Atomicity）B. 一致性（Consistency）C. 隔离性（Isolation）D. 可扩展性（Scalability）答案：D...（此处省略剩余选择题）二、简答题（每题10分，共30分）1. 简述数据库的三级模式结构是什么？答案：数据库的三级模式结构包括外模式（用户模式）、概念模式（逻辑模式）和内模式（存储模式）。

外模式是用户与数据库交互的视图，概念模式是数据库的全局逻辑结构，内模式是数据库的物理存储结构。

2. 解释什么是数据库的规范化，并说明其目的是什么？答案：数据库的规范化是将数据库设计成一种逻辑上更简单、更一致的形式的过程。

其目的是减少数据冗余，提高数据完整性，以及简化数据的维护。

3. 描述什么是数据库的并发控制，并举例说明其重要性。

答案：数据库的并发控制是指在多用户环境中，数据库管理系统（DBMS）用来确保多个事务可以安全地同时执行的机制。

例如，在银行系统中，多个用户可能同时进行转账操作，正确的并发控制可以确保每笔交易的准确性和一致性。

三、计算题（每题15分，共30分）1. 假设有一个学生表Student，包含字段：学号（S#），姓名（Sname），性别（Sex），年龄（Age）。

数据库一.单选题（共39题,58.5分）1在SQL语句中,表达式“工资BETWEEN 1200 AND 1250”的含义是•A、工资> 1200 AND 工资<1250•B、工资> 1200 OR 工资<1250•C、工资> =1200 AND 工资<=1250•D、工资> =1200 OR 工资<=1250正确答案： C答案解析：2要为当前表所有职工增加100元工资,正确的SQL命令是命令•A、CHANGE 职工SET 工资=工资+100•B、REPLACE 职工SET 工资=工资+100•C、EDIT 职工SET 工资=工资+100•D、UPDATE 职工SET 工资=工资+100正确答案： D答案解析：3如下SQL语句Select avg(工资),单位名 from 职工 where 单位号 in (select 单位号 from 单位where 单位名=”设计所”)查询结果为•A、2000.00•B、1833.33•C、2100.00•D、3000.00正确答案： B答案解析：4在浏览窗口中,不能将一条记录逻辑删除的操作是( )•A、将光标定位于该记录,按Ctrl+T键•B、将光标定位于该记录,按DELECT键•C、将光标定位于该记录,单击表菜单中的“切换删除标志”选项•D、单击该记录前的白色小方块,使其变黑。

正确答案： B答案解析：5删除表的SQL命令是•A、DROP TABLE•B、DELETE TABLE•C、ERASE TABLE•D、KILL TABLE正确答案： A答案解析：6有SQL语句:SELECT MIN(工资)FROM 职工的执行结果是•A、工资的最大值•B、工资的最小值•C、工资的平均值•D、工资的合计正确答案： B答案解析：7在SQL语句中用于限定条件的短语是•A、FOR•B、WHILE•C、WHERE•D、CONDITION正确答案： C答案解析：8Delete的作用是•A、将记录从表中彻底删除•B、只给要删除的记录做删除标志•C、不能删除记录•D、删除整个表中的记录正确答案： B答案解析：9在Foxpro6.0中,打开数据库使用的命令为( )•A、USE•B、SELECT•C、OPEN•D、CREATE正确答案： C答案解析：10要为当前表所有商品价格上调8%,正确的SQL命令是命令( )。

四川大学期末考试试题(闭卷)A课程名称：数据库系统原理一．选择题。

（每小题2分，共12分）1.以下不是事物性质的是（）A．持久性 B.原子性 C.可串行性 D.一致性2．以下封解锁序列中，满足两段锁协议的是（）A．Lock-X(U)…Lock-S(V)…Lock-S(W)…Unlock(U)…Unlock(W)…Unlock(V) B．Lock-X(U)…Unlock(U)…Lock-S(V)…Unlock(V)…Lock-S(W)…Unlock(W) C．Lock-X(U)…Lock-S(V)…Unlock(U)…Unlock(V)…Lock-S(W)…Unlock(W) D．Lock-X(U)…Unlock(U)…Lock-S(V)…Lock-S(V)…Unlock(W)…Unlock(W) 3．以下关于死锁的说法中正确的是（）A．两段锁协议可避免死锁 B.DBMS一般采用超时法检查死锁C．死锁是由于持锁事务重启后造成的 D.系统中至少有两个并发事务才可能发生死锁4．当事务获得数据项Q的排他锁后，该事务（）A．只能读Q B. 只能写Q C. 既能读Q，又能写QD．既不能读Q，也不能写Q5. 如果一个系统关系模式仅有两个属性，则该关系模式至少满足（）A. INFB.2NFC.3NFD.BCNF6.在数据局设计中，画ER图是（）的主要任务A．需求分析阶段 B.概念结构设计阶段C．逻辑结构设计阶段 D.物理结构设计阶段二．简答题。

（每小题6分，共12分）1.什么是数据库系统的三级模式结构？它是如何保证数据独立性的？2.1.以下1-2要求写出关系代数查询。

1.查询“t1003”号员工工作过的各部门部门编号和部门名；2.查询在“t1003”号员工工作过的所有部门都工作过的员工的编号及其姓名；以下3-6要求写出SQL查询：3.查询“t1003”号员工工作过的各部门部门编号和部门名；4.查询所有姓名为“王勇”的员工工作过的部门编号和部门名；5.查询在“t1003”号员工工作过的所有部门都工作过的员工的编号及其姓名；6.查询目前在职员工人数最多的部门编号。

_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一Chapter 1 Data Structures and Algorithms: Instructor's CD questions1.The primary purpose of most computer programs isa)to perform a mathematical calculation.*b) to store and retrieve information.c)to sort a collection of records.d)all of the above.e)none of the above.2.An integer is aa)) simple typeb)aggregate typec)composite typed)a and be)none of the above3.A payroll records is aa)simple typeb)aggregate typec)composite type*d) a and b e) none of the above4.Which of the following should NOT be viewed as an ADT?a)listb)integerc)array*d) none of the above5.A mathematical function is most like a*a) Problemb)Algorithmc)Program6.An algorithm must be or do all of the following EXCEPT:a)correctb)composed of concrete steps*c) ambiguousd)composed of a finite number of stepse)terminate7.A solution is efficient ifa.it solves a problem within the require resource constraints.b.it solves a problem within human reaction time.1_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库_______ c.it solves a problem faster than other known solutions.d.a and b.*e. a and c.f. b and c.8.An array isa)A contiguous block of memory locations where each memory location storesa fixed-length data item.b)An ADT composed of a homogeneous collection of data items, each data item identified by a particular number.c)a set of integer values.*d) a and b.e)a and c.f)b and c.9.Order the following steps to selecting a data structure to solve a problem.(1)Determine the basic operations to be supported.(2)Quantify the resource constraints for each operation.(3)Select the data structure that best meets these requirements.(4)Analyze the problem to determine the resource constraints that anysolution must meet.a)(1, 2, 3, 4)b)(2, 3, 1, 4)c)(2, 1, 3, 4)*d) (1, 2, 4, 3)e) (1, 4, 3, 2)10.Searching for all those records in a database with key value between 10 and 100 is known as:a) An exact match query.*b) A range query.c)A sequential search.d)A binary search.Chapter 2 Mathematical Preliminaries: Instructor's CD questions1.A set has the following properties:a)May have duplicates, element have a position.b)May have duplicates, elements do not have a position.c)May not have duplicates, elements have a position.*d) May not have duplicates, elements do not have a position._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库2.A sequence has the following properties:a)) May have duplicates, element have a position.b)May have duplicates, elements do not have a position.c)May not have duplicates, elements have a position.d)May not have duplicates, elements do not have a position.3.For set F, the notation |P| indicatesa)) The number of elements in Pb)The inverse of Pc)The powerset of F.d)None of the above.4.Assume that P contains n elements. The number of sets in the powerset of P isa)nb)n A2*c) 2A nd)2A n - 1e) 2A n + 15.If a sequence has n values, then the number of permutations for that sequence will bea)nb)n A2c)n A2 - 1d)2A n*e) n!6.If R is a binary relation over set S, then R is reflexive if*a) aRa for all a in S.b)whenever aRb, then bRa, for all a, b in S.c)whenever aRb and bRa, then a = b, for all a, b in S.d)whenever aRb and aRc, then aRc, for all a, b, c in S.7.If R is a binary relation over set S, then R is transitive ifa)aRa for all a in S.b)whenever aRb, then bRa, for all a, b in S.c)whenever aRb and bRa, then a = b, for all a, b in S.*d) whenever aRb and aRc, then aRc, for all a, b, c in S.8.R is an equivalence relation on set S if it isa)) reflexive, symmetric, transitive.b)reflexive, antisymmetric, transitive.c)symmetric, transitive.少年易学老难成，一寸光阴不可轻-百度文库d)antisymmetric, transitive.e)irreflexive, symmetric, transitive.f)irreflexive, antisymmetric, transitive.9.For the powerset of integers, the subset operation defines *a) a partial order.b)a total order.c)a transitive order.d)none of the above.10.log nm is equal toa) n + m*b) log n + log mc)m log nd)log n - log m11.A close-form solution isa) an analysis for a program.*b) an equation that directly computes the value of a summation.c) a complete solution for a problem.12.Mathematical induction is most likea) iteration.*b) recursion.c)branching.d)divide and conquer.13.A recurrence relation is often used to model programs witha)for loops.b)branch control like "if" statements.*c) recursive calls.d) function calls.14.Which of the following is not a good proof technique.a) proof by contradiction.*b) proof by example.c) proof by mathematical induction.15.We can use mathematical induction to:a) Find a closed-form solution for a summation.*b) Verify a proposed closed-form solution for a summation.c) Both find and verify a closed-form solution for a summation._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一Chapter 3 Algorithm Analysis: Instructor's CD questions1.A growth rate applies to:a)the time taken by an algorithm in the average case.b)the time taken by an algorithm as the input size grows.c)the space taken by an algorithm in the average case.d)the space taken by an algorithm as the input size grows.e)any resource you wish to measure for an algorithm in the average case.*f) any resource you wish to measure for an algorithm as the input size grows.2.Pick the growth rate that corresponds to the most efficient algorithm as n gets large:a) 5n*b) 20 log nc)2nA2d)2A n3.Pick the growth rate that corresponds to the most efficient algorithm when n =4.a)5nb)20 log nc)2nA2*d)2A n4.Pick the quadratic growth rate.a)5nb)20 log n*c) 2nA2d) 2An5.Asymptotic analysis refers to:a) The cost of an algorithm in its best, worst, or average case.*b) The growth in cost of an algorithm as the input size grows towards infinity.c)The size of a data structure.d)The cost of an algorithm for small input sizes6.For an air traffic control system, the most important metric is:a)The best-case upper bound.b)The average-case upper bound.c)) The worst-case upper bound.d)The best-case lower bound._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库__________e)The average-case lower bound.f)The worst-case lower bound.7.When we wish to describe the upper bound for a problem we use:a)) The upper bound of the best algorithm we know.b)The lower bound of the best algorithm we know.c)We can't talk about the upper bound of a problem because there can alwaysbe an arbitrarily slow algorithm.8.When we describe the lower bound for a problem we use:a)The upper bound for the best algorithm we know.b)the lower bound for the best algorithm we know.c)The smallest upper bound that we can prove for the best algorithm that could possibly exist.*d) The greatest lower bound that we can prove for the best algorithm that could possibly exist.9.When the upper and lower bounds for an algorithm are the same, we use:a)big-Oh notation.b)big-Omega notation.*c) Theta notation.d)asymptotic analysis.e)Average case analysis.f)Worst case analysis.10. When performing asymptotic analysis, we can ignore constants and low order terms because:*a) We are measuring the growth rate as the input size gets large.b)We are only interested in small input sizes.c)We are studying the worst case behavior.d)We only need an approximation.11.The best case for an algorithm refers to:a) The smallest possible input size.*b) The specific input instance of a given size that gives the lowest cost.c)The largest possible input size that meets the required growth rate.d)The specific input instance of a given size that gives the greatest cost.12.For any algorithm:a)) The upper and lower bounds always meet, but we might not know what they are.少年易学老难成，一寸光阴不可轻-百度文库b)The upper and lower bounds might or might not meet.c)We can always determine the upper bound, but might not be able to determine the lower bound.d)We can always determine the lower bound, but might not be able to determine the upper bound.13.If an algorithm is Theta(f(n)) in the average case, then it is: a) Omega(f(n)) in the best case.*b) Omega(f(n)) in the worst case.c) O(f(n)) in the worst case.14.For the purpose of performing algorithm analysis, an important property ofa basic operation is that:a)It be fast.b)It be slow enough to measure.c)Its cost does depend on the value of its operands.*d) Its cost does not depend on the value of its operands.15.For sequential search,a) The best, average, and worst cases are asymptotically the same.*b) The best case is asymptotically better than the average and worst cases.c)The best and average cases are asymptotically better than the worst case.d)The best case is asymptotically better than the average case, and the average case is asymptotically better than the worst case.Chapter 4 Lists, Stacks and Queues: Instructor's CD questions1.An ordered list is one in which:a) The element values are in sorted order.*b) Each element a position within the list.2.An ordered list is most like a:a)set.b)bag.c)) sequence.3.As compared to the linked list implementation for lists, the array-based listimplementation requires:a)More spaceb)Less space*c) More or less space depending on how many elements are in the list._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库4.Here is a series of C++ statements using the list ADT in the book.L1.append(10);L1.append(20);L1.append(15);If these statements are applied to an empty list, the result will look like:a)< 10 20 15 >*b) < | 10 20 15 >c)< 10 20 15 | >d)< 15 20 10 >e)< | 15 20 10 >f)< 15 20 10 | >5.When comparing the array-based and linked implementations, the array-based implementation has:a)) faster direct access to elements by position, but slower insert/delete from the current position.b)slower direct access to elements by position, but faster insert/delete from the current position.c)both faster direct access to elements by position, and faster insert/delete from the current position.d)both slower direct access to elements by position, and slower insert/delete from the current position.6.For a list of length n, the linked-list implementation's prev function requiresworst-case time:a)O(1).b)O(log n).*c) O(n).d) O(n A2).7.Finding the element in an array-based list with a given key value requiresworst case time:a)O(1).b)O(log n).*c) O(n).d) O(n A2).8.In the linked-list implementation presented in the book, a header node isused:*a) To simplify special cases._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一b)Because the insert and delete routines won't work correctly without it.c)Because there would be no other way to make the current pointer indicatethe first element on the list.9.When a pointer requires 4 bytes and a data element requires 4 bytes, thelinked list implementation requires less space than the array-based list implementation when the array would be:a)less than 1/4 full.b)less than 1/3 full.*c) less than half full.d)less than 第full.e)less than 34 fullf)never.10.When a pointer requires 4 bytes and a data element requires 12 bytes, thelinked list implementation requires less space than the array-based list implementation when the array would be:a)) less than 1/4 full.b)less than 1/3 full.c)less than half full.d)less than 2/3 full.e)less than 34 fullf)never.11.When we say that a list implementation enforces homogeneity, we meanthat:a) All list elements have the same size.*b) All list elements have the same type.c) All list elements appear in sort order.12.When comparing the doubly and singly linked list implementations, we findthat the doubly linked list implementation*a) Saves time on some operations at the expense of additional space.b)Saves neither time nor space, but is easier to implement.c)Saves neither time nor space, and is also harder to implement.13. We use a comparator function in the Dictionary class ADT:a)to simplify implementation.*b) to increase the opportunity for code reuse.c) to improve asymptotic efficiency of some functions.14.All operations on a stack can be implemented in constant time except:少年易学老难成，一寸光阴不可轻-百度文库a) Pushb)Popc)The implementor's choice of push or pop (they cannot both be implementedin constant time).*d) None of the above.15.Recursion is generally implemented usinga) A sorted list.*b) A stack.c) A queue.Chapter 5 Binary Trees: Instructor's CD questions1.The height of a binary tree is:a)The height of the deepest node.b)The depth of the deepest node.*c) One more than the depth of the deepest node.2.A full binary tree is one in which:*a) Every internal node has two non-empty children.b) all of the levels, except possibly the bottom level, are filled.3.The relationship between a full and a complete binary tree is:a)Every complete binary tree is full.b)Every full binary tree is complete.*c) None of the above.4.The Full Binary Tree Theorem states that:a)) The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.b)The number of leaves in a non-empty full binary tree is one less than the number of internal nodes.c)The number of leaves in a non-empty full binary tree is one half of the number of internal nodes.d)The number of internal nodes in a non-empty full binary tree is one half of the number of leaves.5.The correct traversal to use on a BST to visit the nodes in sorted order is:a) Preorder traversal.*b) Inorder traversal.c) Postorder traversal.6. When every node of a full binary tree stores a 4-byte data field,10少年易学老难成，一寸光阴不可轻-百度文库two 4-byte child pointers, and a 4-byte parent pointer, theoverhead fraction is approximately:a)one quarter.b)one third.c)one half.d)two thirds.*e) three quarters.f) none of the above.7.When every node of a full binary tree stores an 8-byte data field and two 4-byte child pointers, the overhead fraction is approximately:a)one quarter.b)one third.*c) one half.d)two thirds.e)three quarters.f)none of the above.8.When every node of a full binary tree stores a 4-byte data field and theinternal nodes store two 4-byte child pointers, the overhead fraction is approximately:a)one quarter.b)one third.*c) one half.d)two thirds.e)three quarters.f)none of the above.9.If a node is at position r in the array implementation for a complete binarytree, then its parent is at:a)) (r - 1)/2 if r > 0b)2r + 1 if (2r + 1) < nc)2r + 2 if (2r + 2) < nd)r - 1 if r is evene)r + 1 if r is odd.10.If a node is at position r in the array implementation for a complete binarytree, then its right child is at:a)(r - 1)/2 if r > 0b)2r + 1 if (2r + 1) < n*c) 2r + 2 if (2r + 2) < nd)r - 1 if r is evene)r + 1 if r is odd.11_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库—11.Assume a BST is implemented so that all nodes in the left subtree of agiven node have values less than that node, and all nodes in the rightsubtree have values greater than or equal to that node. Whenimplementing the delete routine, we must select as its replacement:a) The greatest value from the left subtree.*b) The least value from the right subtree.c) Either of the above.12.Which of the following is a true statement:a)In a BST, the left child of any node is less than the right child, and in a heap, the left child of any node is less than the right child.*b) In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.c)In a BST, the left child of any node could be less or greater than the right child, but in a heap, the left child of any node must be less than the right child.d)In both a BST and a heap, the left child of any node could be either less than or greater than the right child.13.When implementing heaps and BSTs, which is the best answer?a)The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n log n).b)The time to build a BST of n nodes is O(n), and the time to build a heap of n nodes is O(n log n).*c) The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n).d) The time to build a BST of n nodes is O(n), and the time to build a heap of n nodes is O(n).14.The Huffman coding tree works best when the frequencies for letters area) Roughly the same for all letters.*b) Skewed so that there is a great difference in relative frequencies for various letters.15.Huffman coding provides the optimal coding when:a)The messages are in English.b)The messages are binary numbers.*c) The frequency of occurrence for a letter is independent of its context within the message.d) Never.12_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一Chapter 6 Binary Trees: Instructor's CD questions1.The primary ADT access functions used to traverse a general tree are: a) left child and right siblingb) left child and right child*c) leftmost child and right siblingd) leftmost child and next child2.The tree traversal that makes the least sense for a general treeis:a) preorder traversal*b) inorder traversalc) postorder traversal3.The primary access function used to navigate the general tree when performing UNION/FIND is:a)left childb)leftmost childc)right childd)right sibling*e) parent4.When using the weighted union rule for merging disjoint sets, the maximum depth for any node in a tree of size n will be:a) nearly constant*b) log nc)nd)n log ne)n A25.We use the parent pointer representation for general trees to solve which problem?a)Shortest pathsb)General tree traversal*c) Equivalence classesd) Exact-match query6. When using path compression along with the weighted union rule for merging disjoint sets, the average cost for any UNION or FIND operation in a tree of size n will be:*a) nearly constantb)log nc)nd)n log n13_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一7.The most space efficient representation for general trees will typically be:a) List of children*b) Left-child/right siblingc) A K-ary tree.8.The easiest way to represent a general tree is to:a) convert to a list.*b) convert to a binary tree.c) convert to a graph.9.As K gets bigger, the ratio of internal nodes to leaf nodes:a)) Gets smaller.b)Stays the same.c)Gets bigger.d)Cannot be determined, since it depends on the particular configuration of the tree.10.A sequential tree representation is best used for:*a) Archiving the tree to disk.b)Use in dynamic in-memory applications.c)Encryption algorithms.d)It is never better than a dynamic representation.Chapter 7 Internal Sorting: Instructor's CD questions1.A sorting algorithm is stable if it:a) Works for all inputs.*b) Does not change the relative ordering of records with identical key values.c) Always sorts in the same amount of time (within a constant factor) for a given input size.2.Which sorting algorithm does not have any practical use?a) Insertion sort.*b) Bubble sort.c)Quicksort.d)Radix Sort.e)a and b.3.When sorting n records, Insertion sort has best-case cost:a)O(log n).14_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库*b) O(n).c)O(n log n).e)O(n!)f)None of the above.4.When sorting n records, Insertion sort has worst-case cost:a)O(log n).b)O(n).c)O(n log n).*d) O(n A2)e)O(n!)f)None of the above.5.When sorting n records, Quicksort has worst-case cost:a)O(log n).b)O(n).c)O(n log n).*d) O(n A2)e)O(n!)f)None of the above.6.When sorting n records, Quicksort has average-case cost:a)O(log n).b)O(n).c)) O(n log n).d)O(n A2)e)O(n!)f)None of the above.7.When sorting n records, Mergesort has worst-case cost:a)O(log n).b)O(n).*c) O(n log n).d)O(n A2)e)O(n!)f)None of the above.8.When sorting n records, Radix sort has worst-case cost:a)O(log n).b)O(n).c)O(n log n).d)O(n A2)e)O(n!)15少年易学老难成，一寸光阴不可轻-百度文库*f) None of the above.9.When sorting n records with distinct keys, Radix sort has a lower bound of:a)Omega(log n).b)Omega(n).*c) Omega(n log n).d)Omega(n A2)e)Omega(n!)f)None of the above.10.Any sort that can only swap adjacent records as an average case lower bound of:a)Omega(log n).b)Omega(n).c)Omega(n log n).*d) Omega(n A2)e)Omega(n!)f)None of the above.11.The number of permutations of size n is:a)O(log n).b)O(n).c)O(n log n).d)O(n A2)*e) O(n!)f)None of the above.12.When sorting n records, Selection sort will perform how many swaps in the worst case?a) O(log n).*b) O(n).c)O(n log n).d)O(n A2)e)O(n!)f)None of the above.13.Shellsort takes advantage of the best-case behavior of which sort?*a) Insertion sortb)Bubble sortc)Selection sortd)Shellsorte)Quicksortf)Radix sort16_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库_______________14.A poor result from which step causes the worst-case behavior for Quicksort?*a) Selecting the pivotb)Partitioning the listc)The recursive call15.In the worst case, the very best that a sorting algorithm can do when sorting n records is:a)O(log n).b)O(n).*c) O(n log n).d)O(n A2)e)O(n!)f)None of the above.Chapter 8 File Processing and External Sorting: Instructor's CD questions1.As compared to the time required to access one unit of data frommain memory, accessing one unit of data from disk is:a)10 times faster.b)1000 times faster.c)1,000,000 time faster.d)10 times slower.e)1000 times slower.*f) 1,000,000 times slower.2.The most effective way to reduce the time required by a disk-based program is to:a) Improve the basic operations.*b) Minimize the number of disk accesses.c)Eliminate the recursive calls.d)Reduce main memory use.3.The basic unit of I/O when accessing a disk drive is:a)A byte.*b) A sector.c)A cluster.d)A track.e)An extent.4.The basic unit for disk allocation under DOS or Windows is:a)A byte.b)A sector.*c) A cluster.17少年易学老难成，一寸光阴不可轻-百度文库d) A track.e) An extent.5.The most time-consuming part of a random access to disk is usually: *a) The seek.b)The rotational delay.c)The time for the data to move under the I/O head.6.The simplest and most commonly used buffer pool replacement strategy is:a)First in/First out.b)Least Frequently Used.*c) Least Recently Used.7.The C++ programmer's view of a disk file is most like:a)) An array.b)A list.c)A tree.d)A heap.8.In external sorting, a run is:a)) A sorted sub-section for a list of records.b)One pass through a file being sorted.c)The external sorting process itself.9.The sorting algorithm used as a model for most external sorting algorithms is:a)Insertion sort.b)Quicksort.*c) Mergesort.d) Radix Sort.10.Assume that we wish to sort ten million records each 10 bytes long (for a total file size of 100MB of space). We have working memory of size 1MB, broken into 1024 1K blocks. Using replacement selection and multiway merging, we can expect to sort this file using how many passes through the file?a)About 26 or 27 (that is, log n).b)About 10.c)4.*d) 2.Chapter 9 Searching: Instructor's CD questions18少年易学老难成，一寸光阴不可轻-百度文库1.Which is generally more expensive?a) A successful search.*b) An unsuccessful search.2.When properly implemented, which search method is generally the most efficient for exact-match queries?a)Sequential search.b)Binary search.c)Dictionary search.d)Search in self-organizing lists*e) Hashing3.Self-organizing lists attempt to keep the list sorted by:a) value*b) frequency of record accessc) size of record4.The 80/20 rule indicates that:a) 80% of searches in typical databases are successful and 20% are not.*b) 80% of the searches in typical databases are to 20% of the records.c) 80% of records in typical databases are of value, 20% are not.5.Which of the following is often implemented using a self-organizing list? *a) Buffer pool.b)Linked list.c)Priority queue.6.A hash function must:a)) Return a valid position within the hash table.b)Give equal probability for selecting an slot in the hash table.c)Return an empty slot in the hash table.7.A good hash function will:a)Use the high-order bits of the key value.b)Use the middle bits of the key value.c)Use the low-order bits of the key value.*d) Make use of all bits in the key value.8.A collision resolution technique that places all records directlyinto the hash table is called:a)Open hashing.b)Separate chaining.*c) Closed hashing.d) Probe function.19少年易学老难成，一寸光阴不可轻-百度文库9.Hashing is most appropriate for:a)In-memory applications.b)Disk-based applications.*c) Either in-memory or disk-based applications.10.Hashing is most appropriate for:a)) Range queries.b)Exact-match queries.c)Minimum/maximium value queries.11.In hashing, the operation that will likely require more record accesses is: *a) insertb) deleteChapter 10 Indexing: Instructor's CD questions1.An entry-sequenced file stores records sorted by:a)Primary key value.b)Secondary key value.*c) Order of arrival.d) Frequency of access.2.Indexing is:a) Random access to an array.*b) The process of associating a key with the location of a corresponding data record.c) Using a hash table.3.The primary key is:a)) A unique identifier for a record.b)The main search key used by users of the database.c)The first key in the index.4.Linear indexing is good for all EXCEPT:a)Range queries.b)Exact match queries.*c) Insertion/Deletion.d)In-memory applications.e)Disk-based applications.5.An inverted list provides access to a data record from its:a) Primary key.20______________________________ 少年易学老难成，一寸光阴不可轻-百度文库*b) Secondary key.c) Search key.6.ISAM degrades over time because:a) Delete operations empty out some cylinders.*b) Insert operations cause some cylinders to overflow.c) Searches disrupt the data structure.7.Tree indexing methods are meant to overcome what deficiency in hashing? *a) Inability to handle range queries.。