中国传媒大学 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 的路由表.

图
图 1:第 32 题图

   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 分)基于万维网的电子邮件系统有什么特点?在传送邮件时使用什么协议?


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利