2线性表
沈阳理工大学应用技术学院
信息与控制学院计算机科学与技术教室
2011-5-8
- 13 -
数据结构复习题：线性表单选题
1、在长度为n的顺序表中，在第I个元素(1in 1)前插入新元素时，需要向后移动_____个元素。 2、从具有n个节点的单链表中查找其值等于x节点的节点时，如果检索成功，需要平均比较_____个节点。 3、在单链表中，已知*q节点是*p节点的前驱节点，在*q和*p之间插入*s节点，将执行_____。 4、线形表为：
5、对于依次存储的线性表，设其长度为n，则无论在哪个位置插入或删除操作都是等概率的，删除一个要素时移动表中的_____个要素。
6、线性表采用链式存储时，其地址_____。
7、假设单链表的指针p指向节点m，指向指针f插入的新节点x。 在链表的最后一个节点m中插入x后，修改_____再修改p-link=f即可。
8、在双向链表的存储结构中，删除p指向的节点时需要修改指针_____。
9、在双向链表存储结构中，在删除p所指节点的前向节点(如果存在)时需要修改指针_____。 10、根据线性表的链式存储结构，各节点所包含的指针的数量将链表分为单链表和_____。 11、在线性表的链式存储结构中，逻辑上相邻的要素物理上位于_____位置。 12、链表不具有的特点是_______。
13、不具有开头节点的单链表head为空的判断条件为______。 14、头节点单链表头为空的判断条件为______。 15、首节点双循环表l为空表的条件为______。
16、满足非空循环单链表head的末尾节点(p指向) _______。
17、在循环双链表p指定的节点前插入s指定的节点的操作为_______。
18、ssdyl表最常用的操作是在最后一个节点后插入一个节点或删除最后一个节点时，采用______保存方式最节约运算时间。
19、某线性列表最常见的操作是在最后一个节点后插入节点或删除第一个节点，所以采用_____存储方式最能节约运算时间。
20、插入并删除需要分配较大空间、不需要移动元素的线形表。 其存储结构为_______。 21、如果最常用的操作是取第I个节点及其前体，那么采用______保存方式最节省时间。
22、在有n个节点的有序单链表中插入新节点，有序时间复杂度为______。 23、长度为n(n1 )的单链表有两个指针：头和尾，执行________操作与链表的长度有关。 24、假设线性表中有n个要素。 在以下算法中，用_______顺序表实现比用链表实现更高效。 25、假设线性表中有2n个元素，算法_______，用单链表实现比用顺序表实现更有效率。 26、与单链表相比，双链表的优点之一是________。 27、对线性表只有4种运算，即删除第一个元素，删除最后一个元素，在第一个元素前插入新元素，在最后一个元素后插入新元素，最后使用________。
28、在线性表只有两种运算的情况下，即删除第一个元素，在最后一个元素后面插入新元素的情况下，最好使用_______。
29、有两个长度为n的单链表，节点类型相同。 如果将h1作为头指针的链表为非循环，将h2作为头指针的链表为循环，则为_______。
30、在长度为n的______上，删除第一个节点，该算法的时间复杂度为o(n )。
31、将各有n个要素的两个顺序表组成一个顺序表，其最小比较次数为_____。 32、开头节点的单链表l为空的判断条件为______。
33、在有n个节点的有序单链表中插入新节点，有序时间复杂度为_______。 34、在长度为n(n1 )的开头节点的单链表h中，另设末尾指针r (指末尾节点)，执行_______操作和链
- 14 -
与表的长度有关。
35、在双链表中，在*p节点后插入节点*q的操作为______。 36、在双链表中，在*p节点前插入*q节点的操作为______。 37、双链式，删除*p节点的操作为_______。
38、在双链表中，删除*p节点后的节点的操作为________。 39、满足非空循环单链表l的末尾节点(p指向) ______。 40、前端节点的双循环链表l为空表的条件为______。
41、ssdyl表最常见的操作是在最后一个节点后插入节点或删除最后一个节点，采用_________保存方式最节省运算时间。
42、对包含n(n1 )个元素线性表的运算仅用4种：删除最初的元素的情况； 删除最后一个要素； 在第一个元素之前插入新元素； 如果要在最后一个元素之后插入新元素，建议使用________。
43、某线性列表最常见的操作是在最后一个节点后插入节点或删除第一个节点时，采用_______保存方式最节省运算时间。
44、有两个长度为n的单链表，节点类型相同，
若以h1为头结点的链表是非循环的，以h2为头结点指针的链表是循环的，则________。45、在长度驎n(n>1)的______上，删除第一个元素，其算法的时间复杂度为O(n)。 46、元素A、B、C、D依次进顺序栈后，栈顶元素是_______，栈底元素是______。 47、经过以下栈运算后，X的值是______。
InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);
48、经过以下的栈运算后，StackEmpty(s)的值是______。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)
49、设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是______。 50、若线性表最常用的运算是存取第i个元素及其前驱的值,则采用______存储方式节省时间. 51、链表不具备的特点是______.
52、在一个长度为n的顺序存储的线性表中，向第i个元素(1<=i<=n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素．
53、在一个长度为n的顺序存储的线性表中，删除第i个元素(1<=i<=n)时，需要从前向后依次前移_________个元素．
54、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x同元素的平均比较次数，查找每个元素的概率都相等)为( )．
57、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_________。 数据结构复习题答案：线性表 单选题
1、n-1|n-i+1|n-i-1|I B 2、n|n/2|(n-1)/2|(n+1)/2 D
3、s->next=p->next; p->next=s;|p->next=s->next; s->next=p;|q->next=s; s->next=p;|p->next=s; s->next=q; C
4、一个有限序列，可以为空。|一个有限序列，不能为空。|一个无限序列，可以为空。|一个无限序列，不能为空。 A
5、n+1|n-1|(n-1)/2|n C 6、必须是连续的。|部分地址必须是连续的。|一定是不连续的。|连续与否均可以。D 7、f->link=p;|f->link=p->link;|p->link=f->link;|f=nil; B 8、((p->rlink) ->rlink) ->link=p;p->rlink=(p->rlink) ->rlink;|(p->llink) ->rlink=p->rlink;(p->rlink)
->llink=p->llink;|p->llink=(p->llink) ->llink;((p->llink) ->llink) ->rlink=p;|((p->llink) ->llink) ->rlink=p;p->llink=(p->llink)
- 15 -
->llink; B
9、((p->llink) ->llink) ->rlink=p;p->llink=(p->llink) ->llink;|((p->rlink) ->rlink) ->llink=p;p->rlink=(p->rlink)
->rlink;|(p->llink) ->rlink=p->rlink;(p->rlink) ->llink=p->llink;| p->llink=(p->llink) ->llink;((p->llink) ->llink) ->rlink=p; A
10、循环链表|多重链表|普通链表|无头结点链表 B 11、一定相邻|不一定相邻|有时相邻| B
12、可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其长度成正比 A
13、head==NULL|head->next==NULL|head->next==head|head!=NULL A 14、head==NULL|head->next==NULL|head->next==head|head!=NULL B 15、L=NULL|L->next==NULL|L->prior==NULL|L->next==L D 16、p->next==NULL|p==NULL|p->next==head|p==head C 17、
p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;|p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;|s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;|s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; D
18、单链表|给出表头指针的单循环链表|双链表|带头结点的双循环链表 D 19、单链表|仅有头结点的单循环链表|双链表|仅有尾指针的单循环链表 D 20、单链表|静态链表|线性链表|顺序存储结构 B 21、单链表|双链表|单循环链表|顺序表 D 22、O(1)|O(n)|O(n2)|O(nlog2n) B
23、删除单链表中的第一个元素|删除单链表中的最后一个元素|在单链表第一个元素前插入一个新元素|在单链表最后一个元素后插入一个新元素 B
24、输出第i(0<=i<=n-1)个元素值|交换第0个元素与第1个元素的值|顺序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号 A 25、删除所有值为x的元素|在最后一个元素的后面插入一个新元素|顺序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0,i,?,n-1) A
26、插入、删除操作更简单|可以进行随机访问|可以省略表头指针或表尾指针|顺序访问相邻结点更灵活 D 27、只有表尾指针没有头指针的循环单链表|只有表尾指针没有表头指针的非循环双链表|只有表头指针没有表尾指针的循环双链表|既有表头指针也有表尾指针的循环单链表 C
28、只有表头指针没有表尾指针的循环单链表|只有表尾指针没有表头指针的循环单链表|非循环双链表|循环双链表 B
29、对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)|对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)|循环链表要比非循环链表占用更多的内存空间|h1和h2是不同类型的变量 B 30、只有表头指针的不带表头结点的循环单链表|只有表尾指针的不带表头结点的循环单链表|只有表尾指针的带表头结点的循环单链表|只有表头指针的带表头结点的循环单链表 A
31、n|2n-1|2n|n-1 A 32、L==NULL|L->next==NULL|L->next==L|L!=NULL B 33、O(1)|O(n)|O(n^2)|O(nlog2n) B
34、删除单链表中的第一个元素|删除单链表中的最后一个元素|在单链表第一个元素前插入一个新元素|在单链表最后一个元素后插入一个新元素 B 35、
- 16 -