一﹑单项选择题：1~40小题，每小题2分，共80分。在每小题给出的四个选项

中，请选出一项最符合题目要求的。

1 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用______存储方式最节省时间。

A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表

2 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i(1<=i<=n)个元素是______。< p="">

A.不确定 B.n-i+1 C.i D.n-i

3 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( )。

A.13 B.33 C.18 D.40

4 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )。

A.M1 B.M1+M2 C.M3 D.M2+M3

5 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为( )。

A.n-1 B.?n/m?-1 C.é(n-1)/(m-1)ù

D. én/(m-1)ù-1 E.é(n+1)/(m+1)ù-1

6 用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为( )。

A.5 B.6 C.8 D.9

7 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

A.O(n) B.O(n+e) C.O(n*n) D.O(n*n*n)

8 当采用分快查找时，数据的组织方式为 ( )

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块

C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块

D.数据分成若干块，每块(除最后一块外)中数据个数需相同

9 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。

A.快速排序 B.堆排序 C.归并排序 D.直接插入排序

10 在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在( )位置上。

A.?n/2? B.?n/2? -1 C.1 D.?n/2? +2

11 硬件和软件实现在逻辑功能上是一样的，但硬件的优势在于_______。

A.速度快 B.成本低

C.容量大 D.灵活性好

12 数据发生溢出的根本原因是_______。

A.数据的位数有限

B.数据运算中将符号位的进位丢弃

C.数据运算中将符号位的借位丢弃

D.数据运算中的错误

13 在页式虚拟存储器中，为了提高主存的命中率，可以采取的措施是______。

A.增大主存容量 B.增大辅存容量

C.增大Cache容量 D.将LRU替换算法改为FIFO

14 下列关于存储器的描述，正确的是______。

A.CPU访问时间由存储器容量决定

B.ROM和RAM在存储器中是统一编址的

C.ROM中任一单元可随机访问

D.DRAM是破坏性读出，因此需要读后重写