数据结构期末习题答案[1]

第一章绪论一，选择1．组成数据的基本单位是（）A．数据项B．数据类型C．数据元素D．数据变量2．数据结构是研究数据的（）以及它们之间的相互关系。A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构3．算法分析的两个主要方面是（）A．正确性和简单性B．可读性和文档性C．数据复杂性和程序复杂性D．时间复杂度和空间复杂度4．算法分析的目的是（）。A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性5.算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B　Ｄ．以上都不是6．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.7.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的8．从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构9．程序段for(i=n-1;i>=1;i--)for(j=1j<=i;j++)if(A[j]>A[j+1])A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A．O（n）B．O(nlogn)C.．O(n3)D．O(n2)10．连续存储时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续二，判断题1．数据结构的抽象操作的定义与具体实现有关。()2．数据结构是数据对象与对象中数据元素之间关系的集合。3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。()4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。5．算法和程序原则上没有区别，在讨论数据结构是两者是通用的。6．同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。7．数据的逻辑结构与数据元素本身的内容和形式无关。8．算法的优劣与算法描述语言无关，但与所用计算机有关。()9．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()10．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()一，选择题 1．C 2．C 3．D 4．C 5．C 6．B 7．D 8．C 9．D 10．A二，判断题 1.× 2.√ 3.× 4.√ 5.× 6.× 7.√ 8.× 9.√ 10.×三，填空1．数据的物理结构包括的示和的表示。2.对于给定的n个元素,可以构造出的逻辑结构有，，，___四种。3．一个数据结构在计算机中称为存储结构。4．抽象数据类型的定义仅取决于它的一组___，而与__无关，即不论其内部结构如何变化，只要它的__不变，都不影响其外部使用。5．线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系。6．一个算法有5个特性:、、，有零个或多个输入、有一个或多个输出。7．已知如下程序段for（i=n；i<=1;i++）{语句1}{x:=x+1；{语句2}for(j=n;j<=i;j++){语句3}y:=y+1;{语句4}}语句1执行的频度为；语句2执行的频度为；语句3执行的频度为；语句4执行的频度为。8．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）for(i＝1;i<=n;i++)for(j＝１;j<=i;j++)for(k＝1;k<=j;j++)ｘ＝ｘ＋delta；9.计算机执行下面的语句时，语句s的执行次数为_______。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;10.下面程序段的时间复杂度为________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;三，填空题1．数据元素数据元素间关系2．集合线性结构树形结构图状结构或网状结构3．表示（又称映像）。4．逻辑特性在计算机内部如何表示和实现数学特性5．一对一　　一对多多对多6．有穷性确定性可行性7．n+1nn(n+3)/2n(n+1)/28．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6O(n3)9.(n+3)(n-2)/210.O(n)四，应用题1．什么是数据?它与信息是什么关系?2．什么是数据结构?数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?3．评价一个好的算法，从哪几方面考虑？4.若将数据结构定义为一个二元组（D，R）,说明符号D，R应分别表示什么？5．解释算法与程序的区别？6．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。（1）A=（K，R），其中：K={a，b，c，d，e，f，g}R={r}r={〈a，b〉，〈b，c〉，〈c，d〉，〈d，e〉，〈e，f〉，〈f，g〉}（2）B=（K，R），其中：K={a，b，c，d，e，f，g，h}R={r}r={〈d，b〉，〈d，g〉，〈d，a〉，〈b，c〉，〈g，e〉，〈g，h〉，〈a，f〉}（3）C=（K，R），其中：K={1，2，3，4，5，6}R={r}r={(1,2)，(2,3)，（2，4），（3，4），（3，5），（3，6），（4，5），（4,6）}这里的圆括号对表示两结点是双向的。7．分析以下程序段的时间复杂度。（1）a=0；b=1；①for（i=2；i〈=n；i++）②{s=a+b；③b=a；④a=S；⑤}（2）inti，j，k；for（i=0；i〈n；i++〉①for（j=0；j〈n；j++〉②{c[i][j]=0；③for（k=0；k〈n；k++〉④c[i][j]=c[i][j]+a[i][k]+b[k][j]；⑤}8．求下列算法段的语句频度及时间复杂度（1）for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;（2）for（i=1;i<=n;i++）for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=i+j-k;四，应用题1．什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。2．数据结构是指数据以及相互之间的关系。记为：数据结构={D,R}。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。有关数据结构的讨论一般涉及以下三方面的内容：（1）数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；（2）数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；（3）施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。3．评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。4．D是数据元素的有限集合，S是D上数据元素之间关系的有限集合。5．算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：有穷性确定性可行性有输入有输出算法与程序的联系和区别：（1）算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。（3）算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。（4）算法与数据结构是相辅相承的：解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。6．（1）A对应逻辑图形如下，它是一种线性结构。（2）B对应逻辑图形如下，它是一种树形结构。（3）C对应逻辑图形如下，它是一种图形结构。7．（1）解：语句①的频度是2；语句②的频度是n；语句③的频度是n-1；语句④的频度是n-1；语句⑤的频度是n-1；故，该程序段的时间复杂度T（n）=2+n+3*（n-1）=4n-1=O（n）。（2）解：语句①的循环控制变量i要增加到n，测试到i=n成立才会终止，故它的频度为n+1；语句②作为语句①循环体内的语句应该执行n次，但语句②本身要执行n+1次，故语句②的频度是n（n+1）；同理可得语句③、④和⑤的频度分别是n2，n2（n+1）和n3。该程序段所有语句的频度之和为：T（n）=2n3+3n2+2n+1其复杂度为O（n3）。8．（1）分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因此，时间频度T(n)=1+2+3+…+n=n*(n+1)/2。有1/4≤T(n)/n2≤1，故它的时间复杂度为Ｏ(n2),即Ｔ(n)与n2数量级相同。（2）分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)。由于有1/6≤T（n)/n3≤1，故时间复杂度为Ｏ(n3)第二章线性表一，选择1．在一个以h为头的单循环链中，p指针指向链尾的条件是（）A.p->next=hB.p->next=NILC.p->next->next=hD.p->data=-12．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7．在带有头结点的单链中插入一个新结点时不可能修改（）。A．头指针B．头结点指针域C．开始结点指针域D．其它结点指针域8．双向链表中有两个指针域，llink和rlink，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）。A.p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;B.q->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink=q->rlink;C.q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;D.p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink=q;9．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL10．在顺序表中查找第i个元素的时间效率最高的算法时间复杂度是（）。A．O(1)B．O()C．O(log2n)D．O(n)11．最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（）。A．O(n)B．O()C．O(log2n)D．O(1)12.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)13.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)14．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。A．O（i）B．O（1）C．O（n）D．O（i-1）15．非空的循环单链表head的尾结点p满足（）。A．p->link=headB．p->link=NILC．p=NILD．p=head一，选择 1.A 2.B 3.C 4.A 5.D 6.D 7.A 8.D 9.B 10.A 11．D 12.C 13.C 14.C 15.A 二，判断1.链表中的头结点仅起到标识的作用。()2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()4．顺序存储方式只能用于存储线性结构。()5．线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。6.线性表的特点是每个元素都有一个前驱和一个后继。()7.取线性表的第i个元素的时间同i的大小有关。()8.循环链表不是线性表。()9.线性表就是顺序存储的表。()10.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()二，判断 1.× 2.√ 3.× 4.× 5.× 6.× 7.× 8.× 9.× 10.×三，填空1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。3．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。4．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。5．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。6.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->next=p；s->prior=________；p->prior=s；________=s；7.顺序存储结构通过________表示元素之间的关系;链式存储结构通过________表示元素之间的关系。8.对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个，单链表为_______个。9.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_______,时间复杂度是。10.带头结点的双循环链表L中只有一个元素结点的条件是：。三，填空1．顺序2．（n-1）/23．n-i+14．O(1)，O(n)5．f->next=p->next;f->prior=p;p->next->prior=f;p->next=f;6．p->priors->prior->next7．物理上相邻指针8．429．u=p->next;p->next=u->next;free(u);O(1);10．L->next->next==L四，算法设计1．试写一算法在带头结点的单链表结构上实现线性表操作LOCATE（L，X）。2．试写一算法在带头结点的单链表结构上实现线性表操作LENGTH（L）。3．试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an,an-1,…,a1）。4．试写一算法，对单链表实现就地逆置。5．设线性表A=（a1，a2，…,an），B=（b1,b2,…,bn），试写一个按下列规则合并A，B为线性表C的算法，即使得C=（a1,b1,…,am,bm,bm+1,…,bn）当m<=n时；或者C=（a1,b1,…,an,bn,an+1,…,an）当m.>n时；线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。1．LNode*Locate(LinkListL,intx)//链表上的元素查找,返回指针{for(p=l->next;p&&p->data!=x;p=p->next);returnp;}//Locate2．intLength(LinkListL)//求链表的长度{for(k=0,p=L;p->next;p=p->next,k++);returnk;}//Length3．voidreverse(SqList&A)//顺序表的就地逆置{for(i=0,j=A.length-1;i<j;i++,j--)A.elem[i]<->A.elem[j];}//reverse4．voidLinkList_reverse(Linklist&L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next;//把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.5．voidmerge1(LinkList&A,LinkList&B,LinkList&C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间{p=A->next;q=B->next;C=A;while(p&&q){s=p->next;p->next=q;//将B的元素插入if(s){t=q->next;q->next=s;//如A非空,将A的元素插入}p=s;q=t;}//while}//merge1第三章栈和队列一，选择1.对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序3.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front4当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top指针。A．top++B．top--C．top=0D．top5.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是()。A.iB.n-iC.n-i+1D.不确定6.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分7.执行完下列语句段后，i值为：（）intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归8.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是()。A．6B.4C.3D.29.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点10.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈11.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改12.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表13.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m14.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)15.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和1一，选择 1.B 3.B 4B 5.D 6.B 7.B 8.C 9.C 10.D 11.D 12.C 13.A 14.D 15.B 二，填空1．_______是限定仅在表尾进行插入或删除操作的线性表。3．中缀表达式3*（x+2）-5所对应的后缀表达式为；后缀表达式“45*32+-”的值为。4.顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。5．向一个循环队列中插入一元素时，需首先移动，然后再向所指位置新插入的元素。6．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_______7．用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为。二，填空1．栈3．3x2+*5-154．data[++top]=x；5．队尾指针写入6．(M+1)MODN(M+1)%N；7．top=0三，应用题1．指出下列程序段的功能(1)voidDemo1(SeqStack*S){inti;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,i<n;i++)Push(S,arr[i]);}//Demo1(2)SeqStackS1,S2,tmp;DataTypex;...//假设栈tmp和S2已做过初始化while(!StackEmpty(&S1)){x=Pop(&S1);Push(&tmp,x);}while(!StackEmpty(&tmp)){x=Pop(&tmp); Push(&S1,x);Push(&S2,x);}(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。四，算法设计题1．回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 1．根据提示，算法可设计为：//以下为顺序栈的存储结构定义#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判断t字符向量是否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量长度for(i=0;i<len/2;i++)//将一半字符入栈Push(&s,t[i]);while(!EmptyStack(&s)){//每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=S[i]) return0;//不等则返回0elsei++;}return1;//比较完毕均相等则返回1}第四章串一，选择1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长3．串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4．若串S=’software’,其子串的数目是（）。A．8B．37C．36D．9一，选择 1.B 2.C 3．B 4.B二，填空1．空格串是指____，其长度等于_____。2．组成串的数据元素只能是________。3．一个字符串中________称为该串的子串。4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。7．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为____，又称P为____。二，填空1．由空格字符（ASCII值32）所组成的字符串空格个数2．字符3．任意个连续的字符组成的子序列4．57．模式匹配模式串第五章数组和广义表一，选择1.已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）2.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d3.稀疏矩阵一般的压缩存储方法有两种,即（）A．二维数组和三维数组B．三元组和散列C．三元组和十字链表D．散列和十字链表4.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]5.对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间　　D．降低运算的时间复杂度6.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-17.A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。A．i（i-1）/2+jB．j（j-1）/2+iC．i（j-i）/2+1D．j（i-1）/2+18.设广义表L=（（a,b,c）），则L的长度和深度分别为（）。A.1和1B.1和3C.1和2D.2和39.数组A[0..4,-1..-3,5..7]中含有元素的个数（）。A．55B．45C．36D．1610.下面说法不正确的是()。A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构一，选择 1.D 2.D 3.C 4.B 5.C 6.B 7.B 8.C 9.B 10.A二，判断1．一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（）2.从逻辑结构上看，n维数组的每个元素均属于n个向量。（）3.稀疏矩阵压缩存储后，必会失去随机存取功能。（）4.对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）5.数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。（）6.所谓取广义表的表尾就是返回广义表中最后一个元素。（）7.二维以上的数组其实是一种特殊的广义表。（）8.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）9.若一个广义表的表头为空表，则此广义表亦为空表。（）10.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（）二，判断 1.× 2.√ 3.√ 4.√ 5.× 6.× 7.√ 8.× 9.× 10.×四应用题1.画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。2.设某表H如下： A B C X a1 a2 b1 c1 c2 其中A,B,C为子表名，a1,a2,b1,c1,c2,x为其元素。试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H)函数从H中取出单元素a2的运算；（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x）HEAD(TAIL(HEAD(H)))=a2五，算法设计1．设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面2.设二维数组a[1..m,1..n]含有m*n个整数。判断a中所有元素是否互不相同?输出相关信息(yes/no)。1.本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到i=j为止。voidArrange(intA[],intn)//n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面{inti=0,j=n-1,x;//用类C编写，数组下标从0开始while(i<j){while(i<j&&A[i]>0)i++;while(i<j&&A[j]<0)j--;if(i<j){x=A[i];A[i++]=A[j];A[j--]=x;}//交换A[i]与A[j]}}//算法Arrange结束.[算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1).2.判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。intJudgEqual(inga[m][n],intm,n)//判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。{for(i=0;i<m;i++)for(j=0;j<n-1;j++){for(p=j+1;p<n;p++)//和同行其它元素比较if(a[i][j]==a[i][p]){printf(“no”);return(0);}//只要有一个相同的，就结论不是互不相同for(k=i+1;k<m;k++)//和第i+1行及以后元素比较for(p=0;p<n;p++)if(a[i][j]==a[k][p]){printf(“no”);return(0);}}//for(j=0;j<n-1;j++)printf(yes”);return(1);//元素互不相同}//算法JudgEqual结束第6章树和二叉树一选择1．算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++2.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④3．具有10个叶结点的二叉树中有（）个度为2的结点，4A．8B．9C．10D．ll4.有n个叶子的哈夫曼树的结点总数为（）。A．不确定B．2nC．2n+1D．2n-15．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定6．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A．acbedB．decabC．deabcD．cedba7．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同　　B．完全相同C．先序和中序相同，而与后序不同　D．中序和后序相同，而与先序不同8．n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n9．深度为k的二叉树，结点数最多有（）A．2kB．2k-1C．2k-1D．2k-1-110．判断线索二叉树中某结点p有左孩子的条件是（）A．p!=NULLB．p->lchild!=NULLC．p->ltag=0D．p->ltag=1二基础知识题1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2．使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。（1）顺序表示 0 1 2 3 4 5 6 7 8 9 ① ② ③ ④ ⑤ ⑥ ⑦ 10 11 12 13 14 15 16 17 ⑧ ⑨（2）二叉链表表示试画出3个结点的二叉树的所有不同形态。4.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001第七章图一，选择1．图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．03．一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6.求解最短路径的Floyd算法的时间复杂度为()。A．O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）7．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V78.在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)9．有n个结点的有向完全图的边数是（）A．n2B．2nC．n（n-1）D．2n（n+1）10．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网11．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。A．B．C．D．+12．对图做宽度优先遍历时会使用何种数据结构(　　)A．队列B．树　　　C．栈D．集合13．无向图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,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b14．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成15．下面哪一方法可以判断出一个有向图是否有环（）：A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径一，选择 1.A 2.B 3.A 4.B 5.D 6.D 7.A 8．B 9.C 10.B 11.B 12.A 13.D 14．B 15.B 二，判断1.树中的结点和图中的顶点就是指数据结构中的数据元素。（Y）2．一个图G有n个顶点，n-1条边，则该图可以看成是G的一棵生成树。(N)3．如果AOE网中某一个关键活动延迟一天，则整个工程将延期一天。反之，如果缩短该关键活动的持续时间，则一定可使整个工程提前完工。(N)4.有e条边的无向图，在邻接表中有e个结点。（N）5.有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（N）6．强连通图的各顶点间均可达。（Y）7．强连通分量是无向图的极大强连通子图。（N）8．连通分量指的是有向图中的极大连通子图。（N）9．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（N）10.在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（Y）四，应用题1．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。2．给出右图的邻接矩阵、领接表表示。3．对下图所示的连通图，请分别用普里姆（Prim）和克鲁斯卡尔（Kruskal）算法构造其最小生成树。4．已知某图的邻接表为（1）．写出此邻接表对应的邻接矩阵；（2）．写出由v1开始的深度优先遍历的序列；时间复杂度是多少？（4）．写出由v1开始的广度优先遍历的序列；时间复杂度是多少？（2）V1V2V5V3V4V6(4)V1V2V3V4V5V65．画出下图所示的AOV网的所有拓扑有序序列。共有8种：ADBECFADBEFCADEBCFADEBFCDABECFDABEFCDAEBCFDAEBFC6．对图所示的有向图，试利用Dijkstra算法求出从源点1到其他各顶点的最短路径，从顶点1到其他各顶点的最短路径及距离如下：1→3（15）1→3→2（19）1→3→6→4（29）1→3→2→5（29）1→3→6（25）第九章查　找一，选择1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()A．（N+1）/2B．N/2C．ND．[（1+N）*N]/22.对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序3.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率4.具有12个关键字的有序表，折半查找的平均查找长度（）A.3.1B.4C.2.5D.55.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。A．1B.2C.3D.47.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A．k-1次B.k次C.k+1次D.k（k+1）/2次8.既希望较快的查找又便于线性表动态变化的查找方法是()A．顺序查找B.折半查找C.索引顺序查找D.哈希法查找9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()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)10.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR 1.A 2.B 3.D 4.A 5.D 7.D 8.C 9.C 10.C二，判断1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（　）2．在散列检索中，“比较”操作一般也是不可避免的。（　）3.平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（　）4.二叉排序树删除一个结点后，仍是二叉排序树。（　）5．Hash表的平均查找长度与处理冲突的方法无关。（　）6.设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。（　）7.散列法的平均检索长度不随表中结点数目的增加而增加，而随负载因子的增大而增大。（　）8.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二叉排序树相同。（　）9.若散列表的负载因子α<1，则可避免碰撞的产生。（　）10.顺序查找法适用于存储结构为顺序或链接存储的线性表。（　）二，判断 1.√ 2.√ 3.× 4.√ 5.× 6.× 7.√ 8.× 9.× 10.√ 三，填空1.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为____次；当使用监视哨时，若查找失败，则比较关键字的次数为____。2．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。3.在哈希函数H（key）=key%p中，p值最好取__________。5.平衡因子的定义是__________6.处理哈希冲突的方法有__　__、___、__　_和__　__。7.__________法构造的哈希函数肯定不会发生冲突。三，填空1．nn+12．6,9,11,123．小于等于表长的最大素数或不包含小于20的质因子的合数5．结点的左子树的高度减去结点的右子树的高度6．开放定址方法；链地址方法；再哈希；建立公共溢出区7．直接定址法四，应用题1.已知散列表的地址空间为A[0..11]，散列函数H（k）=kmod11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。2．设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。1． 散列地址 0 1 2 3 4 5 6 7 8 9 10 11 关键字 231 89 79 25 47 16 38 82 51 39 151 比较次数 1 1 1 1 2 1 2 3 2 4 3 ASLsucc=21/112．第十章内部排序一，选择1.基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（）。A.O(nlogn)B.O(logn)C.O(n)D.O(n*n)2．下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序3．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。A．直接插入B．直接选择C．堆D．快速4．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序5.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。6．在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫()A．插入排序B．枚举排序C．选择排序D．交换排序7．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A．堆排序〈　快速排序〈归并排序B．堆排序〈　归并排序〈快速排序C．堆排序〉归并排序〉快速排序D．堆排序>快速排序>归并排序8．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A．直接插入排序B.气泡排序C.快速排序D.直接选择排序9．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是()A．NB．2N-1C．2ND．N-110．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。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)11.在下面的排序方法中，辅助空间为O（n）的是()。A．希尔排序B.堆排序C.选择排序D.归并排序12．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。A．冒泡B.希尔C.快速D.堆13.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（）。A.直接插入排序B.快速排序C.直接选择排序D.堆排序14.以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.D.(100,85,40,77,80,60,66,98,82,10,20)15．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序 1.A 2.D 3.A 4.C 5.C 6.B 7.A 8.D 9.A 10.C 11.D 12.C 13.B 14.D 15.D 二，判断1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（）2．内排序要求数据一定要以顺序方式存储。（）3．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）4．直接选择排序算法在最好情况下的时间复杂度为O（N）。（）5．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）6．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。（）7．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（）8．堆肯定是一棵平衡二叉树。（）9．堆是满二叉树。（）10．（101，88，46，70，34，39，45，58，66，10）是堆。（） 1.√ 2.× 3.× 4.× 5.× 6.× 7.× 8.× 9.× 10.√ 三，应用题1.对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。2.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：(1)归并排序每归并一次写一个次序。(2)快速排序每划分一次书写一个次序。(3)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。1.125，11，22，34，15，44，76，66，100，8，14，20，2，5，1设D=71，11，8，14，15，2，5，66，100，22，34，20，44，76，125D=31，11，2，5，15，8，14，34，20，22，66，100，44，76，125D=11，2，5，8，11，14，15，20，22，34，44，66，76，100，1252.(1)2路归并第一趟:18,29,25,47,12,58,10,51；第二趟:18,25,29,47,10,12,51,58；第三趟:10,12,18,25,29,47,51,58(2)快速排序第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,88；第三趟:10,12,18,25,29,47,51,88(3)堆排序建大堆:58,47,51,29,18,12,25,10；①51,47,25,29,18,12,10,58；②47,29,25,10,18,12,51,58；③29,18,25,10,12,47,51,58；④25,18,12,10,29,47,51,58；⑤18,10,12,25,29,47,51,58；⑥12,10,18,25,29,47,51,58；⑦10,12,18,25,29,47,51,58四，算法设计1，试以单链表为存储结构实现简单选择排序的算法。voidLinkedList_Select_Sort(LinkedList&L)//单链表上的简单选择排序算法{for(p=L;p->next->next;p=p->next){q=p->next;x=q->data;for(r=q,s=q;r->next;r=r->next)//在q后面寻找元素值最小的结点if(r->next->data<x){x=r->next->data;s=r;}if(s!=q)//找到了值比q->data更小的最小结点s->next{p->next=s->next;s->next=q;t=q->next;q->next=p->next->next;p->next->next=t;}//交换q和s->next两个结点}//for}//LinkedList_Select_Sort第三章栈和队列一，选择1.对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序3.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front4当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top指针。A．top++B．top--C．top=0D．top5.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是()。A.iB.n-iC.n-i+1D.不确定6.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分7.执行完下列语句段后，i值为：（）intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归8.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是()。A．6B.4C.3D.29.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点10.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈11.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改12.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表13.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m14.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)15.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和1一，选择 1.B 3.B 4B 5.D 6.B 7.B 8.C 9.C 10.D 11.D 12.C 13.A 14.D 15.B 二，填空1．_______是限定仅在表尾进行插入或删除操作的线性表。3．中缀表达式3*（x+2）-5所对应的后缀表达式为；后缀表达式“45*32+-”的值为。4.顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。5．向一个循环队列中插入一元素时，需首先移动，然后再向所指位置新插入的元素。6．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_______7．用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为。二，填空1．栈3．3x2+*5-154．data[++top]=x；5．队尾指针写入6．(M+1)MODN(M+1)%N；7．top=0三，应用题1．指出下列程序段的功能(1)voidDemo1(SeqStack*S){inti;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,i<n;i++)Push(S,arr[i]);}//Demo1(2)SeqStackS1,S2,tmp;DataTypex;...//假设栈tmp和S2已做过初始化while(!StackEmpty(&S1)){x=Pop(&S1);Push(&tmp,x);}while(!StackEmpty(&tmp)){x=Pop(&tmp); Push(&S1,x);Push(&S2,x);}(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。四，算法设计题1．回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 1．根据提示，算法可设计为：//以下为顺序栈的存储结构定义#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判断t字符向量是否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量长度for(i=0;i<len/2;i++)//将一半字符入栈Push(&s,t[i]);while(!EmptyStack(&s)){//每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=S[i]) return0;//不等则返回0elsei++;}return1;//比较完毕均相等则返回1}2．双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：//双向栈的栈结构类型与以前定义略有不同#defineStackSize100//假定分配了100个元素的向量空间#definecharDataTypetypedefstruct{DataTypeData[StackSize]inttop0;//需设两个指针inttop1;}DblStackvoidInitStack(DblStack*S){//初始化双向栈S->top0=-1;S->top1=StackSize;//top2也指出了向量空间，但由于是作为栈底，因此不会出错}intEmptyStack(DblStack*S,inti){//判栈空(栈号i)return(i==0&&S->top0==-1||i==1&&S->top1==StackSize);}intFullStack(DblStack*S){//判栈满,满时两头相遇return(S->top0==S-top1-1);}voidPush(DblStack*S,inti,DataTypex){//进栈(栈号i)if(FullStack(S))Error("Stackoverflow");//上溢、退出运行if(i==0)S->Data[++S->top0]=x;//栈0入栈if(i==1)S->Data[--S->top1]=x;//栈1入栈}DataTypePop(DblStack*S,inti){//出栈(栈号i)if(EmptyStack(S,i))Error("Stackunderflow");//下溢退出if(i==0)return(S->Data[S->top0--]);//返回栈顶元素，指针值减1if(i==1)return(S->Data[S->top1++]);//因这个栈以另一端为底，所以指针值加1。}第四章串一，选择1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长3．串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4．若串S=’software’,其子串的数目是（）。A．8B．37C．36D．9一，选择 1.B 2.C 3．B 4.B二，填空1．空格串是指____，其长度等于_____。2．组成串的数据元素只能是________。3．一个字符串中________称为该串的子串。4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。6．模式串P=‘abaabcac’的next函数值序列为________。7．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为____，又称P为____。二，填空1．由空格字符（ASCII值32）所组成的字符串空格个数2．字符3．任意个连续的字符组成的子序列4．55.O(m+n)6．011223127．模式匹配模式串第九章查　找一，选择1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()A．（N+1）/2B．N/2C．ND．[（1+N）*N]/22.对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序3.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率4.具有12个关键字的有序表，折半查找的平均查找长度（）A.3.1B.4C.2.5D.55.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。A．1B.2C.3D.47.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A．k-1次B.k次C.k+1次D.k（k+1）/2次8.既希望较快的查找又便于线性表动态变化的查找方法是()A．顺序查找B.折半查找C.索引顺序查找D.哈希法查找9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()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)10.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR 1.A 2.B 3.D 4.A 5.D 7.D 8.C 9.C 10.C二，判断1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（　）2．在散列检索中，“比较”操作一般也是不可避免的。（　）3.平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（　）4.二叉排序树删除一个结点后，仍是二叉排序树。（　）5．Hash表的平均查找长度与处理冲突的方法无关。（　）6.设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。（　）7.散列法的平均检索长度不随表中结点数目的增加而增加，而随负载因子的增大而增大。（　）8.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二叉排序树相同。（　）9.若散列表的负载因子α<1，则可避免碰撞的产生。（　）10.顺序查找法适用于存储结构为顺序或链接存储的线性表。（　）二，判断 1.√ 2.√ 3.× 4.√ 5.× 6.× 7.√ 8.× 9.× 10.√ 三，填空1.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为____次；当使用监视哨时，若查找失败，则比较关键字的次数为____。2．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。3.在哈希函数H（key）=key%p中，p值最好取__________。5.平衡因子的定义是__________6.处理哈希冲突的方法有__　__、___、__　_和__　__。7.__________法构造的哈希函数肯定不会发生冲突。三，填空1．nn+12．6,9,11,123．小于等于表长的最大素数或不包含小于20的质因子的合数5．结点的左子树的高度减去结点的右子树的高度6．开放定址方法；链地址方法；再哈希；建立公共溢出区7．直接定址法四，应用题1.已知散列表的地址空间为A[0..11]，散列函数H（k）=kmod11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。2．设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。1． 散列地址 0 1 2 3 4 5 6 7 8 9 10 11 关键字 231 89 79 25 47 16 38 82 51 39 151 比较次数 1 1 1 1 2 1 2 3 2 4 3 ASLsucc=21/112．第十章内部排序一，选择1.基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（）。A.O(nlogn)B.O(logn)C.O(n)D.O(n*n)2．下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序3．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。A．直接插入B．直接选择C．堆D．快速4．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序5.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。6．在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫()A．插入排序B．枚举排序C．选择排序D．交换排序7．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A．堆排序〈　快速排序〈归并排序B．堆排序〈　归并排序〈快速排序C．堆排序〉归并排序〉快速排序D．堆排序>快速排序>归并排序8．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A．直接插入排序B.气泡排序C.快速排序D.直接选择排序9．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是()A．NB．2N-1C．2ND．N-110．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。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)11.在下面的排序方法中，辅助空间为O（n）的是()。A．希尔排序B.堆排序C.选择排序D.归并排序12．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。A．冒泡B.希尔C.快速D.堆13.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（）。A.直接插入排序B.快速排序C.直接选择排序D.堆排序14.以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.D.(100,85,40,77,80,60,66,98,82,10,20)15．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序 1.A 2.D 3.A 4.C 5.C 6.B 7.A 8.D 9.A 10.C 11.D 12.C 13.B 14.D 15.D 二，判断1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（）2．内排序要求数据一定要以顺序方式存储。（）3．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）4．直接选择排序算法在最好情况下的时间复杂度为O（N）。（）5．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）6．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。（）7．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（）8．堆肯定是一棵平衡二叉树。（）9．堆是满二叉树。（）10．（101，88，46，70，34，39，45，58，66，10）是堆。（） 1.√ 2.× 3.× 4.× 5.× 6.× 7.× 8.× 9.× 10.√ 三，应用题1.对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。2.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：(1)归并排序每归并一次书写一个次序。(2)快速排序每划分一次书写一个次序。(3)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。1.125，11，22，34，15，44，76，66，100，8，14，20，2，5，1设D=71，11，8，14，15，2，5，66，100，22，34，20，44，76，125D=31，11，2，5，15，8，14，34，20，22，66，100，44，76，125D=11，2，5，8，11，14，15，20，22，34，44，66，76，100，1252.(1)2路归并第一趟:18,29,25,47,12,58,10,51；第二趟:18,25,29,47,10,12,51,58；第三趟:10,12,18,25,29,47,51,58(2)快速排序第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,88；第三趟:10,12,18,25,29,47,51,88(3)堆排序建大堆:58,47,51,29,18,12,25,10；①51,47,25,29,18,12,10,58；②47,29,25,10,18,12,51,58；③29,18,25,10,12,47,51,58；④25,18,12,10,29,47,51,58；⑤18,10,12,25,29,47,51,58；⑥12,10,18,25,29,47,51,58；⑦10,12,18,25,29,47,51,58四，算法设计1，试以单链表为存储结构实现简单选择排序的算法。35_1496314947.unknown_1496314948.unknown