2016年赣南师范学院数学计算机科学学院、脐橙学院数据结构(同等学力加试)考研复试题库
● 摘要
一、选择题
1． 程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）
A.8.4 秒
B.11.7 秒
C.14 秒
D.16.8 秒
答:D 【解析】
2． 设有向图 G= （V ，E ），顶点集V={V0, VI ，V2, V3}，边
集而
若从顶点V0开始对图进行深度优先遍历，则可
能得到的不同遍历序列个数是（ ）。
A.2
B.3
C.4
D.5
答:D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可
3． 下列存储器中，在工作期间需要周期性刷新的是（ ）。
A.SRAM
B.SDRAM
C.ROM
D.FLASH
答:B
【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持因此即使电源不掉电，信息也会自动消失。为此，每隔一定时
第 2 页，共 48 页 能得到的不同遍历序列分别是
：
间必须刷新。
4． 下列选项中，能引起外部中断的事件是（ ）。
A. 键盘输入
B. 除数为0
C. 浮点运算下溢
D. 访存缺页
答:A
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。
5． 已知串其Next 数组值为（ ）。
A.0123
B.1123
C.1231
D.1211
答:A
【解析】KMP 算法的next 数组建立的原则
6． 设有一棵3阶B 树，如题图所示。删除关键字78得到一棵新B 树，其最右叶结点所含的关键字是（ ）。
题图二叉树图
A.60
B.60, 62
C.62, 65
D.65
答:D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下，其最右叶结点所含的关键字是65。
第 3 页，共 48 页
相关内容
相关标签