1、昆明理工大学2016年硕士研究生招生入学考试试题(A卷)考试科目代码：818 考试科目名称 ：计算机学科专业基础综合考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、 单项选择题（共25题，每题1分，共25分）1. 对一个算法的评价，不包括如下（ ）方面的内容。(A)健壮性和
2、可读性 （B）并行性 （C）正确性 （D）时空复杂度2. 对线性表，在下列哪种情况下应当采用链表表示？( )（A）经常需要随机地存取元素 （B）经常需要进行插入和删除操作（C）表中元素需要占据一片连续的存储空间 （D）表中元素的个数不变3. 下面程序段的时间复杂度是（ ）。j=0; s=0; while (snext=p-next-next (B) p=p-next (C) p=p-next-next (D) next=p6. 若某线性表最常用的操作是读取任一指定序号的元素和在最后进行插入和删除运算，则采用 （ ）存储方式最省时间。(A) 顺序表 (B) 双链表 (C )带头结点的双循环链表
3、(D) 单循环链表7. 用链接方式存储的队列，在进行插入运算时( ). (A) 仅修改头指针 (B) 头、尾指针都要修改 (C ) 仅修改尾指针 (D) 头、尾指针可能都要修改8. 在顺序栈中，假定以高端地址作为栈底，以top作为栈顶，则当做出栈处理时，top 的变化为( )。(A) 不变 (B) top=0 (C ) top=top -1 (D) top=top+1昆明理工大学2016年硕士研究生招生入学考试试题9. 一个栈的入栈序列为1 2 3，入栈时可以出栈，则下列序列中不可能是出栈序列的是( )(A) 2 3 1(B) 3 2 1(C) 3 1 2 (D) 1 2 310. 输入受限的
4、双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列( ).。 输入受限的双端队列 (A). 2、8、1、4 (B). 1、4、8、2 ( C) . 4、2、1、8 (D). 2、1、4、811. 栈和队列的共同特点是( )。 (A)只允许在端点处插入和删除元素 (B)都是先进后出 (C)都是先进先出(D)没有共同点 12. 给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动 个元素。 ( A). (n+1)/2 (B) . n/2 (C) . (n-1)/2 (
5、D). 113. 在具有n个单元的顺序存储的循环队列中，假定front、rear 分别为队首和队尾指针，则判断队满的条件是( ).。 （A）(rear%n)= front （B）(front+1%n)=rear （C）(rear-1) %n)= front （D）(rear+1)%n)=front14. 一个中缀算术表达式a+（b-x）*y，则对应的后缀算术表达式为 ( ).。(A) a b x y - * +; (B) a b x - + y *;(C) a b x - y * +; (D) a b x y * - +;15. 设有一个二维数组Amn，假设A00存放位置在644(10)，A2
6、2存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？( ).脚注(10)表示用10进制表示。(A)688 (B)678 (C) 692 （D）69616. 树最适合用来表示( )。 (A)有序数据元素 (B)无序数据元素 (C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据17. 在有n个结点的二叉链表中，值非空的链域的个数为( )。(A) n-1 (B) 2n-1 (C) n+1 (D) 2n+1 18. 在一个具有n个顶点的无向图中，最多包含有( )边。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n219. 在一
7、个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。 (A) n (B) n+1 (C) n-1 (D) n/220. 任何一个无向连通图的最小生成树( )(A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D)可能不存在。21. 在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有( )邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有( )邻接点；(A) 出边，入边 (B) 入边，出边22. 在线性表的存储结构中，( )查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第i个元素速度快；( )查找和存取速度快，但插入、删除速度慢；( )查找、插入和删除
8、速度快，但不能进行顺序存取；( )插入、删除和顺序存取速度快；但查找速度慢。(A) 散列表，顺序有序表，顺序表，链接表(B) 顺序表，顺序有序表，散列表，链接表 (C) 链接表，顺序有序表，散列表，顺序表 (D) 顺序有序表，顺序表，链接表，散列表23. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ）(A)选择排序 （B）希尔排序 （C）归
9、并排序 （D）快速排序24. 已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，( )次比较后查找成功；当二分查找值为47的元素时，( )次比较后查找成功。 (A) 1，4 (B) 2，4 (C) 3，2 (D) 4，225. 在顺序存储的线性表A30上进行顺序查找的平均查找长度为( )。 (A) 15 (B) 15.5 (C) 16 (D) 20二、综合题：（共3题，共50分）1. 在算法设计中，存储结构的设计与什么因素有关？（10分）312456128155420108962. 在几个居民点铺设煤气管道，每两个居民间的铺设
10、费用是可以估算的（如右图所示）。1) 如果要求铺设的总费用最小，从图的理论上，这实际上是什么求解问题。（8分）2) 请用Prim算法思想，从V1点开始，画出铺设方案选边的图示过程。（12分）3. 一组待排序的记录为（46,79,56,38,40,84），写出从小到大： 利用冒泡排序第一,二趟的变化序列; （10分） 利用快速排序第一趟的变化序列; （10分）昆明理工大学2016年硕士研究生招生入学考试试题计算机网络部分一、单项选择题（每空1分，总分20分）1、Internet 中域名与IP地址之间的翻译是由_(1)_ 来完成的。A. 域名服务器B. 代理服务器CFTP 服务器DWeb 服务器2
11、、浏览器与WWW服务器之间传输信息时使用的协议是_(2)_。AHTTPBHTMLCFTP DSNMP3、属于物理层的互连设备是_(3)_。A中继器B网桥C.交换机D.路由器4、路由器是一种常用的网络互连设备，它工作在OSIRM的（4） 上，在网络中它能够根据网络通信的情况（5） ，并识别（6）相互分离的网络经路由器互连后（7） 。(4)：A物理层 B数据链路层 C网络层 D传输层(5)：A动态选择路由 B控制数据流量 C调节数据传输率 D改变路由结构 (6)：AMAC地址 B网络地址 CMAC地址和网络地址 DMAC地址和网络地址的共同逻辑地址 (7)：A形成了一个更大的物理网络 B仍然还是原
12、来的网络 C形成了一个逻辑上单一的网络 D成为若干个互连的子网 5、ADSL对应的中文术语是_(8)_。A分析数字系统层 B非对称数字线C非对称数字用户线 D异步数字系统层6、以下网络设备中，工作于网络层的设备是_(9)_ 。A调制解调器B. 以太网交换机C. 集线器D. 路由器7、在Windows 中，可以提供WWW服务的软件是_(10)_ 。A. IIS B. ISAC. ISP D. ASP8、网络122.21.136.0/22 中最多可用的主机地址是_(11)_ 。A. 1024B. 1023C. 1022D. 1000昆明理工大学2016年硕士研究生招生入学考试试题9、通过_(12)
13、_ 命令可以查看当前计算机的TCP 连接状态。A. route B. pingC. netstat D. ipconfig10、在下列网络服务中，_(13)_ 是远程登陆服务，默认端口号为_(14)_ 。（13）A. WWW B. FTP C. BBS D. Telnet（14）A21B23C25D8011、在网络地址178.15.0.0中划分出10个大小相同的子网，每个子网最多有_(15)_个可用的主机地址。A2046B2048C4094D409612、在浏览Web页面时，发现了自己需要经常使用的Web页面，此时最好的方法是_(16)_。A将该Web页面的地址加入到收藏夹B将该Web页面的地
14、址加入到地址簿C将该Web页面的地址加入到notepadD将该Web页面的地址加入到历史记录13、在Windows的网络属性配置中， “默认网关”应该设置为_(17)_的地址。ADNS服务器BWeb服务器 C路由器D交换机14、电子邮件通常使用的协议有_(18)_。ASMTP和POP3BSMTP和RMON CRMON和SNMP DSNMP和POP315、Internet中用于文件传输的是_(19)_。ADHCP服务器 BDNS服务器 CFTP服务器 D路由器16、代理服务器可以提供_(20)_功能。A信息转发 B路由选择 C域名解析D帧封装昆明理工大学2016年硕士研究生招生入学考试试题二、综
15、合应用题（总分55分）1、制作交叉双绞线(一端按EIA/TIA 568A线序，另一端按EIA/TIA 568B线序)时，其中一端的线序如图(a)所示，另一端线序如图(b)所示，将图(b)中(1)(8)处空缺的颜色名称填写出来（每空2.5分，20分）。2、某公司内部有一个采用TCP/IP作为传输协议的100Base-TX局域网，包括1台服务器和20台客户机，通过一台16端口的交换机与一台8端口共享集线器级连，其网络结构如下图所示。服务器上运行DHCP服务软件，客户机的IP地址由DHCP服务程序自动分配。（15分）问题1连接主机A与交换机的单根网线的最大长度为多少? (5分)问题2该局域网中的集线
16、器每个端口平均享有的带宽是多少? (5分)问题3为了控制局域网用户访问Internet时只能进行WWW浏览，网管应该在路由器上采取什么措施? (5分)昆明理工大学2016年硕士研究生招生入学考试试题3、某一网络地址块192.168.75.0中有5台主机A、B、C、D和E，它们的IP地址及子网掩码如下表所示。（20分）主机IP地址及子网掩码表主机IP地址子网掩码A192.168.75.18255.255.255.240B192.168.75.146255.255.255.240C192.168.75.158255.255.255.240D192.168.75.161255.255.255.240E192.168.75.173255.255.255.240【问题1】（10分）5台主机A、B、C、D、E分属几个网段？哪些主机位于同一网段？【问题2】（5分）主机D的网络地址为多少？【问题3】（5分）若要加入第六台主机F，使它能与主机A属于同一网段，其IP地址范围是多少？第 8 页 共 8页
