数据结构各章习题及答案
数据结构习题及解答
第1章 概述
【例1-1】分析以下程序段的时间复杂度。
for(i=0;i 解：该程序段的时间复杂度为O (m*n )。 【例1-2】分析以下程序段的时间复杂度。 i=s=0; ① while(s 解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。假定循环重复执行x 次后结束， 则语句②和语句③各重复执行了x 次。其时间复杂度按线性累加规则为O (x )。此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。所以有：1+2+3+…+x ≥n ，可以推出： x=n n 241 212811+±-=+±- x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O (n ）。 【例1-3】分析以下程序段的时间复杂度。 i=1; ① while(i<=n) i=2*i; ② 解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤) (2 。 log) 得：T（n）=O(n2 【例1-4】有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n<=1) return(1);① else return(n*fact(n-1));② } 解：设fact（n）的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。 由此可得fact（n）的时间复杂度为O(n)。 习题1 一、单项选择题 1.数据结构是指（1. A ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（3. D ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（4. B）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（5. C、），算法分析的两个主要方面是（A）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（6. C、），它具备输入，输出和（B）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（7. B）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（8. D）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（9. B ）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10.计算机内部数据处理的基本单位是（10. B）。 A.数据 B.数据元素 C.数据项 D.数据库 二、填空题 1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。1.线性结构，非线性结构 2.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。2.集合，线性，树，图 3.线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。3.一对一，一对多或多对多 4.一个算法的效率可分为__________________效率和__________________效率。4. 时间，空间 5.在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。5. 前趋，一，后继，多 6.在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。6. 有多个 7.线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。7. 一对一，一对多，多对多 8.下面程序段的时间复杂度是__________________。8. O(2n) for(i=0;i for(j=0;j A[i][j]=0; 9.下面程序段的时间复杂度是__________________。9. O(n) i=s=0; while(s { i++; s+=i; } 10.下面程序段的时间复杂度是__________________。10. O(2n) s=0; for(i=0;i for(j=0;j s+=B[i][j]; sum=s; 11.下面程序段的时间复杂度是__________________。11. O(log3n) i=1; while(i<=n) i=i*3; 12.衡量算法正确性的标准通常是__________________________。12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。 13.算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。13. 事后统计，事前估计 三、求下列程序段的时间复杂度。 1.x=0; for(i=1;i for(j=i+1;j<=n;j++) x++; 1. O(2n) 2.x=0; for(i=1;i for(j=1;j<=n-i;j++) x++; 2. O( 2 n) 3.int i,j,k; for(i=0;i for(j=0;j<=n;j++) { c[i][j]=0; for(k=0;k c[i][j]=a[i][k]*b[k][j] } 3. O(n 3 ) 4.i=n-1; while((i>=0)&&A[i]!=k)) j--; return (i); 4. O(n) 5.fact(n) { if(n<=1) return (1); else return (n*fact(n-1)); } 5. O(n) 第2章线性表 【例2-1】试编写出将两个顺序存储的有序表A和B合成一个有序表C的算法。 解：假设A、B和C的类型为下述SqList类型： #define maxlen 1000 typedef int elemtype typedef struct { elemtype elem[maxlen]; int len; }SqList; 设A和B的数据元素均为整数且为升序排列，设A的长度为m，B的长度为n，则合并后C的长度为m+n。合并时进行A、B元素的比较，将较小的链入C中，算法描述如下：int merge (SqList *A, SqList *B, SqList *C) //将两个有序表A和B合成一个有序表C { int m,n,i,j,k; m=(*A).len; n=(*B).len; if (m+n>maxlen-1) { printf("overflow"); exit (0); } i=0; j=0; //i和j分别作为扫描顺序表A和B的指针 k=0; //k指示顺序表C中当前位置 while ((i<=m)&&(j<=n)) if((*A).elem[i]<＝(*B).elem[j]) { (*C).elem[k]＝(*A)elem[i]; i++; k++; } else { (*C).elem[k]＝(*B)elem[j]; j++; k++; } while(i<=m) //表B已结束，表A没有结束，链入表A的剩余部分 { (*C).elem[k]＝(*A).elem[i]; i++; k++; } while(j<=m) //表A 已结束，表B 没有结束，链入表B 的剩余部分 { (*C).elem[k]＝(*B).elem[j]; i++; k++; } return (1); } 【例2-2】写一算法实现单链表的逆置。 解：假设单链表的表头指针用head 表示，其类型为下面定义的LinkList ，并且单链表不带头结点。逆置后原来的最后一个结点成为第一个结点，于是从第一个结点开始逐个修改每个结点的指针域进行逆置，且刚被逆置的结点总是新链表的第一个结点，故令head 指向它（如图2-1所示）。 typedef struct Node { elemtype data; struct Node *next; }LinkList; 具体算法描述如下： void contray(LinkList *head) { //将head 单链表中所有结点按相反次序链接 LinkList *p, *q; p=head; //p 指向未被逆序的第一个结点,初始时指向原表头结点 head=NULL; while(p!=NULL) { q=p; //q 指向将被逆序链接的结点 p=p->next; q->next=head; head=q; } } 【例2-3】假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知p 为指 图2-1 单链表逆置示意图 … (a )单链表初始状态 向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。 解：可引入一个指针q，当q->next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下： void delete (LinkList *p) { //在链表中删除p所指结点的前趋结点 LinkList *q,*t; q=p; while(q->next->next!=p) //q->next不是p的前趋结点 q=q->next; t=q->next; //t指向要删除结点 q->next=p; //删除t结点 free(t); ｝ 【例2-4】试设计实现删除单链表中值相同的多余结点的算法。 解：该例可以这样考虑，先取开始结点的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。 设单链表（其类型为LinkList）的头指针head指向头结点，则可按下列步骤执行：首先，用一个指针p指向单链表中第一个表结点，然后用另一个指针q查找链表中其余结点元素，由于是单链表，故结束条件为p= =NULL，同时让指针s指向q所指结点的前趋结点，当查找到结点具有q->data= =p->data时删除q所指的结点，然后再修改q，直到q 为空；然后使p指针后移（即p=p->next），重复进行，直到p为空时为止。算法描述如下：del(LinkList *head) { //删除单链表中值相同的多余结点 LinkList *p, *s, *q; p=head->next; while(p!=NULL && p->next!=NULL) { s=p; //s指向要删除结点的前趋 q=p->next; while (q!=NULL) { if (q->data= =p->data)} //查找值相同的结点并删除 { s->next=q->next; free(q); q=s->next; } else { s=q; q=q->next; } } p=p->next; } } 习题2 一、单项选择题 1.线性表是________。1．A A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。2．A A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。3．D A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。4．C A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。5．D A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6.设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。6．A A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7.在一个长度为n的顺序表中向第i个元素(0< i A．n-i B．n-i+l C．n-i-1 D．i 8.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行8．B A．s->next=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q 9. 以下关于线性表的说法不正确的是______。9．C A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。 C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10.线性表的顺序存储结构是一种_______的存储结构。 10．A A．随机存取B．顺序存取C．索引存取D．散列存取 11. 在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。11．D A．基地址B．结点大小 C．向量大小D．基地址和结点大小 12.在等概率情况下，顺序表的插入操作要移动______结点。 12．B A．全部B．一半 C．三分之一D．四分之一 13.在______运算中，使用顺序表比链表好。 13．C A．插入B．删除 C．根据序号查找D．根据元素值查找 14.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。 14．B A．O(1) B．O(n) C．O(n2) D．O(log2n) 15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列__________。15．C A．A, B, C, D, E B．B, C, D, E, A C．E, A, B, C, D D．E, D, C, B, A 16.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top 作为栈顶指针，当做出栈处理时，top变化为______。16．C A．top不变B．top=0 C．top-- D．top++ 17.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。17．B A．hs->next=s; B．s->next=hs; hs=s; C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next; 18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。18．D A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front 19.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为________。19．C A．rear％n= = front B．front+l= rear C．rear= = front D．(rear+l)％n= front 20. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为________。20．A A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next 二、填空题 1. 线性表是一种典型的_________结构。1．线性 2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。2．n-i+1 3.顺序表中逻辑上相邻的元素的物理位置________。3．相邻 4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。4．前移，前，后 5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。5．物理存储位置，链域的指针值 6. 在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。6．前趋，后继 7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。7．顺序，链接 8.顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。8．一定，不一定 9.线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。9．线性，任何，栈顶，队尾，队头 10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________10．单链表，双链表，非循环链表，循环链表 11.在单链表中设置头结点的作用是________。11．使空表和非空表统一；算法处理一致 12.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。12．O(1)，O(n) 13.对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇 14.设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push 后，输出序列是_________。14．2、3 15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。15．O(1) 三、简答题 1.描述以下三个概念的区别：头指针，头结点，表头结点。 1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。 2.线性表的两种存储结构各有哪些优缺点？ 2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。 3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？ 3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表 中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。 4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。 5.在单循环链表中设置尾指针比设置头指针好吗？为什么? 5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。 6.假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。 6．共有14种可能的出栈序列，即为： ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA 7.什么是队列的上溢现象？一般有几种解决方法，试简述之。 7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法： （1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。 （2）要避免出现“假溢出”现象可用以下方法解决： 第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。 第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。 第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。 8.下述算法的功能是什么? LinkList *Demo(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; } return (L); } 8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 四、算法设计题 1.设计在无头结点的单链表中删除第i个结点的算法。 1．算法思想为： （1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作； （2）当i=0时，删除第一个结点： （3）当０ delete(LinkList *q,int i) { //在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(i<0) printf("Can't delete"); else if(i= =0) { s=q; q=q->next; free(s); } else { j=0; s=q; while((j { p=s; s=s->next; j++; } if (s= =NULL) printf("Cant't delete"); else {p->next=s->next; free(s); } } } 2. 在单链表上实现线性表的求表长ListLength(L)运算。 2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下： int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L; while ( p->next!=NULL ) { p=p->next; len++; } return (len); } 3.设计将带表头的链表逆置算法。 3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下： void invert(LinkList *head) { //逆置head指针所指向的单循环链表 linklist *p, *q, *s; q=head; p=head->next; while (p!=head) //当表不为空时，逐个结点逆置 { s=q; q=p; p=p->next; q->next=s; } p->next=q; } 4. 假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next 和prior。其中data为整型数域，nex t和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。 4．定义类型LinkList如下： typedef struct node { int data; struct node *next,*prior; }LinkList; 此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下： insert (LinkList *head) { LinkList *p,*s,*q; p=head->next; //p指向待插入的结点，初始时指向第一个结点 while(p!=NULL) { s=head; // s指向q结点的前趋结点 q=head->prior; //q指向由prior域构成的链表中待比较的结点 while((q!=NULL) && (p->data>q->data)) //查找插入结点p的合适的插入位置 { s=q; q=q->prior; } s->prior=p; p->prior=q; //结点p插入到结点s和结点q之间 p=p->next; } } 5.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。 5．算法描述如下： delete(LinkList *head, int max, int min) { linklist *p, *q; if (head!=NULL) { q=head; p=head->next; while((p!=NULL) && (p->data<=min)) { q=p; p=p->next; } while((p!=NULL) && (p->data p=p->next; q->next=p; } } 6.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。 6．算法描述如下： delete(LinkList *head, int max, int min) { LinkList *p,*q; q=head; p=head->next; while (p!=NULL) if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; } else { q->next=p->next; free(p); p=q->next; } } 7.假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法： （1）向循环链队列插入一个元素值为x的结点； （2）从循环链队列中删除一个结点。 7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下： （1）插入（即入队）算法： insert(LinkList *rear, elemtype x) { //设循环链队列的队尾指针为rear,x为待插入的元素 LinkList *p; p=(LinkList *)malloc(sizeof(LinkList)); if(rear= =NULL) //如为空队，建立循环链队列的第一个结点 { rear=p; rear->next=p; //链接成循环链表 } else //否则在队尾插入p结点 { p->next=rear->next; rear->next=p; rear=p; } } （2）删除（即出队）算法： delete(LinkList *rear) { //设循环链队列的队尾指针为rear if (rear= =NULL) //空队 printf("underflow\n"); if(rear->next= =rear) //队中只有一个结点 rear=NULL; else rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点} 8.设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。 8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下： int InsertDecreaseList( SqList *L, elemtype x ) { int i; if ( (*L).len>= maxlen) { printf(“overflow"); return(0); } for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--) (*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素 (*L).elem[ i ] =x; (*L).len++; return(1); } 第3章串 【例3-1】已知字符串：a=“an apple”，b=“other hero”，c=“her”，求： （1）concat(substr(a,1,2),b)。 （2）replace(a,substr(a,5,1),c)。 （3）index(a,c)和index(b,c)。 解： （1）返回值为“another hero”，其中substr(a,1,2)的返回值为“an”。 （2）返回值为“an aherherle”，其中sub(a,5,1)的返回值为“p”。 （3）返回值分别为0和3。 3．串的顺序存储结构（顺序串） 串的顺序存储方式类似于线性表的顺序存储方式，其存储结构用C语言描述为：typedef struct strnode { char data[maxlen]; int len; }SeqString; //定义顺序串类型 【例3-2】设定串采用顺序存储结构，写出对串s1和串s2比较大小的算法。串值大小按字典排序（升序）方式，返回值等于-1，0和1分别表示s1 解：算法思想： （1）比较s1和s2共同长度范围内的对应字符： 若s1的字符>s2的字符，返回； 若s1的字符 若s1的字符=s2的字符，按上述规则继续比较； （2）当（1）中对应字符均相同时，比较和的长度： 两者相等时，返回0； 前者>后者时，返回1； 前者<后者时，返回-1； 算法描述如下： #define MAXLEN 256 struct strnode{ char data[MAXLEN]; int len; }SeqString; //定义顺序串类型 int strcmp(SeqString s1, SeqString s2)//比较串s1和串s2的大小 { int comlen; if (s1.len else comlen=s2.len; for(i=0;i if(s1.ch[i] else if(s1.ch[i]>s2.ch[i]) return (1); //s1>s2 if(s1.ch[i]= =s2.ch[i]) return (0); //s1=s2 else if(s1.ch[i] else return (1); //s1>s2 } 习题3 一、单项选择题 1.空串与空格字符组成的串的区别在于（1．B ）。 A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2.一个子串在包含它的主串中的位置是指（2．D）。 A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3.下面的说法中，只有（3．C ）是正确的。 A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4.两个字符串相等的条件是（4．D ）。 A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（5．B ）。 A.“ijing” B.“jing＆” C.“ingNa” D.“ing＆N” 6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（6．C）。 A.2 B.3 C.4 D.5 7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanji ng”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（7．D）。 A.“Nanjing＆Shanghai” B.“Nanjing＆Nanjing” C.“ShanghaiNanjing” D.“Shanghai＆Nanjing” 8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（8．C ）。 A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1 9.字符串采用结点大小为1的链表作为其存储结构，是指（9．D ）。 A.链表的长度为1 B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 二、填空题 1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。1. 固定长度，设置长度指针 2. 两个字符串相等的充要条件是_____________________和___________________。2. 两个串的长度相等，对应位置的字符相等 3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。3. “BCDEDE” 4. 串是指___________________。4. 含n个字符的有限序列（n≥0） 5. 空串是指___________________，空格串是指___________________。5. 不含任何字符的串，仅含空格字符的字符串 三、算法设计题 1.设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j; for(i=1;i<=m;i++) r[s+i]=r[i]; for(j=m+t-i;j<=s;j++) r[s-t+j]=r[j]; return (1); } //delete 2.设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。 2．算法思想为： （1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较； （2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较；（3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。 设单链表类型为LinkList；注意，此时类型LinkList中的data成分为字符类型。 LinkString find(s,t) LinkString *s, *t; { LinkString *ps, *pt; ps=s; while(ps!=NULL) { pt=t; while((pt!=NULL)&&(ps->data!=pt->data)) pt=pt->next; if(pt= =NULL) ps=NULL; else { ps=ps->next; s=ps; } } return s; } //find 填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入，目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 7.2. 为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树，最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间，通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素，可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不 变，都不影响其外部使用。 1.5. 一个算法具有五大特性：有穷性、确定性、可行性，有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中，判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下 排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 4.9. 下列程序判断字符串s是否对称，对称则返回1,否则返回0;如？(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0; Chap1 一、选择题 1.算法的计算量的大小称为计算的（）。 A．效率 B.复杂性 C.现实性 D.难度 2.计算机算法指的是（1），它必须具备（2）这三个特性。 (1)A．计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法 (2)A．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 3.下面关于算法说法错误的是（）。 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 4．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 5．以下数据结构中，哪一个是线性结构（）？ A．广义表 B.二叉树 C.稀疏矩阵 D.串 6．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1TO n DO FOR j:=1TO n DO x:=x+1; n) A．O(2n)B．O(n)C．O(n2)D．O(log 2 7．程序段FOR i:=n-1DOWNTO1DO FOR j:=1TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（）。 A.O（n） B.O(nlogn) C.O(n3) D.O(n2) 8．以下哪个数据结构不是多型数据类型（） A．栈B．广义表C．有向图D．字符串 9．以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 2．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。() 3．程序一定是算法。() 4．数据的物理结构是指数据在计算机内的实际存储形式。() 5.数据结构的抽象操作的定义与具体实现有关。() 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。() 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 数据结构习题集答案 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第一章习题 一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用 求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输 出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 第二章习题 1. 描述以下三个概念的区别：头指针，头结点，首元素结点。 2. 填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。 6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7. 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 《数据结构》第一章练习题 1、单项选择题 1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。 ①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像 ②A 结构 B 关系 C 运算 D 算法 1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。 ①A 算法B 数据元素C 数据操作D 逻辑结构 ②A 操作B 映像C 存储D 关系 1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系 1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A 逻辑 B 存储 C 逻辑和存储 D 物理 1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。①A 找出数据结构的合理性 B 研究算法中输入与输出的关系 C 分析算法效率以求改进 D 分析算法的易懂性和文档性 ②A 空间复杂度和时间复杂度 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 ②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性 1.8在以下的叙述中，正确的是（ ）。 A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出 1.9在决定选择何种存储结构时，一般不考虑（ ）。 、管路敷设技术通过管线不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行 高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况 ，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 数据结构习题及解答 第1章 概述 【例1-1】分析以下程序段的时间复杂度。 for(i=0;i 得：T（n）=O( n 2 log) 【例1-4】有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n<=1) return(1);① else return(n*fact(n-1));② } 解：设fact（n）的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。 由此可得fact（n）的时间复杂度为O(n)。 习题1 一、单项选择题 1.数据结构是指（1. A ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（3. D ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（4. B）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2 n) C.O(n) D.O(3n) 5.算法分析的目的是（5. C、），算法分析的两个主要方面是（A）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（6. C、），它具备输入，输出和（B）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（7. B）。 I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。(完整word版)数据结构课后习题及答案
数据结构第一章试题
经典数据结构面试题(含答案)
数据结构课后习题答案
数据结构课后习题及解析第一章
数据结构模拟卷(含答案)经典习题培训讲学
数据结构课后习题及答案
数据结构课后习题及解析第二章
数据结构模拟卷(含答案)经典习题
数据结构课后习题及解析第二章
数据结构第一章练习题
经典数据结构上机题_答案解析
数据结构各章习题及答案
数据结构例题解析(1)
数据结构习题汇编01 第一章 绪论 试题
数据结构经典题目c语言代码
严蔚敏 数据结构课后习题及答案解析