数据结构各章习题第1章绪论一、名词解释数据数据项数据元素数据结构数据逻辑结构数据物理结构算法算法的时间复杂性二、单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。

① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。

① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象② A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。

① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5.算法指的是。

A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法6. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构三、填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、、和四种类型2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。

3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。

4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。

5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。

四、分析下列算法的时间复杂度:1．sum=0;for (i=1;i<=n;i++){sum=sum+i;}2．i=1;while(i<=n)i=i*10;3．sum=0;for(i=0;i<n;i++)for(j=0;j<n;j++)sum=sum+Array[i][j];4． s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;5． for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;6． i ＝ 0；while（i<=n）i = i * 3；第2章线性表一、单项选择题1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__ __。

A. 110B. 108C. 100D. 1202. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__ _。

A. 正确B. 不正确3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__ _。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以4. 在以下的叙述中，正确的是__ _。

A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构5.在等概率情况下，顺序表的插入操作要移动______结点。

A．全部B．一半C．三分之一D．四分之一6. 不带头结点的单链表head为空的判定条件是____。

A. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL7. 带头结点的单链表head为空的判定条件是____。

A. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL8. 非空的循环单链表head的尾结点（由p所指向）满足____。

A. p->next= =NULLB. p= =NULLC. p->next= =headD. p= =head9. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。

A. s->next=p->next; p->next=s;B. p->next=s->next; s->next=p;B. q->next=s; s->next=p;C. p->next=s; s->next=q;10. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。

A. s->next=p; p->next=s;B. s->next=p->next; p->next=s;C. s->next=p->next; p=s; C. p->next=s; s->next=p;11. 在一个单链表中，若删除p所指结点的后续结点，则执行____。

A. p->next= p->next->next；B. p= p->next; p->next= p->next->next；C. p->next= p->next;D. p= p->next->next；12. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。

A. nB. n/2C. (n-1)/2D. (n+1)/213. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__ __。

A. O(1)B. O(n)C. O (n2)D. O (nlog2n)14. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是__ __。

A. O(1)）B. O(n)C. O (n2)D. O (n*log2n)15.在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是。

A．访问第i（1<=i<=n）个结点和求第i个结点的直接前驱（1<i<=n）B．在第i（1<=i<=n）个结点后插入一个新结点C．删除第i（1<=i<=n）个结点D．以上都不对二、填空题1. 单链表可以做__ __的链接存储表示。

2. 在双链表中，每个结点有两个指针域，一个指向____ __，另一个指向___ __。

3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：q=head;while (q->next!=p) q=q->next;s= new Node; s->data=e;q->next= ; //填空s->next= ; //填空4. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p->next;p->next= _ ___; //填空delete ; //填空5. 在一个单链表p所指结点之后插入一个s所指结点，应执行s->next=__ __和p->next=__ __的操作。

6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__ __；在给定值为x的结点后插入一个新结点的时间复杂度是__ __。

三、简答1. 算法分析的目的是什么？2. 什么是算法的最坏和平均时间复杂性？3. 什么是线性表？线性表的主要运算有哪些？4. 试比较顺序表与链表的优缺点。

5. 写出在单链表L中的p所指结点之前插入一个s所指结点的操作。

四、算法题1. 设顺序表La中的数据元数递增有序。

试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

2、写算法：在顺序表L中找到最小的元素，并将其与原来第一个元素换位置，显示改变后的顺序表。

3、写算法：在单链表L中找到最小的元素，并将其与原来第一个元素换位置，显示改变后的单链表。

4. 设计一个函数，查找单链表中数值为x的结点。

5. 已知一个单链表，编写一个删除其值为x的结点的算法。

6. 已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为x 的结点，使插入后该链表仍然递增有序。

7. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2,…. an）逆置为(an, an-1,…., a1)。

8. 试写一算法，实现单链表的就地逆置(要求在原链表上进行)。

*9. 已知一个单链表，编写一个函数从此单链表中删除自第i个元素起的中k 个元素*10. 有一个共10个结点的单链表，试设计一个函数将此单链表分为两个结点数相等的单链表。

*11. 已知一个指针p指向单循环链表中的一个结点，编写一个对此单循环链表进行遍历的算法。

*12. 一个顺序表中的元素为全部为正或者负整数，试设计一算法，在尽可能少的时间内重排该表，将正、负整数分开，使顺序表中所有负整数在正整数前面。

*13. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。

试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。

第3章栈和队列一单项选择题1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是__ __。

A. edcbaB. decbaC. dceabD. abcde2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为___ _。

A. iB. n=iC. n-i+1D. 不确定3. 栈结构通常采用的两种存储结构是__ __。

4. 判定一个顺序栈ST（最多元素为m）为空的条件是___ _。

5. 判定一个顺序栈ST（最多元素为m）为栈满的条件是__ __。

6. 栈的特点是____，队列的特点是____。

A. 先进先出B. 先进后出7. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是__ __ 。

8. 判定一个循环队列Q（最多元素为m）为空的条件是 _ ___, 为满的条件是_ ___。

9. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。