第二部分 线性表
、选择题
1 ．关于顺序存储的叙述中 ,哪一条是不正确的 （ B ）
A. 存储密度大
B. 逻辑上相邻的结点物理上不必邻接
C. 可以通过计算直接确定第 i 个结点的位置
D. 插入、删除操作不方便
2 ．长度为 n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为
（ C ）
A O （n ）
B O （1）
C O （m ）
D O （m+n ）
3．在 n 个结点的顺序表中，算法的时间复杂度是 O （1） 的操作是： （ A ）
A 访问第 i 个结点（ 1<=i<=n ）和求第 i 个结点的直接前趋（ 2<=i<=n
）
B 在第 i 个结点（ 1<=i<=n ）后插入一个新结点
C 删除第 i 个结点（ 1<=i<=n
）
D 将 n 个结点从小到大排序
4 ．一个向量第一个元素的存储地址
是
100 ，每个元素的长度为 2 ，则第 5
个元素的地址
是
（ B ）
（ A ） 110 （ B ） 108 （ C ） 100 （ D ） 120
5 ．已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元， 若第一个结点的地址为 da ，
则第 i 个结点的地址为： （ A ）
7 ．链表是一种采用（ B ）存储结构存储的线性表。
（ A ）顺序 （ B ）链式 （ C ）星式 （ D ）网状
8 ．线性表若采用链式存储结构时，要求内存中可用存储单元的地址： （ D ）
（ A ）必须是连续的 （ B ）部分地址必须是连续的 （ C ）一定是不连续的 （ D ）连续或不连续都可以
9 ．线性表Ｌ在 （ B ）情况下适用于使用链式结构实现。
Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入
10 ．在长度为 n 的顺序表的第 i
(1 ≤ i ≤ n+1) 个位置上插入一个元素，元素的移动次数
为
A ） da+（i-1）*m
B ） da+i*m
6 ．在具有 n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点
C ）删除开始结点
C ） da-i*m
D ） da+（i+1）*m
A ）的操作，其算法的时间复杂度为 O （n ） 。
B ）在地址为 p 的结点之后插入一个结点 D ）删除地址为 p 的结点的后继结点
Ｃ)Ｌ中含有大量的结点Ｄ)Ｌ中结点结构复杂
( A )
A.n-i+1
B.n-i
C.i
D.i-1
11．线性表是( A )。
a 、一个有限系列，可以为空b、一个有限系列，不能为空
c、一个无限系列，可以为空
d、一个无限系列，不能为空
12.( A )线性表。
A.( 孔子, 诸葛亮, 曹雪芹)
B.{A,B,C,D}
C.{10,11,12,13,14}
D.(1,2,3,...)
13. ( )是表示线性数据结构的。
A. 循环链表
B.邻接多重表
C.孩子链表
D. 单链表
14. 将线性表的数据元素以( B )结构存放, 查找一个数据元素所需时间不依赖于表长。
A. 循环双链表
B.哈希(Hash) 表
C. 一维数组
D. 单链表
15. 在一个单链表中，若p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行( B)。
(A)s->link=p;p->link=s;
(B)s->link=p->link;p->link=s;
(C)s->link=p->link;p=s;
(D ) p->link=s;s->link=p;
16. 在循环链表中first 为指向链表表头的指针，current 为链表当前指针，在循环链表中检测current
是否达到链表表尾的语句是( D ) 。
(A) current->link=NULL (B)first->link=current
( C)first=current (D)current->link=first
17. 从一个具有n 个结点的单链表中查找其值等于x 结点时，在查找成功的情况下，需平均比较
( D ) 个结点。
A. n
B. n/2
C. (n-1 ) /2
D. (n+1)/2
18. 在一个具有n 个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为( B ) 。
A. O(1)
B. O(n)
C. O(n 2)
D. O(nlog 2n)
19. 用链表表示线性表的优点是( C ) 。
A. 便于随机存取
B. 花费的存储空间比顺序表少
C. 便于插入与删除
D. 数据元素的物理顺序与逻辑顺序相同
20. 当需要随机查找线性表的元素时,宜采用( C ) 作存储结构。
A. 双向链表
B. 循环链表
C. 顺序表
D. 单链表
21. 线性表的链接实现有利于（ A ）运算。
A 、插入 b 、读表元
c 、查找
d 、定位
22. 线性表采用链式存储时，其地址（ D ）。
A 必须是连续的
B 部分地址是连续的
C 一定是不连续的
D 连续与否均可以
23. 设单链表中指针 p 指着结点 a ，若要删除 a 之后的结点（若存在） ，则需要修改指针的操作
为（ A ）。
A 、 p->next=p->next->next
C 、 p= p->next->next 127 个元素原顺序表中插入一个新元素并保存原来
顺序不变，平均要移动（ 个元素。
28 ．对长度为 N 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ B ）。 A ．N+1
B ．N
C ．（N+1）/2
D ．N/2
29 ．下列叙述中正确的是 （ A ） 。
A. 线性表是线性结构
B. 栈与队列是非线性结构
C. 线性链表是非线性结构
D. 二叉树是线性结构
30 ．在单链表中，增加头结点的目的是 （ A ） 。
A. 方便运算的实现
B. 使单链表至少有一个结点
C. 标识表结点中首结点的位置
D. 说明单链表是线性表的链式存储实现
31 ．线性表的顺序存储结构和线性表的链式存储结构分别是（ B ）。
A. 顺序存取的存储结构、顺序存取的存储结构
B. 随机存取的存储结构、顺序存取的存储结构
C. 随机存取的存储结构、随机存取的存储结构
D. 任意存取的存储结构、任意存取的存储结构 33 ．线性表中正确的说法是 （ D ）
b 、
p=p->next d 、
24. 向一个有 25. 26. 27. A 、8
向一个有 B 、63.5 C 、63 127 个元素的顺序表中删除一个元素， B ) 63.5
C ) 63
D ）
D 、7
平均要移动（
C ）个元素
用链表表示线性表的优点是（ A ）
A 便于插入和删除操作
C 花费的存储空间较顺序存储少
以下数据结构中不属于线性数据结构的是
A 队列
B 线性表
C 二叉树
数据元素的物理顺序与逻辑顺序相同 便于随即存取
A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表至少要求一个元素
C. 表中的元素必须按由小到大或由大到小排序
D. 除了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继
34 ．线性表是具有n 个( C )的有限序列。
A. 表元素
B. 字符
C. 数据元素
D. 数据项
35 ．若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为( C )。(1≤i≤n+1 )
A. O(0)
B. O(1)
C. O(n)
D. O(n 2)
36 ．在具有n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度( B )。
A. O(1)
B. O(n)
C. O(nlogn)
D. O(n 2)
37 ．某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用( A )存储方式最节省运算时间。
A. 仅有尾指针的单向循环链表
B. 仅有头指针的单向循环链表
C. 单向链表
D. 双向链表
二、填空题
1 ．在单项链表中删除一个指定结点的后继的时间复杂度为[ O(1) ]
2 ．线性表中 _____ 数据元素的个数 ______________________ 称为表的长度。
3. 在n 个结点的单链表中，在P 指向的结点之后插入一个结点的时间复杂度为_O (n)。
4 ．设长度为n 的线性表顺序存贮, 若在它的第i-1 和第i 个元素之间插入一个元素, 共需移动
__n-i+1 ______ 个元素(1
5 ．在顺序表中访问任意结点的时间复杂度为O(1 ) ，因此顺序表也称为随机存储
的数据结构。
6 ．在单链表中要在已知结点*p 之前插入一新结点，需找到插入点，其时间复杂度为O(n ) ，而在双链表中，完成同样操作的时间复杂度为O(1 ) 。
7 ．循环链表的主要优点是从任何一个结点出发可以遍历所有结点。
8 ．在一个单链表中删除p 所指结点的下一个结点时，应执行以下操作：
q=p->link;
p->link=__ p->link ->link __ __
Delete q
9 ．将适当的语句添入单链表搜索函数find 中。template Type>ListNode { current=first->link ；while(current!=NULL) if(current->data=value) break else current=current->link; return __ current ___ __ } 10 ．顺序存储方法是把逻辑上相邻的结点存储在物理位置__ 也相邻_______ 的存储单元中。 11 ．顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。因此，这种表便于 __ 随机__ 访问，是一种__随机访问存储结构__。 12 ．在一个不带头结点的单链表中，在表头插入或删除与其在其他位置插入或删除操作的过程___ 不相同_______ 。 13 ．已知L 是无头结点的单链表，且P 结点既不是首元素结点，也不是尾元素结点，添加 合适的语句。 1) P 结点之后插入结点S ：S->next=P->next; P->next=S; 2) P 结点之前插入结点S： pre=L; while(pre->next!=P) pre=pre->next; S->next=P; pre->next=S; 3) 在表首插入结点S ：S->next=L; L=S; 4) 在表尾插入结点S ：while(P->next) P=P->next; P->next=S; S->next=NULL; 14 ．已知P 结点是某双向链表的中间结点，添加合适的语句。 1) P 结点之后插入结点S： S->next=P->next; S->prior=P; P->next->Prior=S; P->next=S; 2) P 结点之前插入结点S： S->next=P; S->prior=P->prior; P->prior->next=S; P->prior=S; 3) 删除P 结点的直接后继结点： Q=P->next; P->next=Q->next; Q->next->prior=P; free(Q); 4) 删除P 结点的直接前驱结点： Q=P->prior; P->prior=Q->prior; Q->prior->next=P; free(Q); 5) 删除P 结点： P->prior->next=P->next; P->next->prior=P->prior; free(P); 15 ．在链表的结点中，数据元素所占存储量和整个结点所占的存储量之比称作存储密度 三、判断题 1．线性链表中各个链结点之间的地址不一定要连续。( R ) 2．若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。( W ) 3 ．若线性表采用顺序存储结构，每个数据元素占用 4 个存储单元，第12 个数据元素的存储地址为144 ，则第 1 个数据元素的存储地址是101 。( W ) 4 ．若长度为n 的线性表采用顺序存储结构，删除表的第i 个元素之前需要移动表中n-i+1 个元素。( W ) 5 ．在顺序表中取出第i 个元素所花费的时间与i 成正比。( W ) 四、写出下列算法完成的功能 1 ) ListNode *Demo1(LinkList L, ListNode *p) /*L 是带有头结点的单链表*/ { ListNode *q = L->next; while(q && q->next !=p) q = q->next; if(q) return q; else error( “*p is not in L! ”); } 寻找结点P 的前驱结点，若存在则返回前驱结点的地址，若不存在则给出错误信息 2) void Demo2(ListNode *p, ListNode *q) { DataType temp; temp = p->data; p->data = q->data; q->data = temp; } 交换结点p 和q 数据域的内容 3) LinkList Demo3(LinkList L) /*L 是无头结点的单链表*/ { ListNode *p, *q; if(L && L->next) { q=L; L=L->next; p=L; While(p->next) p=p->next; p->next = q; q->next = NULL; } return L; } 将链表L 第一个结点变为最后一个结点 4) LinkList *Connect(LinkList *L1, LinkList *L2) /* L1,L2 是带有头结点的单链表*/ { LinkList *p; p=L1; while(p->next!=NULL) p=p->next; p->next = L2->next; return(L1); } 将L2 连接到L1 后面
相关主题
文本预览