2018年武汉大学933计算机基础

2018年招收攻读硕士研究生

入学考试自主命题试题

考试科目及代码：933计算机基础(数据结构、计算机网络)

适用专业：08用00计算机科学技术083900网络空间安全

085211计算机技术

(所■答案都必须与在入耍欲上，写左锹教欷上及草稿歆上无效，

考竟后徐耍履率敢皴衮①，

模拟卷一(蓝3版)

填空题(20分，每题2分)

1.通常从四个方面评价算法的质量：、、和。

2.一个算法的时间复杂度为(n~3+n~210g2n)/n2,其数量级表示为。

3.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾

指针R指向队尾元素的当前位置，则该循环队列中最多存储队列元素。

4.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为

3的结点数有个。

5.设散列表的长度为8,散列函数H(k)=k%7,用线性探测法解决冲突，则根据一组初始

关键字序列(8,15,16,22,30,32)构造出的散列表的平均查找长度是。

6.设有一组初始记录关键字序列为(50,16,23,68,94,70,73),则将它们调整成初始

堆只需把16与相互交换即可。

7.IEEE802.3采用协议，IEEE802.il采用协议。

8.在采用TCP/IP协议通讯时，必须保证整个网段上主机的IP地址在或。

9.IPv6地址为个比特，其数据报基本首部为固定的字节。

10.表示主机比特全为“0”的IP地址，为：的地址，表示主机比特全为“1”的IP

地址，为：的地址。

判断题（20分，每个2分）

No.12345678910

Answer

1.递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本

身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（）

2.采用不同的遍历方法，所得到的无向图的生成树总是相同的。（）

3.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。（）

4.边数很少的稀疏图，适宜用邻接矩阵表示。（）

5.直接选择排序是一种稳定的排序方法。（）

6.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（）

7.宽带ISDN的核心技术是ATM技术。（）

8.在0SI模型中物理层实现了数据的无差错传输。（）

9.RIP协议采用的路径算法是基于链路状态协议的。（）

10.在命令状态下键入“ping127.0.0.1”可以用来验证网卡是否正常。（）

三.选择题（30分，每个3分）

No.12345678910

Answer

1.下列算法的时间复杂度为（）

voidfun（intn）｛

inti=0;

while(i*i*i<=n)

i++；

)

A.O(n)B,O(nlogn)C.而)D.0(4)

2.线性表(al,a2,…,an)以链接方式存储时，访问第i位置元素的时间复杂性为()

A.O(i)B.O(1)C.O(n)D.O(i-1)

3.下面哪一方法可以判断出一个有向图是否有环（回路）（）

A.深度优先遍历B.求两个结点之间的路径C.求最短路径D.求关键路径

4.一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（）。

A.23415B.54132C.23145D.15432

5.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（B）

A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG

6.为了使数据在网络中的传输延迟最小，首选的交换方式是（）。

A.电路交换

B.报文交换

C.分组交换

D.信元交换

7.在开放系统互连环境中，两个N层实体进行通信，可能用到的服务是（）。

A.N-1层提供的服务

B.N层提供的服务

C.N+1层提供的服务

D.以上都不对

8.某部门申请到一个C类IP地址，若要分成8个子网，其掩码应为（）。

A.-55

B.

C.24

D.92

9.内部网关协议包括（）o

A.OSPF和IGP

B.OSPF和EGP

C.RIP和BGP

D.OSPF和RIP

10.UDP数据报比IP数据报多提供了（）服务。

A.流量控制

B.拥塞控制

C.端口功能

D.路由转发

四.简答题（60分）

1.一只青蛙一次可以跳上1级台阶，也可以跳上2级。

求该青蛙跳上一个n级的台阶总共有多少种跳法。

（递归解法。）

2.根据下图回答下列问题：

(1)从顶点A出发，求它的深度优先生成树

(2)从顶点E出发，求它的广度优先生成树

(3)根据普利姆(Prim)算法，

3.假设哈希表的地址范围是0-8,哈希函数为：H(K)=(K+l)MOD9K为关键字，用线

性表探测再散列法处理冲突，输入关键字序列｛13,32,17,31,30,36,63]

回答下列问题：

(1)画出构造的哈希表。

