第二章 线性表
第二章线性表
1. 填空题
(1) 若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为1 1的(第12个)元素的存储地址为（）。
(2) 线性表的链式存储结构主要包括（）、（）和（）三种形式。
(3) 线性表的顺序存储结构是通过（）来直接反映数据元素之间的逻辑关系，而链式存储结构是通过（）间接反映数据元素之间的逻辑关系。
(4) 若对线性表进行的操作主要不是插入和删除，则该线性表宜采用（）存储结构；若频繁地对线性表进行插入和删除操作，则该线性表宜采用（）存储结构。
2. 设有一线性表e=(e1 , e2 , … , en-1 , en)，其逆线性表定义为e'=( en , en-1 ,… , e2 , e1)，请设计一个算法，将线性表置逆，要求逆线性表仍占用原线性表的空间，并且用顺序表和单链表两种方法来表示，写出不同的处理函数。
3. 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。
4. 已知线性表A的长度为n，并且采用顺序存储结构。写一算法，删除线性表中所有值为x 的元素。
5. 已知list是指向无头结点的线性链表的指针变量，写出删除该链表下标为i的(第i+1个)结点的算法。
6. 已知list是指向无头结点的线性链表的指针变量，写出删除该链表中从下标为i的(第i+1个)结点开始的连续k个结点的算法。
7. 请分别对顺序表和单链表写出求线性表中下标为i的(第i+1个)元素的前驱和后继的算法。
8. 请设计算法求线性表中第一个值为x的元素的前驱和后继的存储位置，要求采用顺序表和单链表两种方法来表示。
9. 编写一算法，删除单链表中值相同的多余结点，即：若链表中有多个结点具有相同的数
据域值，只保留其中一个结点，其余结点均从链表中删去，使得最后得到的链表中的所有结点的数据域都不相同。
10. 请设计一个算法，求出循环表中结点的个数。
11. 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
12. 设线性表X=( x1, x2, … , xn )与线性表Y=( y1 , y2 , … , ym )都采用单链式存储结构。试写一个算法归并这两个线性表为一个线性表，使
13. 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？
14. 设线性表的n个结点定义为(a0,a1,…,an-1)，重写顺序表上实现的插入和删除算法：I nsertList和DeleteList。
15. 试用顺序表作为存储结构，实现线性表(a0,a1,…,an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。
16. 设顺序表L是一个递增有序表，试写一算法将x插入L中，并使L仍是一个有序表。
上机题
1. 试将本章介绍的两种Josephus问题的求解过程在计算机中实现，实现时要求输出的不是
整数，而是实际的人名。
2. 设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针。
请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。
第二章线性表答案
2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=&(va.elem[0]); while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置 for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK; }//OrderListInsert-sq Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=&(va.elem[va.length-1]); while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length;
第二章线性表答案
第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方 便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元 素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF
A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF
第二章线性表习题及答案
第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L;
第2章线性表习题解析(答)
第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;
7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用
第2章线性表习题解答
第2章习题 (1) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.wendangku.net/doc/d75409282.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/d75409282.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/d75409282.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/d75409282.html,st+1之间 return false; else { x=S.data[i-1]; return true; }
} //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/d75409282.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出} return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) { int k; if(https://www.wendangku.net/doc/d75409282.html,st>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>https://www.wendangku.net/doc/d75409282.html,st+2) return 1; //插入位置查处范围，返回1 else { for(k=https://www.wendangku.net/doc/d75409282.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.wendangku.net/doc/d75409282.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.wendangku.net/doc/d75409282.html,st==-1) return 0; //空表，返回0 else if(i<1 || i>https://www.wendangku.net/doc/d75409282.html,st+1) return 1; //删除元素编号超出范围，返回1 else
数据结构第二章线性表1习题
线性表专题 一、选择题 1．关于顺序存储的叙述中,哪一条是不正确的( ) A.存储密度大 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第i个结点的位置 D.插入、删除操作不方便 2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( ) A O(n) B O(1) C O(m) D O(m+n) 3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( ) A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n） B 在第i个结点（1<=i<=n）后插入一个新结点 C 删除第i个结点（1<=i<=n） D 将n个结点从小到大排序 4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( ) （A ）110 （ B ）108 （C ）100 （D ）120 5．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m 6．在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度为O(n)。 A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点 C）删除开始结点D）删除地址为p的结点的后继结点 7．链表是一种采用（）存储结构存储的线性表。 （ A ）顺序（B ）链式（ C ）星式（D ）网状 8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（） （ A ）必须是连续的（ B ）部分地址必须是连续的 （ C ）一定是不连续的（ D ）连续或不连续都可以 9．线性表Ｌ在（）情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( )
第二章_线性表(参考答案)
第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型，树形结构和图形结构合称为非线性结构。 2、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有个前驱结点，最后一个结点没有后续结点，其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置一定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 5、在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是（（4）、（1））； B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））； C、在表首插入S结点的语句序列是（（5）、（12））；
第二章-线性表-自测题-自测题答案
第二章-线性表-自测题-自测题答 案 一、填空(每空1分，共13分) 1. 【严题集 2.2①】在顺序表中插入或删除一个元素，需要平均移动 _表中一半元素，具体移动的元素个数与_表长和该元素在表中的位置 _有关。 2. 线性表中结点的集合是—有限—的，结点间的关系是—一对一的。 3. 向一个长度为n的向量的第i个元素(K i < n+1)之前插入一个元素时，需向后移动_n-i+1 _个兀素。 4. 向一个长度为n的向量中删除第i个元素(K i < n)时，需向前移动_n-i .个 5. 在顺序表中访问任意一结点的时间复杂度均为0(1)_，因此，顺序表也 称为—随机存取—的数据结构。 6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置—必定相邻。单链 表中逻辑上相邻的元素的物理位置不一定相邻。 7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由_其直接前驱结点的链域的值—指示。 8. 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为0 (n)。
二、判断正误(在正确的说法后面打勾，反之打叉)(每小题1分，共10分) (X ) 1.链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。 例如，双向链表中的结点可以含有两个指针域，分别存放指向其 直接前趋和直接后继结点的指针。 (X ) 2.链表的物理存储结构具有同链表一样的顺序。 错，链表的存储结构特点是无序，而链表的示意图有序。 (X ) 3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 错，链表的结点不会移动，只是指针内容改变。 X ) 4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存 放记录型数据。 (X ) 5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” (x ) 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储 的优点。顺序存储方式插入、删除运算效率较低，在 表长为n的顺序表中，插入和删除一个数据元素，平 均需移动表长一半个数的数据元素。 (x ) 7.线性表在物理存储空间中也一定是连续的。错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 (x ) 8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑 上相邻的元素在存储的物理位置次序上也相邻。 (x ) 9?顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可 以用来存放非线性结构，例如完全二叉树是属于非线 性结构，但其最佳存储方式是顺序存储方式。(后一节 介绍) (x ) 10.线性表的逻辑顺序与存储顺序总是一致的。错，理由同7。链式存储就无需一致。 三、单项选择题(每小题1分，共10分) (C ) 1 ?数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： (A )存储结构(B)逻辑结构 (C)顺序存储结构(D)链式存储结构 (B ) 2.—个向量第一个元素的存储地址是100,每个元素的长度为2, 则第5个元素的地址是__________________________ (A)110 (B) 108 (C) 100 (D) 120 (A ) 3.在n个结点的顺序表中，算法的时间复杂度是0(1)的操作是： (A)访问第i个结点(Ki< n)和求第i个结点的直接前驱(2 < i < n)
第2章线性表习题参考答案
一、选择题 1. D 2. B 3. B 4. B 5. B 6. B 7. D 8. B 9. C 10. B 11. C 12. C 13. B 14. D 15. A 16. B 17. B 18. C 19. A 20. C 21. D 22. A 23. A 24. A 二、填空题 1. 首元素其直接前驱结点的链域的值 2. HL→next =NULL； HL=HL→next 3. 有限、一对一 4. O(1) 随机存取 5. 表中一半表长和该元素在表中的位置 6. 必定不一定 7. O（1） O（n） 8. 前驱结点的地址 O（n） 9. n-i+1 n-i 10. s->left=p p->right 三、判断题 1. × 2. × 3. × 4. × 5. × 6. × 7. √ 8. × 9. × 10. × 11. × 四、简答题 1. 线性表为：（78，50，40，60，34，90） 2. (36, 12, 8, 50, 25, 5, 15) 3. 解答： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear, 查找时间都是O(1)。
若用头指针来表示该链表，则查找终端结点的时间为O(n)。 五、编程题 1. 解答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下： int ListLength ( LinkList L ) { int len=0 ; ListNode *p; p=L; //设该表有头结点 while ( p->next ) { p=p->next; len++; } return len; } 2. int searchmin(linklist l) { int min; int *p; p=l; min=p->data; p=p->next; while (p->next< >nil) { if (min>p->data) min=p->data; p=p->next; } return min; } 3. int searchmax(linklist l) { int max; int *p; p=l; max=p->data; p=p->next; while (p->next< >nil) { if (max
(完整版)数据结构第二章线性表1答案
第二部分线性表 一、选择题 1．关于顺序存储的叙述中,哪一条是不正确的( B ) A.存储密度大 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第i个结点的位置 D.插入、删除操作不方便 2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( C ) A O(n) B O(1) C O(m) D O(m+n) 3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( A ) A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n） B 在第i个结点（1<=i<=n）后插入一个新结点 C 删除第i个结点（1<=i<=n） D 将n个结点从小到大排序 4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( B ) （A ）110 （ B ）108 （C ）100 （D ）120 5．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( A ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m 6．在具有n个结点的单链表中，实现（A ）的操作，其算法的时间复杂度为O(n)。 A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点 C）删除开始结点D）删除地址为p的结点的后继结点 7．链表是一种采用（B ）存储结构存储的线性表。 （A ）顺序（B ）链式（ C ）星式（D ）网状 8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（D ）（A ）必须是连续的（ B ）部分地址必须是连续的 （C ）一定是不连续的（ D ）连续或不连续都可以 9．线性表Ｌ在（B ）情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入
第2章 线性表习题及参考答案
第二章线性表习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 4．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 6．循环链表的主要优点是( )。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 7．下面关于线性表的叙述错误的是( )。 (A)线性表采用顺序存储，必须占用一片地址连续的单元；
第二章线性表作业
第二章线性表(作业) 一、判断题 1.线性表的逻辑顺序与物理顺序总是一致的。 2.线性表的顺序存储表示优于链式存储表示。 3.线性表若采用链式存储表示。时所有存储单元的地址可连续可不连续。 4.每种数据结构都应具备三种基本运算：插入、删除和搜索。 5.线性表的特点是每个元素都有一个前驱和一个后继。 6.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 二、填空题 1.线性表（a1,a2,…,an）有两种存储结构：（）和（）。（）存储密度较大，（）存储利用率较高，（）可随机存取，（）不可随机存取，（）插入和删除操作比较方便。 2.在单链表中，删除指针p所指结点的后继结点的语句是：（） 3.带头结点的单循环链表Head的判空条件是（）。 4.画出下列数据结构的图示：①顺序表②单链表③双链表④循环链表 5.在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动（）个元素。
6.对于双向链表,在两个结点之间插入一个新结点需修改的指针共（）个，单链表为（）个。 7.带头结点的双循环链表L中只有一个元素结点的条件是：（） 8.在单链表L中，指针p所指结点有后继结点的条件是：（） 9.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（）存储结构。 10.链接存储的特点是利用（）来表示数据元素之间的逻辑关系。 三、选择题 1.设单链表中结点的结构为（data,next）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？ 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; 2.设单链表中结点的结构为（data,next）。已知指针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; D：p-> next =s; s-> next =p; 3.设单链表中结点的结构为（data,next）。若想摘除结点*p的直接后继，
第2章线性表题目
第2章自测卷答案 一、填空 1.在顺序表中插入或删除一个元素，需要平均移动线性表长度的一半个元素，具体移动的元素个数与插入位置或删除位置和线性表的长度有关。 2. 线性表中结点的集合是有序的的，结点间的关系是独立的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i个元素。 三、单项选择题 1、线性表是（C ）的有限序列。 A、数据 B、数据项 C、数据元素 D、表元素 2、以下关于线性表的说法不正确的是（C ）。 A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前驱和直接后继。 D、存在这样的线性表：表中各结点都没有直接前驱和直接后继。 3、顺序表是线性表的（B ）。 A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构 4、对于顺序表的优缺点，以下说法错误的是（C ）。 A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插人和删除运算较方便 D、容易造成一部分空间长期闲置而得不到充分利用 5、在顺序表中，只要知道（D），就可在相同时间内求出任一结点的存储地址。 A、基地址 B、结点存储长度 C、向量大小 D、基地址和存储长度 6、一个顺序表第一个元素的存储地址是100，每个元素的存储长度为4，则第5个元素的地址是（B）。 A、110 B、116 C、100 D、120 7、一个长度为n的顺序表中，在第i（1≤i≤n+1）个元素的位置上插入一个新元素时，需要向后移动个元素。（B） A、n-i B、n-i+1 C、n-i-1 D、i 8、一个长度为n的顺序表中，删除第i（1≤i≤n）个元素时，需要向前移动（A）个元素。
第二章 线性表
第二章线性表 一、选择题 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．112 B.144 C.148 D.412 5. 线性表是__A____。 A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__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-i B．n+i C．n-i+1 D．n-i-1 8．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____C____个元素。 A.n/2 B.（n+1）/2 C.（n-1）/2 D.n 9．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为__C____。（1≤i≤n+1） A．O（0） B．O（1）C．O（n） D．O（n2）10．线性表中各链接点之间的地址___C____。 A．必须连续B．部分地址必须连续
第二章线性表
第二章线性表 1．什么是顺序存储结构？什么是链式存储结构？ 线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素，它的特点是，线性表中相邻的元素a[i]和a[i+1]赋以相邻的存储位置LOC(a i) 和LOC(a i+ 1 ) 。即，以元素在计算机内"物理位置相邻"来表示线性表中数据元素之间的逻辑关系。简言之逻辑相邻，物理相邻。相邻元素之间查一个元素所占的物理空间，因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 线性量的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的) . 因此，为了表示每个数据元素a i与其直接后继数据元素a i+ 1之间的逻辑关系，对数据元素a i来说，除了存储其本身的信息之外，还需存储-个指示其直接后继的信息〈即直接接后继的存储位置〉. 这两部份信息组成数据元素a i的存储映映像，称为结点(node) . 它包括两个域:其中存储数据元素信息的称为数据域，存储直接后继存储位置的域称为指针域. 指针域中存储的信息称做指针或链. 2．线性表的顺序存储结构和链式存储结构各有什么特点？ 顺序存储结构，逻辑相邻的元素，物理上也相邻，每个结点只需存储数据本身，不许存储逻辑关系，节约存储空间，查找元素方便，但插入或删除元素需要大量移动元素，效率低。适合查找多但插入删除少的情况。 链式存储结构，逻辑上相邻的元素，物理上不一定相邻，每个结点除了存储元素本身外，还要存储元素之间的逻辑关系，占用存储空间大，但查找元素都要从头
第2章线性表习题参考答案
习题二参考答案 一、选择题 1.链式存储结构的最大优点是（D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 2.假设在顺序表{a0,a1,……,a n－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址 为100，则第7个数据元素的存储地址是（ D ）。 A.106 B. 107 C.124 D.128 3.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 4.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（C ）存储方 式。 A.顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表 5.在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是 （D ）。 A.s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是 （C ）。 A.O(1) B. O(log2n) C. O(n) D. O(n2)
7. 要将一个顺序表{a 0,a 1,……,a n-1}中第i 个数据元素a i (0≤i ≤n-1)删除，需要移动（ B ）个数据元素。 A. i B. n-i-1 C. n-i D. n-i+1 8. 在带头结点的双向循环链表中的p 结点之后插入一个新结点s ，其修改链的java 语句序列是（ D ）。 A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s); D. s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s); p.setNext(s); 9. 顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。 A ．小于1 B. 等于1 C. 大于1 D. 不能确定 10. 对于图2.29所示的单链表，下列表达式值为真的是（ D ）。 图2.29 单链表head 的存储结构图 A. head.getNext().getData()=='C' B. head.getData()=='B' C. P 1.getData()==’D ’ D. P 2.getNext()==null 二、填空题 1. 线性表是由n （n ≥0）个数据元素所构成的 有限序列 ，其中n 为数据元素的个数，称为线性表的 长度 ， n=0的线性表称为 空表 。
第二章线性表答案
第2章线性表 选择题 1 ?下述哪一条是顺序存储结构的优点？（ A ） A ?存储密度大 B ?插入运算方便 C ?删除运算方便 D ?可方便地用于各种逻辑结构的 存储表示 2 .下面关于线性表的叙述中，错误的是哪一个？（ B ） A ?线性表采用顺序存储，必须占用一片连续的存储单元。 B ?线性表采用顺序存储，便于进行插入和删除操作。 C ?线性表采用链接存储，不必占用一片连续的存储单元。 D ?线性表采用链接存储，便于插入和删除操作。 3 .线性表是具有n个（C）的有限序列（n>0 ）。 A .表元素 B .字符 C .数据元素 D .数据项 E.信息项 4 ?若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 （A ）存储方式最节省时间。 A .顺序表 B .双链表 C .带头结点的双循环链表 D .单循环链表 5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。 A. 单链表 B.仅有头指针的单循环链表 C.双链表 D .仅有尾指针的单循环 链表 6 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（D ）最节省时间。 A.单链表 B.单循环链表 C.带尾指针的单循环链表 D.带头结点的双循环链表 7 .若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用 （D ）存储方式最节省运算时间。 A.单链表 B .双链表 C .单循环链表 D .带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A.内存地址 B .数组下标 C .下一元素地址 D .左、右孩子地址 9. 链表不具有的特点是（ C ） A .插入、删除不需要移动元素 B .可随机访问任一元素 C .不必事先估计存储空间 D .所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A.线性表在链式存储时，查找第i个元素的时间同i的值成正比
第2章线性表自测题
第2章自测题 一、填空 1.在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 2. 线性表中结点的集合是的，结点间的关系是的。 3. 在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。 4.顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。 5.在单链表中，除了首元结点外，任一结点的存储位置由指示。 6．在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。 二、单项选择题 （）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （）5. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C）只有一部分，存储表示结点间关系的指针 （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （）6. 链表是一种采用存储结构存储的线性表； （A）顺序（B）链式（C）星式（D）网状 （）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的（B）部分地址必须是连续的 （C）一定是不连续的（D）连续或不连续都可以 （）8．线性表Ｌ在情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 （）9．单链表的存储密度 （Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定