文档库 最新最全的文档下载
当前位置:文档库 › 第二章 线性表

第二章 线性表

第二章 线性表
第二章 线性表

第二章线性表

一、通信录管理

1. 题目要求:

利用链表结构解决通讯录的使用问题,通过菜单实现其常用的几种功能:

1、菜单内容

程序运行后,给出6个菜单项的内容和输入提示;

1、通讯录链表的建立

2、通讯录结点的插入

3、通讯录结点的查询

4、通讯录结点的删除

5、通讯录结点的输出

0、退出管理系统

请选择0—5:

2、设计要求

使用数字0—5来选择菜单项,执行相应的操作,其他输入则不起作用。

2. 算法分析:

按照单链表的结构,设计单链表的建立、结点的插入、结点的查找、结点的删除和链表的输出等相应的子函数。为实现菜单的调用功能,需要设计一个函数用于输出提示信息和处理输入,并将返回值提供给主函数实现相应的子函数调用。

二、约瑟夫生死者游戏

1.题目要求:

约瑟夫游戏的大意是:每30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分。因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免于难。无奈,大家只能同意这种办法,并议定30个人围成一圈,由第一个人数起,依次报数,数到第9个人,便把他投入海中,然后再从他的下一个数起,数到第9人,再将他投入海中,如此循环进行,直到剩下15人为止。

要求采用单循环链表实现,利用结点的数据域存放位置。

2.算法分析:

采用单循环链表解决这一问题。将链表结点的数据域存放位置,然后将它们组成一个单循环链表。为了不失一般性,将人数用n表示,报数上限用k表示。算法描述如下:

1、创建含有n个结点的单循环链表;

2、生者与死者的选择:

p指向链表第一个结点,初始i置1;

while(i<=n/2)

{ 从p指向的结点沿链前进k-1步;

删除第k个结点(q所指向的结点);p指向q的下一个结点;

输出其位置q->data;

i自增1;

}

3、输出所有生者的位置。

三、链表的综合应用设计要求

1.题目要求:

设计一个程序,实现链表的以下功能:

1.建立单链表(头插法,不带头结点);

2.建立单链表(头插法,带头结点);

3.建立单链表(尾插法,不带头结点);

4.建立单链表(尾插法,带头结点);

5.逆置单链表;

6.有序链表插入;

7.有序链表删除重复元素;

8.无序链表删除重复元素;

9.两链表合并并排序;

10.两链表并集。

2.算法分析:

设计一个菜单,通过菜单项的调用,实现题目要求的各项功能。

四、哲学家就餐问题

1.题目要求:

一群哲学家围做在一个圆桌,从1开始编号,每人手上持有密码m。取初值m,哲学家从1开始报数,报到m的哲学家停止吃饭,退出圆桌,并取他手上的密码为新的m,继续数数。求哲学家退出的顺序。要求:n和初值m由玩家输入,手上的密码随机产生。最后要打印出编号对应的密码,输出哲学家离开的先后顺序。

2.算法分析:

可用循环链表实现,链表数据类型为结构体,记录编号和相应密码,另外设标志哲学家报数的变量mouth,它的值和哲学家嘴上报的数相等,则如果mouth和m相等,该哲学家就应该离开,离开前取他的密码交给m,同时将他的编号放另一单链表numbsave保存。注意编号要从numbsave的最后节点插入。当循环链表指向自身时停止比较,这个哲学家即是最后离开的一个。依次打印出numbsave中的数即为按编号哲学家离开的先后顺序。

五、纸牌游戏

1.题目要求:

(纸牌游戏)编号为1~52张牌,正面向上,从第二张开始,以2为基数,是2的倍数的牌翻一次,直到最后一张牌;然后从第三张牌开始,以3为基数,是3的倍数的牌翻一次,直到最后一张牌;直到以52为基数的翻过,输出:这时输出正面向上的牌有哪些?

2.算法分析:

