2018年电子科技大学自动化工程学院820计算机专业基础之数据结构考研核心题库
● 摘要
目录
2018年电子科技大学自动化工程学院820计算机专业基础之数据结构考研核心题库（一） ... 2 2018年电子科技大学自动化工程学院820计算机专业基础之数据结构考研核心题库（二） . 12 2018年电子科技大学自动化工程学院820计算机专业基础之数据结构考研核心题库（三） . 21 2018年电子科技大学自动化工程学院820计算机专业基础之数据结构考研核心题库（四） . 30 2018年电子科技大学自动化工程学院820计算机专业基础之数据结构考研核心题库（五） . 39
第 1 页，共 47 页
一、填空题
1． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树
【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
2． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
:_____:
{_____)
(_____、
:_____；_____；p ＝u ；
【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中
(2)p!＝NULL //当链表尚未到尾，p 为工作指针
(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针
(4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中
(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针
3． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为
其中:left 指向其左孩子，left 指向其前驱；，
第 2 页，共 47 页 ， right 指向其右孩子，，，
right 指向其后继。
【答案】
4． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
5． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
二、单项选择题
6． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A. B.
C. O (n) D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为
7． 在下面的排序方法中，辅助空间为O(n)的是（ ）。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
【答案】D
第 3 页，共 47 页 。
8． 有关二叉树下列说法正确的是（ ）。
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
【答案】B
【解析】树的度＝MAX(结点1的度，结点2的度，结点3的度结点n 的度) 。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
9． 某主机的IP 地址为, 子网掩码为。若该主机向其所在子网发送广播分组, 则目的地址可以是（ ）。 A. B. C. D.
【答案】D 。
【解析IPv4地址中的特殊地址, 直接广播地址, 也就是把主机位全部设置为1, 这里77的二进制是01001101, 子网掩码252的二进制是11111100, 由此可以看到77的前6位作为子网位, 后四位作为主机位, 由此可以知道其广播地址是
10．下列关于虚拟存储的叙述中, 正确的是（ ）。
A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制
【答案】D 。
【解析】所谓虚拟存储, 是指运行的进程不必全部装入内存, 只需要部分装入便可以开始运行的一种技术, 在运行过程中, 当所需要的代码部分不在内存时, 通过一种技术(例如缺页中断技术) , 将所需要的页面调入内存, 从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配, 虚拟存储器和外存大小没有关系, 所以选项中的A , B , C 都是错误的, 所以答案是D 项。
11．某系统有n 台互斥使用的同类设备, 3个并发进程需要3, 4, 5台设备, 可确保系统不发生死锁的设备数n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B
第 4 页，共 47 页 , 也就是, 因此答案是D 。
相关内容
相关标签