2013南大计算机真题

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.关中断

C.启动I/O指令 D.设置时钟

24、关于微内核操作系统，不正确的描述是（） A.内核态代码规模小 B.文件系统在用户态工作 C.扩展性好 D.系统性能高 25.程序状态字中通常不包括（）

A.中断状态 B.程序计数器 C.数据寄存器 D.进位标志 26.关于中断，不准确的描述是（） A.中断事件来源与执行程序之外 B.中断处理必须按照优先级顺序处理完毕 C．中断处理要在关中断情况下进行 D．中断是可以屏蔽的

27.在进程状态切换时，引起内存与辅存之间交换数据的是（） A.运行到就绪 B.运行到等待 C.运行到挂起 D.就绪到运行 28.无名管道通信方式适合用于（） A.网络通信B.任意用户间通信 C.有关进程间通信D.任意进程间通信

29.静态资源分配策略可防止死锁，因其打破了死锁的必要条件（） A.互斥 B.占有等待 C.不剥夺 D.互斥和不剥夺 30.多级页表的主要目标是（）

A.减少页表所占用内存 B.提高地址转换效率 C.管理更大的物理空间 D.提供更大的逻辑地址空间

31.请求分页虚拟内存管理时，多种因素与缺页中断率有关，但无直接关联的是（）

A.可用内存大小 B.页框大小 C.程序大小 D.替换算法

32、设备驱动程序的主要功能中通常不包括（） A.出错处理 B.启动设备工作 C.设备抽象 D.设备命名

33.以太网100BASE-TX中的100的含义是（） A.100米 B.100M bps C．100站点 D.时延100ms

34、内部路由协议OSPF采用的路由选择算法是（） A.基于Dijkstra最短路径算法的链路状态路由选择算法 B.基于Dijkstra最短路径算法的距离矢量路由选择算法 C.基于Bellman-Ford最短路径算法的链路状态路由选择算法 D.基于Bellman-Ford最短路径算法的距离矢量路由选择算法 35、以下关于OSI参考模型的描述中，说法错误的是（） A.OSI参考模型定义了开放系统的层次结构 B.OSI参考模型定义了各层所包括的可能的服务 C.OSI参考模型作为一个框架协调组织各层协议的制定 D.OSI参考模型定义了各层接口的实现方法 36.下列IP地址中，分配给主机的A类地址是（） A.126.255.255.255 B.126.0.0.0

C.126.0.0.1 D.128.0.0.1

37、802.11标准定义的分布协调功能所包含的几种帧间间隔中，一般逐级竞争使用信道（）

A.SIFS和PIFS B.SIFS和DIFS C.DIFS D.DIFS和PIFS

38、下列关于TCP滑动窗口机制的叙述中，正确的是（） A.表示滑动窗口大小的字段包含3位 B.滑动窗口大小在TCP连接过程中不再调整 C.滑动窗口仅用于端到端的流量控制 D.滑动窗口大小为0是合法的

39、在一个主机域名http://bbs.nju.edu.cn中，表示主机名的是（） A.http B.bbs C.nju D.cn 40.下图中，“？”处应填入的值是（） A.1 B.i+1 C.jD.j+1

41、（11分）请将下面的序列进行堆排序方法进行排序，给出每一步的步骤。说明堆排序的时间复杂度。

42、（12分）已知二叉树的存储形式是静态二叉链表，如下图所示。试编写算法在二叉树的静态二叉链表存储结构上对二叉树进行前序遍历。要求采用非递归的算法，描述算法的基本设计思想，采用程序设计语言描述算法（C,C++,JAVA语言中的一种实现），关键之处请给出注释，静态二叉链表如图所示：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2013南大计算机真题在线全文阅读。