第2章线性表习题解析(答).doc

1、第二章线性表练习题一、选择题 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）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（

2、3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是 。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2）6.在双向链表存储结构中，删除p所指的结点时须修改指针 。A、pnextprior=pprior; ppriornext=pnext;B、pnext=pnextnext;pnextprior=p;C、ppriornext=p;pprior=ppriorprior;D、pprior=pnextnext;pnext=ppriorprior;7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是 。A、pnext=q;

3、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.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。A、 n b、2n1 c、2n d、n19.在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时须向后移动 个元素。A、ni B、ni+1 C、ni1 D、i10.线性表L=(a1，a2,a

4、n)，下列说法正确的是 。A、每个元素有有一个直接前驱和一个直接后继B、线性表中至少有一个元素C、表中诸元素的排列必须是由小到大或由大到小。D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。11.对单链表表示法，以下说法错误的是 。A、数据域用于存储线性表的一个数据元素B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针C、所有数据通过指针的链接而组织成单链表D、NULL称为空指针，它不指向任何结点只起标志作用12.若指定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 。 A、O(1) B、O(n) C、O(n2) D、O(n

5、log2n)13.以下说法正确的是 。A、顺序存储方式的优点是存储密度大且插入、删除运算率高B、链表的每个结点中都恰好包含一个指针C、线性表的顺序存储结构优于链式存储结构D、顺序存储结构属于静态结构而链式结构属于动态结构14.以下说法错误的是 。A、对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表B、对单链表来说，只有从头结点开始才能扫描表中全部结点C、双链表的特点是找结点的前趋和后继都很容易D、对双链中来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针中15.以下说法错误的是 。A、求表长、定位这两种运算在采用顺序存储结构时实现的效率

6、不比采用链式存储结构时实现的效率低B、序存储的线性表可以随机存取C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D、线性表的链式存储结构优于顺序存储结构二、判断题 1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ 错）2.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（ 错 ）3.顺序存储的线性表可以随机存取。（ 对）4.在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存储结构。（ 错 ）5.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（ 对 ）6.顺序存储结构属于静态结构，链式结构属于动态结构。（对 ）