中国传媒大学 2013 年数据结构与计算机网络
贡献者： xzllxls
答题说明：答案一律写在答题纸上，不需抄题，标明题号即可，答在试题上无效。
1. 一、单项选择题
1~25 小题，每小题 2 分，共 50 分。
1.表长为 $n$ 的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为（ ）。
A. $n$ $\qquad$ B. $n/2$ $\qquad$ C. $(n-1)/2$ $\qquad$ D. $(n+1)/2$
2.设 $n$ 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
int i=1;
while (i<=n)
i=i*2;
3.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区的结构是（ ）。
A.栈 $\qquad$ B.队列 $\qquad$ C.数组 $\qquad$ D.线性表
4.在下面的应用中，通常使用栈的是（ ）。
I 递归调用 $\qquad$ II 括号匹配 $\qquad$ III 表达式求值 $\qquad$
A.I、II $\qquad$ B. II、III $\qquad$ C.I、III $\qquad$ D.I、II、III
5.用链接方式存储的队列，在进行删除运算时，下面正确的是（ ）。
A.仅修改头指针 $\qquad$ B.仅修改尾指针 $\qquad$ C.头、尾指针都要修改 $\qquad$ D.头、尾指针可能都要修改
6. 设树 T 的度为 4,其中度为 1, 2, 3 和 4 的结点个数分别为 4,2, 1,1 则 T 中的叶子数是（ ）。
A.5 $\qquad$ B. 6 $\qquad$ C.7 $\qquad$ D.8
7. 下列关于二叉树的说法中，正确的是（ ）。
A.度为 $2$ 的有序树就是二叉树
B.含有 $n$ 个结点的二义树，其高度为 $\lfloor log_2n \rfloor +1$
C.完全二叉树中，若一个结点没有左孩子，则它必是叶子结点
D.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得的二义排序树与删除前原二叉排序树相同
8.某二义树的先序遍历序列为 IJKLMNO,中序遍历序列为 JLKINMO,则后序遍历序列是（）。
A. JLKMNOI $\qquad$ B. LKNJOMI $\qquad$ C. LKJNOMI $\qquad$ D. LKNOJMI
9. 设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 NI, N2 和 N3。与森林 F 对应的义树根结点的石子树上的结点个数是（ ）。
A. N1 $\qquad$ B. N1+N2 $\qquad$ C.N3 $\qquad$ D. N2+N3
10. 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 $G$ 有 $n$ 个结点，其邻接矩阵为 $A[1..n,1..n]$，且压缩存储在 $B[1..n(n-1)/2]$。若按行压缩存储对称矩阵的上三角元素，则当 $n$ 等于 $10$ 时，边 $(v6, v3)$ 的信息存储在（）。
A. B[18] $\qquad$ B. B[19] $\qquad$ C. B[20] $\qquad$ D. B[21]
11.以下关于图的说法正确的是（ ）。
I. 在一个有向图的拓扑序列中，若顶点 $a$ 在顶点 $b$ 之前，则图中必有一条弧 <a,b>
II. 若一个有向图的邻接矩阵中对角线以下元素均为 0，则该图的拓扑序列必定存在
III. 在 AOE 网中一定只有一-条关键路径
A.I、II $\qquad$ B. II、III $\qquad$ C.I、II $\qquad$ D.仅有 II
12. 设无向图 $G=(V, E)$ 和 $G'=(V',E')$, 如果 $G'$ 是 $G$ 的生成树，则下面说法中错误的是（ ）。
A. G'是 G 的子图 $\qquad$ B. G 是 G 的连通分量
C. G’是 G 的极小连通子图且 V=V' $\qquad$ D. G'是 G 的一个无环子图
13. 以下关于图的说法正确的是（ ）。
I. 图 G 的生成树是该图的一一个极小连通子图
II. 生成树中最长路径的起点和终点的度均为 1
III. 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
A.I. II $\qquad$ B.II、III $\qquad$ C.I、II $\qquad$ D.仅有 II
14. 已知有向图 $G=(V,A)$，其中 $V=${$a,b,c,d,c$}, $A=${<$a,b$>,<$a,c$>,<$d.c$>,<$d,c$>,<$b.e$>,<$c,e$>}，对该图进行拓扑排序，下面序列中不是拓扑排序的是（ ）。
A. a,d,c,b,e $\qquad$ B. d,a,b,c,e $\qquad$ C. a,b,d,c,e $\qquad$ D. a,b,c,d,e
15. 序列（8.9,10,4,5.6,20,1,2），只能是以下哪种排序方法两趟排序后的结果（ ）。
A.选择排序 $\qquad$ B.冒泡排序 $\qquad$ C.插入排序 $\qquad$ D.堆排序
16.下列排序算法中，时间复杂度为 $O(nlogn)$ 且占用额外空间最少的是（ ）
A.堆排序 $\qquad$ B.起泡排序 $\qquad$ C.快速排序 $\qquad$ D.希尔排序
17.对关键码序列（23,17.72.60.25.8.68,71.52）进行堆排序，输出两个最小关键码后的剩余堆是（ ）。
A. (23.72,60,25.68,71,52) $\qquad$ B. (23,25,52,60,71,72,68)
C. (71,25,23.52,60,72,68) $\qquad$ D. (23,25.68,52,60,72,71)
18. 当数据由源端 $A$ 传送至目的端 B 时，不参与数据封装工作的是（ ）。
A.传输层 $\qquad$ B.网路层 $\qquad$ C.数据链路层 $\qquad$ D.物理层
19.在常用的传输介质中，带宽最宽，信号传输衰减最小，抗干扰能力最强的是（ ）。
A.双绞线 $\qquad$ B.同轴电缆 $\qquad$ C.光纤 $\qquad$ D.微波
20.在无噪声情况下，若某通信链路的带宽为 $3kHz$，采用 $16$ 种不同的物理状态米表示数据，则该通信链路的最大数据传输速率是多少？( )
A.24 $\qquad$ B.18 $\qquad$ C.12 $\qquad$ D.3
21.若数据链路层采用后退 $N$ 帧协议，发送方已经发送了编号 $0$~$6$ 的帧。当计时器超时时，只收到了 $1$、$3$ 和 $5$ 号帧的确认，发送方需要重传的帧的数目是（ ）。
A.1 $\qquad$ B. 2 $\qquad$ C.5 $\qquad$ D. 6
22.在 802.3MAC 帧中，目的地址 DA 字段全为 “1”，则表示（ ）。
A.无效地址 $\qquad$ B.广播地址 $\qquad$ C.组地址 $\qquad$ D.本服务器地址
23.某路由器收到了一个 $IP$ 分组，在对其头部进行检验和后发现有差错，该路由器采取的动作是（ ）。
A.把该 IP 分组返回给源计算机
B.重新计算分组头检验和后继续转发该 IP 分组
C.丢弃该 IP 分组
D.给目的地计算机发送一个 ICMP 报文
24.设 $TCP$ 的拥塞窗口的慢开始门限值为 $16$(单位为报文段)，当拥塞窗口上升到 $20$ 时，网络发生超时，$TCP$ 开始慢启动和拥塞避免，那么第 $13$ 次传输时拥塞窗口大小为（ ）。
A.1 $\qquad$ B.17 $\qquad$ C.8 $\qquad$ D.16
25.如果本地域名服务无缓存，当采用递归方法解析另一个网络的某主机域名时，用户主机、本地域名服务器发送的域名请求条数分别为（ ）。
A.1 条，多条 $\qquad$ B.1 条，1 条 $\qquad$ C.多条，1 条 $\qquad$ D.多条，多条。
2. 二、综合应用题
26~34 小题，共 100 分。
26. (10 分)已知加权有向图 $G$ 如下，回答系列问题：
(1)画出该有向图 $G$ 的邻接矩阵：
(2)试利用 $Dijkstra$ 算法求 $G$ 中从顶点 $a$ 到其他各顶点间的最短路径，并给出求解过程。
27. (10 分)对下面的关键字集{30,15,21,40,25,26.36,37}若查找表的装填因子为 $0.8$，采用线性探测再散列方法解决冲突：
(1)设计散列函数;
(2)画出散列表;
(3)计算查找成功和查找失败的平均查找长度。
28. (12 分)请写一 “个算法将顺序存储结构的线性表 $(a_1..a_n)$ 逆置为 $(a_n..a_1)$.
29. (12 分)设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。
30. (12 分)假设非空二义树 bt 采用二义链表存储，其中所有结点数据域为正整数，设计一个递归算法求其中的最大值。
31. (8 分) A、B 两站相距 1km,使用 CSMA/CD 协议，信号在网络上的传播速度为 200 000km/s，两站的发送速率为 10Mbps，A 先发送数据，如果发送碰撞，求：
(1)最先发送数据的 A 站最晚经过多长时间才能检测到发生了碰撞。
(2)检测到碰撞后，A 已经发送了多少位？(假设 A 要发送的帧足够长)
32. (14 分)设有 A、B、C、D 共有 4 台主机都处在同一一个物理网络中，A 主机的 IP 地址为 192.175.12.112, B 主机的 IP 地址是 192.175.12.120, C 主机的 IP 地址是 192.175.12.176，D 主机的 IP 地址是 192.175.12.222。共同的子网掩码是 255.255.255.224。请回答以下问题，并写出解答过程。
(1) A、B、C、D 这 4 台主机之间哪些可以直接通信？哪些需要通过设置网关
(或路由器)才能通信？请画出网络连接示意图，并标注各个子网地址和主机地址。
(2)试描述主机 A 发送一个 IP 数据报到主机 D 的过程（包括物理地址解析过程）。
(3)若加入第 5 台主机 E，使它能与 C 主机直接通信，其 IP 地址的设定范围应是多少？
33. (12 分)用 TCP 传送 512 字节的数据，设窗口为 100 字节，而 TCP 报文段每次也是传送 100 字节的数据。再设发送方和接收方的起始序号分别为 100 和 200。画出发送方和接收方建立连接、传输数据、关闭连接的示意图。
34. (10 分)假设在 Internet 上一台 FTP 服务器，其名称为 ftp.cuc.edu.cn, IP 地址为 202.205.16.35，FTP 服务器进程在默认端口守候并支持匿名访问（用户名：anonymous,口令：guest）。如果用户 A 直接用服务器名称访问该 FTP 服务器，并从该服务器下载两个文件 p 和 q，试叙述 FTP 客户进程与 FTP 服务器进程之间的交换过程（注：文件 p 和 q 允许匿名账户访问）。