数据结构题集答案Word格式.docx
- 文档编号:4492115
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:34
- 大小:170.07KB
数据结构题集答案Word格式.docx
《数据结构题集答案Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构题集答案Word格式.docx(34页珍藏版)》请在冰点文库上搜索。
3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【X.】。
4.算法的优劣与算法的描述语言无关,但与使用的计算机有关【.x】。
5.数据结构的抽象操作的定义与具体实现有关【.X】。
三、填空题
1.数据的逻辑结构指数据元素之间的逻辑关系。
2.—个数据结构在计算机中的表示称为存储结构。
3.数据的物理结构主要包括顺序存储结构的表示和链式存储结构的表示。
4.数据逻辑结构包括集合、线性结构、树和图四种,树结构和图结构统称
为。
5.顺序存储方法把逻辑上逻辑上相邻的元素存储在物理位置相邻的存储单元里;
链式存储方
法中结点间的逻辑关系是由指针域表示的。
6.数据结构研究的是逻辑结构和物理结构以及它们之间的相互关系,并对于这种结构定
义相应的运算,设计岀相应的算法。
7.算法的执行时间是问题规模n的函数。
8.以下是4个算法所有语句频度之和的表达式,其中的复杂度相同的是A和B。
3232
(n)=2n3+3n2+1000(n)=n3-n2log2n-1000
222
(n)=nlog2n+n(n)=n+1000
四、解答题
1.简述数据的逻辑结构和存储结构的关系。
答:
在数据结构中,逻辑结构和存储结构是密切相关的,存储结构不仅将数据元素存储到计算机中,而且还要表示各数据元素之间的逻辑关系。
逻辑结构与计算机无关,存储结构是数据元素之间的关系在计算机中的表示。
通常情况下,一种逻辑结构可以有多种存储结构,例如,线性结构可以采取顺序存储结构或链式存粗结构表示。
2.数据结构和数据类型有什么区别?
数据结构是相互间存在一种或多种特定关系的数据元素的集合,一般包括三个方面的内容:
数据的逻辑结构、存储结构和多数据的运算。
数据类型是一个值得集合和定义在这个值集上的一组操作的总称。
数据结构重点考虑元素之间的关系,数据类型重点考虑数据的个体特征。
3.当为解决某一问题已经选定其数据的逻辑结构后,选择数据的存储结构时,应从哪些方面考虑?
答:
通常从两个方面考虑:
第一是算法实现的存储空间复杂度;
第二是算法执行的时间复杂度。
若
存储空间难以确定,宜选择链式存储结构,否则选择顺序存储结构。
若插入、删除操作频繁,则选链式存储结构,否则选择顺序存储结构。
第二章线性表
1.链表不具备的特点是【A】。
A.可随机访问任一结点B.插入删除不需要移动元素
C.不必事先估算存储空间D.所需空间与其长度成正比
2.设线性表有n个元素,以下操作中,【A】在顺序表上实现比在链表上实现效率更高
A.输岀第i(1<
i<
n)个元素的值
B.顺序输出这n个元素
C.交换第1个与第2个元素的值
D.输岀与给定值x相等的元素在线性表中的序号
3.如果最常用的操作是取第
i个结点及其前驱,则采用【
D]存储方法最节省时间
A.单链表
B.双链表
C.线性链表
D.顺序表
4.线性表是具有
n个【C
]的有限序列(
n》0)o
A.表元素
B.字符
C.数据元素
D.数据项
5.下面关于线性表的叙述中,
错误的是【
B]o
A.线性表采用顺序存储,则必须占用一片连续的存储单元
B.线性表采用顺序存储,则便于插入和删除操作
C.线性表采用链式存储,则不必占用一片连续的存储单元
D.线性表采用链式存储,则便于插入和删除操作
6.线性表的顺序存储结构是一种【A】。
A.随机存取的存储结构B.顺序存取的存储结构
C.索引存取的存储结构存取的存储结构
7.单链表中增加一个头结点的目的是为了【C】。
A.使单链表至少有一个结点B.标识表首结点的位置
C.方便运算的实现
D.说明单链表是线性表的链式存储
8.不带头结点的单链表(头指针为h)为空的条件是【A】。
==NULL>
next==NULL
>
next==h!
=NULL
9.带头结点的单链表(头指针为h)为空的条件是【B]o
10.带头结点的循环双向链表(头指针为L)为空的条件是【D]o
next->
prior==NULL
prior==NULL>
next==L
11.非空的循环单链表(头指针为head)的尾结点(由p指向)满足【C]o
next==NULL==NULL
next==head==head
12.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用【A]最节省时间。
A.带头结点的双循环链表B.单循环链表
C.带尾指针的单循环链表D.单链表
13.若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除,则选用【A]的存储
方式最节省时间。
A.顺序表B.双链表
C.带头结点的双循环链表D.单循环链表
14.
O
(1)的操作是【A】。
在n个结点的线性表的顺序实现中,算法的时间复杂度为
A.访问第i个结点和求第i个结点的直接前驱
B.在第i个结点后插入一个新结点
C.删除第i个结点D.以上都不对
15.
若长度为n的线性表采用顺序存储结构,在第i个位置插入一个新元素的算法的时间复杂度为C】。
1.向一个长度为n的顺序表中的第i个元素之前插入一个元素时,需要向后移动素。
2.在一个长度为n的顺序表中删除第i个元素时,需要向前移动n-i个元素。
3.在单链表中设置头结点的作用是简化插入、删除算法。
4.在单链中要删除某一指定结点,必须找到该结点的直接前驱结点。
5.访问单链表中的结点,必须沿着指针域依次讲行。
6.在双链表中每个结点有两个指针域,一个指向直接前驱结点,一个指向直接后继结
点。
7.在双向循环链表中,删除最后一个结点的算法时间复杂度为O
(1)。
8.访问一个线性表中具有给定值的时间复杂度的数量级是O(n)。
9.由n个数据元素生成一个顺序表,若每次都调用插入算法把一个元素插入到表头,则整个算法的时
间复杂度为O(n),若每次都调用插入算法把一个元素插入到表尾,则整个算法的时间复杂度为
O(n2)。
10.在链表中,可以用表尾指针代替表头指针。
11.根据n个数据元素建立对应的顺序表和单链表存储结构,其算法的时间复杂度最好的情况是
O(n,最坏的情况是—O(n2。
12.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是O
(1)和O(n)
13.在一个带头结点的单链表中,在表头插入或删除与在其他位置插入或删除,其操作过程是否相
同?
相同。
14.在一个不带头结点的单链表中,在表头插入或删除与在其他位置插入或删除,其操作过程是否相同?
不相同。
四、简答题
1.阐述顺序表和链表存储方式的特点。
顺序表存储方式为数据分配连续的存储单元,数据元素按逻辑顺序依次存储到相应存储单元中,使得逻辑相邻的数据元素物理也相邻,因此可以实现随机访问线性表的数据元素,即数据访问的时间复杂度为0
(1)。
链表存储方式分配的存储单元可以不连续,通过每个结点的指针域来表示数据元素之间的逻辑关系,只能顺序访问线性表中的数据元素。
2.若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用何种存储结构,为什么?
若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用链式存储结构。
因为链式存
储结构在插入和删除数据元素时不需要移动数据元素,只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。
3.在单链表、双向循环链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结
点p从相应的链表中删除?
若可以,时间复杂度各为多少。
要实现删除p结点的操作,必须找到其前驱结点,修改其指针域的值使其指向p的后继结点,
以实现删除结点p。
单链表不行,因为不知道头指针就无法找到结点p的前驱结点。
双向循环链表和单
循环链表可以可以实现删除p结点。
单循环链表删除p结点的时间复杂度为0(n),双循环链表删除P结
点的时间复杂度为0
(1)。
4.对链表设置头结点的作用是什么?
对带头结点的链表,在表的任何结点之前插入结点或删除任何位置的结点,所要做的都是修改前一个结点的指针域,因为在带头结点的链表中任何元素结点都有前驱结点。
如果没有头结点,在首元结点前插入结点或删除首元结点都要修改头指针,其算法要比带头结点的算法复杂些。
其次,带头结点的链表结构,初始化后的头指针就固定了,除撤销算法外,所有算法都不会修改头指针,可以减少出错的可能性。
五、算法设计题
1.已知一个线性表用含头结点的单链表做存储结构,写一个算法求单链表的长度。
解:
算法基本思想:
从头结点的下一个结点开发,遍历单链表的每个结点,每遇到一个结点,结点计算器加1。
intlistlenght(linklistL)
{intlength=0;
P=L->
next;
while(p)
{length++;
p=p->
}
return(length);
2.已知一个顺序表L,其中的元素按值递增有序排列,设计一个算法插入一个值为x的元素后保持
该顺序表仍然递增有序,且空间复杂度为0
(1)。
voidinsertsq(sqlistL,elemtypex)
{n=;
while(n>
=0&
&
LT(x,[n])
{[n+1]=[n];
n--;
[n+1]=x;
++;
return;
3.
x的所有元素
写一个算法,从顺序表中删除值为voiddelallsq(Sqlist&
L)
{inti=0,j=0;
while(j<
{if[j]!
=x)
[i++]=[j];
j++;
第三章栈和队列
1.对于栈操作数据的原则是【C】。
A.先进先出B.后进后出
C.后进先岀D.不分顺序
2.队列的先进先出特征是指【A】。
A.最后插入队列的元素总是最后被删除
B.当同时进行插入、删除操作时,总是插入操作优先
C.每当有删除操作时,总要先做一次插入操作
D.每次从队中删除的元素总是最早插入的元素
A.无法判断队列是否为空B.无法判断队列是否为满
C.队列不可能满D.以上说法都不对
13.队列存放在A[0..M-1]中,则入队时的操作为【B】。
=rea叶1=(rear+1)%M
=(rear+1)%(M+1)=(rear+1)%(M-1)
14.队列存放在A[0..M-1]中,则岀队时的操作为【B]o
=front+1B.front=(front+1)%M
C.front=(front+1)%(M+1)D.front=(front+1)%(M-1)
15.循环队列的最大容量为M,则队空的条件是【A]o
==frontB.(rear+1)%M==front
+1==frontD.(rear-1)%M==front
16.循环队列的最大容量为M,则队满的条件是【B]o
二、判断题
【x]1.队列在函数调用时必不可少,因此递归离不开队列。
[V]2.栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。
[V]3.设尾指针的循环链表表示队列,则入队和岀队算法的时间复杂度为0
(1)o
[x]4.队列逻辑上是一个上端和下端既能增加又能减少的线性表。
【V]5.在链队列中,即使不设置尾指针也能进行入队操作。
【V]6.栈和队列度是限制存取点的线性结构。
[x]7.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和岀栈操作,所得的输岀序列一定相同。
【V]8.栈是实现函数调用所必需的数据结构。
【V]9.顺序队列中的元素个数,可以根据队首指针和队尾指针的值计算岀来。
1.循环队列的引入,目的是为了克服顺序队列的假溢出o
2.区分循环队列的空与满有3种方法,它们是少用一个元素、设空满标志、用计数器记录
队列中元素个数o
3.栈和队列的区别是栈只能在表一端讲行插入和删除操作,队列限制在表的一端讲行插入操作,
在另一端进行删除操作o
4.一个栈的输入序列是12345,则栈的输岀序列43512是o
5.设栈采取顺序存储结构,栈中已有i-1个元素,则第i个元素进栈操作的算法时间复杂度是_O
(1)o
6.若用不带头结点的单链表表示栈,则创建一个空栈要执行的操作是_top=NULIo
7.从循环队列中删除一个元素的操作是=+1)%QSizeo
8.从循环队列中插入一个元素的操作是=+1)%QSizeo
9.判断链队列中只有一个结点的条件是>
next==o
10.如果栈的最大长度难以估计,最好使用链栈o
1.为什么说栈是一种后进先出表?
因为栈是限定在表的一端进行插入和删除操作,所以后入栈的数据元素总是先岀栈,所以说栈是一种后进先出表。
2.对于一个栈,其输入序列是A,B,C,试给岀全部可能的输岀序列。
可能的出栈序列是:
ABC、ACB、BAC、BCA、CBA。
3.何谓队列上溢?
何为假溢出现象?
有哪些解决假溢出问题的方法,并分别阐述其工作原理。
队列上溢指在队列的顺序存储分配中,所有单元中已有元素,再进行插入操作时称为队列上溢。
假溢出指在队列的顺序存储分配中,分配给队列的存储空间有存储单元未被占用,但按照操作规则而使进队的数据元素无法进队的现象。
解决假溢出问题的方法是在队列的顺序存储分配中,分配给队列的存储空间可以循环使用,其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。
即:
入队操作:
=+1)%MSize
出队操作:
4.队列可以用单循环链表来实现,故可以只设一个头指针或只设一个尾指针,请分析用哪种方案最合适。
使用循环链表来表示队列,设置尾指针比较合适,因为入队操作可以直接在尾结点后进行插入操作,出队操作时可以根据尾指针很容易找到链表的头结点,入队出队操作的算法时间复杂度均为O
(1)。
若只设头指针,则出队操作的算法时间复杂度为O
(1),入队操作的算法时间复杂度为O(n)。
5.简述线性表、栈和队列的异同?
栈和队列都是操作位置受限的线性表,即对插入和删除操作的位置加以限制。
栈是仅允许在表的一端进行插入和删除操作的线性表,因而是后进先出表。
队列是允许在表的一端进行插入,在表的另一端进行删除的线性表,因而是先进先出表。
线性表可以在任何位置进行插入和删除操作。
五、算法设计题
1.设计一个算法,利用栈和队列的基本运算将指定栈中的元素顺序逆转。
解:
先将栈中元素出栈运算移至队列中,再将队列中元素出队列移至栈中。
voidreverse(Stack&
st)
{Queuesq;
ElemTypex;
InitQueue(sq)
while(!
StackEmpty(st)
{pop(st,x)
EnQueue(sq,x);
QueueEmpty(sq)
{DeQueue(sq,x);
Push(st,x);
DestroyQueue(sq);
2.设计一个算法,利用栈的基本运算返回指定栈中栈底元素。
先将栈中元素依次移至另一个临时栈中,最后一个元素即为栈底元素,设为X.。
再将临时栈中
元素移至原栈中,即恢复栈内容。
ElemTypebottom(Stack&
{ElemTypeX,y;
Stacktmpst;
InitStack(tmpst)
push(tmpst,x);
QueueStack(temst)
h的逆序。
即实现了原单链
{pop(tmpst,y);
计一个算法,利用栈来实现带头结点的单链表解:
将单链表结点依次放入链栈中,链栈本身就是一个单链表,表的逆序。
假设链栈不带头结点,再加上原来的头结点,就完成了原单链表的逆序。
Voidrevert(SNode*h)
{SNode*st=NULL,*p=h->
next,q;
While(p)
{q=p->
next;
p->
next=st;
st=p;
p=q;
h->
、单选题
1.串是任意有限个【
A.符号构成的集合
C.字符构成的集合
第四章串
D】。
B.符号构成的序列
D.字符构成的序列
2.串是一种特殊的线性表,其特殊性体现在【
A.可以顺序存储
C.数据元素可以使多个字符
3.两个串相等必有串长度相等且
A.串的各位置字符任意
C.两个串含有相同的字符
4.设有两个串p和q,求q在p
B】。
B.数据元素是一个字符
D.可以链接存储
B.串中各位置字符均对应相等
D.两个串所含字符任意
中首次岀现的位置的运算称着【B】
A.连接B.模式匹配
C.求子串D.求串长
、填空
1.空串是长度为0的串
2.一个串中任意连续字符组成的子序列
称为该串的子串
3.设s=“abed”,则执行语句s2=Substr(s,2,2)后,s2=“be”。
4.空白串是由一个或多个空格字符组成的串,其长度等于其所包含的空格字符的个
数。
第五章数组
1.一维数组与线性表的区别是【A】。
A.前者长度固定,后者长度可变
B.后进长度固定,前者长度可变
C.两者长度均固定D.两者长度均可变
2.多维数组的数组元素之间的关系,【A】。
A.是线性的B.是树型的
C.既是线性的,又是树型的
D.既不是线性的,也不是树型的
3.设有数组A[8][10],每个元素占3个存储单元,存放该数组的存储单元数为【C】。
4.设有数组A[8][10],每个元素占3个存储单元,首地址为SA,则元素⑺[5]的起始地址是【D】。
+141+144+222+225
5.设有一个n*n的对称矩阵,采用压缩存储,则存入内存的元素个数为【C】。
*n*n/2*(n+1)/2D.(n+1)2/2
6.设A是一个n*n的对称矩阵,压缩存储到一个一维数组B[0..n(n+1)/2-1]中,则下三角部分元素ai,j在B
中的位置是【A】。
A.i(i-1)/2+j-1B.i(i-1)/2+j
C.i(i+1)/2+j-1D.i(i+1)/2+j
7.稀疏矩阵一般的压缩方法有两种,即【C】。
A.二维数组和三维数组B.三元组和散列
C.三元组和十字链表D.散列和十字链表
8.设有一个10*10的对称矩阵A,以行主次序进行压缩存储,每个元素占一个存储单元,ai,i的地址是
1,则A8,5的起始地址是【B】。
二、解答题
1.设数组A[50][80],其基地址为2000,每个元素占2个存储单元,以行序位主序顺序存储,回答下列问题:
(1)该数据组由多少元素?
(2)该数组占用多少存储单元?
(3)数组元素a[30][30]的存储地址是多少?
(1)该数组有:
50*80=4000个元素
(2)该数组占用4000*4=8000个存储单元(3)loc(30,30)=2000+(30*80+30)*2=2000+4860=6860
第六章树与二叉树
1.有关二叉树下列说法正确的是【B】。
A.
B.一棵二叉树的度可以小于2
D.二叉树中任何一个结点的度为2
二叉树的度为2
C.一棵二叉树至少有一个结点的度为2
2.利用二叉链表存储树,则根结点的右指针是【C】
A.指向最左孩子B.指向最右孩子
C.空
D.非空
3.若一棵二叉树具有
10个度为2的结点,5个度为1的结点,则度为0的结点个数为【B】。
D.不确定
4.一棵二叉树有1001个结点,其中叶结点的个数为【D】
5.一棵完全二叉树有1001个结点,其中叶结点的个数为【D】
D.以上答案均不对
6.一棵具有1025个结点的二叉树的高h为【C】。
至1025之间至1024之间
7.一棵124个叶结点的完全树,最多具有【B】个结点。
8.一棵具有10个叶结点的二叉树具有【B】度为2的结点
9.已知一棵完全二叉树有625个结点,叶结点的个数为【C】。
D.其它
10.一棵具有n个结点的完全二叉树的高h为【AB】。
A.log2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)