由于翻牌时有正面向上的牌,也有反面向上的牌,而且最后要计算正面向上的牌数,所以设置了标志位key来表示正面向上的牌的编号,key=1表示正面向上,未翻牌的一直是key=1;经过翻牌就key=0,此时表示经过翻牌,属于是反面向上。设计的单链表的存储结构为:Array每个结点应包括三个域:存储该结点所对应的牌的编号信息data域、表示牌的正反面的标志的key域、存储其直接后继的存储位置的next域(指针域)。

可以使用尾插法建立单链表。因为编号为1-52的52张牌不一定存储在相邻的存储单元中,且在翻牌操作时要对编号依次进行判断,用指针来进行操作很简单。选用单链表这种数据结构来对52张牌进行链接存储。该链表中的每一个结点只有一个指针域。将编号为1到

52的结点依次链接起来,就形成了利用尾插法建立单链表的操作。

第二章线性表答案

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;

第二章 线性表习题

第二章线性表习题 判断题 1.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同。() 选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) (A)110 (B)108 (C)100 (D)120 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素。 (A)64 (B)63 (C)63.5 (D)7 4.线性表采用链式存储结构时,其地址()。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 5. 在一个单链表中,若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; 6.在一个单链表中,若删除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; 7.下列有关线性表的叙述中,正确的是() (A)线性表中的元素之间隔是线性关系 (B)线性表中至少有一个元素 (C)线性表中任何一个元素有且仅有一个直接前趋 (D)线性表中任何一个元素有且仅有一个直接后继 8.线性表是具有n个()的有限序列(n≠0) (A)表元素(B)字符(C)数据元素(D)数据项 填空题 1.已知P为单链表中的非首尾结点,在P结点后插入S结点的语句为:( ) 。 2.顺序表中逻辑上相邻的元素物理位置(一定 )相邻,单链表中逻辑上相邻的元素物理位置( )相邻。

(完整版)数据结构第二章线性表1答案

(A )需经常修改L 中的结点值 (E )需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中,哪一条是不正确的 (B ) A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 (C ) A 0( n ) B 0(1) C 0(m ) D 0(m+n ) 3 .在n 个结点的顺序表中,算法的时间复杂度是 0(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 ) 7 .链表是一种采用( B )存储结构存储的线性表。 (A )顺序 (B )链式 (C )星式 (D )网状 8 .线性表若采用链式存储结构时,要求内存中可用存储单兀的地址: (D ) (A )必须是连续的 (B )部分地址必须是连续的 (C )一定是不连续的 (D )连续或不连续都可以 9 .线性表L 在_ ( B )情况下适用于使用链式结构实现。 A ) da+(i-1)*m B ) da+i*m 6.在具有n 个结点的单链表中,实现( A )遍历链表和求链表的第 i 个结点 C )删除开始结点 C ) da-i*m D ) da+(i+1)*m A )的操作,其算法的时间复杂度为 0(n )。 B )在地址为p 的结点之后插入一个结点 D ) 删除地址为p 的结点的后继结点

第二章线性表答案

第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;

第二章 线性表 解答

