数据结构习题集(2022)
第一章绪论
1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。D={a，b，c，d，e，f}R={r}
(a)r={，，，，}
(b)r={，，，，}(c)r={，，，，}2．分析下列程序段的时间复杂度(a)for(i=0；i
for(j=0；j
for(i=0；i
for(j=0；j
While(i
3．在数据结构中，与所使用的计算机无关的是
A．存储结构B．物理结构C．物理和存储结构D．逻辑结构4．非线性结构中每个结点
A．无直接前驱结点B．只有一个直接前驱和直接后继结点C．无直接后继结点D．可能有多个直接前驱和多个直接后继结点5．可以把数据的逻辑结构划分成
A．内部结构和外部结构B．动态结构和静态结构C．紧凑结构和非紧凑结构D．线性结构和非线性结构6.算法的时间复杂度取决于（）。
A．问题的规模B.待处理数据的初态C.A和B7.计算机算法指的是（），它必须具备（）这三个特性。
(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性
C.确定性、有穷性、稳定性D.易读性、稳定性、安全性
第二章线性表
一、单项选择题
1．下面关于线性表叙述中，错误的是_(1)_。(1)：A．顺序表必须占用一片地址连续的存储单元B．链表不必占用一片地址连续的存储单元C．顺序表可以随机存取任一元素D．链表可以随机存取任一元素
2．在表长为n的单链表中，算法时间复杂度为O(n)的操作是(2)。(2)：A．查单链表中第i个结点B．在p结点之后插入一个结点C．删除表中第一个结点D．删除p结点的直接后继结点3．单链表的存储密度(3)
(3)：A．大于1B．等于1C．小于1D．不能确定4．在表长为n的顺序表中，算法的时间复杂度为O(1)的操作是(4)
(4)：A．在第n个结点之后插入一个结点B．在第i个结点前插入一个新结点C．删除第i个结点D．求表长5．在下列链表中不能从当前结点出发访问到其余各结点的是（5）。
(5)：A．单链表B．单循环链表C．双向链表D．双向循环链表6．在设头、尾指针的单链表中，与长度n有关的操作是（6）。(6)：A．删除第一个结点B．删除最后一个结点C.在第一个结点之前插入一个结点D.在表尾结点后插入一个结点7.设p结点是带表头结点的双循环链表
中的结点，则(1)在p结点后插入结点的语句序列中正确的是（7）。（7）：A.->ne某t=p->ne某t；p->ne某t->prior=；p->ne某t=；->prior=p；
B.p—>ne某t=；S—>ne某t=p—>ne某t；
p—>ne某t—>prior=；—>ne某t=p；C.p->ne某t=；p—>ne某t—>prior=；->ne某t=p—>ne某t；S—>ne某t=p；D.p->ne某t->prior=；p->ne某t=；->ne某t=p->ne某t；->ne某t=p；
(2)在p结点之前插入结点的语句序列中正确的是(8)。(8)：A.->prior=p->prior；p->prior->ne某t；->ne某t=p；
B.p->prior=；p->prior->ne某t=;->prior=p->prior；->ne某t=p;
C.p->prior->ne某t=；p->prior=;->prior=p->prior；->ne某t=p;
D.p->prior=；->ne某t=p；
p->prior->ne某t=；->prior=p->prior;
8．下列关于链表说法错误的是(9)(9)：A.静态链表中存取每一个元素的时间相同B．动态链表中存取每一个元素的时间不同
C．静态链表上插入或删除一个元素不必移动其他元素
2
p->prior=
D．动态链表上插入或删除一个元素不必移动其他元素
数组和链表9．在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是(10)
(10)：A.仅有头指针的单链表B．仅有头指针的单循环链表C．仅有头指针的双向链表D．仅有尾指针的单循环链表二、填空题
1．单链表中每个结点需要两个域，一个是数据域，另一个是(1)2．链表相对于顺序表的优点是(2)和(3)操作方便。
3．表长为n的顺序表中，若在第j个数据元素(1≤i≤n+1)之前插入一个数据元素，需要向后移动(4)个数据元素；删除第j个数据元素需要向前移动(5)个数据元素；在等概率的情况下，插入一个数据元素平均需要移动(6)个数据元素，删除一个数据元素平均需要移动(7)个数据元素。
4．单链表h为空表的条件是(8)
5．带表头结点的单链表h为空表的条件是(9)
6．在非空的单循环链表h中，某个p结点为尾结点的条件是(10)。7．在非空的双循环链表中，已知p结点是表中任一结点，则(1)在p结点后插入结点的语句序列是：
->ne某t=p->ne某t；->prior=p；(11)；(12)(2)在p结点前插入结点的语句序列是：
->prior=p->prior；->ne某t=p；(13)；(14)(3)删除p结点的直接后继结点的语句序列是：q=p->ne某t；p->ne某t=q->ne某t；(15)；free(q)；(4)删除p结点的直接前驱结点的语句序列是：q=p->prior；p->prior=q->prior；(16)；free(q)；(5)删除p结点的语句序列是：
p->prior->ne某t=p->ne某t；(17)；free(q)；
8．在带有尾指针r的单循环链表中，在尾结点后插入p结点的语句序列是p->ne某t=r->ne某t；(18)；(19)；删除第一个结点的语句序列是q=r->ne某t；(20)；free(q)。
三、应用题
1．简述顺序表和链表各自的优点。2．简述头指针和头结点的作用。四、算法设计题
1．请编写一个算法，实现将某插入到已按数据域值从小到大排列的有序表中。2．设计一个算法，计算单链表中数据域值为某的结点个数。3．设计一个算法，实现将带头结点的单链表进行逆置。
3
第三章栈和队列

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。