数据结构习题Word文件下载.docx
- 文档编号:4704813
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:34
- 大小:219.12KB
数据结构习题Word文件下载.docx
《数据结构习题Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构习题Word文件下载.docx(34页珍藏版)》请在冰点文库上搜索。
for(j=i+1;
j<
n;
j++)
if(b[k]>
b[j])k=j;
x=b[i];
b[i]=b[k];
b[k]=x;
}
3、voidfun3(intn)
inti=0,s=0;
while(s<
{i++;
s=s+i;
4、voidfun4(intn)
inti=1;
=n)
i=i*3;
五、假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文。
试写一个算法判别读入的一个以@为结束符的字符序列是否是“回文”,并分析时间复杂度。
第二章
1、一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。
(A)110(B)108(C)100(D)120
2、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素。
(A)64(B)63(C)63.5 (D)7
3、线性表采用链式存储结构时,其地址()。
(A)必须是连续的(B)部分地址必须是连续的
(C)一定是不连续的(D)连续与否均可以
4、在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行()。
(A)s->
next=p;
p->
next=s;
(B)s->
next=p->
next;
(C)s->
p=s;
(D)p->
s->
5、在一个单链表中,若删除p所指结点的后续结点,则执行()
(A)p->
next->
(B)p=p->
p->
(C)p->
(D)p=p->
6、已知L是无表头结点的单链表,且P结点既不是首结点,也不是尾结点,试从下列提供的答案中选择合适的语句序列。
a.在P结点之后插入S结点的语句序列是()。
b.在P结点之前插入S结点的语句序列是()。
c.在表首插入S结点的语句序列是()。
d.在表尾插入S结点的语句序列是()。
(1)p->
(2)p->
(3)p->
next=s->
(4)s->
(5)s->
next=L;
(6)s->
next=NULL;
(7)Q=p;
(8)while(p->
next!
=Q)p=p->
(9)while(p->
=NULL)p=p->
(10)p=Q;
(11)p=L;
(12)L=S;
(13)L=p;
7、已知L是表头结点的非空单链表,且P结点既不是首元结点,也不是尾结点,试从下列提供的答案中选择合适的语句序列。
a.删除P结点的直接后继结点的语句序列是()。
b.删除P结点的直接前驱结点的语句序列是()。
c.删除P结点的语句序列是()。
d.删除首元结点的语句序列是()。
e.删除表尾结点的语句序列是()。
(1)p=p->
(2)p->
(4)p=p->
(5)while(p!
(6)while(Q->
=NULL){p=Q;
Q=Q->
(7)while(p->
(8)while(p->
(10)Q=p;
(11)Q=p->
(12)p=L;
(13)L=L->
(14)free(Q);
8、在一个长度为n的顺序表中向第i个元素(0<
i≤n+1)之前插入一个新元素时,需要向后移动()个元素。
A.n-iB.n-i+1C.n-i-1D.i
9、线性表是()。
(A)一个有限序列,可以为空(B)一个有限序列,不可以为空
(C)一个无限序列,可以为空(D)一个无限序列,不可以为空
10、链表不具有的特点是()。
(A)可随机访问任一元素(B)插入删除不需要移动元素
(C)不必事先估计存储空间(D)所需空间与线性表长度成正比
11、线性表采用链式存储结构时,其地址()。
(A)必须是连续的(B)一定是不连续的
(C)部分地址必须是连续的(D)连续与否均可以
12、在线性表的下列存储结构中,读取元素花费时间最少的是()。
(A)单链表(B)双链表(C)循环链表(D)顺序表
13、若线性表最常用的运算是存取第i个元素及其前驱的值,则采用()存储方式节省时间。
14、在不带头结点(头指针为*head)的单循环链表中,至少有一个结点的条件是(),尾结点*p的条件是()。
(A)head!
=NULL(B)head->
=NULL(C)p==NULL(D)p->
next==head
15、在带头结点(头结点*head)的单循环链表中,至少有一个结点,头结点*head的条件是(),尾结点*p的条件是()。
(A)head!
=NULL(C)p==NULL(D)p->
二、填空
1、在有n个元素的顺序表中,删除任意一个元素所需移动结点的平均次数为();
任意位置插入一个元素所需移动结点的平均次数为();
三、简述下列算法的功能。
StatusA(ListedListL){//L是无表头结点的单链表
if(L&
&
L->
next){
Q=L;
L=L->
P=L;
while(p->
next)p=p->
next=Q;
Q->
ReturnOK;
四、编写算法
1、假设元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同),现要求另辟空间构成一个线性表C,其元素为A和B中元素的交集,且表C中的元素也依值递增有序排列。
试对单链表编写求C的算法。
2、试以循环链表作多项式的存储结构,编写求其导数的算法,要求利用原多项式中的结点空间存放其导函数(多项式),同时释放所有无用(被删)结点。
第三章
1、若入栈序列是a,b,c,d,e,则不可能的出栈序列是()。
(A)edcba(B)decba(C)dceab(D)abcde
2、判定一个栈ST(最多元素为m0)为空的条件是()。
(A)ST.top!
=0(B)ST.top==0
(C)ST.top!
=m0(D)ST.top==m0
3、判定一个栈ST(最多元素为m0)为满的条件是()。
(A)ST.top!
=0(B)ST.top==0
(C)ST.top!
=m0(D)ST.top==m0
4、循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是()。
(A)(rear-front+m)%m(B)rear-front+1
(C)rear-front-1(D)rear-front
5、以数组Q[0…m-1]存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是()。
(A)rear-qulen (B)rear-qulen+m
(C)m-qulen (D)(rear+m-qulen)%m
6、若队列的入队序列是1,2,3,4,则出队序列是()。
(A)4,3,2,1(B)1,2,3,4(C)1,4,3,2(D)3,2,4,1
7、栈和队列的共同特点是()。
(A)都是先进后出(B)都是先进先出
(C)只允许在端点处插入和删除元素(D)没有共同点
8、元素A,B,C,D依次入栈,栈顶元素是(),栈底元素是()。
(A)A(B)B(C)C(D)D
9、经过以下运算:
InitStack(S);
Push(S,a);
Push(S,b);
Pop(S,x);
GetTop(S,x)后,x的值是()。
(A)a(B)b(C)1(D)0
10、设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是()。
(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C
11、已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若pn=n,则pi的值是()。
(A)i(B)n-i(C)n-i+1(D)不确定
12、已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值是()。
(A)可能是2(B)一定是2(C)可能是1(D)一定是1
13、经过以下队列运算:
InitQueue(qu);
enQueue(qu,a);
enQueue(qu,b);
enQueue(qu,c);
deQueue(qu)后,队头的值是()。
14、判定一个循环队列Q(存放元素位置0~QueueSize)队列满的条件是()。
(A)Q.front==Q.rear(B)Q.front+1==Q.rear
(C)Q.front==(Q.rear+1)%QueueSize(D)Q.rear==(Q.front+1)%QueueSize
1、栈的特点是(),队列的特点是()。
2、线性表、栈和队列都是()结构,可以在线性表的()位置插入和删除元素,栈只能在()插入和删除元素,队列只能在()插入元素和()删除元素。
3、设栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过一个栈,一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1则栈S至少应该容纳()个元素。
三、算法设计
1、假设以I和O分别表示入栈和出栈操作,栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列。
(1)下面所标示的序列哪些是合法的?
(A)IOIIOIOO(B)IOOIOIIO(C)IIIOIOIIO(D)IIIOOIOO
(2)通过对
(1)的分析,编写一个算法,判定所给的操作序列是否合法。
若合法返回1;
否则返回0(假设被判定的操作序列已存入一维数组中)。
2、假设从键盘上输入一整数序列a1,a2,…,an,编程实现:
当ai>
0时,ai进队;
当当ai<
0时,队首元素出队;
当ai=0时,表示输入结束。
要求队列处理成循环队列,如对何处对单独编写算法,并在异常情况下(如队满)打印出错。
第四章
一、已知:
a=‘THIS’,f=‘ASAMPLE’,c=‘GOOD’,d=‘NE’,b=‘’
s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2))))
t=Replace(f,SubString(f,3,6),c)
u=Concat(SubString(c,3,1),d)
g=‘IS’
v=Concat(s,Concat(b,Concat(t,Conct(b,u))))
试求:
s,t,v,StrLength(s),Index(v,g),Index(u,g)各是多少?
二、试问执行以下函数会产生怎样的输出结果?
voiddemonstrate()
{
StrAssign(s,‘THISISABOOK’);
Replace(s,SubString(s,3,7),‘ESEARE’);
StrAssign(t,Concat(s,‘S’));
StrAssign(u,‘XYXYXYXYXYXY’);
StrAssign(v,SubString(u,6,3));
StrAssign(w,‘W’);
Printf(“t=%s,v=%s,u=%s”,t,v,Replace(u,v,w));
三、设主串为s=’abcaabbabcabaacbacba’,模式串为p=’abcabaa’。
1、计算模式串p的next函数值和他的修正值nextval。
2、画出利用next函数进行模式匹配时每趟的匹配过程。
第五章
一、选择题
1、对矩阵压缩存储是为了()。
(A)方便运算(B)节省空间(C)方便存储(D)提高运算速度
2、与三元组顺序表相比,稀疏矩阵用十字链表表示,其优点在于()。
(A)便于实现增加或减少矩阵中非零元素的操作
(B)便于实现增加或减少矩阵元素的操作
(C)可以节省存储空间
(D)可以更快地查找某个非零元素
3、对稀疏矩阵采用压缩存储,其缺点之一是()。
(A)无法判定矩阵有多少行多少列
(B)无法根据行列号查找某个矩阵元素
(C)无法根据行列号计算矩阵元素的存储地址
(D)使矩阵元素之间的逻辑关系更加复杂
二、填空题
1、数组A[0..5,0..6]的每个元素占5个存储单元,将其按列为主序存储在起始位置为1000的连续内存单元中,则元素A[5][5]的地址为()。
2、一个n×
n的对称矩阵,如果以行或列为主序存入内存,则容量为()。
3、数组A[1..10,-2..6,2..8]的每个元素占3个存储单元,将其按行为主序存储在起始位置为100的连续内存单元中,则元素A[5][0][7]的地址为()。
4、三位数组R[c1..d1,c2..d2,c3..d3]共含有()个元素。
三、设有三对角矩阵An×
n(从A1,1开始),将其三对角线上元素逐行存储于数组B[1…m]中,使B[k]=Ai,j,求:
1、用i,j表示k的下表变换公式;
2、用k表示i,j的下表变换公式。
四、求下列广义表操作的结果:
(1)GetHead(((a,b),(c,d)))
(2)GetHead(GetTail(((a,b),(c,d))))
(3)GetHead(GetTail(GetHead(((a,b),(c,d))))
(4)GetTail(GetHead(GetTail(((a,b),(c,d))))
五、编写一个算法,计算一个三元组表表示的稀疏矩阵的对角线元素之和。
第六章
1、二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法()。
(A)正确(B)错误
2、由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法()。
3、已知某二叉树的后序遍历序列是dabec。
中序遍历序列是debac,它的前序遍历序列是()。
(A)acbed(B)decab(C)deabc(D)cedba
4、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是()。
(A)bdgcefha(B)gdbecfha(C)bdgaechf(D)gdbehfca
5、在一非空二叉树的中序遍历序列中,根结点的右边()。
(A)只有右子树上的所有结点(B)只有右子树上的部分结点
(C)只有左子树上的部分结点(D)只有左子树上的所有结点
6、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序()。
(A)不发生改变(B)发生改变(C)不能确定(D)以上都不对
7、在线索化二叉树中,t所指结点没有左子树的充要条件是()。
(A)t->
lchild=NULL(B)t->
ltag=1
(C)t->
ltag=1且t->
lchild=NULL(D)以上都不对
8、二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法()。
(A)正确(B)错误
9、设T是一棵完全二叉树,则T的根结点的左子树的结点数n′与右子树的结点数n″相比有()。
(A)n′≥n″(B)n′=n″(C)n′<n″(D)n′≠n″
10、设有n个结点的完全二叉树,顺序存放在数组S[1..n]中,对任一结点S[i]而言,若右孩子存在,则为()。
(A)S[2i](B)S[2i+1](C)S[2i-1](D)都不对
11、对于前序遍历和后序遍历结果相同的二叉树为()。
(A)一般二叉树 (B)只有根结点的二叉树
(C)根结点无左孩子的二叉树 (D)根结点无右孩子的二叉树
12、对于前序遍历与中序遍历结果相同的非空二叉树为()。
(A)根结点无左孩子的二叉树(B)根结点无右孩子的二叉树
(C)所有结点只有左子树的二叉树(D)所有结点只有右子树的二叉树
13、不含任何结点的空树()。
(A)是一棵树(B)是一棵二叉树
(C)是一棵树也是一棵二叉树(D)既不是树也不是二叉树
14、二叉树是非线性数据结构,所以()。
(A)它不能用顺序存储结构存储(B)它不能用链式存储结构存储;
(C)顺序存储结构和链式存储结构都能存储(D)顺序存储结构和链式存储结构都不能使用
15、具有n(n>
0)个结点的完全二叉树的深度为()。
(A)log2n(B)log2n(C)log2n+1(D)log2n+1
16、把一棵树转换为二叉树后,这棵二叉树的形态是()。
(A)唯一的(B)有多种
(C)有多种,但根结点都没有左孩子(D)有多种,但根结点都没有右孩子
17、树是结点的有限集合,它(A)根结点,记为T。
其余的结点分成为m(m≥0)个(B)的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。
一个结点的子结点个数为该结点的(C)。
供选择的答案
A:
①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上
B:
①互不相交②允许相交③允许叶结点相交④允许树枝结点相交
C:
①权②维数③度④序
18、在完全的二叉树中,若一个结点没有(A),则它必定是叶结点。
每棵树都能惟一地转换成与它对应的二叉树。
由树转换成的二叉树里,一个结点N的左孩子是N在原树里对应结点的(B),而N的右子女是它在原树里对应结点的(C)。
A:
①左结点②右结点③左结点或者没有右结点④兄弟
B~C:
①最左结点②最右结点③最邻近的右兄弟④最邻近的左兄弟
⑤最左的兄弟⑥最右的兄弟
19、设T是具有3个结点的二叉树,且T的后序序列与中序序列相同,则T的形态为()。
(A)(B)(C)(D)
1、一棵深度为6的满二叉树有()个叶子和()个分支结点。
2、设一棵完全二叉树有700个结点,则共有()个叶子结点。
3、设一棵完全二叉树具有36个结点,则此完全二叉树有()个叶子结点,有()个度为2的结点,有()个结点只有非空左子树,有()个结点只有非空右子树。
4、一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足关系()。
5、一棵哈夫曼树有19个结点,则其叶子结点的个数是()。
三、判断
1、在任何非空二叉树中,叶子结点数等于度为2的结点数+1,即n0=n2+1。
()
2、在线索二叉树中,根据线索可以找到树中任何一个结点在相应遍历序列中的直接前驱。
3、在非空完全二叉树中,若一个结点不存在左孩子,则该结点一定是叶子结点。
4、在非空完全二叉树中,若一个结点不存在右孩子,则该结点一定是叶子结点。
5、在一棵完全二叉树中,对任一结点而言,若其左孩子不存在,则右孩子一定不存在。
四、简答题
1、对所示二叉树进行后序线索化。
2、试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
3、给定某二叉树的中序序列为BRXSACUYV,后序序列为BRSXCUVYA,试画出该二叉树的结构图。
4、将下列二叉链表改为先序线索链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
A
B
C
D
E
F
G
H
I
J
K
L
M
N
Ltag
Lchild
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题