数据结构(线性表)习题与答案

1、一、单选题1、线性表是具有n个 的有限序列。A.数据项B.字符C.数据元素D.表元素正确答案：C2、线性表是。A.一个无限序列，可以为空B.一个有限序列不可以为空C.一个无限序列，不可以为空D.一个有限序列，可以为空正确答案：D3、关于线性表的正确说法是。A.每个元素都有一个前驱和一个后继元素B.除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素C.表中元素的排序顺序必须是由小到大或由大到小D.线性表中至少有一个元素正确答案：B4、线性表采用链表存储时，其存放各个元素的单元地址是。A.连续与否均可以B.部分地址必须是连续的C.一定是不连续的D.必须是连续的正确答案：A5、链表

2、不具备的特点是。A.插入删除不需要移动元素B.所需空间与其长度成正比C.不必事先估计存储空间D.可随机访问任一节点正确答案：D6、线性表的静态链表存储结构与顺序存储结构相比，优点是。A.所有的操作算法实现简单B.便于利用零散的存储器空间C.便于随机存取D.便于插入和删除正确答案：D7、线性表的顺序存储结构和链式存储结构相比，优点是。A.便于随机存取B.便于插入和删除C.所有的操作算法实现简单D.节省存储空间正确答案：A8、设线性表有n个元素，以下操作中在JII页序表上实现比在链表上实现效率号JoA.交换第1个元素第2个元素的值B.输出与给定值x相等的元素在线性表中的符号C输入第i(l<=

3、i<=n)个元素值D.顺序输出这n个元素的值正确答案：C9、对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反 映数据元素之间的逻辑关系，则应采用 存储结构。A.顺序B.链式C.散列D.索引正确答案：B10、设线性表中有n个元素，以下操作在单链表上实现要比在顺序表上实现效率高。A.交换第i个元素和第n-i+1个元素的值B.在第n个元素的后面插入一个新元素C.顺序输出前k个元素D.删除指定位置元素的后一个元素正确答案：D11、以下属于顺序表的优点是 OA.插入元素方便B.删除元素方便C.以上都不对D.存储密度大正确答案：D12、要求线性表采用静态空间分配方式，且插入和

4、删除操作时不需要移动元素,采用 的存储结构是 OA.静态链表B.单链表C.双链表D.顺序表正确答案：A13、如果最常用的操作时取第i个元素及前驱元素，则采用 存储方式最节省 时间。A.单链表B彳盾环单链表C.顺序表D.双链表正确答案：C14、与单链表相比，双链表的优点之一是。A.插入、删除操作更简单B.可以省略表头指针或表尾指针C.可以进行随机访问D.访问前后相邻节点更方便正确答案：D15、在长度为n的顺序表中插入一个元素的时间复杂度为。A. 0(n2)B.O(l)C.O(n)D.O(log2n)正确答案：C16、在长度为n的顺序表中删除一个元素的时间复杂度为。A.O(log2n)B. 0(1

5、)C.O(n)D. O(n2)正确答案：C17、在两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次 数为。A.2nB.2n-1C.nD.n-1正确答案：C18、将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是 。( MIN表示取最小值)A.nB.mC.不确定D.MIN(m, n)正确答案：D19、在带头节点的单链表L为空的判定条件是。A. L=NULLB.L->NEXT=NULLC. L!=NULLD. L->NEXT=L正确答案：B20、对于一个具有n个元素的线性表，建立其单链表的时间复杂度为 oA. O(n)B. O(n2)C.O(l)

6、D. O(log2n)正确答案：A21、在单链表中查找指定值的节点的时间复杂度是。A.O(n2)B.O(n)C.O(log2n)D.O(l)正确答案：B22、以下关于单链表的叙述中，不正确的是。A.逻辑上相邻的元素物理上不必相邻B.可以通过头节点直接计算第i个节点的存储地址C.插入、删除运算操作简单，不必移动节点D.节点除自身信息外还包括指针域，因此存储密度小于顺序存储结构正确答案：B23、在单链表中，增加一个头节点的目的是为了。A.说明单链表是线性表的链式存储结构B.使单链表至少有一个节点C.方便运算的实现D.标识链表中重要节点的位置正确答案：C24、在一个具有n个节点的有序单链表中插入一个

7、新节点并仍然保持有序的时间复杂 度是。A. 0(n)B.O(n2)C.O(nlog2n)D.O(l)正确答案：A25、将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为。A.O(l)B.O(m)C.O(n)D.O(m+n)正确答案：C26、已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 OA.插入一个节点使之有序的算法的时间复杂度为0(1)B.找最小值节点的算法的时间复杂度为0(1)C.删除最大值节点使之有序的算法的时间复杂度为0(1)D.以上都不对正确答案：B27、在一个长度为n(n>l)的带头节点的单链表上，另设有尾指针r(指向尾节点)， 执行操作与链

