数据结构与算法期末练习题(含答案)

《数据结构与算法》期末练习一选择题以下与数据的存储结构无关的术语是（D。循环队列 B.链表 C.哈希表 D.栈算法的时间复杂度取决于（A）问题的规模 B.待处理数据的初态 C.A和B D.计算机cpu一个栈的输入序列为1234则下列序列中不可能是栈的输出序列的是（BA.23415 B.54132 C.23145 D.15432它存取表中第i个元素的时间与i(2)静态链表中能容纳的元素个数的最大数在表定(3)B）A（2） 1） 1（,(3) D）对于有n（D）nlogn n n|+1 D．不确定2 2 2（C）A．B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．D．在设无向图的顶点个数为n，则该图最多有（B）条边。A．n-1 B．n(n-1)/2 n(n+1)/2 8G=(V,EV={V,V,V,V,V,V,VE={<V,V>,<V,V>,<V,V>,<V,V>,1 2 3 4 5 6 7 1 2 1 3 1 4 2 5<V,V<V,V<V,V<V,V<V,V>},G（A。3 5 3 6 4 6 5 7 6 7A．V,V,V,V,V,V,V ,V,V,V,V,V,V1 3 4 6 2 5 7 1 3 2 6 4 5 7C．V,V,V,V,V,V,V ,V,V,V,V,V,V1 3 4 5 2 6 7 1 2 5 3 4 6 79．下列排序算法中，其中（D）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.希尔排序，归并排序D.归并排序，冒泡排序对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为1）8447251521）1547258421（3）1521258447(）1521254784A)。A.选择 B.冒泡 C.快速 D.插入以下数据结构中，哪一个是线性结构（D）？广义表 B.二叉树 C.稀疏矩阵 D.串下面关于线性表的叙述中，错误的是哪一个？（B）A．B．线性表采用顺序存储，便于进行插入和删除操作。C．D．线性表采用链接存储，便于插入和删除操作。设一个栈的输入序列是则下列序列中是栈的合法输出序列的（DA.51234 B.45132 C.43125 D.32154 n的语句的频度为（Bi=1;k=0;do{@k+=10*i;i++;}While(i<=n-1);n–1 B.n C.n+1 D.n-2 一棵具有n个结点的完全二叉树的树高度（深度）是（A）A．logn+1 B．logn+1 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）元素是（B。不确定 B.n-i+1 C.i D.n-i18．n（D。A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）稳定的排序方法是（B）直接插入排序和快速排序 B．折半插入排序和起泡排序C．希尔排序和四路归并排序 树形选择排序和shell排有一组数据据的排序为(A)按递增序。A．下面的B，C，D都不对。 C．20，15，8，9，7，-1，4，7 D.9，4，7，8，7，-1，15，20以下那一个术语与数据的存储结构无关？（A）栈 B.哈希表 C.线索树 D.双向链表下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列 空串是由空格构成的C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（D。a，c，b，d B.b,C.c,a D.d,c，a，b0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K叉树。正确的是（D）A．①②③B．②③④C．②④D．①④K（C。2k2k-1

-1 D．2k-1-1（C）A．B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．用树的前序遍历和中序遍历可以导出树的后序遍历。D．哈27.关键路径是事件结点网络中（A。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路DFSDFSAA．逆拓扑有序 拓扑有序 无序的一组记录的关键码为46，7，5，3840，8记录为基准得到的一次划分结果为（C。A．(38,40,46,56,79,84) B.(40,38,46,79,56,84)C．(40,38,46,56,79,84) D.(40,38,46,84,56,79)一个向量的第一个元素的地址是ki(D)A.begin+(k-1)i B.begin+(k-2)iC.begin+kiD.begin+(i-1)k31.有一个有序表为{1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要经过(C)次与63比较。A.12 B.6 C.4 D.5一个序列的初始状态为4677，8，5，3，70D)。C.（46，31,D.(46将一个长度为niB)个元素。A.i B.n-i C.n+1 D.n-i+1不带表头的单链表，头指针为headA)A.head==0B.head->next==nullC.head==headD.head->next==head*q表示指针q*q之后插入结点*s，正确的操作步骤序列是(A)。A)q->next=s;s->next=p B)s->next=p->next;q->next=s;C)p->nexr=s;s->next=p; D)p->next=s;s->next=q;非空循环链表head的尾结点*p满足下列(C)条件A)head->next==p;B)head==p;C)p->next==head;D)p->next==0一个栈的输入序列是a,b,c,d,eD)。A.ecdabB)cebdaC)daecbD)abcde设栈ssqstackC)。A.s==NULLB)s->top==0C)s.top==0 D)s.top==NULL5的二叉树至多有个(B)结点。A.12B.31C.14D.15已知二叉树的后、中根序列分别是bedfca和badecf，则该二叉树的前根遍历序列是(C)。A)defbcaB)fedbcaC)abcdefD)fedcba一个有nB)弧。A)n(n+1)B)n(n-1)C)n(n+1)/2 D)n(n-1)/2具有n个顶点的无向图至少要(B条边才有可能是一个连通图A) n(n+1)B)n-1C)n+1 D)n(n-1)已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是(B)。A)1234 B) 1423 C) 1324 D)143214 ^2 ^3 ^23 ^4 ^314 ^2 ^3 ^23 ^4 ^32 ^4 ^4一个向量的第一个元素的地址是100，每个元素的长度是2，则第五个元素的地址是(C)A)102B)110C)108D)120一个循环顺序队列,队头、尾指针的值分别为front,rear，则队列中元素个数为(A（maxlen）(rear-front+maxlen)%maxlen(rear-front)%maxlenrear-front+1front-rear+1一个有nD)条边。A)n(n+1)B)n(n-1)C)n(n+1)/2 D) 0具有5个顶点的无向图至少要(A条边才能确保是一个连通图A)4 B)5C)6 D) 7设栈s的类型为sqstack，最多可容纳maxlenB)。A.s==maxlen-1B)s.top==maxlen-1C)s->top==maxlen-1 D)s.top==0一个顺序队列q的类型为sqqueuefront,reaC)。A)front==rearB)rear==0C)q.front==q.rearD)rear==maxlen-1在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度( B )A.O(1) B.O(n)C.O(nlogn) D.O(n*n)链栈与顺序栈相比，比较明显的优点( D )A.插入操作更加方便 删除操作更加方C.不会出现下溢的情况 不会出现上溢的情二叉树中第5层上的结点个数最多( C )A.8 B.15C.1653.下列编码中属前缀码的是(D.32A)A.{1,01,000,001}C.{0,10,110,11}B.{1,01,011,010}D.{0,1,00,11}如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（BA．深度优先搜索算法 B．广度优先搜索算法C．求最小生成树的prim算法 D．拓扑排序算法对n个关键字的序列进行快速排序，平均情况下的空间复杂度(BA.O(1) B.O(logn)C.O(n) D.O(nlogn)对表长为n度为(C)A.(n-1)/2 B.n/2C.(n+1)/2 D.n对于哈希函数H(key)=key%13,被称为同义词的关键字( D )A.35和41 B.23和39C.15和44 D.25和51（B）A线性表的特点是每个元素都有一个前驱和一个后继B线性表是具有n(n>=0)个元素的一个有限序列C线性表就是顺序存储的表D线性表只能用顺序存储结构实现表长为n时，删除一个元素需要移动元素的平均个数为（A）A(n-1)/2 Bn/2 CnDn-1设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针所指节点之后插入指针s？（D）Ap->RLink=s;s->LLink=p;p->RLink->LLink=s;s->RLink=p->RLink;Bp->RLink=s;p->RLink->LLink=s;s->LLink=p;s->RLink=p->RLink;Cs->LLink=p;s->RLink=p->RLink;p->RLink=s;p->RLink->LLink=s;Ds->LLink=p;s->RLink=p->RLink;p->RLink->LLink=s;p->RLink=s;栈和队列都是（A）A限制存取位置的线性结构B链式存储的非线性结构C顺序存储的线性结构D限制存取位置的非线性结构单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（AAO(n) BO(1) CO(n*n) DO(n*logn)一棵含有n个节点的k叉树，可能达到的最小深度为多少？（CAn-k Bn-k+1C|logn|+1D|logn| 其|k|表示下取整k kB)不是堆。A.12365368486075B.12485368366075C.12483660756853D.12366053486875在下列内排序方法中，(C)的平均时间复杂性是O(nlogn)。直接插入排序 B.简单选择排序 C.快速排序 D.希尔排序设顺序栈s非空，则语句段(C)可实现栈s的出栈操作，其中s.tops.elemxs.top:=s.top+1; B.x:=s.elem[s.top];x:=s.elem[s.top]; s.top:=s.top+1;C.s.top:=s.top-1; D.x:=s.elem[s.top];x:=s.elem[s.top]; s.top:=s.top-1;已知L指向表中某结点，则要删除p作(A)；要在psD)。pnext:=pnextnext; B..next;C.pnext:=s;snext:=pnext; D.snext:=pnext;pnext:=s;关键字有序（D。二叉排序树BC．AVLD．堆69.下面给出的四种排序法中(D)排序法是不稳定性排序法。A.插入 B.冒泡C.二路归并D.快速排序70.O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序2方法是（C。A.快速排序 B.堆排序 C.归并排序 D.直接插入排序二填空题1、在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null2、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是：(请在表达式中用点(.)将数隔开)23.12.3*2-4/34.5*7/++108.9/+3、有一个100*90092该矩阵时，所需的字节数是604、深度为9的完全二叉树具有的 个结点2565、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是ABDEGCF6、先根遍历树林正好等同于先序

