总复习(题目)详解.ppt

总复习题（题目） 6. 下面的算法可以实现递减顺序表的折半 查找，请将算法的空白处补充完整。 typedef struct { int key ; int other; } ElemType; typedef struct { ElemType *elem; int length; } SSTable; int Search_bin(SSTable ST, int key) { int low, mid, high; low=1; high= ; while (low=high) { mid= ; if (key==ST.elem[mid].key) return mid; else if( ) high=mid-1; else low= ; } return 0; } ST.length (low+hith)/2 keyST.elem[mid].key mid+1 练习：若递减顺序表的折半查找算法如下: int Search_bin(SSTable ST, int key) { int low, mid, high; low=1; high= __________; while (___________) { mid=(low+high)/2; if (____________________) return mid; else if (keyST.elem[mid].key) low=mid+1; else high= ; } return 0; } ST.length Low=hith) key==ST.elem[mid].key mid-1 7. 下面的算法可以实现,对顺序表L作降序排序的快速排序一次划分,请将算法的空白处补充完整。 已知顺序表的存储结构如下： typedef struct { int key ; int other; } RedType; typedef struct { RedType r[100] ; int length; } SqList; int Partition ( SqList L, int low, int high ) { L.r[0] = L.r[low]; pivotkey = L.r[low].key; while ( _______________ ) { while ( lowhigh _______________ ) --high ; L.r[low] = L.r[high]; while ( lowhigh L.r[low].key=pivotkey ) _______ ; L.r[high] = L.r[low]; } _________________; return low ; } L.r[high].key=pivotkey ++low L.r[low]=L.r[0] Lowhith) 8. 下面的算法实现对顺序表按直接插入排序方法作降序排序,请将算法的空白处补充完整。 已知顺序表的存储结构如下： typedef struct { int key ; int other; } RedType; typedef struct { RedType r[100] ; int length; } SqList; int InsertSort ( SqList L) { for ( i=2; i=L.length; ++i ) if (______________________) { L.r[0] = L.r[i]; _______________; for ( j=i-2;__