软件考研试题及详细答案

软件考研经典试题及详细答案考试时间：______分钟总分：______分姓名：______一、单项选择题（共40小题，每小题1分，共40分）1.设一个栈的输入序列为a、b、c、d、e，则不可能得到的输出序列是A.edcbaB.decbaC.dceabD.abcde2.在一个单链表中，已知q所指节点是p所指节点的直接前驱，若在p、q之间插入s节点，则执行操作A.s->next=p->next;p->next=s;B.q->next=s;s->next=p;C.p->next=s;s->next=q;D.p->next=s->next;s->next=p;3.一棵完全二叉树有1001个节点，则其叶子节点的个数为A.500B.501C.252D.2534.在下列通路中，不存在回路的图是A.无向树B.有向树C.无向图D.有向图5.设散列函数为H(key)=key%13，序列{19,14,23,1,68,20}散列到长度为13的散列表中，用二次探测法处理冲突，则散列地址为1的元素个数是A.1B.2C.3D.46.下列排序算法中，时间复杂度为O(n^2)且是不稳定排序的是A.直接插入排序B.冒泡排序C.归并排序D.基数排序7.下列数列中，是堆的是A.16,72,30,24,53,96B.16,24,30,53,72,96C.16,30,24,72,96,53D.16,24,53,30,96,728.十进制数-57用8位补码表示的二进制数是A.11000111B.10111111C.11100001D.110000019.若浮点数采用阶移码、补码表示，一个浮点数x的阶码部分为PE，尾数部分为ME。若PE=PEmax，则A.x一定是规格化数B.x一定不是规格化数C.x一定是最大正数D.x一定是负数10.某计算机字长16位，主存地址空间大小为128MB，按字节编址。某指令系统共有64条指令，采用定长指令格式，操作码字段5位，A和B均为通用寄存器，源操作数和目的操作数都采用寄存器间接寻址方式。以下关于该指令格式的描述，正确的是A.该指令长度为16位，包含5位操作码和11位地址码B.该指令的寻址范围可达2^11C.该指令的指令周期取决于主存容量D.该指令若采用立即寻址，则源操作数和目的操作数只能为常数11.某计算机的CPU内部有PC、IR、MAR、MDR、ACC等寄存器，已知指令周期由取指周期、间址周期、执行周期组成。若采用单总线结构，执行“ADDR1,(R2)”指令时，在执行周期中至少需要访问存储器的次数是A.1B.2C.3D.412.在主存和CPU之间增加Cache是为了A.扩大主存容量B.提高主存速度C.bothAandBD.硬件成本13.某计算机系统采用直接映射Cache，主存容量为4MB，Cache容量为64KB，块大小为1KB，主存地址共24位。主存地址中标记字段(Tag)的位数为A.10B.12C.14D.1614.下列关于总线仲裁方式的描述中，错误的是A.集中仲裁方式响应时间快B.独立仲裁方式控制电路简单C.集中仲裁方式下，主模块的优先级是固定的D.独立仲裁方式下，各模块的优先级是固定的15.某中断系统中，断点保护由硬件自动完成，而中断服务程序中的保护现场和恢复现场则由程序员编写的软件实现，这种中断方式是A.硬件中断B.软件中断C.向量中断D.非向量中断16.设有四个进程P1,P2,P3,P4，它们就绪队列的优先级从高到低依次为P1,P2,P3,P4。若采用时间片轮转调度算法，时间片为1个单位，则进程调度的先后顺序为A.P1,P2,P3,P4B.P1,P2,P4,P3C.P1,P2,P1,P2...D.P1,P2,P1,P3...17.若系统中有N个进程竞争同一类资源，且每个进程最多需要M个该类资源。系统为该类资源分配了M个，则系统处于不安全状态的情况是A.N=2,M=2B.N=3,M=3C.N=4,M=4D.N=5,M=218.虚拟存储器的基本实现方法是A.静态重定位B.动态重定位C.覆盖技术D.交换技术19.在文件系统中，为了解决文件命名冲突问题，通常采用A.路径名B.索引文件C.树形目录结构D.活动表20.某磁盘组有12个盘片，每面有200个磁道，每道有16个扇区，每个扇区存储1KB数据。磁盘旋转速度为6000rpm，平均寻道时间为6ms。则该磁盘组的容量和平均寻址时间（包括旋转延迟）约为A.240MB,10msB.240MB,20msC.7.68GB,10msD.7.68GB,20ms21.在物理层接口特性中，规定电压范围的特性是A.机械特性B.电气特性C.功能特性D.规程特性22.在数据链路层，如果信道不可靠，为了提高传输可靠性，可以采用A.CRC校验B.自动重传请求(ARQ)C.光纤通信D.频带复用23.两台主机之间的距离为2000km，光在光纤中的传播速度约为2×10^8m/s。若某数据帧长1000字节，发送速率100Mbps，则信道利用率最高为A.1%B.10%C.20%D.50%24.在IP协议中，为了避免IP地址的浪费，引入了子网划分和CIDR技术。若一个网络的地址块为/12，则该网络中包含的子网数量最多为A.4B.8C.16D.3225.在TCP协议中，发送端发送一个报文段，确认号字段为y，则以下说法正确的是A.发送端期望收到序号为y的TCP段B.接收端已经成功收到序号为y-1及其之前的所有数据C.接收端已经成功收到序号为y的数据D.接收端已经成功收到序号为y+1及其之前的所有数据26.在TCP三次握手过程中，客户端发送的第一个报文段的标志位SYN=1，ACK=0，序列号seq=x。该报文段的作用是A.主动打开连接B.被动打开连接C.询问对方是否同意建立连接D.询问对方是否准备好发送数据27.在域名系统中，域名解析采用A.迭代解析B.递归解析C.两者都是D.两者都不是28.在B/S架构的Web应用中，浏览器与服务器之间使用的应用层协议主要是A.HTTPB.FTPC.SMTPD.SNMP29.在RSA加密算法中，公钥为(e,n)，私钥为(d,n)。如果p和q是两个大素数，则n等于A.p+qB.p*qC.(p-1)*(q-1)D.p^q30.在数字签名技术中，发送方使用私钥进行加密，接收方使用发送方的公钥进行解密，这保证了A.数据的完整性B.数据的机密性C.发送方的身份认证D.通信的不可否认性31.下列协议中，用于电子邮件传输的协议是A.POP3B.SMTPC.HTTPD.Telnet32.在IEEE802.11无线局域网中，802.11a标准的工作频段是A.2.4GHzB.5GHzC.1GHzD.6GHz33.在TCP拥塞控制算法中，当网络发生拥塞时，发送方的拥塞窗口会A.减半B.加倍C.保持不变D.随机变化34.下列关于IPv6的描述中，错误的是A.IPv6地址长度为128位B.IPv6支持自动配置C.IPv6消除了广播流量D.IPv6简化了报头格式35.在OSPF协议中，路由器之间交换链路状态信息，用于计算最短路径的是A.Dijkstra算法B.Bellman-Ford算法C.Floyd算法D.Prim算法36.在ARP协议的工作过程中，主机A想知道主机B的MAC地址，它会发送A.一个ARP请求报文，目标IP地址为主机B的IPB.一个ARP请求报文，目标IP地址为55C.一个ARP请求报文，目标IP地址为D.一个ARP请求报文，目标IP地址为37.在HTTP/1.1协议中，支持持久连接，默认情况下A.每个请求都需要新的连接B.服务器在发送完响应后立即关闭连接C.客户端可以发送多个请求而不关闭连接D.连接在收到第一个请求后立即建立38.数字签名利用非对称加密算法，其安全性依赖于A.加密算法的复杂性B.解密算法的复杂性C.密钥对的保密性D.哈希函数的单向性39.在SNMP网络管理模型中，用于存储设备配置信息和管理信息的数据库是A.MIBB.OIDC.AgentD.Manager40.在计算机网络中，CSMA/CD协议适用于A.以太网B.令牌环网C.FDDI网D.ATM网二、综合应用题（共7小题，共70分）41.（15分）已知一棵二叉树的前序遍历序列为：A,B,D,E,C,F,G；中序遍历序列为：D,B,E,A,F,C,G。（1）画出该二叉树；（2）写出该二叉树的后序遍历序列；（3）若对该二叉树进行层次遍历，则遍历序列为？42.（18分）某计算机采用定点补码表示整数，机器字长16位。其中，1位符号位，15位数值位。采用一次乘法器，乘法运算通过累加和移位实现。（1）写出该机器数能表示的最小正数和最大正数；（2）写出该机器数能表示的最小负数（绝对值最大）；（3）若两个操作数分别为X=+0.1010，Y=-0.1101，采用Booth编码算法计算X*Y的值，请写出计算过程及最终结果。43.（13分）某系统有三个进程P1,P2,P3，共享一个资源R，资源R最多只能被一个进程使用。三个进程请求资源的情况如下：P1请求R：若可用则获得，否则等待；P2请求R：若可用则获得，否则等待；P3请求R：若可用则获得，否则等待。（1）若系统为R分配了1个单位，此时系统状态是安全的吗？请给出一个安全序列；（2）若系统为R分配了2个单位，此时系统状态是安全的吗？请给出一个安全序列。44.（12分）某文件系统采用树形目录结构，根目录常驻内存。目录文件采用链接存储，每个目录项包含文件名、文件长度及指向下一目录块的指针。磁盘块大小为512字节，每个目录项占32字节。假设某目录文件有N个文件，且分布在不同磁盘块中。（1）要查找一个文件，最多需要访问多少个目录块？（2）要删除一个文件，最多需要访问多少个目录块？（3）若要插入一个文件，平均需要访问多少个目录块？45.（24分）某网络拓扑如下图所示（假设图中各链路带宽均为1Mbps，传播延迟为5ms，分组大小为1000字节，忽略帧头开销）。主机A向主机B发送数据，主机B向主机A发送确认，采用停止-等待协议。（1）若主机A以1Mbps速率连续发送数据，不考虑ACK分组大小和传播延迟，信道的利用率是多少？（2）若ACK分组长度为100字节，传播延迟为5ms，则信道的利用率是多少？（3）若主机A发送数据包后，主机B的接