2019年云南昆明理工大学计算机学科基础综合考研真题A卷.doc

《2019年云南昆明理工大学计算机学科基础综合考研真题A卷.doc》由会员分享，可在线阅读，更多相关《2019年云南昆明理工大学计算机学科基础综合考研真题A卷.doc（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. 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）

3、，按照依次插入结点的方法生成一棵二叉排序树，则最后两层上的结点总数是 。A. 1 B. 2 C. 3 D. 47.对线性表进行二分查找时，要求线性表必须是 。A.以顺序方式存储 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的元素时，

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 的值应该是 A0 B1 C2 D313.由分别带权为9

5、，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是 。A. 23 B.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分）3.在运用计算机解决实际问

9、题时，合理的存储结构设计应考虑哪些方面的因素？举例说明为什么？（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 地址

10、映射到MAC地址5. 路由选择协议位于（ .）。A. 物理层 B. 数据链路层 C. 网络层 D. 应用层6. 255.255.255.224可能代表的是（ ）。A. 一个B类网络号 B. 一个C类网络中的广播C. 一个具有子网的网络掩码 D. 以上都不是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

11、. PDU D . 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地址范围和子网掩码。