(2)计算成功查找长度以及失败查找长度。

4.在数据传输过程中，若接收方收到的二进制比特序列为10110011010,接收双方采用的

生成多项式为G(x)=x4+x3+l,则该二进制比特序列在传输中是否出错？如果传输没

有出现差错，发送数据的比特序列和CRC检验码的比特序列分别是什么？

5.(1)子网掩码为代表什么意思？

(2)某网络的现在掩码为48,问该网络能够连接多少个主机？

(3)某A类网络和某B类网络的子网号subnet-id分别为16个1和8个1,问这两个

网络的子网掩码有何不同？

(4)某A类网络的子网掩码为55,它是否是一个有效的子网掩码？

五.算法设计（20分）

（请使用类C语言进行编程，如果编码困难可以写伪代码，会适当扣分）

试写出算法，求任意二叉树中第一条最长的路径长度（多条相等只输出一条），并输出此路

径上各结点的值。

typedefstructBiTree{

intdata；

structBiTree*Rc；

structBiTree*Lc；

}*BiTree；

程过大学

2018年招收攻读硕士研究生

入学考试自主命题试题

考试科目及代码：933计算机基础（数据结构、计算机网络）

适用专业：08用00计算机科学技术0839技网络空间安全

085211计算机技术

（所■答案都必须与在卷耍欲上，写左锹耍欲上及草稿歆上无效,

考竟后曲蹶成答耍欷衮①，

模拟卷一（'J版）参考答案

填空题（20分，每题2分）

1.通常从四个方面评价算法的质量：I正确性I、I易读性I、I强壮性胤高效树。

2.一个算法的时间复杂度为（n~3+n~210g2n）/n2,其数量级表示为I。（n）|。

3.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾

指针R指向队尾元素的当前位置，则该循环队列中最多存储叵］队列元素。

4.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为

3的结点数有回个。

5.设散列表的长度为8,散列函数Il（k）=k%7,用线性探测法解决冲突，则根据一组初始

关键字序列（8,15,16,22,30,32）构造出的散列表的平均查找长度是国。

6.设有一组初始记录关键字序列为（50,16,23,68,94,70,73）,则将它们调整成初始

堆只需把16与网相互交换即可。

7.IEEE802.3采用〔CSMA/CD胁议,IEEE802.11采用|CSMA/CA|协议。

8.在采用TCP/IP协议通讯时,必须保证整个网段上主机的1P地址在I同一网前TI或网

络号相同。

9.IPv6地址为画个比特，其数据报基本首部为固定的画字节。

10.表示主机比特全为“0”的IP地址，为：国的地址,表示主机比特全为“1”的IP

地址，为：尸藕的地址。

判断题（20分，每个2分）

No.12345678910

AnswerVXVXXVVXXJ

1.递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本

身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（V）

2.采用不同的遍历方法，所得到的无向图的生成树总是相同的。（X）

3.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。（V）

4.边数很少的稀疏图，适宜用邻接矩阵表示。（X）

5.直接选择排序是一种稳定的排序方法。（X）

6.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（V）

7.宽带ISDN的核心技术是ATM技术。（V）

8.在OSI模型中物理层实现了数据的无差错传输。（X）

9.RIP协议采用的路径算法是基于链路状态协议的。（X）

10.在命令状态下键入“ping127.0.0.1”可以用来验证网卡是否正常。（V）

三.选择题（30分，每个3分）

No.12345678910

AnswerCCABBAACDC

1.下列算法的时间复杂度为（C）

voidfun（intn）｛

inti=0;

while（i*i*i<=n）

i++；

）

A.O（n）B.O（nlogn）C.0（西）D.0（4）

2.线性表（al,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（C）

A.O（i）B.O（1）C.O（n）D.O（i-1）

3.下面哪一方法可以判断出一个有向图是否有环（回路）（A）

A.深度优先遍历B.求两个结点之间的路径C.求最短路径D.求关键路径

4.一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（B）。

A.23415B.54132C.23145D.15432

5.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（B）

A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG

6.为了使数据在网络中的传输延迟最小，首选的交换方式是（A

A.电路交换

B.报文交换

C.分组交换

D.信元交换

【解析】电路交换需要在传输之前建立一个固定的连接，在连接未拆除之前，数据通信双方

