1、第1页共 5页三 峡 大 学2014年研究生入学考试试题(A卷)科目代码：837 科目名称： 计算机综合 考试时间为3小时，卷面总分为150分答案必须写在答题纸上数据结构部分（75分）一、填空题 (每小题 2分，共 20分)1. 线性表采用链式存储时，结点的存储地址（ ）A必须是不连续的 B.连续与否均可C必须是连续的 D.和头结点的存储地址相连续2、设有一个顺序栈H，元素按H1,H2,H3,H4.H5,H6顺序进栈，若6个元素的出栈顺序为H2, H3, H4，H6，H5，H1，则顺序栈的容量至少应为（ ）。A. 2 B.3 C. 4 D.53. 已知循环队列容量为10，采用空闲单元法区分队满
2、队空，f=3，r=7，则队列长度是（ ）A3 B.4 C. 5 D.64、设有一个二维数A1010，假设A00存放位置在644，按行优先存储，每个元素占一个空间，A44在（ ）位置。A680 B.686 C.687 D.6885、20个结点的二叉树最少有（ ）层A、5 B、6 C、4 D、206、在含n个顶点和e条边的无向图的邻接矩阵中，非零元素的个数为（ ）A.e B.2e C.n2-e D.n2-2e7. 设有40个有序的元素，采用折半搜索时，最大比较次数为（ ）A.4 B.5 C. 6 D.78设有5个字符出现的频度分别为1,2,3,5, 4，则对应的哈夫曼树的带权路径长度为（ ）A、3
3、4 B、33 C、35 D、15第2页9已知待散列的线性表为（28，21，27，35，6），假定选用的散列函数是H（K）= K % 7，则冲突最大次数是（ ）A、0 B、1 C、2 D、310、对于无序大数据，排序效率最高的算法是（ ）A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接插入排序二、判断题题 (每题2分，共10分, 对的打，错的打)1.对于最大指数很大，非零项很多的一元多项式加法适合采用顺序存储结构存储。（ ）2. 采用空闲单元法的循环队列空间利用率小于1。（ ）3. 给定二叉树先序遍历序列和后序遍历序列不能唯一确定树结构。（ ）4. 给定结点权重的哈弗曼树，树结构和结点编
4、码可能不唯一，但带权路径和唯一。（ ）5.图的某一关键活动时间减少可能不能减少关键路径长度。（ ）三、计算题（需要过程） (共45分)1. 已知一完全二叉树有501个结点，试计算其中n0、n1和n2的个数！（5分）2. 已知某二叉树先序遍历结果为GBCDEF，中序遍历果为BCGEFD，请画出该树结构，并求其后序遍历结果和层序遍历结果. （10分）3. 根据左图回答问题（15分）（1）若将上图看成一个AOV网，并约定当存在多个入度为0的结点时先输出编号较小的结点，则请写出拓扑排序结果。（5分）（2）忽略边的方向性，给出以v1为起点的深度优先和广度优先遍历序列（4分）（3）若将上图看成无向网，各边
5、权值为活动持续时间，请给出该无向网的一棵最小生成树。（6分） 第3页4.已知待排序关键字序列是3，6，5，8，1，4，2请给出按下列排序规则排序 一趟之后的数据序列，要求排成升序序列。（15分）（1） 直接插入排序 （3分）（2） 快速排序（4分）（3） 简单选择排序（3分）（4） 堆排序的初始堆（第一个元素出堆前）（5分）计算机网络部分（75分）一、 单项选择题（每小题 2 分，共 20 分)1) 在数据加密中DES属于（ ）A. 非对称密钥密码体制 B. 加密密钥 C. 对称密钥密码体制 D. 解密密钥2) 以下不属于内部网关协议的是( )ARIP B. OSPF C. BGP D. RI
6、P23) 在物理层扩展局域网所用的设备是（ ）A. 路由器 B. 交换机C. 集线器 D. 调制解调器4) 域名解析的作用是（ ）A. 寻找目的域名的IP地址 B. 将IP地址映射为物理地址C. 将IP地址映射为子网掩码 D. 将子网掩码转换为网络地址5) C类IP地址的默认子网掩码是（ ）A.255.255.255.0 B.255.128.0.0C.0xFFFF0000 D.111.111.0.06) 假设网络地址为192.168.35.0，子网掩码为/28，则这个网络中可用的子网数和主机数分别是（ ）A6个子网/64台主机 B14个子网/32台主机C14个子网/14台主机 D30个子网/6
7、4台主机7) 以下的地址前缀中的哪一个地址和2.52.90.140匹配（ ）A. 0/4 B. 32/4 C. 4/6 D. 80/48) UDP是TCP/IP 参考模型中哪一层的协议（ ）A. 应用层 B. 传输层C. 网络层D. 数据链路层9) RARP协议是用来（ ）A. 寻找目的域名的IP地址 B. 将物理地址转为IP地址映射C. 将IP地址映射为子网掩码 D. 将子网掩码转换为网络地址第4页10) 以下几种描述不正确的是（ ）A. 常规密钥密码体制所使用的加密密钥和解密密钥是相同的B. 公开密钥密码体制使用不同的加密密钥和解密密钥C. 公开密钥加密方法要比传统的加密方法更加安全D.
8、报文鉴别可以用于对付主动攻击中的篡改和伪造二、 计算题( 共35 分) 1. 下图表示有五个站点分别连接在三个局域网上，并且用网桥B1和B2连接起来。每一个网桥都有两个接口（1和2）。在一开始，两个网桥中的转发表都是空的。以后有以下各站点向其他的站点发送了数据帧：A发送给E，C发送给B，D发送给C，B发送给A，网桥通过这些过程学习转发表，请按要求把有关数据补充在对应的表项中（请注意要写到答题纸上）。（此题20分）发送的帧B1的转发表B2的转发表B1的处理B2的处理地址接口地址接口A-EAA1转发，写入转发表C-BCC转发，写入转发表转发，写入转发表D-CD2D写入转发表，丢弃不转发转发，写入转
9、发表B-A接收不到这个帧2假定网络中路由器S的路由表中有如下项目(选用RIP协议)目的网络距离下一跳N18AN23CN69FN98F现在S收到从路由器C发来的路由信息，经过更新后，S的路由表变为：目的网络距离下一跳N17CN26CN310CN66CN95C第5页请求出路由器C发来的路由信息（答案用表格表示，所包含的两列分别为“目的网络”和“距离”）（此题15分）三、分析题 （共 20 分）1、已知地址块中的一个地址是140.120.84.24/20。试求这个地址块中的最小地址和最大地址；地址块中共有多少地址；相当于多少个C类地址（此题8分）。2. 已知某网络的连接拓扑如下图所示，请根据拓扑结构并按照给出的路由表内容格式写出路由器R1中到达各网络的路由表项（此题12分）。 地址掩码目的网络地址下一跳地址路由器接口
