2013年南京师范大学研究生入学考试初试试题

数据结构部分（共90分）

 

一、           选择题（10分）

1.       若长度为n 线性表采用顺序存储结构，在其第1 个位置插入一个新元素的算法时间复杂度为（    ）。

A  O(o)        B  O(1)        C  O(n)       D  O(n²)

 

2.       表达式 a*(b+c)-d 的后缀表达式是（       ）。

            A  abcd*+-      B  abc+*d-     C  abc*+d-    D -+*abcd

 

3.  某线性表最常用的运算是播入和删除，插入运算是表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用（     ）存储方式最节省运算时间。

   A 仅有尾指针的单向循环链表     B  仅有头指针的单向循环链表

   C  单向链表                    D  双向链表

 

4.  将一个A[ 1…100,1…100]的三角矩阵，按行优先存入一维数组B[1…198]中，A中元素A[66,65]在B数组中的位置k 为（）。

       A  198    B  195     C  197     D  194

 

5. 广义表A=(a,b,(c,d),(e,(f,g)))，则下面式子的值为（    ）。

   Head(Tail(Head(Tail(Tail(A)))))

      A (g)     B（d）   C c     D d

 

6. 在一棵三元树中，度为3的结点数为2个 ，度为2 的结点数为1 个，度为1的结点数为2个，则度为0的结点数为（    ）个。

A  4     B 5    C6     D7

 

7. 判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用（   ）。

A 求关键路径的回路     B 求最短路径的Dijkstra

C 深度优先遍历算法     D 广度优先遍历算法

 

8. 对于一个无向图，下面（）的说法是正确的。

   A 每个顶点的入度等于出度     B 每个顶点的度等于其入度与出度之和

   C 每个顶点的入度为0          D每个顶点的出度为0

 

9. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是（      ）。

A分块查找   B 顺序查找  C  折半查找  D 基于属性查找

10. 设有500个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（      ）排序法。

A 冒泡排序     B 快速排序      C堆排序      D基数排序

 

 

二、           填空题（10分）

1.       算法时间复杂度是指_________________。

2.       n 个数入栈，所有可能的出栈序列共有____________种。

3.       设循环队列Q用牺牲一个单元空间的方法来区分队满和队空状态判断条件，则队满条件可表示为_________________________

4.       已知一棵二叉树的前序遍历序列为ABCD，中序遍历序列为BDCA，则该二叉树的后序遍历序列为____________________

5.       对含有n个顶点的图，Prim算法的时间复杂度为____________

 

三、           应用题（10 x 4）

1.       已知记录关键字集合为｛51，39，28，40，65，64，35，50，24，15｝，要求散列到地址区间[0,10]中，散列函数的选用除留余数法。请现出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决），并给出平均查找长度ASL。

 

 

 

2.       设电文出现的字符为a,b,c,d,e,f，它们在电文中邮现的频繁分别为10%，15%，12%，18%，25%和20%，试设计出最佳编码使电文的编码长度最小。

 

 

 

3.       试用Kruskal 算法求下图的最小生成树，要求给出步骤。

 

 

 

4.       下面的函数对用邻接表表示的有向图的顶点进行拓扑排序。

请在空框处填写适当内容，每个空框只填一个语句。并指出语句（1）的功能是什么？语句（2）、（3）的功能是什么？语句（4）、（5）的功能是什么？

#define maxn 50

#define maxm 100

typedef struct {   int t_ver ;

               int h_ver;

             }E_NODE;

typedef struct vl_node { int  ver;

                     Struct vl_node *link;

                    }VL_NODE；

       typedef  struct { int count ;

                      VL_NODE *head;

                     }CH_NODE;

        E_NODE e[maxm];

        CH_NODE ch[maxn];

int tpv[maxn];

int n,m,i,count;

int topol_order(ch,n,tpv)

CH_NODE ch[];

int n,tpv[];

{  int I,j,k;

         int top=0;

  VL_NODE *t;

         for(i=1; i<=n;i++)

        iIf(ch[i].count==0)

        {   top++;

            _______;(1)

        }

       i=0;

while(top!=0)

 {

________;(2)_______(3);

tpv[++i]=j;

t=ch[j].head;

while(t!=NULL) {

k=t->ver;

if(--(ch[k].count)==0)

{

 _____;(4)______;(5)

}

t=t->link;

}

}

return  (i);

}

 

四、           编写算法题（10 x 3）

1.       对给定的n个整数，试写出选择法进行排序的算法，要求将n 个数由小到大排序。

2.       对有n个记录的有序表，试给出折半查找算法（若关键字key在有序中，则返回其位置，否则返回-1）。

3.       若root 为指向某二叉树要结点的指针，试写出一个函数返回度为2、1和0的结点数，并返回该二叉树的层数。

 

 

 

计算机网络部分（共60分）

一、           选择题（每小题2分，共30分）

1.       对于ＯＳＩ／ＲＭ，协议是（  ），上层使用下层提供的（  ），物理层透明传送（  ）。网络协议要素包括语法、语义和（     ）。

A数据   B水平的    C功能     D帧

E同步   D比特流    G服务

2.       在TCP/IP体系中，（  ）是面向连接的可靠协议；（   ）协议无法判断它的数据正确性；（    ）为应用进程之间提供端到端的逻辑通信，（   ）直接为用户的应用进程提供服务。

A数据链路层   B应用层     C运输层     D PPP

E TCP          FIP          G网络

