2017华工数据结构作业(已做)

2017华工数据结构作业一、程序阅读填空在次序表中第i个地址插入新元素xtemplate<classType>intSeqList<Type>::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;//插入成功}}直接选择排序的算法template<classType>voidSelectSort(datalist<Type>&list){for(inti=0;i<list.CurrentSize-1;i++)_______SelectExchange(list,i)_________________;}template<classType>viodSelectExchange(datalist<Type>&list,constinti){intk=i;for(intj=i+1;j<list.CurrentSize;j++)if(list.Vector[j].getKey()<list.Vector[k].getKey())___k=j__________________;//当前拥有最小要点码的对象if(k!=i)S[i],list.Vector[k]);//交换}3、删去链表中除表头结点外的全部其余结点template<classType>voidList<Type>::MakeEmpty(){ListNode<Type>*q;while(first→link!=NULL){____________q=first->link______________;_________fitst->link=q->link_________________;将表头结点后第一个结点从链中摘下deleteq;//开释它}last=first;//更正表尾指针}4、基于有序次序表的折半找寻递归算法（Element为有序次序表）template<classType>intorderedList<Type>::BinarySearch(constType&x,constintlow,constinthigh)const{intmid=-1;if(low<=high){________mid=(low+high)/2__________________;if(Element[mid].getKey()<x)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

;

//插入

xL->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<R[k].key)k=j;if(k!=i){R[0]=R[i];R[i]=R[k];R[k]=R[0];}}}二、简答题线性表可用次序表或是链表储存，此两种储存表示各有哪些优弊端？答：1）次序储存表示是将数据元素存放于一个联系的储存空间中，实现次序存取或（按下标）直接存取。次序储存的优弊端有：1）它的储存效率高，存取速度快。但它的空间大小一经定义，在程序整个运转时期不会发生改变，所以，不易扩大。2）因为在插入或删除是，为了保持原有次序（没有规定元素进栈次序），均匀需要挪动一半（或近一半）元素，更正效率不高。）链表是一种物理储存单元上非连续、非次序的储存结构，数据元素的逻辑次序是经过链表中的指针链接次序实现的。链表储存的优弊端有：1）只要储存器中还有空间，就不会产生储存溢出问题。2）在插入和删除时不需要保存数据元素本来的物理次序，只要要保存本来的逻辑次序，所以不用挪动数据，只要更正它们的链接指针，更正效率较高。但存取表中的数据元素时，只好循链接次序接见，所以存取效率不高。2.设有一个输入数据的序列是{46,25,78,62,12,37,70,29}，试画出从空树起，逐一输入各个数据而生成的二叉找寻树。答：挨次序逐一输入：46\2578/\/123762/\29703.用广义表的带表头结点的储存表示法表示以下会集。A=()B=(6,2)C=(‘a’,(5,3,‘x’))D=(B,C,A)E=(B,D)答：4.上图所示为一有向图，请给出该图的下述要求：（1）给出每个极点的入度和出度；2）以结点3为初步结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树；3）给出该图的毗邻矩阵；4）给出该图的毗邻表；答：（1）极点入度出度1302223124135216232）深度优先生成树广度优生成树1516624233（３）毗邻矩阵000000100100010001001011100000110010毗邻表对于如上图所示的有向图，试写出：从极点①出发进行深度优先找寻所获取的深度优先生成树；从极点②出发进行广度优先找寻所获取的广度优先生成树；答：（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)．解析以下两个程序段的运转时间（时间复杂度）。voidmystery(intn){inti,j,k;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)for(k=1;k<=j;k++);}答：O(n3)void{

odd(intn)inti,j,x=0,y=0;for(i=1;i<=n;i++)ifodd(i){for(j=i;j<=n;j++)for(j=1;j<=i;j++)

x++;y++;}}答：O(n2)8.有一组数据：25，50，70，21，4，18，100，43，7，12。现采纳汽泡排序算法进行排序，写出每趟排序的结果，并注明第一趟数据的挪动状况。答：第一趟：25，50，70，21，4，18，100，43，7，1225，50，70，21，4，18，100，43，7，1225，50，21，70，4，18，100，43，7，1225，50，21，4，70，18，100，43，7，1225，50，21，4，18，70，100，43，7，1225，50，21，4，18，70，100，43，7，1225，50，21，4，18，70，43，100，7，1225，50，21，4，18，70，43，7，100，1225，50，21，4，18，70，43，7，12，100第二趟：25，2