欢迎来到天天文库
浏览记录
ID:35983202
大小:160.50 KB
页数:8页
时间:2019-04-29
《数据结构作业(已做).doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、一、程序阅读填空1.在顺序表中第i个位置插入新元素xtemplateintSeqList::Insert(Type&x,inti){if(i<0
2、
3、i>last+1
4、
5、last==MaxSize-1)return0;//插入不成功else{last++;for(___intj=MaxSize-1______;j>i;j--)____data[j+1]=data[j]_______;data[i]=x;return1;//插入成功}}2.直接选择排序的算法templat
6、evoidSelectSort(datalist&list){for(inti=0;iviodSelectExchange(datalist&list,constinti){intk=i;for(intj=i+1;j7、ector[k].getKey())___k=j_______________;//当前具有最小关键码的对象if(k!=i)Swap(list.Vector[i],list.Vector[k]);//交换}3、删去链表中除表头结点外的所有其他结点templatevoidList::MakeEmpty(){ListNode*q;while(first→link!=NULL){__q=first->link;__first->link=q->link___;/8、/将表头结点后第一个结点从链中摘下deleteq;//释放它}last=first;//修改表尾指针}4、基于有序顺序表的折半搜索递归算法(Element为有序顺序表)templateintorderedList::BinarySearch(constType&x,constintlow,constinthigh)const{intmid=-1;if(low<=high){___mid=(low+high)/2____;if(Element[mid].getKey()9、x)mid=BinarySearch(x,low,mid-1);}returnmid;}5、在顺序表中第i个位置插入新元素x。intinsert(sqlist*L,datatypex,inti){intj;if(L->n==maxsize){cout<<”表满,不能插入!(上溢)”;return–1;}if(i<010、11、i>=maxsize){cout<<”12、非法插入位置!”;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].key13、ey)k=j;if(k!=i){R[0]=R[i];R[i]=R[k];R[k]=R[0];}}}二、简答题1.线性表可用顺序表或是链表存储,此两种存储表示各有哪些优缺点?答:顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间不会发生改变,因此,不易扩充。同时,由于在插入或删除时,为保持原有次序(没有规定元素进栈顺序),平均需要移动一半(或近一半)元素,修改效率不高。链接存储表示的存储空间一般在程14、序的运行过程中动态分配和释放,且只要存储器中还有空间,就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高。2.设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起,逐个输入各个数据而生成的二叉搜索树。答:按顺序逐个输入46/2578//123762
7、ector[k].getKey())___k=j_______________;//当前具有最小关键码的对象if(k!=i)Swap(list.Vector[i],list.Vector[k]);//交换}3、删去链表中除表头结点外的所有其他结点templatevoidList::MakeEmpty(){ListNode*q;while(first→link!=NULL){__q=first->link;__first->link=q->link___;/
8、/将表头结点后第一个结点从链中摘下deleteq;//释放它}last=first;//修改表尾指针}4、基于有序顺序表的折半搜索递归算法(Element为有序顺序表)templateintorderedList::BinarySearch(constType&x,constintlow,constinthigh)const{intmid=-1;if(low<=high){___mid=(low+high)/2____;if(Element[mid].getKey()
9、x)mid=BinarySearch(x,low,mid-1);}returnmid;}5、在顺序表中第i个位置插入新元素x。intinsert(sqlist*L,datatypex,inti){intj;if(L->n==maxsize){cout<<”表满,不能插入!(上溢)”;return–1;}if(i<0
10、
11、i>=maxsize){cout<<”
12、非法插入位置!”;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].key13、ey)k=j;if(k!=i){R[0]=R[i];R[i]=R[k];R[k]=R[0];}}}二、简答题1.线性表可用顺序表或是链表存储,此两种存储表示各有哪些优缺点?答:顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间不会发生改变,因此,不易扩充。同时,由于在插入或删除时,为保持原有次序(没有规定元素进栈顺序),平均需要移动一半(或近一半)元素,修改效率不高。链接存储表示的存储空间一般在程14、序的运行过程中动态分配和释放,且只要存储器中还有空间,就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高。2.设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起,逐个输入各个数据而生成的二叉搜索树。答:按顺序逐个输入46/2578//123762
13、ey)k=j;if(k!=i){R[0]=R[i];R[i]=R[k];R[k]=R[0];}}}二、简答题1.线性表可用顺序表或是链表存储,此两种存储表示各有哪些优缺点?答:顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间不会发生改变,因此,不易扩充。同时,由于在插入或删除时,为保持原有次序(没有规定元素进栈顺序),平均需要移动一半(或近一半)元素,修改效率不高。链接存储表示的存储空间一般在程
14、序的运行过程中动态分配和释放,且只要存储器中还有空间,就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高。2.设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起,逐个输入各个数据而生成的二叉搜索树。答:按顺序逐个输入46/2578//123762
此文档下载收益归作者所有