2017年首都师范大学教育技术系857计算机软件与技术考研仿真模拟题
● 摘要
一、填空题
1． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
2． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
3． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）链表未到尾就一直进行
（2）
将当前结点作为头结点后的第一元素结点插入
4． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
5． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】树。故结点个数为
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
6． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
7． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． 已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）
【答案】
10．对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
二、选择题
11．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
A.4
B.3 C.2 D.1 【答案】B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
12．下列选项中，不会引起指令流水线阻塞的是（ ）。
A. 数据旁路（转发）
B. 数据相关 C. 条件转移 D. 资源冲突 【答案】A
【解析】由于采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：
①结构相关，又称资源相关； ②数据相关；
③控制相关，又称指令相关，主要由转移指令引起。
13．主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）
A .10 Mbps B. 20 Mbps C.80 Mbps D.100 Mbps 【答案】C
【解析】
14．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005, 8006，8007，8008, 8001，8002，8003，8004，8000， 则可能发生发生缓存冲突的地址对是（ ）。
A.8004、8008 B.8002、8007 C.8001、8008 D.8000、8004 【答案】D
【解析】交叉存储器，又称低位交叉编址，即低位地址为体号，高位地址为体内地址。本题中，主存地址对应的体号分别是：1，2，3，4，1，2，3，4，4。地址为8004和8000都是存取的四号储存器，可能导致8004存储还未完成而又存取8000地址，因此可能发生缓存冲突。
15．某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为字节，页表项大小为2字节，逻辑地址结构为：
逻辑地址空间大小为（ ）。
A.64
页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是
相关内容
相关标签