《2019年云南昆明理工大学计算机学科基础综合考研真题A卷》由会员分享，可在线阅读，更多相关《2019年云南昆明理工大学计算机学科基础综合考研真题A卷（4页珍藏版）》请在金锄头文库上搜索。
1、2019年云南昆明理工大学计算机学科基础综合考研真题A数据结构部分：一、选择题：（40分，每题2分）1. 已知10个数据元素（54，28，16，34，73，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个元素速度快；查找和存取速度快，但插入、删除速度慢；查找
2、、插入和删除速度快，但不能进行顺序存取； 插入、删除和顺序存取速度快；但 查找速度慢。A.顺序有序表,散列表，顺序表，链接表 B.顺序有序表，链接表，散列表，顺 序表C. 顺序表，顺序有序表，散列表，链接表 D. 顺序表，顺序有序表，链接表，散 列表4. 由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是 。A. 23B.37 C. 44 D. 465. 如果已知一个栈的入栈序列是：1, 2, 3, . . . , n,其出栈序列是：pl, p2，p3，.，pn,若p1=n，则pi为A.iB.n+iC.n-iD.n-i+16. 已知8个数据元素（34，76，45，1
3、8，26，54，92，65），按照依次插入结点的方法生成 一棵二叉排序树，则最后两层上的结点总数是 。A. 1 B. 2 C. 3 D. 47. 对线性表进行二分查找时，要求线性表必须是 。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且数据元素有序D.以链接方式存储，且数据元素有序& 一个中缀算术表达式a+ （b-x） *y,则对应的后缀算术表达式为。A. ab xy- *+;B. a bx-+ y*;C. ab x-y *+;D. a bxy * -+;9. 已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找 值为90的元素时，
4、次比较后查找成功；当二分查找值为47的元素时， 次比 较后查找成功。A. 1，4 B. 2，4 C. 3，2 D. 4，210. 以下的叙述中，正确的是： A.线性表的顺序存储结构优于链式存储结构。B.栈的操作方式是先进先出。C.二维数组是它的数据元素为线性表的线性表。D.队列的操作方式是先进后出。11. 线性表是( )。A.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空D.一个无限序列，不能为空12在无权图G的邻接矩阵A中，如果(vi,vj)属于图G的边集合(其中vi,vj表示图的顶点)， 则对应的元素Aij的值应该是A.0B.1C.2D.313. 由分别带权为9
5、，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是 。A. 23B.37 C. 44 D. 4614. 已知一个图的邻接矩阵表示，计算第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.链表存储结
6、构和树形存储结构17. 在一个无向图中，所有顶点的度数之和等于所有边数的倍。A. 1/2 B. 1 C. 2 D. 418. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。A. n B. n+1 C. n-1 D. n/219. 链式存储结构与顺序存储结构相比，下列哪一条是链式存储结构的缺点 A.可实现动态分配 B.不需要一组地址连续的存储单元C.插入、删除时不用移动大量元素 D.不是可随机存取的结构20. 从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为 ；从未排序序列中挑选元素，并将其放入已排序序列的另 一端，此方法称为 ；依次
7、将每两个相邻的有序表合并成一个有序表的排序方法叫做 ；当两个元素比较出现反序(即逆序)时就相互交换位置的排序方法叫做 。A. 归并排序,交换排序,选择排序,插入排序B. 选择排序,插入排序,归并排序,交换排序C. 交换排序,选择排序,插入排序,归并排序D. 插入排序,选择排序,归并排序,交换排序二、判断题：(10分，每题1分)1. 满二叉树也是完全二叉树。（ ）2. 二分查找要求所有记录按关键字排序。（ ）3. 直接插入排序是不稳定的。（ ）4. 线性表中所有结点的类型必须相同。（ ）5. 用树的前序遍历和中序遍历可以导出树的后序遍历；（ ）6. 中序遍历一棵二叉排序树的节点就可得到排好序的节
8、点序列。 （ ）7. 若待排序的记录数目较小，可采用直接插入排序或直接选择排序。（ ）8. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所 得的输出序列也一定相同； （ ）9. 稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。（ ）10. 树中所有结点都有双亲结点。（ ）三、简答题（共25分）1. 已知用于通讯的电文由7个字母组成，其字母的出现的频度权值W=6,8,2,4,9,15,19, 请构造出这组权值的哈夫曼树，并为这7个字母设计哈夫曼编码。（8分）2. 在顺序存储的线性表A30上进行二分查找的平均查找长度是多少（要求计算过程）？ （7
9、分）3. 在运用计算机解决实际问题时，合理的存储结构设计应考虑哪些方面的因素？举例说明 为什么？ （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
10、. 路由选择协议位于（ .）。A.物理层 B.数据链路层C.网络层 D.应用层6. 255.255.255.224可能代表的是（）。A. 一个B类网络号B. 一个C类网络中的广播C. 一个具有子网的网络掩码 D. 以上都不是7. IP地址为140.111.0.0的B类网络，若要切割为9个子网，而且都要连上In terne t, 请问子网掩码设为（）。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 . ICI9.
11、在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地址范围和子网掩码。
