浙江工商大学 计算机2004

浙江工商大学2004年研究生入学考试试卷（A）卷

招生专业：计算机应用技术 考试科目：数据结构、计算机网络 考试时间：3小时

准考证号： 姓名： 得分：

A、第一部分：数据结构（共75分）

一、简答题（本大题共5小题，每小题5分，共计25分）

1、试举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

2、给出下算法的时间复杂度： main ( ) {

int x , n , y ; scanf(“%d”, &n); x=n; y=0;

while(x>=(y+1)(y+1) ) y++; }

3、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否是稀疏矩阵？

4、对链表设置表头结点的作用是什么？（至少说出2条好处） 5、快速排序在什么情况下排序算法产生恶化，原因是什么？

二、给出下面问题的算法函数描述（本大题共3小题，每小题10分，共计30分）

1、设计一个将单循环链表逆置的算法函数。

2、给定一棵用二叉链表表示的二叉树，每个结点都有2个指针（Ichild,rchild），分别用来指向其左右、子女，该树的根结点指针为t，试编写一个非递归求二叉树的叶子结点数目的算法函数。

3、设无向图采用邻接矩阵方法存储，请给出其广度先搜的算法函数。 三、下面是一段电文{CASE TAT A SA}，根据字符出现的濒率做权值构造一棵哈夫曼树，并给出每个字符的哈夫曼编码。（本大题共1小题，每小题10分，共计10分）

四、设散列表为HT[0..16]，即表的大小为m-17。现采用双散列法解决冲突。散列函数为：H0(key)=key；注：%是求余数运算（=mod）

Hi=(REV(key+1)+1); I=1,2,3,…, m-1

其中，函数REV（x）表示颠倒10进制数x的各位，如REV(37)=73，REV(7)=7等。若插入的关键码序列为{37，8，31，20，19，18，53，27}。试画出插入这8个关键码后的散列表。（本大题共1小题，每小题10分，共计10分）

B、第二部分：计算机网络（75分） 一、填空题（每空0.5分，共10分）

1、OSPF协议采用了 路由选择算法。

2、当网络负载增加到一定量后，若网络吞吐量反而下降，则表明网络出现了 现象。

3、光纤是现代计算机网络中常用的传输媒体，根据光信号在光纤中传输的特性不同，可将光纤分为 和 两大类。

4、IEEE802.3规定了数据帧的最短帧长，是因为 。 5、计算机网络中的网络协议指的是 。 6、从功能上，可以把计算机网络分成二大部分：通信子网和资源子网。通信子网实现 功能，资源子网实现 功能。

7、IPV4使用 个字节表示IP地址，IPV6使用 个字节表示IP地址。

8、在TCP/IP网络中，路径选择设置在 层，电子邮件服务设置在 层。

9、OSI参考模型采用了七层的体系结构，在物理层上所传的数据的单位是 ，在数据链路层所传的数据的单位是 ，在网络层上所传的数据的单位是 ，在运输层上所传的数据的单位是 。

10、物理层具有四个显著特性，它们是 、 、 、 。

二、选择题（每题1分，共10分）

1、无证实的服务包含哪2个服务原语。（ ）

A、请求和响应 B、请求和证实 C、请求和指示 D、请求和应答 2、下列哪一个产品是在OSI的数据链路层进行互连的。（ ） A、中继器 B、路由器 C、网关 D、网桥

3、根据下面滑动窗口状态，指出通信双方处于何种状态。（ ） 发送方 接收方 窗口序号模式

7 0 6 1 5 4 3

A、发送方发送0号帧，接收方准备接收0号帧 B、发送方发送1号帧，接收方接收完0号帧 C、发送方发送0号帧，接收方准备接收1号帧 D、发送方发送1号帧，接收方接收完1号帧

4、采用HDLC传输比特串011111111000001，比物填充后输出为。（ ） A、0101111111000001 B、0111110111000001 C、0111101111000001 D、0111111011000001 5、ASN.1编码规则是一种（ ）。

