2017年中国传媒大学脑科学与智能媒体研究院821数据结构与计算机网络考研题库
● 摘要
目录
2017年中国传媒大学脑科学与智能媒体研究院821数据结构与计算机网络考研题库（一）.... 2
2017年中国传媒大学脑科学与智能媒体研究院821数据结构与计算机网络考研题库（二）.. 14
2017年中国传媒大学脑科学与智能媒体研究院821数据结构与计算机网络考研题库（三）.. 28
2017年中国传媒大学脑科学与智能媒体研究院821数据结构与计算机网络考研题库（四）.. 39
2017年中国传媒大学脑科学与智能媒体研究院821数据结构与计算机网络考研题库（五）.. 50
一、填空题
1． 二进制地址为011011110000，大小为【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为式如下：
当大小为4时，起始地址
为当大小为16时，起始地址为
：
2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
3． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
4． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
5． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
和其伙伴块的起始地址计算公和块的伙伴地址分别为：_____
6． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为
7． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
8． 设数组
储，则元素
为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
9． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
10．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
11．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
12．一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
二、选择题
13．某计算机使用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地址，因此可能发生缓存冲突。
14．某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）
A.5
B.6
C.8
D.9
【答案】C 【解析】所以至少需要8位才能表示完130个地址。
15．一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
16．若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有
由此可得对应的平衡二叉树如下图所示。
相关内容
相关标签