昆明理工大学2017年硕士研究生招生入学考试试题(A卷)
考试科目代码：818                考试科目名称 ：计算机学科专业基础综合
考生答题须知
1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。
2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。
3．答题时一律使用蓝、黑墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。
4．答题时不准使用涂改液等具有明显标记的涂改用品。
数据结构部分
一、填空题：（每空1分，共20分）
昆明理工大学2017年硕士研究生招生入学考试试题
4. 多维数组采用的存储结构是　顺序存储　；广义表采用的存储结构是　链式存储　　。
5. 哈希表的查效率主要取决于所选择的  中国继续医学教育网下载哈希函数    与   处理冲突的方法  。
6. 与后缀表达式a b c - d * + ，等价的中缀表达式为    a+(b-c)*d          。
7. 树转换成的二叉树，其根结点的    右 子树一定为空。
二、单项选择题（每题2分，共20分）
1.下面程序段的时间复杂度为（  ）。
  for(i=0;i<n+1;i++)  for(j=0;j<m+1;j++)  A[i][j]=0;
    A.  O(m-1)*O(n-1)  B.  O((m-1)*(n-1))  C.  O((m+1)*(n+1))  D. O(m*n)
2. 从一个长度为n的顺序表中，在第i个元素之前插入一个元素需要向后移动（  ）个元素。
济南市人才网    A.  n-i    深圳招考网2020 B. n-i+1    C. n-i-1    D. i
3. 在一单链表head中，若要在指针q所指的结点后面插入一个由指针p所指的结点，则执行（ ）。
    A. q->next=p->next; p->next=q;    B. p->next=q->next; q=p;
    C. q->next=p; p->next=q->next;    D.p->next=q->next; q->next=p;
4. 若入栈序列为A、B、C、D、E,入栈过程中可以出栈，则不可以是出栈序列（  ）。
    A. ABCDE  B. BCDEA  C. EABCD  D. EDCBA
5. 一链队列中，假设f和r分别为队首指针和队尾指针，则出队列时，下列（  ）语句是必要的。
    A. r=f->next  B. r=r->next  C. f=f->next  D. f=r->next
6. 假定一个顺序循环队列的队首队尾指针分别用front和rear表示，则判断队空的条件是（ ）。
    A. front=rear  B. rear+1=front会计资格评价中心证书查询  C. front=0  D. front+1=rear
7. 以下叙述中，正确的是（  ）。
    A. 线性表的顺序存储结构优于链式存储结构
    B. 网络的最小生成树是唯一的
    C. 二维数组是它的数据元素为线性表的线性表 
    D. 数据的逻辑结构与存储结构都是依赖于计算机的
8. 在一棵完全二叉树中，若编号为j的结点有右孩子，则其编号为（  ）。
    A. 2j    B.  2j+1   C. 2j-1  D.  └j/2┘
9. n个顶点的连通图至少有（  ）条边。
    A. n-1    B. n-2    C. n    D. n+1
10. 一有序表(6,9,11,12,14,17,21,33,37)，当二分查值为11的结点时，（ ）次比较后查成功。
    A.  2  B. 3     C.  4  D. 5  mid=0.5(high+low) 四舍五入
三、完成如下问题（每题5，共,10分）
1.已知二叉树的中序遍历序列为CDBAEGF,后序遍历序列为DCBGFEA,请画出该二叉树。
2. 若一篇文档有以下字符：A、B、C、D、E、F，各字符在文档中出现的概率依次为4,5,6,7,10,12。请构建以各字符为叶子结点的Huffman树，并写出各字符的Huffman编码。（构建时按左小右大、左0右1的规则进行）
四、已知如下无向网络的邻接矩阵（其权值为整型数据）（共25）
1. 用C语言描述网络的邻接矩阵的存储结构。（10分）
2. 写出从顶点4出发的深度优先搜索序列、从顶点1出发的广度优先搜索序列。（6分）
3. 用prim算法思想求最小生成树，要求画出生成过程。（9分）
        1    2    3  4    5    6
1  ∞  3    1  ∞  ∞  ∞
2  3    ∞  2  4    ∞  ∞
3  1    2    ∞  2    ∞  ∞
4  ∞  4    2  ∞  3    4
5  ∞  ∞  ∞  3    ∞  1
6  ∞  ∞  ∞  4    1    ∞
网络部分：
一、单项选择题（每小题1分，总分22分）
1.在OSI参考模型中，自下而上第一个提供端到端服务的层次是（    ）。
A．数据链路层 B.传输层  C.会话层  D.应用层
2.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是（    ）。W = 2 x H x log2V
A．12kbps B.24 kbps  C.48 kbps  D.96 kbps 
3.数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（    ）。
A．2    B.3        C.4        D.5  根据后退N帧协议，接收方的窗口为“1”，如果发送方收到了3号帧的确认，则说明0、1、2、3号帧都已经发送成功，所以只需要重发4、5、6、7号帧即可
4. 在OSI参考模型中，数据链路层的数据服务单元是（    ）。
A.帧  B.报文  C.分组  D.比特序列
5.100BaseT的传输介质是（    ）。
A．3类双绞线  B. 5类双绞线  C.光纤  D.同轴电缆
6. 在TCP/IP协议中，UDP协议是一种（    ）协议。
    A.主机－网络层  B.互联层 C.传输层  D.应用层