一直占用该连接，保证了数据传输的可靠性，因此其传输的延迟最短。

7.在开放系统互连环境中，两个N层实体进行通信，可能用到的服务是（A）。

A.N-1层提供的服务

B.N层提供的服务

C.N+1层提供的服务

D.以上都不对

【解析】在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务，要实现

本层协议，还需要使用下面一层所提供的服务。

8.某部门申请到一个C类IP地址，若要分成8个子网，其掩码应为（C）.

A...55

B.

C.24

D.92

【解析】C类地址范围：〜54。C类地址第1字节、第2字节和第3

个字节为网络地址，第4个字节为主机地址。为了划分成8个子网，必须占用3位主机

地址，第4个字节对应掩码的二进制应为11100000。

所以子网掩码应为：24。

9.内部网关协议包括（D）。

A.OSPF和IGP

B.OSPF和EGP

C.RIP和BGP

D.OSPF和R1P

【解析】要区分外部网关协议（EGP）和内部网关协议（IGP）,OSPF、RIP属于内部网关协议，

BGP则属于外部网关协议。

10.UDP数据报比IP数据报多提供了（C）服务。

A.流量控制

B.拥塞控制

C.端口功能

D.路由转发

【解析】虽然UDP协议和IP协议都是数据报协议，但是它们之间还是存在差别。其中,

最大的差别是IP数据报只能找到目的主机而无法找到目的进程，UDP提供端口功能以及

复用和分用功能，可以将数据报投递给对应的进程。

四.简答题(60分)

1.一只青蛙一次可以跳上1级台阶，也可以跳上2级。

求该青蛙跳上一个n级的台阶总共有多少种跳法。

uoidforg(intn,inti)

(

count++；

elseif(n<i)

(

forg(n+1,i)；

forg(n+2,i)；

)

递归解法。).

2.根据下图回答下列问题：

(1)从顶点A出发，求它的深度优先生成树

(2)从顶点E出发，求它的广度优先生成树

(3)根据普利姆(Prim)算法,

设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列

(l)ABGFDEC(2)EACFBDG

⑶

3.假设哈希表的地址范围是0-8,哈希函数为：H(K)=(K+l)MOD9K为关键字，用线

性表探测再散列法处理冲突，输入关键字序列｛13,32,17,31,30,36,63]

回答下列问题：

(3)画出构造的哈希表。

(4)计算成功查找长度以及失败查找长度。

地址012345678

关键字17366330133231

比较次1121113

失败432154321

成功10/7

失败25/9

4.在数据传输过程中，若接收方收到的二进制比特序列为10110011010,接收双方采用的

生成多项式为G(x)=x4+x3+l,则该二进制比特序列在传输中是否出错？如果传输没

有出现差错，发送数据的比特序列和CRC检验码的比特序列分别是什么？

答：根据题意，生成多项式G(x)对应的二进制比特序列为11001。进行如下的二进制

模2除法，被除数为10110011010,除数为11001：

____________1101010

11001)10110011010

11001

11110

11001

11111

11001

11001

11001

0

所得余数为0,因此该二进制比特序列在传输过程中没有出现差错。发送数据的比特序列是

1011001,CRC

检验码的比特序列是1010。

5.(1)子网掩码为代表什么意思？

(2)某网络的现在掩码为48,问该网络能够连接多少个主机？

(3)某A类网络和某B类网络的子网号subnet-id分别为16个1和8个1,问这两个

网络的子网掩码有何不同？

(4)某A类网络的子网掩码为55,它是否是一个有效的子网掩码？

答：(1)可代表C类地址对应的子网掩码默认值：也可代表A类或B类

地址的掩码，即主机号由最后8bit决定，而路由器寻找目的网络的下一跳地址由前24bit决

定。

(2)248=(11111000)2，即IP地址中前29位代表网络，后3位代表主机。所以共有主机

数为23=8,但由于主机号全0代表该网络的网络地址，主机号全1代表该网络的广播地

址，均不能分配给连网主机使用，所以网络能够连接的主机数为23—2=6台。

(3)这两个网络的子网掩码是一样的，均为,但子网数不同，子网号为16bit

