搜索
第1页共6页昆明理工大学2017年硕士研究生招生入学考试试题(A卷)考试科目代码：818考试科目名称：计算机学科专业基础综合考生答题须知1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3．答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4．答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、填空题：（每空1分，共20分）3.用计算机处理问题的方法称为算法。评价其优劣的的办法是在其的前提下主要是考察其时间和空间复杂度。1.在DataSet中，数据元素分为行元素和列元素；元素间的关系是独立于计算机之外的称为逻辑关系，分为线性和非线性关系。实际?问题2.这里的数据关系称为存储关系，有顺序、链式、索引和散列存储方法。用数据描述实际问题获得数据集DataSet计算机存储器数据存入计算机第2页共6页昆明理工大学2017年硕士研究生招生入学考试试题4.多维数组采用的存储结构是顺序存储；广义表采用的存储结构是链式存储。5.哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。6.与后缀表达式abc-d*+，等价的中缀表达式为a+(b-c)*d。7.树转换成的二叉树，其根结点的右子树一定为空。二、单项选择题（每题2分，共20分）1.下面程序段的时间复杂度为（）。for(i=0;in+1;i++)for(j=0;jm+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-iB.n-i+1C.n-i-1D.i3.在一单链表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.ABCDEB.BCDEAC.EABCDD.EDCBA5.一链队列中，假设f和r分别为队首指针和队尾指针，则出队列时，下列（）语句是必要的。A.r=f-nextB.r=r-nextC.f=f-nextD.f=r-next6.假定一个顺序循环队列的队首队尾指针分别用front和rear表示，则判断队空的条件是（）。A.front=rearB.rear+1=frontC.front=0D.front+1=rear7.以下叙述中，正确的是（）。A.线性表的顺序存储结构优于链式存储结构B.网络的最小生成树是唯一的C.二维数组是它的数据元素为线性表的线性表D.数据的逻辑结构与存储结构都是依赖于计算机的8.在一棵完全二叉树中，若编号为j的结点有右孩子，则其编号为（）。A.2jB.2j+1C.2j-1D.└j/2┘9.n个顶点的连通图至少有（）条边。A.n-1B.n-2C.nD.n+110.一有序表(6,9,11,12,14,17,21,33,37)，当二分查找值为11的结点时，（）次比较后查找成功。第3页共6页A.2B.3C.4D.5mid=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分）1234561∞31∞∞∞23∞24∞∞312∞2∞∞4∞42∞345∞∞∞3∞16∞∞∞41∞网络部分：一、单项选择题（每小题1分，总分22分）1.在OSI参考模型中，自下而上第一个提供端到端服务的层次是（）。A．数据链路层B.传输层C.会话层D.应用层2.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是（）。W=2xHxlog2VA．12kbpsB.24kbpsC.48kbpsD.96kbps3.数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（）。A．2B.3C.4D.5根据后退N帧协议，接收方的窗口为“1”，如果发送方收到了3号帧的确认，则说明0、1、2、3号帧都已经发送成功，所以只需要重发4、5、6、7号帧即可4.在OSI参考模型中，数据链路层的数据服务单元是（）。A.帧B.报文C.分组D.比特序列5.100BaseT的传输介质是（）。第4页共6页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.1946B.1969C.1977D.197310.按0比特插入/删除方法规定，在两个标志字段F之间的比特序列中，如果检查出连续的（）个1，不管后面的比特位是0或1，都需要增加一个0。A.4B.5C.6D.811.在（）差错控制方式中，只会重新传输那些差错的数据帧。A.连续工作B.停止等待C.选择重发D.拉回12.IP地址块202.120.80.128/26包含了（）个主机地址。A.15B.31C.62D.12713.以下关于Ethernet帧结构的描述中，错误的是（）。A.EthernetV2.0规范和IEEE802.3标准中的Ethernet帧结构有差别。802.3标准规定的“类型字段”对应EthernetV2.0帧的“类型/长度字段”B.前导码与帧前定界符字段长度为64位C.目的地址与源地址字段为全1表示广播地址，该帧将被所有的结点接收D.数据字段的最小长度为46B，最大长度为1500B14.某网络的IP地址为192.168.5.0/24采用定长子网划分，子网掩码为255.255.255.248，则该网络的最大子网个数为（），每个子网内的最大可分配地址个数为（）。A.32，8B.32，6C.8，32D.8，30第5页共6页15.若路由器R因为拥塞丢弃IP分组，则此时R可以向发出该IP分组的源主机发送的ICMP报文件类型是（）。A.路由重定向B.目的不可达C.源抑制D.超时目标不可达可能是有网络故障引起的传输错误16.给定一个用二进制数表示的IP地址为：11010111001111000001111111000000，那么如果用点分十进制表示应该是（）。A.211.60.31.120B.215.64.31.120C.215.60.31.192D.211.64.31.19217.SMTP协议的默认端口为（），其作用是（）。A.21，发送邮件B.23，接受邮件C.25，浏览网页D.80，QQ聊天18.在Internet中，用于文件传输的协议是（）。A.HTMLB.SMTPC.FTPD.POP19.IPv4数据包首部的最小长度为（）字节。A.10B.20C.30D.4020.设计传输层的目的是弥补通信子网的服务的不足，提高传输服务的可靠性与保证（）。A.安全性B.进程通信C.保密性D.服务质量QoS21.下列选项中，不属于网络体系结构中所描述的内容是（）。A．网络的层次B.每一层使用的协议nC．协议的内部实现细节D.每一层必须完成的功能22.采用OSPF协议配置路由协议时，主干区域为（）。A.区域0B.区域1C.区域10D.区域100二、综合应用题（总分53分）1.请给出计算机网络的定义并予以简要解释。（10分）计算机网络，是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。2.ISO在制定OSI参考模型时对层次划分的主要原则是什么？（10分）网络中各结点都具有相同的层次2）不同结点的同等层具有相同的功能第6页共6页3）不同结点的同等层通过协议来实现对等层之间的通信4）同一结点内相邻层之间通过接口通信5）每个层可以使用下层提供的服务，并向其上层提供服务3.广域网采用的数据交换技术主要有哪些类型？（10分）4.请简单说明四种虚拟局域网的组网方法。（10分）（1）基于端口划分的VLAN。这是最常应用的一种VLAN划分方法，应用也最为广泛、最有效，目前绝大多数VLAN协议的交换机都提供这种VLAN配置方法。（2）基于MAC地址划分VLAN。这种划分VLAN的方法是根据每个主机的MAC地址来划分，即对每个MAC地址的主机都配置他属于哪个组，它实现的机制就是每一块网卡都对应唯一的MAC地址，VLAN交换机跟踪属于VLANMAC的地址。这种方式的VLAN允许网络用户从一个物理位置移动到另一个物理位置时，自动保留其所属VLAN的成员身份。（3）基于网络层协议划分VLAN。这种按网络层协议来组成的VLAN，可使广播域跨越多个VLAN交换机。（4）根据IP广播组划分VLAN。IP广播实际上也是一种VLAN的定义，即认为一个IP广播组就是一个VLAN。5．将某C类网络192.168.25.0划分成4个子网，请计算出每个子网的有效的IP地址范围和对应的网络掩码（掩码用二进制表示）。(13分)