数据结构复习题目及答案
- 格式:docx
- 大小:1017.12 KB
- 文档页数:55
《数据结构-C语言版》
第一章绪论
单项选择题
1.在数据结构中,数据的基本单位是_________。
A.数据项
B.数据类型
C.数据元素
D.数据变量
2.数据结构中数据元素之间的逻辑关系被称为______。
A.数据的存储结构
B.数据的基本操作
C.程序的算法
D.数据的逻辑结构3.在数据结构中,与所使用计算机无关的是数
据的_______。
A.存储结构
B.逻辑和物理结构
C.逻辑结构
D.物理结构4.在链式存储结构中,数据之间的关系是通过________体现的。
A.数据在内存的相对位置
B.指示数据元素的指针
C.数据的存储地址
D.指针
5.计算算法的时间复杂度是属于一种_______。
A.事前统计的方法
B.事前分析估算的方法
C.事后统计的方法
D.事后分析估算的方法
6.在对算法的时间复杂度进行估计的时候,下列最佳的时间复杂
度是______。
2
A.n
B.nlogn
C.n
D.logn
7.设使用某算法对n个元素进行处理,所需的时间是T(n)=100nlog2n+200n+2000,则该算法的渐近时间复杂度
为_______。
A.O(1)
B.O(n)
C.O(200n)
D.O(nlog2n)
1
CDCBBDD
第二章线性表
单项选择题
1.链表不具有的特点是________。
A.可随机访问任一元素
B.插入和删除时不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表的长度正比
2.设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100,则第6个元素占
用的最后一个存储单元的地址为。
A.139
B.140
C.147
D.148
3.在线性链表存储结构下,插入操作算法。
A.需要判断是否表满
B.需要判断是否表空
C.不需要判断表满
D.需要判断是否表空和表满
4.在一个单链表中,若删除p所指结点的后继结点,则执行。
A.p->next=p->next->next;
B.p->next=p->next;
C.p=p->next->next;
D.p=p->next;p->next=p->next->next;
5.将长度为 n的单链表接在长度为m的单链表之后的算法时间复杂度为。
A.O(n)
B.O(1)
C.O(m)
D.O(m+n)
6.需要预分较大空间,插入和删除不需要移动元素的线性表,其存储结构是。A.单链表 B.静态链表 C.线性链表 D.顺序存储方式ACCABB
填空题
1.在带表头结点的单链表中,当删除某一指定结点时,必须找到该结点的_____结点。2.在单链表中,指针p所指结点为最后一个结点的条件是。
3.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是。4.在一个长度为n的顺序表中第i个元素(1≤i≤n)之前插入一个元素时,需向后移动元
素的个数是。
5.在长度为 n的顺序表中插入一个元素的时间复杂度为。
1前驱
2p->next==NULL
2
3.1
4.n-i+1
5.O(n)
例题解析
【例2-1】编写一个算法将一个单链表逆转,要求在原表上进行,不允许重新建链表。
解:该算法可以在遍历原表的时候将各结点的指针逆转,从原表的第一个结点开始,头结点的指针在最后修改成指向原表的最后一个结点,即新表的第一个结点。实现本题功能的函数如下:
voidinverse(Lnode*h)
{s=h->next;
if(s==NULL) return;
q=NULL;
p=s;
while(p!=NULL)
{p=p->next;
s->next=q; /*逆转指针*/
q=s; /*指针前移*/
s=p; }
h->next=q; /*头指针h的后继是p*/
}
【例2-2】编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。
解:对于两个或两个以上的,结点按元素值有序排列的单链表进行操作时,应采用
“指
针平行移动,依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元
素
进行比较,复制小的并插
入c表尾。当两表中之一已到表尾,则复制另一个链表的剩余部分,插入到c表尾。设pa、pb分别指向两表当前结点,p指向c表的当前表尾结点。若设A中当前所指的元素为a,B中当前所指的元素为b,则当前应插入到C中的元素c为
a a b
c
a b
b
例如:A=(3,5,8,11)
B=(2,6,8,9,11,15,20)
则C=(2,3,5,6,8,8,9,11,11,15,20)
实现本题功能的函数如下:
Lnode*hb(Lnode*pa,Lnode*pb)