2017年河北师范大学数学与信息科学学院820数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下列不是设计一个“好”的算法应考虑达到的目标是（ ）。
A. 可行的
B. 健壮的
C. 无二义性的
D. 可读性好的
【答案】A
【解析】设计一个“好”的算法应考虑以下目标：正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。
2． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257
B.258
C.384
D.385
【答案】C
【解析】由
：
_
则和
__可知
，
即显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
3． 某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP 分组正确地路由到图中所有子网，则在R1中需要増加一条路由（目的网络，子网掩码，下一跳）是（ ）。
A.192.168.2.0, 255.255.255.128, 192.168.1.1
B.192.168.2.0, 255.255.255.0, 192.168.1.1
C.192.168.2.0, 255.255.255.128, 192.168.1.2
D.192.168.2.0, 255.255.255.0, 192.168, 1, 2
【答案】D
【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址，因此是 192.168.1.2, 此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点，注意其连接了 2个网络分别是192.168.2.0/25和192.168.2.128/25，但答案选项中只有一条信息，因此这里用到了超网的概念，超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址和主机地址。但是，与子网把大网络分成若干小网络相反，它是把一些小网络组合成一个大网络——超网，这里192.168.2.00000000/25和192.168.2.10000000/25 前24位是相同的，因此所构成的超网就是192.168.2.0/24，那么子网掩码就是255.255.255.00000000即 255.255.255.0, 因此答案是 D 。
4． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。
A.
B.
C.
D. 字节
字节
字节
字节
【答案】C
【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为B 。
5． 已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）
A.27
B.46
C.54
D.56
【答案】B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
6． 用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。
【答案】A
【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。
7． 设栈S 和队列Q 的初始状态均为空，元素a , b , c ，d ，e , f ，g 依次进入栈S 。若每个元素出栈
后立即进入队列Q ，且7个元素出队的顺序是b ，d ，c ，f , e , a ，g ，则栈S 的容量至少是（ ）。
A.1
B.2
C.3
D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b , 表明栈内还有元素a ，b 出栈前的深度为2; 第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3; c 出栈后，剩余元素为a ，c 出栈前的深度为2; f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3; e 出栈后，剩余元素为a ，e 出栈前的深度为2; a 出栈后，无剩余元素，a 出栈前的深度为1; g 出栈后，无剩余元素，g 出栈前的深度为1。所以栈容量至少是3。
8． 下列关于RISC 的叙述中，错误的是（ ）。
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成
C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少
【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
9． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）。
A.1000
B.2000
C.3000
D.4000
【答案】A
【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，
=2000字节，于是此时发送方的发送窗口为min{4000, 2000）由于发送方还没有收到第二个最大段
的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000-1000=1000字节，正确选项为A 。
相关内容
相关标签