注意：此页面搜索的是所有试题
国家开放大学数据结构复习题
序列3,1,7,18,6,9,13,12经一趟归并排序的结果为1,3,7,18,6,9,13,12。
待排序的序列为8,3,4,1,2,5,9，采用直接选择排序算法，当进行了两趟选择后，结果序列为1,2,8,3,4,5,9。
序列15,13,16,14,19,17，采用冒泡排序算法(升序)，经一趟冒泡后，结果序列是13,15,14,16,17,19。
在对10个记录的序列(14,30,10,7,22,13,66,85,47,58)进行直接插入排序时，当把第6个记录13 插入到有序表时，为寻找插入位置，需比较3次。
冒泡排序是一种比较简单的插入排序方法。
在归并排序中，在第3趟归并中，是把长度为4的有序表归并为长度为8的有序表。
（1）一组记录的关键字序列为（45，40，65，43，35，95），利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果为（ ）。
A. 35，40，65，45，35，95
B. 35，40，65，43，45，95
C. 35，40，43，45，65，95
D. 35，40，45，43，65，95
（2）对上述序列利用直接插入排序，逐次插入过程中，共进行了（ ）次元素间的比较。
A. 8 B. 11 C. 9 D. 10
（1）对关键字序列（36，69，46，28，30，74）采用快速排序，以第一个关键字为分割元素，经过一次划分后的结果序列为（ ）。
A. 30，28，46，36，69，74 B. 28，30，36，46，69，74
C. 28，30，46，36，69，74 D. 30，28，36，46，69，74
（2）用冒泡法对上述序列排序，经过两趟冒泡的结果序列为（ ）。
A. 36，28，30，46，69，74 B. 36，46，28，20，69，74
C. 38，36，30，46，69，74 D. 28，36，30，46，69，74
（1）一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序的方法建立的初始堆为（ ）（堆顶元素是最小元素,采用树的形式建堆）。
A. 39，41，57，80，47，46 B. 39，41，46，80，47，57
C. 39，47，46，80，41，57 D. 39，41，57，80，46，47
（2）输出堆顶元素后,调整后的堆为（ ）。
A. 41，47，46，80，57 B. 41，57，46，80，47
C. 41，57，80，47，46 D. 41，80，46，47，57
（1）一组记录的关键字序列为（42，37，62，40，32，92），利用快速排序算法，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
A. 37，32，40，42，62，92 B. 32，37，40，42，62，92
C. 32，37，40，62，42，92 D. 42，37，40，62，32，92
（2）利用筛选过程把序列（42，82，67，102，16，32，57，52）建成初始堆（小根堆）为（ ）。
A. 42，16，67，52，82，32，57，102
B. 16，32，42，52，82，57，67，102
C. 16，42，32，52，82，67，57，102
D. 16，32，82，52，42，102，67，57
（1）对关键字序列（56，51，71，54，46，106），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
A. 46，51，56，54，71，106 B. 56，51，54，46，71，106
C. 46，51，54，56，71，106 D. 56，51，46，54，71，106
（2）一组记录的关键字序列为（60，47，80，57，39，41，46，30），利用归并排序的方法，经过(2,2)归并的结果序列为（ ）。
A. 30，57，60，80，47，39，41，46
B. 47，,60，57，80，30，39，41，46
C. 41，57，60，80，30，39，47，46
D. 47，57，60，80，30，39，41，46
以下直接插入排序算法对存放在a[0],a[1],···,a[n-1]中，长度为n的记录序列按关键字key由小到大排序。
void disort (NODE a[ ], int n)
{ int i,j;
NODE temp;
for (i=1;i<n;i++)
{ temp=a[i];
j=j-1;
while (__(1)____&&temp.key<a[j].key)
{ a[j+1]= (2) ;
(3) ;
}
a[j+1]= __(4) ;
}
}
【答案选项】
A. j--
B. j>=0
C. temp
D. a[j]
以下程序是折半插入排序的算法
设待排序的记录序列存放在a[1],…a[n]中，以a[0]作为辅助工作单元，程序是要把a[i] 插入到已经有序的序列a[1],…a[i-1]中。
void binsort (NODE a[ ],int n)
{ int x,i,j,s,k,m;
for (i=2；i<=__(1)____ ;i++)
{ a[0]=a[i];
x= a[i].key;
s=1;
j=i-1;
while (s<=j)
{ m=__(2)___;
if( x<a[m].key)
__(3)___;
else
__(4)___;
}
for ( k=i-1;k>=j+1;k- -)
__(5)___=a[k];
a[j+1]=a[0];
}
}
【答案选项】
A. (s+j)/2
B. j=m-1
C. a[k+1]
D. n
E. s=m+1
以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，其中n是元素个数，要求按升序排列。
void bsort (NODE a[ ], int n)
{ NODE temp;
int i,j,flag;
for(j=1; (1) ;j++)
{ flag=0;
for(i=1; (2) ;i++)
if(a[i].key>a[i+1].key)
{ flag=1;
temp=a[i];
(3) ;
(4) ;
}
if(flag= =0) break;
}
}
程序中flag的功能是 (5) 。
【答案选项】
A. a[i]=a[i+1]
B. j<=n-1
C. a[i+1]=temp
D. 当某趟冒泡中没有出现交换则已排好序结束循环
E. i<=n-j
以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序。
typedef struct
{ int key;
……
}NODE;
void selsort(NODE a[],int n)
{
int i,j,k;
NODE temp;
for( i=1; i<= ___(1)_____; i++)
{
k=i;
for( j=i+1;j<= _(2)_ _ _; j++)
if(a[j].key<a[k].key) (3)_____ _;
if( i!=k)
{
temp=a[i];
(4)___ __;
(5)__ __;
}
}
}
【答案选项】
A. n
B. a[i]=a[k]
C. k=j
D. a[k]=temp
E. n-1
待排序的序列为8,3,4,1,2,5,9，采用直接选择排序算法，当进行了两趟选择后，结果序列为1,2,8,3,4,5,9。
序列15,13,16,14,19,17，采用冒泡排序算法(升序)，经一趟冒泡后，结果序列是13,15,14,16,17,19。
在对10个记录的序列(14,30,10,7,22,13,66,85,47,58)进行直接插入排序时，当把第6个记录13 插入到有序表时，为寻找插入位置，需比较3次。
冒泡排序是一种比较简单的插入排序方法。
在归并排序中，在第3趟归并中，是把长度为4的有序表归并为长度为8的有序表。
（1）一组记录的关键字序列为（45，40，65，43，35，95），利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果为（ ）。
A. 35，40，65，45，35，95
B. 35，40，65，43，45，95
C. 35，40，43，45，65，95
D. 35，40，45，43，65，95
（2）对上述序列利用直接插入排序，逐次插入过程中，共进行了（ ）次元素间的比较。
A. 8 B. 11 C. 9 D. 10
（1）对关键字序列（36，69，46，28，30，74）采用快速排序，以第一个关键字为分割元素，经过一次划分后的结果序列为（ ）。
A. 30，28，46，36，69，74 B. 28，30，36，46，69，74
C. 28，30，46，36，69，74 D. 30，28，36，46，69，74
（2）用冒泡法对上述序列排序，经过两趟冒泡的结果序列为（ ）。
A. 36，28，30，46，69，74 B. 36，46，28，20，69，74
C. 38，36，30，46，69，74 D. 28，36，30，46，69，74
（1）一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序的方法建立的初始堆为（ ）（堆顶元素是最小元素,采用树的形式建堆）。
A. 39，41，57，80，47，46 B. 39，41，46，80，47，57
C. 39，47，46，80，41，57 D. 39，41，57，80，46，47
（2）输出堆顶元素后,调整后的堆为（ ）。
A. 41，47，46，80，57 B. 41，57，46，80，47
C. 41，57，80，47，46 D. 41，80，46，47，57
（1）一组记录的关键字序列为（42，37，62，40，32，92），利用快速排序算法，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
A. 37，32，40，42，62，92 B. 32，37，40，42，62，92
C. 32，37，40，62，42，92 D. 42，37，40，62，32，92
（2）利用筛选过程把序列（42，82，67，102，16，32，57，52）建成初始堆（小根堆）为（ ）。
A. 42，16，67，52，82，32，57，102
B. 16，32，42，52，82，57，67，102
C. 16，42，32，52，82，67，57，102
D. 16，32，82，52，42，102，67，57
（1）对关键字序列（56，51，71，54，46，106），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
A. 46，51，56，54，71，106 B. 56，51，54，46，71，106
C. 46，51，54，56，71，106 D. 56，51，46，54，71，106
（2）一组记录的关键字序列为（60，47，80，57，39，41，46，30），利用归并排序的方法，经过(2,2)归并的结果序列为（ ）。
A. 30，57，60，80，47，39，41，46
B. 47，,60，57，80，30，39，41，46
C. 41，57，60，80，30，39，47，46
D. 47，57，60，80，30，39，41，46
以下直接插入排序算法对存放在a[0],a[1],···,a[n-1]中，长度为n的记录序列按关键字key由小到大排序。
void disort (NODE a[ ], int n)
{ int i,j;
NODE temp;
for (i=1;i<n;i++)
{ temp=a[i];
j=j-1;
while (__(1)____&&temp.key<a[j].key)
{ a[j+1]= (2) ;
(3) ;
}
a[j+1]= __(4) ;
}
}
【答案选项】
A. j--
B. j>=0
C. temp
D. a[j]
以下程序是折半插入排序的算法
设待排序的记录序列存放在a[1],…a[n]中，以a[0]作为辅助工作单元，程序是要把a[i] 插入到已经有序的序列a[1],…a[i-1]中。
void binsort (NODE a[ ],int n)
{ int x,i,j,s,k,m;
for (i=2；i<=__(1)____ ;i++)
{ a[0]=a[i];
x= a[i].key;
s=1;
j=i-1;
while (s<=j)
{ m=__(2)___;
if( x<a[m].key)
__(3)___;
else
__(4)___;
}
for ( k=i-1;k>=j+1;k- -)
__(5)___=a[k];
a[j+1]=a[0];
}
}
【答案选项】
A. (s+j)/2
B. j=m-1
C. a[k+1]
D. n
E. s=m+1
以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，其中n是元素个数，要求按升序排列。
void bsort (NODE a[ ], int n)
{ NODE temp;
int i,j,flag;
for(j=1; (1) ;j++)
{ flag=0;
for(i=1; (2) ;i++)
if(a[i].key>a[i+1].key)
{ flag=1;
temp=a[i];
(3) ;
(4) ;
}
if(flag= =0) break;
}
}
程序中flag的功能是 (5) 。
【答案选项】
A. a[i]=a[i+1]
B. j<=n-1
C. a[i+1]=temp
D. 当某趟冒泡中没有出现交换则已排好序结束循环
E. i<=n-j
以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序。
typedef struct
{ int key;
……
}NODE;
void selsort(NODE a[],int n)
{
int i,j,k;
NODE temp;
for( i=1; i<= ___(1)_____; i++)
{
k=i;
for( j=i+1;j<= _(2)_ _ _; j++)
if(a[j].key<a[k].key) (3)_____ _;
if( i!=k)
{
temp=a[i];
(4)___ __;
(5)__ __;
}
}
}
【答案选项】
A. n
B. a[i]=a[k]
C. k=j
D. a[k]=temp
E. n-1