1、昆明理工大学2019年硕士研究生招生入学考试试题(A卷)考试科目代码：818 考试科目名称 ：计算机学科基础综合（含数据结构、计算机网络）考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构 部分： 一、 选择题：（40分，每题2分） 1.已知10个数据元素（54，28，16，34，7
2、3，62，95，60，26，43），按照依次插入结点的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是 。A. 2 B. 3 C. 4 D. 52.在一棵完全二叉树中，若编号为 j 的结点有右孩子，则该结点的编号为 。A. 2*j-1 B. 2*j C. 2*j+1 D. j/23.在线性表的存储结构中， 查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第i个元素速度快； 查找和存取速度快，但插入、删除速度慢； 查找、插入和删除速度快，但不能进行顺序存取； 插入、删除和顺序存取速度快；但查找速度慢。A. 顺序有序表,散列表，顺序表，链接表 B. 顺序有序表，链接表，散
3、列表，顺序表C. 顺序表，顺序有序表，散列表，链接表 D. 顺序表，顺序有序表，链接表，散列表4.由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是 。A. 23 B.37 C. 44 D. 465.如果已知一个栈的入栈序列是：1，2，3，n，其出栈序列是：p1，p2，p3，pn，若p1=n，则pi为 Ai Bn+i Cn-i Dn-i+16.已知8个数据元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则最后两层上的结点总数是 。A. 1 B. 2 C. 3 D. 47.对线性表进行二分查找时，要求线性表必须是 。A
4、.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且数据元素有序 D.以链接方式存储，且数据元素有序8.一个中缀算术表达式a+（b-x）*y，则对应的后缀算术表达式为 。A. a b x y - * +; B. a b x - + y *;C. a b x - y * +; D. a b x y * - +;9.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， 次比较后查找成功。A. 1，4 B. 2，4 C. 3，2 D. 4，2昆明理工大学2019年硕士研究生招生入
5、学考试试题10.以下的叙述中，正确的是 ： A线性表的顺序存储结构优于链式存储结构。 B栈的操作方式是先进先出。C二维数组是它的数据元素为线性表的线性表。 D队列的操作方式是先进后出。11.线性表是（ ）。A.一个有限序列，可以为空 B.一个有限序列，不能为空C.一个无限序列，可以为空 D.一个无限序列，不能为空12.在无权图G的邻接矩阵A中，如果(vi,vj) 属于图G的边集合(其中vi,vj表示图的顶点)，则对应的元素Aij 的值应该是 A0 B1 C2 D313.由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是 。A. 23 B.37 C. 44 D. 46
6、14.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 A.求矩阵第i行非零元素之和 B.求矩阵第i列非零元素之和C.求矩阵第i行第i列元素之值 D.求矩阵非零元素第i行之和与第i列之和的差的绝对值15.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度 A. O(1) B. O(n) C. O(n)/2 D. O(p*n)16.栈结构一般采用的两种存储结构是： A线性存储结构和非线性存储结构 B顺序存储结构和链表存储结构C散列方式和索引方式 D链表存储结构和树形存储结构17.在一个无向图中，所有顶点的度数之和等于所有边数的 倍。A. 1/2 B. 1 C. 2
7、D. 418.在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。A. n B. n+1 C. n-1 D. n/219.链式存储结构与顺序存储结构相比，下列哪一条是链式存储结构的缺点 A 可实现动态分配 B不需要一组地址连续的存储单元 C 插入、删除时不用移动大量元素 D不是可随机存取的结构20.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为 ；从未排序序列中挑选元素，并将其放入已排序序列的另一端，此方法称为 ；依次将每两个相邻的有序表合并成一个有序表的排序方法叫做 ；当两个元素比较出现反序（即逆序）时就相互交换位置的排序方法叫做
8、。A. 归并排序,交换排序,选择排序,插入排序B. 选择排序,插入排序,归并排序,交换排序C. 交换排序,选择排序,插入排序,归并排序D. 插入排序, 选择排序,归并排序,交换排序昆明理工大学2019年硕士研究生招生入学考试试题二、判断题：（10分，每题1分）1.满二叉树也是完全二叉树。（ ）2.二分查找要求所有记录按关键字排序。（ ）3.直接插入排序是不稳定的。（ ）4.线性表中所有结点的类型必须相同。（ ）5.用树的前序遍历和中序遍历可以导出树的后序遍历；（ ）6.中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。 （ ）7.若待排序的记录数目较小，可采用直接插入排序或直接选择排序。（
9、 ）8.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同； （ ）9.稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。（ ）10.树中所有结点都有双亲结点。（ ）三、简答题（共25分） 1.已知用于通讯的电文由7个字母组成，其字母的出现的频度权值W=6,8,2,4,9,15,19,请构造出这组权值的哈夫曼树，并为这7个字母设计哈夫曼编码。（8分）2. 在顺序存储的线性表A30上进行二分查找的平均查找长度是多少（要求计算过程）？（7分）3.在运用计算机解决实际问题时，合理的存储结构设计应考虑哪些方面的因素？举例说明为什么？（
10、10分）网络 部分：一、单项选择题（每小题2分，共30分）1. 以下属于物理层的设备是（ ）。A. 中继器 B. 以太网交换机 C. 桥 D. 网关2.下面哪种LAN 是应用CSMA/CD协议的 （ ）。A.令牌环 B. FDDI C. ETHERNET D. NOVELL3.应用程序PING 发出的是（ ）报文。A.TCP 请求报文 B.TCP 应答报文 C.ICMP 请求报文 D.ICMP 应答报文4. ARP 协议的作用是 （ ）。A.将端口号映射到IP 地址 B.连接IP 层和TCP 层C.广播IP 地址 D.将IP 地址映射到MAC地址5. 路由选择协议位于（ .）。A. 物理层 B
11、. 数据链路层 C. 网络层 D. 应用层6. 255.255.255.224可能代表的是（ ）。A. 一个B类网络号 B. 一个C类网络中的广播C. 一个具有子网的网络掩码 D. 以上都不是昆明理工大学2019年硕士研究生招生入学考试试题7. IP地址为 140.111.0.0 的B类网络，若要切割为9个子网，而且都要连上Internet，请问子网掩码设为（ ）。A.255.0.0.0 B. 255.255.0.0 C. 255.255.128.0 D. 255.255.240.08. 相邻层间交换的数据单元称之为服务数据单元，其英文缩写为（ ）。A. SDU B.IDU C. PDU D
12、. ICI9. 在IP地址方案中，159.226.181.1是一个（ ）。A. A类地址 B. B类地址 C. C类地址 D. D类地址10. 以下属于广域网技术的是（ ）。A. 以太网 B. 令牌环网C. 帧中继D. FDDI11. TCP的协议数据单元被称为（ ）。A. 比特B. 帧C. 分段D. 字符12. 世界上第一个计算机网络是 （ ）。A. ARPANET B. ChinaNet C.Internet D.CERNET13. 一般来说，用户上网要通过因特网服务提供商，其英文缩写为( )。AIDC BICP CASP DISP14. PPP协议是哪一层的协议( )。A物理层 B数据链路层C网络层 D高层15. TCP/IP协议规定为（ ）。A、 4层 B、 5层 C、 6层 D、7层二、综合题（每小题9分，共45分）1.简述CSMA/CD的工作原理。2.简述VPN的工作原理。3.简述路由器分组转发的过程。4.简述IP地址与MAC地址的联系与区别。5. 某公司使用192.168.25.0一个标准C类网络。请使用子网划分技术划分成6个子网，给出子网划分方案，并给出每个子网的IP地址范围和子网掩码。第 5 页 共 5页
