免费智能真题库 > 历年试卷 > 程序员 > 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维数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
               设有n维数组Ab1b2,…,bn],其每一维的下界都为1,bi是第i维的上界。从数据结构的逻辑关系角度来看,A中的每个元素Aj1j2,…,jn](1≤jibi)都被n个关系所约束。在每个关系中,除第一个和最后一个元素外,其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言,这n个关系仍是线性的。
               以下面的二维数组Am][n]为例,可以把它看成是一个定长的线性表,它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表:
               Am*n=[[a11a12a1n][a21a22a2n]…[am1am2amn]]
               也可将A看作列向量形式的线性表:
               Am*n=[[a11a21am1][a12a22am2]…[a1na2namn]]
               数组结构的特点如下:
               (1)数据元素数目固定。一旦定义了一个数组结构,就不再有元素的增减变化。
               (2)数据元素具有相同的类型。
               (3)数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作:
               (1)取值操作。给定一组下标,读其对应的数据元素。
               (2)赋值操作。给定一组下标,存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上,在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是,不能对数组进行整体的运算,只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算,也就是说,一旦定义了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
               对于数组,一旦确定了它的维数和各维的长度,便可为它分配存储空间。反之,只要给出一组下标便可求得相应数组元素的存储位置,也就是说,在数据的顺序存储结构中,数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序(按行存储)和以列为主序(按列存储)两种方法,如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元,mn为数组的行数和列数,那么以行为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((i-1)×n+(j-1))×L
               同理,以列为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((j-l)×m+(i-1))×L
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。


 题号导航      2019年上半年 程序员 下午试卷 案例   本试卷我的完整做题情况 
1 /
2 /
3 /
4 /
5 /
6 /
 
↓第2题