2018年北京交通大学计算机与信息技术学院925数据结构考研仿真模拟五套题
● 摘要
一、判断题
1． 折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ）
【答案】×
【解析】不是，当二元查找树是一棵单支树时，时间性能是O(n)。而折半查找依然是
2． 如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。
3． 在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）
【答案】 ×
【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。
4． 栈和队列都是限制存取点的线性结构。（ ）
【答案】 √
5． 任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】 ×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
6． 一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的
【答案】 √
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为
个结点在第k 层的任一位置上。（ ）
二、单项选择题
7． 某计算机的控制器采用微程序控制方式, 微指令中的操作控制字段采用字段直接编码法, 共有33个微命令, 构成5个互斥类, 分别包含7、3、12、5和6个微命令, 则操作控制字段至少有 （ ）。
A.5位
B.6位
C.15位
D.33位
【答案】C 。
33个微命令分成5个互斥类(即5个字段) , 根据每个类中微命令的多少可以分别确定【解析】
字段的长度为3、2、4、3、3位, 又因为采用直接编码方式, 所以它们之和也就是操作控制字段的位数。
8． —组记录的关键码为(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) ;
一次划分结束。
9． 下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
【答案】D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写, 只有选项D 中的英文缩写均为总线标准。
10．下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C. D.
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
11．一个具有1025个结点的二叉树的高h 为（ ）。
A.11
B.10
C.11至1025之间
D.10至1024之间
【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
12．图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
【答案】A
【解析】顶点到顶点之间的一条路径是指顶点序列。路径上边的数目称为路径的长度。
13．求整数阶乘的算法如下, 其时间复杂度是（ ）。
A.
B.0(n) C. 2D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。