logo资料库

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

第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
资料共4页,全文预览结束
2019 年云南昆明理工大学计算机学科基础综合考研真题 A 卷 数据结构 部分: 一、 选择题:(40分,每题2分) 1.已知10个数据元素(54,28,16,34,73,62,95,60,26,43),按照依次插入结点 的方法生成一棵二叉排序树后,则查找值为62的结点所需比较的次数是[ ]。 A. 2 B. 3 C. 4 D. 5 2.在一棵完全二叉树中,若编号为 j 的结点有右孩子,则该结点的编号为[ ] 。 A. 2*j-1 B. 2*j C. 2*j+1 D. j/2 3.在线性表的存储结构中,[ ]查找(按关键字查找)、插入、删除速度慢,但顺序存 取和随机存取第i个元素速度快;[ ]查找和存取速度快,但插入、删除速度慢;[ ] 查找、插入和删除速度快,但不能进行顺序存取;[ ]插入、删除和顺序存取速度快;但 查找速度慢。 A. 顺序有序表,散列表,顺序表,链接表 B. 顺序有序表,链接表,散列表,顺 序表 列表 C. 顺序表,顺序有序表,散列表,链接表 D. 顺序表,顺序有序表,链接表,散 4.由分别带权为9,2,5,7的四个叶结点构造一棵哈夫曼树,则该树的带权路径长度是 [ ]。 A. 23 B.37 C. 44 D. 46 5.如果已知一个栈的入栈序列是:1,2,3,...,n,其出栈序列是:p1,p2,p3,..., pn,若p1=n,则pi为 [ ] A.i B.n+i C.n-i D.n-i+1 6.已知8个数据元素(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成 一棵二叉排序树,则最后两层上的结点总数是[ ]。 A. 1 B. 2 C. 3 D. 4 7.对线性表进行二分查找时,要求线性表必须是[ ]。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储,且数据元素有序 D.以链接方式存储,且数据元素有序 8.一个中缀算术表达式a+(b-x)*y,则对应的后缀算术表达式为[ ]。 A. a C. a b b x x y - - * y * +; +; B. a D. a b b x x - y + 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
10.以下的叙述中,正确的是 : [ ] A.线性表的顺序存储结构优于链式存储结构。 B.栈的操作方式是先进先出。 C.二维数组是它的数据元素为线性表的线性表。 D.队列的操作方式是先进后出。 11.线性表是( )。 A.一个有限序列,可以为空 B.一个有限序列,不能为空 C.一个无限序列,可以为空 D.一个无限序列,不能为空 12.在无权图G的邻接矩阵A中,如果(vi,vj) 属于图G的边集合(其中vi,vj表示图的顶点), 则对应的元素A[i][j] 的值应该是 [ ] A.0 B.1 C.2 D.3 13.由分别带权为9,2,5,7的四个叶结点构造一棵哈夫曼树,则该树的带权路径长度是 [ ]。 A. 23 B.37 C. 44 D. 46 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 D. 4 18.在一个具有n个顶点的无向图中,要连通全部顶点至少需要[ ]条边。 A. n B. n+1 C. n-1 D. n/2 19.链式存储结构与顺序存储结构相比,下列哪一条是链式存储结构的缺点 [ ] A. 可实现动态分配 B.不需要一组地址连续的存储单元 C. 插入、删除时不用移动大量元素 D.不是可随机存取的结构 20.从未排序序列中依次取出元素与已排序序列中的元素作比较,将其放入已排序序列中的 正确位置上,此方法称为[ ];从未排序序列中挑选元素,并将其放入已排序序列的另 一端,此方法称为[ ];依次将每两个相邻的有序表合并成一个有序表的排序方法叫做 [ ];当两个元素比较出现反序(即逆序)时就相互交换位置的排序方法叫做 [ ]。 A. 归并排序,交换排序,选择排序,插入排序 B. 选择排序,插入排序,归并排序,交换排序 C. 交换排序,选择排序,插入排序,归并排序 D. 插入排序, 选择排序,归并排序,交换排序 二、判断题:(10 分,每题 1 分)
1.满二叉树也是完全二叉树。( ) 2.二分查找要求所有记录按关键字排序。( ) 3.直接插入排序是不稳定的。( ) 4.线性表中所有结点的类型必须相同。( ) 5.用树的前序遍历和中序遍历可以导出树的后序遍历;( ) 6.中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。 ( ) 7.若待排序的记录数目较小,可采用直接插入排序或直接选择排序。( ) 8.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所 得的输出序列也一定相同; ( ) 9.稀疏矩阵中值为0的元素分布有规律,因此可以采用三元组方法进行压缩存储。( ) 10.树中所有结点都有双亲结点。( ) 三、简答题(共 25 分) 1.已知用于通讯的电文由 7 个字母组成,其字母的出现的频度权值 W={6,8,2,4,9,15,19}, 请构造出这组权值的哈夫曼树,并为这 7 个字母设计哈夫曼编码。(8 分) 2. 在顺序存储的线性表 A[30]上进行二分查找的平均查找长度是多少(要求计算过程)? (7 分) 3.在运用计算机解决实际问题时,合理的存储结构设计应考虑哪些方面的因素?举例说明 为什么?(10 分) 网络 部分: 一、单项选择题(每小题 2 分,共 30 分) 1. 以下属于物理层的设备是( )。 A. 中继器 B. 以太网交换机 C. 桥 D. 网关 2.下面哪种 LAN 是应用 CSMA/CD 协议的 ( )。 A.令牌环 B. FDDI C. ETHERNET D. NOVELL 3.应用程序 PING 发出的是( )报文。 A.TCP 请求报文 B.TCP 应答报文 C.ICMP 请求报文 D.ICMP 应答报文 4. ARP 协议的作用是 ( )。 A.将端口号映射到 IP 地址 B.连接 IP 层和 TCP 层 C.广播 IP 地址 D.将 IP 地址映射到 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.0
8. 相邻层间交换的数据单元称之为服务数据单元,其英文缩写为( )。 A. SDU B.IDU C. PDU D . ICI 9. 在 IP 地址方案中,159.226.181.1 是一个( )。 A. A 类地址 B. B 类地址 C. C 类地址 D. D 类地址 10. 以下属于广域网技术的是( )。 A. 以太网 B. 令牌环网 C. 帧中继 D. FDDI 11. TCP 的协议数据单元被称为( )。 A. 比特 B. 帧 C. 分段 D. 字符 12. 世界上第一个计算机网络是 ( )。 A. ARPANET B. ChinaNet C.Internet D.CERNET 13. 一般来说,用户上网要通过因特网服务提供商,其英文缩写为( )。 A.IDC B.ICP C.ASP D.ISP 14. 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 地址范围和子网掩码。
分享到:
收藏