《华中科技大学-834-2017-真题》由会员分享，可在线阅读，更多相关《华中科技大学-834-2017-真题（8页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 2017 年招收攻读硕士研究生 入学考试自主命题试题 考试科目及代码: 834 计算机专业基础综合(数据结构、计算机网络) 适用专业: 计算机系统结构、计算机软件与理论、计算机应用技术、网络空间安全、计算机技术、项目管理、控制科学与工程 (所有答案都必须写在答题纸上，写在试题纸上及草稿纸上无效，考完后试题随答题纸交回) 数据结构部分（90 分）一、选择题（20 分，每题 2 分） 1. 二元组形式表为 A=(D,R),D=01,02,03,04,05R=r,r=,则数据结构 A 是( )。 A.集合B.树形结构C.线性结构D.图形结构2.下列存储结构中， （ ）适合作为队列的存储
2、结构。 A.采用尾指针的单链表B.采用头指针的循环单链表C.采用尾指针的循环单链表 D.采用头指针的单链表 3.如下程序段的时间复杂度为( ） 。 viod main() int s=0,i=0; do i=i+1; 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研s=s+i; while( inext=s;s=-pre=p;p-next-pre=s;s-next=p-next; B.s-
3、pre=p;s-next=p-next;p-next=s;p-next-pre=s; C.s-pre=p;s-next=p-next;p-next-pre=s;p-next=s; D.p-next=s;p-next-pre=s;s-pre=p;s-next=p-next; 6.已知 s=”abacbabcaccab”,串 t1=“aba”串 t2=“cba” ，函数 index(s,t)的返回值为串t 在串 s 中首次出现的位置。 经过操作序列： SubString（s1，s，1，index（s,t2） ）; SubString(s2,s,index(s,t1),2); Concat(T,s2
4、,s1); 则串 t 为( )。 A. abaabac B. abababc C.babbac D. ababac 7.设输入序列是 1,2,3,.n,经过栈的作用后输出序列的第一个元素是 n，则输入序列中的 i 在第（ ）个输出。 A. i B.n-i C.n-i-1 D.n-i+1 8.设连通图 G 中的边集 E=（A,B）,(A,C),(A,D),(A,F),(B,F),(F,D),(D,C),(D,E),则从顶点 A 出发可以得到一种深度优先遍历的顶点序列为（ ） 。 A.ACEDFB B.ADFCEB C.ABFDEC D.ABFCDE 9.时间复杂度不受数据初始状态影响而始终为 O
5、(nlog2n)的是（ ） 。 A.快速排序 B.冒泡排序 C.基数排序 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研D.堆排序 10.设无向图中有 n 个顶点 e 条边，则建立该图邻接表的时间复杂度为( )。 A.O(n2) B.O(n+e) C.O(n*e) D.O(n3) 二填空题(10 分，每题 1 分） 1. 设带有头结点的单向循环链表的头指针变量为 head，则其判空条件是
6、 。 2. 设一课 m 叉树中度数为 0 的结点为 X，度数为 1 的结点为 N1，以此类推，度数为 m的结点数为 Nm，则 X= 。 3. 设有向图 G 中有 n 个顶点 e 条有向边，所有顶点度数之和为 d，则 e 和 d 关系为e=2d。 4. 设后序遍历某二叉树的序列为 ABCD,中序遍历该二叉树的序列为 BADC,则前序遍历该二叉树的序列为 。 5. 假设二维数组 A45按行优先顺序存储，若每个元素占 2 个存储单元，元素 A00的存储地址为 1000，则下标变量 A32的存储地址为 。 6. 广义表（ （a,b） ，c， （d） ， （e， （） ） ，f）的表尾是 。 7. 设顺
7、序线性表有 n 个数据元素，删除第 i 个位置的数据元素需要移动表中 个数据元素。 8. 设一组初始关键字序列为（38，65，97，76，13，38，10） ，则按递增顺序第四趟冒泡排序的结果为 . 9. 设有一个循环队列中有 m 个存储单元，则该循环队列中最多能够存储 个队列元素（设头指针 f 指向当前队头元素的位置，尾指针 r 指向当前队尾元素的后一个位置） 。 10. 设一组初始记录关键字序列为（21，19，23，16，30，20） ，则以 21 为中轴的一趟快速排序的结果为 . 三判断题（10 分，每题 1 分） No. 1 2 3 4 5 6 7 8 9 10 Answer 1. 有
8、向图的邻接表和逆邻接表中表结点的个数不一定相等。( ) 2. 对链表进行插入和删除操作时需要移动链表中结点。( ) 3. 堆是完全二叉树，完全二叉树不一定是堆。（ ） 4. 由树转化成二叉树，该二叉树的右子树不一定为空。( ) 5. 向一棵 B 树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少 1。 （ ） 6. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。( ) 7. 在哈希表的构造中，使用线性探测再散列法处理冲突，所有同义词在 HASH 表中位置相邻。( ) 8. 数据元素是数据的最小单位。（ ） 各个学校计算机/软件专业考研真题 免费分享
9、 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研9.当向二叉树插入一个结点,则该结点一定成为叶子结点。 （ ） 10.入栈操作和入队操作在顺序存储结构上实现时都需要考虑溢出的情况。 （ ) 四简答题（40 分） 1.以 1 为出发点运用 Prime 算法给出该图的最小生成树，并计算出最小生成树各边上的权值之和。2. 采用哈希函数（k）=3*k mod 13 并用线性探测开放地址法处理冲突，在数列地址空间0.12中对关键字序列 22
10、,41,53,46,30,13,1,67,51。（1）构造哈希表（画示意图） ；（2）装填因子； （3）成功的平均查找长度。 （4）不成功的平均查找长度。 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 3. 6，5，4，3，2，1利用数组建成一个最小堆并使用堆排序将其排序成唯一的降序数组。要求画出所有中间过程。 4. 将下列由三棵树组成的森林转换为二叉树。 （只要求给出转换结果） 五算
11、法设计（10 分） （请使用类 C 语言进行编程，如果编码困难可以写伪代码，会适当扣分） 1.假设以带头结点的单链表为有序表，单链表的类型定义如下： Typeddf struct LNode Element Type data; Struct LNode *next; LNode, *LinkList; 编写算法 Delete（LinkList &A, LinkList&B）从有序表 A 中删除所有和有序表 B 中元素相同的结点。 (1) 描述算法思想。 (2) 用 C 语言写出算法函数。 (3) 分析算法的时间复杂度。 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g
12、i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 计算机网络部分（60 分） 一、选择题（20 分，每题 2 分） 1. 为了使数据在网络中的传输延迟最小，首选的交换方式是（ ） 。 A电路交换 B报文交换 C分组交换 D信元交换 2. 在开放系统互连环境中，两个 N 层实体进行通信，可能用到的服务是（ ） 。 AN-1 层提供的服务 BN 层提供的服务 CN1 层提供的服务 D以上都不对 3. 内部网关协议包括（ ） 。 AOSPF 和 IGP BOSPF
13、和 EGP CRIP 和 BGP DOSPF 和 RIP 4. UDP 数据报比 IP 数据报多提供了（ ）服务。 A流量控制 B拥塞控制 C端口功能 D路由转发 5. IP 层的功能不包括（ ） 。 A差错处理 B数据报路由选择 C无连接的数据报传输 D提供可靠连接 6. 假如用 5 个路由器将 6 个网络互连，使用链路状态路由算法，需要（ ）个路由表。 A1 B5 C6 D11 7. TCP 协议中发送窗口的大小应该是（ ） 。 A通知窗口的大小 B拥塞窗口的大小 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y
14、 /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研C通知窗口和拥塞窗口中较小的一个 D通知窗口和拥塞窗口中较大的一个 8. 某部门申请到一个 C 类 IP 地址，若要分成 8 个子网，其掩码应为（ ） 。 A255.255.255.255 B255.255.255.0 C255.255.255.224 D255.255.255.192 9. 下面 IP 地址属于 B 类 IP 地址的是（ ） 。 A130.111.168.1 B128.108.111.2 C202.199.1.35 D294.125.13.110
15、10. 一个路由器有两个端口，分别接到两个网络，两个网络各有一个主机，IP 地址分别为 110.25.53.1 和 110.24.52.6，子网掩码均为 255.255.255.0，可分配给路由器两个端口的两个 IP 地址分别是（ ） 。 A110.25.52.1 和 110.24.52.6 B111.25.53.1 和 111.25.53.6 C110.25.53.6 和 110.24.52.1 D110.25.53.1 和 110.24.53.6 二填空题(10 分，每题 1 分） 1. CDMA 系统中使用的多路复用技术是 。 2. 计算机网络最主要的两个性能指标是 。 3. 将主机名转
16、换成 IP 地址，要使用 协议。 4. ARP 协议负责把 IP 地址转换为 地址。 5. IP 地址的掩码常称为子网掩码，这是因为 。 6. 在数据链路层数据包的名称通常称为 。 7. 某单位分配到一个地址块 136.23.12.64/26。现在需要进一步划分为 4 个一样大的子网，则每一个子网中的地址数为 。 8. IEEE802.11 采用 协议。 9. IPv6 地址为 128 个比特，其数据报基本首部为固定的 字节。 10. 表示主机比特全为“1”的 IP 地址，为： 的地址。 三简答题（30 分） 1. 在数据传输过程中，若接收方收到的二进制比特序列为 10110011010，接收
17、双方采用的生成多项式为 G （x）x4x31，则该二进制比特序列在传输中是否出错？如果传输没有出现差错，发送数据的比特序列和 CRC 检验码的比特序列分别是什么？ 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研2. 如下图所示有一个移动主机，原来的 IP 地址是 160.80.40.2016，为了移动到其他网络，它将 160.80.40.26 设置为了本地代理。之后它移动到了 179.5
18、6.0.016 的网络中，设置了 179.56.0.1 为外部代理，并且获得了新的 IP 地址 179.56.78.69。请问： （1）如果这时候该主机和其他主机通信，对端需要把数据发给什么地址？ （2）当一个 160.80.40.20 到达 160.80.0.016 网络后，会有主机响应该 ARP 请求吗？ （3）本地代理需要将发送给移动主机的分组发送到哪个地址？ 3. 设某路由器建立如下路由表： 目的网络 子网掩码 下一条路由器 128.96.39.0 255.255.255.128 接口 0 128.96.39.128 255.255.255.128 接口 1 128.96.40.0 2
19、55.255.255.128 R2 192.4.153.0 255.255.255.196 R3 （默认） R4 （1） 现收到 5 个分组，其目的 IP 地址分别为： 128.96.39.10 ， 128.96.40.20 ， 128.96.40.153 ， 192.4.153.12 ，192.4.153.90。 试分别计算其下一跳。 （2）路由协议的作用是什么？ （3）在什么情况下要选择多协议路由器？ 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研
