二叉树中 计算机考研408真题及答案(5)

栈的特点是先进后出。队列的特点是先进先出。树的特点是 节点的前驱只能有一个的数据结构。 图是最复杂的数据结构， 它是前驱和后继都可以有多个 的网状结构。 2.元素 abcdefg 依次进入栈，bdcfeag 依次出队，那么他们在栈中操作顺序依次为：a 入栈、 b 入栈、b 出栈、c 入栈、d 入栈、d 出栈、c 出栈、e 入栈、f 入栈、f 出栈、e 出栈、a 出 栈、g 入栈、g 出栈。这其间栈中数据最多有 3 个。 3.一看第一个遍历出来的元素是 3，所以后序遍历 4.平衡二叉树，又称 AVL 树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子 树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过 1.。5. 第 6 层有 8 个叶节点，说明这个完全二叉树最多共 7 层，所以树的节点数为： 1+2+4+8+16+32+48=111。 8. B 树是一种多叉平衡查找树。一棵 m 阶的 B 树，或为空树，或为满足下列特性的 m 叉树： ①树中每个结点至多有 m 棵子树； ②若根结点不是叶子结点，则它至少有两棵子树； ③除根之外的所有非叶子结点至少有「m/2]棵子树； ④所有的非叶子结点中包含卞列数据信息 (n，A0，K1，A1，K2，A2，?，Kn，An) 其中：Ki(i=1，2，?，n)为关键字，且 Ki<Ki+1(i=1，2，?，n-1)：Ai(i=0，1，?， n) ⑤所有的叶子结点都出现在同一层次上，并且不带信息(可以看作县外部结点或查找失 败的结点，实际上这些结点不存在，指向这些结点的指针为空)。

9.堆调整算法的应用 10.解此题必须熟知各种排序方法的步骤。 11.考察 CPU 区分指令和数据的方法：取指令和取数据发生在指令的不同阶段。 13.熟悉浮点运算过程 14.熟悉组相联映射的方式。组相联的映象规则： (1) 主存和 Cache 按同样大小划分成块。 (2) 主存和 Cache 按同样大小划分成组。 (3) 主存容量是缓存容量的整数倍， 将主存空间按缓冲区的大小分成区， 主存中每一区 的组数与缓存的组数相同。二叉树中 (4) 当主存的数据调入缓存时， 主存与缓存的组号应相等， 也就是各区中的某一块只能 存入缓存的同组号的空间内， 但组内各块地址之间则可以任意存放， 即从主存的组到 Cache 的组之间采用直接映象方式；在两个对应的组内部采用全相联映象方式。 15.需要 ROM 片数：4K*8/2K*8=2，需要 RAM 片数：60K*8/4K*4=30. 16.相对寻址： 以当前程序计数器 pc 的内容为基址， 加上指令给出的一字节补码数 （偏移量） 形成新的 pc 值的寻址方式称为相对寻址。 17.精简指令集的特点： 统一指令编码(例如， 所有指令中的 op-code 永远位于同样的位位置、 等长指令)，可快速解译； 泛用的缓存器，所有缓存器可用于所有内容，以及编译器设计的单纯化(不过缓存器中 区分了整数和浮点数)； 单纯的寻址模式(复杂寻址模式以简单计算指令序列取代)； 硬件中支持少数数据型别(例如， 一些 CISC 计算机中存有处理字节字符串的指令。

这在 RISC 计算机中不太可能出现)。 RISC 设计上同时也有哈佛内存模块特色，凡指令流和数据流在概念上分开；这意味着更改 代码存在的内存地址对处理器执行过的指令没有影响（因为 CPU 有着独立的指令和数据缓 存） ，至少在特殊的同步指令发出前。在另一面，这允许指令缓存和数据缓存同时被访问， 通常能改进运行效率。 18.时钟周期以最大的流水段为准 19. 硬布线控制器是早期设计计算机的一种方法。 硬布线控制器是将控制部件做成产生专门 固定时序控制信号的逻辑电路，产生各种控制信号，因而又称为组合逻辑控制器。这种逻辑 电路以使用最少元件和取得最高操作速度为设计目标， 因为该逻辑电路由门电路和触发器构 成的复杂树型网络，所以称为硬布线控制器。 微程序控制的基本思想， 就是仿照通常的解题程序的方法， 把操作控制信号编成所谓的“微指令”，存放到一个只读存储器里．当机器运行时，一条又一条地读出这些微指令，从而产 生全机所需要的各种操作控制信号，使相应部件执行所规定的操作 20.10M/2*4=20MB/S 21.(1000-50)/1000=95% 25.K 的最小值是 4，当 K 为 4 是，每个进程若占用 2 台打印机，则发生死锁。