三峡大学考研专业课试题837计算机综合2015.doc

1、第1页共 5 页三 峡 大 学2015年研究生入学考试试题(B卷)科目代码： 837 科目名称： 计算机综合 考试时间为3小时，卷面总分为150分答案必须写在答题纸上第一部分：数据结构(共75分)（本套试题出现的代码采用C语言规定）一、单选题 （每题2分，共20分）1. 指针p的值为非空的循环单链表head的尾节点，则p满足（ ）。A. p-next = NULL B. p = NULL C. p-next = head D. p = head2. 线性表若采用链式存储结构，要求内存中使用的存储单元地址满足（ ）。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续不

2、连续都可以3. 往一个长度为n的顺序存储线性表的任一结点前插入一个新结点，平均需要移动（ ）个结点。A. n B.n-1 C. n+1 D.(n+1)/2 4. 若已知一个栈的入栈序列是1,2，,n,其出栈序列是p1,p2,pn, 若p1=n, 则pi为 （ ）。A. i B. n-i C. n-i+1 D. 不确定5. 一个队列的数据入队序列是1,2,3,4，则出队序列是（ ）A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 6. 二维数组A的每个元素的长度是4个字节，行下标i从0到8，列下标j从0到10,从首地址1000开始按行优先方式存放，元素A64

3、的起始地址为（ ）。A. 1276 B. 1280 C. 1284 D.12887 排序方法中，从未排序序列中一次取出元素与已经排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法，称为（ ）A. 希尔排序 B. 冒泡排序 C.插入排序 D.选择排序8 对n个元素的表作快速排序，在最坏情况下，算法的时间复杂度是（ ）A. O(n) B. O(n2) C. O(nlogn) D. O(n3)第 2 页9. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。A4 B5 C6 D710、有8个结点的无向连通图最少有（ ）条边。A

4、6 B7 C8 D9二、填空题 （每空2分，共10分）1. 已知strlen(s)返回字符串s的长度，substr(s,i,len)返回字符串s从第i个字符起长度为len的子串，字符串的首字符序号为0. 现s=”ABCDEFGHIJK”,t=”ABC”, 则strlen(t) =（ ）， substr(s, strlen(t),strlen(t) = ( )2. 设树T的度为4，其中度为1,2,3,4的结点个数分别为4,2,1,1, 则T中的叶子数为（ ）3对于一个具有n个结点的树，该树中所有结点的度数和为（ ）4假定k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行（

5、 ）次探测。三 计算题（共45分）1. 试分别画出具有4个结点的二叉树，其按先序遍历和中序遍历的结点访问序列相同（10分）。2. 有如图1所示的的无向图，试给出其邻接矩阵(5分)和邻接表（5分）。3. 对如图1所示的无向图中，若从顶点0出发进行遍历，分别给出进行深度优先（5分）和广度优先（5分）的结点访问序列。4给定关键字序列3,8,12,19,25,30,34,47，按顺序依次将关键字插入一个空的二叉树中，形成二叉排序树。画出这棵树（5分）并计算在等概率查找情况下，成功查询的平均查找长度（5分）。第 3 页5. 设有关键字序列35,67,42,21,29,86,95,47,50,36,91，

6、散列函数为H(k)=k%11,用链接地址法处理冲突，试将关键字依次插入散列表中（画出散列表示意图，5分）。第二部分：计算机网络（共75分）一、填空题（每空2分，共10分）1. IP地址的编址方法共经历了三个阶段，它们是分类的IP地址，子网的划分和 。2. DES的保密性仅取决于对 的保密，而算法是公开的。3. SNMP协议的中文名称是 。4. 连接到因特网的计算机的协议软件需要配置的项目包括IP地址，子网掩码，默认路由器的IP地址和 。5. TCP运输连接的三个阶段是连接建立，数据传送和 。二、选择题（每题2分，共20分）1. IP地址（IPv4）是由下面哪种形式的二进制数字组成（ ）A、8位

7、 B、16位 C、32位 D、64位2. 以下不属于ICMP差错报告报文种类的是（）A终点不可达 B. 源点抑制 C. 参数问题 D. 网络拥塞3. （ ）是指在一条通信线路中可以同时双向传输数据的方法。A、全双工通信 B、同步通信C、异步通信 D、半双工通信4. 关于IPv4地址的说法，下列（）是错误的A、IP地址由两部分组成：网名地址和主机地址B、网络中的每台主机分配了唯一的IP地址C、IP地址可分为三类：A, B, CD、随着网络主机的增多，IP地址资源将会耗尽5. 在公钥密码体制中，（ ）是公开的A、公钥和私钥B、公钥和算法C、明文和秘文 D、加密密钥和解密密钥第 4 页6. TCP连

8、接的释放需要在客户端和服务器端之间经过（ ）次握手A、1次 B、2次 C、3次 D、4次7. 域名解析的作用是（ ）A、寻找目的域名的IP地址 B、将IP地址映射为物理地址C、将IP地址映射为子网掩码 D、将子网掩码转换为网络地址8. 在OSI模型中，第N层与第Nl层之间的关系是( )AN层为N+1层提供服务BN+1层将从N层接收的信息增加了一个头CN层利用N+1层提供的服务DN层对N+1层没有任何作用9. 以下不属于CSMA/CD协议其核心内容的是（ ）A多点介入 B. 碰撞检测 C. 多路复用 D. 载波监听10.以下几种描述不正确的是（ ）A、常规密钥密码体制所使用的加密密钥和解密密钥是

9、相同的B、公开密钥密码体制使用不同的加密密钥和解密密钥C、报文鉴别可以用于对付主动攻击中的篡改和伪造D、公开密钥加密方法要比传统的加密方法更加安全三、简答题（每题10分，共20分）1. 请说明RIP协议的有缺点及和OSPF的区别2. 拥塞控制与流量控制的区别与联系四、计算题（共25分）1. 已知路由器R1的路由表如下表所示地址掩码目的网络地址下一跳地址路由器接口/26140.5.12.64180.15.2.5m2/24130.5.8.0190.16.6.2m1/16110.71.0.0-m0/16180.15.0.0-m2/16190.16.0.0-m1默认默认110.71.4.5m0第 5 页试画出各网络和必要的路由器的连接拓扑，标注出必要的IP地址和接口。对不能确定的情况应当指明。（15分）2. 某单位分配到一个地址块136.23.12.64/26。现在需要进一步划分为4个一样大的子网。请回答以下问题（共10分）（1） 每个子网的子网前缀是多长？（2） 每一个子网有多少个地址？（3） 每一个子网的地址块是什么？（4） 每一个子网可分配给主机使用的最小地址和最大地址是多少？