第二章线性表 一、单项选择题 1、在顺序表中查找第i个元素的时间效率最高的算法的时间的复杂度是A。 A. O(1) B. O(n) C. O(log2n) D. O(n) 2、最好的情况下,在顺序表中按值查找一个元素算法时间的复杂度是 D 。 A. O(n) B. O(n) C. O(log2n) D. O(1) 3、在查找顺序表各结点概率相等的情况下,顺序按值查找某个元素的算法的时间的复杂度是 B 。 A. O(1) B. O(n) C. O(n) D. O(log2n) 4、在带有头结点的单链中插入一个新结点时不可能修改A。 A. 头指针 B. 头结点指针域 C. 开始结点指针域 D. 其它结点指针域 5、在带头结点的单链中删除由某个指针变量指向的结点的直接后继算法时间复杂度是 B 。 A. O(n) B. O(1) C. O(n) D. O(log2n) 6、在带头结点的单链中,若被删除结点位置概率相等,那么,删除第i个结点算法的时间复杂度是 D 。 A. O(1) B. O(log2n) C. O(n) D. O(n) 二、填空题 1、顺序表的存储密度是 1 ,而链式存储结构的存储密度值一定是< 1。 2、头指针的值或为NULL,或为单链表第1 个结点的地址。 3、在顺序表中按值查找一个元素的时间耗费不仅与表长有关,还与被查找元素在顺序表中的位置有关。 4、在不带头结点的单链表的结点类型为 typedef strut node{ int data; struct node * next; }TNode; 若sizeof(int)=2,sizeof(struct node *)=4,则该单链表的存储密度值为1/3 。 5、在单链表中查找第i个结点算法的时间复杂度是O(n) 。 三、基础知识 1、试描述头指针、头结点、开始结点的区别,并说明头指针和头结点的作用。 头指针是一个指针变量。若相应的链表有表头结点,则头指针指向该头结点;否则,头指针的值或者为NULL或者为开始结点的地址。

第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/3d2268090.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/3d2268090.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/3d2268090.html,st+1) //i为元素编号,有效范围在https://www.wendangku.net/doc/3d2268090.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/3d2268090.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/3d2268090.html,st>MAXLEN-1) return 0; //表满,返回0 else if(i<1 || i>https://www.wendangku.net/doc/3d2268090.html,st+2) return 1; //插入位置查处范围,返回1 else { for(k=https://www.wendangku.net/doc/3d2268090.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.wendangku.net/doc/3d2268090.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.wendangku.net/doc/3d2268090.html,st==-1) return 0; //空表,返回0 else if(i<1 || i>https://www.wendangku.net/doc/3d2268090.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.线性表L在()情况下适用于使用链式结构实现。 (A)需经常修改L中的结点值(B)需不断对L进行删除插入 (C)L中含有大量的结点(D)L中结点结构复杂 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 (maxdata) max=p->data; p=p->next; } return max; } 4. 顺序表:要将该表逆置,可以将表中的开始结点与终端结点互换,第二个结点与倒数第二个结点互换,如此反复,就可将整个表逆置了。 算法如下: // 顺序表结构定义同上题 void ReverseList( Seqlist *L) { DataType temp ; //设置临时空间用于存放data int i; for (i=0;i<=L->length/2;i++)//L->length/2为整除运算 { temp = L->data[i]; //交换数据 L -> data[ i ] = L -> data[ L -> length-1-i]; L -> data[ L -> length - 1 - i ] = temp; }

(完整版)数据结构第二章线性表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.线性表L在(B )情况下适用于使用链式结构实现。 (A)需经常修改L中的结点值(B)需不断对L进行删除插入

第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的直接后继,

第二章 线性表

第二章线性表 一、选择题 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.部分地址必须连续

第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. 线性表是________。 A.一个有限序列,可以为空B.一个有限序列,不可以为空 C.一个无限序列,可以为空D.一个无限序列,不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时,需向前移动个元素。 A.n-i B.n-i+l C.n-i-1 D.i 3. 线性表采用链式存储时,其地址________。 A.必须是连续的B.一定是不连续的 C.部分地址必须是连续的D.连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较________个元素结点。 A.n/2 B.n C.(n+1)/2 D.(n-1)/2 5. 在双向循环链表中,在p所指的结点之后插入s指针所指的结点,其操作是____。 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之后的结点(若存在),则需修改指针的操作为________。A.p->next=p->next->next; B.p=p->next; C.p=p->next->next; D.p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< inext=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. 以下关于线性表的说法不正确的是______。 A.线性表中的数据元素可以是数字、字符、记录等不同类型。 B.线性表中包含的数据元素个数不是任意的。 C.线性表中的每个结点都有且只有一个直接前趋和直接后继。 D.存在这样的线性表:表中各结点都没有直接前趋和直接后继。

相关文档
相关文档 最新文档