2018四川大学874

第1页2018年攻读硕士学位研究生入学考试试题考试科目:计算机科学专业基础综合科目代码:874（试题共8页）（答案必须写在答题纸上，写在试题上不给分）数据结构与算法（65分）一、单项选择题（每小题2分，共17小题，共34分1.下面关于“算法”的描述，错误的是（）A.算法必须是正确的B.算法必须要能够结束C.一个问题可以有多种算法解决D.算法的某些步骤可以有二义性2.下面函数的时间复杂度是（）voidfunc(intn){intsum＝0,i,j;for(i＝1;in;i++)for(j＝1;jn;j*＝2)sum++;A.O(log2n)B.O(n2)C.(nlog2n)D.O(n)3.下面关于线性表的叙述中，错误的是（）A.线性表采用顺序存储，必须占用一片连续的存储单元B.执行查找操作时，链式存储比顺序存储的查找效率更高。C.线性表采用链式存储，不必占用一片连续的存储单元。D.线性表采用链式存储，便于插入和删除操作。4.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间A.单链表B.带头指针的单循环链表C.带尾指针的单循环链表D带头结点的双循环链表第2页5.一个栈的输入序列为1，2，3，....，n，若输出序列的第一个元素是n，则输出的第i(1=i=n)个元素是（）A.不确定B.n-i+1C.iD.n-i6.若一棵完全二叉树有666个结点，则该二叉树中叶子结点的个数是（）A.156B.155C.333D.3347.对于下列关键字序列，不可能构成某二叉查找树中一条查找路径的序列是（）A.99，28，86，36，94，65B.97，18，89，34，76，42C.16，91，68，29，33，50D.21，27，80，76，29，398.下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）A.二叉查找树B.哈夫曼树C.AVL树D.堆9.在右图的AVL树中插入关键字18后得到一棵新AVL树，在新AVL树中，关键字11所在结点的左、右孩子结点中保存的关键字分别是（）A.7，16C.9，26B.9，18D.7，1810.将一棵树T1转化为对应的二叉树T2，则T1后序遍历序列是T2的（）序列A.前序遍历B.中序遍历C.后序追历D.层次遍历11.当各边上的权值（）时，BFS算法可用来解决单源最短路径问题A.均相等B.均互不相等C.较小D.以上都不对12.已知有向图G=(V,E)，其中V={V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V2,V6,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7}，则G的一个拓扑序列（）A.V1，V3，V2，V6，V4，V5，V7B.V1，V3，V4，V6，V2，V5，V7C.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7第3页13.采用Kruskal算法求右图的最小生成树时，依次选择的边是（）A.(a,b)(b,c)(c,d)(d,f)(a,e)B.(d,f)(c,d)(b,c)(a,b)(a,e)C.(a,b)(b,c)(d,f)(c,d)(a,d)D.(a,b)(d,f)(b,c)(c,d)(a,e)14.设哈希表长为13，哈希函数是H（key）=key％13，表中已有关键字18，39，75，93共四个，现要将关键字为70的结点加到表中，用伪随机探测再散列法解决冲突，使用的伪随机序列为5，8，3，9，7，1，6，4，2，11，13，21则放入的位置是（A.8B.11C.7D.515.一棵高度为3的3阶B树，至少含有（）个关键字A.12B.10C.7D.都不是16.在下列排序算法中，哪一个算法的时间复杂度与数据的初始排列无关（）A.直接插入排序B.希尔排序C.快速排序D.基数排序17.数据表中有10000个元素，如果仅要求求出最大的3个元素，则采用（）算法最节省时间A.堆排序B.希尔排序C.快速排序D.直接选择排序二、综合应用题（18-20题，共31分18.（10分）对于一个字符集中具有不同权值的字符进行Huffman编码时，如果已知某个字符的Huffman编码为0101，对于其他无字符的Huffman编码，请分析说明:（1）具有哪些特征的编码是不可能的（2）具有哪些特征的编码是一定会有的19.（10分）设有向图用邻接表表示，图有n个顶点，表示为0至n-1，试写一个算法求顶点k的入度（0＜＝k＜n）20.（11分）二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild)，child，rchild左右儿子指针；data是数据元素；bf是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。第4页操作系统（50分）一.单项选择题（26分，每题2分）1.如果一个程序被多个进程共享，那么该程序的代码在执行过程中不能被修改，即程序应该是？A可执行码B可重入码C可改变码D可再现码2.当被阻塞进程所期待的事件出现时，如I/0操作完成或等待的数据到达，则调用唤醒原语操作，将被阻塞的进程唤醒请问唤醒被阻塞进程的是？A.被阻塞进程的父进程B.被阻塞进程的子进程C.被阻塞进程自身D.与被阻塞进程相关的进程或其他进程3.某基于动态分区存储管理的计算机，其主存的容量为55MB，这些空间在初始为空闲。采用最佳分配算法，分配和释放的顺序分别为:分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是？A7MBB9MBC10MBD15MB4.关于DMA（DirectMemoryAccess），下列说法哪个是正确的？A.进程可以直接读写一个外部设各B.内核可以直接读写进程的内存而不需要缓冲区C.进程可以直接读写内核内存而不需要缓冲区D.外部设备可以直接读写系统内存5.当一个程序被装入内存准备开始执行时，下面哪个段的大小是操作系统不知道的？A.textB.dataC.bssD.heap6.假设某系统中的TLB的命中率大约为75％，并且使用了2级页表，那么平均内存时间为？A.大约是原来的1.25倍B.大约是原来的1.5倍C.大约是原来的1.75倍D.大约是原来的2倍第5页7.在动态分区存储系统中，空闲表的内容如下:空闲块号1234块大小80755590块的基址60150250350此时，进程P请求50KB内存，系统从第1个空闲块开始查找，结果把第4个空闲块分配给了进程P。请问系统是采用哪种分区分配算法实现这一方案？A首次适应法B最佳适应法C最差适应法D下次适应法8.某系统使用32位逻辑地址，页大小为4kbytes，以及36位物理地址。那么该系统中的页表大小为？A.2^20个页表项(2^(32-12)B.2^24个页表项(2^(36-12))C.2^4个页表项(2^(36-32))D.2^12个页表项9.在上下文切换期间，操作系统做了以下哪项工作？A修改了页表中的某些项，以反映新进程的内存映射B切换页表寄存器指向另外的页表C为新进程修改页表中的访问权限D因为页表是系统级别的资源，所以并不会修改页表10.下列选项中，降低进程优先权级的合理时机是？A、进程的时间片用完B、进程刚完成I/0，进入就绪列队C、进程长期处于就绪列队D、进程从就绪状态转为运行状态11.设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待该资源的进程数，则M，N分别是？A.0，1B.1，0C.1，2D.2，012.有以请求分页的存储管理系统，页面大小为100B，有一个50×50的整型数组，按行为主序连续存放，每个整数占2B，将数组初始化为0的程序描述如下:intA(50)(50);for(inti=0;i50;i++)for(intj=0;j50;j++)A(i,j)＝0;第6页若在程序执行时内存只有一个存储块用来存放数组信息，试问该程序执行时产生多少次缺页中断？A.1B.50C.100D.250013.某文件中共有3个记录，每个记录占用1个磁盘块，在1次读文件的操作中，为了读出最后1个记录，不得不读出了其他的2个记录。根据这个情况可知这个文件所采用的结构是？A顺序结构B链接结构C索引结构D顺序结构或连接结构二.综合题（24分，每题8分）1.设文件索引节点中有8个地址项，其中4个地址为直接地址索引，2个地址项是一级间接地址索引，2个地址项是二级间接地址索引，每个地址项的大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，计算可表示的单个文件最大长度。（8分）2.已知某系统页面长4K字节，页表项4字节，采用多层分页策略映射64位虚拟地址空间。若限定最高层页表占1页。问它可以采用几层分页策略。（8分）3.有一只球框，最多可以容纳两个球。每次只能放入或取出一个球男教师专门向框中放入白球(wb)，女教师专门向框中放入黑球(bb)。男生专门拿框中的白球(wb)，女生拿框中的黑球(bb)。请用Wait，Signal操作实现男教师，女教师，男生，女生之间的同步关系。（8分）计算机网络（共35分）一、选择题（每题2分，共9题，18分）1关于ARPANET特征的描述中，不正确的是（）A.ARPANET的成功运行证明了交换理论的正确性B.ARPANETInternet的基础C.Web服务的出现促进了ARPANET的发展D.ARPANET采用的是TCP/IP标准2.如果发送数据比特序列为11110011，生成多项式比特序列为11001，那么发送方法给接收方的比特序列为（）A.111100110001B.111100111100C.1111001111001D.111100111110第7页3.IP分组分片基本方法中，描述错误的是（）A.IP分组长度大于MTU时，就必须对IP分组进行分片B.DF＝1，分组的长度超过MTU，则丢弃分组，不需要向源主机报告C.分片MF值为1表示接收的分片不是最后一个分片D.片偏移值是以8字节为单位来计数的4.假如有一个公司有一个A类IP地址，原来内部有700个子网，公司重组之后需要再建450个子网，而且要求每个子网最多可以容纳4092台主机，含适的子网掩码是（）A./16B./17C./18D./195、以下关于TCP支持可靠传输服务的描述中，错误的是（）A.TCP使用确认机制来检查数据是否安全和完整地到达，并提供拥塞控制功能B.TCP对发送和接收的数据进行跟踪、确认和重传，以保证数据能够到达接收端C.TCP能够通过校验和来保证传输的可靠性D.TCP采用滑动窗口方法进行流量控制。6.如果子网掩码为255.255.192.0，那么下列地址的主机中必须通过路由器才能够与主机125.2.144.6通信的是（）A.125.2.190.32B.125.2.144.27C.125.2.192.160D.125.2.176.2217.一台交换机具有24个10/100Mbps的端口和两个1Gbps端口，如果所有端口都工作在全双工状态，那么交换机的最大带宽为（）A.4.4GB.6.4GC.6.8GD.8.8G8.在MAC协议中，对正确接收的数据帧进行确认的是（A.CDMAB.CSMAC.CSMA/CDD.CSMA/CA9.在对OSI参考模型中第n层与n＋1层关系的描述中，正确的是（）A.第n-1层为第n层提供服务B.第n层和n＋1层之间是相互独立的C.第n层利用n＋1层提供的服务为n-1层提供服务D.第n＋1层为从n层接收的数据添加一个头部第8页二、计算题（共17分）（8分）1.根据图1所示的网络拓扑结构及地址，请写出R1的路由表，其中R1有两个接口m1和m0，路由表形式如下表所示。（要求R1的路由表的表项在满足路由情况下，尽可能精简）图1拓扑结构目的地址子网掩码（用点分十进制表示）下一跳转发端口（9分）2.假设把一个大小为3000bit的数据报从源主机发送到目的主机，中间经过4个路由器，共5段链路。每条链路的传