2019年东南大学建筑学院935计算机专业基础之数据结构考研核心题库

考研专业课资料、辅导、答疑一站式服务平台

第 1 页，共 54 页

目录

2019年东南大学建筑学院935计算机专业基础之数据结构考研核心题库（一） (2)

2019年东南大学建筑学院935计算机专业基础之数据结构考研核心题库（二） (12)

2019年东南大学建筑学院935计算机专业基础之数据结构考研核心题库（三） (24)

2019年东南大学建筑学院935计算机专业基础之数据结构考研核心题库（四） (34)

2019年东南大学建筑学院935计算机专业基础之数据结构考研核心题库（五） (45)

考研专业课资料、辅导、答疑一站式服务平台

第 2 页，共 54 页 2019年东南大学建筑学院935计算机专业基础之数据结构考研核心题库（一） 特别说明：

1-本资料为2019考研考研复习使用，精选汇编了该科目历年常考核心试题，精题精练。

2-资料仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权、请联系我们立即处理。

一、单项选择题

1． 某以太网拓扑及交换机当前转发表如下图所示, 主机向主机发送1个数据帧,主机收到该帧后,向主机

发送一个确认帧,交换机对这两个帧的转发端口分别是（ ） A.

和 B.{2,3}和{1} C.

和 D.和

{1}

【答案】B

【解析】

第一次交换机没有

的信息,只能选择从其他端口全部发送,同时记录这个数据报源MAC 地址的信息,确认帧发送时已经有的信息了所以只用从1端口转发。

2． 若某通信链路的数据传输速率为2400bps,采用4相位调制,则该链路的波特率是（ ）。

A.600波特

B.1200波特

C.4800波特

D.9600波特

【答案】B

【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系:

,而奈奎斯特公式一无噪信道传输能力公式是

,N 为—个码元所取的离散值个数。从而可以得到波特率与数据传输速率的关系,即

,在本题中数据传输速率C=2400,N=4,因此波特率是1200,答案是B 。

考研专业课资料、辅导、答疑一站式服务平台

第 3 页，共 54 页

3． 将森林F 转换为对应的二叉树T,F 中叶结点的个数等于（ ）

A.T 中叶结点的个数

B.T 中度为1的结点个数

C.T 中左孩子指针为空的结点个数

D.T 中右孩子指针为空的结点个数

【答案】C

【解析】森林转化为对应的二叉树是…孩子-兄弟?存储的,即左孩子指针指向当前节点的孩子节点,右孩子指针指向当前节点的兄弟节点,所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C

4． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A.4

B.5

C.6

D.7

【答案】C

【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所以x ＝6。

5． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。 A.

B.

C.

D. 【答案】D

【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n 0，n 1，n 2分别代表度为0，度为1，度为2的结点数)。又在非空二叉树中:n 0＝n 2＋l ，且本题所给树为正则二叉树，n 1＝0，所以n ＝2*n 0﹣l ，因此n 1＝(n+1)/2。

6． 计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。

A.可执行性、可移植性、可扩充性

考研专业课资料、辅导、答疑一站式服务平台

第 4 页，共 54 页 B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性

D.易读性、稳定性、安全性

【答案】B

【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性:有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。

7． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

A.h ﹣＞next ＝s ；

B.s ﹣＞next ＝h ；

C.s ﹣＞next ＝h ；h ﹣＞next ＝s ；

D.s ﹣＞next ＝h ﹣next ；h ﹣＞next ＝s ；

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。

8． 元素a,b,c,d,e 依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d 开头的序列个数是（ ）。

A.3

B.4

C.5

D.6

【答案】B

【解析】d 首先出栈后的状态如下图所示。

此时可有以下4种操作:

(1)e 进栈后出栈,出栈序列为decba 。

(2)c 出栈,e 进栈后出栈,出栈序列为dceba 。

(3)cb 出栈,e 进栈后出栈,出栈序列为dcbea 。

(4)cba 出栈,e 进栈后出栈,出栈序列为dcbae 。

考研专业课资料、辅导、答疑一站式服务平台

第 5 页，共 54 页 9． 用希尔排序方法对一个数据序列进行排序时,若第1趟排序结果为9,1,4,13,7,8,20,23,15,则该趟排序采用的增量(间隔)可能是（ ）

A.2

B.3

C.4

D.5

【答案】B

【解析】对于A ,增量为2,那么9,4,7,20,15是一组,而它们是无序的,所以A 错误

对于C ,增量为4,那么9,7,15是一组,而它们是无序的,所以C 错误

对于D ,增量为5,那么9,8是一组,降序,1,20是一组,而它们是升序,所以D 也错误。对于B ,分为3组:9,13,20; 1,7,23; 4,8,15都是升序有序,所以B 正确

10．折半查找的时间复杂性为（ ）。 A.

B.O(n)

C.

D.

【答案】D

【解析】顺序查找的事件复杂度为,因为折半查找是查找效率最髙的算法，它的事件复杂度为。

11．下列选项中,在用户态执行的是（ ）。

A.命令解释程序

B.缺页处理程序

C.进程调度程序

D.时钟中断处理程序

【答案】A

【解析】题目是问用户态执行,可见是有关操作系统基本概念的问题。四个选项中,用户唯一能面对的是命令解释程序,缺页处理程序和时钟中断都属于中断,在核心态执行,而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口,可以运行在用户态,接受用户的命令操作控制。

12．某机器有一个标志寄存器,其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF,条件转移指令bgt(无符号整数比较大于时转移)的转移条件是（ ）。

A.CF+OF=0

B.SF+ZF=0

C.CF+ZF=0

D.CF+SF=0

【答案】C

【解析】判断无符号整数A>B 成立,满足的条件是结果不等于0,即零标志ZF=0,且不发生进

考研专业课资料、辅导、答疑一站式服务平台

第 6 页，共 54 页 位,即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF ,显然可以排除掉。

13．下面关于串的叙述中，不正确的是（ ）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

【答案】B

【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。

14．主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）.

A.1000

B.2000

C.3000

D.4000

【答案】A

【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为min{4000，2000)＝2000字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000－1000＝1000字节，正确选项为A.

15．在一个文件被用户进程首次打开的过程中,操作系统需做的是（ ）

A.将文件内容读到内存中

B.将文件控制块读到内存中

C.修改文件控制块中的读写权限

D.将文件的数据缓冲区首指针返回给用户进程

【答案】B

【解析】概念

二、判断题

16．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）

【答案】×

【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢

本文来源：https://www.bwwdw.com/article/206q.html