2018年湘潭大学信息工程学院870数据结构(二)[专业硕士]考研仿真模拟五套题
● 摘要
目录
2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研仿真模拟五套题（一） .... 2
2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研仿真模拟五套题（二） .. 13
2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研仿真模拟五套题（三） .. 25
2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研仿真模拟五套题（四） .. 36
2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研仿真模拟五套题（五） .. 46
一、填空题
1． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】；边稀疏
2． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
3． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树
【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
4． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
5． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
6． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
二、单项选择题
7． 在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps ，分组大小为1000B ，其中分组头大小20B ，若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）
.
A.80ms B.
C.
D.
【答案】c
【解析】由题设可知，分组携带的数据长度为980B ，文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B ，总共需要传送的数据量大小为IMB. 由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机. 当t ＝lM ×8/100Mbps＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t 0＝lK ×8/100Mbps＝，所以，在不考虑分组拆装时间和传播延时的情况下，当时，H2接受完文件，
即所需的时间至少为
8． 下列选项中, 会导致用户进程从态切换到内核的操作是（ ）
Ⅰ. 整数除以零
Ⅱ.sin （ ）函数调用
Ⅲ.read 系统调用
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。
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．由3个“1”和5个“0”组成的8位二进制补码, 能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
D.-3
【答案】B
【解析】能表示的最小整数一定是负数, 符号位占用1个“1”; 负数的补码和原码的转化是:原码符号位不变, 数值部分按位取反, 末位加“1”。
因此最小的整数的补码是“10000011”, 原码为“111111101”, 即
11．希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
【答案】A
【解析】希尔排序基本思想是:先将整个待排元素序列按某个增量分割成若干个子序列, 在子序列内进行直接插入排序, 然后依次缩减增量再进行排序, 待整个序列中的元素基本有序(增量足够小) 时, 再对全体元素进行一次直接插入排序。
12．某计算机有五级中断, 中断屏蔽字为屏蔽。若中断响应优先级从高到低的顺序是
的顺序为
A.11110 , 则。 表示对级中断进行
, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。
相关内容
相关标签