数据结构试题及答案修改一Word下载.docx
- 文档编号:5650658
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:20
- 大小:28.34KB
数据结构试题及答案修改一Word下载.docx
《数据结构试题及答案修改一Word下载.docx》由会员分享,可在线阅读,更多相关《数据结构试题及答案修改一Word下载.docx(20页珍藏版)》请在冰点文库上搜索。
已知图的顶点集V的每个边集G如下:
V={0,1,2,3,4,5,6,7,8,9};
e={(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,9),(6,7),
(7,8),(8,9)}
7
当它由邻接矩阵和邻接表表示时,顶点序列通过深度优先搜索从顶点V0遍历获得,顶点序列通过宽度获得是分别写的
假设每个顶点邻接表中的节点按顶点数的降序链接
邻接矩阵代表
邻接表代表深度优先序列广度优先序列时间图4,阅读算法,回答问题(每项8分,共16分)
1,假设从键盘输入一批整数,顺序为:
786345309134–1,请写出输出结果
#include#include
consstintstackmassize=30;
typedefint元素类型;
结构堆栈{
元素类型堆栈[堆栈大小];
inttop;
};
#包括”stack.h“Voidmain()
{stacka;
initstack(a);
intx;
CIN>
>
x;
同时(x!
=-1){推(a,x);
}
while(!
stackmpty(a))coutlchild)
(一)冒泡排序
(B)快速排序
(C)堆排序
(D)丘排序
18
2。
如果线性表中有n个数据元素,那么在顺序存储结构上实现顺序搜索的平均时间复杂度为___________,在链式存储结构上实现顺序搜索的平均时间复杂度为____________3.
设置一个具有n个节点的二叉树,那么当二进制链表作为其存储结构时,二进制链表总共有________个指针字段和________个空指针字段4.
设置指针变量p指向单链表中的节点a,指针变量s指向插入的节点b,则在节点a后插入节点b的操作顺序为_________________________________________________5.
集合无向图g有n个顶点和e条边,其对应的邻接表有________个头节点和________个表节点6.7.8.
集合无向图g有n个顶点和e条边。
如果所有顶点的度数之和是m,那么e和m有一个______关系
设置一棵二叉树,它的前序遍历序列和中序遍历序列是ABC,那么二叉树的后序遍历序列是__________假设在一个完整的二叉树中有21个节点。
如果从上到下从左到右的数字是1,那么编号为8的父节点的数字是______________,编号为8的左子节点的数字是_______________9.以下程序段
的功能实现了主串S中子串T位置的算法,要求在下划线处填入正确的语句。
国际指数(查尔[),查尔[]){
1=j=0;
while(inext=p->
next;
s->
next=sn,2em=2eCBA4,16i-j+1,0
C7。
C
3。
D8。
B
C9。
A10。
10。
n-1
h0
h1?
?
83.申请问题
h21。
链存储结构稍微有点,序言ABDEC、中间序言DBEAC和后记DEBCA。
h3?
102.霍夫曼树略,WPL=78h4?
25?
32h5?
68012419,518,63。
(18,5,16,19,21,23),(5,163,21,23)74。
线性检测:
8?
1025322768链地址方法:
h6?
27
深度:
125364,宽度:
123456,最小生成树的边集T为E={(1,4),(1,3),(3,5),(5,6),(5,6)}4。
算法设计问题1。
设计判断单个链表中的节点是否关于中心对称类型定义结构{国际标准[100];
inttop}sqstack。
intlklistsymmetry(lklist*head){
sqstack;
top=-1;
lklist*p;
为(p=水头;
p!
=0。
p=p->
next){stack.top++;
[栈顶]=p->
数据;
为(p=headp!
p=p->
next)if(p->
data==stack.s[stack.top])stack.top=stack.top-1;
否则返回(0);
返回
(1);
}2。
设计了一个算法,在链存储结构上建立一个二叉树typedefchar数据类型;
typedef结构节点{datatypedata结构节点*lchild,*rchild}bitreevoidcreatebitree(bitree*scanf(\if(ch==‘#‘){Bt=0;
返回;
Bt=(bitree*)malloc(sizeof(bitree));
bt->
数据=chcreatebitree(Bt->
lchild);
createbitree(Bt->
archild);
}3。
设计了一种算法来判断二叉树是否是二叉排序树intminnum=-32768,flag=1;
typedef结构节点{int键;
结构节点*lchild,*rchild}bitreevoidinorder(bitree*Bt){
if(Bt!
=0)
{inorder(Bt->
if(minnum>
key)标志=0;
minnum=Bt->
key;
排序(Bt->
rchild);
(5)
数据结构试卷(5)
1,选择题(24分)
1。
以下关于线性表的陈述是错误的()
(A)线性表使用顺序存储,这必须占用连续存储空间(b)线性表使用链式存储,这不需要占用连续存储空间(c)线性表使用链式存储,这便于插入和删除操作(d)线性表使用顺序存储,这便于插入和删除操作(
2)。
假设霍夫曼树中的叶节点总数为m,如果使用二进制链表作为存储结构,则霍夫曼树中有()个空指针
个指针字段(a)2m-1(b)2m(c)2m+1(d)4m
3。
假设顺序循环队列q[0:
m-1]的头指针和尾指针分别是f和r,头指针f总是指向团队头元素的前一个位置,而
尾指针r总是指向团队尾元素的当前位置,那么循环队列中元素的数量是()(a)r-f(b)f-r(c)(r-f+m)%m(d)(f-r+m)%M4。
假设二叉树的中间顺序遍历序列是ABCD,前顺序遍历序列是CABD,那么遍历二叉树得到的序列是()(a)badc(b)bcda(c)cdab(d)cbda5。
如果在完全无向图中有n个顶点,那么在完全无向图中有()条边(a)N2(d)N2-16。
如果二叉树中有2000个节点,二叉树的最小高度是()(a)9(b)10(c)11(d)12
7。
如果有向图中有n个顶点,那么在对应于有向图的邻接表中有()个头节点(a)n-1(b)n(c)n+1(d)2n-1
8。
设置一组初始记录键序列(5,2,6,3,8),并使用第一个记录键5作为快速排序结果
as()的基础
(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8
2,填写问题(24分)
为了有效地应用HASH搜索技术,必须解决的两个问题是___________________和
_________________________
下面程序段的功能实现了数据X堆栈,要求在下划线处填写正确的语句
typedef结构{国际标准[100];
voidpush(sqstack
else{_______________________;
______________;
通过遍历
21
3.4.5.6.7.
序列中的二进制排序树获得的序列是________(有序或无序的)快速排序的最差时间复杂度是________,平均时间复杂度是_________
如果二叉树中度为0的节点数为N0,度为1的节点数为N1,则二叉树中度为2的节点数为______;
如果采用二进制链表作为二叉树的存储结构,则二叉树总共有______个空指针字段如果无向图中的顶点数和边数分别为n和e,并且所有顶点的度数之和为d,则e=_____
将一组初始记录密钥序列设置为(55,63,44,38,75,80,31,56),那么通过筛选方法建立的初始堆为_________________________________
8。
v1?
3?
2?
4v2?
1?
3v3?
4?
2让无向图G的邻接表是v4?
3、从顶点V1开始的深度优先遍历序列是
_________;
广度优先遍历序列是___________
3,申请问题(36分)
如果一组初始记录关键字序列是(45,80,48,40,22,78),则分别给出第四简单选择排序和第四
直接插入排序的结果
将指针变量P设置为指向双链表中的节点A,将指针变量Q设置为指向插入的节点B,需要给出在节点A后插入
节点B的操作顺序(将双链表中节点的两个指针字段分别设置为llink和rlink)
将记录关键字的有序序列设置为(13,18,24,35,47,50,62,83,90)。
搜索方法使用二进制搜索。
当搜索关键字62时,需要
来计算比较次数,当搜索成功时,需要计算平均搜索长度。
4.将树T中的边集设置为{(A,b),(A,C),(A,d),(b,e),(C,f),
(C,G)}。
需要用子兄弟表示(二进制链表)来表示树的存储结构,并将树转换成相应的二叉树。
5.有一个无向图G(如右图所示),在用prim算法构造最小生成树时,它需要
遍历的一组边。
有一组初始记录关键字(45,80,48,40,22,78),它需要构建一个
的分叉分类树,并给出构建过程
算法设计问题(16分)
1。
有一组初始记录密钥序列(K1,K2,...,Kn)。
需要设计一种算法,能够在时间复杂度为0(n)的范围内将线性表分成两部分,其中左半部分的每个键小于Ki,右半部分的每个键大于或等于Ki
有两个集合A和B,它们需要设计算法来生成集合C=A∪B,其中集合A、B和C由链存储结构
表示
数据结构试卷(5)参考答案
1,选择题1.D2.B3.C4.a5.a6.C7.b8.c
2,填空题
构造一个好的HASH函数。
确定冲突解决方法2。
stack.top++,stack.s[stack.top]=x3.ordered
4。
O(n2),O(nlog2n)5。
N0-1,2N0+N16。
d/2
7。
(31,38,54,56,75,80,55,63)8.(1,3,4,2),(1,3,2,4)
3,申请问题
(22,40,45,48,80,78),(40,45,48,80,22,78)2.q->
llink=p;
q->
rlink=p->
rlink;
p->
rlink->
llink=q;
rlink=q;
3.2,ASL=91*1+2*2+3*4+4*2)=25/94。
树的链式存储结构略,二叉树略
5.e={(1,3),(1,2),(3,5),(5,6),(6,4)6。
略
算法设计问题
22
有一组初始记录密钥序列(K1,K2,...,Kn)。
需要设计一种算法,该算法能够在时间复杂度为0(n)的范围内将线性表分成两部分,其中左半部分中的每个键小于Ki,右半部分中的每个键大于或等于Kivoidquickpass(intr[),ints,intt){
inti=s,j=t,x=r[s];
而(idata=p->
t->
next=HC;
hc=t。
}}}
数据结构试卷(6)
1,选择题(30分)
假设数据结构的二进制形式表示为A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},
r={,,,,},那么数据结构A是()(a)线性结构(b)树形结构(c)物理结构(d)模式结构2。
下面程序的时间复杂度是()
for(i=1,s=0;
idata=q->
next=q->
自由(q);
(二)q=p->
下一个;
数据=p->
(三)q=p->
(四)q=p->
数据=q->
对于要排序的n个记录关键字,()在堆排序中需要辅助记录单元(a)1(b)n(c)nlog2n(d)n2
如果一组初始密钥记录密钥是(20,15,14,18,21,36,40,10),则基于20的快速
序列的结果是()
(A)10、15、14、18、20、36、40、21(B)10、15、14、18、20、40、36、21(C)10、15、14、20、18、40、36、2l(D)15、10、14、18、20、36、40、21
6。
如果二进制排序树中有n个节点,则二进制排序树中的平均搜索长度为()
2
(a)o
(1)(b)o(log2n)(c)(d)o(n)
如果无向图g中有n个顶点和e条边,则其对应的邻接表中头节点和表节点的数量为()(A)n,e(B)e,n(C)2n,e(D)n,2e8。
如果强连通图中有n个顶点,那么强连通图中至少有()条边(a)n(n-1)(b)n+1(c)n(d)n(n+1)
9。
有5000个记录关键字需要排序。
如果需要用最快的方法选择最短的10个记录关键字,下面的
()方法可以达到这个目的(a)快速排序(b)堆排序(c)合并排序(d)插入排序10。
在以下四种类型中(),空间复杂度最大(a)插入排序(b)冒泡排序(c)堆排序(d)合并排序
2,填入空格(48分,其中最后两项各为6分)
数据的物理结构主要包括_________和_________两种情况
如果在一个完整的二叉树中有500个节点,那么二叉树的深度是______;
如果使用二进制链表作为完整的二进制
树的存储结构,则总共有____________个空指针字段
23
4.
将输入序列设置为1、2、3,那么在堆栈动作后可以获得不同的输出序列
具有邻接矩阵A[n][n]作为图g的存储结构,那么邻接矩阵中第一行的所有元素的和等于顶点1的_______并且第一列的所有元素的和等于顶点1的_______
如果霍夫曼树中有n个节点,那么霍夫曼树有1度的________个节点
有向图g中有n个顶点和e条有向边,如果所有顶点度数之和是d,那么e和d之间的关系是_______7.________遍历二进制排序树中的节点,以获得递增的密钥序列(填写第一顺序、中间顺序或第二顺序)
假设查找表中有100个元素。
如果通过二分法搜索方法找到数据元素x,则可以通过比较多达______次来确定数据元素x是否在查找表中。
无论是顺序存储结构的堆栈还是链式存储结构的堆栈,堆栈进入和堆栈退出操作的时间复杂度都是
___________
有n个节点的完全二叉树。
如果从上到下,从左到右从1开始编号,则I节点的双
父节点的编号为_____________,右子节点的编号为_____________
将一组初始记录关键字设置为(72,73,71,23,94,16,5),然后基于记录关键字72进行快速排序
将产生___________________________
如果有向图g中有一组E={,,,},则该图的拓扑顺序
被列为_____________________
13。
以下算法在顺序哈希表中查找值为X的关键字。
请在下划线处填写正确的陈述。
struct记录{int键;
其他;
inthashsqsearch(structrecordhashtable[),intk){
inti,j;
j=I=k%p;
while(哈希表[j)。
钥匙。
=k如果(i==j)返回(-1);
}如果(____________________)返回(j);
否则返回(-1);
14。
下面的算法在二进制排序树中找到键值K。
结构节点*lchild。
结构节点*rchild}bitreebitree*b搜索(bitree*t,intk){
if(t==0)返回(0);
elsewhile(t!
if(t->
key==k)___________;
否则,如果(t->
键>
k)t=t->
lchild;
否则_______________;
3,算法设计问题(22分)
设计一种算法,删除单个链表中具有相同值的冗余节点2.设计一种在二叉树中寻找节点X的父节点算法
数据结构试卷(6)参考答案
1,选择题
1.B2.B3.a4.a5.a6.B7.D8.c9.b10.d
第3项:
首先将指针变量q指向节点a的后继节点b,然后将节点b的值复制到节点a,最后删除节点b。
第9项分析:
9快速排序、合并排序和插入排序必须等到整个排序完成后才能找到最少10个,而堆排序只需要在初始堆的基础上再进行10次筛选,每次筛选的时间复杂度为O(log2n)
2,填写问题
顺序存储结构,链式存储结构。
95013。
5
外向度,5度。
06.e=d7。
中间顺序8。
79.O
(1)10.i/2,2i+1
(5,16,71,23,72,94,73)12.(1,4,3,2)
j+1,哈希表[[j]。
key==k14。
return(t),t=t->
archild
24
第8项分析:
二进制搜索的过程可以用一棵二叉树来描述,称为二进制决策树当在有序表上执行二进制搜索时,搜索长度不超过二进制决策树的高度1+log2n
3,算法设计问题
设计一种算法,删除单个链表中具有相同值的冗余节点
typedefint数据类型;
typedef结构节点{datatypedata结构节点*下一步;
}lklist。
voiddelredundant(lklist*
for(p=head;
next){
for(q=p->
next,s=q;
q!
)
if(q->
data==p->
data){s->
q=s->
}否则{s=q,q=q->
设计一种在二叉树中寻找节点X的父节点的算法
typedef结构节点{datatypedata结构节点*lchild,*rchild}bit
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试题 答案 修改