2016年西南大学柑桔研究所数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。
A.245Mbps
B.979Mbps C. D.
答:D
【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到的时间用来刷新
1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：
2． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
答:D
【解析】至少探测次数
3． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7
B.-8
C.15
D.16
答:C
【解析】Hanoi 问题总移动次数为：次。
4． 假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。
A.146k
B.147K
C.148K
D.158K
答:B
【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K
个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容
=147K。 量为：
5． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。
A.lOMB/s
B.20MB/S
C.40MB/S
D.80MB/S
答:B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4
=20MB/s。 字节信息, 则总线带宽是4B ÷
6． 有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156
答:C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。
7． float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。 A. B. C. D.
答:D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：S 为符号位，E 的取值为
f 为23位；故float 类型能表示的最大整数是
8． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
答:D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
9． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。
A. 分块
B. 顺序
C. 折半
D. 哈希
答:A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
10．下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
答:D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写，只有选项D 中的英文缩写均为总线标准。
二、填空题
11．建立索引文件的目的是_____。
答:提高查找速度
12．已知二维数组
为1000的连续存储区域时，
答:1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
13．栈是_____的线性表，其运算遵循_____的原则。
；后进先出 答:操作受限（或限定仅在表尾进行插入和删除操作）
中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。
相关内容
相关标签