2018年宁夏大学数学计算机学院845C语言程序设计与数据结构考研基础五套测试题
● 摘要
目录
2018年宁夏大学数学计算机学院845C 语言程序设计与数据结构考研基础五套测试题（一） . 2 2018年宁夏大学数学计算机学院845C 语言程序设计与数据结构考研基础五套测试题（二） 16 2018年宁夏大学数学计算机学院845C 语言程序设计与数据结构考研基础五套测试题（三） 30 2018年宁夏大学数学计算机学院845C 语言程序设计与数据结构考研基础五套测试题（四） 45 2018年宁夏大学数学计算机学院845C 语言程序设计与数据结构考研基础五套测试题（五） 59
一、单项选择题
1． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。
A. 存在, 且唯一
B. 存在, 且不唯一不唯一
C. 存在, 可能不唯一
D. 无法确定是否存在
【答案】C 。
【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,
如图的邻接矩阵为, 则存在两个拓扑序列。
2． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。 A.
B.
C.
D. 【答案】D
【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n0，n 1，n 2分别代表度为0，度为1，度为2的结点数) 。又在非空二叉树中:n 0＝n 2＋l ，且本题所给树为正则二叉树，n 1＝0，所以n ＝2*n0﹣l ，因此n 1＝(n+1)/2。
3． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是:假设待排序的记
录存放在数组中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区中适当的位置上。使和，其中:前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
4． 下面关于哈希(Hash，杂凑) 查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，称这个对应关系f 为哈希(Hash)函数，哈希函数的选择要视具体情况而定。
5． 某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1
B.2
C.3
D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。
6． 以下说法错误的是（ ）。
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n ) 的算法
(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
(4)同一个算法，实现语言的级别越高，执行效率就越低
A.(1)
B.(1), (2)
C.(1), (4)
D.(3)
【答案】A
【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
7． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆排序法
【答案】A
【解析】选择排序的基本思想是:
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录
和
8． 为支持
A. 连续结构
B. 链式结构
C. 直接索引结构
D. 多级索引结钩
【答案】A
【解析】为了实现快速随机播放, 要保证最短的查询时间, 即不能选取链表和索引结构, 因此连续结构最优。
9． —个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms
, , 计算20ms ; P2:计算120ms
,
不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。
A.240ms
B.260ms
C.340ms
D.360ms
【答案】B 。
【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2的执行过程, 作业运行的甘特图如下所示, 故答案为B 。 分别变为新的有序区和新的无序区。 中视频文件的快速随机播放, 播放性能最好的文件数据块组织方式是（ ）和，该趟排序，将它与无序区的第1个记录R[i]交换，使操, 计算40ms 若