的A类网络的子网数有2|6-2个，而子网号为8bit的B类网络的子网数有28-2个。

(4)有效，因RFC文档中没有规定子网掩码中的一串1必须是连续的，但不建议这样使

用。

五.算法设计(20分)

(请使用类C语言进行编程，如果编码困难可以写伪代码，会适当扣分)

试写出算法，求任意二叉树中第一条最长的路径长度(多条相等只输出一条)，并输出此路

径上各结点的值。

typedefstructBiTree{

intdata；

structBiTree*Rc；

structBiTree*Lc；

}*BiTree；

因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈

时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长

路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

voidLongestPath(BiTreebt)//求二叉树中的第一条最长路径长度

{BiTreep=bt,IM,s[]；〃l,s是栈，元素是二叉树结点指针，1中保留当前最长路径中的结

点

inti>top=0,tag[],longest=0;

while(p||top>0)

{while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下

if(tag[top]==l)〃当前结点的右分枝已遍历

{if(!s[top]->Lc&&!s[top]->Rc)〃只有到叶子结点时，才查看路径长度

if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top—;}

〃保留当前最长路径到1栈，记住最高栈顶指针，退栈

}

elseif(top>0){tag[top]=l;p=s[top].Rc;}〃沿右子分枝向下

}//while(p!=null||top>0)

}〃结束LongestPath

2018年招收攻读硕士研究生

入学考试自主命题试题

考试科目及代码：933计算机基础（数据结构、计算机网络）

适用专业：081200计算机科学技术083900网络空间安全

085211计算机技术

（所■答案都必须与在答电欲上，写左锹教欷上及草稿歆上无效，

考竟后徐蹶履率夏皴拿命，

模拟卷二（僦版）

填空题（20分，每题2分）

1.广义表（a,（a,b）,d,e,（（i,j）,k））的长度是,深度是。

2.循环队列用数组A［0..mT］存放其元素值，已知其头尾指针分别是front和rear,则当

前队列的元素个数是。

3.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度

为,在给定值为x的结点后插入一个新结点的时间复杂度为。

4.已知数组AE0..9.0..9］的每个元素占5个存储单元，将其按行优先次序存储在起始地

址为1000的连续的内存单元中，则元素A［6,8］的地址为。

5.高度为K的完全二叉树至少有个叶子结点。

6.如果含n个顶点的图形形成一个环，则它有棵生成树。

7.IP使用D类地址支持多播，其地址范围是。

8.目前常用的四种信道复用方式是：、时分复用、和波分复用。

9.在路由表中，对第一条路由最主要的是和。

10.一个TCP报文段分为首部和—两部分，TCP首部的最小长度是字节。

判断题（20分，每个2分）

No.12345678910

Answer

1.数组是同类型值的集合。（）

2.取线性表的第i个元素的时间同i的大小有关.（）

3.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.（）

4.一个广义表可以为其它广义表所共享。（）

5.最小生成树的KRUSKAL算法是一种贪心法（GREEDY）。（）

6.当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）

7.TCP适用于组播和广播通信方式，而UDP只适用于单播。（）

8.OSI参考模型中的数据链路层的主要功能是负责分组流控制、差错控制等。（）

9.应用层的网络应用程序分为直接网络应用和间接网络应用两类。（）

10.RIP是一种距离矢量路由选择算法，现在仍然广泛使用，适合于大型网络。（）

三.选择题（30分，每个3分）

No.12345678910

Answer

1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

x=2;

while（x<n/2）

x=2*x+l;

A.O（log2n）B.O（n）C.O（nlog2n）D.O（n2）

2.以下数据结构中，（）是非线性数据结构

A.树B.字符串C.队D.栈

3.由3个结点可以构造出多少种不同的二叉树？（）

A.2B.3C.4D.5

4.设哈希表长为14,哈希函数是H（key）=key%ll,表中已有数据的关键字为15,38,61,84

共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的

位置是（）

A.8B.3C.5D.9

5.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是

（）。

A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80

C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40

6.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。

A.G中有弧<Vi,Vj>B.G中有一条从Vi到Vj的路径

C.G中没有弧<Vi,Vj>D.G中有一条从Vj到Vi的路径

7.以下没有采用存储转发技术的交换方式是（）。

