2018年杭州师范大学阿里巴巴商学院826计算机基础之数据结构考研核心题库
● 摘要
一、单项选择题
1． 以下说法错误的是（ ）。
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n ) 的算法
(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
(4)同一个算法，实现语言的级别越高，执行效率就越低
A.(1)
B.(1), (2)
C.(1), (4)
D.(3)
【答案】A
【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
2． 下列关于USB 总线特性的描述中, 错误的是（ ）。
A. 可实现外设的即插即用和热插拔
B. 可通过级联方式连接多台外设
C. 是一种通信总线, 可连接不同外设
D. 同时可传输2位数据, 数据传输率高
【答案】D 。
【解析】USB 总线即通用串行总线, 它的特点有:
(1)即插即用; (2)热插拔; (3)有很强的链接能力能将所有外设链接起来, 且不损失带宽;
(4)有很好的可扩展性; (5)高速传输, 速度可达480Mbps 。
所有A , B , C 都符合USB 总线的特点。对于选项D , USB 是串行总线, 不能同时传输两位数据, 所以答案为D 。
3． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。
深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得。对应的平衡二叉树如下图所示。
表示
4． 下列措施中, 能加快虚实地址转换的是1增大快表(TLB)2让页表常驻内存3增大交换区（ ）
A. 仅1
B. 仅2
C. 仅1, 2
D. 仅2, 3
【答案】C
【解析】加大快表能增加快表的命中率, 即减少了访问内存的次数; 让页表常驻内存能够使cpu 不用访问内存找页表, 从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用, 对虚实地址转换并无影响
5． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5
B.2和4
C.4和2
D.5和1
【答案】B
【解析】入队操作的主要步骤:rear ＝(rear+1)%6，加入一个后，rear ＝(0+1)%6＝1，再加入一个后，rear ＝(1+1)%6＝2。出队操作的主要步骤:front ＝(front+1)%6。删除一个后，front ＝(3+1)%6＝4。
6． 广义表A ＝(a，b ，(c，d) ，(e，(f，g))) ， 则式子Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
A.(g)
B.(d)
C.c
D.d
【答案】D
【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。也就是tail 得到的元素需要在外层再加一个（ ）。
7． 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
8． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）
A.007.110.119.114.911.120.122
B.007, 110, 119, 114, 911, 122, 120
C.007, 110, 911, 114, 119, 120, 122
D.110, 120, 911, 122, 114, 007, 119
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。
9． 排序过程中, 对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中, 每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ. 简单选择排序
Ⅱ. 希尔排序
Ⅲ. 快速排序
Ⅳ. 堆排
Ⅴ. 二路归并排序
A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
【答案】A 。
【解析】其中简单选择排序、堆排序属于选择类排序, 每一趟排序结束时将确定最大(或最小) 关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路
相关内容
相关标签