2018年湘潭大学信息工程学院848数据结构(一)考研强化五套模拟题
● 摘要
一、填空题
1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
2． 模式串的next 函数值序列为_____。
【答案】01122312
3． —个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
4． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
5． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】
【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少
6． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
二、单项选择题
7． 若将关键字1, 2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中, 则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中, 构成的平衡树如下图所示, 由图可知平衡因子为0的分支结点为3个叶子结点, 故答案为D 。
8． 在
A.PPP
B.IP
C.UDP
D.TCP
【答案】B 。 图 体系结构中, 直接为ICMP 提供服务的协议是（ ）。
【解析】首先明确ICMP 是网络层的协议, 由于服务必须是下一层向上一层提供服务的, 因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层, 在网络层上面, 所以显然错误, 而PPP 协议是广域网数据链路层协议, 直接为网络层, 也就是IP 层提供服务, ICMP 协议是封装在网络层, 因此PPP 不能直接为ICMP 提供服务, ICMP 报文直接封装在IP 分组中, 故答案是B 。
9． 有关二叉树下列说法正确的是（ ）。
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
【答案】B
【解析】树的度＝MAX(结点1的度，结点2的度，结点3的度
以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
10．下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
结点n 的度) 。二叉树之所
D. 归并排序，起泡排序
【答案】D
11．分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.(100, 80, 90, 60, 120, 110, 130)
B.(100, 120, 110, 130, 80, 60，90)
C.(100, 60, 80, 90, 20, 110, 130)
D.(100, 80, 60, 90, 120, 130, 110)
【答案】C
【解析】二叉排序树:左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
12．某主机的IP 地址为, 子网掩码为
分组, 则目的地址可以是（ ）。 A. B. C. D.
【答案】D 。
【解析IPv4地址中的特殊地址, 直接广播地址, 也就是把主机位全部设置为1, 这里77的二进制是01001101, 子网掩码252的二进制是11111100, 由此可以看到77的前6位作为子网位, 后四位
, 也就是, 因此答案是D 。 作为主机位, 由此可以知道其广播地址是
13．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。
14．下列各类存储器中, 不采用随机存取方式的是（ ）。
A.EPROM
B.CDR0M
C.DRAM
D.SRAM
【答案】B
【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取, 而且存取时间与存
储单元的物理位置无关。CDROM 是只读的光盘存储器, 采用串行存取方式而不是随机存取方式。
。若该主机向其所在子网发送广播
相关内容
相关标签