完善下面程序下划线的地方，实现排序： def insert_sort（lists): for i in range（len（lists)): pos

程序填空题： (请阅读下面拓扑排序算法程序，完成填空，将答案写在该题横线上 ,每空3分，本题满分9分)。 int TopoSort (AdjList G) { Stack S; int indegree[MAX_VERTEX_NUM]; int i, count, k; ArcNode *p; FindID(G,indegree); /*求各顶点入度*/ InitStack(&S); for(i=0;i<g.vexnum;i++) if( ) push(&s,i); count="0;" while(!stackempty(s)) { pop(&s,&i); printf("%c",g.vertex[i].data); count++; p="G.vertexes[i].firstarc;" while( k="p-">adjvex; indegree[k]--; if(indegree[k]==0) Push(&S, k); ; } } /*while*/ if (count < G.vexnum) return(Error); else return(Ok); }

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 阅读SELECTION-SORT算法，关于第3.行至第4.行间程序段的作用，下列说法正确的是_____。

A、循环地在未排序元素集合中找最小值元素的位置，该位置保存在变量k中

B、循环地在未排序元素集合中找最小值元素，该元素保存在变量k中

C、循环地在未排序元素集合中找最大值元素的位置，该位置保存在变量k中

D、循环地在未排序元素集合中找最大值元素，该元素保存在变量k中

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 阅读INSERTION-SORT算法，关于第4.行至第6.行间程序段的作用，下列说法正确的是_____。

A、将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置

B、将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置

C、将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向前移动一个位置

D、将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向后移动一个位置

A、data=[34,5,-6,12,87,29] data.sort()

B、data=[34,5,-6,12,87,29] n=len(data) od=[] while i<n: while if data[j]> data[j+1]: t=data[j] data[j]=data[j+1] data[j+1]=t j+=1 i+=1

C、data=[34,5,-6,12,87,29] n=len(data) i=0 j=0 while i <n-1: while if data[j]> data[j+1]: t=data[j] data[j]=data[j+1] data[j+1]=t j+=1 i+=1 print(data)

D、data=[34,5,-6,12,87,29] n=len(data) i=0 j=0 while i <n-1: while if data[i]> data[j]: t=data[i] data[i]=data[j] data[j]=t j+=1 i+=1

下面程序的功能是 ： 将 N 行 N 列二维数组中每一行的元素进行排序 ， 第 0 行从小到大排序 ， 第 1 行从大到小排序，第 2 行从小到大排序，第 3 行从大到小排序，例如：

define N 4

void sort(int a[][N])

{ int i, j, k, t;

for (i=0; i<N;i++)

for (j=0; j<N-1:j++)

for (k= 【 13 】 ; k<N;K++)

/* 判断行下标是否为偶数来确定按升序或降序来排序 */

if ( 【 14 】 ? a[i][j]<a[i][k]); a[i][j]>a[i][k])

{ t = a[i][j];

a[i][j]=a[i][k];

a[i][k] = t;

}

}

void outarr(int a[N][N])

{ …… }

main()

{ int aa[N][N]={{2,3,4,1},{8,6,5,7},{11,12,10,9},{15,14,16,13}};

outarr(aa); /* 以矩阵的形式输出二维数组 */

sort(aa);

outarr(aa);

}

【Test-10-2】直接插入排序算法可以基于链表来实现。假设有一个数据随机排列的带表头结点的单链表，表头指针为 head，下面算法的功能是：一个基于链表的直接插入排序算法，排序后的单链表的表头指针仍然是 head。请在空白处填入正确的语句。 const ElemType maxValue = ……; //自行设定最大值, 应大于链表中任何数据值 void insertSort(LinkList *&head) { LinkNode *pre, *p, *q, *s = ______①______, *t; if(s == NULL) return; _____②_______; head->data = _______③_______; q = ______④________; s->next = head; //形成一个元素的有序循环链表 while(q != NULL) { pre = head; p = head->next; while(__________⑤________) { pre = p; p = p->next; } s = q; q = q->next; s->next = p; pre->next = s; if(s->data > t->data) t = s; } t->next = NULL; }

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 阅读BUBBLE-SORT算法，其中关于haschange变量的作用，下列说法不正确的是_____。

A、haschange用于标记每个轮次的相邻元素比较中，是否有“交换”发生

B、haschange用于判断至某个轮次时是否已完成排序，以便提前结束算法

C、haschange需要在每轮次之前置初始值为假，表示没有“交换”发生

D、上述说法有不正确的

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 关于三种排序算法，下列说法正确的是_____。

A、三种算法的时间复杂度都为，所以三种算法的执行效率是一样的；

B、尽管三种算法的时间复杂度都为，但细致比较还是有差别的，例如冒泡法排序比选择法排序要快一些；

C、尽管细致比较三种算法的执行时间是有差别的，但这种差别对内排序问题而言是可以忽略不计的

D、尽管细致比较三种算法的执行时间是有差别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 阅读BUBBLE-SORT算法，已知N=20，下列说法正确的是_____。

A、第5轮次，是将第1个元素至第15个元素之间的元素，相邻者进行比较

B、第4轮次，是将第1个元素至第20个元素之间的元素，相邻者进行比较

C、第8轮次，是将第20个元素至第12个元素之间的元素，相邻者进行比较

D、第11轮次，是将第20个元素至第1个元素之间的元素，相邻者进行比较