2018年扬州大学信息工程学院858程序设计与数据结构之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关
【答案】A
【解析】邻接表就是对图G 中的每个顶点建立一个单链表，第i 个单链表中的结点表示依附于顶点的边，这个单链表就称为顶点的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
2． 下列程常段的时间复杂度是（ ）
A.O()
B.O(n) C.O() D.O()
【答案】C
【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行
内部循环的退出条件是j>n, 对于j , 每次循环都执行, 所以循环次数为; , 所以每次循环次数为n 次。所以此程序
) , 即选C 。 段的时间复杂度为O(
3． 设有数组A[i，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。
A.BA+141
B.BA+180
C.BA+222
D.BA+225
【答案】B
【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储
首地址为BA ＋(61﹣1)*3＝180+BA。
4． 若磁盘转速为7200转/分, 平均寻道时间为8ms , 每个磁道包含1000个扇区, 则访问一个扇区的平均存取时间大约是（ ）。 A. B. C. D.
【答案】B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关, 为
。
磁盘的存取一个扇区的时间为
因此总的时间为:
。
5． 对矩阵压缩存储是为了（ ）。
A. 方便运算
B. 方便存储
C. 提高运算速度
D. 减少存储空间
【答案】D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
6． 用直接插入排序方法对下面4个序列进行排序(由小到大) ，元素比较次数最少的是（ ）。
A.94，32，40，90，80，46，21，69
B.32，40，21，46，69，94，90，80
C.21，32，46，40，80，69，90，94
D.90，69，80，46，21，32，94，40
【答案】C
7． 文件系统中，文件访问控制信息存储的合理位置是（ ）.
A. 文件控制块
B. 文件分配表
C. 用户口令表
D. 系统注册表
【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息(基本信息、存取控制信息以及使用信息) 都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息.
8． 在一棵具有15个关键字的4阶B 树中, 含关键字的结点数最多是（ ）
A.5 B.6 C.10 D.15
【答案】D
【解析】M 阶B 树非根结点含关键字个数。
4阶B 树非根结点含关键字1~3个, 所以要使关键字结点数量最多, 那么每个结点只有一个关键字, 一共有15个关键字那么最多有15个含有关键字的结点
9． 假设某计算机的存储系统由Cache 和主存组成. 某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.
A.5% B.
C.50%
D.95%
【答案】D
【解析】Cache 的命中率H ＝N 1(N1＋N 2) ，其中N 1为访问Cache 的次数，N 2为访存主存的次数，程序总访存次数为N 1＋N 2，程序访存次数减去失效次数就是访问Cache 的次数队. 所以根据公式可得：H ＝(1000﹣50) /100＝95%.
10． 基于比较方法的n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（ ）。
A. B.
C. O (n) D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为。
11．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4
B.5
C.6
D.7
【答案】C
【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所
相关内容
相关标签