数据结构 期末习题
- 格式：doc
- 大小：50.00 KB
- 文档页数：7
1 第2章 线性表习题
一、 单项选择题
1、在有n 个结点顺序表中，等概率插入结点所需的结点移动平均次数为 ① ，等概率删除结点所需的结点移动平均次数为 ② 。
① A.n B.(n-1)/2 C.n/2 D.(n+1)/2
A.n B.(n-1)/2 C.n/2 D.(n+1)/2
2、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是 。
A访问第i个结点. (1≤i≤n)
B.在第i个结点之前插入一个新结点(1≤i≤n)
C.删除第i个结点(1≤i≤n)
D.将n个结点从大到小排序(1≤i≤n)
3、顺序表中逻辑上相邻的结点的物理位置 。
A.按照某种规律排序 B.不必相邻
C.一定相邻 D.无要求
4、相对于顺序存储而言，链式存储的优点是 。
A.随机存取 B.增、删操作方便 C.节约空间 D.结点间关系简单
5、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s所指结点，则应执行的操作是 。
A. q->next=s;s->next=p; B. p->next=s->next;s->next=p;
C. s->next=p->next;p->next=s; D. p->next=s;s->next=q;
6、在一个单链表中，若p所指结点不是最后结点，删除p之后的结点，则执行 。
A. p->next=p->next->next; B. p=p->next;
C. p=p->next->next; D. p->next=p;
7、在一个单链表中，若p所指结点不是最后结点，删除p的直接后继结点，则执行 。
A. p->next=p->next->next; B. p=p->next;
C. p=p->next->next; D. p->next=p;
8、链表不具备的特点是 。
A. 可以随机访问任一结点 B. 插入操作不需要移动元素
C. 不必事先估计存储空间 D. 所需空间与其长度成正比
2 9、不带头结点的单链表L为空的判定条件是 。
A. L!=NULL B. L->next==NULL
C. L->next==L D. L==NULL
10、带头结点的单链表L为空的判定条件是 。
A. L!=NULL B. L->next==NULL
C. L->next==L D. L==NULL
11、带头结点的双循环链表L为空的判定条件是 。
A. L==NULL B. L->next==NULL
C. L->back==NULL D. L->next==L
12、非空循环单链表L的尾结点（由p所指向）满足 。
A. p->next==NULL B. p==NULL
C. p->next==L D. p==L
13、在双循环链表L的p所指结点之前插入s所指向的结点的操作是 。
A. p->back=s;s->next=p;p->back->next=s;s->back=p->back;
B. p->back=s;p->back->next=s;s->next=p;s->back=p->back;
C. s->next=p;s->back=p->back; p->back=s; p->back->next=s;
D. s->next=p; s->back=p->back; p->back->next=s; p->back=s;
14、需要分配较大空间，插入和删除不需要移动元素的线性表其存储结构是 。
A.线性链表 B.单链表 C.静态链表 D.顺序存储
答：C。静态链表是用一维数组实现的链式存储结构，每个数据元素附加一个指针（通常为下一个元素的下标）。它允许不改变各元素的物理位置，只需重新链接就能够改变这些元素的逻辑顺序。需要分配较大空间，插入和删除需要修改指针，不需要移动元素。
15、如果最常用的操作是取第i个结点及其前驱，则采用 。
A.双链表 B.单链表 C.循环单链表 D.顺序表
16、在具有n 个结点有序单链表中，插入新结点并仍然保持有序的时间复杂度是 。
A.O(1) B.O(n) C.O(n2) D.O(nlog2n)
17、在不带头结点的单链表L（长度n>1）上，设有头指针和尾指针，执行 操作与链表的长度有关。
A. 删除单链表的第一个元素
B. 删除单链表的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D. 在单链表最后一个元素后插入一个新元素
3 18、线性表有n个元素，以下算法中， 在顺序表上实现比在链表上实现效率更高。
A.输出第i个结点值(1≤i≤n)
B.交换第0个元素和第1个元素的值
C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
19、线性表有n个元素，以下算法中， 在单链表中实现要比顺序表上实现效率更高。
A.删除所有值为x的结点 顺序表每删除一个元素都要移动元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第n-i个元素的值(1≤i≤n)
20、与单链表相比，双链表的优点之一是 。
A.插入、删除操作更简单
B.可以进行随机访问
C.可以省略表头指针和表尾指针
D.顺序访问相邻结点更灵活
二、 填空题
1、在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有 ② 个前驱结点；最后一个结点 ③ 后继结点，其余每个结点有且只有 ④ 个后继结点。
2、线性结构中元素之间存在 ① 关系，树型结构中元素之间存在 ② 关系，图形结构中元素之间存在 ③ 关系。
3、在长度为n的顺序表中，第i个元素(1≤i≤n)之前插入一个元素时，n-i+1 个元素。
4、在长度为n的顺序表中，删除第i个元素(1≤i≤n)时，需要向前移动 n-i 个元素。
5、设线性表L是顺序存储，若起始地址L(a1)=1000，每个元素占4个存储单元，则L(a6)=
1020 。
1000+4*5=
6、在单链表中，删除p所指结点的后继结点的语句是 。
7、访问单链表中的结点，必须沿着 依次进行。
8、在顺序表中插入或删除一个元素，需要平均移动 一半 元素，移动的元素个数与
有关。表长 位置 4
9、顺序表中逻辑上相邻的元素的物理位置 紧邻。单链表中逻辑上相邻的元素的物理位置 紧邻。
10、在单链表中，除首结点外，任一结点的存储位置由 指示。
11、在单链表中设置表头结点作用是 。
12、什么情况下顺序表比链表好？
13、已知L是无表头结点的单链表，p结点位于链表中间，试从下列答案中选择合适的语句序列。
A.在p结点后插入s结点的语句序列是 。
B.在p结点插入s结点的语句序列是 。
C.在表首插入s结点的语句序列是 。
D.在表尾插入s结点的语句序列是 。
(1)p->next=s;
(2)p->next=p->next->next;
(3) p->next=s->next;
(4) s->next=p->next;
(5) s->next=L;
(6) s->next=NULL;
(7) q=p;
(8) while(p->next!=q) p=p->next;
(9) while(p->next!=NULL) p=p->next;
(10) p=q;
(11) p=L;
(12) L=s;
(13) L=p;
14、已知L是带表头结点的单链表，p结点位于链表中间，试从下列答案中选择合适的语句序列。
A.删除p结点的直接后继结点的语句序列是 。
B.删除p结点的直接前驱结点的语句序列是 。
C.删除p结点的语句序列是 。
D.删除首结点的语句序列是 。
E.删除尾结点的语句序列是 。
(1) p=p->next;
(2) p->next=p;
(3) p->next=p->next->next;
(4) p =p->next->next; 5 (5) while(p!=NULL) p=p->next;
(6) while(q->next!=NULL){ p=q;q=q->next;}
(7) while(p->next!=q) p=p->next;
(8) while(p->next->next!=q) p=p->next;
(9) while(p->next->next!=NULL) p=p->next;
(10) q=p;
(11) q=p->next;
(12) p=L;
(13) L=L->next;
(14) free(q);
15、已知p是某双向链表的中间结点，试从下列答案中选择合适的语句序列。
A. 在p结点后插入s结点的语句序列是 。
B. 在p结点前插入s结点的语句序列是 。
C. 删除p结点的直接后继结点的语句序列是 。
D. 删除p结点的直接前驱结点的语句序列是 。
E. 删除p结点的语句序列是 。
(1) p->next=p->next->next;
(2) p->back=p->back->back;
(3) p->next=s;
(4) p->back=s;
(5) s->next=p;
(6) s->back=p;
(7) s->next=p->next;
(8) s->back=p->back
(9) p->back->next=p->next;
(10) p->back->next=p;
(11) p->next->back=p;
(12) p->next->back=s;
(13) p->back->next=s;
(14) p->next->back= p->back;
(15) q= p->next
(16) q= p->back
(17) free(p)
(18) free(q);
16、在 链表上，删除最后一个结点的算法的时间复杂度为O(1)。
17、在非循环的 链表中，可以用尾指针代替表头指针。
