2016年攻读硕士学位研究生入学考试试题考试科目：计算机科学专业基础综合
科目代码:874＃
适用专业：计算机科学与技术.计算机应用技术.计算机技术.软件工程
（试题共9页）（答案必须写在答题纸上，写在试题上不给分）
数据结构与算法分析（共65分）
一.单项选择题（每小题2分，共18小题，共36分）
1.程序段
for(i=n-1;>=1;--i)
for(j=i;j<i;++j)
if(A[j])ali与al+1对换;
其中n为正整数，则最后一行的语句最多执行（）次。
A.O(n)
B.O(n2)
C.O(n3)
D.O(nlogn)
2.将两个有N个元素的有序表归并成一个有序表，其最少比较次数为（）。
A.N
B.2N
C.N-1
D.2N-2
3.下列编码中属前缀编码的是（）
A.｛1，01，000，001｝
B.｛0，1，00，11
C.｛0，10，110，11｝
D.｛1，01，011，010｝
4.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（）
A.O(1)BO(n)  C.O(nlogn)  D.O(n2)
5.若用一个不带头结点的循环单链表表示队列，则最好用（）标识链队。
A.首结点指针B尾结点指针
C.首结点和尾结点两个指针D任何结点指针
6.一个10阶对称矩阵10]采用压缩存储方式，将其下三角和主对角部分按行优先存储到一维数组]中，则A[5][8]元素在B中的位置k是（）。
A.32
B.37
C.45
D.60
7.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（）
A.直接插入排序
B.起泡排序
C.快速排序
D.基数排序
8.采用邻接矩阵表示一个具有n个顶点m条边的无向图，该矩阵的大小是（）。
A.2n*2m
B.m*m
C.n*m
D.n*n
9.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
A.99
B.100
C.101
D.102
10.以下关于广度优先遍历算法的叙述中正确的是
A.广度优先历算法不适合有向图。
B.对任何有向图调用一次广度优先遍历算法便可访问所有的顶点
C.对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点
D.对任何非强连通图都需要多次调用广度优先遍历算法才可访问所有的顶点
11.对某个带权连通图构造最小生成树，以下说法中正确的是（）。
Ⅰ.该图的所有最小生成树的总代价一定是唯一的
Ⅱ.该图中所有权值最小的边一定都会出现在所有的最小生成树中
Ⅲ.用普里姆（Prim）算法从不同顶点开始构造的所有最小生成树一定相同
Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A.仅Ⅰ
B.仅Ⅱ
C.仅Ⅰ、Ⅲ
D.仅Ⅱ、Ⅳ
12.求解单源点最短路径的Dijkstra算法和所有顶点对最短路径的Floyd-Warshall算法分别使用了设计算法的（1）和（2）技术
A.贪心，动态规划
B.动态规划，贪心
C.贪心，贪心
D.动态规划，动态规划
13.在某个有向图G的拓扑序列中，顶点i在顶点j之前，则以下情况不可能出现的是
A.G中有边<i，j>
C.G中没有边<i，j>
B.G中有一条从顶点i到顶点j的路径
D.G中有一条从顶点j到顶点i的路径
14.为便于判别有向图中是否存在回路，可借助于（）
A.广度优先搜索算法  C.拓扑排序算法
B.最小生成树算法  D.最短路径算法
15.在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左.右子结点中保存的关键字分别是（）
A.13，48
B.24，48
C.24，53数据结构与算法考研真题
D.24，90
16.已知一棵完全二叉树的第6层（设根为第1层）有11个叶结点，则完全二叉树的结点个数最多是（）
A.42
B.55
C.114
D.122
17.某线性表中有100000个元素，其中前99990个元素递增有序，则采用（）方法进行递增排序时关键字比较次数最少
A简单选择排序  B.直接插入排序
C.二路归并排序
D.快速排序
18.设栈的初始状态为空，进栈序列为1.2.3.4.5.6，若出栈序列为2.4.3.6.5.1，则操作过程中中元素个数最多时是（）。
A.1个
B.2个
C.3个
D.4个
二.综合应用题（共2小题，共29分）
19.（14分）已知一个带有表头结点的单链表，结点结构为data llink。假设该链表只给出了头指针list（类型为LinKlist）。在不改变链表的前提下，请设计一个尽可能高效的算法，查链表中倒数第k个位置上的结点（k为正整数）。若查成功，算法输出该结点的data值，并返回1，否则，只返回0。要求:
（1）描述算法的基本设计思想（4分）
（2）描述算法的详细实现步骤（4分）
（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释（6分）
20.（15分）设G=(V,E)是赋权有向图，其中一个顶点为s。每条边的权值均为取自｛0，1，…K｝的正整数。试设计算法，计算由s到其他顶点的最短路径，使算法时间复杂性达到(O((V+E)logK)。
计算机网络（共35分）
一.单项选择题（共8小题，每小题2分，共16分）
1.在OSI（open system interconnect）参考模型中以太网技术属于以下哪一层（）
A.物理层
B.数据链路层
C.网络层
D.传输层
2.一个总线型以太网，电缆总长度为1km，电缆中信号的传播速率为2×108m/s；帧长为104比特，为了保证CSMA/CD协议工作的正确性，该网络最大传输速率为（）
A.1Mbps
B.2Mbps
C.2Gbps
D.1Gbps
3.PPP协议为实现透明传输在异步传输时采用（），在同步传输时采用（）。
A.字符填充法，比特填充法
B.比特填充法，字符填充法
C.字符填充法，字符计数法
D.字符计数法，字符填充法
4.下列协议中，与系统没有直接关系的是（）
A.SMTP
B.POP3
C.MIME
D.SNMP
5.主机A为了与主机B建立连接发送一个含有（SYN=1，seq=11220）的TCP段，若主机B 接受该连接请求，那么主机B向主机A最有可能是发送下面哪个TCP段（）
A.（SYN=0，ACK=0，seq=11221，ack=11221）
B.（SYN=1，ACk=1，seq=11220，ack=11220）
C.（SYN=1，ACK=1，seq=11221，ack=11221）
D.（SYN=0，ACK=0，seq=11220，ack=11220）
6.下列中，不属于网络体系结构所描述的内容是（）
A.网络的层次
B.对等层之间的协议
C.层与层之间的接口
D.协议的实现细节
7.IP分组经过路由器转发时，如果不被分片，则（）
A.TTL字段和校验和字段值均会被改变；
B.TTL字段和IP地址字段均会被改变；
C.DF和MF字段的值均会被改变；
D.IP地址字段和首部长度字段均会被改变。
8.A计算机和B计算机的IP地址分别为216.12.31.20和216.13.32.21，要想让A和B工作在同一IP网络，应该给它们分配的子网掩码是（）
A255.255.255.0B255.255.0.0C255.0.0.0D255.255.192.0
二.应用题（共2小题，共19分）
1.（6分）动态路由协议通过网络节点之间交换某些信息，计算从自己到所有其它节点的路径，生成本地的路由表。常见的距离矢量路由协议和链路状态路由协议都属于动态路由协议。根据所学知识，回答下面问题:
1）两种路由协议在实现信息交换过程中，交换的内容.交换的对象和交换的时机有何区别？2）距离矢量路由算法为什么会出现计数到无穷问题（无穷计数）？
3）常见的RIP协议和OSPF协议各属于哪种路由协议（距离矢量或链路状态）？
2.（13分）某学校网络拓扑结构如下图所示。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。