当前位置：问答库＞考研试题

目录

2018年三峡大学计算机与信息学院837计算机综合之数据结构考研仿真模拟五套题（一） ... 2 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研仿真模拟五套题（二） . 12 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研仿真模拟五套题（三） . 25 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研仿真模拟五套题（四） . 35 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研仿真模拟五套题（五） . 45

第 1 页，共 55 页

一、填空题

1． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。

【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

2． 模式串的next 函数值序列为_____。

【答案】01122312

3． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)

4． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

5． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。

第 2 页，共 55 页

其含义为数据data 入栈，出栈和测试栈是否空(不空返

("图有回路") ;

【答案】

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

6． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

7． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增 量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; (10，7，-9，0，47，23，1，8，98，36)

8． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

9． 在二叉树中，指针p 所指结点为叶结点的条件是_____。

【答案】

【解析】叶子节点的左右孩子都不存在。

第 3 页，共 55 页

10．二进制地址为011011110000, 大小为

【答案】011011110100；011011100000

和块的伙伴地址分别为:_____

和

其伙伴块的起始地址计

【解析】011011110000是块的起始地址，大小分别为算公式如下:

当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。

二、单项选择题

11．假设栈初始为空, 将中缀表达式当扫描到f 时, 栈中的元素依次是（ ）

A. B. C. D. 【答案】B

【解析】中缀表达式转后缀表达式遵循以下原则: (1)遇到操作数, 直接输出; (2)栈为空时, 遇到运算符, 入栈; (3)遇到左括号, 将其入栈;

(4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出; (5)遇到其他运算符符入栈;

(6)最终将栈中的元素依次出桟, 输出。

所以扫描到‟/‟, 入栈„描到‟+‟, 由于‟+‟优先级比‟/'低, 所以将‟/‟弹出, ‟+‟入栈; 扫描到‟*,, 优先级比‟+‟高, 入栈; 扫描到‟(„, 入栈; 扫描到‟一„, 将栈中优先级更高的‟*‟弹出, „一, 入栈; 扫描到‟*‟, 优先级比‟一„高, 入栈。所以扫描至“f的时候, 栈中元素为:+(一*

12．数组通常具有的两种基本操作是（ ）。

A. 查找和修改 B. 查找和索引 C. 索引和修改 D. 建立和删除 【答案】A

第 4 页，共 55 页

转换为等价后缀表达式的过程中,

时, 弹出所有优先级大于或等于该运算符的栈顶元素, 然后将该运算