|
|
|
|
知识点：
sizeof
内存
排列
排序
数组
|
|
|
|
|
|
|
|
|
【说明】
规定整型数组a中的元素取值范围为[0, N)，函数usrSort(int n, int a[])对非负整型数组a的前n个元素进行计数排序。排序时，用temp_arr[i]表示i在数组a中出现的次数，因此可以从0开始按顺序统计每个非负整数在a中的出现次数，然后对这些非负整数按照从小到大的顺序，结合其出现次数依次排列。
例如，对含有10个元素{0,8,5,2,0,1,4,2,0,1}的数组a[]排序时,先计算出有3个0、2 个1、2个2、1个4、1个5和1个8,然后可确定排序后a的内容为{0,0,0,1,1,2,2,4,5,8}。
下面代码中用到的memset函数的原型如下，其功能是将p所指内存区的n个字节都设置为ch的值。
void * memset(void*p,int ch, size_t n);
【c代码】
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 101
void printArr(int a[],int n);
void usrSort(int n,int a[]);
int main()
{
int a[10]={0,8,5,2,0,1,4,2,0,1};
printArr(a,sizeof(a)/sizeof(int));
(1) ； //调用usrSort ()对数组a进行升序排序
printArr(a,sizeof(a)/sizeof(int));
return 0;
}
void printArr(int a[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ”，a[i]);
printf(”\n”);
}
void usrSort (int n, int a [])
{
int i, k;
int *temp_arr; //用temp_arr [i]表示i在a中出现的次数
temp_arr=(int *)malloc(N * sizeof(int));
if (!temp_arr)return;
//将所申请并由temp_arr指向的内存区域清零
memset ( (2));
for(i=0; i<n; i++)
temp_arr [ (3) ] ++;
k=0;
for (i=0; i<N; i++){
int cnt; //cnt表示i在数组a中的出现次数
(4) ;
while(cnt > 0){
a[k]=i; //将i放入数组a的适当位置
(5) ;
cnt-;
}
}
free(temp_arr);
}
|
|
|
问题：3.1
（共15分）
阅读以下说明和C代码，填写程序中的空缺，将解答写入答题纸的对应栏内。
|
|
|
|
|
|
|
|
| |
|
为保障您的权益，请登录
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
sizeof用于计算表达式或数据类型的字节数，其运算结果与系统相关。例如，对于下面的数组定义，可用“sizeof（a）/sizeof（int）”计算出数组a的元素个数为7。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
除了CPU，内存也是影响系统性能的最常见的瓶颈之一。看系统内存是否够用的一个重要参考就是分页文件的数目，分页文件是硬盘上的真实文件，当操作系统缺少物理内存时，它就会把内存中的数据挪到分页文件中去，如果单位时间内此类文件使用频繁（每秒个数大于5）,那就应该考虑增加内存。具体考察内存的性能的参数包括内存利用率、物理内存和虚拟内存的大小。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
设S为具有n个不同元素的n元集，从S中选取r个元素且考虑其顺序称为S的一个r排列，不同排列的总数记为 ，有时也用P(n，r)表示。如果r=n，则称这个排列为S的全排列。从排列的定义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序也必须完全相同。
|
|
|
|
|
|
例子1：用0～9这十个数字，可以组成多少个没有重复数字的三位数？
|
|
|
解法1：由于百位数上的数字不能为0，因此可先考虑排百位上的数字，再排十位和个位上的数字。百位数上的数字只能从除0以外的1～9数字中任选一个，有 种；十位和个位上的数字，可以从余下的9个数字中任选两个，有 种。根据乘法原理，所求的三位数的个数是 。
|
|
|
解法2：可先考虑从0～9这十个数字中任取三个数字的排列数（ ），再减去其中以0开头的排列数（ ）。因此，所求的三位数的个数是 。
|
|
|
解法3：符合条件的三位数可以分为三类：每一位数字都不是0的三位数有 个；个位数是0的三位数有 个；十位数是0的三位数有 个。根据加法原理，符合条件的三位数个数是 。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设含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］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
|
|
|
|
|
|
|
|
Am*n=［［a11a12…a1n］［a21a22…a2n］…［am1am2…amn］］
|
|
|
|
|
|
Am*n=［［a11a21…am1］［a12a22…am2］…［a1na2n…amn］］
|
|
|
|
|
|
（1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
|
|
|
|
|
|
（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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
