PDF《问题与练习答案 21》

问题与练习答案

21 2.

当查找J时: 当查找P时: 4. 在每个结点上,每个孩子指针可用来表示字母表中的一个字母.沿着表示一个单词的拼写次 序的指针序列遍历树的路径,就可以表示一个单词.如果一个结点表示的是拼写正确的单词 的结束,那么它就可以用一种特殊的方式进行标记. 8.5 节1. 类型是一个模板;

而这个类型的实例是通过这个模板构建出的一个真实的实体.打个比方, 狗是动物的一类,而Lassie和Rex则是该类型的实例. 2. 用户自定义数据类型是数据组织的一种描述,而抽象数据类型则包括了对数据进行处理 的操作. 3. 这里的问题在于,你是选择用邻接表还是用链表来实现.你的选择会影响到插入新项、删除 旧项以及找到感兴趣的项这些操作过程的结构.然而,该抽象数据类型的实例的用户看不到 这种选择. 4. 这个抽象数据类型至少得包含一个数据结构的描述,用来存储账户余额,以及通过支票存取 款的过程. 8.6 节1. 抽象数据类型和类都是构建类型实例的模板.然而,类更为普遍,这就在于它与继承性相关 procedure PrintTree(Tree) if(Tree的根结点不为NIL) then(对以Tree的左分支出现的树应 用PrintTree过程;

Print Tree的根结点;

对以Tree 的右分支出现的树应用PrintTree过程.) procedure PrintTree(Tree) if(Tree的根结点不为NIL) then(对以Tree的左分支出现的树应 用PrintTree过程;

Print Tree的根结点;

对以Tree 的右分支出现的树应用PrintTree过程.) 当K被打印时,在这里 3.

22 问题与练习答案 联,可以只描述一组过程的集合. 2. 类是模板,通过它来构建对象. 3. 这个类可以包含一个循环队列,以及用于添加项、删除项、测试队列为满和测试队列为空的 这些操作的过程. 8.7 节1. a.A5 b.A5 c.CA 2. D50F,2EFF,5FFE 3. 2EA0,2FB0,2101,20B5,D50E,E50F,5EE1,5FF1,BF14,B008,C000 4. 一个链表的项由两个存储单元组成(一个数据单元,后跟一个指向下一项的指针) ,当遍 历这个链表时,指令形式DR0S能用来读取数据,而指令形式DR1S可用来检索下一项的 指针.如果用指令形式DRTS,那么可以通过修改寄存器T中的值来调整所访问的实际存 储单元. 第9章9.1 节1. 对于库存信息而言,采购部门的兴趣在于存放更多的原材料订单的库存记录,而财务部门则 需要平衡账目的信息. 2. 数据库模型提供了数据库的一种组织观点, 它更切合于应用的角度, 而不是实际组织的角度. 所以,数据库模型的定义是数据库作为抽象工具来使用的第一步. 3. 应用软件把用户的请求从应用的术语翻译成数据库管理系统支持的数据库模型的术语. 数据 库管理系统又把这些请求转化为实际数据库中的操作. 9.2 节1. a.G. Jerry Smith b.Cheryl H. Clark c.S26Z 2. 一种解答是: TEMP ← SELECT from JOB where Dept = PERSONNEL LIST ← PROJECT JobTitle from TEMP 在有些系统中,这会导致表中的职务重复,因其在人事部门出现的次数而异.也就是说,秘 书这个职务可能在我们的表中出现很多次.然而,更为常见的方法就是将PROJECT操作设 计成能把结果关系中重复的元组去掉. 3. 一种解答是: TEMP1 ← JOIN JOB and ASSIGNMENT where JOB.JobId = ASSIGNMENT.JobId TEMP2 ← SELECT from TEMP1 where TermDate = * 问题与练习答案

