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

一、填空题

1． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，

元素个数为

一个元素时，此时堆的元素个数最少，元素个数为

2． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。

【答案】

或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

3． 空格串是指_____，其长度等于_____。

【答案】由空格字符（

值32）所组成的字符串；空格个数

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

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

5． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ） { if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;

if （node->rflag）（3）; else {do t=*x；; while （*x==node ）; *x=t;

} }

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

6． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

7． 当两个栈共享一存储区时，栈利用一维数组表示，两栈顶指针为则当栈1空时

，

【答案】

为_____，栈2空时

，

为_____，栈满时为_____。

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

8． 在一棵m

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

【答案】

【解析】m

阶树除根结点和叶子结点外，结点中关键字个数最多是最少

9． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

10．在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。

【答案】要加“虚结点”。

设编号为

和

的结点在顺序存储中的下标为

和

。

，

则结点

和

在同一层上的条件是

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

二、选择题

11．下列关于IP 路由器功能的描述中，正确的是（ ）。

I. 运行路由协议，设置路由表；II. 监测到拥塞时，合理丢弃IP 分组；III. 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失；IV . 根据收到的IP 分组的目的IP 地址，将其转发到合适的输出线路上。

A. 仅III 、IV B. 仅 I 、II 、III C. 仅 I 、II 、IV

D.I 、II 、III 、IV 【答案】C 。

【解析】路由器的主要功能是路由和转发，因此I 和IV 是正确的，而针对II 和III ，可以从ICMP 协议的差错控制出发，注意检测到拥塞时，合理丢弃IP 分组，并回传ICMP 源抑制报文，II 是正确的，而III 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失，差错校验是正确的，但网络层不保证IP 分组不丢失，也就是不可靠的，因此III 的说法错误，正确的说法仅I 、II 、IV , 因此答案是C 。

12．设无向图的顶点个数为m 则该图最多有（ ）条边。

A.n-1

B.n （n-l ）/2

C.n （n+l）/2 D.0 E.n2

【答案】B

【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为n （n-l ）/2。

13．假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。

A.245Mbps B.979Mbps

C.

D. 【答案】D

【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到

的时间用来刷新

1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：

14．某主机的IP 地址为180.80.77.55, 子网掩码为255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（ ）。

A.180.80.76.0 B.180.80.76.255 C.180.80.77.255 D.180.80.79.255 【答案】D 。

【解析】IPv4地址中的特殊地址，直接广播地址，也就是把主机位全部设置为1，这里77的二进制是01001101, 子网掩码252的二进制是11111100，由此可以看到77的前6位作为子网位，后四位作为主机位，由此可以知道 其广播地址是180.80.01001111.255，也就是180.80.79.255，因此答案是D 。