《数据结构(第二版)习题库章节练习题1-9章全》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
第一章绪论一．填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的_____________以及它们之间的_________和操作等的学科。2.数据结构包括数据的_____________结构、_____________结构和运算。3.数据的物理结构被分为_________、________、__________和___________四种。4.数据的逻辑结构是指数据元素之间的逻辑关系，根据数据元素之间关系的不同特性，逻辑结构通常有_______________，________________，________________和__________________四类基本结构。5.一种抽象数据类型包括____________和_____________两个部分。6.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为____________当结点之间存在1对N（1：N）的联系时，称这种结构为____________。7.数据结构被形式地定义为（D,R），其中D是___________的有限集合，R是D上的有限集合。8.数据的基本单位是________，它在计算机中是作为一个整体来处理的。9.算法的特性有________，___________，____________，_______________和__________等五种特性。10.通常从四个方面评价算法的质量：_________、_________、_________和_________。11.算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。12.算法的效率可分为______________效率和__________________效率。13.算法的时间复杂度为(3n3+2000nlog2n+90)/n2，其数量级表示为________。14.下面程序段的时间复杂度为____________。for(inti=0;i
1，4>，<4，1>}，则数据结构A是__________。A、线性结构B、树型结构C、图型结构D、集合10．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是__________。A、线性结构B、树型结构C、物理结构D、图型结构11.对一个算法的评价，不包括如下__________方面的内容。A、健壮性和可读性B、并行性C、正确性D、时空复杂度12.算法的五个重要特性是________？A、可执行性、可移植性、可扩充性、输入和输出。B、可行性、确定性、有穷性、输入和输出。C、确定性、有穷性、稳定性、输入和输出。D、可执行性、可移植性、可扩充性、输入和输出。13．算法分析的两个方面是________。A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性14.算法分析的目的是__________？A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档性15.以下算法的空间复杂度是__________。#include#definen10cout(intA[]){intB[n],i;for(i=0;i
2for(i=1;i<=m;++i)for(j=1;j<=n;++j)c[i][j]=0;A、O(n)B、O(m+2n)C、O(m+n)D、O(m*n)19．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（）。A、O(n)B、O(nlog2n)C、O(n2)D、O(n/2)20．下列程序段的时间复杂度为__________。for(i=0；i
3数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。6.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。7.设有数据结构(D,R)，其中，，试按图论中图的画法惯例画出其逻辑结构图。解：8.设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：(1)i=1;k=0;while(i<=n-1){@k+=10*i;i++;}(2)i=1;k=0;do{@k+=10*i;i++;}while(i<=n-1);(3)i=1;k=0;while(i<=n-1){i++;@k+=10*i;}(4)k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;}(5)for(i=1;i<=n;i++){for(j=1;j<=i;j++){for(k=1;k<=j;k++)@x+=delta;
4}(6)i=1;j=0;while(i+j<=n){@if(i>j)j++;elsei++;}(7)x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}(8)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;}解：(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+...+1=(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)===(6)n(7)向下取整(8)1100五、程序算法题1.设n为整数，求下列各程序段的时间复杂度（1）i=1;k=2;While(i
5While(y>0)If(x>100){x=x-10;y=y-1;}elsex=x+1;2.试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值解：intmax3(intx,inty,intz){if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;}第二章线性表一、选择题1．线性表是具有n个__C___的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项2．一个顺序表所占用的存储空间大小与___B___无关。A．表的长度B．元素的存放顺序C．元素的类型D．元素中各字段的类型3．线性表的顺序存储结构是一种__A___。A．随机存取的存储方式B．顺序存取的存储方式C．索引存取的存储方式D．Hash存取的存储方式4.若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则第12个元素的存储地址是__B____。A．112B.144C.148D.4125.线性表是__A____。A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空
66．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。A．O（n）O（n）B．O（n）O（1）C．O（1）O（n）D．O（1）O(1)7．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中___A____中数据元素。A．n-iB．n+iC．n-i+1D．n-i-18．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____C____个元素。A.n/2B.（n+1）/2C.（n-1）/2D.n9．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为__C____。（1≤i≤n+1）A．O（0）B．O（1）C．O（n）D．O（n2）10．线性表中各链接点之间的地址___C____。A．必须连续B．部分地址必须连续C．不一定连续D．连续与否无所谓11．在n个结点的线性表的数组表示中，算法的时间复杂度是O（1）的操作是_A______。A．访问第i个结点后插入一个新结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．以上都不对12．单链表中，增加一个头结点的目的是为了____C_____。A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储13．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_B____。A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL
714．将长度为n的单链表链接在长度为m的单链表后面的算法的时间复杂度采用大O形式表示应该是___C____。A．O（1）B．O（n）C．O（m）D．O（n+m）15．静态链表中指针表示的是___C____。A．下一个元素的地址B．内存储器的地址C．下一个元素在数组中的位置D．左链或右链指向的元素的地址16．非空的循环单链表head的尾结点p满足__A______。A．P->link=headB．P->link=NULLC．P=NULLD．P=head17．某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next==head成立时，线性表的长度是___B____。A．0B．1C．2D．318．在什么情况下，应使用链式结构存储线性表L?___B____A．需经常修改L中的结点值B．需不断对L进行删除插入C．需要经常查询L中的结点值D．L中结点结构复杂19．与单链表相比较，双向链表的优点之一是___D_____。A．可以省略头结点指针B．可以随机访问C．插入、删除操作更简单D．顺序访问相邻结点更灵活20．某线性表常发生的操作为删除第一个数据元素和最后一个元素后添加新元素，采用__D__作为存储结构，能使其存储效率和时间效率最高。A．单链表B．仅用头指针的循环单链表C．双向循环链表D．仅用尾指针的循环单链表21．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用_D___存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表22．对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够反映数据之间的逻辑关系，则应用___C____。A．顺序方式存储B．散列方式存储C．链接方式存储D．以上方式均可23．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用___A___存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
824．若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式为___D_____。A．单链表B．双向链表C．单循环链表D．顺序表25．下面哪一条是顺序存储结构的优点？___C______A．插入运算方便B．可方便地用于各种逻辑结构的存储表示C．存储密度大D．删除运算方便26．下面关于线性表的叙述中，错误的是___B_____。A.线性表采用顺序存储，必须占用一批连续的存储单元B.线性表采用顺序存储，便于进行插入和删除的操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作27．在非空线性链表中由p所指的链接点后面插入一个由q所指的链接点的过程是依次执行动作__B____。A．q->link=p；p->link=q；B．q-link=p->link；p->link=q；C．q->link=p->link；p=q；D．p->link=q；q->link=p；26．在非空双向循环链表中由q所指的链接点前面插入一个由p指的链接点的过程是依次执行语句p->rlink=q；p->llink=q->llink;q->llink=p;____D____。A．q->rlink->llink=p;B．q->llink->rlink=p;C．p->rlink->llink=p;D．p->llink->rlink=p;29．在非空双向循环链表中由q所指的链接点后面插入一个由p指的链接点的动作依次为__D____。A．p->llink=q;p->rlink=q->rlink;q->rlink=p;q->rlink->llink=p；B．p->rlink=q->rlink;p->llink=q;q->rlink;q->rlink->llink=p；C．p->llink=q;p->rlink=q->rlink;q->rlink=p;p->llink->rlink=p；D．p->llink=q;p->rlink=q->rlink;q->rlink=p;p->rlink->llink=p；30．在双向链表存储结构中，删除p所指的结点时须修改指针__A____。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlink;
9D．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;31．单链表的存储密度为__C____。A．大于1B．等于5C．小于1D．不能确定二．判断题1.线性表的逻辑顺序与存储顺序总是一致的。（）2.线性表的顺序存储结构比链式存储结构更好。（）3.线性表中的所有元素都有一个前驱元素和后继元素。（）4.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）5.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）6.非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）7.用一组地址连续的存储单元存放的元素一定构成线性表。（）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）9.顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）10.顺序表中所有结点的类型必须相同。（）11.对链表进行插入和删除操作时不必移动链表中结点。（）12.非空的双向循环链表中任何结点的前驱指针均不为空。（）13.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。（）14.单链表从任何一个结点出发，都能访问到所有结点。（）15.符号p->next出现在表达式中表示p所指的那个结点的内容。（）16.带表头结点的双向循环链表判空的条件是：first->rlink==first（first为表头指针）。（）三、综合应用题1.利用顺序表的操作，实现以下函数：1）从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2）从顺序表中删除第i个元素并由函数返回被删除元素的值，如果i不合理或顺序表为空则显示出错信息并退出运行。3）向顺序表中第i个位置插入一个新元素x。如果i不合理则显示出错信息并退出运行
104）从顺序表中删除具有给定值x的所有元素。5）从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。如果s或t不合理或者顺序表为空，则显示错误信息并退出。6）从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空，则显示错误信息并退出。7）将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表8）从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。2.请设计算法将不带头结点的单链表就地逆置。3.有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。4.设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：找出最小值结点，且打印该数值。若该数值是奇数，则将其与直接后继结点的数值交换。若该数值是偶数，则将其直接后继结点删除。5.给定（已生成）一个带表头结点的单链表，设head为头指针，结点的结构为（data，next），data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。6.假设有两个按元素值递增次序排列的线性表，并要求利用原来两个单链表的结点存放归并后的单链表。7.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7,10,10,21,30,42,42,42,51,70）将变为（7,10,21,30,42,51,70）。8.试编写在带头结点的单链表中删除一个最小值结点的高效算法：voiddelete(Linklist&L)。
119.已知两个单链表A和B，其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。10.已知非空线性表由list指出，链结点的构造为（data，link）。请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面（要求：不得额外申请新的链结点）。11.带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合，两表中的元素皆为递增有序。请写一算法求A和B的并集AUB，要求该并集中的元素仍保持递增有序，且要利用A和B的原有结点空间。12.已知两个链表A和B分别表示两个集合，其元素递增排列。编写一函数程序，求A与B的交集，并存放于A链表中。13.设计一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A、B集合中的元素按递增排列，C为空；操作完成后，A、B保持不变，C中元素按递增排列。下面的函数append（last，e）是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕后，再删除并释放表示结果集合的链表的表头结点。typedefstructnode{intelement;structnode*link;}NODE;;NODE*A,*B,*C;NODE*append(NODE*last,inte){last->link=(NODE*)malloc(sizeof(NODE));last->link->element=e;return(last->link);}NODE*difference(NODE*A,NODE*B){
12………}14.设一单向链表的头指针为head，链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照key递增的次序进行就地排序。15.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于等于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。16.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。1）写出其类型定义。2）写出算法。17.两个整数序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。18.已知线性表（a1，a2，a3，…，an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值（假设0为正数）元素前边的算法。例如：（x，-x，-x,x,x,-x,…,x）变为（-x,-x,-x,…,x,x,x）。19.一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next。现对链表求一阶导数，链表的头指针为ha，头结点的exp域为-1。20．设用带头结点的双向循环链表表示的线性表为L=（a1，a2,a3,…,an）。写出算法将L改造成：L=（a1,a3,…,an,…,a4,a2）.结点和结点指针类型定义如下：typedefstructnode{ElemTypedata;Structnode*prior,next;}*DLinkList;
1321.设有一个头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针）、data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate（L，x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate（L，x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。第三章栈和队列一．选择题1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为。A．top不变B．top＝top-nC．top＝top-1D．top=top+12.在一个顺序存储的循环队列中，队首指针指向队首元素的。A．前一个位置B．后一个位置C．队首元素位置D．队尾元素位置3.若进栈序列为1,2,3,4,栈过程中可以出栈，则不可能是一个出栈序列。A．3,4,2,1B．2,4,3,1C．1,4,2,3D．3,2,1,44.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是。A．front==rear+1B．front+1==rearC．front==rearD．front==05.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行。A．hs->next=s;B．s->next=hs->next;hs->next=s;C．s->next=hs;hs=s;D．s->next=hs;hs=hs->next;6.下列说法哪个正确：_______A．堆栈是在两端操作、先进后出的线性表B．堆栈是在一端操作、先进先出的线性表C．队列是在一端操作、先进先出的线性表D．队列是在两端操作、先进先出的线性表7.栈和队列的共同点_______A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点8.以下数据结构中哪一个是非线性结构？_______A．队列B．栈C．线性表D．二叉树9.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_______A．iB．n=iC．n-i+1D．不确定10.当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_______语句修改top指针。A．top++B．top--C．top=0D．top11.4个元素进S栈的顺序是A,B,C,D,经运算POP(S)后栈顶元素是_______
14A．AB．BC．CD．D12.一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是_______A.edcbaB.decbaC.dceabD.abcde13．设用链表作为栈的存储结构则退栈操作_______。A．必须判别栈是否为满B．必须判别栈是否为空C．判别栈元素的类型D．对栈不作任何判别14．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是_______。A．n-iB．n-1-iC．n+1-iD．不能确定15．递归函数f(n)=f(n-1)十n(n>1)的递归出口是_______。A．f(1)=0B．f(1)=1C．f(0)=1D．f(n)=n16．中缀表达式A-(B+C／D)*E的后缀形式是_______。A．ABC+D／*E-B．ABCD／+E*-C．AB-C+D／E*D．ABC-+D/E*17.字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_______个不同的字符串？A.15B.14C.16D.2118.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_______个不同的字符串？A.14B.5C.6D.819．判定一个循环队列QU(最多元素为m0)为满队列的条件是_______A．QU->front==QU->rearB．QU->front!=QU->rearC．QU->front==(QU->rear+1)％m0D．QU->front!=(QU->rear+1)％m020.以下哪一个不是队列的基本运算？_______A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值21．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是_______。A．6B．4C．3D．222.用链接方式存储的队列，在进行插入运算时_______。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改23.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为_______？A.1和5B.2和4C.4和2D.5和124．将一个递归算法改为对应的非递归算法时，通常需要使用_______。A.栈B.队列C.循环队列D.优先队列25．在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是_______。A.(front-rear+1)%mB.(rear-front+1)%mC．(front-rear+m)%mD.(rear-front+m)%m二．填空题1.栈和队列分别称为_____________的线性表。
152.栈结构允许进行删除操作的一端为_____________。3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________；删除一个结点时，需要执行的操作是______________________________（假设栈不空而且无需回收被删除结点）。4.向量、栈和队列都是__________结构，可以在向量的__________位置插入和删除元素；对于栈只能在____________插入和删除元素；对于队列只能在________插入和_______删除元素。5.栈是一种特殊的线性表，允许插入和删除运算的一端称为___________。不允许插入和删除运算的一端称为_____________。6.栈又称为_______________表，队列又称为___________表。7.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是_____________________。8.设输入序列为1、2、3，则经过栈的作用后可以得到_____种不同的输出序列。9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。10.(a+b)*c+(e*f-h)/(q+r)+3的后缀表达式为__________________________。11.后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。三．判断题1.栈是一种线性结构。（）2.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）3.栈是一种插入和删除操作在表的一端进行的线性表。（）4.出栈序列为abcd，则入栈序列可能是bcda。（）5.一个栈的输入序列是12345，则栈的输出序列不可能是12345。（）6.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）7.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）8.栈和队列的存储方式既可是顺序方式，也可是链接方式。（）9.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）10.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）11.高级语言中通常利用“递归工作栈”来处理递归。（）四、简答题1.简述栈与队列的相同点与不同点。2.在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列常都采用循环队列结构？3.写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;
16charx,y;InitStack(S);x=‘c’;y=‘k’;Push(S,x);Push(S,‘a’);Push(S,y);Pop(S,x);Push(S,‘t’);Push(S,x);Pop(S,x);Push(S,‘s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}4.简述以下算法的功能（栈的元素类型SElemType为int）。(1)statusalgo1(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}(2)statusalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}五．程序算法题1.设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针），试编写相应的入队列、出队列算法。2.设计一个输出如下形式数值的递归算法。
174444333223.试证明：若借助栈由输入序列12…n得到的输出序列为(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i 18A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符7.设有两个串p和q，求q在p中首次出现的位置的运算称作________。A．连接B．模式匹配C．求子串D．求串长8.设串s1="ABCDEFG",s2="PQRST",函数con(x,y)返回x和y串的连接串。subs(s，i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2))的结果串是________。A．BCDEFB．BCDEFGC．BCPQRSTD.BCDEFEF9．函数substr("DATASTRUCTURE"，5，9)的返回值为________。A．"STRUCTURE"B．"DATA"C．"ASTRUCTUR"D."DATASTRUCTURE"10．设串S="IAMATEACHER",其长度是________。A.16B.11C.14D.1511.设字符串s1="abcdefg",s2="pqrst"，则运算s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为________。A."bcdef"B."bcdefg"C."bcpqrst"D."bcdefef"1312.设有一个字符串S="windows"，求子串的数目是________。A．25B．26C．27D.28二.填空题1._______________称为空串；_______________________称为空白串。2.一个串的任意个连续的字符组成的子序列称为该串的______，包含该子串的串称为____。三．简答题1．空串与空格串有什么区别？字符串中的空格有什么意思？空串在串的处理中有什么作用？2．串是由字符组成的，长度为1的串和字符是否相同？为什么？3．简述串的静态顺序存储结构与动态顺序存储结构有什么区别，分别写出它们的结构体定义。4．字符串采用静态顺序存储结构。编写一个算法删除S中第i个字符到第j个字符。5．编写一个算法判断s2是否是s1的子串。6.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。intindex(chars[],chart[]){inti=0,j=0;while(i 19{i=_______;j=______;}if(j==strlen(t))return(i-strlen(t));elsereturn(-1);}第五章数组和广义表一．选择题1．在二维数组A中引用A[i,j]的时间_________。A．与i、j的大小有关B．与i、j的大小无关C．与i的大小有关，与j的大小无关D．与i的大小无关，与j的大小有关2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。A．行号B．列号C．元素值D.地址3．二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。A．470B．471C．472D.4734．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。A．行号B．列号C．元素值D.地址5．下面的说法中，不正确的是________。A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。A．表达变得简单B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销7．若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了________个数组元素。A．n2B．n*(n-1)C．n*(n+1)／2D．n*(n-1)8.稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。A.行号B.列号C.元素值D.元素总数9．稀疏矩阵一般的压缩存储方法有两种，即________。A．二维数组和三维数组B．三元组和散列C.三元组和十字链表D．散列和十字链表10．有一个10阶对称矩阵A，采用压缩存储方式(以行序为主存储，且A[0Ⅱ0]=1)，则A[8][5]的地址是________。 20A．52B．48C．54D．5311.数组通常具有的两种基本操作是________。A．建立与删除B．索引和修改C．查找和修改D．查找与索引12．二维数组M的成员是6个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节。A．90B．180C．240D．54013．二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5,M按行存储时元素M[3Ⅱ5]的起始地址与M按列存储时元素________的起始地址相同。A．M[2][4]B．M[3][4]C．M[3][5]D.M[4][4]14．下面的说法中，不正确的是________。A．数组是一种线性表结构B．数组是一种定长的线性表结构，C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D．数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作15．数组的逻辑结构不同于下列________的逻辑结构。A．线性表B．栈C．队列D.树16．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为________。A．10B．19C．28D.5517．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为________。A．100B．40C．55D.8018．设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按行序放在一维数组B[1，n(n+1)/2]中。下三角部分中任一元素Aij(i>=j),在一维数组B中的下标位置是________。A．i(i-1)/2+j-1B．i(i-1)/2+jC．i(i+1)/2+j-1D.i(i+1)/2+j19.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为________。A．356B．358C．360D.36220.二维数组Amn按行序为主序存放在内,每个数组元素占1个存储单元,则元素Aij的地址计算公式是:________。A．loc(Aij)=loc(A11)+[(i-1)*m+(j-1)]B．loc(Aij)=loc(A11)+[(j-1)*m+(i-1)]C．loc(Aij)=loc(A11)+[(i-1)*n+(j-1)]D.loc(Aij)=loc(A11)+[(j-1)*n+(i-1)]21.广义表(a,b,c,d)的表头是________。.A．aB．(a)C．a,b,cD.(a,b,c)22.若广义表K满足head(K)=tail(K),则K为________。A.()B.(())C.(()),(())D.((),(),())23.设一个广义表中结点的个数为n,则广义表深度算法的时间复杂度为 21________。A.O(1)B.O(n)C.O(n2)D.O(log2n)24.下列广义表中，深度为2的有________。A.(a，b)B.((c，(a，b))，d)C.(c，(a，b))D.((a，b)，(c，(a，b)))25.广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为________。A.(g)B.(d)C.cD.d二.填空题1.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)/2个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。2．数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址100开始连续存放在存储器内，该数组若按行主序存放时，元素A[8][5]的起始地址为________；该数组若按列主序存放时，元素A[8][5]的起始地址为__________。3.假设有二维数组A[6][8]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为________；末尾元素A57的第一个字节地址为________；若按行存储时，元素A14的第一个字节地址为_________；若按列存储时，元素A47的第一个字节地址为__________。4.若一个n阶矩阵A中的元素满足：Aij=Aji(0<=i,j<=n-1)则称A为________矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为__________。5.已知广义表A=((a,b,c),(d,e,f)),则运算head(head(tail(A)))=________。6.一个广义表中的元素分为________元素和________元素两类。7.稀疏矩阵中第2行3列的元素值是5，它的三元组是________。8.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________为辅序的次序排列。9.广义表A=(a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。10．设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为____________。11．设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为___________。12.二维数组在内存中存储可以有两种存储方式，一种是_____优先存储，一种是________优先存储。13.设广义表L＝(（），（），（（））)。则head(L)是________；tail(L)是________；L的长度是________；L的深度是________。14.设广义表L＝(（a），（b），（（c））)则head(L)是______；tail(L)是___。三.判断题1.在C语言中，多维数组的存储采取的是行优先的方式。（）2.广义表在本质上也是线性表。（） 223.可以用三元组存储法来压缩存储稀疏矩阵。（）4.已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。（）5.二维数组和多维数组均不是特殊的线性结构。（）6.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。（）7.多维数组元素之间的关系是线性的。（）8.数组可以看作是二元组<下标，值>的一个集合。（）9.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（）10.一个广义表的表尾总是一个广义表。（）四.简答题1．什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？2．什么样的矩阵叫特殊矩阵？特殊矩阵压缩存储的基本思想是什么？3．什么样的矩阵叫稀疏矩阵？稀疏矩阵压缩存储的基本思想是什么？4．已知稀疏矩阵如下：请写出该稀疏矩阵三元组表示。5.请写出下面链表表示的广义表。6.画出广义表list=(5,(3,2,(14,9,3),(),4),2,(6,3,10))的链表表示。五.程序设计题 231.设计一个算法求广义表的深度。2.若矩阵A[m][n]中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有鞍点。3．对于二维数组A[m][n]，其中m<=50，n<=50，先读入m和n，然后读该数组的全部元素，对如下三种情况分别编写相应函数：（1）求数组A靠边元素之和；（2）求从A[0][0]开始的互不相邻的各元素之和；（3）当m==n时，分别求两条对角线上的元素之和，否则打印出m!=n的信息。第六章树一、选择题1．对于一棵具有n个结点的树，该树中所有结点的度数之和为________。A．n-1B.nC.n+1D.(n+1)/22．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为________。A．3B.4C.5D.13．根据二叉树的定义可知二叉树共有________种不同的形态。A．4B.5C.6D.74．在一棵树中，________没有前驱结点。A.分支结点B.叶结点C.树根结点D.空结点5．设某棵二叉树中只有度数为0和度数为2的结点,且度数为0的结点数为n，则这棵二叉中共有________个结点。A．2nB.n+1C.2n-1D.2n+16．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有________。A．20B.256C.512D.10247.一棵具有5层满二叉树中结点总数为________。A．31B.32C.33D.168.如下图所示的4棵二叉树，_______不是完全二叉树。9.具有65个结点的完全二叉树的高度为________。(根的层次号为1) 24A.8B.7C.6D.510.把一棵深度4的左单支二叉树改造成完全二叉树时，要增添个空结点。A．10B．8C．6D．411.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为________。A．2i+1B.2iC.i/2D.2i-112.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为________。A.前序遍历B.后序遍历C.中序遍历D.层次遍历13.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为________。A．CBEFDAB.FEDCBAC.CBEDFAD.不定14.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是________。A．acbedB．decabC．deabcD．cedba15.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,…,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按编号。A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次遍历序列16.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是________的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子17.由前序序列和中序序列________唯一确定一棵二叉树。A．能B.不能C.不一定18.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是________。 25A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D．以上都不对19.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为2n个，其中________个用于指向孩子结点。A．n-1B.nC.n+1D.n-220.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为________。A．N1-1B.N2-1C.N2+N3D.N1+N321.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_____。A.23B.37C.44D.4622.n个权构成一棵Huffman树，其结点总数为__________。A．2n-1B.2nC.2n+1D.不确定二、填空题1.在一棵二叉树中，度为0的结点的个数为n0，度为2的结点的个数为n2，则：n0=。2．结点数为7的二叉树的高度最矮是_______，最高是_______。3．给定二叉树的结点数，要使树高为最大，那么该树应该是_______形状。4．给定二叉树的结点数，要使树高为最矮，那么该树应该是_______形状。5．如果一棵满二叉树的深度为7，那么它共有_______个结点，有_______个叶结点。6．深度为5的二叉树，至多有_______个结点。7．深度为k的完全二叉树至少有_______个结点，至多有_______个结点。8．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有_______个前驱结点，叶子结点没有后继结点，其余每个结点的后继结点可以有_______个。 269.设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点。10.设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是___________________________。11.在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为________。12.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是_____，编号为8的左孩子结点的编号是_______。13.设哈夫曼树中共有n个结点，则该哈夫曼树中有_____个度数为1的结点。14.以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树为____，其带权路径长度为_________。15.设一棵Huffman树有6个叶结点，权值分别为3、4、7、14、15、20，则根结点的权值是_______。16.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_________。三、综合应用题1.已知一棵树的边的集合表示为{（L,N）,（G,K）,（G,L）,（G,M）,（B,E）,（B,F）,（D,G）,（D,H）,（D,I）,（D,J）,（A,B）,（A,C）,（A,D）}。画出这棵树并回答下面问题：（1）树的根节点是哪个，哪些是叶子结点，哪些是非终端结点。（2）树的深度是多少，各个结点的层数是多少。（3）对于G结点，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点。2.设二叉树如下图所示，分别写出它的先序遍历、中序遍历、后序遍历序列。ABECFGDHIJ 273.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。4.某二叉树结点的中序序列为HBCDEFG，后序序列为BDCHFGE，请据此画出该二叉树，再给该树加上中序线索。5.请按照孩子-兄弟表示法，将下图所示树转化为二叉树。ACBDEFG6.若7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），计算出带权路径长度WPL及该树的结点总数。7.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：（1）什么是哈夫曼树？（2）根据题目所给频率值，画出相应的哈夫曼树。（3）给出各个字符对应的哈夫曼编码。（4）该段文字经过哈夫曼编码后，长度是多少。四、算法设计题1.设计一个求结点x在二叉树中的双亲结点的算法。 282. 设计判断两个二叉树是否相同的算法。3. 设计计算二叉树中所有结点值之和的算法。4.设计求二叉树中值为x的结点所在的层号的算法。第七章图一．选择题1．任何一个无向连通图的最小生成树________。A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在2．下列算法中，________算法用来求图中每对顶点之间的最短路径。A．DijkstraB．FloyedC．PrimD．Kruskal3．由N个顶点组成的有向图，最多可以有________条边。A．N*NB．N（N+1）C．N（N-1）D．N(N-1)/24．关键路径是结点网络中________。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路5．在一个图中，所有顶点的度数之和等于所有边数的________倍。A．2B．3C．1D．1.56.下面关于图的存储的叙述中正确的是________。A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关7.AOV网是一种________。A．有向图B．无向图C．无向无环图D．有向无环图8.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有________条边。A．n+2B．n(n-1)C．n2D．2n9.设完全无向图中有n个顶点，则该完全无向图中有________条边。A．n(n-1)/2B．n(n-1)C．n(n+1)/2D．(n-1)/210.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是________。A．1，2，3，4B．2，3，4，1C．1，4，2，3D．1，2，4，311.设某无向图有n个顶点，则该无向图的邻接表中有________个表头结点。A．2nB．nC．n/2D．n(n-1)12.设无向图G中有n个顶点，则该无向图的最小生成树上有________条边。A．nB．n-1C．2nD．2n-1 2913.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为________。A．aedfcbB．acfebdC．aebcfdD．aedfbc14.有n个顶点e条边的无向图G,它的邻接表中的表结点总数是________。A．2nB．nC．2eD．e15.连通图G中有n个顶点,G的生成树是________连通子图。A．包含G的所有顶点B．包含G的所有边C．不必包含G的所有顶点D．必须包含G的所有顶点和所有的边16.下面关于求关键路径的说法不正确的是________。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间同以该事件为尾的弧的活动最迟开始时间相同与该活动的持续时间的和D．关键活动一定在关键路径上17．设某强连通图中有n个顶点，则该强连通图中至少有________条边。A．n(n-1)B．n+1C．nD．n(n+1)18．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为________。A．nB．eC．2nD．2e19.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有________条有向边。A．nB．n-1C．mD．m-120．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为________。A．第i行非0元素的个数之和B．第i列非0元素的个数之和C．第i行0元素的个数之和D．第i列0元素的个数之和21．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为________。A．O(n+e)B．O(n2)C．O(ne)D．O(n)22．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的________。A．先序遍历B．中序遍历C．后序遍历D．按层遍历23.可以判断一个有向图中是否含有环（回路）的方法为________。A．广度优先遍历B．拓扑排序C．求最短路径D．求关键路径24.采用邻接表存储的图的深度优先遍历算法类似于二叉树的________。A．先序遍历B．中序遍历C．后序遍历D．按层遍历25.一个具有8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差为________。A．16B．8C．0D．226．在有向图中每个顶点的度等于该顶点的________。A.入度B.出度C.入度与出度之和D.入度与出度之差 30二．填空题1.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的________，对于有向图来说等于该顶点的________。2.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的顶点序列为________，按广度优先搜索遍历得到的顶点序列为________。ABCDEF┏011010┓A┃100011┃B┃100100┃C┃001001┃D┃110001┃E┗010110┛F3.有n个顶点的有向连通图最多有________条边，最少有________条边。4.具有n个顶点的完全无向图有________条边，完全有向图有________条边。5.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。6.设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。7.表示图的五种常用的存储结构为_______________________________。8.在有12个结点的无向图中，其边数最多为________条。9.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个边结点。10.n个顶点的连通图至少____条边。11.在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。12.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于____。13.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。14.在一个具有10个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。15.设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。16.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。17.设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。18.设无向图对应的邻接矩阵为A，则A中第i行上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。19.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。20.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。21.设无向图G中有n个顶点e 31条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。22.设某无向图G的邻接表为V1->3->2->4;V2->1->3;V3->1->2->4;V4->1->3;则从顶点V1开始的深度优先遍历序列为___________；广度优先遍历序列为____________。23.设有向图G的二元组形式表示为G=（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。24.AOV网以结点和有向边分别代表____________25.AOV网是一种___________________的图。三、判断题1.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）2.有向图的邻接表和逆邻接表中表结点的个数不一定相等。（）3.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。（）4.邻接矩阵表示图所用的存储空间大小与图的边数成正比。（）5.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（）6.n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。（）7.调用一次深度优先遍历可以访问到图中的所有顶点。（）8．带权无向图的最小生成树是唯一的。（）9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）10.对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）11.在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。（）四．简答题1．对于一个有向图，不用拓扑排序，如何判定图中是否存在环？2．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边数是否相关？3.无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。 324.设有无向图G（如右图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。5.设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。6.一个网络如下（1）求出从顶点1出发的一个广度优先搜索序列和一棵广度优先生成树。 33（2）求出它的一棵最小生成树并画出求解过程。7.已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示0100110010000110110110110（1）画出该图的图形；（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。8.已知一个图的顶点集V和边集E分别为：V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20};按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。9.已知一无向网A的邻接矩阵表示如下，请按要求回答下面的问题。其中：（1）试画出该网。（2）画出它的最小生成树五．算法设计题1.设计一个算法，求出无向图G的连通分量个数。2.假设图用邻接矩阵表示，设计一个算法，判定从顶点vi到顶点vj是否有路径。3.假设图用邻接表表示，设计一个算法，输出从指定顶点vi出发的所有简单回路。第八章查找一．选择题1．对长度为n的无序线性表进行顺序查找，则查找成功、不成功时的平均数据比较次数分别为_______。 34A．n/2,nB．(n+1)/2，n-1C．(n+1)/2，nD．(n-1)/2，n-12.设有一个文件有200个记录，按分块查找法查找记录，如分成10块，每块20个记录，用二分查找法查索引表，用顺序查找法查块内记录，则平均查找长度为________。A．8.4B．10.5C．13.4D．163.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做________次关键码比较。A.2B.3C.4D.54．一个有序表为{1，3，9，12，41，50，59，75，77，82，95，100}，利用折半查找查找关键字为82的结点时________次比较后查找成功。A.1B.2C.4D.85.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过________。A．log2n+1B．log2n-1C．log2nD．log2(n+1)6.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较____次。A．25B．10C．7D．17.折半查找要求查找表中各元素的关键字值必须是___________排列。A．递增或递减B．递增C．递减D．无序8.对线性表进行折半查找时，必须要求线性表________。A．以顺序方式存储B．以链接方式存储C．以顺序方式存储，且结点按关键字有序排列D．以链接方式存储，且结点按关键字有序排列9．顺序查找法适合于存储结构为________的线性表。A．散列存储B．顺序存储或链接存储C．压缩存储D．索引存储10．采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为________。A．nB．n/2C．(n-1)/2D．(n+1)/211.在二叉排序树中插入一个关键字值的平均时间复杂度为________。A．O(n)B．O(1og2n)C．O(nlog2n)D．O(n2)12．依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索树中，查找元素35要进行_____元素间的比较。A.4次B.5次C.7次D.10次13.二叉排序树中左子树上所有结点的值均________根结点的值。A． 35A．4B．5C．6D．716.在一个空AVL树内，依次插入关键字：49,94,91,47,92,45,89,42,87，当删除关键码时，如果该关键码同时具有左右子女，则以其中序后继替代，则删除关键码91时的旋转类型是__________。A.左单旋B.左右双旋C.右单旋D.其它情况17.在一棵m阶B-树中，若在某叶子结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_______。A.mB.m-1C.m/2ùD.m/2-118．对包含n个元素的散列表进行查找，平均查找长度________。A.O(log2n)B.O(n)C.不直接依赖于nD.上述三者都不是19.设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择________。A．小于等于m的最大奇数B．小于等于m的最大素数C．小于等于m的最大偶数D．小于等于m的最大合数20．设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择________。A．99B．97C．91D．9321.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做________次线性探测。A．n2B．n(n+1)C．n(n+1)/2D．n(n-1)/222.采用开放定址法处理散列表的冲突时，其平均查找长度________。A．低于链接法处理冲突B.高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找23.散列法存储的基本思想是根据A来决定B，碰撞（冲突）指的是C，处理碰撞的两类主要方法是D。供选择的答案：A，B：①存储地址②元素的符号③元素个数④关键码值⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间C:①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法③除余法和折叠法④拉链法和开地址法24._____是HASH查找的冲突处理方法。A．求余法B．平方取中法C．二分法D．开放地址法25.当α的值较小时，散列存储通常比其他存储方式具有________的查找速度。A.较慢B.较快C.相同26．当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度________。A．必定快B．不一定C．在大部分情况下要快D．取决于表递增还是递减27.当采用分块查找时，数据的组织方式为________。A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序C． 36数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D．数据分成若干块，每块（除最后一块外）中数据个数需相同28．对二叉排序树进行_________遍历，可以得到该二叉树所有结点构成的有序序列。A．前序 B．中序 C．后序 D．按层次29．一个哈希函数被认为是“好的”，如果它满足条件_________。A．哈希地址分布均匀B．保证不产生冲突C．所有哈希地址在表长范围内D．满足B和C30.哈希表的平均查找长度是__________的函数。A．哈希表的长度B．表中元素的多少C．哈希函数D．哈希表的装满程度31.平均查找长度最短的查找方法是____________。A．折半查找B．顺序查找C．哈希查找D．其他二.判断题1.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）2.中序遍历一棵二叉排序树可以得到一个有序的序列。（）3.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）4.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）5.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）6.在散列存储中，装填因子α越小，则发生冲突的可能性也越小。（）7.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）8.在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。（）9.对于折半查找，其前提条件是待查找序列只要是有序的即可。（）三．填空题1.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。2.以折半（或二分）查找方法从长度为8的有序表中查找一个元素时，平均查找长度为________。3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_______个，比较两次查找成功有结点数有_________个。4.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。5.假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为________，则比较二次查找成功的结点数为________，则比较三次查找成功的结点数为________，则比较四次查找成功的结点数为________，比较五次________查找成功的结点数为，平均查找长度为________。6.对于长度为n 37的线性表，若进行顺序查找，则时间复杂度为____；若采用二分法查找，则时间复杂度为________。7.根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为_________。8.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。9.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。10.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。11.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为____________，空间复杂度为___________。12.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度比原树的高度___________。13.Hash技术关键是________和________两个方面14.在散列存储中，装填因子a的值越大，则____；a的值越小，则____。15.在线性表的散列存储中，处理冲突的常用方法有_______和_______两种。四.简答题1.什么叫动态查找？什么叫静态查找？什么样的存储结构适宜于进行静态查找？什么样的存储结构适宜于进行动态查找？2．什么叫平均查找长度？写出平均查找长度的定义.3．输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。(1)按输入次序构造一棵二叉排序树（只要求画出最终二叉排序树）。(2)依此二叉排序树，如何得到一个从小到大的有序序列？4．若一棵排序二叉树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。5.已知一组关键字为{1,14,27,29,55,68,10,11,23}，则按哈希函数H(key)=keyMOD13和链地址法处理冲突来构造哈希表。（1）画出所构造的哈希表。（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。6.设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。7.设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。8.设散列表的长度为8，散列函数H(k)=kmod7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。9.设有一组关键字，其出现次序为：105，97，28，52，37，22，16，90，45，76，59，74，采用哈希函数为H(key)=keyMOD13,试在0~14的散列地址空间中对该关键字序列构造哈希表。(1)采用线性探测再散列解决冲突。 38(2)采用二次探测再散列解决冲突。10．给定关键码序列(11,81,23,59,17,19,68)，散列表长度为11，散列函数为H(key)=(5*key)%11，用二次探查法解决冲突，试画出插入所有关键码后得到的散列表，并计算查找成功与查找不成功时的平均搜索长度六．设计题1.设计在顺序有序表中实现二分查找的算法(递归与非递归)。2.设计判断二叉树是否为二叉排序树的算法。3.设计求结点在二叉排序树中层次的算法。4.设计一个算法将二叉排序树按递减次序打印输出。5.设计在二叉排序树上查找结点X的算法。6.设计在有n个结点的顺序表中查找最小的k（1≤k≤n）个结点。第九章排序一、选择题1.下述排序算法中，稳定的是________。A．直接选择排序B．直接插入排序C．快速排序D．堆排序2.下列排序算法中，________需要的辅助存储空间最大。A．快速排序B．插入排序C．希尔排序D．归并排序3.下列排序算法中，________是稳定的。A．插入、希尔B．冒泡、快速C．选择、堆排序D．基数、归并4.下列各种排序算法中平均时间复杂度为O(n2)的是________。A．快速排序B．堆排序C．归并排序D．冒泡排序5.在待排序的元素基本有序的前提下，效率最高的排序方法是________。A．简单插入排序B．简单选择排序C．快速排序D．归并排序6.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为_______。A．O(n)B．O(nlog2n)C．O(n2)D．O(log2n)7.对n个记录进行堆排序，所需要的辅助存储空间为________。A．O(1og2n)B．O(n)C．O(1)D．O(n2)8.快速排序在最坏情况下的时间复杂度为________。A．O(log2n)B．O(nlog2n)C．O(n)D．O(n2)9.设有序列12、42、37、19，当使用直接插入排序从小到大排序时，其比较次数为________。 39A．3B．4C．5D．610.对数据元素序列(49,72,68,13,38,50,97,27)排序，前三趟排序结束时的结果依次为：第一趟：13,72,68,49,38,50,97,27；第二趟：13,27,68,49,38,50,97,72；第三趟：13,27,38,49,68,50,97,72；该排序采用的方法是_________。A.直接插入排序B.直接选择排序C.冒泡排序D.堆排序11.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。________就是不稳定的排序方法。A．起泡排序B．归并排序C．直接插入排序D．简单选择排序12.设一组初始记录关键字的长度为8，则最多经过________趟插入排序可以得到有序序列。A．6B．7C．8D．913.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是________。A．F，H，C，D，P，A，M，Q，R，S，Y，XB．P，A，C，S，Q，D，F，X，R，H，M，YC．A，D，C，R，F，Q，M，S，Y，P，H，XD．H，C，Q，P，A，M，S，R，D，F，X，Y14.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做________排序。A．插入B．堆C．快速D．归并15.每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序。A．插入B．堆C．快速D．归并16.下列________种排序算法的平均时间复杂度为O(nlog2n)。A．简单选择排序B．简单插入排序C．冒泡排序D．归并排序17.下列________种排序算法更适合于外部排序。 40A．选择排序B．插入排序C．冒泡排序D．归并排序18.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为________。A．2，3，5，8，6B．3，2，5，8，6C．3，2，5，6，8D．2，3，6，5，819.二路归并排序的时间复杂度为________。A．O(n)B．O(n2)C．O(nlog2n)D．O(log2n)20.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是________。A．堆排序B．冒泡排序C．希尔排序D．快速排序21.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是________。A．堆排序B．冒泡排序C．快速排序D．希尔排序22.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列________方法可以达到此目的。A．快速排序B．堆排序C．归并排序D．插入排序23.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为________。A．10，15，14，18，20，36，40，21B．10，15，14，18，20，40，36，21C．10，15，14，20，18，40，36，2lD．15，10，14，18，20，36，40，2124.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行________趟的分配和回收才能使得初始关键字序列变成有序序列。A．3B．4C．5D．825．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为________。A．40，50，20，95B．15，40，60，20C．15，20，40，45D．45，40，15，2026.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2 41的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为________。A．15，25，35，50，20，40，80，85，36，70B．15，25，35，50，80，20，85，40，70，36C．15，25，35，50，80，85，20，36，40，70D．15，25，35，50，80，20，36，40，70，8527.对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为__________的结点开始。A．100B．12C．60D．1528.一组记录的排序码为（46，79，56，38，40，84），则堆排序时建立的初始大顶堆为________。A．79，46，56，38，40，80B．38，46,56，79，40，84C．84，79，56，38，40，46D．84，56，79，40，46，38二、填空题1.设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_______。2.对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为______，在整个排序过程中最多需要进行______趟排序才可以完成。3.设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为________。4.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_______，整个堆排序过程的时间复杂度为________。5.对n个元素的序列进行起泡排序时，最少的比较次数是_______。6.在插入和选择排序中，若初始数据基本正序，则选用_______；若初始数据基本反序，则选用_______。7.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_______。8. 42设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果是________。9.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果是_______。10.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_______。11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为_________。12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用____排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用_______排序。13.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有_______。14.在快速排序、堆排序、归并排序中，_______排序是稳定的。三、判断题1.直接选择排序是一种稳定的排序方法。（）2.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）3.希尔排序算法的时间复杂度为O(n2)。（）4.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）5.一组关键码已完全有序时，最快的排序方法是快速排序。（）6.快速排序是排序算法中平均性能最好的一种排序。（）7.堆是完全二叉树，完全二叉树不一定是堆。（）8.层次遍历初始堆可以得到一个有序的序列。（）9.从平均性能而言，快速排序最佳，其所需时间最省。（）四、算法设计题1.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。 432.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。3.对给定的j（1<=j<=n），要求在无序的记录区R［1…n］中找到按关键字自小到大排在第j个位置上的记录（即在无序集合中找到第j个最小元），试利用快速排序的划分思想编写算法实现上述的查找操作。4.改写快速排序算法，要求采用前、中、后三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。一、填空题1、数据元素关系2、逻辑结构物理结构3、顺序存储链式存储索引存储哈希存储4、线性结构树图集合5、数据描述操作声名6、联系图树7、数据元素8、数据元素9、有穷性确定性可行性输入输出10、正确性可读性健壮性效率与存储量的要求11、O（n）12、时间空间13、O（n）14、O（m*n）15、O（n）16、时间复杂度空间复杂度二、选择题1-5BACAD6-10BCCB11-15BBACB16-20BDDAA21-23ACB三．判断题FT四、简答题1、数据的逻辑结构分为线性结构和非线性结构；常用的存储方式有顺序存储、链式存储、索引存储和哈希存储2、例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢? 44用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。3、算法是描述求特定问题而规定的一系列操作步骤集合。特性包括：有穷性、确定性、可行性、有零个或多个输入，有一个或多个输出。4、（1）a—b—c—d—e—f—g—h线性结构(2)树形结构dagbhef（3）图型结构5、解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。6、解： 45抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。7、解：8、解：(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+...+1=(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)===(6)n(7)向下取整(8)1100五、程序算法题1、（1）O(n)（2）O(n)（3）O(1)2、解：intmax3(intx,inty,intz){if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;}一、选择题1-5CBABA6-10CACCC11-15ACBCC16-20ABBDD21-25DCADC26-30BBDDA31C二、判断题1-5FFFFF6-10FFTFT11-15TTFFF16F三综合应用题1、(1)EmemtypeDelete(Elemtypea[],int&Length){ 46Elemtypetag=0;Elemtypemin;if(Length==0)returnERROR;for(inti=1;i 47",n);--(*LA).length;/*表长减1*/returnOK;}(3)StatusListInsert_Sq(SqList*LA,inti,ElemTypee){/*在顺序线性表L中第i个位置之前插入新的元素e,//i的合法值为1≤i≤Listlength_Sq(L)+1*/ElemType*newbase,*q,*p;intn=0;/*定义局部变量*/ 48if(i<1||i>(*LA).length+1)returnERROR;/*值不合法*/if((*LA).length>=(*LA).listsize){/*当前空间已满，增加分配*/newbase=(ElemType*)realloc((*LA).elem,((*LA).listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);/*存储分配失败*/(*LA).elem=newbase;/*新基址*/(*LA).listsize+=LISTINCREMENT;}/*增加存储容量*/q=&((*LA).elem[i-1]);/*q为插入位置*/for(p=&((*LA).elem[(*LA).length-1]);p>=q;--p){*(p+1)=*p;++n;}/*插入位置及之后的元素右移*/printf("n=%d 49",n);*q=e;/*插入e*/++(*LA).length;returnOK;}4、voiddel_x(Sqlist&L,Elemtypex){intk=0;for(i=0;i 50}L.length-=k;returntrue;}（6）boolDel_s_t(sqList&L,Elemtypes,Elemtypet){inti,j;if(L.length==0||s>=t)returnfalse;for(i=0;i 51inti,j;for(i=0,j=1;j 52”,pre->data)； 53if(pre->data%2!=0)∥处理奇数if(pre->next!=null){∥若该结点没有后继，则不必交换t=pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交换完毕else∥处理偶数情况if(pre->next!=null){∥若最小值结点是最后一个结点，则无后继u=pre->next；pre->next=u->next；free(u)；}∥释放后继结点空间}5、解法如下：假定链表结点类型如下;structnode{intdata;node*next;};voidsort(node*head){node*p=head->next;while(p){node*q=p->next;while(q){if(q->data 54pa=la->next;pb=lb->next;∥pa，pb分别是链表la和lb的工作指针la->next=null;∥la作结果链表的头指针，先将结果链表初始化为空。while(pa!=null&&pb!=null)∥当两链表均不为空时作if(pa->data<=pb->data){r=pa->next;∥将pa的后继结点暂存于r。pa->next=la->next;∥将pa结点链于结果表中，同时逆置。la->next=pa;pa=r;∥恢复pa为当前待比较结点。}else{r=pb->next;∥将pb的后继结点暂存于r。pb->next=la->next;∥将pb结点链于结果表中，同时逆置。la->next=pb;pb=r;∥恢复pb为当前待比较结点。}while(pa!=null){∥将la表的剩余部分链入结果表，并逆置。r=pa->next;pa->next=la->next;la->next=pa;pa=r;}while(pb!=null){r=pb->next;pb->next=la->next;la->next=pb;pb=r;}returnla;}7、voidDel_Same(LinkList&L){LNode*p=L->next,*q;while(p->next!=null){q=p->next;if(p->data==q->data){p->next=q->next;free(q);}elsep=p->next; 55}}8、LinkedListDelete（LinkedListL）∥L是带头结点的单链表，本算法删除其最小值结点。{p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。pre=L；∥pre指向最小值结点的前驱。q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。while（p->next!=null）{if（p->next->data 5610、LinkedListdelinsert(LinkedListlist){p=list->link;pre=list;q=p;while(p->link!=null){if(p->link->data 57return(ha);}12、LinkedListUnion(LinkedListla,LinkedListlb){pa=la->next;pb=lb->next;∥设工作指针pa和pb；pc=la;∥结果表中当前合并结点的前驱的指针。while(pa&&pb){if(pa->data==pb->data){∥交集并入结果表中。pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);}elseif(pa->data 58对两个链表进行归并，但当A的一个元素，不是B中的一个元素时，才将其加入到新链表C中。算法的代码：NODE*difference(NODE*A,NODE*B){NODE*C,*last；C=last=(NODE*)malloc(sizeof(NODE))；while(A!=null&&B!=null){∥两均未空时循环if(A->element 59returnla;}15、LinkedListDisCreat(LinkedListA)∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。处理之后，B表的头指针即为A表头指针，只需返回C表头指针即可。{B=A;C=(LinkedList)malloc(sizeof(LNode));∥为C申请结点空间。C->next=null∥C初始化为空表。p=A->next;∥p为工作指针。B->next=null;∥B表初始化。while(p!=null){r=p->next;∥暂存p的后继。if(p->data<0){∥小于0的放入B表。p->next=B->next;B->next=p;∥将小于0的结点链入B表}else{p->next=C->next;C->next=p;}p=r;∥p指向新的待处理结点。}returnC;}16、LinkedListDisCreat(LinkedListA){∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号∥为奇数的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。i=0;∥i记链表中结点的序号。B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。B->next=null;∥B表的初始化。LinkedListra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。ra=A;rb=B;p=A->next;∥p为链表工作指针，指向待分解的结点。A->next=null;∥置空新的A表while(p!=null){r=p->next;∥暂存p的后继。i++;if(i%2==0){∥处理原序号为偶数的链表结点。p->next=null;∥在B表尾插入新结点； 60rb->next=p;rb=p;∥rb指向新的尾结点；}else{∥处理原序号为奇数的结点。p->next=ra->next;ra->next=p;ra=p;}p=r;∥将p恢复为指向新的待处理结点。}returnB;}17、intPattern(LinkedListA，LinkedListB){∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；∥否则，返回0表示不是。p=A；∥p为A链表的工作指针，本题假定A和B均无头结点。pre=p；∥pre记住每趟比较中A链表的开始结点。q=B；∥q是B链表的工作指针。while(p&&q)if(p->data==q->data){p=p->next；q=q->next；}else{pre=pre->next；p=pre；∥A链表新的开始比较结点。q=B；}∥q从B链表第一结点开始。if(q==null)return1；∥B是A的子序列。elsereturn0；∥B不是A的子序列。}18、voidRearrange(SeqLista;intn){∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线∥性表a，使所有值为负数的元素移到所有值为正数的数的前面。i=0;j=n-1;∥i,j为工作指针（下标），初始指向线性表a的第1个和第n个元素。t=a[0];∥暂存枢轴元素。while(i 61a[i]=a[j];i++;}while(i 62}21、DLinkListlocate(DLinkListL，ElemTypex){∥L是带头结点的按访问频度递减的双向链表，本算法先查找数据x，∥查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。DLinkListp=L->next,q;∥p为L表的工作指针，q为p的前驱，用于查找插入位置。while(p&&p->data!=x)∥查找值为x的结点。p=p->next;if(!p){printf(“不存在值为x的结点 63”);returnNULL;}else{p->freq++;∥令元素值为x的结点的freq域加1。p->next->pred=p->pred;∥将p结点从链表上摘下。p->pred->next=p->next;q=p->pred;∥以下查找p结点的插入位置while(q!=L&&q->freq 64{if(a[tag]>a[i])tag=i;}min=a[tag];a[tag]=a[Length-1];Length--;returnmin;}(2)StatusListDelete_Sq(SqList*LA,inti,ElemType*e){/*在顺序线性表L中删除第i个元素，并用e返回其值//i的合法值为1≤i≤Listlength_Sq(L)*/ElemType*q,*p;intn=0;/*定义局部变量*/if((i<1)||(i>(*LA).length))returnERROR;/*i值不合法*/p=&((*LA).elem[i-1]);/*p为被删除元素的位置*/*e=*p;/*被删除元素的值赋给e*/q=(*LA).elem+(*LA).length-1;/*表尾元素的位置*/for(++p;p<=q;++p){*(p-1)=*p;++n;}/*被删除元素之后的元素左移*/printf("n=%d 65",n);--(*LA).length;/*表长减1*/returnOK;}(3)StatusListInsert_Sq(SqList*LA,inti,ElemTypee){/*在顺序线性表L中第i个位置之前插入新的元素e,//i的合法值为1≤i≤Listlength_Sq(L)+1*/ElemType*newbase,*q,*p;intn=0;/*定义局部变量*/if(i<1||i>(*LA).length+1)returnERROR;/*值不合法*/if((*LA).length>=(*LA).listsize){/*当前空间已满，增加分配*/newbase=(ElemType*)realloc((*LA).elem,((*LA).listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);/*存储分配失败*/(*LA).elem=newbase;/*新基址*/ 66(*LA).listsize+=LISTINCREMENT;}/*增加存储容量*/q=&((*LA).elem[i-1]);/*q为插入位置*/for(p=&((*LA).elem[(*LA).length-1]);p>=q;--p){*(p+1)=*p;++n;}/*插入位置及之后的元素右移*/printf("n=%d 67",n);*q=e;/*插入e*/++(*LA).length;returnOK;}4、voiddel_x(Sqlist&L,Elemtypex){intk=0;for(i=0;i 68if(L.length==0||s>=t)returnfalse;for(i=0;i 69p=L->next；∥p为工作指针。L->next=null；∥第一结点成为尾结点。while（p!=null）{r=p->next；p->next=L；∥将p结点插到L结点前面。L=p；∥L指向新的链表“第一”元素结点。p=r；}returnL;}3、LinkListreverse(LinkList&L)//带头结点单链表的就地逆置{p=L->next;L->next=null;while(p!=NULL){r=p->next;p->next=L->next;L->next=p;p=r;}returnL;}4、voidMiniValue(LinkedListla){∥la是数据域为正整数且无序的单链表，本算法查找最小值结点且打印。∥若最小值结点的数值是奇数，则与后继结点值交换；否则，就删除其直接后继结点。p=la->next；∥设la是头结点的头指针，p为工作指针。pre=p；∥pre指向最小值结点，初始假定首元结点值最小。while(p->next!=null){∥p->next是待比较的当前结点。if（p->next->data 70”,pre->data)；if(pre->data%2!=0)∥处理奇数if(pre->next!=null){∥若该结点没有后继，则不必交换t=pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交换完毕else∥处理偶数情况if(pre->next!=null){∥若最小值结点是最后一个结点，则无后继 71u=pre->next；pre->next=u->next；free(u)；}∥释放后继结点空间}5、解法如下：假定链表结点类型如下;structnode{intdata;node*next;};voidsort(node*head){node*p=head->next;while(p){node*q=p->next;while(q){if(q->data 72pa=r;∥恢复pa为当前待比较结点。}else{r=pb->next;∥将pb的后继结点暂存于r。pb->next=la->next;∥将pb结点链于结果表中，同时逆置。la->next=pb;pb=r;∥恢复pb为当前待比较结点。}while(pa!=null){∥将la表的剩余部分链入结果表，并逆置。r=pa->next;pa->next=la->next;la->next=pa;pa=r;}while(pb!=null){r=pb->next;pb->next=la->next;la->next=pb;pb=r;}returnla;}7、voidDel_Same(LinkList&L){LNode*p=L->next,*q;while(p->next!=null){q=p->next;if(p->data==q->data){p->next=q->next;free(q);}elsep=p->next;}}8、LinkedListDelete（LinkedListL）∥L是带头结点的单链表，本算法删除其最小值结点。{p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。pre=L；∥pre指向最小值结点的前驱。 73q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。while（p->next!=null）{if（p->next->data 74{if(p->link->data 75if(pa->data==pb->data){∥交集并入结果表中。pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);}elseif(pa->data 76A=A->link；}elseif(A->element==B->element){∥两表中相等元素不作结果元素A=A->link；B=B->link；}elseB=B->link；∥向后移动B表指针}while(A!=null){last=append(last,A->element)；A=A->link；}last->link=null；∥置链表尾last=C；C=C->link；free(last)；returnC；}14、LinkedListLinkListInsertSort(LinkedListla){∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成递增的有序链表。if(la->next!=null){∥链表不为空表。p=la->next->next;∥p指向第一结点的后继。la->next->next=null;∥直接插入原则认为第一元素有序，从第二元素起依次插入。while(p!=null){r=p->next;∥暂存p的后继。q=la;while(q->next!=null&&q->next->data 77B=A;C=(LinkedList)malloc(sizeof(LNode));∥为C申请结点空间。C->next=null∥C初始化为空表。p=A->next;∥p为工作指针。B->next=null;∥B表初始化。while(p!=null){r=p->next;∥暂存p的后继。if(p->data<0){∥小于0的放入B表。p->next=B->next;B->next=p;∥将小于0的结点链入B表}else{p->next=C->next;C->next=p;}p=r;∥p指向新的待处理结点。}returnC;}16、LinkedListDisCreat(LinkedListA){∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号∥为奇数的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。i=0;∥i记链表中结点的序号。B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。B->next=null;∥B表的初始化。LinkedListra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。ra=A;rb=B;p=A->next;∥p为链表工作指针，指向待分解的结点。A->next=null;∥置空新的A表while(p!=null){r=p->next;∥暂存p的后继。i++;if(i%2==0){∥处理原序号为偶数的链表结点。p->next=null;∥在B表尾插入新结点；rb->next=p;rb=p;∥rb指向新的尾结点；}else{∥处理原序号为奇数的结点。p->next=ra->next;ra->next=p;ra=p;} 78p=r;∥将p恢复为指向新的待处理结点。}returnB;}17、intPattern(LinkedListA，LinkedListB){∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；∥否则，返回0表示不是。p=A；∥p为A链表的工作指针，本题假定A和B均无头结点。pre=p；∥pre记住每趟比较中A链表的开始结点。q=B；∥q是B链表的工作指针。while(p&&q)if(p->data==q->data){p=p->next；q=q->next；}else{pre=pre->next；p=pre；∥A链表新的开始比较结点。q=B；}∥q从B链表第一结点开始。if(q==null)return1；∥B是A的子序列。elsereturn0；∥B不是A的子序列。}18、voidRearrange(SeqLista;intn){∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线∥性表a，使所有值为负数的元素移到所有值为正数的数的前面。i=0;j=n-1;∥i,j为工作指针（下标），初始指向线性表a的第1个和第n个元素。t=a[0];∥暂存枢轴元素。while(i 79a[i]=t;∥将原第一元素放到最终位置。此枢纽是为了减少交换次数，正负皆可。}19、voidderivative(ha){q=ha;pa=ha->next;while(pa!=null){∥遍历到链表结束if(pa->exp==0){∥若指数为0，即本项为常数项q->next=pa->next;∥删常数项free(pa);pa=q;}else{pa->coef=(pa->coef)*(pa->exp);pa->exp--;∥指数项减1q=pa;}∥前驱后移,或q->nextpa=pa->next;∥取下一元素}}20、voidAdjust(DLinkListL){DLinkListtail=L->prior,p=L->next；inti=0;while(p!=tail){i++;q=p->next;if(i%2==0){p->prior->next=q;q->prior=p->prior;tail->next->prior=p;p->next=tail->next;p->prior=tail;tail->next=p;}p=q;}}21、DLinkListlocate(DLinkListL，ElemTypex){∥L是带头结点的按访问频度递减的双向链表，本算法先查找数据x，∥查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。DLinkListp=L->next,q;∥p为L表的工作指针，q为p的前驱，用于查找插入位置。while(p&&p->data!=x)∥查找值为x的结点。p=p->next; 80if(!p){printf(“不存在值为x的结点 81”);returnNULL;}else{p->freq++;∥令元素值为x的结点的freq域加1。p->next->pred=p->pred;∥将p结点从链表上摘下。p->pred->next=p->next;q=p->pred;∥以下查找p结点的插入位置while(q!=L&&q->freq 82五、程序算法题1、typedefintDatatype;typedefstructqueuenode{Datatypedata;structqueuenode*next;}QueueNode;//以上是结点类型的定义typedefstruct{queuenoderear;}LinkQueue;//只设一个指向队尾元素的指针voidInitQueue(LinkQueue&Q){//置空队：就是使头结点成为队尾元素Q.rear=(queuenode*)malloc(sizeof(queuenode))QueueNode*s;Q->rear=Q->rear->next;//将队尾指针指向头结点while(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next;Q->rear->next=s->next;free(s);}//回收结点空间}intEmptyQueue(LinkQueue&Q){//判队空//当头结点的next指针指向自己时为空队returnQ->rear->next->next==Q->rear->next;}voidEnQueue(LinkQueue&Q,Datatypex){//入队//也就是在尾结点处插入元素QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点p->data=x;p->next=Q->rear->next;//初始化新结点并链入Q-rear->next=p;Q->rear=p;//将尾指针移至新结点 83}DatatypeDeQueue(LinkQueue&Q,Datatype&x){//出队,把头结点之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q))Error("Queueunderflow");p=Q->rear->next->next;//p指向将要摘下的结点x=p->data;//保存结点中数据if(p==Q->rear){//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点Q->rear=Q->rear->next;Q->rear->next=p->next;}elseQ->rear->next->next=p->next;//摘下结点pfree(p);//释放被删结点returnx;}2、#include"stdio.h"voidout(intnum){inti=0;if(num==1){printf("%d",num);}else{for(i=1;i<=num;i++){printf("%d",num);}printf(" 84");out(--num);} 85}voidmain(){out(9);getch();}3、解：因为输入序列是从小到大排列的，所以若pj 867.charst［m0］;8.inttop=0,i=1;9.flag=1;10.while(i<=m0&&tag)11.{12.if(exp［i］=='('‖exp［i］=='［'‖exp［i］=='{'13./*遇到'('、'［'或'{'，则将其入栈*/14.{15.top++;16.st［top］=exp［i］;17.}18.if(exp［i］==')')/*遇到')'，若栈顶是'('，19.则继续处理，否则以不配对返回*/20.if(st［top］=='(')top--;21.elseflag=0;22.if(exp［i］=='］')/*遇到')'，若栈顶是'［'，23.则继续处理，否则以不配对返回*/24.if(st［top］=='［')top--;25.elseflag=0;26.if(exp［i］=='}')/*遇到')'，若栈顶是'{'，27.则继续处理，否则以不配对返回*/28.if(st［top］=='{')top--;29.elseflag=0;30.i++;31.}32.if(top>0)flag=0;/*若栈不空，则不配对*/33.}6、解：假设队列为循环顺序队列。建立一个临时队列，将指定队列中所有元素出队并入队到临时队列中，这样指定队列为空，再将临时队列中所有元素出队并入队到指定队列(因为不能破坏原队列结构，所以需要恢复元素)，最后一个元素即为所求。具体算法如下：datatypelastelem(queue*Q){datatypex；queuetmpQ；initqueue(&tmpQ)while(!emty(Q))//将Q中元素放入tmpQ{x=dequeue(Q)enqueue(&tmpQ，x)；}while(!empty(&tmpQ))//将tmpQ中元素恢复回Q{x=dequeue(&tmpQ)； 87enqueue(Q，x)；}returnx；}7、解：队列为空：count==0 队列为满：count=MAXLEN 队尾第一个元素位置==(front+count)%MAXLEN 队首第一个元素位置==(front+1)%MAXLEN const MAXLEN=100; int queue[MAXLEN]; int front,count; // 定义队头和计数器count （1）初始化队列 void init() { front=1; count=0; } （2）判定队空 int QEmpty() { if (count==0) return(1); else return(0);} （3）读队头元素 void ReadFront(int queue[],x) { if (count==0) printf(" 下溢出 88"); else { front=(front+1)%MAXLEN; x=queue[front]; } }（4）入队操作 void InQueue(int queue[],int x) { int place; if (count==MAXLEN) printf(" 上溢出 89"); else { count++; place=(front+count)%MAXLEN; queue[MAXLEN]=x; 90 } } （5）出队操作 void OutQueue(int queue[]) // 删除队列头元素 { if (count==0) printf(" 队列下溢出 91"); else { front=(front+1)%MAXLEN; count--; } } 8、解析：定义本题队列类型如下：typedefstruct{linklist*rear;}Queue2(1)队列中人队操作是在队尾进行，即在链尾插入一个新结点。voidenqueue(Queue2*Q，datatypex){linklist*s；s＝(linklist*)malloe(sizeof(linklist))；//建立新结点s—>datda=x；s—>next=Q—>rear—>next；//将新结点插入队尾q—>rear—>next=s；q—>rear=s；}(2)队列中出队操作是在队头进行，即删除链表第一个数据结点。datatypedequeue(Queue2*Q){datatypex；linklist*p；if(Q—>rear—>next==Q—>rear)//队列为空returnNULL；p＝Q一>rear一>next一>next；//p指向队头结点x=p一>data；Q一>rear一>next一>next＝p一>next//删除*p结点free(p)returnx；//返回原队头元素}第四章串一．选择题 921.A2.C3.C4.D5.D6.D7.B8.D9.A10.C11.D12.D二．填空题1.长度为零的串字符串元素只有空格的串2.子串主串三.简答题1.答：长度为0的串称为空串；由一个或多个空格组成的串称为空格串。空格也是串的字符集合中的一个元素。2.答：虽然串是由字符组成的，但串和字符是两个不同的概念。串是长度不确定的字符序列，儿子富只是一个字符，即使是长度为1的串也与字符不同。例如，串“a”和字符‘a’就是两个不同的概念，因为在执行时串的结尾通常加上串结束标志“\0”。3.答：串的顺序存储结构是用一维数组存放串中的字符，用静态内存分配的方法定义数组，数组元素在编译时是确定的，在运行时是不可改变的称为静态顺序存储，用动态内存分配方法定义数组，数组元素个数是在程序运行时用户申请确定的称为动态顺序存储。4.StatusStrDelete(String&S,inti,intj){intlen;len=j-i+1;if(i<1||i>s[0]||j>s[0])returnERROR;S[pos..S[0]-len]=S[pos+len..S[0]];S[0]=S[0]-len;ReturnOK;} 93第五章一．选择题1.B2.A3.C4.B5.D6.D7.C8.D9.C10.B11.C12.D13.A14.C15.D16.D17.C18.D19.B20.C21.A22.B23.B24.C25.D二．填空题1.i(i+1)/2+j2.174139 943.4.对称上三角（下三角）矩阵5.d6.表头表尾7.（2,3,5）8.行列9.3310.O(n)11.O(n2)12.行列13.（）((),(()))3314.(a)((b),((c)))三．判断题1.√2.√3.√4.√5.×6.×7.√8.√9.√10.√四、简答题1.二维数组存储时，要把它的元素映像存储在一维存储器中，存储时若按先行后列的顺序存储，叫做二维数组的行序优先存储。若按先列后行的顺序存储，叫做二维数组的列序优先存储。2.元素分布特殊的矩阵，列如三角矩阵，对称矩阵，带状矩阵，稀疏矩阵等，叫做特殊矩阵。特殊矩阵压缩存储的基本思想是压缩存储，即值相同的元素只分配一个存储空间，零元素不分配存储空间。3.设m*n矩阵中有t个非零元素且t< 95由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。1.ije0010422042154365.(((a,b,()),(),a,(b)),())6.程序设计题1.11.intgenlistDepth(BSLinkListlist){/*list存放广义链表的首地址，该算法返回广义链表的深度*/2BSLinkListstack1[M],p;/*stack1用来记录子表的起始位置*/3/*stack2用来记录子表当前的深度，depth用来表示当前所求子表的深度，maxdep用来记录当前已求出的那些子表的最大深度,stack1和stack2共用一个栈顶指针*/4intstack2[M],depth=0,maxdep=0,top=-1;5p=list->pointer;/*将p指针指向广义链表的第一个元素所在的链接点*/6if(p!=NULL){7do{8while(p!=NULL){9stack1[++top]=p;/*记录当前子表的起始位置*/10stack2[top]=depth;/*记录当前所求子表的深度*/11if(p->flag==1){/*当前链接点元素是子表*/12depth++;/*当前层次数加1*/13p=p->pointer;/*移动到下一层*/ 961}2else3p=NULL;4}5if(maxdep 97{printf("No 98");flat++;break;}if(flat==0)printf("%c 99",m);}}3.（1）#include 100",s);}（2）voidproc2(matrixA){ints=0,i,j;i=0;while(i 101",s);}（3） 102voidproc3(matrixA){inti,s;if(m!=n)printf("m!=n");else{s=0;for(i=0;i 103",s);}}voidmain(){intm,n,i,j;matrixA;printf("m,n:");scanf("%d%d",&m,&n);printf("元素值: 104");for(i=0;i 1051、完全二叉树2、127643、314、2+12-15、1多6、1297、P->lchild==null&&p->rchild==null8、哈夫曼树9、41610、011、16512、6316、6三综合应用题1 106（1）根节点：A叶子节点：CEFHIJKMN非终端节点：ABDGL（2）深度：5各节点层数A：1；B、C、D：2；E、F、G、H、I、J：3；K、L、M：4；N：5（3）双亲：D祖先：AD孩子：KLM子孙：KLMN兄弟：HIJ堂兄弟：EF2先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIG后序遍历：DCBFJIHGEA3对应的二叉树后序遍历为：bdeca4 10756 108带权路径长度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131树的结点总数137(1)哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。(2)哈夫曼树为：（3）哈弗曼编码： 109a:1110b:1111c:110d:00e:01f:10(4)长度：244四、算法设计题1.设计一个求结点x在二叉树中的双亲结点的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx 110");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}2. 设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0); 111elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}3. 设计计算二叉树中所有结点值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}}4.设计求二叉树中值为x的结点所在的层号的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}第六章树答案一选择题1-5ABBDC6-10CACBD11-15BCADB16-20BAAAA21-22CA二填空题 1121、n2+12、373、单分支4、完全二叉树5、127646、317、2+12-18、1多9、12910、P->lchild==null&&p->rchild==null11、哈夫曼树12、41613、014、16515、6316、6三综合应用题1 113（1）根节点：A叶子节点：CEFHIJKMN非终端节点：ABDGL（2）深度：5各节点层数A：1；B、C、D：2；E、F、G、H、I、J：3；K、L、M：4；N：5（3）双亲：D祖先：AD孩子：KLM子孙：KLMN兄弟：HIJ堂兄弟：EF2先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIG后序遍历：DCBFJIHGEA3对应的二叉树后序遍历为：bdeca4 11456 115带权路径长度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131树的结点总数137(1)哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。(2)哈夫曼树为：（3）哈弗曼编码： 116a:1110b:1111c:110d:00e:01f:10(4)长度：244四、算法设计题1.设计一个求结点x在二叉树中的双亲结点的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx 117");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}2. 设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0); 118elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}3. 设计计算二叉树中所有结点值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}}4.设计求二叉树中值为x的结点所在的层号的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}第七章图一．选择题1.B2.B3.C4.A5.A6.B7.D8.B9.A10.A11.B12.B13.A14.C15.A16.C17.C18.D19.C20.B21.A22.D23.B24.A25.C26.C二、填空题 1191.度，出度2.ACDFBEABECFD3.n(n-1)，n4.4.n(n-1)/2n(n-1)5.m=2e6.n-17.邻接矩阵，邻接表，十字链表，临接多重链表，边集数组8.669.n,2e10.n-111.1,012.113.第i列元素的和14.45,9015.n-116.e,2e17A[i][j]=A[j][i]=118.等于19.出度,入度20.可以随机访问任意顶点21.O（n2）,O(n+e)22.v1,v3,v2,v4v1,v3,v2,v423.1324524.活动和活动间的优先关系25有向无环三、判断题1.√2.×3.×4.×5.×6.√7.×8×9.√10√11√四、简答题1.图的深度遍历2.相关无关3.123564123456最小生成树：4. 1205.边的集合{【1,5】，【2，5】，【3,5】，【3,4】}权值之和106.12543广度优先生成树：（2）7.（1）（2）深度优先遍历：abdce广度优先遍历abedc8.(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,（4,6)4,(5,7)209.（1） 121（2）五、算法设计题1.intCount(GraphG){intcount=0;for(v=0;v 122visited[v]=true;for(w=FirstAdjVex(G,v);w;w=NextAgjVex(G,v,w)){if(!visited[w])DFS(G,w)}}2.intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFSvoidfind(intA[][],intm,intn)//求矩阵A中的马鞍点{inti,j,min,flag;for(i=0;i 123{LinkListp,q,r;p=A->next;q=B->next;r=C=A;while(p&&q){if(p->data 1248.669.n,2e10.n-111.1,012.113.第i列元素的和14.45,9015.n-116.e,2e17A[i][j]=A[j][i]=118.等于19.出度,入度20.可以随机访问任意顶点21.O（n2）,O(n+e)22.v1,v3,v2,v4v1,v3,v2,v423.1324524.活动和活动间的优先关系25有向无环三、判断题1.√2.×3.×4.×5.×6.√7.×8×9.√10√11√四、简答题1.图的深度遍历2.相关无关3.123564123456最小生成树：4.5.边的集合{【1,5】，【2，5】，【3,5】，【3,4】}权值之和106.12543广度优先生成树： 125（2）7.（1）（2）深度优先遍历：abdce广度优先遍历abedc8.(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,（4,6)4,(5,7)209.（1）（2） 126五、算法设计题1.intCount(GraphG){intcount=0;for(v=0;v 127if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFSvoidfind(intA[][],intm,intn)//求矩阵A中的马鞍点{inti,j,min,flag;for(i=0;i 128}else{r->next=q;r=r->next;q=q->next;}}r->next=(p!=NULL?p:q);free(B);}3.第八章答案一、选择题1~5CCCCD6~10BACBD11~15BAAAA16~20CBCBB21~25CB⑧①③④DB26~31CBDBCA二、选择题1~9对对错对对对错三、填空题（1）2.9（2）2.1（3）1、2（4）7（5）1、2、4、8、5、3.7（6）O(n)、O(log2n)（7）3（8）增高一层（9）h（10）递增数列、后缀表达式（11）┌m/2┐-1、m-1、O(n)、O(nlog2n)、O(n)（12）减少一层（13）如何构造哈希函数、如何处理冲突（14）发生冲突的可能性越大、发生冲突的可能性越小（15）开放定址法、拉链法 129四、简答题1.静态查找表：如果一个查找表的操作只涉及查询和检索某个特定的数据元素的操作，无需动态的修改查找表，此类查找表称之为静态查找表。动态查找表：需要动态的插入或删除操作的查找表称之为动态查找表。适合静态查找的存储结构有：顺序存储，散列存储。适合动态查找的存储结构有：顺序存储，散列存储。2.平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字的次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。其数学定义为ASL=∑PiCi(i=1,2,3,…,n),其中：Pi为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。3.（1）53/\1766/\/\12255870/\\566087（2）中序遍历二叉排序树可得到一个从小到大的有序序列。4. 1305.（1）（2）ASL=(4+2*3+3*2+4)/9=20/96. 1317.8.H(25)=25mod7=4H(31)=31mod7=3 132H(8)=8mod7=1H(27)=27mod7=6H(13)=13mod7=6H(68)=68mod7=5线性探测法：ASL=(5*1+2)/6=7/6链地址法：ASL=(5*1+1*2)/6=7/69.H(105)=105mod13=1H(97)=97mod13=6H(28)=28mod13=2H(52)=52mod13=0H(37)=37mod13=11H(22)=22mod13=9H(16)=16mod13=3H(90)=90mod13=12H(45)=45mod13=6H(76)=76mod13=11H(59)=59mod13=7H(74)=74mod13=9（1）散列地址0123456789101112131415关键字5210528169745592274379076冲突次数111112212113（2）散列地址0123456789101112131415关键字5210528169745592276379074冲突次数11111221311510.H(11)=(5*11)%11=0H(81)=(5*81)%11=7H(23)=(5*23)%11=5H(59)=(5*59)%11=9H(17)=(5*17)%11=8H(19)=(5*19)%11=7H(68)=(5*68)%11=10散列地址012345678910关键字11231981175968冲突次数1131111ASL(成功)=（6*1+3)/7=9/7ASL（不成功）=(1+7+6+5+4+3+2)/11=28/11 133六、设计题1.二分查找递归算法：Typedefstruct{//查找表的数据结构ElemType*elem;intlength;}SSTable;intBinSearch(SeqlistR,ElemTypek,intlow,inthigh){intmid;if(low<=high){mid=(low+high)/2;if(k>R[mid].key)Search(R,key,mid+1,high);elseif(k 134if(b1==0||pred>=bt->data)return0;pred=bt->data;b2=JudgeBST(bt->rchild);returnb2;}}3.intlevel(BiTreebt,BSTNode*p){intn=0;BiTreet=bt;if(bt!=NULL){n++;while(t->data!=p->data){if(t->data 135return(BST_Search(bt->rchild,X));}6.boolsearchmin(Sqlist&L,DateTypek){if(L.Length==0)returnfalse;k=L.data[0];intpos=0;for(inti=1;i 136 while(i 137 voidCollect(seqlistR,LinkQueueB[]) { //依次将各非空箱子中的记录收集起来，本过程结束，各箱子都变空 inti,j; for(j=0;j 1383、O(n)，O(nlogn)4、O(n)，O(nlogn)5、n-16、插入，选择7、38、（12,24,27,35,18,26）9、（12,18,24,35,27,26）10、（38,13,27,10,65,76,97）11、（5,16,71,23,72,94,73）12、快速，归并13、希尔排序，选择排序，快速排序，堆排序14、归并排序三、判断题1、错2、对3、错4、错5、错6、对7、错8、错四、算法设计题1、解：因为只需将负数关键字排在前面而无需进行精确排列顺序，因此本算法采用两端扫描的方法，就象快速排序采用的方法一样，左边扫描到正数时停止，开始扫描右边，遇到负数时与左边的当前记录交换，如此交替进行，一趟下来就可以完成排序。 voidReSort(SeqListR) {//重排数组，使负值关键字在前 inti=1,j=n;//数组存放在R[1..n]中 while(i 139 for(i=0;i 140 voidQuickSort(SeqListR,intlow,inthigh) {//对R[low..high]快速排序 intpivotpos; if(high-low<=2)//若当前区内元素少于3个 {//则进行直接插入排序 InsertSort(R,low,high); } Else { pivotpos=midPartion(R,low,high); QuickSort(R,low,pivotpos-1); QuickSort(R,pivotpos+1，high); } }//QuickSort
此文档下载收益归作者所有