8、表的长度有关。A.在单链表最后一个元素后插入一个新节点B.删除单链表中的第一个元素C.在单链表中第一个元素前插入一个新节点D.删除单链表的尾节点正确答案：D28、在一个双链表中，在*p节点之后插入节点*q的操作是。A.q ->next = p -> next; p -> next -> prior =q ; p-> next=q ; q->prior = p ;B.p-> next=q ; q->prior = p ; q ->next = p -> next; p -> next -> prior =q ;C.p -&g

9、t; next -> prior =q ; q->prior = p ; p-> next=q ; q ->next = p -> next;D.q->prior = p ; p-> next=q ; p -> next -> prior =q ; q ->next = p -> next;正确答案：A29、在一个双链表中，在*p节点之前插入节点*q的操作是。A.p -> prior = q ; q-> next=p ; p -> prior ->next=q ; q ->prior= p ->

10、; prior;B.q-> next=p ; p -> next=q ; q-> prior ->next= q ; q-> next=p ;C.p -> prior ->next=q ; q-> next=p ; q -> prior = p->prior; p -> prior = q ;D.q ->prior= p -> prior; p -> prior ->next=q ; q-> next=p ; p -> prior = q->next;正确答案：c30、在一个双链表中，删

11、除*p节点的操作是 oA.p ->prior= p -> prior -> prior; p -> prior ->prior = p ;B.p-> next -> prior = p ; p-> next=p-> next-> next;C.p -> next= p->prior -> prior; p-> prior = p->prior->prior;D.p -> prior ->next= p-> next; p ->next-> prior = p ->

12、 prior;正确答案：D31、在一个双链表中，删除*p节点之后的一个节点，其时间复杂度为。A.O(nlog2n)B.O(n2)C.O(l)D.O(n)正确答案：C32、非空的循环单链表L的尾节点(由p所指向)满足 oA.p-> next = NULLB.p = NULLC.p -> next = LD. p=L正确答案：c33、带表头结点的双循环链表L为空表的条件是。A.L -> next = LB.L= NULLC.L -> prior = NULLD.L-> next -> prior = NULL正确答案：A34、某线性表最常用的操作是在尾元素之后插

13、入一个元素和删除尾元素，则采用 存储方式最节省运算时间。A.单链表B.双链表C循环双链表。循环单链表正确答案：C35、如果对含有n ( n>l)个元素的线性表的运算只有4种，即删除第一个元素、删除 尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用OA.只有尾节点与第十没有头节点的非循环双链表B.既有表头指针也有表尾指针的循环单链表C.只有尾节点书第十没有头节点的循环单链表D.只有开始数据节点指针没有尾节点指针的循环双链表正确答案：D36、在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。故采 用 存储方式最节省时间。A.单链表B.双链表C.仅有尾书

14、第十的循环单链表D.仅有头节点指针的循环单链表正确答案：C37、两个表长都为n、不带表头结点的单链表，结点类型都相同，头指针分别为hl与 h2 ,且前者是循环链表，后者是非循环链表，则。A.hl和h2是不同类型的变量B彳盾环链表要比循环链表占用更多的内存空间C.对于两个链表来说，删除尾节点的操作，其时间复杂度都是0(n)D.对于两个链表来说，删除首节点的操作，其时间复杂度都是0(1)正确答案：C38、在长度为n的 上，删除第一个元素，其算法的时间复杂度为O(n)oA.只有表尾指针的带表头节点的循环单链表B.只有表头指针的不带表头节点的循环单链表C.只有表头指针的带表头节点的循环单链表D.只有表

15、尾指针的不带表头节点的循环单链表正确答案：B39、下面关于线性表的叙述错误的是。A.线性表采用JII酹存储便于插入和删除操作的实现B.线性表采用顺序存储必须占用一片连续的存储空间C.线性表采用链式存储不必占用一片连续的存储空间D.线性表采用链式存储便于插入和删除操作的实现正确答案：A40、对于双链表，在两个节点之间插入一个新节点是，需要修改 个二旨针域。A.3B.1C.4D.2正确答案：C41、在单链表中，要删除某一指定的节点,必须找到该节点的 节点。A.前驱B.头节点C后继D.尾节点正确答案：A42、求一个单链表长度的算法的时间复杂度为。A.O（l）B. 0（n2）C.O（log2n）D. 0（n）正确答案：D二、判断题43、线性表中每个元素都有一个前驱元素和一个后继元素。（x ）44、线性表中所有元素的排列顺序必须从小到大或从大到小。（X