23 TEMP3 ← JOIN EMPLOYEE and TEMP2 where EMPLOYEE.EmplId = TEMP2.EmplId RESULT ← PROJECT Name,Dept from TEMP3 4. Select JobTitle from JOB where Dept = PERSONNEL Select EMPLOYEE.Name, JOB.Dept from JOB,ASSIGNMENT,and EMPLOYEE where (JOb.Job = ASSIGNMENT.JobId) and (ASSIGNMENT.EmplId = EMPLOYEE.EmplID) and (ASSIGNMENT.TermDate = * ) 5. 模型本身并不提供数据独立性.这是数据库管理系统的一个属性.即使是实际的组织发生了 变化,只要数据管理系统有能力为应用软件提出始终如一的关系组织,那么就能获得数据独 立性. 6. 通过公共属性.例如,本节中的EMPLOYEE关系是通过属性EmplId与关系ASSIGNMENT 相联系的,而关系ASSIGNMENT是通过属性JobId与关系JOB相联系的.像这样的用来连接 关系的属性,有时候称为连接属性. 9.3 节1. 应该有对StartDate和TermDate赋值和检索的方法.另一种方法可能是为报告服务的总时 间而提供. 2. 持久对象就是一个无限期存储的对象. 3. 一种方法就是为库存中的每一类产品建立一个对象. 每个这样的对象能够维护该产品的总库 存量、产品的总成本以及到未交付的产品定单的链接. 4. 正如本节开始所讨论的,就处理复合型数据类型而言,使用面向对象数据库比关系型数据库 要容易得多.而且,事实上,对象可包含在解决问题上起着能动作用的方法,而关系数据只 包含有数据,因而,这就使得面向对象数据库优于关系数据库. 9.4 节1. 事务到达了它的提交点以后, 数据库管理系统就承担起了查看在数据库上执行的完整事务的 责任,而没有达到提交点的事务就没有这样的保证.如果出现了问题,就不得不重新提交. 2. 一种方法就是在某一时刻停止交叉的事务,使得当前所有的事务都能完全完成.这就可以建 立一个点,在这个点后的级联回滚将终止. 3. 如果一次执行一个事务,可以使账户的最终余额为100美元.如果第一个事务是在第二个事 务读取了初始的余额而尚未存入新的余额期间执行的,那么就可以使账户的最终余额为200 美元.如果第二个事务是在第一个事务读取了初始的余额而尚未存入新的余额期间执行的, 那么就可以使账户的最终余额为300美元. 4. a. 如果没有其他事务互斥访问,则准许共享访问. b. 如果另一个事务已经做了某种形式的访问,那么通常数据库管理系统会让新事务等待, 或者将其他的事务回滚而让新事务访问.

24 问题与练习答案 5. 如果两个事务中的每一个都获得了对不同数据项的互斥访问,然后请求访问另一项,那么就 会出现死锁. 6. 通过回滚其中一个事务(利用日志) ,并让另一个事务访问原来被第一个事务占用的数据项, 上述的死锁就能被消除. 9.5 节1. 你应当经过这样一些步骤: 2. 该算法的思想是: 首先将文件进行分割, 存放在许多独立的文件中, 每个文件包含一条记录. 接下来,把这些单记录文件组成对,并对每个对应用归并算法.其结果就使得文件数减半, 而每个文件有两条记录.此外,每个这样的双记录文件是排序过的,我们就能再把这些文件 组成对,并应用归并算法.于是我们就发现,文件数越来越小,而文件越来越大,每个文件 都是排序过的.就这样一直继续下去,我们最终会发现只剩一个文件,且该文件包含所有的 初始记录,但已经排过序了. (如果在这个过程的任意一步中出现了奇数个文件,我们只需 把那个不成对的文件放在一边,在下一步中将其与一个较大的文件配成对. ) 3. 如果文件是存放在磁带或CD上,那么它的实际组织最有可能是顺序的.然而,如果文件是 存放在磁盘上,那么它最有可能是分散在磁盘的不同扇区,这时,文件的顺序特性就是一个 概念属性,并得到指针系统或者是某种形式的表(表中记录着存放文件的扇区)的支持. 4. 首先找到文件索引中的目标键,从那可以得到目标记录的地址.这样就可以在这个地址上读 取记录. 5. 一个选取不恰当的散列算法会比正常情况造成更多的群集,因而也就会出现更多的溢出.因 为海量存储器每个部分的溢出组成了一个链表, 所以对溢出记录的搜索本质上........