2018年西北工业大学软件专业考研真题.docx

【2018年西北工业大学软件专业考研真题】数据结构一、选择题(共5题，每题3分，共15分)1、最小堆里删除最小元素的时间复杂度()(A)O(nlogn)(B)O(n)(C)O(n*n)(D)O(logn)2.如果初始序列升序，下列哪个算法比较容易实现()(A)冒泡(B)归并(C)堆排序(D)快速3.对线性表，在下列哪种情况应当采用链表表示()(A)经常需要随机的存取元素(B)经常需要进行插入和删除操作(C)表中需要占据-片连续的存储空间(D)表中元素个数不变4.一个非空广义表的表头()(A)不可能是原子(B)只能是子表(C)只能是原子(D)可以是子表或原子5.空节点为n0，单分支节点为n1,双分支节点为n2，下列哪个关系是正确的二、简答题(总分60分)1.用前序和中序二叉树序列画出这个二叉树，有过程。2.平衡二叉树的建立过程，以及删除一个元素后的最终平衡二叉树。3.一个图，有6个点，边上有权值，高速公路要连接这几个点，并且代价最小，如果修路4.多项式的存储结构，两个多项式相加的算法。计算机网络一、选择题(共10题，每题2分，共20分)1.FTP采用什么协议()2.给了一个网络地址，问可用主机地址()3.网络中出现拥塞,路由器发出什么报文()(A)路由重定向(B)目标不可达(C)源抑制(D)子网掩码请求4.IPv6的地址表示中哪个是错误的()5.传输层的端到端的协议有哪两个?6.交换技术中，没有哪种(A)电路交换(B)地址交换(C)报文交换(D)分组交换7.多路复用中哪个是错误的(A)FDM的前提是传输介质的可用带宽必须大于多路给定信号所需带宽的总和B)TDM可分为同步和异步(C)同步又称为时分多路复用技术(D)对于模拟信号，可以把FDM和TDM结合起来使用8.CSMA/CA和CSMA/CD的含义，哪个是冲突避免，哪个是冲突检测()9.OSPF用什么建立路由表(A)距离矢量路由算法(B)链路状态路由算法(C)流量状态路由算(D)逆向学习机制10.后退n帧流量控制，发送窗口的最大长度二、简答(一个6分，共5个30分)1.电路交换和数据报的差别2.TCP为什么要采用三次握手.3.简述RIP和OSPF的区别4.为什么要划分子网，子网掩码的作用5.给了一个网址，写出域名解析过程三、分析综合题(1)数据传输速率是10Mbps，分组大小是1000B，分组头是20B,所要传输98000B的文件，问传输延迟是多少(2)分配ip地址，给了一个网络地址，公司有四个部门，分别需要主机数110 62 3025，要求四个部门划分不同的子网，且IP地址的主机位满足部门依次减小的关系，要求不浪费地址的情况下划分子网。并写出每个部门的网络地址，可分配地址范围以及子网掩码。