1、数据结构习题及参考答案习题1一、单项选择题1. 数据结构是指（ ）。A.数据元素的组织形式 B.数据类型C.数据存储结构 D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构3. 树形结构是数据元素之间存在一种（ ）。A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系4. 设语句x+的时间是单位时间，则以下语句的时间复杂度为（ ）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+;A.O(1) B.O() C.O(n) D.O()5. 算法分析的目的是（1），算
2、法分析的两个主要方面是（2）。（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进 D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。（1） A.计算方法 B.排序方法C.解决问题的有限运算序列 D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储
3、要（ ）。A.低 B.高 C.相同 D.不好说8. 数据结构作为一门独立的课程出现是在（ ）年。A.1946 B.1953 C.1964 D.19689. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ ）。A.正确 B.错误C.前半句对，后半句错 D.前半句错，后半句对10. 计算机内部数据处理的基本单位是（ ）。A.数据 B.数据元素 C.数据项 D.数据库二、填空题 1. 数据结构按逻辑结构可分为两大类，分别是_和_。2. 数据的逻辑结构有四种基本形态，分别是_、_、_和_。3. 线性结构反映结点间的逻辑关系是_的，非线性结构反映结点间的逻辑关系是_的。4. 一个算法的效率可分为_
4、效率和_效率。5. 在树型结构中，树根结点没有_结点，其余每个结点的有且只有_个前趋驱结点；叶子结点没有_结点；其余每个结点的后续结点可以_。6. 在图型结构中，每个结点的前趋结点数和后续结点数可以_。7. 线性结构中元素之间存在_关系；树型结构中元素之间存在_关系；图型结构中元素之间存在_关系。8. 下面程序段的时间复杂度是_。for(i=0;in;i+)for(j=0;jn;j+)Aij=0;9. 下面程序段的时间复杂度是_。i=s=0;while(sn) i+; s+=i;10. 下面程序段的时间复杂度是_。s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;s
5、um=s;11. 下面程序段的时间复杂度是_。i=1;while(i=n)i=i*3;12. 衡量算法正确性的标准通常是_。13. 算法时间复杂度的分析通常有两种方法，即_和_的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求下列程序段的时间复杂度。1. x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;2. x=0;for(i=1;in;i+)for(j=1;j=n-i;j+) x+;3. int i,j,k;for(i=0;in;i+)for(j=0;j=n;j+) cij=0;for(k=0;k=0)&Ai!=k)j-;return (i);5. fa
6、ct(n) if(n=1) return (1); else return (n*fact(n-1);习题1参考答案一、单项选择题1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B二、填空题1. 线性结构，非线性结构2. 集合，线性，树，图3. 一对一，一对多或多对多4. 时间，空间5. 前趋，一，后继，多6. 有多个7. 一对一，一对多，多对多8. O()9. O()10. O()11. O(logn)12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。13. 事后统计，事前估计三、算法设计题 1. O() 2. O()
7、3. O(n) 4. O(n) 5. O(n)习题2一、单项选择题 1. 线性表是_。A一个有限序列，可以为空 B一个有限序列，不可以为空C一个无限序列，可以为空 D一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0=inext=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-ne
8、xt; p-next-prior=s; p-next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为_。Ap-next=p-next-next; Bp=p-next;Cp=p-next-next; Dp-next=p; 7. 在一个长度为n的顺序表中向第i个元素(0 inext=p-next; p-next=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9. 以下关于线性表的说法不正确的是_。 A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元
9、素个数不是任意的。C线性表中的每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。10. 线性表的顺序存储结构是一种_的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取11. 在顺序表中，只要知道_，就可在相同时间内求出任一结点的存储地址。A基地址 B结点大小 C向量大小 D基地址和结点大小12. 在等概率情况下，顺序表的插入操作要移动_结点。 A全部 B一半 C三分之一 D四分之一13. 在_运算中，使用顺序表比链表好。 A插入 B删除 C根据序号查找 D根据元素值查找14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序
10、的时间复杂度是_。 AO(1) BO(n) CO(n2) DO(log2n)15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列_。AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 16. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为_。Atop不变 Btop=0 Ctop- Dtop+17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行_。Ahs-next=s; Bs-next=hs; hs=s;Cs-next=
11、hs-next;hs-next=s; Ds-next=hs; hs=hs-next; 18. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为_。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front 19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为_。Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front20.
12、 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为_。Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next二、填空题 1. 线性表是一种典型的_结构。2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移_个元素。3. 顺序表中逻辑上相邻的元素的物理位置_。4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位置，移动过程是从_向_依次移动每一个元素。5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关
13、系是通过_决定的。6. 在双向链表中，每个结点含有两个指针域，一个指向_结点，另一个指向_结点。7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。8. 顺序表中逻辑上相邻的元素，物理位置_相邻，单链表中逻辑上相邻的元素，物理位置_相邻。9. 线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素；对于栈只能在_位置插入和删除元素；对于队列只能在_位置插入元素和在_位置删除元素。10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_；而根据指针的联接方式，链表又可分为_和
14、_。11. 在单链表中设置头结点的作用是_。12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_，在给定值为x的结点后插入一个新结点的时间复杂度为_。 13. 对于一个栈作进栈运算时，应先判别栈是否为_，作退栈运算时，应先判别栈是否为_，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_分别设在这片内存空间的两端，这样只有当_时才产生上溢。14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, p
15、ush, push后，输出序列是_。15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为_。三、简答题 1. 描述以下三个概念的区别：头指针，头结点，表头结点。2. 线性表的两种存储结构各有哪些优缺点？3. 对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4. 对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5. 在单循环链表中设置尾指针比设置头指
16、针好吗？为什么?6. 假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7. 什么是队列的上溢现象？一般有几种解决方法，试简述之。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);四、算法设计题1. 设计在无头结点的单链表中删除第i个结点的算法。2. 在单链表上实现线性表的求表长ListLe
17、ngth(L)运算。3. 设计将带表头的链表逆置算法。4. 假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。5. 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。6. 已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max
18、但大于min的元素的算法。7. 假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：（1）向循环链队列插入一个元素值为x的结点；（2）从循环链队列中删除一个结点。8. 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。习题2参考答案一、单项选择题1A 2A 3D 4C 5D 6A 7B 8B 9C 10A 11D 12B 13C 14B 15C 16C 17B 18D 19C 20A二、填空题1线性 2n-i+1 3相邻 4前移，前，后5物理存储位置，链域的指针值 6前趋，后继7顺序，链接 8一定，不一定9线性，
19、任何，栈顶，队尾，队头10单链表，双链表，非循环链表，循环链表11使空表和非空表统一；算法处理一致12O(1)，O(n)13栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇142、315O(1)三、简答题1头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因
20、而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随
21、机存取的存储结构，而链表则是一种顺序存取的存储结构。5设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。6共有14种可能的出栈序列，即为：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7在队列的顺序存储结构中，设队头指针为fron
22、t，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法：（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。（2）要避免出现“假溢出”现象可用以下方法解决： 第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位
23、置，假定空余空间足够。 第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。 第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题 1算法思想为：（1）应判断删除位置的合法性，当in-1时，不允许进行删除操作；（2）当i=0时，删除第一个结点：（3）当in时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结
24、点的前趋结点。算法描述如下：delete(LinkList *q,int i) /在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(inext; free(s); else j=0; s=q; while(jnext;j+;if (s= =NULL) printf(Cantt delete); else p-next=s-next; free(s); 2由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：int ListLength ( LinkList *L ) /求带头结点的单链表的表长 int len=0; L
25、istList *p; p=L; while ( p-next!=NULL ) p=p-next;len+; return (len);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定义类型LinkList如下：typedef struct node int data; struct node *next,*prior;LinkList;此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点
