免费智能真题库 > 历年试卷 > 程序员 > 2019年上半年 程序员 下午试卷 案例
  第2题      
  知识点：   排序   数组

 
【说明】
函数bubbleSort(int arr[]，int n， int（*compare）（int，int））的功能是根据调用时传递的比较函数compare对数组arr的前n个元素进行排序。
【C代码】
#define swap(a, b) { a = a^b; b = a^b; a = a^b;} //交换a与b的值
int less(int x，int y)
{
return ((x<y) ? 1 : 0)；
}
int larger(int x，int y)
{
return ((x>y) ? 1 : 0)；
}

void bubbleSort(int arr[ ]，int n，int (*compare)(int，int))
{ int i，j；
int swapped=1，
for(i=0；swapped；i++) {
swapped=0;
for(j=0；j<n-l-i；j++)
if (compare( arr[j+1]，arr[j])) {
swap(arr[j+1]，arr[j])；
swapped=1；
}
}
}
 
问题：2.1   设有如下数组定义：
int data1[ ]={4，2，6，3，1};
int data2[ ]={4，2，6，3，1};
int data3[ ]={4，2，6，3，1};
请分别给出下面的函数调用执行后，数组data1、data2和data3各自的元素序列。
(1)bubbleSort(data1，5，less)；
(2) bubbleSort(data2，5，larger)；
(3) bubbleSort(data3，3，larger)；
 
 
 

   知识点讲解    
   · 排序    · 数组
 
       排序
        假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
 
       数组
               数组的定义及基本运算
               一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               设有n维数组A［b1，b2，…，bn］，其每一维的下界都为1，bi是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j1，j2，…，jn］（1≤ji≤bi）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。
               以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表：
               Am*n=［［a11a12…a1n］［a21a22…a2n］…［am1am2…amn］］
               也可将A看作列向量形式的线性表：
               Am*n=［［a11a21…am1］［a12a22…am2］…［a1na2n…amn］］
               数组结构的特点如下：
               （1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
               （2）数据元素具有相同的类型。
               （3）数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作：
               （1）取值操作。给定一组下标，读其对应的数据元素。
               （2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（i-1）×n+（j-1））×L
               同理，以列为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（j-l）×m+（i-1））×L
   题号导航      2019年上半年 程序员 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第2题    在手机中做本题