线性表算法题

《数据结构》第2章线性表共55题一、单选1. (1)分题目ID号：10545 题目难度：容易在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤i十1)位量插入一个新元素时，需要从后向前依次后移【1】个元素。

A. n—iB. n—i十1C. n一i一1 D. i题目答案：B2. (1)分题目ID号：10546 题目难度：容易线性表是【1】。

A. 一个有限序列，可以为空B. 一个有限序列，不能为空C. 一个无限序列，可以为空D. 一个无序序列，不能为空题目答案：A3. (1)分题目ID号：10548 题目难度：容易在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为【1】A. (n十1)／2B. n／2C. nD. n十l题目答案：C4. (1)分题目ID号：10549 题目难度：容易在一个顺序表的表尾插入一个元素的时间复杂度的量级为【1】A. ○(n)B. ○(1)C. ○(n*n)D. ○(lbn)题目答案：B5. (1)分题目ID号：10550 题目难度：容易单链表的存储密度为【1】A. 大于1B. 等于1C. 小于1D. 不能确定题目答案：C题目分析：存储密度=单链表数据项所占空间/结点所占空间结点所占空间由数据项所占空间和存放后继结点地址的链域，所以，存储密度小于1 。

6. (4)分题目ID号：10551 题目难度：难设单链表中指针p指向结点ai，指针q指着将要插入的新结点x，问：[1] 当x插在链表中两个数据元素ai和ai+1之间时，只要先修改【1】后修改【2】即可。

A.p一＞next＝qB.p一＞next＝p一>next->nextC.p->next=q->nextD.q一＞next＝p一＞nextE.q->next＝NULLF.q一＞next＝p[2] 在链表中最后一个结点an之后插入时，只要先修改【3】后修改【4】即可。

第2章线性表习题参考解答一、简答题1．试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。

【答】头指针：是指向链表中的第一个结点的指针。

头结点：在开始结点之前附加上的一个结点。

开始结点：链表的第一个结点。

头指针是一个指向地址的变量，用于表示一个链表的开始。

引入头结点可以更加方便的进行链表是否为空的判断，同时方便了插入和删除结点。

开始结点用于存储链表的第一个数据元素。

2．何时选用顺序表、何时选用链表作为线性表的存储结构为宜?【答】顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元素；相反，链表中却是方便插入或者删除元素，在查找元素的是，需要进行遍历。

因此，当所涉及的问题常常进行查找等操作，而插入、删除相对较少的是，适合采用顺序表；当常常需要插入、删除的时候，适合采用链表。

3．为什么在单循环链表中设置尾指针比设置头指针更好?【答】在单循环链表中，设置尾指针，可以更方便的判断链表是否为空。

4．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?【答】本题分三种情况讨论：1、单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继，但是不知道头指针，因此不能找到该结点的直接前趋，因此，无法删除该结点。

2、双链表：根据指针p可以找到该结点的直接前趋和直接后继，因此，能够删除该结点。

3、单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前趋和直接后继，因此，也可以删除该结点。

5．下述算法的功能是什么?LinkList Demo(LinkList *L) /* L是无头结点单链表*/{LNode *Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;}return L;} /* Demo */【答】将原来的第一个结点变成末尾结点，原来的第二个结点变成链表的第一个结点。

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若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;参考答案：B5.在一个单链表中，若删除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;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

第二章线性表习题一判断题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) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表6．循环链表的主要优点是( )。

数据结构--线性表习题及答案第⼆章线性表⼀、选择题1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。

A. O(log2n)B.O(1)C. O(n)D.O(n2)2、若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。

A. 顺序表B. 单链表C. 双链表D. 单循环链表3、具有线性结构的数据结构是（）。

A. 图B. 树C. ⼴义表D.栈4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。

A. n-iB. n-i+1C. n-i-1D. i5、⾮空的循环单链表head的尾结点p满⾜（）。

A. p->next==headB. p->next==NULLC. p==NULLD. p==head6、链表不具有的特点是（）。

A. 可随机访问任⼀元素B. 插⼊删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正⽐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、线性表采⽤链式存储时，结点的存储地址（）。

A. 必须是连续的B. 必须是不连续的C. 连续与否均可D. 和头结点的存储地址相连续9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。

第2章线性表练习题答案一、填空1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

3. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。

4. 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

5．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。

二、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。

答：错误。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

错，链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

错，链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

错，前一半正确，但后一半说法错误，那是链式存储的优点。

顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（×）7. 线性表在物理存储空间中也一定是连续的。

错，线性表有两种存储方式，顺序存储和链式存储。

第二章线性表一、选择题1.线性表是（）A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.一维数组与线性表的特征是（）。

A．前者长度固定，后者长度可变B．两者长度均固定C．后者长度固定，前者长度可变D．两者长度均可变3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ).A．当前结点所在地址域B．指针域C．空指针域D．空闲域4.用链表表示线性表的优点是（）。

A．便于随机存取B．便于进行插入和删除操作C．占用的存储空间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。

A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点 C．删除开始结点6.下面关于线性表的叙述中，错误的是（）。

A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。

现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。

