搜索
期末考试一、选择题：15x2’=30’二、填空题：15x1’=15’三、两道编程题+画图题1、算法时间复杂度2、线性表的定义3、顺序表：顺序表的合并（比较次数）；线性表查找、删除、插入结点操作4、单链表：查找、删除、插入5、栈、队列：栈满、栈空以及队满、队空的判断6、存储密度的定义与计算7、拓扑排序12级数据结构模拟题10、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为C。A.nB.(n-1)/2C.n/2D.(n+1)/2//在第i个结点后面插入一个新节点需要移动后面n-i个结点，还有一种情况是插入到第一个结点前面要移动n个结点，所以有n+1种插入情况，平均移动结点的数目可以这样计算：1/(n+1)*(0+1+2+3+......+n)=1/(n+1)*(n*(n+1)/2)=n/211、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为C。A.nB.n/2C.(n+1)/2D.(n-1)/2分析：第i个元素出现的概率为1/n,所以第i个元素的期望查找长度为i，则平均查找长度即总期望长度为1/n*(1+2+3+……+n)=1/n*n(n+1)/2=(n+1)/2*13、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是A。A.nB.2n-1C.2nD.n-18、设栈S和队列Q的初始状态为空,元素e1，e2，e3，e4，e5和e6依次通过栈，一个元素出栈后即进入队列Q,若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是C。A.6B.4C.3D.210、循环队列SQ队满的条件是。A.SQ-rear==SQ-frontB.(SQ-rear+1)%MAXLEN==SQ-frontB.SQ-rear==0D.SQ-front==0//选项B应该是队空的情况，队满时应该满足：(SQ-rear+2)%MAXLEN==SQ-front13、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为。A.42B.16C.17D.41//循环队列中，front指向第一个元素，rear指向最后一个元素，因此本题中元素个数应该为32-15+1=18个？？？（rear-front+n+1）%n?15、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为C。A.O(m)B.O(n)C.O(m+n)D.O(m×n)*17、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为D。A.20%B.40%C.50%D.33.3%存储密度：结点数据本身所占的存储量/结点结构所占的存储总量本题中存储密度=1/（1+2）=33.3%20、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a,b,c,d,e元素依次进队，则不可能得到的顺序是C。A.bacdeB.dbaceC.dbcaeD.ecbad4、对于循环向量的循环队列，求队列长度的公式为（rear-front+n+1）%n。*5.已知广义表(a,b,c,d)的表头是A，则表尾是D；A.aB.()C.(a,b,c,d)D.(b,c,d)9、深度为h的完全二叉树至少有D个结点，至多有B个结点A.2hB.2h-1C.2h+1D.2h-1//满二叉树是完全二叉树结点最多的情况10、具有n个结点的满二叉树有个叶结点。A.n/2B.(n-1)/2C.(n+1)/2D.n/2+1//n个结点的满二叉树深度：（2^h）-1=n,叶结点的个数：x=2^(h-1)=(2^h)/2//所以，x=(n+1)/211、一棵具有25个叶结点的完全二叉树最多有个结点。A.48B.49C.50D.51//完全二叉树：结点最多时k-1层最右非终结结点只有一个左分支，此时，度为0的只有叶节点，25个，度为1的只有非终结结点1个，度为2的有25-1个，所以结点最多为25+1+24=50个*3、广义表(a,(a,b),d,e,((i,j),k))的长度是5，深度是3。2、n个结点的线索二叉树上含有的线索数为C。A.2nB.n-1C.n+1D.N//二叉树中叶子节点比度为2的结点多一个，而线索二叉树中叶子结点都有两条线索，度为1的结点有一条线索，度为2的结点没有线索，所以二叉树除去其中一个叶子节点剩下的n-1个结点有n-1条线索，再加上除去的叶子节点的两条线索一共n+1条线索*5、在结点数为n的堆中插入一个结点时，复杂度为C。A.O(n)B.O(n2)C.O(log2n)D.O(logn2)//如果对的高度为h，则需要遍历h次3、将一棵树T转换为二叉树B，则T的后根序列是B的B。A.先根序列B.中根序列C.后根序列D.层次序列3、G是一个非连通无向图，共有28条边，则该图至少有D个顶点。A.6B.7C.8D.9//首先连通图顶点一定边数最多的情况为各顶点倆俩相连，此时边数为n(n-1)/2,则当顶点个数为8的时候边数最多为28，又G是非连通图，至少有一个独立的点，所以该图至少有9个顶点。4、下面关于工程计划的AOE网的叙述中，不正确的是B。A.关键活动不按期完成就会影响整个工程的完成时间。B.任何一个关键活动提前完成，那么整个工程将会提前完成。//（除非该关键活动在所有的关键路径上）C.所有关键活动都提前完成，那么整个工程将会提前完成。D.某些关键工程若提前完成，那么整个工程将会提前完成。3、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作C型调整使其平衡。A.LLB.LRC.RLD.RR2、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是C：A.(100,80,90,60,120,110,130)B.(100,120,110,130,80,60,90)C.(100,60,80,90,120,110,130)D.(100,80,60,90,120,130,110)编程题1.线性表-单链表typedefintelementtype;//元素类型structcelltype//链表节点{elementtypeelements;celltype*next;};typedefcelltype*LIST;//单链表的型typedefcelltype*position;//线性表的“型”与位置的“型”相同//复制链表voidcopy(LIST&L1,LISTL2){positionp1=0,p2=0,p3=0;for(p3=L2;p3;p3=p3-next){p1=newcelltype;p1-elements=p3-elements;if(L1==0){L1=p1;p2=p1;}else{p2-next=p1;p2=p1;}}p2-next=NULL;}//删除指定元素的节点intDelete(LIST&L,intx){intm=1;//指定元素在线性表中的位置positionp1=0,p2=0;if(L-elements==x){p1=L;L=L-next;deletep1;returnm;}else{p1=p2=L;while(p1-elements!=x&&p1!=NULL){p2=p1;m++;p1=p1-next;}p2-next=p1-next;deletep1;returnm;}return-1;//不存在元素x}2.线性表-双向链表typedefintElementtype;structcelltype{Elementtypeelement;//数据域celltype*previous,*next;//前驱和后驱};typedefcelltype*position;//位置的型typedefcelltype*DLIST;//双向链表的型//插入元素,在p后面插入，根据p后面有没有结点分为表尾插入和表中插入voidinsert(positionp,Elementtypex){if(p-next){positionq=newcelltype;q-element=x;q-next=p-next;q-previous=p;p-next-previous=q;p-next=q;}else{positionq=newcelltype;q-element=x;q-next=p-next;q-previous=p;p-next=q;}}//删除中间结点voidDelete(positionp){if(p-next!=NULL&&p-previous!=NULL)//删除的不是头尾结点{p-previous-next=p-next;p-next-previous=p-previous;deletep;}elsecout头尾结点不是中间结点，不能删除！endl;}intswap(Elementtypex,DLIST&head)//查找交换{positiontemp,L;temp=head;while(temp-next){temp=temp-next;if(temp-element==x&&temp-previous!=head)//元素匹配并且前驱不能是头结点{L=temp-previous;L-previous-next=temp;temp-previous=L-previous;L-next=temp-next;temp-next-previous=L;L-previous=temp;temp-next=L;return1;}}return0;}3.队列typedefintque_elementtype;//队列元素类型//队列元素节点类型structcelltype{que_elementtypeelement;celltype*next;};//队列结构型structQUEUE{celltype*front;celltype*rear;};//front指向头结点，rear指向最后一个元素，当rear也指向头结点时队列为空4.线性表-栈#definemaxlength100//栈的容量typedefintElementtype;//数制转换中元素类型为int//typedefcharElementtype;//括号匹配中元素类型为字符型char//栈的数组实现//此处将栈底规定在数组的底部，即让maxlength-1指向栈底的第一个元素，top指针指向栈顶元素structSTACK//定义整型线性数组栈{inttop;Elementtypeelements[maxlength];};//数制转换voidconvert(intnum,STACK&S,intn)//进制转换函数{while(num!=0){push(S,num%n);num/=n;}}//括号匹配Booleancheck(char*s){//算法思路：遍历字符数组s，如果是左括号则入栈，如果是右括号则跟栈顶符号进行匹配，//匹配失败立即返回FALSE，匹配成功将栈顶出栈，继续运行STACKS;makeNull(S);intj=0;while(s[j]!='\0'){switch(s[j]){case'(':push(S,'(');break;case')':if(top(S)=='(')pop(S);elsereturnFALSE;break;case'[':push(S,'[');break;case']':if(top(S)=='[')pop(S);elsereturnFALSE;break;case'{':push(S,'{');break;case'}':if(top(S)=='{')