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

一、程序阅读填空

1. 在顺序表中第 i 个位置插入新元素 x

template int SeqList::Insert (Type & x, int i){

if (ilast+1||last==MaxSize-1) return 0; //插入不成功

else {

last++;

for( _____ int j=MaxSize-1___________________;j>i;j--)

__________ data[j+1]=data[j]__________________;

data[i] = x;

return 1; //插入成功

}

}

2. 直接选择排序的算法

template void SelectSort(datalist & list)

{ for(int i=0; i

template viod SelectExchange(datalist & list, const int i){

int k = i;

for(int j=i+1;j

if(list.Vector[j].getKey()

{ for(j = i; j

for( j = 1; j

}

}

答：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