中国传媒大学 2014 年数据结构与计算机网络
贡献者： xzllxls
答题说明：答案一律写在答题纸上，不需抄题，标明题号即可，答在试题上无效。
1. 一、单项选择题
(每小题 2 分，共 50 分)
1.下列关于栈和队列说法中，正确的是（ ）。
A.消除递归不一定需要使用栈
B.对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同
C.通常使用队列来处理函数或过程处理
D.队列和栈是运算受限的线性表，只允许在表的两端进行运算
2.一个栈的入栈序列是 1,2,3,4,5，则栈的不可能的输出序列是（）。
A. 5,4,3,2,1, $\qquad$ B.4,5,3,2,1 $\qquad$ C.4,3,5,1,2, $\qquad$ D.1,2,3,4,5
3.已知栈的输入序列为 $1$,$2$,$3$,...$n$,输出序列为 $p_1$, $p_2$, $p_3$, ..., $p_n$,若 $p_1=3$,则 $p_2$ 的值为（ ）。
A.一定是 2 $\qquad$ B.-定是 1 $\qquad$ C.可能是 1 $\qquad$ D.可能是 2
4.循环队列用数组 A[0..m-1]存放其元素值，已知其头尾指针分别为 front 和 rear,则当前元素个数为（）。
A. (rear-front+m) MOD m $\qquad$ B. rear-front+1
C. rear-front-1 $\qquad$ D. rear-front
5.已知有一维数组 $A[0..m*n-1]$,若要对应为 $m$ 行、$n$ 列的矩阵，将元素 $A[k](0\leqslant k< m*n)$ 表示成矩阵的第 $i$ 行、第 $j$ 列的元素 $(0\leqslant i< m, 0\leqslant j< n)$,则下面的对应关系是（ ）。
A. $i=k/n, j=k\%m$ $\qquad$ B. $i=k/m, j=k\%m$
C. $i=k/n, j=k\%n$ $\qquad$ D. $i=k/m, j=k\%n$
6.设有一个 $10$ 阶的对称矩阵 $A$,采用压缩存储方式，以行序为主存储，$a_{1,1}$. 为第一元素，其存储地址为 $1$,每个元素占一个地址空间，则 $a_{8,5}$ 的地址是（）。
A.13 $\qquad$ B.33 $\qquad$ C.18 $\qquad$ D.40
7.含有 $n$ 个结点的三叉树的最小高度是（ ）。
A.$n$ $\qquad$ B.$\lfloor n/3 \rfloor$ $\qquad$ C.$\lfloor log_3n\rfloor+1$ $\qquad$ D.$\lceil log_3(2n+1)\rceil$
8.在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（ ）。
A. n $\qquad$ B. n-1 $\qquad$ C. n 十 1 $\qquad$ D.2*n
9.在常用的描述二叉排序树的存储结构中，关键字值最大的结点是（ ）。
A.左指针一定为空 $\qquad$ B.右指针一定为空
C.左右指针均为空 $\qquad$ D.左右指针均不为空
10. 由权值为 9、2、5、7 的四个叶子构造一棵哈夫曼树，该树的带权路径长度为（ ）
A.23 $\qquad$ B.37 $\qquad$ C.44 $\qquad$ D.46
11. 若一个具有 n 个结点、k 条边的非连通无向图是一个森林（n>k）, 则该森林中必有树的数目是（ ）。
A. k $\qquad$ B. n $\qquad$ C. n-k $\qquad$ D. n+k
12.采用邻接表存储的图的广度优先遍历算法类似于树的（ ）。
A.中根遍历 $\qquad$ B.先根遍历 $\qquad$ C.后根遍历 $\qquad$ D.按层次遍历
13.在有向图 $G$ 的拓扑序列中，若顶点 $V_i$ 在顶点 $V_j$ 之前，则下列情形不可能出现的是（ ）。
A. $G$ 中有弧 $< V_i,V_j>$ $\qquad$ B. $G$ 中有一条从 $V_i$ 到 $V_j$ 的路径
C. $G$ 中没有弧 $< V_i,V_j>$ $\qquad$ D. $G$ 中有一条从 $V_j$ 到 $V_i$ 的路径
14.有一个长度为 12 的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是（ ）。
A.37/12 $\qquad$ B.35/12 $\qquad$ C.39/12 $\qquad$ D.43/12
15.假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，至少要进行的探查次数是（ ）。
A. k-I $\qquad$ B. k $\qquad$ C. k+1 $\qquad$ D. k(k+1)/2
16.下列序列中，满足堆定义的是（ ）。
A. (100，86, 48，73，35, 39，42，57, 66, 21)
B. (12, 70，33，65，24, 56，48，92，86，33)
C. (103, 97，56，38，66, 23，42，12, 30，52, 6, 26)
D. (5, 56，20，23, 40, 38，29，61, 36，76，28，100)
17.对于一个长度为 $n$ 的任意表进行排序，至少需要进行的比较次数是（）。
A. $O(m)$ $\qquad$ B. $O(n^2)$ $\qquad$ C.$O(logn)$ $\qquad$ D. $O(nlogn)$
18.关于网络分层结构，下列说法正确的是（ ）。
A.某一层可以使用其上一层提供的服务而不需知道服务是如何实现的
B.层次划分越多，灵活性越好，协议效率也越高
C.由于结构彼此分离，实现和维护更加困难
D.当某一层发生变化时，只要接口关系不变，以上或以下的各层均不受影响
19.不受电磁干扰或噪声影响的介质是（ ）。
A.双绞线 $\qquad$ B.光纤 $\qquad$ C.同轴电缆 $\qquad$ D.微波
20.要在带宽为 4kHz 的信道上用 2 秒钟发送 80kb 的数据块，按照香农定理，信道的信噪比最小应为多少？( )
A.1023 $\qquad$ B.200 $\qquad$ C.1005 $\qquad$ D.600
21.若数据链路层采用选择重传协议，发送方已经发送了编号为 0~6 的帧。当计时器超时时，只有 5 号帧的确认还没有返回，则发送方需要重发的帧数为（ ）。
A.1 $\qquad$ B.2 $\qquad$ C.3 $\qquad$ D.7
22.下面技术无法使 10Mbps 以太网升级到 100Mbps 和 1Gbps 的是（）。
A.采用帧扩展和帧突发技术
B.传输介质使用高速光纤
C.帧长保持不变，网络跨距增加
D.使用以太网交换机，引入全双工流量控制协议
23.位于不同子网中的主机之间进行相互通信，下面说法中正确的是（）。
A.源站点可以直接进行 ARP 广播得到目的站的硬件地址
B.路由器在转发 IP 数据报时，重新封装源硬件地址和目的硬件地址
C.路由器在转发 IP 数据报时，重新封装目的 IP 地址和目的 IP 硬件地址
D.路由器在转发 IP 数据报时，重新封装源 IP 地址和目的 IP 地址
24.在 TCP/IP 网络上，主机及主机上运行的程序可以用（）来标识。
A. IP 地址，MAC 地址 $\qquad$ B.端口号，IP 地址
C. IP 地址，主机地址 $\qquad$ D. IP 地址，端口号
25.标准的 URL 组成：服务器类型、主机名和路径及（）。
A.文件名 $\qquad$ B.浏览器
C.客户名 $\qquad$ D.进程名
2. 二、综合应用题
26~34 小题，共 100 分。
26. (10 分) 现有一个解决无向连通图的最小生成树的一种方法如下：
将图中所有边按权重从大到小排序为(e1,e2,...,em);
i=1;
while (所剩边数>=顶点数) {
从图中删去ei;
若图不再连通，则恢复ei;
i=i+1;
}
27. (10 分)采用散列函数 $H(k)=3\times k \quad MOD \quad 13$ 并用线性探测开放地址法处理冲突，在散列地址空间 $[0..12]$ 中对关键字序列 $22$, $41$, $53$, $46$, $30$, $13$, $1$, $67$, $51$;
(1)构造散列表（画示意图）;
(2)装填因子;
(3)等概率情况下查找成功的平均查找长度;
(4)等概率情况下查找失败的平均查找长度。
28. (12 分)已知数组 $A[1..n]$ 的元素类型为整型 $int$, 设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。
(1)给出算法的基本设计思想;
(2)根据设计思想，采用 $C$ 或 $C++$ 语言表述算法，关键之处给出注释;
(3)说明你所设计算法的时间复杂度和空间复杂度。
29. (12 分)已知带头结点的单链表 $H$，写一算法将其数据结点逆序链接，即线性表 $(a_1,..,a_n)$ 逆置为 $(a_n,..,a_1)$.
(1)给出算法的基本设计思想。
(2)根据设计思想，采用 $C$ 或 $C++$ 语言描述算法，关键之处给出注释。
30. (12 分)假设二叉树采用二叉链表存储结构存储，设计一个算法，利用结点的右孩子指针 $rchild$ 将一棵二叉树的叶子结点按从左往右的顺序串成一个单链表。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用 $C$ 或 $C++$ 语言描述算法，关键之处给出注释。
31. (8 分)若构造一个 CSMACD 总线网，速率为 100Mbps,电缆总长度 1km,中间用一个中继器连接，电缆中的信号传播速度是 200000km/s,信号经过中继器产生 2Hs 时延。试求出数据帧的最小长度。
32. (14 分)一个公司有两个部门，销售部和财务部，销售部有 28 台 PC,财务部。有 15 台 PC。现在，公司申请了一个 C 类地址 221.156.18.0，规划的网络拓扑如下图所示，试解答如下问题。
(1)给出合理的子网规划，并说明理由。
(2)为两个部门各分配一个子网地址，并为两个路由器的接口和各台 PC 分配 IP 地址。
(3)如果路由器 R1 和 R2 都采用了 RIP 作为路由选择协议，请给出当稳定运行之后，R1 和 R2 的路由表。
33. (12 分)假设主机 A 已向主机 B 发送了一个序号为 70 的报文段，并己在超时计数器超时之前收到了主机 B 的确认。现主机 A 向主机 B 又连续发送了两个 TCP 报文段 p、q，其序号分别为 90、130。请回答以下问题，并写出解答过程。
(1) p 报文段携带了多少字节的数据？
(2)主机 B 收到 p 报文段后发回的确认中的确认号应当是多少？
(3)如果主机 B 收到 q 报文段后发回的确认中的确认号是 180, 试问 A 发送的 q 报文段中的数据有多少字节？
(4)如果 A 发送的 p 报文段丢失了，但 q 报文段到达了 B. B 在 q 报文段到达后向 A 发送确认。试问这个确认号应为多少？
34.(10 分)基于万维网的电子邮件系统有什么特点？在传送邮件时使用什么协议？