搜索
共6页，第1页学生答题注意：勿超黑线两端；注意字迹工整。共6页，第2页试卷真假请读者自己辨别安徽大学2013年硕士研究生入学考试一、单项选择01．以下说法正确的是。A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构02．在以下的叙述中，正确的是。A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出03.二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是()A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．以上答案都不对04.有n个叶子的哈夫曼树的结点总数为（）。A．2n-1B．2nC．2n+1D．不确定05.有一个具有n个顶点的连通图生成的最小生成树中,具有()条边A、nB、n-1C、n+1D、2n-106.下面的二叉树中，（）不是平衡二叉树。ABCD07.知U=‘xyxyxyxxyxy’；t=‘xxy’；依次执行下列运算后，ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；ASSIGN（m，‘ww’），则REPLACE（S，V，m）结果为()。A．’xyxywwyxy’B．’xyxyxywwy’C．’xyxyxwwxy’D．’xyxywwxyx’.08.、某二叉树的层序序列是abcdefgh，中序序列是dbgehacf，则该树的后序序列是_______________。A.fahgbecB.eagbfdcC.dghebfcaD.acdbfge09.依次读入数据元素序列{a,b,c,d,e,f}进栈,每进一个元素机器可要求下一个元素进栈和出栈.如此进行,则栈空时弹出的元素构成的序列不可能出现()A、{c,d,b,e,f,a}B、{d,c,e,b,f,a}C、{b,d,c,e,a,f}D、{b,e,d,a,c,f}10.从具有n个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为()A、0(n)B、0(1)C、0(logn)D、O(n²)11..若P、V操作的信号量S初值为2，当前值为–1,则表示有等待信号量S所代表资源的进程。A．0个B．1个C．2个D．3个12..进程因为执行P（S）操作而阻塞，则执行P（S）操作后，.Value一定。A．=0B．0C．0D．不确定13.信箱通信方式是一种通信方式。A.直接通信B.间接通信C.低级通信D.信号量14.为多道程序提供的共享系统资源不足时，可能出现死锁；不适当的也可能产生死锁。A．程序并行操作B．资源的线性分配C．进程推进顺序D．分配队列优先权15..采用资源剥夺法可解脱死锁，还可以采用_________方法解脱死锁。A．停止并行操作B．撤消进程C．拒绝分配新资源D．修改信号量16.发生死锁的必要条件有四个，要防止死锁的发生，应该破坏这四个必要条件之一，但破坏条件是不实际的。A．互斥B．不可抢占C．部分分配D．循环等待17.SPOOLing系统是___________。A.现代操作系统的重要组成部分B.操作系统中采用的一项重要技术C.一种用于输入输出操作的系统得分----------------------装---------------------------------------------订----------------------------------------线----------------------------------------共6页，第3页学生答题注意：勿超黑线两端；注意字迹工整。共6页，第4页得分D.一种输入输出的手段18.将系统中的每一台设备按某种原则进行统一的编号，这些编号作为硬件区分和识别设备的代号，该编号称为设备的______________。A.物理编号B.逻辑编号C.类型号D.符号名19.从用户角度看，引入文件系统的主要目的是_________________。A.实现虚拟存储B.保存系统文档C.保存用户和系统文档D.实现对文件的按名存取20.文件的逻辑组织将文件分类记录式文件和_________________文件。A.索引文件B.流式文件C.字符文件D.读写文件二、填空题1.与链式存储结构不同，顺序存储结构是通过________表示元素之间的逻辑关系的。2.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用遍历方法最合适。3.在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。4.对于17个元素的有序表A[1]-A[17]作二分查找,在查找其等于A[8]的元素时需比较_____次.5.树的三种存储结构是双亲表示法、孩子表示法和。6.若不考虑基数排序，则在内部排序过程中，主要进行的两种基本操作是关键字的比较和记录的。7.一个“好”的算法要考虑以下标准：正确性、可读性、和效率与低存储量需求。8.已知一个无向图的邻接表如下图所示:则从顶点1出发进行深度优先搜索遍历得到的顶点序列为_____________和广度优先搜索得到的顶点序列为_______________。9.在含有n个结点的二叉链表中，其空链域个数是。10进程的基本特征有______、______、______、______、______。11.信号量的物理意义是___________________________________。12.临界资源是_____________，而临界区是指_______________________。13.将作业地空间中逻辑地址转换成主存中的物理地址的过程称为。14.在请求页式管理中，页面置换算法通常用的有和两种。15.页式和段式管理中，指令的地址结构形式分别为和。三、判断题（判断下面叙述的正误，正确的打“√”，错误的打“×”）1．在决定选取何种存储结构时，一般不考虑各结点的值如何。（√）2．抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一ADT的逻辑特性，不必考虑如何在计算机中实现。（√）3．抽象数据类型与计算机内部表示和实现无关。（√）4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（×）5．线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（×）6．对任何数据结构链式存储结构一定优于顺序存储结构。（×）7．顺序存储方式只能用于存储线性结构。（×）8．集合与线性表的区别在于是否按关键字排序。（×）9．线性表中每个元素都有一个直接前驱和一个直接后继。（×）10．线性表就是顺序存储的表。（×）11.并发性是指若干事件在同一时间间隔内发生。()12.进程退出临界区时要执行信号量的P操作。()13.P/V操作只能解决互斥问题。()14.管态就是一种特权状态。()15.进程是程序的一次执行，因此进程与程序是一一对应的。()第二题，第8小题图共6页，第5页学生答题注意：勿超黑线两端；注意字迹工整。共6页，第6页得分四、分析计算题1．对于如下的连通图，请给出从顶点0出发，利用普里姆（Prim）算法求出它的最小生成树的过程中得到的顶点集和边集及最小生成树的权，并画出所得到的最小生成树。1268151316412920105（第三大题第1题图）2．设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，画出所对应的二叉树。T1T2T3森林（第三大题第2题图）3.记录的关键字集合K={23，9，39，5，68，12，62，48，33}，请给出采用快速排序法进行排序时每趟划分后的排序结果（选第一个记录为枢轴（支点）分割）。4．给定关键字序列15,38,61,84,49,60,71,33,24,29,36，一组数据用冒泡排序进行排序5．某赋权有向图如下图所示。用迪杰斯特拉（Dijkstra）算法思想，求源点A到各其余顶点的最短路径及路径长度0541632BAEDCFGHIJKBACEG152126844共6页，第7页学生答题注意：勿超黑线两端；注意字迹工整。共6页，第8页（第四大题第5题图）6.设系统中有A、B、C三种资源和P1、P2、P2、P2、p5五个进程，A资源的数量为17，B资源的数量为5，C资源的数量为20。T0时刻系统状态如下：最大需求已分配资源数量ABCABCP1559212P2536402P34011405P4425204P5424314a)T0时刻系统是否安全？若是，请给出一个安全序列。b)T0时刻P2请求资源（0，3，4），是否可以实施资源分配？为什么？c)T0时刻P4请求资源（2，0，1），是否可以实施资源分配？为什么？7.在一个分页存储管理系统中，地址结构和一个进程的页表如下所示（“--”表示页面不在内存），以逻辑地址086AH为例，简要说明页式地址变换的过程，画出地址变换示意图，转换后的物理地址是多少？地址结构：页号P页内位移W151090页表：页号01234567块号2--4--7----18.假设有一磁盘有6400块，每块长度为1024字节，块号记作0—6399，现用400个16位（Bit）的字作该磁盘的位示图，试问第2999块对应于位示图中的第几字的第几位（字、位均从0开始计）；而第299字的第7位（同上，从0开始）又对应第几块？五、算法设计题1.写出在一个链表中的第一个节点前面插入一个数的算法得分DF510