A.电路交换

B.报文交换

C.分组交换

D.信元交换

8.在以太网中，当一台主机发送数据时，总线上所有计算机都能检测到这个数据信号，只

有数据帧中的目的地址与某主机的地址一致时，该主机才接收这个数据帧。这里所提到的

地址是()。

A.MAC地址

B.IP地址

C.端口

D.地理位置

9.局域网的协议结构一般不包括(

A.网络层

B.数据链路层

C.物理层

D.媒体访问控制层

10.考虑在一条1000米长的电缆(无中继器)上建立一个1Gb/s速率的CSMA/CD网

络，假定信号在电缆中的速度为2*108米/秒。最小帧长是()。

A.1220字节

B.1230字节

C.1280字节

D.1250字节

四.简答题(60分)

1.某算法的计算时间为：T(n)=4T(n/2)+O(n),其中T(l)=0(1),求其时间复杂

度，写出具体过程。

2.采用哈希函数H(k)=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间

[0..12]中对关键字序列22,41,53,46,30,13,1,67,5k

(1)构造哈希表(画示意图)；

(2)装填因子；

(3)成功的平均查找长度。

(4)不成功的平均查找长度。

3.已知待排序的序列为（503,87,512,61,908,170,897,275,653,462）,试完成

下列各题。（12分）

（1）根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。

（2）输出最小值后，如何得到次小值。（并画出相应结果图）

4.欲构建一个数据传输率为1Gb/s的千兆以太网，假设电缆长度为1km,其中无中继器,

信号在电缆中的传播速度为2*108m/s»则帧的最小长度是多少？

5.一个自治系统有5个局域网，如下图所示，LAN2至LAN5上的主机数分别为：91、

150、3和15,该自治系统分配到的IP地址块为30.138.118/23,试给出每一个局域网的

地址块（包括前缀）。

LAN2,91台主机LAN3,150台主机LAN4,3台主机

LAN5,15台主机

LANI

五.算法设计（20分）

（请使用类C语言进行编程，如果编码困难可以写伪代码，会适当扣分）

设计非递归算法求树的深度。（20分）

typedefstructBiTree（

intdata；

structBiTree*rchild；

structBiTree*lchild；

}*BiTree；

2018年招收攻读硕士研究生

入学考试自主命题试题

考试科目及代码：933计算机基础（数据结构、计算机网络）

适用专业：081200计算机科学技术083900网络空间安全

085211计算机技术

（所■答案都必须与在答电欲上，写左锹教欷上及草稿歆上无效，

考竟后徐蹶履率夏皴拿命，

模拟卷二（箴版）参考答案

填空题（20分，每题2分）

1.广义表（a,（a,b）,d,e,（（i,j）,k））的长度是耳，深度是,

2.循环队列用数组A［Om-1］存放其元素值，已知其头尾指针分别是front和rear,则当

前队列的元素个数是（rear-front+m）%川。。

3.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为

瓯］,在给定值为X的结点后插入一个新结点的时间复杂度为国。

4.已知数组A［0..9,0..9］的每个元素占5个存储单元，将其按行优先次序存储在起始地

址为1000的连续的内存单元中，则元素A［6,8］的地址为回。

5.高度为K的完全二叉树至少有四个叶子结点。

6.如果含n个顶点的图形形成一个环，则它有臼棵生成树。

7.IP使用D类地址支持多播，其地址范围是1224.0.0.0~239.255.255.255

8.目前常用的四种信道复用方式是：|频分复用|、时分复用、|码分复用|和波分复

用。

9.在路由表中，对第一条路由最主要的是|目的网络地址|和|下一跳地址|。

10.一个TCP报文段分为首部和陋两部分，TCP首部的最小长度是网字节。

判断题（20分，每个2分）

No.12345678910

AnswerXXqqXXXqX

1.数组是同类型值的集合。（x）

2.取线性表的第i个元素的时间同i的大小有关.（X）

3.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.

（4）

4.一个广义表可以为其它广义表所共享。（4）

5.最小生成树的KRUSKAL算法是一种贪心法（GREEDY）。（4）

6.当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。

（X）

7.TCP适用于组播和广播通信方式，而UDP只适用于单播。（x）

