2013南大计算机真题 科目代码：845 满分：150
一、 单选（40题，每题2分，共80分） 1、下面关于线性表的叙述中，不正确的是（）
I线性表在链式存储时，查找第i个元素的时间同i的值成正比 II线性表在链式存储时，查找第i个元素的时间同i的值无关 III线性表在顺序存储时，查找第i个元素的时间同i的值成正比 IV线性表在顺序存储时，查找第i个元素的时间同i的值无关 A. I,II B.II,III C.III,IV D.I,IV
2、对n个关键码进行直接选择排序，在原关键码已经有序的情况下，关键码的比较次数为（）
A.n B.n-1 C.n(n-1)/2 D.n(n-1) 3、引入二叉线索树的目的是（） A.加快查找结点的前驱和后继的进度 B.为了能在二叉树中方便地进行插入与删除 C.为了能方便地找到双亲 D.使二叉树的遍历结果唯一
4、可以判断出一个有向图是否有环（回路）的方法是（） A.深度优先遍历 B.广度优先遍历 C.求最短路径 D.拓扑排序
5、在哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（） A.n-1 B.n+1 C.2n-1 D.2n+1
6、下面关于广义表的说法中，不正确的是（） A.广义表的表头总是一个原子 B.广义表的表尾总是一个广义表 C.广义表适宜用链表存储结构 D.广义表可以是一个多层次的结构
7、具有n个关键字的有序表，折半查找的平均查找长度为（） A.O(n) B.O(n*n) C.O(log2 n) D.O(nlog2 n)
8、哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行的探测次数为（） A. k-1 B.k C.k+1 D.k（k+1）/2
9、数组A[0..6，0..9]的每个元素占2个字节，将其按列优先次序存储在起始地址为100的内存单元中，则元素A[7，8]的地址是（） A.210 B.226 C.234 D.256
10、一棵具有125个结点的完全二叉树的树高度（空树的高度为0）是（）
A.5 B.6 C.7 D.8
11、下面关于m阶B树说法中，正确的是（） I每个结点至少有两棵非空子树 II树中每个结点至多有m-1个关键字 III所有叶子在同一层
IV当插入一个数据项引起B树结点分裂后，树长高一层 A.I,II,III B.II,III C.II,III,IV D.I,IV
12、某程序P由一个100条指令构成的循环程序段组成，该循环程序段共被执行200次，在计算机M中执行程序P用了40 000个时钟周期，M的主频为500MHz，则M在执行程序P时的MIPS数是（） A.0.5 B.2 C.250 D.1000
13、已知float型变量采用IEEE 754单精度浮点标准表示。若x，y为float类型，且x=126，y=15.75，则执行赋值语句“z=x+y；”，在浮点运算部件中进行对阶操作后的结果是（） A.x不变，y为0 1000 0101，0.0011 1111 0?0 B.x不变，y为0 1000 0110，0.0011 1111 0?0 C.y不变，x为1 1000 0101，0.0011 1111 0?0 D.y不变，x为1 1000 0110，0.0011 1111 0?0
14、已知char型变量x和y的补码表示分别为[x]补=EFH，[y]补=FEH,则x-y的值以及相应的溢出标志（OF）分别是（） A.-15，0 B.15，0 C.-15，1 D.15，1
15、假定变量i，f的数据类型分别是int，float。已知i=54321，f=5.4321e3，则在一个32位机器中执行下列表达式时，结果为假的是
A.i==(int)(float)i B.f==(float)(int)f C.i==(float)(double)i D.f==(float)(double)f
16、假定页表中有一个控制位C，用来表示对应页面是否可在Cache缓存。C=1表示可在Cache缓存，C=0表示不能在Cache缓存。以下是关于虚实地址转换时对控制位C进行相关处理的描述，其中错误的
是（）
A.若装入位（Valid）为0，则无需考虑C的取值如何 B.若修改位（Dirty）为1，则不管原来C为何值都将其清0 C.若C=0，则根据转换后的地址直接访问主存而不访问Cache D.若C=1，则根据转换后的地址先到Cache中进行访问
17、机器M1和M2具有完全相同的指令集体系结构（ISA），某程序均匀涵盖了所有指令，P在M1上的运行四件比在M2上快30秒。针对上述情况，以下叙述中，错误的是（） A.M1和M2的时钟频率以及CPI都可能不同 B.在M1和M2上所采用的Cache实现方式可能不同 C.同一条指令在M1和M2上的实现方式可能不同 D.M1和M2的通用寄存器个数及位数都可能不同 18、以下有关程序计数器PC的叙述中，正确的是（） A.每条指令执行后，PC的值都会变得更大 B.指令顺序执行时，PC的值总是自动加1 C.返回指令执行后，PC中一定是返回地址 D.条件转移指令执行后，PC中一定是转移目标地址
19、若设计一台机器，要求机器字长32位，按字编址，主存地址空间大小为2GB，指令长度为32位，则PC的位数个数是（） A.29 B.30 C.31 D.32
20、某机器采用双字节定长指令字，ZF,OF,CF,SF分别是零标志、溢出标志、进位/借位标志和符号标志。下图给出的是某条指令相关的
部分数据通路，该指令是（）
A.带符号整数大于转移指令（jg） B.带符号整数大于等于转移指令（jge） C.无符号数大于转移指令（jug） D.无符号数大于等于转移指令（juge）
21、假定连接主存和磁盘的总线带宽是110MB/s,磁盘最大数据传输率是4MB/s，若磁盘输入/输出占用50%的总线带宽，则总线上可同时接入的磁盘个数最多是（） A.13 B.15 C.27 D.29
22、以下操作中，由中断隐指令完成的是（） A.设置中断屏蔽字 B.保护中断屏蔽字 C.保护通用寄存器（现场） D．保护返回地址（断点）
23、下列指令中，在用户态执行的是（） A.访管指令 B.关中断