当前位置：问答库＞考研试题

一、单项选择题

1． —组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

A.(38，40，46，56，79，84)

B.(40，38，46，79，56，84)

C.(40，38，46，56，79，84)

D.(40，38，46，84，56，79)

【答案】C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较:46比84小，不交换；

第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;

第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;

第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;

第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;

一次划分结束。

2． 下列措施中, 能加快虚实地址转换的是1增大快表(TLB)2让页表常驻内存3增大交换区（ ）

A. 仅1

B. 仅2

C. 仅1, 2

D. 仅2, 3

【答案】C

【解析】加大快表能增加快表的命中率, 即减少了访问内存的次数; 让页表常驻内存能够使cpu 不用访问内存找页表, 从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用, 对虚实地址转换并无影响

3． 在文件的索引节点中存放直接索引指针10个, 一级二级索引指针各1个, 磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中, 到把该文件的偏移量(按字节编址) 为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。

A.1, 2

B.1, 3

C.2, 3

D.2, 4

【答案】B

【解析】文件的索引结点的直接索引指针有10个, 因此直接索引的偏移量范围是0〜2559, 一级索引的偏移量范围是2560〜65791, 二级索引访问的偏移量范围是65792〜45183907。偏移量1234可以通过直接索引得到在磁盘块的地址, 因此需要一次访问, 307400需要通过二级索引查找其在磁盘的位置, 需要分别访问存放二级索引的两个索引块以及对应的数据块。

4． 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）

A. 索引结点的总数

B. 间接地址索引的级数

C. 地址项的个数

D. 文件块大小

【答案】A

【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。

5． 将森林F 转换为对应的二叉树T , F 中叶结点的个数等于（ ）

A.T 中叶结点的个数

B.T 中度为1的结点个数

C.T 中左孩子指针为空的结点个数

D.T 中右孩子指针为空的结点个数

【答案】C

【解析】森林转化为对应的二叉树是„孩子-兄弟‟存储的, 即左孩子指针指向当前节点的孩子节点, 右孩子指针指向当前节点的兄弟节点, 所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C

6． 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。

A. 线性表的顺序存储结构

B. 队列

C. 线性表的链式存储结构

D. 栈

【答案】D

【解析】用栈更合适，如果是左括号，进栈；如果是右括号，看栈顶是不是左括号，如果是，则左括号出栈；否则不配对(可以直接结束算法) 。处理完所有符号号，如果栈为空则配对成功。

7． 归并排序中，归并的趟数是（ ）。

A.O(n) B. C. D.

【答案】B

【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n

。因此每次归并元素的个数増加一倍。所以

。

8． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）.

A.33KB

B.519KB

C.1057KB

D.16513KB

【答案】C

【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B ＝lKB ，一级间接地址索引可以索引256/4＝64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B ＝32KB ，二级间接地址索引为256/4×256/4＝4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B ＝1024KB ，共计1KB ＋32KB ＋1024KB ＝1057KB.

9． 某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ） A. B. C. D.

【答案】A

【解析】IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为

1100 01 10 0100 0000 0000 0000 0000 0000,

转换为标准的格式为:

因此, 浮点数的值为

。 。所以归并的趟数为