文档介绍：该【数据结构题集答案 】是由【森林书屋】上传分享，文档一共【25】页，该文档可以免费在线阅读，需要了解更多关于【数据结构题集答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构题集
第一章 绪论
一、单选题
,从逻辑上可以把数据结构分成【 C】。
【 A】。
【A】是数据的最小单位,【B】是数据的基本单位。
,这是指【 B】。
【 C】。
,不仅要考虑存储各数据元素的值,而且还要存储【
【 D 】。
C】。
。
【 A】。
【 B】。
,存储单元的地址【 A 】。
,部分不连续
二、判断题
【 .×】。
,它依赖于计算机的存储结构【× .】。
【× .】。
,但与使用的计算机有关【 .×】。
【 .×】。
三、填空题
数据元素之间的逻辑关系
。
表示
称为存储结构。
顺序存储结构
的表示和
链式存储结构
的表示。
集合
、
线性结构
、
树
和
图
四种,树结构和
图结构统称为
非线性结构
。
逻辑上相邻的元素
存储在物理位置
相邻的存储单元里;
链式存储方法中结点间的逻辑关系是由
指针域
表示的。
6、数据结构研究的是
逻辑结构
和物理结构
以及它们之间的相互关系,并对
于这种结构定义相应的
运算
,设计出相应的算法
。
问题规模n
的函数。
4个算法所有语句频度之和的表达式,其中的复杂度相同的是
A和B。
3
2
+1000
3
2
2
(n)=2n+3n
(n)=n
-nlogn-1000
(n)=n2log2n+n2 (n)=n2+1000
四、解答题
。
答:在数据结构中,逻辑结构和存储结构是密切相关的,存储结构不仅将数据元素存
储到计算机中,而且还要表示各数据元素之间的逻辑关系。 逻辑结构与计算机无关, 存储结
构是数据元素之间的关系在计算机中的表示。通常情况下,一种逻辑结构可以有多种存储结构,例如,线性结构可以采取顺序存储结构或链式存粗结构表示。
答:数据结构是相互间存在一种或多种特定关系的数据元素的集合,一般包括三个方
面的内容:数据的逻辑结构、存储结构和多数据的运算。数据类型是一个值得集合和定义在这个值集上的一组操作的总称。数据结构重点考虑元素之间的关系,数据类型重点考虑数据的个体特征。
,选择数据的存储结构时,应从哪些方面考虑
答:通常从两个方面考虑:第一是算法实现的存储空间复杂度;第二是算法执行的时间复杂度。若存储空间难以确定,宜选择链式存储结构,否则选择顺序存储结构。若插入、删除操作频繁,则选链式存储结构,否则选择顺序存储结构。
第二章 线性表
一、单选题
【
A】。
n个元素,以下操作中,【A】在顺序表上实现比在链表上实现效率更高。
(1≤i≤n)个元素的值
n个元素
x相等的元素在线性表中的序号
i个结点及其前驱,则采用【
n个【 C】的有限序列( n≥0)。
D】存储方法最节省时间。
,错误的是【
B】。
,则必须占用一片连续的存储单元
,则便于插入和删除操作
,则不必占用一片连续的存储单元
,则便于插入和删除操作
线性表的顺序存储结构是一种【A】。
存取的存储结构
【 C】。
(头指针为 h)为空的条件是【 A】。
==NULL >next==NULL
>next==h !=NULL
带头结点的单链表(头指针为h)为空的条件是【B】。
==NULL>next==NULL
>next==h!=NULL
(头指针为 L)为空的条件是【 D】。
==NULL
>next->prior==NULL
>prior==NULL
>next==L
(头指针为
head)的尾结点(由
p指向)满足【
C】。
>next==NULL
==NULL
>next==head
==head
,则选用【
A】最节省时间。
,则选用
【A】的存储方式最节省时间。
14.
在n个结点的线性表的顺序实现中,算法的时间复杂度为
O(1)的操作是【
A】。
i个结点的直接前驱
15.
若长度为n的线性表采用顺序存储结构,在第i个位置插入一个新元素的算法的时间复杂
度为【
C】。
(0)
(1)
(n)
(n2)
16.
对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为【
C】。
(n)O(n)
(n)O(1)
(1)O(n)
(1)O(1)
17.
线性表以链式方式存储,访问第
i个结点的时间复杂度为【
C】。
(i)
(1)
(n)
(i-1)
18.
循环链表
H尾结点p的特点是【
A】。
>next==H >next==H->next
==H ==H->next
二、判断题
【× 】 i个元素的时间同 i的大小有关。
【× 】。
【× 】。
【× 】,结点和结点内部的存储空间可以不连续。
【×】,执行删除单链表最后一个结点的操作与链表的长度无关。
三、填空题
,需要向后移动n-i+1个元素。
2.
在一个长度为n的顺序表中删除第
i个元素时,需要向前移动
n-i个元素。
简化插入、删除算法
。
,必须找到该结点的
直接前驱
结点。
5.
访问单链表中的结点,必须沿着
指针域
依次进行。
,
一个指向
直接前驱结点
,一个指向
直接后继
结点
。
链表中,删除最后一个结点的算法时间复杂度为
O(1)。
O(n)
。
,若每次都调用插入算法把一个元素插入到表头,则
整个算法的时间复杂度为
O(n)
,若每次都调用插入算法把一个元素插入到表尾,则
整个算法的时间复杂度为
O(n2)
。
10.
在
双向
链表中,可以用表尾指针代替表头指针。
,
其算法的时间复杂度最好的
情况是
O(n)
,最坏的情况是
O(n2)
。
O(1)
和
O(n)
。
,
在表头插入或删除与在其他位置插入或删除,
其操作过
程是否相同
相同
。
,在表头插入或删除与在其他位置插入或删除,其操
作过程是否相同 不相同 。
四、简答题
。
答:顺序表存储方式为数据分配连续的存储单元,数据元素按逻辑顺序依次存储到相应存储单元中,使得逻辑相邻的数据元素物理也相邻,因此可以实现随机访问线性表的数据元
素,即数据访问的时间复杂度为 O(1)。
链表存储方式分配的存储单元可以不连续,通过每个结点的指针域来表示数据元素之间的逻辑关系,只能顺序访问线性表中的数据元素。
若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用何种存储结构,为
什么
答:若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用链式存储结构。
因为链式存储结构在插入和删除数据元素时不需要移动数据元素,只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。
、双向循环链表和单循环链表中,若仅知道指针 p指向某结点,不知道头指
针,能否将结点 p从相应的链表中删除若可以,时间复杂度各为多少。
答:要实现删除 p结点的操作,必须找到其前驱结点,修改其指针域的值使其指向 p
的后继结点,以实现删除结点 p。单链表不行,因为不知道头指针就无法找到结点 p的前驱
结点。双向循环链表和单循环链表可以可以实现删除 p结点。单循环链表删除 p结点的时
间复杂度为 O(n),双循环链表删除 P结点的时间复杂度为 O(1)。
答:对带头结点的链表, 在表的任何结点之前插入结点或删除任何位置的结点, 所要做
的都是修改前一个结点的指针域, 因为在带头结点的链表中任何元素结点都有前驱结点。 如
果没有头结点,在首元结点前插入结点或删除首元结点都要修改头指针, 其算法要比带头结
点的算法复杂些。
其次,带头结点的链表结构,初始化后的头指针就固定了,除撤销算法外, 所有算法都
不会修改头指针,可以减少出错的可能性。
五、算法设计题
,写一个算法求单链表的长度。
解:算法基本思想: 从头结点的下一个结点开发, 遍历单链表的每个结点, 每遇到一个
结点,结点计算器加 1。
intlistlenght(linklistL)
{intlength=0;
P=L->next;
while(p)
{length++;
p=p->next;
}
return(length);
}
L,其中的元素按值递增有序排列,设计一个算法插入一个值为 x
的元素后保持该顺序表仍然递增有序,且空间复杂度为 0(1)。
voidinsertsq(sqlistL,elemtypex)
{n=;while(n>=0&&LT(x,[n])
{[n+1]=[n];n--;
}
[n+1]=x;
}
++;
return;
}
,从顺序表中删除值为 x的所有元素。
voiddelallsq(Sqlist&L)
{inti=0,j=0;while(j<
{if[j]!=x)
[i++]=[j];
j++;
}
=i;
}
第三章 栈和队列
一、单选题
【
C】。
【 A】。
、删除操作时,总是插入操作优先
,总要先做一次插入操作
,链栈有一个比较明显的优势是【
A】。
【
C】。
【① B】,队列的特点是【② A 】;栈和队列都是【③
1,2,3,4,则【④ A 】是不可能的出栈序列;若进队列的序列是
C 】若入栈序列是
1,2,3,4,则【⑤
】是可能的出队序列。
①②
③
④⑤ ,2,1,4 ,2,4,1 ,2,3,1 ,2,3,4
【 A】。
1,2,3,4,5,则可能得到的出栈序列为【
C】。
,2,5,3,4
,1,2,5,4
,2,5,4,1
,4,2,3,5
ABC,若输出序列变为 CBA,经过的栈操作为【 B】。
,pop,push,pop,push,pop
push,push,push,pop,pop,pop
push,push,pop,pop,push,pop
push,pop,push,push,pop,pop
栈在【D】应用。
,B,C
、右括号是否配对的算法,采用【
D】数据结构最佳。
【 D】。
【
D】。
A[0..M-1]
中,则入队时的操作为【
B】。
=rear+1 =(rear+1)%M
=(rear+1)%(M+1) =(rear+1)%(M-1)
A[0..M-1]
中,则出队时的操作为【
B】。
=front+1
=(front+1)%M
=(front+1)%(M+1)=(front+1)%(M-1)
M,则队空的条件是【 A】。
==front B.(rear+1)%M==front
+1==front D.(rear-1)%M==front
M,则队满的条件是【 B】。
==front B.(rear+1)%M==front
+1==front D.(rear-1)%M==front
二、判断题
【× 】,因此递归离不开队列。
【√ 】,既可以是顺序方式,又可以是链式方式。
【√ 】,则入队和出队算法的时间复杂度为 0(1)。
【× 】。
【√ 】,即使不设置尾指针也能进行入队操作。
【√ 】。
【×】,所得的输出序列一定相同。
【√ 】。
【√ 】,可以根据队首指针和队尾指针的值计算出来。
三、填空题
,目的是为了克服 顺序队列的假溢出 。
3种方法,它们是 少用一个元素 、设空满标志 、用
计数器记录队列中元素个数 。
栈只能在表一端进行插入和删除操作, 队列限制在表的一端进行
插入操作,在另一端进行删除操作 。
12345,则栈的输出序列 43512是 错误的 。
,栈中已有 i-1个元素,则第 i个元素进栈操作的算法时间复
杂度是 O(1) 。
,则创建一个空栈要执行的操作是
=+1)%QSize
=+1)%QSize
>next== 。
,最好使用 链栈 。
。
。
top=NULL
。
四、简答题
答:因为栈是限定在表的一端进行插入和删除操作, 所以后入栈的数据元素总是先出栈,
所以说栈是一种后进先出表。
,其输入序列是 A,B,C,试给出全部可能的输出序列。
答:可能的出栈序列是: ABC、ACB、BAC、BCA、CBA。
,并分别阐述其工作原
理。
答:队列上溢指在队列的顺序存储分配中,所有单元中已有元素,再进行插入操作时称为队列上溢。
假溢出指在队列的顺序存储分配中,分配给队列的存储空间有存储单元未被占用,但按照操作规则而使进队的数据元素无法进队的现象。
解决假溢出问题的方法是在队列的顺序存储分配中,分配给队列的存储空间可以循环使用,其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即:
入队操作:=+1)%MSize
出队操作:=+1)%MSize
, 故可以只设一个头指针或只设一个尾指针, 请分析用
哪种方案最合适。
答:使用循环链表来表示队列,设置尾指针比较合适,因为入队操作可以直接在尾结
点后进行插入操作, 出队操作时可以根据尾指针很容易找到链表的头结点, 入队出队操作的
算法时间复杂度均为O(1)。若只设头指针,则出队操作的算法时间复杂度为O(1),入队操作的算法时间复杂度为O(n)。
、栈和队列的异同
答:栈和队列都是操作位置受限的线性表,即对插入和删除操作的位置加以限制。栈
是仅允许在表的一端进行插入和删除操作的线性表,因而是后进先出表。队列是允许在表的一端进行插入,在表的另一端进行删除的线性表,因而是先进先出表。线性表可以在任何位置进行插入和删除操作。
五、算法设计题
,利用栈和队列的基本运算将指定栈中的元素顺序逆转。
解:算法基本思想:先将栈中元素出栈运算移至队列中,再将队列中元素出队列移至栈中。
voidreverse(Stack&st)
{Queuesq;ElemTypex;InitQueue(sq)
while(!StackEmpty(st)
{pop(st,x)EnQueue(sq,x);
}
while(!QueueEmpty(sq)
{DeQueue(sq,x);Push(st,x);
}
DestroyQueue(sq);
}
,利用栈的基本运算返回指定栈中栈底元素。
解:先将栈中元素依次移至另一个临时栈中,最后一个元素即为栈底元素,设为x.。再将临时栈中元素移至原栈中,即恢复栈内容。
ElemTypebottom(Stack&st)
{ElemTypex,y;Stacktmpst;
InitStack(tmpst)
while(!StackEmpty(st)
{pop(st,x)
push(tmpst,x);
}
while(!QueueStack(temst)
{pop(tmpst,y); 计一个算法,利用栈来实现带头结点的单链表 h的逆序。
解:算法基本思想:将单链表结点依次放入链栈中,链栈本身就是一个单链表,即实
现了原单链表的逆序。假设链栈不带头结点,再加上原来的头结点,就完成了原单链表的逆序。
Voidrevert(SNode*h)
{SNode*st=NULL,*p=h->next,q;While(p)
{q=p->next;p->next=st;
st=p;
p=q;
}
h->next=st;
}