一．填空题（每题2分，共20分）；1.数据结构算法中，通常用时间复杂度和___空间复杂度_两种方法衡量其效率。2.下面程序段的时间复杂度为___O(n2)___。(n>1)for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;3.在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动____n-i+1___个元素。4.在n个结点的单链表中要删除已知结点*p，需找到它的__前驱_。5.在具有n个元素空间的循环队列中，队满时共有_____n-1____个元素。6.两个串相等的充分必要条件是___串长相等且对应字符相等_____。7.具有256个结点的完全二叉树的深度为_9__。8.G是一个非连通无向图，共有36条边，则该图至少有___9___个顶点。边数=N(N-1)/29.在顺序表（8,11,15,19,21,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为___4____。10.直接插入排序用监视哨的作用是_始终存放待插入的记录，免去查找过程中每一步都要检测整个表是否查找完毕_______。二．单项选择题1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表2.设a1、a2、a3为3个结点，则如下的链式存储结构称为：(A)表元编号结点表元间关系1a132a213a32A．循环链表B．单链表C．双向循环链表D．双向链表3.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（B）A.543612B.346521C.453126D.2341564.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B）。A.top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]5.数组Ｑ［ｎ］用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为(D)A.rear－frontB.（n＋front－rear）%nC.n＋rear－frontD.（n＋rear－front）%n6.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4,e6,e5，e3,e1则栈S的容量至少应该是(B)。A．6B.4C.3D.27.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(B)。A.BA+141B.BA+180C.BA+222D.BA+2258.已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项t的运算是（D）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）9.一棵树高为K的完全二叉树至少有（C）个结点?A．2–1B.2–1C.2D.2kk-1k-1k10.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（C）的二叉树。A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数D．任一结点无右子树11.无向图G=(V,E),其向V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是(A）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b12.下面关于求关键路径的说法不正确的是（B）。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作(C)型调整以使其平衡。A.LLB