2018年杭州电子科技大学数字媒体与艺术设计学院851数据结构考研核心题库
● 摘要
一、判断题
1． 若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）
【答案】×
【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。
2． 数组不适合作为任何二叉树的存储结构。（ ）
【答案】 ×
【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构是高效率的(存储密度大) 。
3． 顺序存储结构的主要缺点是不利于插入或删除操作。（ ）
【答案】 √
【解析】因为顺序表的插入删除会移动大量的元素。
4． 若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
5． 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）
【答案】√
【解析】从哈希表删除一个记录，不是将这个记录的位置置空，而是设置一个标记，标记这个元素是无效的了。
6． 负载因子(装填因子) 是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素:哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
二、单项选择题
7． —组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A.(38，40，46，56，79，84)
B.(40，38，46，79，56，84)
C.(40，38，46，56，79，84)
D.(40，38，46，84，56，79)
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较:46比84小，不交换；
第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;
第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;
第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;
第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;
一次划分结束。
8． 若将关键字1, 2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中, 则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中, 构成的平衡树如下图所示, 由图可知平衡因子为0的分支结点为3个叶子结点, 故答案为D 。
图
9． 主机甲通过1个路由器个路由器(存储转发方式) 与主机乙互联, 两段链路的数据传输速率均为10Mbps , 主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1个大小为8Mb(1M=106)的报文。若忽略链路传播延迟、分组头开销和拆装时间, 则两种交换方式完成该报文传输所需的总时间分别为（ ）
A.800ms>1600ms
B.801ms 、1600ms
C.1600ms 、800ms
D.1600ms 、801ms
【答案】D
【解析】不进行分组时, 发送一个报文的时延是
的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是
总时间为801ms 。
10．程序段
与对换；
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
A.D(n)
B.O(nlogn)
C.O(n3)
D.O(n2)
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行l ＋2＋... ＋n ﹣l 次交换，即时间复杂度是0(n2) 。
11．在支持多线程的系统中, 进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段
B. 进程P 中打开的文件
C. 进程P 的全局变量
D. 进程P 中某线程的栈指针
【答案】D
【解析】现代操作系统中, 进程是资源分配的基本单位, 线程是处理机调度的基本单位。因此, 进程是线程运行的容器, 本题中, 进程的代码段, 进程打开的文件, 进程的全局变量等都是进程的资源, 唯有进程中某线程的栈指针是属于线程的, 那么, 属于进程的资源可以共享, 属于线程的栈是独享的, 不能共享。
, 在接收端接收此报文件, 接收一个报文的时延也是1ms , 但是在发送第二个报文时, 第一个报文已经开始接收。共计有800个分组,