华工数据结构作业已做.docx
- 文档编号:4157765
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:12
- 大小:150.69KB
华工数据结构作业已做.docx
《华工数据结构作业已做.docx》由会员分享,可在线阅读,更多相关《华工数据结构作业已做.docx(12页珍藏版)》请在冰点文库上搜索。
华工数据结构作业已做
2017华工数据结构作业
一、程序阅读填空
1、在顺序表中第i个位置插入新元素x
template
:
Insert(Type&x,inti){
if(i<0||i>last+1||last==MaxSize-1)return0;//插入不成功
else{
last++;
for(________intj=MaxSize-1________________;j>i;j--)
___________data[j+1]=data[j]__________________;
data[i]=x;
return1;//插入成功
}
}
1.直接选择排序的算法
template
{for(inti=0;i template intk=i; for(intj=i+1;j if(list、Vector[j]、getKey() ___k=j__________________;//当前具有最小关键码的对象 if(k! =i)S[i],list、Vector[k]);//交换 } 3、删去链表中除表头结点外的所有其她结点 template : MakeEmpty(){ ListNode while(first→link! =NULL){ ____________q=first->link______________; _________fitst->link=q->link_________________; //将表头结点后第一个结点从链中摘下 deleteq;//释放它 } last=first;//修改表尾指针 } 4、基于有序顺序表的折半搜索递归算法(Element为有序顺序表) template : BinarySearch(constType&x,constintlow,constinthigh)const { intmid=-1; if(low<=high){ ________mid=(low+high)/2__________________; if(Element[mid]、getKey() mid=BinarySearch(__________x,mid+1,high________________); elseif(Element[mid]、getKey()>x) mid=BinarySearch(x,low,mid-1); } returnmid; } 5、在顺序表中第i个位置插入新元素x。 intinsert(sqlist*L,datatypex,inti) {intj; if(L->n==maxsize){cout<<”表满,不能插入! (上溢)\n”;return–1;} if(i<0||i>=maxsize){cout<<”非法插入位置! \n”;return0;} for(j=L->n;j>=i;j--) L->data[j]=L->data[j-1];//节点后移 L->data[j]=x;//插入x L->n++;//修改表长 Return1;//插入成功 } 6、直接选择排序的算法 voidSelectSort(listR,intn) {inti,j,k; for(i=1;i<=n-1;i++){//n-1趟排序 k=i; for(j=i+1;j<=n,j++)//在当前无序区中找键值最小的记录R[k] if(R[j]、key if(k! =i){R[0]=R[i];R[i]=R[k];R[k]=R[0];} } } 二、简答题 1、线性表可用顺序表或就是链表存储,此两种存储表示各有哪些优缺点? 答: 1)顺序存储表示就是将数据元素存放于一个联系的存储空间中,实现顺序存取或(按下标)直接存取。 顺序存储的优缺点有: (1)它的存储效率高,存取速度快。 但它的空间大小一经定义,在程序整个运行期间不会发生改变,因此,不易扩充。 (2)由于在插入或删除就是,为了保持原有次序(没有规定元素进栈顺序),平均需要移动一半(或近一半)元素,修改效率不高。 2)链表就是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序就是通过链表中的指针链接次序实现的。 链表存储的优缺点有: (1)只要存储器中还有空间,就不会产生存储溢出问题。 (2)在插入与删除时不需要保存数据元素原来的物理顺序,只需要保存原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。 但存取表中的数据元素时,只能循链接顺序访问,因此存取效率不高。 2、设有一个输入数据的序列就是{46,25,78,62,12,37,70,29},试画出从空树起,逐个输入各个数据而生成的二叉搜索树。 答: 按顺序逐个输入: 46 /\ 2578 /\/ 123762 /\ 2970 3、用广义表的带表头结点的存储表示法表示下列集合。 A=() B=(6,2) C=(‘a’,(5,3,‘x’)) D=(B,C,A) E=(B,D) 答: 4、上图所示为一有向图,请给出该图的下述要求: (1)给出每个顶点的入度与出度; (2)以结点3为起始结点,分别画出该图的一个深度优先生成树与一个宽度优先生成树; (3)给出该图的邻接矩阵; (4)给出该图的邻接表; 答: (1)顶点入度出度 130 222 312 413 521 623 (2) 深度优先生成树 广度优生成树 (3)邻接矩阵 000000 100100 010001 001011 100000 110010 (4)邻接表 5、对于如上图所示的有向图,试写出: (1)从顶点①出发进行深度优先搜索所得到的深度优先生成树; (2)从顶点②出发进行广度优先搜索所得到的广度优先生成树; 答: (1)以顶点①为根的深度优生树(不唯一): ②③④⑤⑥ ①① ②③或②③ ④⑤④⑤ (3)以顶点②为根的广度优生成树: ④ ②③ ⑤① 6、已知二叉树的先序、中序与后序序列分别如下,但其中有一些已模糊不清,试构造出该二叉树。 先序序列 _BC_EF__ 中序序列 BDE_AG_H 后序序列 _DC_GH_A 答: 后续最后一个就是A,所以A就是先序的第一个得到: 先序序列ABC_EF_ 中序序列BDE_AG_H 后序序列_DC_GH_A (A) /\ (BDE)(G_H) 先序的第二个元素时B,所以B就是A的左子树根节点,有中序B在最前,知道其她元素都在B的右子树上。 所以,后序序列为(DE_)B(B_H)A,对比已有的后序序列_DC_GH_A 得后序序列为: EDCBGHFA,中序序列为: BDECAGFH先序序列ABC_EF_中序序列BDECAGFH后序序列EDCBGHFA 所以 (A) /\ (B)(F) \/\ (C)(G)(H) / (D) \ (E) 7.分析下列两个程序段的运行时间(时间复杂度)。 voidmystery(intn) {inti,j,k; for(i=1;i for(j=i+1;j<=n;j++) for(k=1;k<=j;k++); } 答: O(n3) voidodd(intn) {inti,j,x=0,y=0; for(i=1;i<=n;i++) ifodd(i) {for(j=i;j<=n;j++)x++; for(j=1;j<=i;j++)y++; } } 答: O(n2) 8、有一组数据: 25,50,70,21,4,18,100,43,7,12。 现采用汽泡排序算法进行排序,写出每趟排序的结果,并标明第一趟数据的移动情况。 答: 第一趟: 25,50,70,21,4,18,100,43,7,12 25,50,70,21,4,18,100,43,7,12 25,50,21,70,4,18,100,43,7,12 25,50,21,4,70,18,100,43,7,12 25,50,21,4,18,70,100,43,7,12 25,50,21,4,18,70,100,43,7,12 25,50,21,4,18,70,43,100,7,12 25,50,21,4,18,70,43,7,100,12 25,50,21,4,18,70,43,7,12,100 第二趟: 25,21,4,18,50,43,7,12,70,100 第三趟: 21,4,18,25,43,7,12,50,70,100 第四趟: 4,18,21,25,7,12,43,50,70,100 第五趟: 4,18,21,7,12,25,43,50,70,100 第六趟: 4,18,7,12,21,25,43,50,70,100 第七趟: 4,7,12,18,21,25,43,50,70,100
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华工 数据结构 作业
![提示](https://static.bingdoc.com/images/bang_tan.gif)