《计算机软件技术基础》课后题答案.doc 102页

'数据结构习题答案第一节概论一、选择题1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着()。A．数据元素具有同一的特点*B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等2．数据结构是一门研究非数值计算的程序设计问题中计算机的((1))以及它们之间的((2))和运算的学科。(1)A．操作对象B．计算方法*C．物理存储D．数据映像(2)A．结构*B．关系C．运算D．算法3．数据结构被形式地定义为(D，R)，其中D是((1))的有限集合，R是D上((2))的有限集合。(1)A．算法*B．数据元素C．数据操作D．逻辑结构(2)A．操作B．映像C．存储*D．关系4．在数据结构中，从逻辑上可以把数据结构分为()。A．动态结构和静态结构B．紧凑结构和非紧凑结构*C．线性结构和非线性结构D．内部结构和外部结构5．线性表的顺序存储结构是一种()的存储结构。*A．随机存取B．顺序存取C．索引存取102 D．Hash存取6．算法分析的目的是()。A．找出数据结构的合理性B．研究算法中的输入和输出的关系*C．分析算法的效率以求改进D．分析算法的易懂性和文档性7．计算机算法指的是((1))，它必须具备输入、输出和((2))等五个特征。(1)A．计算方法B．排序方法*C．解决某一问题的有限运算序列D．调度方法(2)A．可行性、可移植性和可扩充性*B．可行性、确定性和有穷性C．确定性，有穷性和稳定性D．易读性、稳定性和安全性8．线性表若采用链表存储结构，要求内存中可用存储单元的地址()。A．必须是连续的B．部分必须是连续的C．一定是不连续的*D．连续不连续都可以9．在以下的叙述中，正确的是()。A．线性表的线性存储结构优于链式存储结构*B．二维数组是它的每个数据元素为一个线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是()。102 *A．集合中任何两个结点之间都有逻辑关系但组织形式松散B．线性结构中结点按逻辑关系依次排列形成一条“锁链”C．树形结构具有分支、层次特性，其形态有点像自然界中的树D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11．以下说法正确的是()。A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合*D．数据结构是带有结构的数据元素的集合二、判断题╳1．数据元素是数据的最小单位。√2．数据结构是带有结构的数据元素的集合。√3．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。╳4．数据项是数据的基本单位。√5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。√6．数据的物理结构是数据在计算机中实际的存储形式。╳7．算法和程序没有区别，所以在数据结构中二者是通用的。√8．顺序存储结构属于静态结构，链式存储结构属于动态结构。102 三、填空题1．所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____。2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___。3．数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型。4．在线性结构中，开始结点__没有_前驱结点，其余每个结点有且只有__一个_个前驱结点。5．在树形结构中，根结点只有___一个___，其余每个结点有且只有___一个___前驱结点；叶结点没有___后继__结点，其余每个结点的后继结点可以有__任意个__·6．在图形结构中，每个结点的前驱结点和后继结点可以有___任意个___。7．算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出__。8．下列程序段的时间复杂度是__O（n）___。for(i=1；i<=n；i++)A[i，i]=0；9．下列程序段的时间复杂度是__O（n2）___。S=0；for(i=1；i<=n；i++)102 for(j=1；j<=n；j++)s=s+B[i,j]；sum=s；10．存储结构是逻辑结构的___物理__实现。11．从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即__数据__、__数据元素_和__数据项___。12．根据需要，数据元素又被称为__结点__、__记录__、___元素__或__顶点_。13．通常，存储结点之间可以有___顺序存储__、____链式存储__、____索引存储__、___散列存储_四种关联方式，称为四种基本存储方式。14．通常从___确定性___、__可读性_、___健壮性__、_高效性__等几方面评价算法(包括程序)的质量。15．一个算法的时空性能是指该算法的_时间复杂度___和___空间复杂度_，前者是算法包含的__计算量__，后者是算法需要的___存储量__。16．在一般情况下，一个算法的时间复杂度是__问题规模__的函数。17．常见时间复杂度的量级有：常数阶O(__1_)、对数阶O(__log2n___)、线性阶O(__n__)、平方阶O(_n2_)和指数阶O(__2n_)。通常认为，具有指数阶量级的算法是__不可行__的。18．数据结构的基本任务是数据结构的__设计__和__实现__。102 19．数据对象是性质相同的__数据元素_的集合。20．抽象数据类型是指一个__数学模型__以及定义在该模型上的一组操作。四、应用题1．分析下列程序段的时间复杂度。……i=1；WHILE(i<=n)i=i*2；……答：O(log2n)2．叙述算法的定义及其重要特性。答：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。3．简述下列术语：数据，数据元素，数据结构，数据对象。答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。102 4．逻辑结构与存储结构是什么关系？答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。5．将数量级210，n，n2，n3，nlog2n，log2n，2n，n!，(2／3)n，n2／3按增长率进行排列。答：(2／3)n，210，log2n，n2／3，n，nlog2n，n2，n3，2n，n!6．设有数据逻辑结构为：D={k1，k2，k3，…，k9}，R={，，，，，，，，，}，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？答：图略。开始结点k1、k2，终端结点k6、k7。7．设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。答：数据逻辑结构为：D={k1，k2，k3，…102 ，k8}，R={，，，，，，}，其逻辑结构类型为树型结构。8．分析下列程序的时间复杂度(设n为正整数)。(1)intrec(intn){if(n==1)return(1)；elsereturn(n*rec(n-1))；}(2)x=91；y=100；While(y>0)if(x>10)y--；(3)i=1；j=0；while(i+j<=n)if(i>j)j++；elsei++;(4)x=n；y=0；while(x>=(y+1)*(y+1))y++；答：(1)O(n)(2)O(1)(3)O(n)(4)O(n1/2)9．设n为正数。试确定下列各程序段中前面加记号@的语句的频度：(1)i=1；k=0；while(i<=n-1){@k+=10*i；i++；)(2)k=0；for(i=1；i<=n；i++)for(j=i；j<=n：j++)@k++；答：(1)n-1(2)n+(n-1)+……+1=n(n+1)/2第二节线性表102 一、选择题1．线性结构中的一个结点代表一个()。*A．数据元素B．数据项C．数据D．数据结构2．线性表L=(a1，a2，…，ai，…，an)，下列说法正确的是()。A．每个元素都有一个直接前驱和直接后继B．线性表中至少要有一个元素C．表中诸元素的排列顺序必须是由小到大或由大到小的D．*除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继3．顺序表是线性表的()。A．链式存储结构*B．顺序存储结构C．索引存储结构D．散列存储结构4．对于顺序表，以下说法错误的是()。*A．顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B．顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C．顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻D．顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中5．对顺序表上的插入、删除算法的时间复杂度分析来说，通常以()为标准操作。A．条件判断*B．结点移动C．算术表达式102 D．赋值语句6．对于顺序表的优缺点，以下说法错误的是()。A．无需为表示结点间的逻辑关系而增加额外的存储空间B．可以方便地随机存取表中的任一结点*C．插入和删除操作较方便D．由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)7．在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为()。A．n*B．n/2C．(n-1)/2D．(n+1)/28．在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为()。A．nB．n/2*C．(n-1)/2D．(n+1)/29．带头结点的单链表为空的条件是()。A．head=NULL*B．head->next=NULLC．head->next=headD．head!=NULL10．非空单循环链表head的尾结点*p满足()。A．p->next=NULLB．p=NULL*C．p->next=headD．p=head11．在双循环链表的*p结点之后插入*s结点的操作是()。A．p->next=s；s->prior=p；p->next->prior=s；s->next=p->next；B．p->next=s；p->next->prior=s；s->prior=p：s->next=p->next；102 C．s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；*D．s->prior=p；s->next=p->next；p->next->pror=s；p->next=s；12.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行()。A．s->next=p->next；p->next=s；B．p->next=s->next；s->next=p；*C．q->next=s;s->next=p；D．p->next=s;s->next=q；13.在一个单链表中，若*p结点不是最后结点。在*p之后插入结点*s，则执行()。A．s->next=p；p->next=s;*B．s->next=p->next；p->next=s；C．s->next=p->next；p=s；D．p->next=s；s->next=p;14.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用()存储方式最节省时间。*A．顺序表B.单链表C．双链表D．单循环链表15．设rear是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为()。A．p=rear；rear=rear->next；free(p)B．rear=rear->next；free(rear)；C．rear=rear->next->next；free(rear)；102 *D．p=rear->next->next；rear->next->next=p->next；free(p)；16．在一个单链表中，若删除*p结点的后继结点，则执行()。*A．q=p->next；p->next=q->next；free(q)；B．p=p->next；p->next=p->next->next；free(p)；C．p->next=p->next；free(p->next)；D．p=p->next->next；free(p->next)；17．设指针p指向双链表的某一结点，则双链表结构的对称性可用()式来刻画。A．p->prior->next->==p->next->nextB．p->prior->prior==p->next->prior*C．p->prior->next->==p->next->priorD．p->next->next==p->prior->prior18．在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是()。A．rear和rear->next->next*B．rear->next和rearC．rear->next->next和rearD．rear和rear->next19．循环链表的主要优点是()。A．不再需要头指针了B．已知某个结点的位置后，容易找到它的直接前驱C．在进行插入、删除操作时，能更好地保证链表不断开*D．从表中任一结点出发都能扫描到整个链表102 20．在线性表的下列存储结构中，读取元素花费时间最少的是()。A．单链表B．双链表C．循环链表*D．顺序表二、判断题√1．顺序存储的线性表可以随机存取。╳2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。√3．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。╳4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。√5．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。√6．在单链表中，可以从头结点开始查找任何一个元素。╳7．线性表的链式存储结构优于顺序存储结构。√8．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。╳9．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。╳10．顺序存储方式只能用于存储线性结构。三、填空题102 1．为了便于讨论，有时将含n(n>0)个结点的线性结构表示成(a1，a2，…，an)，其中每个ai代表一个__结点_。a1称为_第一个_结点，an称为__最后一个_结点，i称为ai在线性表中的_位置__。对任意一对相邻结点ai、ai+1(1≤inext；p->next=q->next；free(q)；___·6．非空的单循环链表head的尾结点(由指针p所指)满足__p->next=head_____。7．rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为__p=rear->next；q=p->next；p->next=q->next；free(q)；____。8．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为__O(1)__，在给定值为x的结点后插入新结点的时间复杂度为__O(n)__。102 9．单链表表示法的基本思想是用___指针___表示结点间的逻辑关系。10．在顺序表中插入或删除一个元素，平均需要移动_一半_元素，具体移动的元素个数与__元素的位置_有关。11．在一个长度为n的向量的第i(1≤i≤n+1)个元素之前插入一个元素时，需向后移动___n-i+1__个元素。12．在一个长度为n的向量中删除第i(1≤i≤n)个元素时，需向前移动__n-i__个元素。13．在双链表中，每个结点有两个指针域，一个指向___前驱__，另一个指向___后继___。14．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=__p->next->next；___。15．设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成__单循环链表___。16．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是_删除__s指向的结点。17．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___s->next=r->next__；r->next=s；r=s；102 18．在单链表中，指针p所指结点为最后一个结点的条件是__p->next=NULL___。19．在双循环链表中，若要在指p所指结点前插入s所指的结点，则需执行下列语句：s->next=p；s->prior=p->prior；__p->prior->next__=s；p->prior=s；20．在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作：s->next=___p->next__；p->next=s；temp=p->data；p->data=__s->data___；s->data=__temp_；四、应用题1．描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。2．何时选用顺序表，何时选用链表作为线性表的存储结构为宜？102 答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。3．在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？答：平均移动表中大约一半的结点，插入操作平均移动n/2个结点，删除操作平均移动（n-1）/2个结点。具体移动的次数取决于表长和插入、删除的结点的位置。4．为什么在单循环链表中设置尾指针比设置头指针更好？答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O(1)时间内完成，同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？答：能删除。双链表上删除p所指向的结点的时间复杂度为O(1)，单循环链表上删除p所指向的结点的时间复杂度为O(n)。102 6．下列算法的功能是什么？LinkList*testl(LinkList*L){//L是无头结点的单链表LinkList*q，*p；if(L&&L->next){q=L；L=L->next；p=L;while(p->next)p=p->next；p->next=q;q->next=NULL；}returnL；}答：如果长度大于1，则将首元结点删除并插入到表尾。7．如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。五、算法设计题102 假设算法中用到的顺序表和链表结构如下：#definemaxsize100;Typedefstructnode1{datatypedata[maxsize];intlength}SeqList;Typedefstructnode2{datatypedata;structnode2*next}LinkedList;1．试用顺序表作为存储结构，实现将线性表(a0，a1，a2，…an-1)就地逆置的操作，所谓“就地”是指辅助空间为O(1)。答：(1)顺序表的就地逆置分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。voidSeqreverse(SeqList*L){／／顺序表的就地逆置for(i=0；j=L->length-1；idata[i];L->data[i]=L.data[j];L->data[j]=t;}}(2)链表的就地逆置分析：本算法的思想是逐个地把L的当前元素r插入到新的链表头部。voidLinkedreverse(LinkedList*L){／／链表的就地逆置p=L->next；L->next=NULL；102 while(p!=NULL){r=p，p=p->next；／／r指向当前待逆置的结点，p记下下—个结点r->next=L—>next；L->next=r；／／放到表头}}2．设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个有序表。答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将x插入到其位置上，同时顺序表长度增1。voidSeqListinsert(SeqList*L，intx){／／x插入到递增有序的顺序表L中i=0;while((i<=L->length-1)&&(x>=L->data[i]))i++；／／找正确的插入位置for(k=L->length-1;k>=i；k--)／／元素从后往前依次后移L->data[k+1]=L->data[k]；L->data[i]=x；／／x插入到正确位置L->length++；)3.设单链表L是一个递减有序表，试写一个算法将x插入其中后仍保持L的有序性。102 答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。voidLinkListinsert(LinkedList*L，intx){／／x插入有序链表L中q=L；p=q—>next；while(p!=NULL&&p—>data>x)／／找到插入的位置{q=p；p=p—>next；}s=(LinkedList*)malloc(sizeof(LinkedList))；／／生成新结点S—>data=x；S—>next=p；q—>next=s；}4.试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。voidLinkedListlnsert(LinkedList*L，intx，inti){／／不带头结点的单链表的第i个元素之前插入一个元素p=L：j=1;while(p!=NULL&&jnext；j++；}if(i<=0||p==NULL)printf(”插入位置不正确＼n”)；102 else{q=(LinkedList*)malloc(sizeof(LinkedList))；q—>data=x；if(i==1){q—>next=L；L=q；}／／在第一个元素之前插入else{q—>next=p—>next；p—>next=q；}／／在其他位置插入}}5．设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。SeqList*Seqmerge(SeqListA，SeqListB，SeqList*C){／／有序顺序表A和B归并成有序顺序表Ci=0；j=0；k=0；／／i，i，k分别为顺序表A，B，C的下标while(idata[k]=A.data[il；i++；]102 else{C->data[k]=B.data[j];j++；}／／B中当前元素较小k++；}if(i==m)for(t=j；tdata[k]=B.data[t];k++；}／／B表长度大于A表elsefor(t=i；tdata[k]=A.data[t]；k++；}／／A表长度大于B表C->length=m+n；returnC;}(2)VOidLinkmerge(LinkedList*A，LinkedList*B，LinkedList*C){／／有序链表A和B归并成有序链表Cpa=A—>next；pb=B—>next；C=A；pc=C；while(pa&&pb)／／A和B都不为空时{if(pa—>datadata)／／A当前结点值较小{qa=pa->next；pC->next=pa；pc=pc->next；pa=qa；}else{qb=pb->next；pc->next=pb：pc=pc->next；pb=qb；}／／B当前结点值较小}if(pa)pc—>next=pa；102 ／／A没有结束，将A表剩余元素链接到C表if(pb)pc—>next=pb；／／B没有结束，将B表剩余元素链接到C表free(B)；／／释放B表的头结点}本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。答：分析：先在la中找到第i个结点，分别用两个指针pre和p指向第i-1和第i个结点，然后用指针q从第i个结点起向后走len个元素，使q指向此位置。然后在lb中找到第j个结点，将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。voidDeletelnsert(LinkedList*la，LinkedList*lb，inti，intj,intlen){／／删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表lb中第j个结点之前if(i<0||j<0||len<0)exit(0)；p=la；k=1；pre=NULL；102 while(p&&knext;k++；}if(!p)exit(0)；q=p；k=l；／／p指向la表中第i个结点while(q&&knext；k++；}／／查找la表中第i+len-1个结点if(!q)exit(0)；if(pre==la)la=q—>next；／／i=1的情况elsepre—>next=q—>next；／／完成删除／／将从la中删除的结点插入到lb中if(j==1){q->next=lb；lb=p；}／／j=1时else{r=lb;k=1；／／j>1时while(r&&knext；k++；}／／查找Lb表中第i—1个元素if(!r)exit(0)；q—>next=r—>next；r—>next=p；／／完成插入}}7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。答：LinkedListdelete(LinkedList*L，int102 min，intmax){／／删除递减有序单链表L中值大于min且小于max的结点q=L；if(min>max){printf(”min>max＼n”)；exit(0)；}elsep=L—>next；／／q始终指向p的前驱while(p—>data>=max)／／当前元素大于或等于max，则p、q依次向后移动{q=p；p=p—>next；}while((p!=NULL)&&(p一>data>min)){／／当前元素的值比min大同时比max小，删除p指向的结点q—>next=p—>next，free(p)；p=q—>next；}returnL；}．8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。答：分析：用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。102 voiddecompose(LinkedList*A，LinkedList*B){／／单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表Bp=A->next；B=(LinkedList*)malloc(sizeof(LinkedList))；r=B；while(p!=NULL&&p->next!=NULL){q=p—>next；／／q指向偶数序号的结点p—>next=q—>next；／／将q从A表中删除r—>next=q；／／将q结点链接到B链表的末尾r=q；／／r总是指向B链表的最后—·个结点p=p—>next；／／p指向原链表A中的奇数序号的结点}r—>next=NULL；／／将生成B链表中的最后一个结点的next域置为空}9．假设以两个元素值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C，其元素为两集合的交集，且表C中的元素值也递增有序排列。用顺序表实现并写出C的算法。102 答：分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，若A、B表中当前元素值相同，则写入C中，并使i、j、k值增1；若A表元素值较小，则使i增1；若B表元素值较小，则使j增1，直到有一个表先结束。SeqLiSt*intersection(SeqListA，SeqListB，SeqList*C){／／求元素依值递增有序排列的顺序表A、B的交集Ci=0；j=0；k=0；while((i<=A.length-1)&&(j<=B.length-1)){if(A.data[i]==B.data[j])／／找到值相同的元素{C->data[k]=A.data[i]；／／相同元素写入C表中k++；i++；j++；}elseif(A.data[i]length=k；returnC；}11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前驱结点。答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s开始，顺次向后寻找。102 voidDeletePre(Linkedlist*s){／／删除单循环链表中结点s的直接前驱p=s；while(p—>next—>next!=s)p=p—>next；／／找到s的前驱的前驱pq=p—>next；／／q是p的后继，即s的前驱p—>next=s；／／将q删除free(q)；}12．计算带头结点的循环链表的结点个数。答：intnumber(Linkedlist*head){／／计算单循环链表中结点的个数p=head—>next；i=0；while(p!=head){i++；p=p->next；}returni；}13．已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个表可使用原来的单链表。q指向p的下一个结点，根据*p的数据域的值将其插入到不同的链表上。再把q的值给p，处理下一个结点。102 voidchange(LinkedList*L，LinkedList*pa，LinkedList*pb，LinkedList*pc){／／分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符p=L—>next；pa=L；pa—>next=pa；／／分别构造三个单循环链表pb=(LinkedList*)malloc(sizeof(LinkedList))；pc=(LinkedList*)malloc(sizeof(LinkedList))；pb—>next=pb；pc—>next=pc；while(p!=L){q=p—>next；·／／q记下L中下一个结点的位置if(p—>data<=’z’&&p—>data>=’a’)／／链接到字母链表的头部{p—>next=pa—>next；pa—>next=p；}elseif(p—>data<=’9’&&(p—>data>=’0’)／／链接到数字链表的头部{p—>next=pb—>next；pb—>next=p；}else{p->next=pc->next；pc->next=p；}／／链接到其他字母链表的头部p=q；}}102 14、己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法(注：题中未特别指明同一表中的元素值各不相同)。答：分析：先从B和C中找出共有元素，记为same，再在A中从当前位置开始，凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个SameSeqListIntersectDelete(SeqList*A，SeqListB，SeqListC){／／对顺序表A删去那些既在B表中出现又在C表中出现的元素i=0；j=0；k=0；m=0;／／i指示A中元素原来的位置，m为移动后的位置while(ilength&&iC.data[k])k++;else{same=B.data[j]；／／找到了相同元素samewhile(B.data[j]==same)j++；while(C.data[k]==same)k++；／j、k后移到新的元素while(ilength&&A->data[i]data[m++]=A->data[i++]；／／需保留的元素移动到新位置102 while(i1ength&&A->data[i]==same;i++；／／跳过相同的元素}}while(ilength)A->data[m++]=A->data[i++]；／／A的剩余元素重新存储A->1ength=m；}15．双循环链表中，设计满足下列条件的算法。(1)在值为x的结点之前插入值为y的结点。(2)删除值为x的结点。答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。typedefstructNode{DataTypedata；structNode*prior，*next；}DLNode，*DLinkedList；voidDLinsertl(DLinkedListL，intx，inty){／／在双循环链表中插入结点p=L->next；while(p!=L&&p->data!=x)p=p->next；／／在链表中查找值为x的结点if(p->data==x)／／找到值为x的结点{q=p->prior；／／q指向值为x的结点的前驱s=(DLinkedList)malloc(sizeof(DLNode))；102 s->data=y；s->next=p；s->prior=q；／／将y插入到q与p指向的结点之间p->prior=s；q->next=s；}else{printf(”没有值为x的结点”)；exit(0)；}}voidDLDelete(DLinkedListL，intx){／／在双循环链表中删除结点p=L->next；while(p!=L&&p->data!=x)p=p->next；if(p->data==x){p->prior->next=p->next；p->next->prior=p->prior；free(p)；}else{printf(”没有值为x的结点”)；exit(0)；}}16．设有一个双循环链表，其中有一结点的指针为p，编写算法将p与其右边的一个结点进行交换。答：typedefstructNode{DataTypedata；structNode*prior，*next；}DLNode，*DLinkedList；voidDLchange(DLinkedListp){／／将双循环链表中p指向的结点与其右边的一个结点进行交换q=p—>next；／／q指向p的后继p—>prior—>next=q；q—>prior=p—>prior；／／将p的前驱与q相链接p—>next=q—>next；p—>prior=q；102 ／／将p插入到q之后q->next—>prior=p；q—>next=p；}17．设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq，在链表启用之前，其初始值均为0。每当链表进行一次LocateNode(L，x)操作时令元素值为x的结点中freq域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。答：分析：先在双链表中查找值为x的结点，若找到则使其freq值增1，然后从头至尾扫描链表，将此结点插入到按freq递减顺序排列的正确位置。typedefstructDLNode{intdata，freq；structDLNode*prior，*next；}DLNode，*DLinkedList；voidLocateNode(DLinkedListhead，intx){／／双链表按访问频度域freq递减次序排列p2=head；p1=p2—>next；／／p2在前，p1在后while(p1)／／查找单链表中值为x的结点if(pl—>data==x){pl—>freq++；break；}／／使值为x的结点的freq加1else{p2=pl；p1=p2—>next；}if(p1==NULL)printf(”Notfound.＼n”)；102 else{if(p1—>next==NULL){p2—>next=p1—>next；temp=p1；}／／在链表中找temp所指向的结点，按freq值递减应插入的位置else{p2—>next=p1—>next；／／插入链表中间的某一位置p1—>next->prior=p2；temp=pl；}for(p2=head，p1=p2->next；pl&&p1->freq>temp->freq；p2=p1，pl=p2->next)；／／插入if(p1==NULL){p2->next=temp；temp->prior=p2；temp->next=NULL；}else{p2->next=temp；temp->prior=p2；temp->next=pl；p1->prior=temp；}}}18．给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。答：typedefstructPNode{intcoef；／／系数intexp；／／指数structPNode*next；}*PLink；PLinkCreatPoly(){／／建立多项式head=(PLink)malloc(sizeof(structPNode))；102 r=head；printf(”输入系数和指数：”)；scanf(&n，&m)；while(n!=0)／／若n=0则退出循环{s=(Plink)malloc(sizeof(structPNode))；s->coef=n；s->exp=m；r->next=s；r=s；／／把s链接到r的后面printf(”输入系数和指数:”)；scanf(&n，&m)；}r->next=NULL；head=head—>next；／／删除头结点returnhead；}19．根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。答：分析：对所有指数相同的项，将其对应系数相加，若和不为0，则构造新“和多项式”的结点；将所有指数不同的项复制到和多项式中。Plinkadd(PLinkpa，PLinkpb){／／多项式相加p=pa；q=pb；pc=(PLink)malloc(sizeof(structPNode))；r=pc；while(p!=NULL&&q!=NULL){if(p->exp==q->exp)／／两结点的指数相同时，将两系数相加生成新结点插入c中{x=p->coef+q->coef；102 if(x!=0){s=(PLink)malloc(sizeof(structPNode))；s->coef=x；s->exp=p->exp；r->next=s；r=s；}p=p->next；q=q->next；}elseif(p->exp>q->exp)／／两结点的指数不同时，将较小系数的结点复制成新结点插入c中{s=(PLink)malloc(sizeof(structPNode))；s->coef=q->coef；s->exp=q->exp；r->next=s；r=s；q=q->next；}else{s=(PLink)malloc(sizeof(structPNode))；s->coef=p->coef；s->exp=p->exp；r->next=s；r=s；p=p->next；}}while(p!=NULL)／／复制A的余下部分{s=(PLink)malloc(sizeof(structPNode))；s->coef=p->coef；s->exp=p->exp；r->next=s：r=s；p=p->next；}while(ql=NULL)／／复制B的余下部分{s=(PLink)malloc(sizeof(structPNode))；s->coef=q->coef；s->exp=q->exp；r->next=s；r=s；q=q->next；}r->next=NULL；／／最后结点的next域置为空s=pc；pc=pc->next；／／删除c的头结点102 free(s)；returnpc;}20．约瑟夫环问题：任给正整数n、k，按下述方法可得排列1，2，…，n的一个置换：将数字l，2，…，n环形排列，按顺时针方向从1开始计数；计满k时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10、k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。答：voidJs1(intA[n]，intN，ihtK){／／以数组为存储结构for(i=0；inext；／／此时q为头结点fp为q的前驱while(N>0){for(j=2；j<=K；j++)／／循环K-1次{p=q；q=p->next；}printf(”%d”，q->data)；N--；p->next=q->next;／／删除qq=p—>next；}}第三节栈和队列一、选择题1．设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是()。A．2*B．3C．5D．62．若一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为()。A．4*B．5C．6D．73．设有一顺序栈已经含有3个元素，如图3-1所示，元素a4正等待入栈。以下序列中不可能出现的出栈序列是()。*A．a3，a1，a4，a2B．a3，a2，a4，a1102 C．a3，a4，a2，a1D．a4，a3，a2，a14．和顺序栈相比，链栈有一个比较明显的优势是()。*A．通常不会出现栈满的情况B．通常不会出现栈空的情况C．插入操作更容易实现D．删除操作更容易实现5．若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是()。A．不确定B．n-i*C．n-i+1D．n-i-16．以下说法正确的是()。*A．因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况B．因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况C．对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢”D．对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢”7．顺序队列的入队操作应为(sq.rear初值为-1)。*A．sq.rear=sq.rear+1；sq.data[sq.rear]=x;B．sq.data[sq.rear]=x；sq.rear=sq.rear+1；C．sq.rear=(sq.rear+1)％maxsize；sq.data[sq.rear+1]=x;102 D．sq.data[sq.rear]=x；sq.rear=x;sq.rear=(sq.rear+1)％maxslze；8．循环队列的入队操作应为(sq.rear初值为-1)。A．sq．rear=sq．rear+1；sq．data[sq．rear]=xB．sq．data[sq．rear]=x；sq．rear=sq．rear+l；*C．sq．rear=(sq．rear+1)％maxsize；sq．data[sq．rear]=x；D．sq．data[sq．rear]=x；sq．rear=(sq．rear+1)％maxsize；9．顺序队列的出队操作为(sq.front初值为-1)。A．sq．front=(sq．front+1)％maxsize；*B．sq．front=sq．front+1；C．sq．rear=(sq．rear+1)％maxsize；D．sq．rear=sq．rear+1;10．循环队列的出队操作为(sq.front初值为-1)。*A．sq．front=(sq．front+1)％maxsize；B．sq．front=sq．front+1；C．sq．rear=(sq．rear+1)％maxsize；D．sq．rear=sq．rear+l；11．循环队列的队满条件为()。A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize；B．(sq．rear+1)％maxsize==sq．front+1；*C．(sq．rear+1)％maxsize==sq．front；D．sq．rear==sq．front；12．循环队列的队空条件为()。102 A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize；B．(sq．rear+1)％maxsize==sq．front+1；C．(sq．rear+1)％maxsize==sq．front；*D．sq．rear==sq．front；13．如果以链表作为栈的存储结构，则出栈操作时()。A．必须判别栈是否满B．判别栈元素的类型*C．必须判别栈是否空D．对栈不做任何判别14，向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为()。A．Top->next=s；B．s->next=Top->next；Top->next=s；*C．s->next=Top；Top=s；D．s->next=Top；Top=Top->next；15．从栈顶指针为Top的链栈中删除一个结点，并将被删结点的值保存到x中，其操作步骤为()。*A．x=Top->data；Top=Top->next；B．Top=Top->next；x=Top->data；C．x=Top；Top=Top->next；D．x=Top->data；16．在一个链队中，苕f、r分别为队头、队尾指针，则插入s所指结点的操作为()。A．f->next=s；f=s；*B．r->next=s；r=s；C．s->next=r；r=s；D．s->next=f；f=s；17．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是()。A．e，d，c，b，aB．d，e，c，b，a102 *C．d，c，e，a，bD．a，b，c，d，e18．一个队列的入队序列是1，2，3，4，则队列可能的输出序列是()。A．4，3，2，1*B．1，2，3，4C．1，4，3，2D．3，2，4，119．设计一个判别表达式中左，右括号是否配对出现的算法，采用()数据结构最佳。A．线性表的顺序存储结构*B．栈C．队列D．线性表的链式存储结构二、判断题√1．在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。╳2．与顺序栈相比，链栈的一个优点是插入和删除操作更加方便。╳3．若一个栈的输入序列为1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1，2，…，n)。√4．在链队中，即使不设置尾指针也能进行入队操作。√5．在对链队(带头指针)做出队操作时，不会改变front指针的值。╳6．循环队列中元素个数为rear-front。╳7．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2．√102 8．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。╳9．若以链表作为栈的存储结构，则入栈需要判断栈是否满．√10．若以链表作为栈的存储结构，则出栈需要判断栈是否空。三、填空题1．向一个栈顶指针为Top的链栈中插入一个s所指的结点时，其进行的操作是__s->next=Top；Top=s；__。2．从栈顶指针为Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_x=Top->data；Top=Top->next；__。3．在具有n个单元的循环队列中，队满时共有___n-1_个元素。4．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为__b，c，e，d，a___。5．设有数组A[m]作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是_rear=（rear+1）％（m+1）；A[rear]=x;__。6．在一个链队中，如果f、r分别为队头、队尾指针，则插入s所指结点的操作是_r->next=s;r=s;___。7．栈的逻辑特点是__后进先出____，队列的逻辑特点是_先进先出__，二者的共同特点是_操作受限__。102 8．___栈___可以作为实现递归函数调用的一种数据结构。9．在队列中，新插入的结点只能添加到__队尾__。10．链队在一定范围内不会出现__队满___的情况。当lq．front==lq．rear时，队中无元素，此时___队空__。11．设一个链栈的栈顶指针为ls，栈中结点的格式为data:next，栈空的条件是_ls=NULL__；如果栈不为空，则出栈操作为p=ls;___ls=ls->next__；free(p)。12．对带有头结点的链队lq，判定队列中只有一个数据元素的条件是__lq->front->next=lq->rear___。13．设有一个空栈，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push后，栈顶指针所指元素是__4__。14．设用一维数组A[n]来表示一个栈，令A[0]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值__加1___，从栈中弹出一个元素时，变量t的值___减1___。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是___c__。四、应用题102 2．设有字符串为3*-y-a/y^2，试利用栈写出将其转换为3y-*ay2^/-的操作过程。假定用X代表扫描该字符串过程中顺序取一个字符入栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。答：XSXXXSSSXXSXXSXXSSSS3．设有一个输入序列a，b，c，d，元素经过一个栈到达输出序列，而且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列?答：可以得到14种输出序列：abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc.4．按照运算符优先法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9-2*4+(8+1)/3。答：序号运算符栈操作数栈输入字符1#92#9-3#-924#-92*5#-*9246#-*924+7#-988#19#+1(102 10#+(1811#+(18+12#+(+18113#+(+181)14#+19/15#+/19316#+/193#17#+1318#45．链栈中为何不设置头结点?答：因为链栈只在链表头插入和删除结点，不可能在链表中间插入或删除结点，算法实现很简单，所以一般不设置头结点。第四节数组一、选择题1．数组通常具有的两种基本操作是()。A．建立和删除B．索引和修改*C．查找和修改D．查找和索引2．二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是()。*A．1208B．1212C．1368D．13643．对矩阵压缩存储是为了()。102 A．方便运算*B．节省空间C．方便存储D．提高运算速度4．稀疏矩阵的压缩存储方法通常有两种，即()。A．二元数组和三元数组B．三元组和散列*C．三元组和十字链表D．散列和十字链表二、判断题√1．数组是同类型值的集合。√2．数组是一组连续的内存单元。╳3．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。╳4．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。√5．使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。三、填空题1．二维数组A[10，20]采用列序为主序方式存储，每个元素占一个存储单元，并且A[1，1]的存储地址是200，则A[6，12]的地址是___315___。2．有一个10阶对称矩阵A采用压缩存储方式(以行序为主序方式)存储其下三角元素，且第一个元素A[0，0]的存储地址为1，则A[4，5]的地址是__14__，A[8，3]的地址是___31_。102 3．下三角矩阵A[N,N]的下三角元素已压缩到一维数组S[N(N+1)／2]中，若按行序为主序存储，则A[i，j]对应的S中的存储位置是__I(I-1)/2+j(i≥j),n(n+1)/2+1(I0)层上至多有__2i-1__个结点。4．深度为k(k>0)的二叉树至多有__2k-1__个结点。5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__n2+1__。6．满二叉树上各层的节点数已达到了二叉树可以容纳的__最大值_。满二叉树也是__完全__二叉树，但反之不然。7．具有n个结点的完全二叉树的深度为___│log2n│+1___。102 8．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是__│log2i│=│log2j│____。9．如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(0l，则X的双亲PARENT(X)的编号为__│i/2│___。(2)若2i>n，则结点x无__左孩子__且无__右孩子__；否则，X的左孩子LCHILD(X)的编号为__2i__。(3)若2i+1>n，则结点X无__右孩子__；否则，X的右孩子RCHILD(X)的编号为__2i+1__。10．二叉树通常有___顺序____存储结构和___链式__存储结构两类存储结构。11．每个二叉链表还必须有一个指向__根__结点的指针，该指针具有标识二叉链表的作用。12．对二叉链表的访问只能从___根__指针开始。13．具有n个结点的二叉树中，一共有__2n__个指针域，其中只有__n-1_个用来指向结点的左右孩子，其余的__n+1__个指针域为NULL。14．已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为__99（40+39+20）___。15．二叉树有不同的链式存储结构，其中最常用的是_二叉链表___与__三叉链表__。16．可通过在非完全二叉树的“残缺”位置上增设__空指针___将其转化为完全二叉树。17．具有100个结点的完全二叉树的深度是__7___。102 18．深度为90的满二叉树上，第10层有___512___个结点。19．在__前序__遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。20．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号是__│n/2│___，编号最小的分支结点序号是__1_，编号最大的叶结点序号是_n_，编号最小的叶结点序号是__│n/2│+1____。21．若一棵二叉树的叶子数为n，则该二叉树中左、右子树皆非空的结点个数为__n-1__。22．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为__n-2m+1__个。23．设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有___59__个结点。24．现有按中序遍历二叉树的结果为ABC，有__5___种不同形态的二叉树可以得到这一遍历结果。25．以数据集{4，5，6，7，10}为叶结点的权值所构造的哈夫曼树的带权路径长度为_63_.26．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有__16_个叶结点。27．设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶结点的个数是__8_。102 28．如果结点a有三个兄弟，而b是a的双亲，则b的度是__4__。29．一棵树的形状如图6-5所示，它的根结点是__A_，叶结点是__E,J,K,L,O,P,Q,R,N,I__，结点H的度是__3__，这棵树的度是_4_，这棵树的深度是__5__，结点F的儿子结点是_J,K__，结点G的父结点是__C__。30．设结点x有左孩子结点y、右孩子结点z，用三种基本遍历方法得到的遍历序列中x__不一定___是y的前驱，x__不一定__是z的后继，y__一定__是z的前驱(填“一定”，“不”、“不一定”)。31．在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_前驱__，且存在一条从根到该结点的__惟一路径__。32．含有2n个结点的二叉树高度至少是__n+1___，至多是__2n_(仅含根结点的二叉树高度为1)。33．设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为_2h-1__，至多为__2h-1__。四、应用题102 1．分别画出含3个结点的树与二叉树的所有不同形态。答：略。2．设在树中，结点x是结点y的双亲，用来表示边。已知一棵树边的集合为：{，，，，，，，，，，}，用树形表示法画出此树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶结点？(3)哪个是g的双亲？(4)哪些是g的祖先？(5)哪些是e的子孙？(6)哪些是f的兄弟？(7)结点b和j的层次各是多少？(8)树的深度是多少？(9)树的度数是多少？答：略。3．任意一个有n(n>0)个结点的二叉树，已知它有m个叶结点，试证明非叶结点有m-1个度为2，其余度为1。答：设度为1的结点数n1,设度为2的结点数n2,分支数B,则有:m+n1+n2=n,B+1=n,B=1*n1+2*n2,即:m+n1+n2=n,n1+2n2+1=n,解之可得:n2=m-14．分别画出图6-6所示二叉树的二叉链表、三叉链表和顺序存储结构。102 答：略.5．分别写出图6-7所示二叉树的前序、中序和后序序列。答：前序：ABCDEF、中序：CBEFDA和后序：CFEDBA6．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。答：前序遍历序列：ABCDEFGH7．二叉树中的结点进行按层次顺序(每层自左到右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二又树。答：略.8．将图6-9所示的森林转换成二叉树。102 答：略.9．分别画出图6-10所示二叉树对应的森林，并写出森林的前序和后序遍历序列。答：前序：ABDGCEFHIJK，后序：DGBAECIHJKF。10．设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。答：略.11．将代数式y=3*(x+a)-a/x2描述成表达式树，并写出前缀式和后缀式。答：前缀式：-*3+xa/a*xx，后缀式:3xa+*axx*/-。13．试证明：任一棵高度为h>1的二叉树，其内部结点(除根、叶子之外的结点)的数目小于2h-1-1，而叶结点数目小于或等于2h-1。102 答：高度为h的满二叉树包含的结点个数最多,最下层是叶子,除根外,其余是内部结点,不包含叶子的子树高度是h-1,该子树的最多结点数是2h-1-1.除根外,内部结点的数目应小于2h-1-1.而整个树所含的最多结点数是2h-1,所以,叶子数最多为2h-1-(2h-1-1)=2h-1个.14．编码{00，01，10，11}、{0，1，00，11，}、{0，10，110，111}哪一组不是前缀码?答：编码{00，01，10，11}、{0，10，110，111}不是前缀码,{0，1，00，11}是前缀码.15．一棵度为k的树有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，问该树中有多少个叶结点?答：n=n0+n1+……+nk=1*n1+2*n2+……k*nkn0=1+n2+2n3+……+(k-1)nk16．一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少?答：最大深度：n，最小深度：│logk(n(k-1))│+117．画出和已知序列对应的树T：树的前序序列为：ABCEFDGH；树的后序序列为：BEFCHGDA。答：略.五、算法设计题1．以二叉链表作为存储结构，试编写求二叉树深度的算法。答：intbdepth(btreet){if(t==NULL)return0;102 else{l=bdepht(t->lchild);r=bdepht(t->rchild);return(l>r？l:r+1；}}2．以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。答：略.第六节图一、选择题1．在一个图中，所有顶点的度数之和等于所有边数的()倍。A．1／2B．1*C．2D．42．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A．1／2*B．1C．2D．43．一个有N个顶点的无向图最多有()条边。A．NB．N*(N-1)*C．N*(N-1)／2D．2N4．具有4个顶点的无向完全图有()条边，*A．6B．12C．16D．205．具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。*A．5B．6C．7D．8102 6．一个具有N个顶点的无向图中，要连通全部顶点至少需要()条边。A．NB．N+1*C．N-1D．N／27．对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是()。A．NB．(N-1)*(N-1)C．N-1*D．N*N8．对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为((1))；所有邻接表中的结点总数是((2))。(1)*A．NB．N+1C．N-1D．N+E(2)A．E/2B．E*C．2ED．N+E9．已知图7-1所示的图，若从顶点A出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为((1))；若按广度优先搜索法进行遍历，则可能得到的一种顶点序列为((2))。(1)A．ABECDFB．ACFEBDC．AEBCFD*D．AEDFCB(2)A．ABCEDF*B．ABCEFDC．AEBCFDD．ACFDEB102 10．采用邻接表存储的图的深度优先遍历算法类似于二叉树的()。*A．前序遍历B．中序遍历C．后序遍历D．层次遍历11．采用邻接表存储的图的广度优先遍历算法类似于二叉树的()。A．前序遍历B．中序遍历C．后序遍历*D．层次遍历12．含n个顶点的连通图中的任意一条简单路径，其长度不可能超过()。A．1B．n／2*C．n-1D．n13．一有向图的邻接表存储结构如图7-2所示。现在按深度优先遍历算法，从顶点v1出发，所得到的顶点序列是()。A．v1v3v2v4v5B．v1v3v4v2v5C．v1v2v3v4v5*D．v1v3v4v5v214．设有两个无向图G=(V,E)，G’=(V’，E’)，如果G’是G的生成树，则下列说法不正确的是()。A．G’是G的子图*B．G’是G的连通分量C．G’是G的无环子图D．G’是G的极小子图，且V’=V15．任何一个带权的无向连通图的最小生成树()。102 A．只有一棵*B．有一棵或多棵C一定有多棵D．可能不存在16．设图G采用邻接表存储，则拓扑排序算法的时间复杂度为()。A．O(n)*B．O(n+e)C．O(n*n)D．O(n*e)17．在图7-3中，从顶点vl出发，按广度优先遍历图的顶点序列是()。A．V1V5V3V4V2V6V7*B．V1V2V4V5V7V6V3C．VlV5V3V4V2V7V6D．VlV2V7V4V6V5V318．以下说法正确的是()。A．连通图的生成树是该连通图的一个极大连通子图B．无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的C．任何一个有向图，其全部顶点可以排成一个拓扑序列*D．有回路的图不能进行拓扑排序19．以下说法错误的是()。A．用邻接矩阵法存储图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关*B．邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用102 C．存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下(或上)三角部分D．用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可20．以下说法正确的是()。A．连通分量是无向图中的极小连通子图*B．强连通分量是有向图中的极大强连通子图C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧D．对有向图G，如果从任意顶点出发进行一次深度优先搜索或广度优先搜索能访问到每个顶点，则该图一定是完全图二、判断题√1．用邻接矩阵法存储图时，所占用的存储空间大小仅与图中结点个数有关。╳2．对任意图，从它的某个顶点出发，进行一次深度优先搜索或广度优先搜索，即可访问图的每个顶点。╳3．任何有向网拓扑排序的结果是惟一的。√4．有回路的图不能进行拓扑排序。╳5．存储有向图的邻接矩阵一定是对称的。√6．一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点vi、vj和vk的相对位置为vi、vj、vk。√7．含有10个顶点的无向连通图其生成树含有9条边。102 ╳8．十字链表是图的一种顺序表示法。三、填空题1．对具有n个顶点的图，其生成树有且仅有__n-1_条边，即生成树是图的边数__最少_的连通图。2．对无向图，其邻接矩阵是一个关于__主对角线_对称的矩阵。3．在有向图的邻接矩阵上，由第i行可得到第__i__个结点的出度，而由第j列可得到第__j__个结点的入度。4．对无向图，设有n个结点e条边，则其邻接表表示中需要_2e_个表结点。对有向图，设有n个顶点e条弧，则其邻接表表示需要__e_个表结点。5．在无权图G的邻接矩阵A中，若(Vi，Vj)或属于图G的边集，则对应元素A[i，j]等于__1___，否则等于___0___。6．已知图G的邻接表如图7-4所示，从其顶点V1出发的深度优先搜索序列为___V1V2V3V6V5V4__，从其顶点v1出发的广度优先搜索序列为__V1V2V5V4V3V6___。102 7．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是__第i列的元素之和__。删除所有从第i个结点出发的边的方法是__将第i行的元素清0____。8．设无向图G中顶点数为n，则图G最少有__0___条边，最多有__n（n-1）/2__条边。若G为有向图，有n个顶点，则图至少有___0__条边，最多有___n（n-1）__条边。9．设图G有n个顶点和e条边，若采用邻接矩阵的存储结构，进行深度优先搜索的时间复杂度为__O(n2)__；若采用邻接表存储结构，进行广度优先搜索的时间复杂度至少为___O(e+n)___。10．连通分量是无向图中的__极大__连通子图。11．对无向图，若它有n个顶点e条边，则其邻接表中需要___n+2e__个结点。其中，___n__个结点构成头结点，___2e__个结点构成顶点表。12．对有向图，若它有n个顶点e条边，则其邻接表中需要___n+e__个结点。其中，_n___个结点构成头结点，____e__个结点构成顶点表。13．在邻接表上，无向图中顶点vi的度恰为__第i个链表中的结点数__。对有向图，顶点Vi的出度是__第i个链表中的结点数__。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为__i__的结点的个数是顶点vi的入度。14．遍历图的基本方法有__深度__优先搜索和___广度__优先搜索两种。四、应用题102 1．给出如图7-6所示的无向图G1的邻接矩阵和邻接表。答：略2．分别给出图7-6所示的G2的邻接矩阵、邻接表和逆邻接表。答：略3．分别给出图7-6所示的G3从V5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。答：深度优先：V5V4V3V2V1，广度优先：V5V4V2V3V14．设有一无向图G=(V，E)，其中V={1，2，3，4，5，6}，E={(1，2)，(1，6)，(2，6)，(1，4)，(6，4)，(1，3)，(3，4)，(6，5)，(4，5)，(1，5)，(3，5)}。(1)按上述顺序输入后，画出其相应的邻接表。(2)在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。答：(1)略(2)DFS序列453162，BFS序列453612。5．已知连通网的邻接矩阵如图7-8所示，顶点集合为{V1，V2，V3，V4，V5}，试画出它所表示的从顶点V1开始利用Prim算法得到的最小生成树。102 答：略。6．拓扑排序的结果不是惟一的，对图7-9进行拓扑排序，写出全部不同的拓扑排序序列。答：拓扑排序序列：164275938，614275938，641275938。7．已知图G的邻接表如图7-10所示，顶点V1为出发点，完成以下要求：(1)深度优先搜索的顶点序列。(2)广度优先搜索的顶点序列。答：(1)深度优先：V1V5V6V3V2V4(2)广度优先：V1V2V4V5V3V6第七节查找102 一、选择题1．顺序查找法适合于()存储结构的查找表。A．压缩B．散列C．索引*D．顺序或链式2．对采用折半查找法进行查找操作的查找表，要求按()方式进行存储。A．顺序存储B．链式存储*C．顺序存储且结点按关键字有序D．链式存储且结点按关键字有序3．设顺序表的长为n，用顺序查找法,则其每个元素的平均查找长度是()。*A．(n+1)／2B．(n-1)／2C．n／2D．n4．设有序表的关键字序列为(1，4，6，10，18，35，42，53，67，71，78，84，92，99)，当用折半查找法查找键值为35的结点时，经()次比较后查找成功。A．2B．3*C．4D．65．长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是()。A．24／10B．24／11C．39／10*D．39／116．在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为()。*A．n+lB．1C．nD．n-1102 7．在采用链地址法处理冲突所构成的开散列表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值()。*A．一定都是同义词B．不一定都是同义词C．都相同D．一定都不是同义词8．用顺序查找法对具有n个结点的线性表查找的时间复杂度量级为()。A．O(n2)B．O(nlog2n)*C．O(n)D．O(log2n)9．用折半查找法对具有n个结点的线性表查找的时间复杂度量级为()。A．O(n2)B．O(nlog2n)C．O(n)*D．O(log2n)10．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值()。A．一定都是同义词*B．不一定都是同义词C．都相同D．一定都不是同义词11．设哈希函数为H(key)=key％7，一组关键字为(37，21，9，20，30，19，46)，哈希表T的地址空间为0..6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为()。A．01234562120379463019*B．0123456102 2146379301920C．01234562119937304620D．0123456203730214619912．设有一个用线性探测法解决冲突得到的哈希表：0123456789101325801617614哈希函数为H(key)=key％11，若要查找元素14，探测的次数是()。A．3*B．6C．7D．913．在哈希函数H(key)=key％m中，一般来讲，m应取()。A．奇数B．偶数*C．素数D．充分大的数14．分块查找的时间性能()。A．低于折半查找*B．高于顺序查找而低于折半查找C．高于顺序查找D．低于顺序查找而高于折半查找15．以下说法错误的是()。A．哈希法存储的基本思想是由关键字的值决定数据的存储地址102 *B．哈希表的结点中只包含数据元素自身的信息，不包含任何指针C．装填因子是哈希法的一个重要参数，它反映哈希表的装填程度D．哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法16．以下说法正确的是()。A．前序遍历二叉排序树的结点就可以得到排好序的结点序列B．任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间C．对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的*D．采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要17．已知采用线性探测法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是()。A．将该元素所在的存储单元清空*B．将该元素用一个特殊的符号代替C．将与该元素有相同散列地址的后继元素顺次前移一个位置D．用与该元素有相同散列地址的最后插入表中的元素替代18．设哈希表长为M=14，哈希函数H(key)=key％11。表中已有4个结点：ADDR(15)=4，ADDR(38)=5，ADDR(61)=6，ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是()。A．3B．8C．9*D．10102 19．有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为()。A．32／12B．35／12*C．37／12D．39／1220．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应()个结点最佳。*A．25B．10C．6D．62521．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用()查找方法。*A．分块B．顺序C．折半D．散列22．有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行()次探测。A．k-1B．kC．k+l*D．k(k+1)／223．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其平均查找长度与()查找方法量级相当。A．分块B．顺序*C．折半D．散列24．在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为()。*A．O(n)B．O(1)C．O(log2n)D．O(n2)25．哈希表的平均查找长度()。A．与处理冲突的方法有关而与表的长度无关102 B．与处理冲突的方法无关而与表的长度有关*C．与处理冲突的方法有关且与表的长度有关D．与处理冲突的方法无关且与表的长度无关26．若对长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为()。A．(d+1)％m*B．(d-1)％mC．(d+4)％mD．(d-4)％m27．以下说法正确的是()。*A．数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字的分布情况，并且键值的位数比散列地址的位数多B．除余法要求事先知道全部键值C．平方取中法需要事先掌握键值的全部分布情况D．随机数法适用于键值不相等的场合28．有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列()输入序列。A．45，12，49，6，40，56，32*B．40，12，6，32，49，45，56C．6，12，32，40，45，49，56D．32，12，6，40，45，56，4929．在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为()。A．nB．log2nC．(h+1)／2*D．h二、判断题102 √1．分块查找方法的平均查找长度低于顺序查找，高于折半查找。√2．若采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。╳3．前序遍历二叉排序树的结点就可以得到排好序的结点序列。╳4．在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查找时间。╳5．虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。√6．对两棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。√7．在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。╳8．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。三、填空题1．任何结点之间都不存在_逻辑_关系，这是集合这种逻辑结构的基本特点。2．在开散列表上查找键值等于K的结点，首先必须计算该键值的__散列地址__，然后再通过指针查找该结点。102 3．在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个“索引项”。每个索引项有两个域：块内最大__元素__值和块__首__位置。4．索引顺序表上的查找分两个阶段：一、___确定元素所在的块__；二、___在块内查找元素__。该查找方法称为__分块__查找。5．二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值__大_于其左孩子(及其子孙)的键值且__小__于其右孩子(及其子孙)的键值。6．在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值__大__的结点，只需通过结点x的右指针到它的右子树中去找。7．中序遍历一棵二叉排序树所得到的结点访问序列是键值的___递增__序列。8．二叉排序树上的查找长度不仅与__元素个数_有关，也与二叉排序树的__输入序列__有关。9．二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵单支树时，查找算法退化为__顺序___查找，平均查找长度上升为__（n+1）/2__。10．__散列__查找法的平均查找长度与元素个数n无关。102 11．在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为__1___，比较两次查找成功的结点数为__2__，比较五次查找成功的结点数为_5_。总的平均查找长度为__37/10___。12．当所有结点的值都相等时，用这些结点构造的二叉排序树上只有___一个结点__。13．折半查找方法仅适用于这样的表：表中的记录必须__有序__，其存储结构必须是__顺序存储___。14．考虑具有如下性质的二叉树：除叶结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9-1所示的二叉树中，并使之满足上述性质(圆圈旁边的数字表示插入结点的序号)。15．设线性表L=(a1，a2，…，an)(n>2)，表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查找法和折半查找法查找与k相等的元素，比较次数分别为s和b，若查找不成功，则s和b的数量关系是_s>b_。102 16．某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为__10001/2___，最大比较次数为__10000__。现把10000个元素按排列顺序划分成若干组，使得每一组中有g个元素(最后一组可能小于g)。查找时，先从第一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的g是__100__，此时的平均比较次数是__101__。17．长度为225的表，采用分块查找法，每块的最佳长度是_15__，应分_15_块，若每块的长度为10，则平均查找长度为_35/2_。18．已知有序表为(13,17,20,32,48,54,65,79,86,91,97)，当采用折半查找法查找86时需进行_2__次比较可确定查找成功，查找48时需进行_4_次比较可确定查找成功，查找100时需进行_4_次比较才能确定查找不成功。四、应用题1．已知有长度为9的表(16,29,32,5,89,41,14,65,34)，它们存储在一个哈希表中，利用线性探测再散列法，要求它在等概率情况下查找成功的平均查找长度不超过3。(1)该哈希表的长度m应设计成多大？(2)设计相应的哈希函数。(3)将数据填入到哈希表中。102 (4)计算查找成功时的平均查找长度。答：(1)该哈希表的长度m=12（公式）(2)H(key)=key%11(3)0123456789101189341416529413265121121112(4)ASL=(1+2+1+1+2+1+1+1+2)/9=12/9=4/32．假定有n个关键字，它们具有相同的哈希函数值，用线性探测法把这n个关键字存入到哈希表中要做多少次探测？答：n个关键字都是同义词，因此用线性探测法解决冲突都会发生冲突，所以探测次数为：1+2+……+n=n(n+1)/2.3．地址空间为0—14的哈希表中，对关键字序列(JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC)构造哈希函数H(key)=└i／2┘，其中i为关键字中第一个字母在字母表中的序号。用线性探测法和链地址法分别求出这两个哈希表在等概率情况下查找成功和查找不成功的平均查找长度。答：(1)用线性探测法01234567891011121314102 APRAUGDECFEBJANMARMAYJUNJULSEPOCTNOV121111245256查找成功ASL=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12查找不成功ASL=(5+4+3+2+1+9+8+7+6+5+4+3+2+1+1)/15=61/15(2)链地址法：图略。查找成功ASL=(1*7+2*4+3*1)/12=18/12=3/2查找不成功ASL=(3+1+2+2+1+4+3+3+1+2+1+1+1+1+1)/15=27/15=9/54．有一个400项的表，欲采用索引顺序查找方法进行查找，问：(1)分成多少块最为理想？(2)每块的理想长度是多少？(3)平均查找长度是多少？答：(1)分成20最为理想？(2)每块的理想长度是20(3)平均查找长度是（20+1）/2+（20+1）/2=215．设有一组关键字(19，05，21，24，45，20，68，27，70，11，10)，用哈希函数H(key)=key％13，采用线性探测再散列方法解决冲突，试在0—14的散列地址空间中对该关键字序列构造哈希函数，并求查找成功和查找不成功时的平均查找长度。答：012345678910111213142768051945212070241110102 11112136124查找成功ASL=（1+1+1+1+2+1+3+6+1+2+4）/11=23/11查找不成功ASL=（1+2+1+2+1+10+9+8+7+6+5+4+3+2+1）/15=62/156．线性表的关键字集合(47，26，120，08，39，68，96，23，70，63，57)，已知散列函数为H(key)=key％13，采用链地址法处理冲突。设计出这种链表结构，并计算该表的查找成功和查找不成功时的平均查找长度。答：图略。查找成功ASL=(1*6+2*4+3*1)/11=17/11查找不成功ASL=(3+1+1+3+1+4+1+1+3+1+2+2+1)/13=24/137．分别画出在线性表(06，10，19，24，37，42，50，83)中进行折半查找，查找关键字10和30的过程。答：图略。查找关键字10：2次和30：3次。8．将(for,case,while,switch,break,do,define,const,if,int)中的关键字依次插入初始状态为空的二叉排序树(按字母在字母表中的序号排序)中，请画出所得到的树T。然后画出删除for之后的二叉排序树T，若再将for插入到T中得到二叉排序树T”，问T”与T是否相同？答：图略。T”与T不同102 9．设二叉排序树中的关键字由1—100内的整数构成，现要查找关键字为63的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列？(1)12，25，7，68，33，34，37，63(2)92，20，91，24，88，25，36，63(3)95，22，91，24，94，25，63(4)21，89，77，29，36，38，41，47，63答：(3)是不可能在二叉排序树上查找到的序列10．给定表(25，18，48，07，76，52，81，70，92，15)。试按元素在表中的次序将它们依次插入一棵初始状态为空的二叉排序树，画出插入完成之后的二叉排序树。答：图略。11．二叉排序树中的关键字互不相同，则其中最小元素无左孩子，最大元素无右孩子，此命题是否正确？最小元素和最大元素一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？答：最小元素无左孩子，最大元素无右孩子，此命题正确。最小元素和最大元素不一定是叶子。一个新结点一定是插在二叉排序树的某叶子上。第八节排序一、选择题102 1．在文件局部有序或文件较小的情况下，最佳的排序方法是()。*A．直接插入排序B．直接选择排序C．起泡排序D．归并排序2．初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为()。*A．n-1B．log2nC．2log2nD．n*n3．快速排序在最坏情况下的时间复杂度是()。A、O(log2n)B．O(nlog2n)*C．O(n2)D．O(n3)4．具有24个记录的序列，采用起泡排序最少的比较次数为()。A．1*B．23C．24D．5295．用某种排序方法对序列(25，84，21，47，15，27，68，35，20)进行排序，记录序列的变化情况如下：201521254727683584、152021253527476884、152021252735476884，则采用的排序方法是()。A．直接选择排序B．起泡排序*C．快速排序D．2-路归并排序6．在排序过程中，键值比较的次数与初始序列的排序顺序无关的是()。A．直接插入排序和快速排序B．直接插入排序和归并排序*C．直接选择排序和堆排序D．快速排序和归并排序102 7．()方法是从未排序序列中依次取出元素与已经排序序列中的元素进行比较，将其放人已经排序序列的正确位置上。A．归并排序*B．插入排序C．快速排序D．选择排序8．()方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。A．归并排序B．插入排序C．快速排序*D．选择排序9．()方法是对序列中的元素通过适当的位置变换将有关元素一次性地放置在其最终位置上。A．归并排序B．插入排序*C．快速排序D．基数排序10．将上万个无序并且互不相等的正数存储在顺序存储结构中，采取()方法能够最快地找到其中最大的正整数。A．快速排序B．插入排序*C．选择排序D．归并排序11．以下四种排序方法，要求附加内存空间最大的是()。A．插入排序B．选择排序C．快速排序*D．归并排序12．以下说法错误的是()。A．直接插入排序的空间复杂度为O(1)102 B．快速排序附加存储开销为O(log2n)*C．堆排序的空间复杂度为O(n)D．2-路归并排序的空间复杂度为O(n)，需要附加两倍的存储开销13．以下不稳定的排序方法是()。A．直接插入排序B．冒泡排序*C．直接选择排序D．2-路归并排序14．以下稳定的排序方法是()。A．快速排序*B．起泡排序C．直接选择排序D．堆排序15．以下时间复杂度不是O(n2)的排序方法是()。A．直接插入排序*B．2-路归并排序C．起泡排序D．直接选择排序16．以下时间复杂度不是O(nlog2n)的排序方法是()。A．堆排序*B．直接插入排序C．2-路归并排序D．快速排序17．快速排序方法在()情况下最不利于发挥其长处。A．要排序的数据量太大B．要排序的数据中含有多个相同值*C．要排序的数据已基本有序D．要排序的数据个数为奇数18．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用()方法。A．起泡排序B．快速排序*C．堆排序D．基数排序102 19．一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法以第一个记录为基准得到的一次划分结果为()。A．38，40，46，56，79，84B．40，38，46，79，56，84*C．40，38，46，56，79，84D．40，38，46，84，56，7920．一组记录的关键码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为()。·A．79，46，56，38，40，84*B．84，79，56，38，40，46C．84，79，56，46，40，38D．84，56，79，40，46，38二、判断题╳1．如果某种排序算法是不稳定的，则该方法没有实际意义。√2．当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要原因之一。╳3．对于n个记录的集合进行起泡排序，所需要的平均时间是O(nlog2n)。√4．对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)。╳5．对于n个记录的集合进行快速排序，所需要的平均时间是O(n)。╳6．堆排序所需的时间与待排序的记录个数无关。三、填空题102 1．对于n个记录的集合进行归并排序，所需的附加空间为___O(n)__。2．设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、起泡排序、归并排序进行递增排序，则__起泡排序_最节省时间，__快速排序__最费时间。对快速排序来讲，其最好情况下的时间复杂度为__O(nlog2n)____，最坏情况下的时间复杂度为___O(n2)____。3．目前以比较为基础的内部排序的时间复杂度T(n)的范围是_O(nlog2n)~O(n2)___，其比较次数与待排序的记录的初始状态无关的是_归并排序、直接选择排序__。4．在内部排序中要求附加的内存容量最大的是_快速排序、归并排序___，排序时不稳定的是___选择排序、起泡排序、快速排序、堆排序____。5．从时间上看，快速排序的平均性能优于其它排序方法，但从空间上看，快速排序需要一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度接近的两个序列，则栈的最大深度为__log2n___；在最坏情况下，栈的深度为__n-1__。6．堆的形状是一棵___完全二叉树__。7．若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是_稳定__的，否则称为___不稳定__的。102 8．按照排序过程涉及的存储设备的不同，排序可分为__内部__排序和__外部_排序。9．直接插入排序是稳定的，它的时间复杂度为_O(n2)__，空间复杂度为__O(1)__。10．归并排序要求待排序列由若干个___有序___的子序列组成。11．2-路归并排序的时间复杂度是___O(nlog2n)____。12．在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较__3_次。13．在堆排序和快速排序中，若原始记录接近正序和反序，则选用__堆排序___；若原始记录无序，则最好选用____快速排序__。14．在插入排序和选择排序中，若初始数据基本正序，则选用____插入排序___；若初始数据基本反序，则选用__选择排序__。四、应用题1．一组关键字(19，01，26，92，87，11，43，87，21)，进行起泡排序，试列出每一趟排序后的关键字序列，并统计每趟排序所进行的关键字比较次数。答：略。2．对上题给出的关键字序列，进行选择排序，列出每一趟排序后的关键字序列，并统计每趟排序所进行的关键字比较次数。答：略。102 3．从快速排序法的基本原理不难看出，对n个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。(1)试问：当n=7时，在最好情况下需进行多少次比较?说明理由。(2)对n=7给出一个最好情况的初始排列的实例。答：(1)当n=7，k(3趟划分)=3时，在最好情况下，第一趟6次比较，第二趟各需2次比较，共10次比较即可。(2)对n=7一个最好情况的初始排列：4，7，5，6，3，1，2。4．对下列一组关键字(46，58，15，45，90，18，10，62)，试写出快速排序的每一趟的排序结果，并标出第一趟中各元素的移动方向。答：略。5．判断以下序列是否为堆，若不是，则调整为堆。(1)(97，86，48，73，35，39，42，57，66，20)(2)(12，70，33，65，24，56，48，92，86，31)(3)(103，97，56，38，66，23，42，12，30，52，06，20)(4)(05，56，20，23，40，38，29，61，35，76，28，99)答：(1)、(3)、是大根堆；(2)不是堆，调整为小堆（12，24，33，65，31，56，48，92，86，70）；(4)不是堆，调整为小堆（05，23，20，35，28，38，29，61，56，76，40，99）102 6．设有5000个无序的元素，希望用最快的速度挑选出前10个大元素。请说明哪种算法最好，并说明理由。答：采用堆排序。7．用图示给出关键字序列(92，37，86，33，12，57，25)初始建堆和输出前两个最小关键字后重建堆的过程。答：略。操作系统练习题参考答案(一)单项选择题B1.操作系统是计算机系统的一种()。A．应用软件B．系统软件c．通用软件D．工具软件D2．操作系统目的是提供一个供其他程序执行的良好环境，因此它必须使计算机()A.使用方便B．高效工作C.合理使用资源D．使用方便并高效工作A3．允许多个用户以交互方式使用计算机的操作系统是()。A．分时操作系统B．批处理单道系统C．实时操作系统D．批处理多道系统C4．下列系统中()是实时系统。A．计算机激光照排系统B．办公自动化系统C.化学反应堆控制系统D．计算机辅助设计系统D5．操作系统是一种系统软件，它()。102 A．控制程序的执行B．管理计算机系统的资源C.方便用户使用计算机D．管理计算机系统的资源和控制程序的执行C6．计算机系统把进行()和控制程序执行的功能集中组成一种软件，称为操作系统A．CPU管理B．作业管理C．资源管理D．设备管理D7．批处理操作系统提高了计算机系统的工作效率，但()。A.不能自动选择作业执行B．无法协调资源分配c．不能缩短作业执行时间D在作业执行时用户不能直接干预B8．分时操作系统适用于()。A．控制生产流水线B．调试运行程序c．大量的数据处理D．多个计算机资源共享C9．在混合型操作系统中，“前台”作业往往是指()。A．由批量单道系统控制的作业B．由批量多道系统控制的作业c．由分时系统控制的作业D．由实时系统控制的作业B10.在批处理兼分时的系统中，对()应该及时响应，使用户满意。A．批量作业B.前台作业c．后台作业D．网络通信C11．实时操作系统对可靠性和安全性要求极高，它()。A．十分注重系统资源的利用率B．不强调响应速度c．不强求系统资源的利用率D．不必向用户反馈信息102 D12．分布式操作系统与网络操作系统本质上的不同之处在于()。A．实现各台计算机之间的通信B．共享网络个的资源c．满足较大规模的应用D．系统中若干台计算机相互协作完成同一任务B13．()为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。A处理器管理B．存储管理c．文件管理D．作业管理A14．在现代计算机系统层次结构中，最内层是硬件,最外层是使用计算机的人，人与硬件之间是()。A．软件系统B．操作系统c．支援软件D．应用软件B15.财务管理软件是一种专用程序,它属于()A．系统软件B．应用软件c接口软件D．支援软件C16.在多道程序设计技术的计算机系统中，中央处理器()。A.只能被一个程序占用B．可以被多个程序同时占用c．可以被多个程序交替占用D．可以被操作系统和另一个程序同时占用D17．()不是一种永久性的存储设备，当电源被切断时，其中的信息就会消失。A．硬盘B.磁带c.软盘D.主存储器Cl8．中央处理器可以直接存取()中的信息。A．光盘B．软盘c．主存储器D．硬盘102 B19．中央处理器存取寄存器中信息的速度与使用主存储器和辅存储器信息相比()。A.比较快B.最快c.差不多D．最慢D20．存放在()信息只能顺序存取，无法随机访问。A．硬盘B．软盘c．光盘D．磁带(二)填空题1．计算机系统是按用户要求接收和存储信息，自动进行___数据处理____并输出结果信息的系统。2.计算机是由硬件系统和__软件_系统组成。3．软件系统由各种__程序__和数据组成。4．计算机系统把进行_资源管理_和控制程序执行的功能集中组成一种软件称为操作系统。5．操作系统使用户合理__共享资源__，防止各用户间相互干扰。6．使计算机系统使用方便和__高效地工作_是操作系统的两个主要设计目标。7．批处理操作系统、__分时操作系统_和实时操作系统是基本的操作系统。8．用户要求计算机系统中进行处理的一个计算机问题称为__作业__。9．批处理操作系统按照预先写好的__作业说明书__控制作业的执行。10．在多道操作系统控制下，允许多个作业同时装入__主存储器___，使中央处理器轮流地执行各个作业。102 11．批处理操作系统提高了计算机系统的__工作效率__，但在作业执行时用户不能直接干预作业的执行。12．在分时系统中，每个终端用户每次可以使用一个由__时间片__规定的cPu时间。13分时系统具有同时性、独立性、及时性和__交互性___等特点。14．在批处理兼分时系统中，往往把由分时系统控制的作业称为__前台__作业，把由批处理系统控制的作业称为__后台__作业。l5．实时系统要求有__高可靠性和安全性__,不强求系统资源的利用率。(三)简答题1.什么是计算机系统?它由哪几部分组成?计算机系统是按用户的要求接收和存储信息，自动进行数据处理并输出结果信息的系统。计算机系统由硬件系统和软件系统组成。硬件系统是计算机系统赖以工作的实体，软件系统保证计算机系统按用户指定的要求协调地工作。2．计算机系统的资源包括哪些?计算机系统的资源包括两大类:硬件资源和软件资源。硬件资源主要有中央处理器、主存储器、辅助存储器和各种输入输出设备。软件资源有编译程序、编辑程序等各种程序以及有关数据。3.简述操作系统的定义。102 操作系统是计算机系统的一种系统软件，它统一管理计算机系统的资源和控制程序的执行。4．为计算机设计操作系统要达到什么目的?设计时应考虑哪些目标?操作系统是一种系统程序，其目的是为其他程序的执行提供一个良好的环境。它有两个主要设计目标：一是使计算机系统使用方便，二是使计算机系统能高效地工作。5．从操作系统提供的服务出发，操作系统可分哪几类?从操作系统提供的服务出发，操作系统可分为：批处理操作系统、分时操作系统、实时操作系统、网络操作系统和分布式操作系统。6．简述操作系统的五大功能。从资源管理的观点出发，操作系统具有五大功能：(1)处理器管理。为用户合理分配处理器时间，提高处理器工作效率。(2)存储管理。为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。(3)文件管理。管理用户信息，为用户提供按文件名存取功能，合理分配文件的存储空间。(4)设备管现。负责设备的分配、启动以及虚拟设备的实现等.(5)作业管理。实现作业调度和控制。102'