7.下面关于VLAN的描述中，正确的是（    ）。
    A.一个VLAN是一个广播域        B.一个VLAN是一个冲突域
    C.一个VLAN必须连接同一个交换机 D.不同VLAN之间不能通信
8.设立数据链路层的主要目的是将一条原始的、有差错的物理线路变为对网络层无差错的（    ）。
    A.物理链路  B.数据链路  C.传输介质  D.端到端连接
9. 世界上第一个计算机网络是在（    ）年诞生。 
    A.1946        B.1969        C.1977        D.1973 
10. 按0比特插入/删除方法规定，在两个标志字段F之间的比特序列中，如果检查出连续的  （    ）个1，不管后面的比特位是0或1，都需要增加一个0。
    A.4      B.5      C.6          D.8
11. 在（    ）差错控制方式中，只会重新传输那些差错的数据帧。
    A.连续工作  B.停止等待  C. 选择重发  D. 拉回
12.IP地址块202.120.80.128/26包含了（    ）个主机地址。
    A.    15        B.    31      C.    62            D.    127
13.以下关于Ethernet帧结构的描述中，错误的是（      ）。
    A. Ethernet V2.0规范和IEEE802.3标准中的Ethernet帧结构有差别。802.3标准规定的“类型字段”对应Ethernet V2.0帧的“类型/长度字段”
    B.前导码与帧前定界符字段长度为64位
    C.目的地址与源地址字段为全1表示广播地址，该帧将被所有的结点接收
    D. 数据字段的最小长度为46B，最大长度为1500B
14.某网络的IP地址为192.168.5.0/24采用定长子网划分，子网掩码为255.255.255.248，则该网络的最大子网个数为（    ），每个子网内的最大可分配地址个数为（    ）。
    A.32，8        B.32，6      C.8，32      D.8，30
15.若路由器R因为拥塞丢弃IP分组，则此时R可以向发出该IP分组的源主机发送的ICMP报文件类型是（    ）。
      A.路由重定向    B.目的不可达 C.源抑制    D.超时
目标不可达可能是有网络故障引起的传输错误
16.给定一个用二进制数表示的IP地址为：11010111 00111100 00011111 11000000，那么如果用点分十进制表示应该是（    ）。
      A.211.60.31.120  B.215.64.31.120  C.215.60.31.192  D.211.64.31.192
17.SMTP协议的默认端口为 （    ），其作用是（    ）。
    A.21，发送邮件    B.23，接受邮件      C.25，浏览网页    D.80， QQ聊天
18. 在Internet中，用于文件传输的协议是（    ）。
    A.HTML  B.SMTP  C.FTP  D.POP
19.IPv4数据包首部的最小长度为（    ）字节。
    A.10        B.20        C.30    D.40
江西省三支一扶入围名单20. 设计传输层的目的是弥补通信子网的服务的不足，提高传输服务的可靠性与保证（    ）。
    A.安全性  B.进程通信  C.保密性 D.服务质量QoS2021年湖北省公务员考试报名
21.下列选项中，不属于网络体系结构中所描述的内容是（    ）。
    A．网络的层次                    B.每一层使用的协议n
    C．协议的内部实现细节        D.每一层必须完成的功能
22.采用OSPF协议配置路由协议时，主干区域为（    ）。
    A.区域0    B.区域1        C.区域10        D.区域100
二、综合应用题（总分53分）
  1.请给出计算机网络的定义并予以简要解释。（10分）
计算机网络，是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。
  2.ISO在制定OSI参考模型时对层次划分的主要原则是什么？（10分）
网络中各结点都具有相同的层次
2）不同结点的同等层具有相同的功能
3）不同结点的同等层通过协议来实现对等层之间的通信
4）同一结点内相邻层之间通过接口通信
5）每个层可以使用下层提供的服务，并向其上层提供服务
  3.广域网采用的数据交换技术主要有哪些类型？（10分）
  4.请简单说明四种虚拟局域网的组网方法。（10分）
（1）基于端口划分的VLAN。这是最常应用的一种VLAN划分方法，应用也最为广泛、最有效，目前绝大多数VLAN协议的交换机都提供这种VLAN配置方法。
（2）基于MAC地址划分VLAN。这种划分VLAN的方法是根据每个主机的MAC地址来划分，即对每个MAC地址的主机都配置他属于哪个组，它实现的机制就是每一块网卡都对应唯一的MAC地址，VLAN交换机跟踪属于VLAN MAC的地址。这种方式的VLAN允许网络用户从一个物理位置移动到另一个物理位置时，自动保留其所属VLAN的成员身份。
（3）基于网络层协议划分VLAN。这种按网络层协议来组成的VLAN，可使广播域跨越多个VLAN交换机。
（4）根据IP广播组划分VLAN。IP广播实际上也是一种VLAN的定义，即认为一个IP广播组就是一个VLAN。
  5．将某C类网络192.168.25.0划分成4个子网，请计算出每个子网的有效的IP地址范围和对应的网络掩码（掩码用二进制表示）。(13分)