2018年西安交通大学研究生院(苏州)814计算机基础综合[专业硕士]之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 假定用若干个是（ ）。
A.0000H B.0600H C.0700H D.0800H 【答案】D
【解析】由若干芯片构成存储器, 采用字和位同时扩展方法。8片组2个芯片, 各组芯片的地址分配分别为:
第1组, 第3组,
; 第2组, ; 第4组,
; 。
位的芯片分成4组, 每
位的芯片组成一个8K ×8位的存储器, 则地址0B1FH 所在芯片的最小地址
地址0BIFH 处于第2组内, 其芯片的最小地址为0800H 。
2． 浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤. 设浮点数的阶码
7
和尾数均采用补码表示，且位数分别为5位和7位(均含2位符号位). 若有两个数X ＝2×29/32，Y
＝2×5/8，则用浮点加法计算X ＋Y 的最终结果是（ ）.
A.001111100010 B.001110100010 C.010000010001 D. 发生溢出
5
【答案】D
【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步.X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐. 因此将Y 对阶后得到：Y ＝2×5/32，然后将尾数相加，得到尾数之和为：34/32.因为这是两
7
个同号数相加，尾数大于1，则需要右规，阶码加1. 由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在之间. 而阶码本身等于7，再加1就等于8. 因此，最终结果发生溢出.
3． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
4． 主机甲和乙已建立了TCP 连接, 甲始终以MSS=1KB大小的段发送数据, 并一直有数据发送; 乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗口为8KB , 则从t 时刻起, 不再发生超时的情况下, 经过10个RTT 后, 甲的发送窗口是（ ）
A.10KB B.12KB C.14KB D.15KB 【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值, 这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的, 取最小值。
5． 文件系统中，文件访问控制信息存储的合理位置是（ ）.
A. 文件控制块 B. 文件分配表 C. 用户口令表 D. 系统注册表 【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息(基本信息、存取控制信息以及使用信息) 都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息.
6． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组B[l...(n(n＋1))/2]中，则在B 中确定a ij (i＜j) 的位置k 的关系为（ ）。
A.i*(i﹣1)/2＋j B.j*(j﹣1)/2＋i C.i*(i＋1)/2＋j D.j*(j＋1)/2＋i 【答案】B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为n(n＋1)/2。对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)
依次存放于一维数组
中，当i ＜j 时，i 与k 的关系为j*(j﹣1)/2＋i 。
7． 在一株高度为2的5阶B 树中, 所含关键字的个数最少是（ ）
A.5 B.7 C.8 D.14
【解析】根据B 树的定义可知, 跟结点最少含有max(2, (m-1))个关键字, 高度为2的阶B 树最少有(5-1)+1=5个关键字, 其中根节点含有(5-1)个关键字, 第2层结点含有1个关键字。
8． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A. B. C. O (n) D. 【答案】A 【解析】在内部排序中，最坏情况下的时间复杂度为
9． 已知有向图G=(V，E) , 其中
G 的拓扑序列是（ ）。 A. B. C. D.
【答案】A 拓扑序列的条件:若在顶
点
。
,
能被称为必须排
【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列
是图中的边(即从顶点。
10．就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D
【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为间复杂度也是注意
仅仅表示的是一个量级，比如
和
的量级都为
到有一条路径) ，则在序列中顶点
之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
，虽然堆排序的时
。之所以说
，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要
快排最好，是在综合考虑的情况下。
二、填空题