数据结构及应用算法教程（修订版） 第2章线性表习题.ppt

《数据结构及应用算法教程（修订版） 第2章线性表习题.ppt》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 第2章线性表习题.ppt（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第2章 线性表习题,本章要点回顾: 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,线性表的顺序存储结构具有三个弱点：一在作插入或删除操作时，需移动大量元素；二由于难以估计大小，必须预先分配较大的空间，使存储空间不能得到充分利用；三表的 容量难以扩充。 链式存储结构一般来说克服了顺序存储结构的三个

2、弱点。(1)插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；(2)不需要预先分配空间，可根据需要动态申请空间；(3)表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的 缺点。,习题 2.1 首元结点：指链表中存储线性表中第一个数据元素a1的结点； 头结点：为了操作方便，在链表的首元结点之前附设的一个结点，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一的处理； 头指针：指向链表中第一个结点（或为首元结点或为头结点）的指针。 习题 2.2 （1）表中一半 该元素的位置 （2）必定 不一定 （3）其直接前驱结点的

3、链域的值 （4）插入和删除首元素时不必进行特殊的处理,习题2.3 第1个FOR循环后: 第2个FOR循环后: 第3个FOR循环后:,L,L,L,p,注：Del_LinkList(L,i)中的i 为第i个数据元素 习题2.4 将单链表的第二个元素改为表头，第一个元素改为表尾。,习题 2.5 算法2.9（ P23） 习题 2.6/算法2.11（P25） void invert(Sqlist /for /invert,void invert(Sqlist /for /invert,习题 2.7 void ListConcat(LinkList /if /ListConcat O(Min(m,n),习

4、题 2.8 void merge(LinkList /while /merge,习题 2.9 void LinkList_Divide(LinkList /LinkList_Divide,习题 2.11 void DelMid(LinkList /Delete_Between,习题 2.12 void reverse_merge(LinkList /将B的剩余元素插入 /reverse_merge O(m+n),补充习题: 1.下列有关线性表的叙述中，正确的是（ ）。 A）线性表中元素之间的关系是线性关系 B）线性表中至少有一个元素 C）线性表中的任一元素有且仅有一个直接前趋 D）线性表中的任

5、一元素有且仅有一个直接后继 2.下述哪一条是顺序存储结构的优点？（ ） A）存储密度大 B）插入方便 C）删除方便 D）可方便地用于各种逻辑结构的存储表示 3.在一个长度为n的顺序表中，在第i个元素（1=i=n）之前插入一个新元素时需向后移动（ ）个元素。 A）1 B）n-i C）n-i-1 D）n-i+1,1.A 2.A 3. D,补充习题: 4.如果某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，那么采用（ ）存储方式最节省时间。 A）顺序表 B）单链表 C）双链表 D）循环链表 5.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均

6、要移动表中的（ ）个元素。 A）n/2 B）(n+1)/2 C）(n-1)/2 D）n 6.下述哪一条是顺序存储结构的缺点？（ ） A）存储密度太大 B）随机存取 C）一般要估计最大的需要空间 D）只能应用于少数几种逻辑结构的存储表示,4.A 5.A 6.C,补充习题: 7.在单链表中，增加头结点的目的是（ ）。 A）使单链表至少有一个结点 B）标志表中首结点的位置 C）方便运算的实现 D）说明单链表是线性表的链式存储表示 8.单链表不具有的特点是（ ）。 A)可随机访问任一元素 B)插入和删除不需要移动元素 C)不必事先估计存储空间 D)所需空间和线性表长度成正比 9.循环链表的主要优点是（

7、 ）。 A）不再需要头指针了 B）已知某个结点的位置后，能够容易找到他的直接前趋 C）在进行插入、删除运算时，能更好的保证链表不断开 D）从表中的任意结点出发都能扫描到整个链表,7.C 8.A 9.D,补充习题: 10.链表对于数据元素的插入与删除是（ ）。 A）不需移动结点，不需改变结点指针 B）不需移动结点，只需改变结点指针 C）只需移动结点，不需改变结点指针 D）既需移动结点，又需改变结点指针 11.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若要在q 和p所指结点之间插入s所指的结点,则执行（ ）。 A）s-next = p-next; p-next = s; B）q-nex

8、t = s; s-next = p; C）p-next = s; s-next = q; D）p-next = s-next; s-next = p;,10.B 11.B,补充习题: 12.向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。 A) 115 B) 114 C) 58 D) 57 13.带头结点的单链表Head为空表的判定条件是 ( ) 。 A) Head-next=Head B) Head-next=NULL C) Head!=NULL D) Head=NULL 14.若要求能快速地实现在链表的末尾插入结点和删除第一个结点的运算，则选择( )最合适。 A) 单链表 B) 带尾指针的单循环链表 C) 双链表 D) 双循环链表,12.C 13.B 14.B,补充习题: 15.给定有n个元素的向量，建立一个有序单链表的时间复杂度是( )。 A)O(n) B)O(log2n) C)O(nlog2n) D. O(n2) 16.线性表采用链式存储时，其地址( )。 A)必须是连续的 B)必须是不连续的 C)连续与否均可 D)部分地址必须是连续的 17.在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是( )。 A)O(n) B)O(log2n) C)O(1) D)O(n2),15.D 16.C 17.A,