_遍历对应的二叉树.7、构造n个结点的强连通图，至少条弧n8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为6,9,11,129ps10、有N个顶点的有向图，至少需要条弧才能保证是连通的N-111、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值12，需做的关键码比较次数为413、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处（顶点号由1开始）0101110100010101010110010该图的顶点数为 该图的边数为 顶点3的度为 56214、后根遍历树林正好等同于(6) 遍历对应的二叉树中序15、n个结点的完全有向图含有边的数n*（n－l）16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法。时间复杂度17、假设S和X分别表示进栈和出栈操作，由输入序列得到输出序列的操序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列。SXSSXXSSXSSXXX18、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数219、如图所示的有向无环图可以排种不同的拓扑序列。1220、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为( 75,66,48,29,31,3721、对长度为20的有序表进行二分查找的判定树的高度。522、n个顶点的连通无向图，其边的条数至少n-123、排序(sorting)有哪几种方法 ， ， ， ， 。直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序24、下面程序段的时间复杂度（用O估计）FORi:=1TOnDOFORj:=iTOns=s+j;O（n*n）25、非线性结构包和 树，图26、在线性表存储结构上进行插入或删除操作要移动元素顺序存储结构27、用一维数组r[0..m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front和rear，且队头指针所指的单元闲置，则队满的条件队空的条件。Front=rear,rear+1=front28、下面表达式树所对应的表达式的前缀表达式，后表达式。+*a-bc/de,abc-*de/+29在AOE-网中设e(i)和l(i)分别表示活动ai的最早开始时间和最晚开始时间，则当仅当 时，ai为关键活动。e(i)==l(i)30．对有向图进行拓扑排序，若拓扑排序不成功，则说明该。下面向图的一个拓扑有序序列。存在回路，12345679831、二叉排序树的特点是其 序列是有序的中序遍历三简答题11）（）算法的时间复杂性；（3）(hashing4）23、快速分类法的基本思想是什么?4用prime(5,4),则，下一条边应在哪几条边中选取？选取哪一条？175 225 383 641445 35、二叉树的后根遍历的序列中，任何一个非叶子结点均处在其孩子结点后面。该论断是否正确？6、有一棵哈夫曼树共有5个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。7、对于一个队列，若入队的顺序为a,b,c,则所有可能的出队序列是什么？8、已知一个图如下，试画出其逆邻接链表。112349、若一个栈的输入序列是1,2,3……，n,其输出序列为p1,p2,……pn,若p1=n，则pi为多少？10吗？11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。12、已知一个图如图所示，如从顶点aacebdf?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？aacbefd13、栈的存储方式有哪两种？14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中：priordatenextdatenextpriordatenextdatenext15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111。请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；和9，带权路径长度。1、对于线性表的两种存储结构（顺序存储和链式存储结构构？试说明理由。17、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈s1和s2并对两个栈的容量进行分析。18（1）2）画出该二叉树后序线索化图（3）试画出该二叉树对应的森林。19、一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。201,2,…,nP,PP（它是输入序列的1 2 n一个排列，则在输出序列中不可能出现这样的情形：存在着i<j<kP<P<P。j k i四算法阅读1、voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={1,5,8,12,15};for(i=0;i<5;i++)Push(S,2*a[i]);while(!StackEmpty(S))print(Pop(S));}该算法被调用后得到的输出结果为：2、voidABC(BTNode*BT,int&c1,int&c2){if(BT!=NULL){ABC(BT->left,c1,c2);c1++;if(BT->left==NULL&&BT->right==NULL)c2++;ABC(BT->right,c1,c2);}//if}该函数执行的功能是什么？3、在下面的每个程序段中，假定线性表La的类型为的类型为ElemType,元素类型ElemType为La。InitList(La);Inta[]={100,26,57,34,79};For(i=0;i<5;i++)ListInsert(La,1,a[i]);ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);ClearList(La);ForListInsert(La,i+1,a[i]);4、intPrime(intn){inti=1;intx=(int)while(++i<=x)if(n%i==0)if(i>x)return1;elsereturn0;}指出该算法的功能；该算法的时间复杂度是多少？写出下述算法A其中BiTreeTypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)){ DeQueue(Q,e);If(e==NULL)Else{Print(e.data);ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);}}}阅读下列函数algo,并回答问题：假设队列q中的元素为(2,4,5,7,8)algo(&q)后的队列q；简述算法algovoidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,while(!ＥnQueue(Q,Pop(&S));}五算法填空1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。typedefstructnode{intdata;structnode*next;}lklist;voiddel(lklistrear,int&x);{lklistp,q;q=rear->next;if( printf(“itisempty!\n”);else{p=q->next;x=p->data; ;if( )rear=q;;};};2typedefstruct{char*int }HString；HStringStatusStrCat(s，t)/*将串t连接在串s的后面*/{inti;char*temp;if(temp==NULL)return(0);for(i=0; temp［i］=s->ch［i］;for( ;i<s->len+t.len;i++)temp［i］=t.ch［i-s->len］;s->len+=t.len;frs->ch=temp;return(1);}3、向单链表的末尾添加一个元素的算法。LNode是一个包含（data，Next）的结构体VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newIf( ){cerr<<"Memoryallocationfailare!"<<endl;exit(1);} newptr->next=NULL;if(HL==NULL)HL= ;else{LNode*P=HL;While(P->next!=NULL) p->next=newptr;}}4Lf30的功能是删除L中数据域data的值大于c请在空缺处填入合适的内容，使其成为一个完整的算法。LinkListf30(LinkListL,intc){LinkListLc,p,pre;pre=L;p= (1) ;Lc=(LinkList)malloc(sizeof(ListNode));Lc->next=Lc;while(p!=L)if(p->data>c){pre->next=p->next;(2) ;Lc->next=p;p=pre->next;}else{pre=p;(3) ;}returnLc;}adjvexnextvertexfirstedgeadjvexnextvertexfirstedge下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。intFindDegree(ALGraph*G,inti)//ALGraph为图的邻接表类型{intdgree,EdgeNode*p;degree= (1) for(j=0;j<G->n;j++){p=G->adjlist［j］.firstedge;while( (2) ){if( (3) ){degree++;break;}p=p->next;}}returndegree;}六简单应用题1GBAHEDJFIBCHEJIFDA试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么?2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。3、画出由下面的二叉树转换成的森林。4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表：1A1A(0)231A(1)231A(2)231A(3)231PATH(0)231PATH(1)231PATH(2)231PATH(3)23123PATH1235、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。weightParentLchildRchildweightParentLchildRchild150001229000237000380080001400023000300011000--000--000--000--000--000--000--000456789101112131415567891011121314156、考虑右图：(1)从顶点A出发，求它的深度优先生成树(4分)(2)从顶点E出发，求它的广度优先生成树(4分)(3）(Prim)算法，求它的最小生成树(请画出过程)列)(6答案如下：七编写算法题1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data域中。voidcount1(lklisthead,intx)2、设计递归函数，求一棵二叉树的深度。intdepth(bitreptrroot)3、设计建立有向图正邻接矩阵的函数（数据输入格式自定Typedefstruct{intdata[maxsize][maxsize];intdem,e;}sqgraph;sqgraphcrt(sqgraphg)4、设计函数，将不带表头结点的单链表清除。5、设计递归函数，求一棵非空的二叉树的深度。6、设线性表A=(a1,a2,a3,…,anA7、试编写一个算法，能由大到小遍历一棵二元树。8、假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树?9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a,b,op)op和b算法中允许直接引用函数operate(函数operate不必定义)，如果需要还允许引用栈和队列的基本操作。11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（以申明零时变量、指针。该链表带头节点、头节点和数据节点的结构定义如下typedefstructLNode{ElemTypedata;StructLNode*}List,LNode;函数定义：voidinvert(List&L)12、编写算法计算给定二叉树中叶结点的个数。其中树节点定义如下typedefstructBiTNode{DataTypedata;StructBiTNode*LChild,*RChild;}BiTNode,*BiTree;函数定义：CountLeaf(BiTreeT,int&LeafNum)13已知二叉树结点定义为：structnode{elemtpdata;structnode*lc,*rc;);Typedefstructnode*bitreptr(指向根),*tpointer(指向一般结点);voidpreorder(bitreptrP)//P指向树根节点voidpreorder(bitreptrP){If(P!=0){printf(P->data);preorder(P->lc);preorder(P->rc);}}14、在邻接矩阵存储结构上实现图的基本操作：InsertVex(G,v)//插入顶点StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v{if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;G.vexs[++G.vexnum]=v;returnOK;}//Insert_Vex15、已知某哈希表的装载因子小于1，哈希函数为关键字（标识符）voidPrint_Hash(HashTableH)//按第一个字母顺序输出Hash表中的所有关键字,voidPrint_Hash(HashTableH)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法{for(i=1;i<=26;i++)for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex])if(H(H.elem[j].key)==i)p