数据结构-线性表-习题.doc

《数据结构-线性表-习题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二章线性表一、选择题1.线性表是（）A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.一维数组与线性表的特征是（）。A．前者长度固定，后者长度可变B．两者长度均固定C．后者长度固定，前者长度可变D．两者长度均可变3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是().A．当前结点所在地址域B．指针域C．空指针域D．空闲域4.用链表表示线性表的优点是（）。A．便于随机存取B．便于进行插入和删除操作C．占用的存储空

2、间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有n个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点C．删除开始结点6.下面关于线性表的叙述中，错误的是（）。A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作7.已知单链表的每个结点包括一个指针

3、域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.设al，a2，a3为三个结点；p,10,20代表地址，则如下的链表存储结构称为（）。A．链表B．单链表C．双向循环链表D．双向链表9.单链表的存储密度（）。

4、A．大于1B．等于1C．小于1D．不能确定10.己知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址al，则第i个结点的地址为（）。A.al+(i-1)*mB.al+i*mC.al-i*mD.al+(i+1)*m11.在n个结点的顺序表中，算法的时间复杂度是O(l）的操作是（）。A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n)B．在第i个结点之后插入一个新结点（1≤i≤n-1）C．删除第i个结点（1≤i≤n)D．将n个结点从小到大排序12.在线性表中（）只

5、有一个直接前驱和一个直接后继。A．首元素B．中间元素C．尾元素D．所有元素13.对具有n个结点的线性表进行查找运算，所需的算法时间复杂度为（）。A.0(n2)B.0(nlog2n)C.O(log2n)D.O(n)14.线性表采用顺序存储的缺点是（）。A．存储密度降低B．只能顺序访问C．元素的逻辑顺序与物理顺序不一致D．插入、删除操作效率低15.以下链表结构中，从当前结点出发能够访问到任一结点的是（）。A．单向链表和双向链表B．双向链表和循环链表C．单向链表和循环链表D．单向链表、双向链表和循环链表

6、16.线性表是具有n个（）的有限序列。A．数据项B．数据元素C．表元素D．字符17.若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为（）。A.0(l)B.0(n)C.0(n2)D.0(log2n)18.指针P指向循环链表L的首元素的条件是（）。A.P＝＝LB.L->next＝＝PC.P->next==NULLD.P->next＝＝L19.指针P所指的元素是双循环链表L的尾元素的条件是（）。A.P＝＝LB.P->prior＝＝LC.P＝＝NULLD.P->next＝＝L20.不

7、带头结点的单链表L为空的条件是()A.L!＝NULLB.L＝＝NULLC.L->next＝＝NULLD.L->next＝＝L1.带头结点的单链表L为空的条件是()A.L!＝NULLB.L＝＝NULLC.L->next＝＝NULLD.L->next＝＝L2.两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。A.P->next＝＝Q->nextB.P->next＝＝QC.Q->next＝＝PD.P＝＝Q3.在长度为n的顺序表中，若要删除第i(1≤i≤n）个元素，则需要向

8、前移动元素的次数为（）。A.1B.n一iC.n一i+1D.n一i一l4.在长度为n的顺序表中第i(1≤i≤n）个位置上插入一个元素时，为留出插入位置所需移动元素的次数为（）。A.n-iB.iC.n–i+1D.n-i-l5.假定己建立以下动态链表结构，且指针Pl和P2已指向如图所示的结点：则以下可以将P2所指结点从链表中删除并释放该结点的语句组是()A.pl->next=p2->next;free(pl);B.pl=p2;free(p2);C.pl->next=p2->next；fr