A、抽象语法 B、传送语法 C、本地语法 D、通用语法 6、采用串行线路连接到网络时，如果希望能够支持动态分配IP地址，那么数据链路协议应该采用（ ）协议。

A、SLIP B、PPP C、HDLC D、SDIC 7、采用星型拓扑的10Mbps基带双绞线以太网可以表示为（ ）。 A、10Base5 B、10Base2 C、10Base-T D、100Base-T 8、（ ）实现在由许多开放系统构成的环境中网络实体之间的通信功能。 A、数据链路层 B、应用层 C、网络层 D、传输层 9、下列哪个地址可以作为C类主机IP地址：（ ）

A、127.0.0.1 B、192.12.25.255 C、202.96.96.0 D、192.3.5.1 10、有关交换技术的论述，以下哪个是正确的：（ ）

A、电路交换要求在通信的双方之间建立起一条实际的物理通路，但通 信过程中，这条通路可以与别的通信方共享

B、现有的公用数据网都采用报文交换技术 C、报文交换可以满足实时或交互式的通信要求

D、分组交换将一个大报文分割成分组，并以分组为单位进行存储转发， 在接收端再将各分组重新装成一个完整的报文 三、判断题（每题1分，共10分）

1、FDDI由于采用了光纤作为传输介质，所以它的传输速率可达1000Mbps。 2、OSI参考模型的传输层仅提供了面向连接的服务。 3、会话层是网络体系结构中高低层之间的接口。

4、OSI模型中，数据在通信子网中传输时，一般只涉及到最底下的三层。 5、透明网桥在转发帧的同时，还要通过逆向学习算法来搜集MAC地址。 6、在电子邮件服务中，POP服务器是用来发送和接收电子邮件的。 7、每个以太网卡都拥有一个全世界唯一的48位地址。 8、OSI体系结构中，对数据的加密在应用层实现。 9、以太网是一种共享信道的网络。

10、局域网中，LLC帧是MAC帧的数据部分。 四、应用题（45分）

1、（10分）下图描述了拨号用户通过Internet通信的过程。 （1）请从以下备选答案中为（1）至（5）选择具体的协议：（5分） A.PPP B.SDLC C.HDLC D.DNS E.IP F.TCP G.HTTP H.RS-232-C I.SMTP J.OSPF K.POP3

应用层协议（1） 数据链路协议（2）

域名服务器 计算机 调制解调器 电话网 访问路由器 物理层协议（ 3） 应用层协议（5）

路由器 交换机

web服务器

Internet 路由协议（4）

以太网 -----------

路由器 邮件服务器

（2）PC机通过浏览器访问Web服务器上的页面，请按通信过程将A至I列出。（5分）

A、解析Web页面的URL，得到Web服务器的域名； B、通过域名服务器获得Web服务器的IP地址； C、从Web服务器获得URL指定的文档； D、通过电话网拨号与访问路由建立物理连接； E、与Web服务器通过应用层协议建立连接； F、与访问路由器建立数据链路；

G、浏览器解释页面文档，并显示在屏幕； H、获得PC机的IP地址； I、与Web服务器建立TCP连接。

2、（10分）报文110110101011011采用多项式X4+X3+X+1传送到达。这是否正确？为何？

3、（10分）证明：当用n个比特进行编号时，若接收窗口的大小为1，则只有在发送窗口的大小WT≤2n-1时，连续ARQ协议才能正确运行。

4、（10分）IP地址192.168.1.200，子网掩码是255.255.255.224，要求计算其网络地址、主机地址和广播地址。

5、（5分）设信号脉冲周期为0.002秒，脉冲信号有效值状态个数为8。请回答下列问题：

（1）如果用2进制代码表示上述信号，一个脉冲信号需用几位2进制代码表示。（2分）

（2）用2进制代码表示上述信号，其数据传输速度是多少。（3分）

本文来源：https://www.bwwdw.com/article/pk1x.html