1 / 9
文档名称:

《数据结构》4次作业.docx

格式:docx   大小:56KB   页数:9页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

《数据结构》4次作业.docx

上传人:毒药 Posion 2022/11/30 文件大小:56 KB

下载得到文件列表

《数据结构》4次作业.docx

相关文档

文档介绍

文档介绍:该【《数据结构》4次作业 】是由【毒药 Posion】上传分享,文档一共【9】页,该文档可以免费在线阅读,需要了解更多关于【《数据结构》4次作业 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。《数据结构》4次作业
一、单项选择题
,存储单元的地址()。
,部分不连续
()。

[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为()。
++++225
,则利用()存储方式最节省时间。

,则采用()存储方式最节省运算时间。

(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为()。
(i)(1)(n)(i-1)
,判定该表为空表的条件是()。
==→next==→next==!=NULL
,2,3,…,n,其输出序列为p1,p2,p3,…,pN,若pN是n,则pi是()。
--i+
,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列?()。

,因为散列函数是一对一的关系,则选择好的()方法是散列文件的关键。

11.   对一个算法的评价,不包括如下()方面的内容。

12.    在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行()。
->next=HL->next;HL->next=p;->next=HL;HL=p;
->next=HL;p=HL;=p;p->next=HL;
13.   对线性表,在下列哪种情况下应当采用链表表示?()


14.  一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是()

15.   AOV网是一种()。

16.   若需要利用形参直接访问实参时,应将形参变量说明为()参数。

17.   在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的()。


二、填空题


,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用_______存储结构。
=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是________。
(1<=i<=n)之前插入一个元素时,需向后移动________个元素。

:1,2,3则不可能的栈输出序列是_______。
,只有两种方法,它们是______和______。
9.     数据结构是指数据及其相互之间的______________。当结点之间存在M对N(M:N)的联系时,称这种结构为_____________________。
10.     队列的插入操作是在队列的___尾______进行,删除操作是在队列的____首______进行。
11.    当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈满的条件是___top==0_____________。
12.       对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为_________,在表尾插入元素的时间复杂度为____________。
13.       二叉树是指度为2的____________________树。一棵结点数为N的二叉树,其所有结点的度的总和是_____________。
14.       对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个______________。对一棵由算术表达式组成
的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。
三、判断题
,如果用C语言或PASCAL语言等高级语言来描述,则算法实际上就是程序了。()
,实现应用程序与存储结构的独立。()
,必会失去随机存取功能。()
。()
,因此与线性表一样,可以对它进行插入,删除等操作。()
,必会失去随机存取功能。()
。()
,每个记录由一个或多个数据项组成,因而一个文件可看作由多个记录组成的数据结构。()
三、解答题
?
?各有什么特点?
,其入栈次序为:A,B,C,D,E,在各种可能的出栈次序中,以元素C,D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?
四、程序阅读题
,写出此程序所要完成的功能,及时间复杂度。
intcompare(SqListA,SqListB)
{j=0;
while(j<&&j<)
if([j]<[j])return(-1);
elseif([j]>[j])return(1);
elsej++;
if(==)return(0);
elseif(<)return(-1);
elsereturn(1);
}
,其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队,出队和判别队列是否为空的函数,请填写算法中得空白处,完成其功能。
typedefstructnode
{intdata;structnode*lchild,*rchild;}btnode;
voidEXCHANGE(btnode*bt)
{btnode*p,*q;
if(bt){ADDQ(Q,bt);
while(!EMPTY(Q))
{p=DELQ(Q);q=(1)_;p->rchild=(2)___;(3)___=q;
if(p->lchild)(4)___;if(p->rchild)(5)___;
}
}
}
五、算法设计题

 六、 运算题
1.       已知一个6´5稀疏矩阵如下所示,试:
(1) 写出它的三元组线性表;
(2) 给出三元组线性表的顺序存储表示。
2.  设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起,逐个输入各个数据而生成的二叉搜索树。
七、阅读算法
1.       intPrime(intn)
{inti=1;
intx=(int)sqrt(n);
while(++i<=x)
if(n%i==0)break;
if(i>x)return1;
elsereturn0;}
指出该算法的功能;
(2)    该算法的时间复杂度是多少?
2.  写出下述算法的功能:
voidAJ(adjlistGL,inti,intn)
{QueueQ;
InitQueue(Q);
cout<<i<<'';
visited[i]=true;
QInsert(Q,i);
while(!QueueEmpty(Q)){
intk=QDelete(Q);
edgenode*p=GL[k];
while(p!=NULL)
{intj=p->adjvex;
if(!visited[j])
{cout<<j<<'';
visited[j]=true;
QInsert(Q,j);}
p=p->next;}}}
HL是单链表的头指针,试写出删除头结点的算法。
ElemTypeDeleFront(LNode*&HL)
数据结构复****资料
一、选择题
1-5ABCAC
6-10DDCBB

二、填空题
l.(n-2)(n+3)/2
=n2+1

-1n2+n3


7.
8.
9.        联系图(或图结构)
10.        尾首
11.        top==0
12.        O(1)O(n)
13.        12844108
14.        33
6
5
5
1
5
1
3
2
-1
4
5
-2
5
1
5
6
3
7
图7
三、判断题
1.×2.× 3.√4.√5.×
6.√7.√8.×
四、解答题
1、数据结构是计算机存储、,
2、数据元素之间的关系在计算机中有几种表示方法?各有什么特点?
答:四种表示方法(1)顺序存储方式。数据元素顺序存放,每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大,但有些操作(如插入、删除)效率较差。(2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。(3)索引存储方式。除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表,索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标),兼有静态和动态特性。(4)散列存储方式。通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址,这种存储方式称为散列存储。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。
3、栈是操作受限制的线性表,出栈是先进后出。CD固定后可以先进E,再出E,再出B再出A,就CDEBA,或者是先出B,再进E,再出E,再出A,就是CDBEA,或者先出B,再出A,再进E,再出E,即为CDBAE。故为三种。

五、算法设计题
:
intflag=1;
intmax;
voidsortbitree(bitreeT)
{if(T)
{sortbitree(T->lchild);
k++;
if(k==1)max=T->data;
else
{if(T->data>max)max=T->data;
elseflag=0;}
sortbitree(T->rchild);
}
}
:
intpathed[MAX_VERTEX_NUM];
inttop=0;
intpath[MAX_VERTEX_NUM];
intispath(algraphgraph,intvi,intvj)
{arcptrp;
intj;
pathed[vi]=1;path[++top]=vi;/*将顶点vi加入当前路径path*/
if(path[top]==vj)/*存在顶点vi到顶点vj的路径*/
return1;
else/*将顶点vi的邻接点加入当前路径*/
for(p=[vi].firstarc;p;p=p->nextarc)
if(!pathed[p->adjvex])returnispath(graph,p->adjvex,vj);
pathed[vi]=0;top--;/*将顶点vi从当前路径path中删除*/
if(top==0)return0;/*不存在vi到vj的简单路径*/
}
:
bithrtreeinsucc(bithrtreep)/*找p结点的后继*/
{if(p->rtag==1)/*后继线索*/
returnp->rchild;
else/*右子树的最左下结点*/
{p=p->rchild;
while(p->ltag==0)p=p->lchild;
returnp;}
六、 运算题
1.        (1)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)
(2)三元组线性表的顺序存储表示如图7示。
2.        如图8所示。
图8
七、 阅读算法
1.        (1)判断n是否是素数(或质数)
(2)O()
2.        功能为:从初始点vi出发广度优先搜索由邻接表GL所表示的图。