2018年广东工业大学计算机学院831数据结构与C语言[专业硕士]之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156
【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。
2． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，起泡排序
【答案】D
3． 为支持
A. 连续结构
B. 链式结构
C. 直接索引结构
D. 多级索引结钩
【答案】A
【解析】为了实现快速随机播放, 要保证最短的查询时间, 即不能选取链表和索引结构, 因此连续结构最优。
4．
参考模型的网络层提供的是（ ）。
A. 无连接不可靠的数据报服务
B. 无连接可靠的数据报服务
C. 有连接不可靠的虚电路服务
D. 有连接可靠的虚电路服务
第 2 页，共 44 页 中视频文件的快速随机播放, 播放性能最好的文件数据块组织方式是（ ）
【答案】A
【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。
5． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，A[0][0]存放于B[0]中，那么第i 行的对角元素A[i][i]存放于B 中（ ）处。
A.(i＋3)*i/2
B.(i＋1)*i/2
C.(2n﹣i ＋l)*i/2
D.(2n﹣i ﹣l)*i/2
【答案】A
【解析】A[i][i]中列标不大于行标，又A[0][0]存放在B[0]中，所以A[i][i]存放的位置为i*(i＋l)/2＋i ＋l ﹣l ＝i*(i＋3)/2。
6． 某计算机的Cache 共有16块，采用2路组相联映射方式(即每组2块). 每个主存块大小为32字节，按字节编址. 主存129号单元所在主存块应装入到的Cache 组号是（ ）.
A.0
B.2
C.4
D.6
【答案】C
【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K ＝ImodQ(K代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数) 来计算Cache 的组号. 由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4，Cache 共有16块，采用2路组相联映射方式(即每组2块) ，故Cache 有8组，按照上面的公式可以计算得到Cache 的组号＝4mod8＝4.
7． 下列二叉排序树中，满足平衡二叉树定义的是（ ）. A. B.
第 3 页，共 44 页
C. D.
【答案】B
【解析】平衡二叉树是指左右子树高度差(平衡因子) 的绝对值不超过1的二叉树.A 项中根结
B 项中每个结点的平衡因子的绝对值均不超过1；C 项中根结点的平衡因子是；点的平衡因子是2；
D 项中根结点的平衡因子是3.
8． 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
9． 设二维数组(即m 行n 列) 按行存储在数组
A[i，j]在一维数组B 中的下标为（ ）。
A.(i﹣1)*n＋j
B.(i﹣1)*n＋j ﹣l
C.i*(j﹣1)
D.j*m＋i ﹣l
【答案】A
【解析】前i ﹣1的元素个数为(i﹣1)*n，所以二维数组元素A[i，j]在一维数组B 中的下标为(i﹣1)*n＋j 。需要注意数组B 的下标是从0开始，还是从1开始。
第 4 页，共 44 页 中，则二维数组元素