3.       对于PPP帧，（  ）字段表示帧的开始和结束，（  ）字段用于解析信息部分是什么内容，（  ）字段用于检验帧是否出错。对于PPP协议，能够保证数据传输的（    ）性。

A透明      B FCS    C协议    D    CRC

E标志      F控制   G地址

4.       PCM信号采用（   ）；ADSL的上行信道和下行信道采用（   ）；在无线局域网中采用（  ）;地下铺设光缆采用（  ）。

A频分复用   B时分复用    C波分复用    D码分复用

E带宽复用    F集中复用    G统计复用

5.       SDH采用自愈混合的（   ）；目前小区同轴电缆组成的电视网络为（  ）；使用集线器组成的以太网逻辑上为（  ）；使用交换机组成的以太网为（  ）。

A环形结构     B树形结构     C星形结构     D总线结构

E蜂窝结构     F链式结构      G综合结构

6.       对于以太网，MTU为（  ），在（  ）方式下，采用CSMA/CD协议；（  ）决定一个网段的最大距离。（  ）表示广播地址。

A全双工     B半双工    C最小帧长    D最大帧长

E全1        F最大数据字体长度        G EUI-48

7.       IP数据报包括（  ），所以需要填充字段；分片需要（  ）和片偏移等字段配合使用；IP数据报没有包含（  ）字段；路由器根据（  ）查找路由表。

A目的地址     B子网掩码      C标识      D选项

E协议         F区分服务       G生存时间

8.       对于小规模自治系统（AS），路由选择协议采用（   ）；采用（  ）可以将AS划分为区域。（   ）要求每一个AS至少需要一个BGP发言人。BGP支持（），所以路由表中应该包含目的网络前缀。

A  IGP     B  RIP    C  OSPF     DEGP

E  BGP-4   F  CIDR   G  UDP

9.       IP多播采用（  ）作为标识符；在本地局域采用（  ）协议确定多播组成员，多播组路由器之间可以采用（  ）；通过不支持多播的网络需要包装后采用（   ）。

 A 单播      B  MAC地址   C  IGMP   D  ICMP

E  MOSP    F  D类地址    G  多播

10. 一个单位包括AB两个本地网络，采用VPN连接因特网，路由器R(A)连接      A 网和因特网，路由器R(B)连接B网和因特网。A网络主机A1与B网络主机B1通信时，在A网络传送的帧中目的地址为（   ）。在因特网中的IP数据报中目的IP地址为（  ）。A1通过NAT访问因特网服务器，在A网络的IP数据报中源IP地址为（  ），在因特网中的IP数据报中源IP地址为（   ）。

A  R(A)本地网硬件地址  B  R(A)本地IP地址  C  R(A)全球IP地址

D  R(B)本地IP地址     E  R(B)全球IP地址

F  A1本地IP地址       G  B1硬件地址

11. 与TCP协议可靠传输有关的（  ）、（  ）、（  ）和（  ）。

A 全双工通信     B端口     C累积确认    D  TCP报文检验和

E超时重传        F三次握手建立连接       G 拥塞控制

12. 主机通过（  ）可以动态获取IP地址；IP地址转换为硬件地址采用（  ）。采用（  ）路由可以减少路由项目数。（  ）具有自学习功能。

A  RARP    B  ARQ    C 默认   D网桥

E  ISP      F  ARP     G  DHCP

13. 对于网络管理，网络管理员运行的管理进程属于（   ）；SNMP中的（  ）使用TLV表示数据元素，IPAddress 10.1.2.3的TLV编码（T字段40H）为（  ）。在FTP中，服务器的（  ）接收FTP客户的文件传送请求。

A客户进程   B服务器   C代理进程    D 40 05 10 01 02 03

 E 40 04 0A 01 02 03  F SMIF控制进程    G数据传送进程

14. 用户A 向用户B发送明文X，如果采用DES密码体制，算法（）；对于采用RSA体制，A用（）对X加密；对于数字签名，B用（）还原X ；运输层使用（）安全协议。

A保密的    B公开的    C A的公钥    D  B的公钥

E A的私钥   F  B的私钥GSSL    H   IPsec

15. 有固定基础设施的无线局域通过（）构建基本服务集，通过（）连接想来构成（）；为了避免碰撞，采用（）协议。

A  AP    B ESS    C Wi-Fi    D SSID

E  DS    F CSMA/CA  G 802.11

 

二、           计算题（3 x 5）

1.       1000字节在10Km的光纤上传送，发送速率1Mb/s，光纤中的传播速率约为2.0x10⁵Km/s，求发送时延和传播时延。

2.       已知IP地址 206.0.72，130/18，求这个地址所在的地址块中的最大地址。

3.       以太网的多播地址范围为00-00-5E-00-00-00到00-00-5E-FF-FF-FF，求IP多播地址224.129.64.32对应的以太网硬件多播地址。

4.       在100Mb/s以太网上，两个主机的应用进程之间通过UDP传输“欢迎来到南师大。”（不包引号），求以太网的帧长。

5.       求MIME采用quoted-printable方法对“汉hang”(一个汉字3个半角字符)编码后的字节数。

 

三、           说明题（每小题3分，共15分）

因特网有一个用户在浏览器中键入URL为http://www.bbb.cn/b2/sports.htm。说明 ：

1.       该用户主机如何得到Web服务器的IP地址？

2.       这里用户进程和服务器进程分别是什么？

3.       采用HTTP传送网页的大致过程。

4.       HTTP协议无状态和持续连接的好处。

5.       如果通过网页方式发送和接收电子邮件，说明电子邮件传输过程、使用的协议。