数据结构与算法作业文档格式.docx
- 文档编号:3925653
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:24
- 大小:254.34KB
数据结构与算法作业文档格式.docx
《数据结构与算法作业文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构与算法作业文档格式.docx(24页珍藏版)》请在冰点文库上搜索。
【10,1,4】设n为正整数,试确定下列各程序段中前置以记号@的语句的频度:
(1)i=1;
k=0;
while(i<
=n-1){
i++;
@k+=10*i;
//语句的频度是______________________。
(2)k=0;
for(i=1;
i<
=n;
i++){
for(j=i;
j++)
@k++;
【11,1,4】按增长率由大到小排列下列函数的结果是________________________________。
log2(log2n),nlog2n,n2,n1/2,log2n,n
【12,2,1】当线性表的规模比较大,难以估计其存储规模时,一般以采用文件的存储结构为好。
【13,2,1】线性表(a1,a2,…,an)有两种存储结构:
顺序存储结构和链式存储结构,请就这两种存储结构完成下列填充:
__顺序存储_存储密度较大;
__链式存储__存储利用率较高;
__链式存储__可以随机存取;
__顺序存储___不可以随机存取;
__链式存储__插入和删除操作比较方便。
【14,2,2】从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动n-i个元素。
【15,2,3】带头结点的双链表L为空的条件是L->
next=L。
【16,2,3】带头结点的单链表Head为空的条件是____head→next==NULL______。
【17,2,3】非空单循环链表L中*p是尾结点的条件是____P!
=NULL__________。
【18,2,3】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点,应执行s->
next=__p->
next___;
和p->
next=___S____的操作。
【19,2,3】在一个单链表中的指针p所指结点之前插入一个由指针s所指结点,可执行以下操作序列:
s->
next=p->
next____;
p->
next=s;
t=p->
data;
data=___s->
data_____;
data=t;
【20,2,3】在一个单链表中删除p所指结点时,应执行以下操作:
q=p->
next;
p->
data=p->
next->
next=q->
next_;
free(q);
【21,2,3】在单链表中,删除指针P所指结点的后继结点的语句是p->
next;
next=p->
next->
__。
【22,2,3】带头结点的单循环链表Head的判空条件是__Head->
Null___;
不带头结点的单循环链表的判空条件是___②__。
【23,2,3】删除带头结点的单循环链表Head的第一个结点的操作是__①___;
删除不带头结点的单循环链表的第一个结点的操作是__②___。
【24,2,3】已知L是带表头结点的非空单链表,且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.删除P结点的直接前驱结点的语句序列是________________________________。
b.删除结点P的语句序列是________________________________。
c.删除尾元结点的语句序列是________________________________。
(1)P=P->
(2)P->
next=P;
(3)P->
next=P->
next->
(4)P=P->
(5)while(P!
=NULL)P=P->
(6)while(Q->
next!
=NULL){P=Q;
Q=Q->
next};
(7)while(P->
=Q)P=P->
(8)while(P->
(9)while(P->
(10)Q=P;
(11)Q=P->
(12)P=L;
(13)L=L->
(14)free(Q);
【25,3,1】栈操作的原则是先进后出。
【26,3,1】对一个栈,给定输入的顺序是A、B、C,则全部不可能的输出序列有①。
【27,3,1】数据A、B、C、D依次进栈后,再从栈中取一数据,则它是D。
则本栈得到DCBA的输出序列,其理由是先进后出,进入的顺序是ABCD则出来的顺序为DCBA。
【28,3,1】.在栈顶指针为HS的链栈中,判定栈空的条件是 。
【29,3,1】将递归算法改写成等价的非递归算法,通常应该设置①的数据结构
【30,3,2】下列程序把十进制数转换为十六进制数,请填写合适的语句成分。
(每空2分)
voidconversion10_16()
{InitStack(&
s);
scanf(“%d”,&
N);
while(N){
1_____________________;
N=N/16;
while(!
StackEmpty(s)){
2_____________________;
if(e<
=9)printf(“%d”,e);
elseprintf(“%c”,e-10+’A’);
}/*conversion*/
【31,3,4】若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素为n,则第i个输出元素是n-i+1。
【32,3,4】若用一个大小为6个元素的数组来实现循环队列,且当前rear=0和front=3。
当从队列中删除一个元素,再加入两个元素后,rear和front的值分别是①和②。
【33,3,4】已知一个栈的输入序列为1,2,3,…,n,输出序列为a1,a2,a3,…,an,那么a2=n的输出序列共有0种。
【34,3,4】堆栈和队列都是线性表,堆栈是____一种先进后出的线性表____的线性表,而队列是__是一种先进先出的_____________的线性表。
【35,3,4】从循环队列中删除一个元素时,其操作是 。
【36,3,4】若用一个大小为6个元素的数组来实现循环队列,且当前rear=0和front=3。
当从队列中删除一个元素,再加入两个元素后,rear和front的值分别是和。
【37,3,4】下面是关于循环队列的操作,请在划线空白处填写合适语句成分。
StatusEnQueue(SqQueue&
Q,QelemTypee)
if((Q.rear=1)%MAXSIZE==q.fromt
)retrunERROR;
Q.base[(Q.rear+1)%MAXSIZE]=e;
Q.rear=(Q.rear+1)%MAXSIZE
;
returnOK;
}//EnQueue
【52,6,1】
已知一棵树边的集合是{<
a,d>
<
d,c>
d,j>
e,a>
f,g>
d,b>
g,h>
g,i>
e,f>
}。
那么根结点是①,结点b的双亲是②,结点a的子孙有③,树的深度是④,树的度是⑤,结点g在树的第⑥层。
【53,6,2】通常使用 来表示二叉树结构。
【54,6,2】从概念上讲,树与二叉树是二种不同的数据结构,将树转化为二叉树的基本的目的是 。
【55,6,2】在图1至图5中,__2、3、4、5______是树,___2、3、4__________是二叉树,____2、3__________是完全二叉树,_______3__________是满二叉树。
图1图2图3图4图5
【56,6,3】在图4中,结点H在这棵树的前序、中序和后序遍历次序中分别是_____、第__5___和第______个结点。
【57,6,2】满三叉树的第i层的结点个数为①,深度为h时该树中共有②结点。
【58,6,2】在图4中,A是______结点,D是______结点,B是E的________,B是G的________,D是E的________。
这棵树的度是________,深度是________。
【59,6,2】程序填空:
下列算法是求以二叉链表存储的二叉树中的最小值,设数据域的类型为int。
voidminnode(BiTreeT,int*min)
{
if(T!
=NULL)
{
if(①)*min=T->
minnode(T->
lchild,min);
②;
【60,6,2】已知一棵完全二叉树有56个叶子结点,从上到下、从左到右对它的结点进行编号,根结点为1号。
则该完全二叉树总共结点有________个;
有_______层;
第91号结点的双亲结点是_______号;
第63号结点的左孩子结点是_________号。
【61,6,2】下列表示的图中,共有___5____个是树;
有___3____个是二叉树;
有___2____个是完全二叉树。
【62,6,3】下列二叉树的中序遍历序列是_DBNGOAEC__;
后序遍历序列是______________________________________。
【63,6,3】一棵二叉树的中序遍历序列是DBNGOAEC,后序遍历序列是DNOGBECA,则其先序遍历的序列中的第一个元素是____,第五个元素是__,最后一个元素是__
【64,6,3】下列二叉树的先序遍历序列的第5个结点是______;
第8个结点是_____;
后序遍历序列的第2个结点是_____;
第6个结点是_____。
(每空2分)
【65,6,3】如果某二叉树的后序遍历序列是ABCDEFGHI,中序遍历序列是ACBIDFEHG,则其先序遍历序列的第一个字母是①,最后一个字母是②。
【66,6,3】程序填空:
设算法DFS(Mgraph*G,inti)是无向图G从i顶点开始的深度优先遍历算法。
下列算法是判断无向图G是否是连通的。
intisconnect(Mgraph*G)
{inti,k=0;
for(i=0;
G->
vexnum;
i++)
visited[i]=0;
if(!
visited[i])
{①;
DFS(G,i);
if(k==1)②;
elsereturn0;
【67,7,2】图有①和②等存储结构。
【68,7,2】设无权图G的邻接矩阵为A,若(vi,vj)属于图G的边集合,则对应元素A[i][j]等于①,22、设无向图G的邻接矩阵为A,若A[i][j]等于0,则A[j][i]等于①。
【69,7,2】若一个图用邻接矩阵表示,则计算第i个结点的入度的方法是①。
【70,7,2】若一个图用邻接矩阵表示,则删除从第i个顶点出发的所有边的方法是①。
【71,7,4】n个顶点的连通图至少有①条边。
【72,7,4】设一个图
G={V,{A}},V={a,b,c,d,e,f},A={<
a,b>
b,e>
a,e>
c,a>
e,d>
d,f>
f,c>
那么顶点e的入度是①;
出度是②;
通过顶点f的简单回路有③条;
就连通性而言,该图是④图;
它的强连通分量有⑤个;
其生成树可能的最大深度是⑥ 。
【73,7,5】下面有向图共有_______个顶点;
从v3到v2的最短简单路径之一是_________________;
v1的出度是________;
包含所有顶点的简单路径之一是_____________________。
【74,9,2】n个结点的二叉排序树的最大深度是①,最小深度为②
【75,9,3】设HASH表的大小为n(n=7),HASH函数为h(x)=x%n,如果用线性探测法F(i)=i解决冲突,请在下面HASH表中依次插入关键字5,18,21,14,25,4以后,关键字4、5和25所在地址的下标分别是、和,插入上述6个元素的平均比较次数是。
下标:
0 123456
【76,10,1】排序过程一般需经过两个基本操作,它们是①和②。
【77,10,2】结点的关键字序列是(F,B,J,G,E,A,I,D,C,H),对它按字母的字典序进行排列。
如果采用Shell排序方法,那么步长取5时,第一次扫描结果的前5个字母分别是②。
【78,10,2】在对一组关键字是(54,38,96,45,15,72,60,23,83)的记录进行直接插入排序时,当把第七个记录(关键字是60)插入到有序表时,为寻找插入位置需比较①次。
【79,10,3】在利用快速排序方法对一组关键字是(54,38,96,45,15,72,60,23,83)的记录进行排序时,需要递归调用partition函数,递归的最大深度(设第一次调用深度为1)为①,共需5次递归调用,其中第二次递归调用是对关键字是②的一组记录进行的。
【80,10,4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中,不稳定的排序方法有①。
2)分析计算作图题:
序号1-30(选自《数据结构题集》—严蔚敏等编)
【1,1,4】
(选自《数据结构题集》1.8,选做题)
设n为正整数,试确定下列各段程序中前置以记号@的语句的频度(语句的频度指的是该语句重复执行的次数)。
(1)i=1;
k=0;
while(i<
i++;
@k+=10*i;
(2)x=91;
y=100;
while(y>
0){
@if(x>
100){x-=10;
y--;
elsex++;
【2,1,4】
(选自《数据结构题集》1.9,选做题)
假设n为2的乘幂,并且n>
2,试求下列算法的时间复杂度及变量count的值(以n函数形式表示)
intTime(intn){
count=0;
x=2;
while(x<
n/2){
x*=2;
count++;
return(count);
}//Time
【3,2,3】
(选自《数据结构题集》2.6,必做题)
已知L是无表头结点的单链表,且P既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.在P结点后插入S结点的语句序列是____________________
b.在P结点前插入S结点的语句序列是____________________
c.在表首插入S结点的语句序列是________________________
d.在表尾插入S结点的语句序列是________________________
(1)P—>
next=S;
(2)P—>
next=P—>
next—>
next;
(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;
【4,2,2】
(选自《数据结构题集》2.10,选做题)
指出以下算法中的错误和低效(即费时)之处,并将它改写为一个既正确又高效的算法。
StatusDeleteK(SqList&
a,inti,intk){
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if(i<
1||k<
0||i+k>
a.length)returnINFEASIBLE;
//参数不合法
else{
for(count=1;
count<
k;
count++){
//删除一个元素
for(j=a.length;
j>
=i+1;
j――)a.elem[j-1]=a.elem[j];
a.length――;
returnOK;
}//DeleteK
【5,3,1】
(选自《数据结构题集》3.4,必做题)
简述以下算法的功能(栈的元素类型SElemType为int)
(1)Statusalgo1(StackS){
inti,n,A[255];
n=0;
while(!
StackEmpty(S)){n++;
Pop(S,A[n]);
for(i=1;
i<
=n;
i++)Push(S,A[i]);
(2)Statusalgo2(StackS,inte){
StackT;
intd;
InitStack(T);
while(!
StackEmpty(S)){
Pop(S,d);
if(d!
=e)Push(T,d);
StackEmpty(T)){
Pop(T,d);
Push(S,d);
【6,3,1】
(选自《数据结构题集》3.15,选做题)
假设以顺序存储结构实现一个双向栈,即在一堆数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点。
试编写实现这个双向栈tws的三个操作:
初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法,其中i为0或1,用以分别指示设在数组两端的两个栈,并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么优缺点。
【7,3,4】
(选自《数据结构题集》3.13,必做题)
简述以下算法的功能(栈和队列的元素类型均为int)
voidalgo3(Queue&
Q){
StackS;
intd;
InitStack(S);
while(!
QueueEmpty(Q)){
DeQueue(Q,d);
Push(S,d);
StackEmpty(S)){
Pop(S,d);
EnQueue(Q,d);
【8,3,2】
(选自《数据结构题集》3.19,选做题)
假设一个算术表达式中可以包含三种括号:
圆括号“(”和“)”,方括号“[”和“]”和花括号“{”和“}”,且这三种括号可以按任意的次序嵌套使用(如:
…[…{…}…[…]…]…[…]…(…)…)。
编写判别给定表达式所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。
【9,4,1】
(选自《数据结构题集》4.3,必做题)
设s=‘IAMASTUDENT’,t=‘GOOD’,q=‘WORKER’。
求:
StrLength(s),StrLength(t),SubString(s,8,7),SubString(t,2,1),
Index(s,‘A’),Index(s,t),Replace(s,‘STUDENT’,q),
Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))
【10,5,1】
(选自《数据结构题集》5.1,必做题)
假设有两维数组A6x8,每个元素用相邻的6个字节存储,存储按字节编址。
已知A的起始地址为1000,计算:
(1)数组A的存储量;
(2)数组A的最后一个元素a57的第一个字节的地址;
(3)按行存储时,元素a14的第一个字节的地址;
(4)按列存储时,元素a47的第一个字节的地址;
【11,6,1】
(选自《数据结构题集》6.1,必做题)
已知一棵树边的集合为{<
I,M>
,<
I,N>
E,I>
B,E>
B,D>
A,B>
G,J>
G,K>
C,G>
C,F>
H,L>
C,H>
A,C>
},请画出这棵树,并回答下列问题:
(1)哪个是根结点?
(2)哪些是叶子结点?
(3)哪个是结点G的双亲?
(4)哪些是结点G的祖先?
(5)哪些是结点G的孩子?
(6)哪些是结点E的子孙?
(7)哪些是结点E的兄弟?
哪些是结点F的兄弟?
(8)结点B和N的层次号分别是什么?
(9)树的深度是多少?
(10)以结点C为根的子树的深度是多少?
【12,6,1】
(选自《数据结构题集》6.4,选做题)
一棵深度为H的满k叉树有如下性质第H层上的结点都是叶子节点,其余各层上每个结点都有k棵非空子树。
如果按层次顺序从1开始对全部结点编号,问:
(1)各层的结点数目是多少?
(2)编号为p的父结点(若存在)的编号是多少?
(3)编号为p的结点的第i个儿子结点(若存在)的编号是多少?
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 作业