第2章线性表
一、填空题
1、线性结构反映结点间的逻辑关系是一对一的。
2、线性结构的特点：
1）只有一个首结点和尾结点
2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继
3、线性表的顺序表示又称为顺序存储结构。
4、结点只有一个指针域的链表，称为单链表。
5、首尾相接的链表称为循环链表。
6、线性表的链式表示又称为非顺序映像。
7、指向链表中第一个结点的指针称为头指针。
8、链表中存储第一个数据元素的结点称为首元结点。
二、判断题
1、线性表的逻辑顺序与存储顺序总是一致的。（╳）
2、顺序存储的线性表可以按序号随机存取。（√）
3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（╳）
4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）
5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（╳）
6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）
7、线性表的链式存储结构优于顺序存储结构。（╳）
8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）
9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）
10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（╳）
11、线性表的特点是每个元素都有一个前驱和一个后继。（╳）
三、单项选择题
1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。
A．110 B．108 C．100 D．120
解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
2、在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个结点从小到大排序
解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
3、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（B）。
A．8 B．63.5 C．63 D．7
解释：平均要移动的元素个数为：n/2。
4、链接存储的存储结构所占存储空间（A）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数
5、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续或不连续都可以
6、线性表Ｌ在（B）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入
C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂
解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
7、单链表的存储密度（C）。
A．大于1 B．等于1 C．小于1 D．不能确定
解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。
8、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（A）。
A．n B．2n-1 C．2n D．n-1
解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。
9、在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（B）个元素。
A．n-i B．n-i+1 C．n-i-1 D．I
10、线性表L=(a1，a2,……a n)，下列说法正确的是（D）。
A．每个元素都有一个直接前驱和一个直接后继
B．线性表中至少有一个元素
C．表中诸元素的排列必须是由小到大或由大到小
D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
11、创建一个包括n个结点的有序单链表的时间复杂度是（C）。
A．O(1) B．O(n) C．O(n2) D．O(nlog2n)
解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。
12、以下说法错误的是（D）。
A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B．顺序存储的线性表可以随机存取
C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D．线性表的链式存储结构优于顺序存储结构
解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。
13、在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（D）。
A．s->next=p+1; p->next=s;
B．(*p).next=s; (*s).next=(*p).next;
C．s->next=p->next; p->next=s->next;
D．s->next=p->next; p->next=s;
14、在双向链表存储结构中，删除p所指的结点时须修改指针（A）。
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;
15、在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（C）。
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->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
四、应用题
1、假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占４个字节。问下列元素的存储地址是什么？
(1) a0000 100
(2)a1111 100+(1*3*5*8+1*5*8+1*8+1)*4=776
(3)a3125 100+(3*3*5*8+1*5*8+2*8+5)*4=1784
(4)a8247 100+(8*3*5*8+2*5*8+4*8+7)*4=4416
四、算法设计题
1、已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。
void DelElem(ElemType Sqlist[],int &n,int i){
int j;
if(i<1||i>n)
exit(0) /*非法删除*/
for(j=i;j Sqlist[j-1]=Sqlist[j]; /*将第i位置,以后的元素依次前移*/
n--; /*表长减1*/
}
2、请在下划线中填写语句，完成在双向链表中插入数据的算法：
typedef struct DulNode
{
ElemType data;
struct DulNode *prior;
struct DulNode *next;
} DulNode, *DuLinkList;
status ListInsert_Dul(DuLinkList &L , int i ,ElemType &e)
{
if (!(p=GetElem_Dul(L,i)))
return ERROR;
s=new DulNode;
s->data=e;
___ s->prior=p->prior;________;
___ p->prior->next=s;_____ ___;
__ _s->next=p;____ ______;
____p->prior=s;_____________;
return OK;
}//ListInsert_Dul
3、请在下划线中填写语句，完成单链表插入算法。
{
;
∗;
},∗;
Status ListInsert(LinkList &L,int i,ElemType e)
{
p=L;j=0;
while(p&&(j
if(!p||j>i−1)return ERROR;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
第2章线性表 线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。 重点提示： ●线性表的逻辑结构特征 ●线性表的顺序存储和链式存储两种存储结构的特点 ●在两种存储结构下基本操作的实现 2-1 重点难点指导 2-1-1 相关术语 1．线性表 线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。 要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。 2．顺序表 顺序存储的线性表。 要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。 3．链表 用链表存储的线性表。 要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。 4．单链表 每个结点除了数据域外还有一个指向其后继的指针域。 要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。 5．头指针 要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。 6．头结点 要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学 2000 一、1（2分）】 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】 A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】 A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 11. 线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。 供选择的答案： A.连续 B.单向链接 C.双向链接 D.不连接 E.循环链接 F.树状 G.网状 H.随机 I.顺序 J.顺序循环 【上海海运学院 1995 二、1（5分）】 12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
第二章线性表 一、填空题 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））；
第2章线性表 一、选择题 1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删 除一个元素需要移动的元素个数为（）。【＊＊，★】 A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/2 2.线性表是具有N 个（）的有限序列。【＊】 A、表元素 B、字符 C、数据元素 D、数据项 E、信息 3.“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（）。【＊】 A、正确的 B、错误的 C、不一定，与具体结构有关。 4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。【＊，★】 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。 5.带头结点的单链表为空的判定条件是（）。【＊】 A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 6.不带头结点的单链表head 为空的判定条件是（）。【＊】 A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 7.非空的循环单链表head 的尾结点P 满足（）。（注:带头结点）【＊】 A、P->NEXT=NULL B、p=NULL C、p->next==head D、p==head 8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。【＊，★】 A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9.在一个单链表中，若删除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; 10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。【＊，★】
第 2 章线性表 课后习题讲解 1. 填空 ⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。 【解答】表长的一半，表长，该元素在表中的位置 ⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108 ⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。 【解答】p->next=(p->next)->next ⑷单链表中设置头结点的作用是（）。 【解答】为了运算方便 【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 ⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。 【解答】p->next=head 【分析】如图2-8所示。 ⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。 【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图2-9所示：
⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。 【解答】Ο(1)，Ο(n) 【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。 ⑻可由一个尾指针唯一确定的链表有（）、（）、（）。 【解答】循环链表，循环双链表，双链表 2. 选择题 ⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】参见2.2.1。 ⑵线性表采用链接存储时，其地址（）。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。 ⑶单循环链表的主要优点是（）。 A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表； C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。 【解答】B ⑷链表不具有的特点是（）。 A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 【解答】A ⑸若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表 【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。 ⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表
《数据结构》 第二章线性表习题 一、单项选择题 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< i
第2章线性表 一、填空题 1、线性结构反映结点间的逻辑关系是一对一的。 2、线性结构的特点： 1）只有一个首结点和尾结点 2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继 3、线性表的顺序表示又称为顺序存储结构。 4、结点只有一个指针域的链表，称为单链表。 5、首尾相接的链表称为循环链表。 6、线性表的链式表示又称为非顺序映像。 7、指向链表中第一个结点的指针称为头指针。 8、链表中存储第一个数据元素的结点称为首元结点。 二、判断题 1、线性表的逻辑顺序与存储顺序总是一致的。（╳） 2、顺序存储的线性表可以按序号随机存取。（√） 3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（╳） 4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（╳） 6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√） 7、线性表的链式存储结构优于顺序存储结构。（╳） 8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√） 10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（╳） 11、线性表的特点是每个元素都有一个前驱和一个后继。（╳） 三、单项选择题 1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。 A．110 B．108 C．100 D．120 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 2、在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个结点从小到大排序 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
数据结构第二章线性表 基本信息：[矩阵文本题] * 1. 在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为 [单选题] * A．n-i+1(正确答案) B．n-i C．i D．i-1 2. 若一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么，第6个元素的存储地址应是 [单选题] * A．1020(正确答案) B．1010 C．1016 D．1024 3. 带头结点的单链表（以head为头指针）为空的判断条件是 [单选题] *
A．head!=NULL B．head->next==head C．head->next==NULL(正确答案) D．head ==NULL 4. 将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为 [单选题] * A．O(1) B．O(m)(正确答案) C．O(n) D．O(m+n) 5. 在一个单链表中，若删除p指向结点的后继结点，则执行的操作为 [单选题] * A．q=p->next；p->next=p->next->next；free(q)；(正确答案) B．p=p->next；q=p->next；p=q->next；free(q)； C．q=p->next->next；p=p->next；free(q)； D．p=p->next->next；q=p->next；free(q)； 6. 线性表是一个有限序列，组成线性表的基本单位是 [单选题] * A．数据项 B．数据元素(正确答案) C．数据域
D．字符 7. 顺序表便于 [单选题] * A．插入结点 B．删除结点 C．按值查找结点 D．按序号查找结点(正确答案) 8. 对需要频繁插入和删除结点的线性表，适合的存储方式是 [单选题] * A．顺序储存 B．链式存储(正确答案) C．索引存储 D．散列存储 9. 设带头结点的单循环链表的头指针为head，指针变量p指向尾结点的条件是 [单选题] * A．p->next->next==head B．p->next==head(正确答案) C．p->next->next==NULL D．p->next==NULL 10. 针对线性表逻辑上相邻的两个元素，下列叙述中，正确的是 [单选题] * A．采用顺序存储时一定相邻，采用链式存储时也一定相邻
数据结构第二章线性表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 ）情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( A ) A.n-i+1 B.n-i C.i D.i-1 11．线性表是（A）。 a、一个有限系列，可以为空 b、一个有限系列，不能为空 c、一个无限系列，可以为空 d、一个无限系列，不能为空 12. （A）线性表。 A.(孔子,诸葛亮,曹雪芹) B.{A,B,C,D} C.{10,11,12,13,14} D.(1,2,3,...) 13. （）是表示线性数据结构的。 A.循环链表 B.邻接多重表
《数据结构》教材课后习题+答案数据结构 第一章介绍 数据结构是计算机科学中重要的概念，它涉及到组织和存储数据的方法和技术。数据结构的选择对于算法的效率有着重要的影响。本教材为读者提供了丰富的课后习题，以帮助读者巩固所学知识并提高解决问题的能力。下面是一些选定的习题及其答案，供读者参考。 第二章线性表 习题一： 给定一个顺序表L，编写一个算法，实现将其中元素逆置的功能。 答案一： 算法思路： 1. 初始化两个指针i和j，分别指向线性表L的首尾两个元素 2. 对于L中的每一个元素，通过交换i和j所指向的元素，将元素逆置 3. 当i>=j时，停止逆置 算法实现： ```python
def reverse_list(L): i, j = 0, len(L)-1 while i < j: L[i], L[j] = L[j], L[i] i += 1 j -= 1 ``` 习题二： 给定两个线性表A和B，编写一个算法，将线性表B中的元素按顺序插入到线性表A中。 答案二： 算法思路： 1. 遍历线性表B中的每一个元素 2. 将B中的元素依次插入到A的末尾 算法实现： ```python def merge_lists(A, B): for element in B: A.append(element)
``` 第三章栈和队列 习题一： 编写一个算法，判断一个表达式中的括号是否匹配。表达式中的括号包括小括号"()"、中括号"[]"和大括号"{}"。 答案一： 算法思路： 1. 遍历表达式中的每一个字符 2. 当遇到左括号时，将其推入栈中 3. 当遇到右括号时，判断栈顶元素是否与其匹配 4. 当遇到其他字符时，继续遍历下一个字符 5. 最后判断栈是否为空，若为空则表示括号匹配 算法实现： ```python def is_matching(expression): stack = [] for char in expression: if char in "([{":
数据结构(第二版)课后习题答案第一章：数据结构概述 数据结构是计算机科学中非常重要的一个概念，它用于组织和管理计算机内部存储的数据。数据结构的设计直接影响到程序的运行效率和对真实世界问题的建模能力。第二版的《数据结构》教材旨在帮助读者更好地理解和应用数据结构。为了提高学习效果，每章节后都附有一系列习题。本文将为第二版《数据结构》教材中的部分习题提供详细的答案和解析。 第二章：线性表 2.1 顺序表 习题1：请问如何判断顺序表是否为空表？ 答案：当顺序表的长度为0时，即为空表。 解析：顺序表是用一块连续的内存空间存储数据元素的线性结构。当顺序表中没有元素时，长度为0，即为空表。 习题2：如何求顺序表中第i个元素的值？ 答案：可以通过访问顺序表的第i-1个位置来获取第i个元素的值。 解析：顺序表中的元素在内存中是连续存储的，通过下标访问元素时，需要将下标减1，因为数组是从0开始编号的。 2.2 链表
习题1：请问链表中的结点包含哪些信息？ 答案：链表的结点一般包含两部分信息：数据域和指针域。 解析：数据域用于存储数据元素的值，指针域用于存储指向下一个 结点的指针。 习题2：如何删除链表中的一个结点？ 答案：删除链表中的一个结点需要将其前一个结点的指针指向其后 一个结点，然后释放被删除结点的内存空间。 解析：链表的删除操作相对简单，只需要通过修改指针的指向即可。但需要注意释放被删除结点的内存空间，防止内存泄漏。 第三章：栈和队列 3.1 栈 习题1：如何判断栈是否为空？ 答案：当栈中没有任何元素时，即为空栈。 解析：栈是一种先进后出（Last In First Out，LIFO）的数据结构， 栈顶指针指向栈顶元素。当栈中没有元素时，栈顶指针为空。 习题2：请问入栈和出栈操作的时间复杂度是多少？ 答案：入栈和出栈操作的时间复杂度均为O(1)。 解析：栈的入栈和出栈操作只涉及栈顶指针的改变，不受栈中元素 数量的影响，因此时间复杂度为O(1)。
第二章线性表：习题 习题 一、选择题 1．L是线性表，已知Length(L)的值是5，经运算？Delete(L，2)后，length(L)的值是( c)。 A.5 B.0 C.4 D.6 2．线性表中，只有一个直接前驱和一个直接后继的是( )。 A．首元素 B.尾元素 C．中间的元素 D.所有的元素 +3．带头结点的单链表为空的判定条件是( )。 A. head= =NULL B. head->next= =NULL C. head->next=head D. head!=NULL 4．不带头结点的单链表head为空的判定条件是( )。 A. head=NULL B. head->next =NULL C.head->next=head D. head!=NULL 5．非空的循环单链表head的尾结点P满足()。 A. p->next = =NULL B. p=NULL C. p->next==head D. p= =head 6．线性表中各元素之间的关系是( c)关系。 A.层次 B.网状C．有序 D.集合 7.在循环链表的一个结点中有（）个指针。 A．1B．2 C. 0 D. 3 8.在单链表的一个结点中有（）个指针。 A．1B．2 C. 0 D. 3 9.在双链表的一个结点中有（）个指针。 A．1B．2 C. 0 D. 3 10.在一个单链表中，若删除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; 11.指针P指向循环链表L的首元素的条件是（）。 A．P= =L B. P->next= =L C. L->next=P D. P-> next= =NU LL 12. 在一个单链表中，若在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;
第二章线性表 2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 并说明头指针和头结点的作用。 答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。 开始结点指第一个元素结点。 头指针的作用是用来惟一标识一个单链表。 头结点的作用有两个：一是使得对空表和非空表的处理得以统一。二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。 2.2填空题 1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。 2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。单链表中逻辑上相邻的元素的物理位置（不一定）相邻。 3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。 4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。 2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在
第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置 由 指示，首元素结点的 存 储位置由指示，除首元素结点外，其它任一元素结点的存储位 置由指示。 3．已知 L 是无表头结点的单链表， 且P 结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序 列。 a. 在 P 结点后插入 S 结点的语句序列是：。 b. 在 P 结点前插入 S 结点的语句序列是：。 c. 在表首插入 S结点的语句序列 是：。 d. 在表尾插入 S 结点的语句序列 是：。 供选择的语句有： （1） P->next=S; （2） P->next= P->next->next; （3） P->next= S->next; （4） S->next= P->next; （5） S->next= L; （6） S->next= NULL; （7） Q= P; （8） while(P->next!=Q) P=P->next; （9） while(P->next!=NULL) P=P->next; （10） P= Q; （11） P= L; （12） L= S; （13） L= P; 4. 设线性表存于 a(1:arrsize)的前 elenum 个分量中且递增有序。试写一算 法，将 X 插入 到 线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i 个元素开始 的k 个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高 效算法，删除表中所有大于mink 且小于 maxk 的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将 线性表（a1, a2..., an）逆置为（ an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前 elenum 个分量中。 （2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表 A 和 B，均以单链表作为存储结构，请编写算法，将 A 表和 B 表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即 A
数据结构与算法上机作业第二章线性表
一、选择题 1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为 C 。 A. O(log2n) B. O(1) C. O(n) D. O(n2) 2、以下关于线性表的说法中，不正确的是 C 。 A. 线性表中的数据元素可以是数字、字符、结构等不同类型 B. 线性表中包含的数据元素个数不是任意的 C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继 D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继 3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 B 。 A. O(1) B. O(n) C. O(n2) D. O(log2n) 4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 C 。提示：插入的位置有n+1个，移动总数为：1+2+3+……+n A. n B. (n-1)/2 C. n/2 D. (n+1)/2 5、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 C 。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 6、在顺序表中，只要知道 D ，就可以求出任一结点的存储地址。 A. 基地址 B. 结点大小 C. 向量大小 D. 基地址和结点大小 7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 A 。 A. n B. 2n-1 C. 2n D. n-1 8、线性表采用链表存储时其存储地址要求 D 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 必须是不连续的 D. 连续的和不连续的都可以 9、下面关于线性表的描述中，错误的是 B 。 A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作 C. 线性表采用链式存储，不必占用一片连续的存储单元 D. 线性表采用链式存储，便于插入和删除操作 10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 B A. O(1) B. O(n) C. O(n2) D. O(log2n) 11、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是 D 。 A. HL=p; p->next=HL; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p; 12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是C 。 A. p=q->next; p->next=q->next; B. p=q->next; q->next=p; C. p=q->next; q->next=p->next; D. q->next=q->next->next; q->next=q; 13、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 D 。 A. 1234 B. 1243 C. 1324 D. 1423 14、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是B 。
2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i]
} } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 《数据结构》各章课后作业答案 第一章 绪论课后作业答案 1. 简述线性结构与非线性结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。 2．分析下面各程序段的时间复杂度（每小题5分，共20分） 解：1.第一个for 循环执行n+1次，第二个for 循环执行n(m+1)次，A[i][j]=0;语句执行n*m 次，此程序段总的执行次数为n+1+n*(m+1)+n*m=2nm+2n+1次。故时间复杂度为O(n*m)。 2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为： s+=B[i][j]; 它的执行次数为n 2，所以本程序段的时间复杂度是O(n 2 )。 3. 该算法的基本操作是语句x++, 其语句频度为： 111 1n n i i j --==∑∑=10 ()n i n i -=-∑= (1) 2 n n - 所以本程序段的时间复杂度是O(n 2 )。 4.设语句执行m 次，则有 3m ≤n ⇒m ≤log 3n 所以本程序段的时间复杂度为O(log 3n)。 第二章 线性表课后作业答案 1. 填空题。 （1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 （2）线性表中结点的集合是 有限 的，结点间的关系是 一对一的。 （2）s=0; for （i=0; i 数据结构第二章习题解答 一、单选题 1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移（B）个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 2．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移（A）个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3. 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（即需要比较的元素个数）为( C )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为(C )。 A. (n+1)/2 B. n/2 C. n D. n+1 5. 在一个顺序表的表尾插入一个元素的时间复杂度为(B )。 A. O(n) B. O(1) C. O(n*n) D. O(log2n) 6.若一个结点的引用为p，它的前驱结点的引用为q，则删除p的后继结点的操作为(B )。 A. p=p.next.next B. p.next=p.next.next C. q.next=p.next D. q.next=q.next.next 8. 假定一个多项式中x的最高次幂为n，则在保存所有系数项的线性表表示中，其线性表长度为(A )。 A. n+1 B. n C. n-1 D. n+2 二、填空题 1．对于当前长度为n的线性表，共包含有________多个插入元素的位置，共包含有________多个删除元素的位置。（答案n+1 n） 2．若经常需要对线性表进行表尾插入和删除运算，则最好采用________存储结构，若经 常需要对线性表进行表头插入和删除运算，则最好采用________存储结构。（答案：顺序链式） 3．由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为________。（答案：O（n）O（n）） 4．由n个元素生成一个单链表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为________。（答案：O（1）O（1）） 5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为________， 在表尾插入元素的时间复杂度为________。（答案：O（n），O（1）） 6. 对于一个单链接存储的线性表，在表头插入结点的时间复杂度为________，在表尾插 入结点的时间复杂度为________。（答案：O（1），O（1）） 7. 从一个顺序表和单链表中访问任一个给定位置序号的元素（结点）的时间复杂度分别 为________和_______。（答案：O（1），O（n）） 三、算法设计题 1. 修改从顺序存储的集合中删除元素的算法，要求当删除一个元素后检查数组空间的大小，若空间利用率小于40%同时数组长度大于maxSize时则释放数组的一半存储空间。public void remove(int i) throws Exception{《数据结构》各章课后作业答案
《数据结构》吕云翔编著第2章线性表习题解答
相关主题
文本预览