8.0SI参考模型中的数据链路层的主要功能是负责分组流控制、差错控制等。

（x）

9.应用层的网络应用程序分为直接网络应用和间接网络应用两类。（4）

10.RIP是一种距离矢量路由选择算法，现在仍然广泛使用，适合于大型网络。

（x）

三.选择题（30分，每个3分）

No.12345678910

AnswerAADDCDAAAD

1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（A）。

x=2;

while(x<n/2)

x=2*x+l;

A.O(log2n)B.O(n)

C.O（nlog2n）D.O（n2）

2.以下数据结构中，（A）是非线性数据结构

A.树B.字符串C.队D.栈

3.由3个结点可以构造出多少种不同的二叉树？（D）

A.2B.3C.4D.5

4.设哈希表长为14,哈希函数是H（key尸key%11,表中己有数据的关键字为15,38,61,84

共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的

位置是（D）

A.8B.3C.5D.9

5.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是

（C）。

A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80

C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40

6.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前,则下列情形不可能出现的是（D）。

A.G中有弧<Vi,Vj>B.G中有一条从Vi到Vj的路径

C.G中没有弧<Vi,Vj>D.G中有一条从Vj到Vi的路径

7.以下没有采用存储转发技术的交换方式是（A）。

A.电路交换

B.报文交换

C.分组交换

D.信元交换

【解析】“电路交换”又称为“线路交换”，是一种面向连接的服务。电路交换没有采用存储转

发机制，而报文交换和分组交换则采用了存储转发机制。

8.在以太网中，当一台主机发送数据时，总线上所有计算机都能检测到这个数据信号，只

有数据帧中的目的地址与某主机的地址一致时，该主机才接收这个数据帧。这里所提到的

地址是（A）。

A.MAC地址

B.IP地址

C.端口

D.地理位置

【解析】数据帧中的源地址和目的地址指的是MAC地址。

9.局域网的协议结构一般不包括（A）。

A.网络层

B.数据链路层

C.物理层

D.媒体访问控制层

【解析】局域网中的所有主机都处于同一个网段中，不需要路由器或更上层设备将数据转发

到不同网段，在局域网中只需要物理地址就可以实现主机间的通信，物理地址属于数据链路

层的地址，因此局域网仅涉及数据链路层和物理层，不会包括网络层及其上层。

10.考虑在一条1000米长的电缆（无中继器）上建立一个1Gb/s速率的CSMA/CD网

络，假定信号在电缆中的速度为2*108米/秒。最小帧长是（D）。

A.1220字节

B.1230字节

C.1280字节

D.1250字节

【解析】本题考查最小帧长的计算，信道中的往返传播延时=2*1000/（2*108）=10ps

=10-5so在1Gb/s即109b/s的速率下，所以最小帧长=数据发送速率*往返传播延

时=109*10—5=10000b=1250字节。

四.简答题(60分)

1.某算法的计算时间为：T(n)=4T(n/2)+O(n),其中T(l)=0(1),求其时间复杂

度，写出具体过程。

答：

假设有递推关系式T(")=aT(m)+f(")，其中"为问题规模，.为递推的子问题数量，£为每个子问题的规模(假设

每个子问题的效模基本一样)，/5)为递推以外进行的计算工作。

ail,A1为常数，*n)为函数，T(n)为非负整数。则有以下结果：

