2017年山东建筑大学计算机科学与技术学院900计算机专业综合之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1. 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
2. 从平均时间性能而言,_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
3. 模式串的next 函数值序列为_____。
【答案】01122312
4. 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
5. —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端)结点和_____个叶子,该满二叉树的深度为_____。 【答案】
或
【解析】满二叉树没有度为1的结点,度为0的结点等于度为2的结点个数+1。
6. 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个,进行入栈运算时发生上溢,则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的空间时,应将两栈的_____分别设在内存空间的两端,这样只有当_____时才产生溢出。
【答案】满;空;n ; 栈底;两栈顶指针相邻(即值之差的绝对值为1)
7. 设数组
储,则元素
为_____。
【答案】9174;8788
【解析】设一个元素的行标为i ,列标为j 。若以行序为主存储顺序,
则它的存储地址为
若以列序为主存储顺序,则它的存储地址为
的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存的存储地址为_____;若以列序为主序顺序存储,则元素的存储地址
8. 高度为4的3阶B-树中,最多有_____个关键字。
【答案】26
【解析】第4层是叶结点,1层至3层每个结点两个关键字,每个节点的关键字达到最大时,关键字最多。
9. 已知二叉排序树的左右子树均不为空,则_____上所有结点的值均小于它的根结点值,_____上所有结点的值均大于它的根结点的值。
【答案】左子树;右子树
【解析】二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:①若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;②若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;③它的左、右子树也分别为二叉排序树。
10., 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:)则的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ,列标为j 。若则的地址为 将代入得33。 则的地址为若
二、选择题
11.—个栈的入栈序列为的个数是( )
A.n-3
B.n-2
C.n-1
D. 无法确定
【答案】C
【解析】除了3本身以外,其他的值均可以取到,因此可能取值的个数为n-1。
12.若某文件系统索引结点(inode )中有直接地址项和间接地址项,则下列选项中,与单个文件长度无关的因素是( )
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
【答案】A
【解析】根据文件长度与索引结构的关系可知,只有选项A 是与单个文件长度无关的。 其出栈序列是若,则则可能取值
13.中断处理和子程序调用都需要压栈以保护现场,中断处理一定会保存而子程序调用不需要保存其内容的是( )。
A. 程序计数器
B. 程序状态字寄存器
C. 通用数据寄存器
D. 通用地址寄存器
【答案】B 。
【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关,而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序,并要求其去处理某一事件的一种常用手段。因此,除了要保护当前程序的地址,计数器(指针)和数据寄存器以外,还需要保存程序状态字。子程序调用是与当前进程有关,是正在运行的程序有意安排执行的,这一类调用发生的时间以及位置具有确定性,处于同一个进程内,因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。
14.在对n 个元素的序列进行排序时,堆排序所需要的附加存储空间是( )。
【答案】B
【解析】堆排序需要一个空间用于交换,因此堆排序所需要的附加存储空间为
15.设二维数组(即m 行n 列)按行存储在数组中,
则二维数组元素
在一维数组B 中的下标为( )。
【答案】A
【解析】
前
的元素个数为
所以二维数组元素在一维数组B
中的下标为
需要注意数组B 的下标是从0开始,还是从1开始。
16.下列选项中,不会引起指令流水线阻塞的是( )。
A. 数据旁路(转发)
B. 数据相关
C. 条件转移
D. 资源冲突
【答案】A
【解析】由于采用流水线方式,相邻或相近的两条指令可能会因为存在某种关联,后一条指令不能按照原指定的时钟周期运行,从而使流水线断流。有三种相关可能引起指令流水线阻塞:
①结构相关,又称资源相关;
②数据相关;
③控制相关,又称指令相关,主要由转移指令引起。
相关内容
相关标签