2018年北京联合大学软件工程803软件基础之数据结构考研核心题库
● 摘要
一、填空题
1． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；
2． 建立索引文件的目的是_____。
【答案】提高查找速度
3． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
4． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。
【答案】比较；移动
5． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
；O(1)；满足堆的性质
二、单项选择题
6． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。 A.
B.
C.
D. 【答案】D
【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n0，n 1，n 2分别代表度为0，度为1，度为2的结点数) 。又在非空二叉树中:n 0＝n 2＋l ，且本题所给树为正则二叉树，n 1＝0，所以n ＝2*n0﹣l ，因此n 1＝(n+1)/2。
7． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
8． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断:①另设一个布尔变量来区别队列是空还是满；②队满时，
(rear+1)
font 。
9． 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT(往返时间) 时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。
A.7KB
B.8KB
C.9KB
D.16KB
【答案】C
【解析】回顾TCP 流量控制和拥塞控制(慢启动) 的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2＝8, 故三次成功后为8，以后为线性增长，故为8＋1＝9, 答案为C 。
10．下列四个序列中，哪一个是堆（ ）?
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 个关键字序列
①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
根据堆定义即可得出答案。
11．若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.
B.n/2 C.
D.n
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
。
12．在一棵三元树中度为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。
13．主机甲向主机乙发送一个(SYN一1, seq 一11220) 的TCP 段, 期望与主机乙建立TCP 连接, 若主机乙接受该连接请求, 则主机乙向主机甲发送的正确的TCP 段可能是（ ）。 A. B. C. D.
【答案】C
那么
相关内容
相关标签