《马昱春数据结构作业【华工数据结构作业】.docx》由会员分享,可在线阅读,更多相关《马昱春数据结构作业【华工数据结构作业】.docx(5页珍藏版)》请在三一文库上搜索。
1、马昱春数据结构作业【华工数据结构作业】一、程序阅读填空1. 在顺序表中第 i 个位置插入新元素 xtemplate int SeqList:Insert (Type x, int i)if (ilast+1|last=MaxSize-1) return 0; 插入不成功else last+;for( _ int j=MaxSize-1_;ji;j-)_ dataj+1=dataj_;datai = x;return 1; 插入成功2. 直接选择排序的算法template void SelectSort(datalist list) for(int i=0; itemplate viod Sel
2、ectExchange(datalist list, const int i)int k = i;for(int j=i+1;jif(list.Vectorj.getKey_ k=i _;当前具有最小关键码的对象if(k!=i) Swap(list.Vectori, list.Vectork); 交换3、 删去链表中除表头结点外的所有其他结点template void List : MakeEmpty ( ) ListNode *q;while (firstlink!=NULL)_ q=first-link _;_ first-link=q-link _;将表头结点后第一个结点从链中摘下del
3、ete q; 释放它last = first; 修改表尾指针4、基于有序顺序表的折半搜索递归算法(Element 为有序顺序表)template int orderedList :BinarySearch(const Type x, const int low, const int high)constint mid = -1;if ( low_ mid=(low+high) 25 7812 37 62_(BDE_)_(G_H)_先序的第二个元素是B ,所以B 是A 的左子树根节点由中序B 在最前,知道其他元素都在B 的右子树上所以,后序序列为(DE_)B(G_H)A,对比已有的后序序列_DC
4、_GH_A得后序序列为:EDCBGHFA ,中序序列为:BDECAGFH先序序列 ABC_EF_中序序列 BDECAGFH后序序列 EDCBGHFA所以,二叉树为:_(A)_(C)_(G)_(H)_/_(D)_(E)_7分析下列两个程序段的运行时间(时间复杂度)。void mystery (int n) int i, j, k;for (i =1; ifor (j = i+1; jfor (k = 1; k答:O(n3)void odd (int n) int i, j, x = 0, y = 0;for (i =1; iif odd(i) for(j = i; jfor( j = 1; j答
5、: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,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
链接地址:https://www.31doc.com/p-6346202.html