2018年福建师范大学数学与计算机科学学院841计算机专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 循环队列A[0..m﹣1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。
A.(rear﹣front ＋m)%m
B.rear ﹣front ＋1
C.rear ﹣front ﹣1
D.rear ﹣front
【答案】A
【解析】对于循环队列，需要深刻理解队头(font)和队尾(rear)的概念，在队头进行出队操作，在队尾进行进队操作。rear-front 可能为正也可能为负，为正时元素个数＝(rear-front)；如果为负则元素的个数＝(rear-front+m)，所以统一的公式就是(rear-front+m)%m。
2． 下列存储器中, 在工作期间需要周期性刷新的是（ ）。
A.SRAM
B.SDRAM
C.ROM
D.FLASH
【答案】B
【解析】动态随机存储器(DRAM)是利用存储元电路中栅极电容上的电荷来存储信息的, 电容
上的电荷一般只能维持, 因此即使电源不掉电, 信息也会自动消失。为此, 每隔一定时间必须刷新。
3． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C. D.
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
4． 由3个“1”和5个“0”组成的8位二进制补码, 能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
D.-3
【答案】B
【解析】能表示的最小整数一定是负数, 符号位占用1个“1”; 负数的补码和原码的转化是:原码符号位不变, 数值部分按位取反, 末位加“1”。
因此最小的整数的补码是“10000011”, 原码为“111111101”, 即。
5． 某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1
B.2
C.3
D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。
6． 分区分配内存管理方式的主要保护措施是（ ）.
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护. 通常的界地址保护方法采用软硬件结合的方法. 考生要注意本题与虚拟存储方法的区别.
7． 数组中含有元素的个数（ ）。
A.55
B.45
C.36
D.16
【答案】B
【解析】该数组为三维数组。其个数为5*3*3＝45。
8． 下列介质访问控制方法中, 可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDMAC
D.FDMA
【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议, 答案为B 。
9． 下列四个序列中，哪一个是堆（ ）?
A.75，65，30，15，25，45，20，10
B.75，65，45，10，30，25，20，15
C.75，45，65，30，15，25，20，10
D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义:
n 个关键字序列
①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
根据堆定义即可得出答案。
10．n 个顶点的无向图的邻接表最多有（ ）个表结点。
A.n 2
B.n(n－1)
C.n(n+1) D.
【答案】B
【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n －1个结点连接，从而会产生n(n－1) 个表结点。
二、算法应用题
11．设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。
【答案】n 个元素采用起泡排序法进行排序，通常需要进行n －1趟排序。第j 趟起泡排序要进行n －j 次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记flag 的使用。
用作控制标记
是起泡排序趟数，最多n －1趟
设标记，若本趟不发生交换，本趟起泡排序后，算法结束
相关内容
相关标签