《线性表习题解析(答)》由会员分享,可在线阅读,更多相关《线性表习题解析(答)(4页珍藏版)》请在金锄头文库上搜索。
1、第二章第二章 线性表练习题线性表练习题一、选择题一、选择题 1.1.线性表是具有线性表是具有 n n 个个 的有限序列。的有限序列。A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.2.线性表的静态链表存储结构与顺序存储结构相比优点是线性表的静态链表存储结构与顺序存储结构相比优点是 。A、所有的操作算法实现简单 B、便于随机存储C、便于插入和删除 D、便于利用零散的存储器空间3.3.若长度为若长度为 n n 的线性表采用顺序存储结构,在其第的线性表采用顺序存储结构,在其第 i i 个位置插入一个新元素算法的个位置插入一个新元素算法的时间复杂度为时间复杂度为 。A、O(log2n)
2、 B、O(1) C、O(n) D、O(n2)4.4.(1 1)静态链表既有顺序存储的特点,又有动态链表的优点。所以,它存取表中)静态链表既有顺序存储的特点,又有动态链表的优点。所以,它存取表中第第 i i 个元素的时间与个元素的时间与 i i 无关;无关;(2 2)静态链表中能容纳元素个数的最大数在定义时就确定了,以后不能增加;)静态链表中能容纳元素个数的最大数在定义时就确定了,以后不能增加;(3 3)静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。)静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。以上错误的是以上错误的是 。A、 (1) 、 (2) B、 (1)
3、C、 (1) 、 (2) 、 (3) D、 (2)6.6.在双向链表存储结构中,删除在双向链表存储结构中,删除 p p 所指的结点时须修改指针所指的结点时须修改指针 。A、pnextprior=pprior; ppriornext=pnext;B、pnext=pnextnext;pnextprior=p;C、ppriornext=p;pprior=ppriorprior;D、pprior=pnextnext;pnext=ppriorprior;7.7.在双向循环链表中,在在双向循环链表中,在 P P 指针所指的结点后插入指针所指的结点后插入 q q 所指向的新结点,其修改指针所指向的新结点,其
4、修改指针的操作是的操作是 。A、pnext=q; qprior=p;pnextprior=q;qnext=q;B、pnext=q;pnextprior=q;qprior=p;qnext=pnext;C、qprior=p; qnext=pnext; pnextprior=q; pnext=q;D、qnext=pnext;qprior=p;pnext=q;pnext=q;8.8.将两个各有将两个各有 n n 个元素的有序表归并成一个有序表,其最少的比较次数是个元素的有序表归并成一个有序表,其最少的比较次数是 。A、 n b、2n1 c、2n d、n19.9.在一个长度为在一个长度为 n n 的顺序
5、表中,在第的顺序表中,在第 i i 个元素(个元素(1in+11in+1)之前插入一个新元素)之前插入一个新元素时须向后移动时须向后移动 个元素。个元素。A、ni B、ni+1 C、ni1 D、i10.10.线性表线性表 L=(a1L=(a1,a2,an)a2,an),下列说法正确的是,下列说法正确的是 。A、每个元素有有一个直接前驱和一个直接后继B、线性表中至少有一个元素C、表中诸元素的排列必须是由小到大或由大到小。D、除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。11.11.对单链表表示法,以下说法错误的是对单链表表示法,以下说法错误的是 。A、数据域用于存储
6、线性表的一个数据元素B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针C、所有数据通过指针的链接而组织成单链表D、NULL 称为空指针,它不指向任何结点只起标志作用12.12.若指定有若指定有 n n 个元素的向量,则建立一个有序单向链表的时间复杂性的量级是个元素的向量,则建立一个有序单向链表的时间复杂性的量级是 。 A、O(1) B、O(n) C、O(n2) D、O(nlog2n)13.13.以下说法正确的是以下说法正确的是 。A、顺序存储方式的优点是存储密度大且插入、删除运算率高B、链表的每个结点中都恰好包含一个指针C、线性表的顺序存储结构优于链式存储结构D、顺序
7、存储结构属于静态结构而链式结构属于动态结构14.14.以下说法错误的是以下说法错误的是 。A、对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表B、对单链表来说,只有从头结点开始才能扫描表中全部结点C、双链表的特点是找结点的前趋和后继都很容易D、对双链中来说,结点*p 的存储位置既存放在其前趋结点的后继指针域中,也存放在它的后继结点的前趋指针中15.15.以下说法错误的是以下说法错误的是 。A、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B、序存储的线性表可以随机存取C、由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活D、线性
8、表的链式存储结构优于顺序存储结构二、判断题二、判断题 1.1.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。 ( 错错)2.2.在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点。在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点。 ( 错错 )3.3.顺序存储的线性表可以随机存取。顺序存储的线性表可以随机存取。 ( 对对)4.4.在单链表中,要访问某个结点,只要知道该结点的指针即可;因此,单链表是一在单链表中,要访问某个结点,只要知道该结点的指针即可;因此,单链表是一种随机存储结构。种随机存储结构。 ( 错错 )5.5.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。置有关。 ( 对对 )6.6.顺序存储结构属于静态结构,链式结构属于动态结构。顺序存储结构属于静态结构,链式结构属于动态结构。 (对对 )