A . q = p->next; p->next = q->next ;B . p->next = q->next; q = p->next ;C . q->next = p->next; p->next = q ;D . p->next = q; q->next = p->next ;8.设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（）。

A．链表B．单链表C．双向循环链表D．双向链表9.单链表的存储密度（）。

习题1 线性表班级姓名学号日期选择题1．下面关于线性表叙述中，错误的是_ _。

A．顺序表必须占用一片地址连续的存储单元B．链表不必占用一片地址连续的存储单元C．顺序表可以随机存取任一元素D．链表可以随机存取任一元素2．在表长为n的单链表中，算法时间复杂度为O(n)的操作是。

A．查找单链表中第i个结点 B．在p结点之后插入一个结点C．删除表中第一个结点 D．删除p结点的直接后继结点3．在表长为n的顺序表中，算法的时间复杂度为O(1)的操作是。

A．在第n个结点之后插入一个结点 B．在第i个结点前插入一个新结点C．删除第i个结点 D．求表长4．在下列链表中不能从当前结点出发访问到其余各结点的是。

A．单链表 B．单循环链表 C．双向链表 D．双向循环链表5.设p结点是带表头结点的双循环链表中的结点，则(1)在p结点后插入s结点的语句序列中正确的是。

A.s->next=p->next；p->next->prior=s； p->next=s；s->next=p->next；B.p—>next=s；S—>next=p—>next； p—>next—>prior=s；s—>next=p；C.p->next=s；p—>next—>prior=s； s->next=p—>next；S—>next=p；D.p->next->prior=s；p->next=s； s->next=p->next；s->next=p；(2)在p结点之前插入s结点的语句序列中正确的是A.s->prior=p->prior；p->prior->next p->prior=s；s->next=p；B.p->prior=s；p->prior->next=s; s->prior=p->prior；s->next=p;C.p->prior->next=s；p->prior=s; s->prior=p->prior；s->next=p;D.p->prior=s；s->next=p； p->prior->next=s；s->prior=p->prior;填空题1、单链表中每个结点需要两个域，一个是数据域，另一个是2、表长为n的顺序表中，若在第j个数据元素(1≤i≤n+1)之前插入一个数据元素，需要向后移动个数据元素；删除第j个数据元素需要向前移动个数据元素；在等概率的情况下，插入一个数据元素平均需要移动个数据元素，删除一个数据元素平均需要移动个数据元素。

数据结构第二章习题第2章线性表一、单项选择题1．线性表就是具备n个_________的非常有限序列。

a．表元素b．字符c．数据元素d．数据项2．线性表是_________。

a．一个非常有限序列，可以为空b．一个非常有限序列，不可以为空c．一个无穷序列，可以为空d．一个无穷序列，不可以为空3．线性表使用链表存储时，其地址_________。

a．必须是连续的b．一定是不连续的c．部分地址必须是连续的d．连续与否均可以4．链表不具备的特点是_________。

a．可以随机出访任一结点b．填入删掉不须要移动元素c．不必事先估算存储空间d．所须要空间与其长度成正比5．设立线性表存有n个元素，以下操作方式中，_________在顺序单上同时实现比在链表上同时实现效率更高。

a．输出第i(1≤i≤n)个元素值b．互换第1个元素与第2个元素的值c．顺序输入这n个元素的值d．输出与给定值x相等的元素在线性表中的序号6．设立线性表中存有2n个元素，以下操作方式中，_________在单链单上同时实现Obrero在顺序单上同时实现效率更高。

a．删掉选定的元素b．在最后一个元素的后面插入一个新元素c．顺序输出前k个元素d．互换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7．如果最常用的操作是取第i个结点及其前驱，则采用_________存储方式最节省时间。

a．单链表中b．双链表中c．单循环链表d．顺序表8．与单链表相比，双链表的优点之一是_________。

a．填入和删掉操作方式更直观b．可以展开随机出访c．可以省略字段指针或表尾指针d．出访前后相连结点更有效率9．率先垂范结点的单链表中l为觑的认定条件就是_________。

a．l==nullb．l->next==nullc．l->next==ld．l!=null10．在一个具备n个结点的有序单链表填入一个崭新结点并仍然维持有序的时间复杂度就是_________。

第二章习题：1.表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为（）。

A．n B. n/2 C. (n-1)/2 D. (n+1)/22.在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移（）个元素。

A. n-iB. n-i+1C. n-i-1D. i3.设单链表中结点的结构为TYPEDEF STRUCT NODE { //链表结点定义ELEMTYPE DATA; //数据STRUCT NODE * NEXT; //结点后继指针} LISTNODE;已知指针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;4.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

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;5.非空的循环单链表FIRST的尾结点（由P所指向）满足：（）A．P->NEXT = NULL; B．P = NULL; C．P->NEXT = FIRST; D．P = FIRST; 1．以下那一个术语与数据的存储结构无关？（ A ）A．队列 B. 哈希表C. 线索树D. 双向链表2、一个算法应该是（ B ）。

A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.3、数据结构中，与所使用的计算机无关的是数据的（ C ）A．存储结构 B．物理结构 C．逻辑结构 D．物理结构和存储结构4. 算法的计算量的大小称为计算的（ B ）。