(D若/■(")=0(/08“-'),£>0,那么7'(“)=6(/°8»")

⑵若/(”)=e"咱"),T(”)=e("啕alogn)

(3)若f(")=Q(”iog"+e),f>0,且对于某个常数c<1和所有充分大的"有a/(m)V<7(”),那么

T(n)=O(f(n)).

设T(n)=4T(n/2)+n,

则a=4,b=2,f(n)=n,代入得T(n)=O(n2)。

2.采用哈希函数H(k)=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间

[0..12]中对关键字序列22,41,53,46,30,13,1,67,51.

(1)构造哈希表(画示意图)；

(2)装填因子；

(3)成功的平均查找长度。

(4)不成功的平均查找长度。

答：

(1)

散列地址0123456789101112

关键字13225314167465130

比较次数111212111

(2)装填因子=9/13=0.7(3)ASLs*=ll/9(4)ASLx=29/13

3.已知待排序的序列为(503,87,512,61,908,170,897,275,653,462),试完成

下列各题。(12分)

(3)根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。

(4)输出最小值后，如何得到次小值。(并画出相应结果图)

答：

回画画画回回

(2)求次小值

908

4.欲构建一个数据传输率为1Gb/s的千兆以太网，假设电缆长度为1km,其中无中继器，

信号在电缆中的传播速度为2*108m/s。则帧的最小长度是多少？

答：已知电缆的长度为1km,信号在电缆中的传播速度为2*108m/s,则信号的单向传播

时延为1/200000s,

往返时延=2*1/200000=1/100000s,即为该网络的争用期。为了按照CSMA/CD的方

式，最小帧的发送时间不能小于1/100000s,否则会被当成无效帧。以1Gb/s

的数据传输速率发送数据，1/100000s内可发送的比特数为109*1/100000=10kb。因

此，帧的最小长度为10kb。

5.一个自治系统有5个局域网，如下图所示，LAN2至LAN5上的主机数分别为：91、

150、3和15,该自治系统分配到的IP地址块为30.138.118/23,试给出每一个局域网的

地址块(包括前缀)。

LAN2,91台主机LAN3,150台主机LAN4,3台主机

LANI

答：分配网络前缀应先分配地址数较多的前缀。已知该自治系统分配到的IP地址块为

30.138.118/23o

LAN3：主机数150,由于(27—2)<150+1<(28—2),所以主机号为8bit,网络前缀为24bit。

取第24位为

0,分配地址块/24,

LAN2：主机数91,由于(26—2)<91+1<(27—2),所以主机号为7bit,网络前缀为25bit。

取第24,25位

10,分配地址块/25»

LAN5：主机数为15,由于(24—2)VI5+l<(25—2),所以主机号为5bit,网络前缀27bit»

取第24,25,

26,27位为1110,分配的地址块为92/27«

LAN1：共有3个路由器，再加上一个网关地址，至少需要4个IP地址。由于(22—

2)<3+1<(23-2),所以主机号为3bit,网络前缀29bit。取第24,25,26,27,28,29

位为111101,分配的地址块为32/29»

LAN4：主机数为3,由于Q2—2)V3+1V(23—2),所以主机号为3bit,网络前缀29bit。

取第24,25,26,27,28,29位为111110,分配的地址块为40/29o

五.算法设计(20分)

(请使用类C语言进行编程，如果编码困难可以写伪代码，会适当扣分)

设计非递归算法求树的深度。(20分)

typedefstructBiTree{

intdata；

structBiTree*rchild；

structBiTree*lchild；

}*BiTree；

[题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一

子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子

树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。

intheight(CSTreet)〃非递归遍历求以孩子兄弟链表表示的树的深度

{if(t==null)return(O);else{intfront=1,rear=1;//front,rear是队头队尾

元素的指针

intlast=l,h=O;//last指向树中同层结点中最后一个结点，h是树的高度

Q[rear]=t;//Q是以树中结点为元素的队列

while(front<=last)

{t=Q[front++l;〃队头出列while(t!=null)

〃层次遍历

{if(t->firstchild)Q[++rear]=t->firstchild;〃第一子女入队t=t->nextsibling;〃同

层兄弟指针后移

)

if(front>last)//本层结束，深度加1(初始深度为0)

{h++;last=rear;}//last再移到指向当前层最右一个结点

}//while(front<=last)

}//else

}//Height

2018年招收攻读硕士研究生

入学考试自主命题试题

考试科目及代码：933计算机基础（数据结构、计算机网络）

适用专业：08用00计算机科学技术083900网络空间安全

085211计算机技术

（所■答案都必须与在入耍欲上，写成锹耍欷上及草稿歆上无效，

考竟后徐耍成率敢皴衮®，

模拟卷三（僦版）

填空题（20分，每题2分）

1.队列的插入操作是在队列的进行，删除操作是在队列的进行。

2.广义表A=（a,（a,b）,（（a,b）,c））,则它的深度为,它的长度为.

3.二叉树是指度为2的树。一棵结点数为N的二叉树，其所有结点的度的总和

是o

4.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用排序：