马昱春数据结构作业【华工数据结构作业】

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，2