数据结构试卷3数组和广义表

题目部分，(卷面共有95题,608.0分,各大题标有题量和总分)

一、单项选择题(22小题,共44.0分) (2分)[1]

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 A、 13 B、 33 C、 18 D、 40 (2分)[2]

二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,?,8,列下标j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9] (2分)[3]

已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =

A、（a） B、 A C、 a D、（b） E、 b F、(A)

(2分)[4]

下面说法不正确的是

A、 广义表的表头总是一个广义表 B、 广义表的表尾总是一个广义表 C、 广义表难以用顺序存储结构 D、 广义表可以是一个多层次的结构 (2分)[5]

设广义表L=（（a,b,c）），则L的长度和深度分别为

A、 1和1 B、 1和3 C、 1和2 D、 2和3 (2分)[6] 广义表（（a,b,c,d））的表头是（ ），表尾是 A、 a B、b C、（a,b,c,d） D、（b,c,d） (2分)[7]

广义表运算式Tail(((a,b),(c,d)))的操作结果是

A、 (c,d) B、 c,d C、 ((c,d)) D、 d (2分)[8]

已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是 A、 head(tail(LS)) B、 tail(head(LS))

C、 head(tail(head(tail(LS))) D、 head(tail(tail(head(LS)))) (2分)[9]

对稀疏矩阵进行压缩存储目的是

A、便于进行矩阵运算 B、便于输入和输出 C、节省存储空间 D、降低运算的时间复杂度 (2分)[10]

数组A[0..4,-1..-3,5..7]中含有元素的个数

A、 55 B、 45 C、 36 D、 16 (2分)[11]

设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为 A、（i-1）*n+j B、（i-1）*n+j-1 C、 i*（j-1） D、 j*m+i-1

(2分)[12]

A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是

A、 i（i-1）/2+j B、 j（j-1）/2+i C、 i（j-i）/2+1 D、 j（i-1）/2+1 (2分)[13]

广义表A=(a，b，(c，d)，(e，(f,g)))，则下面式子的值为 Head(Tail(Head(Tail(Tail(A))))) A、(g) B、(d) C、c D、d (2分)[14]

对于以行为主序的存储结构来说．在数组A[c1..d1,c2..d2]中，c1和d1分别为数组A的第一维下标的下、上界，c2和d2分别为第二维下标的下、上界．每个数据元素占k个存储单元，二维数组中任一元素a[i,j]的存储位置可由（ ）确定。 A、 Loc[i,j]=[(d2-c2+1)(i-c1)+(j-c2)] ×k

B、 Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)] ×k C、 Loc[i,j]=A[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)] ×k D、 Loc[i,j]=Loc[0,0]+[(d2-c2+1)(i-c1)+(j-c2)] ×k

(2分)[15]

二维数组A的每个元素是由6个字符组成的串，其行下标i=0、1、?、8．列下标i=1、2、? 、10。若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A、 A[8，5] B、 A[3，10] C、 A[5，8] D、 A[0，9] (2分)[16]

若广义表A满足Head(A)=Tail(A)，则A为 A、() B、(()) C、((),()) D、(()，()，()) (2分)[17]

将一个Ａ［l．． 100,1...100］的三角矩阵，按行优先存入一维数组B[1... 298]中，A中素(即该元素下标i=66，j=65)在B数组中的位置k为 A、198 B、195 C、197 (2分)[18]

已知广义表L=（（x,y,z）,a,(u,t,w)）,从L表中取出原子项t的运算是 A、 head(tail(tail(L))) B 、tail(head(head(tail(L)))) C、 head(tail(head(tail(L)))) D、 head(tail(head(tail(tail(L))))) (2分)[19]

设有一个10阶的对称矩阵A，采用压缩破除计方式，以行序为主存储，a1,1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8,5的地址为。 A、13 B、33 C、18 D、40

(2分)[20]

用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为。

A、j=r[j].next B、 j=j+1 C、 j=j->next D、 j=r[j]-> next

(2分)[21]

稀疏矩阵一般的压缩存储方法有两种，即。 A、 二维数组和三维数组 B、 三元组和散列

C、 三元组和十字链表 D、 散列和十字链表 (2分)[22]

数组的基本操作主要包括 。

A、 建立与删除 B、 索引与修改 C、 访问与修改 D、 访问与索引 二、算法设计题(35小题,共449.0分) (10分)[1]

给定一个整数数组b[0..N-1]，6中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。 (12分)[2]

给定有m个整数的递增有序数组a[l..m]和有n个整数的递减有序数组b[l..n]，试写出算法将数组a和b归并为递增有序数组c[1..m+n]。(要求算法的时间复杂度为o(m+n)

(12分)[3]

试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表如下形式输入（a1,a2,a3?,含空格字符的空表。

(10分)[4]

设有大小不等的n个数据组(n个数据组中数据的总数为m )顺序存放在空间区D内，每个数据占据一个存储单元。数据组的首地址由数组S给出(如下图所示)，试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。

）n>==0,其中

或为单字母表示的原子或为广义表，n=0时为只

(15分)[5]

试设计一个不带回溯的稀疏矩阵(用三元组表存储)转置算法

(18分)[6] 编写子程序，将一维数组A[1：n×n](n≤10)中的元素．按蛇形方式存放在一维数组B[1：n,1:n]中。

B（1，1）=A（1）， B（1，2）=A（2），B（2，1）=A（3），

B（3，1）=A（4） B（2，2）=A（5），B（1，3）=A（６）， ．．．．．．

依此类推，如下图所示。

(12分)[7]

设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。 (15分)[8]

试设计一 个算法，将数组A[0? n-1]中的元素循环右移k行．并要求只用一个元素大小的存储空间，元素移动或交换的次数为0(n)

(18分)[9]

试设计一算法，输入一个有m行n列的整数矩阵,然后将每一行的元素按非递减次序输出 例如，若输入 4 3 5 6 2 9 8 1 2 8 7 1 2 3 8 则输出： 2 3 4 5 6 l 2 8 8 9 1 2 3 7 8 (21分)[10]

已知A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组A中的最大整数。 (2) 求n个整数的和。 (3) 求n个整数的平均值。 (15分)[11]

假设稀疏矩阵A 和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A，B之外的附加空间，你的算法能否达到Ｏ(m+n)的时间复杂度？其中m和n分别为矩阵A，B中非零元的数目。 (20分)[12]

假设稀疏矩阵A 和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

(15分)[13]

若将稀疏矩阵A的非零元素以行序为主序的顺序存于一维数组V中，并用二维数组B表示A中的相应元素是否为零元素（以0和1分别表示零元素和非零元素）。

试写一算法，实现在上述表示法中实现矩阵相加的运算。并分析你的算法的时间复杂度。 (10分)[14]

试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。 (16分)[15]

三元组顺序表的另一种变型是，不存矩阵元素的行、列下标，而存非零元在矩阵中以行为主序时排列的顺序号，即在LOC(0,0)=1, l=1时按教科书5.2节中公式(5-2)计算出的值。试写一算法，由矩阵元素的小标值i,j求元素的值。

(10分)[16]

试编写算法，依次从左至右输出广义表中第l层的原子项。 (10分)[17]

试编写递归算法，逆转广义表中的数据元素。 (9分)[18]

试编写递归算法，输出广义表中所有原子项及其所在层次。 (10分)[19]

试编写判别两个广义表是否相等的递归算法。 (21分)[20]

已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： (1) 求链表中的最大整数。 (2) 求链表的结点个数。 (3) 求所有整数的平均值。 (14分)[21]

设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第2行，?。第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提示：用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j+1列。) (12分)[22]

【背包问题】设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w[1], w[2], ?, w[n]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此背包问题的递归定义如下：）

(18分)[23]

已知Ackerman函数定义如下：

(1) 根据定义，写出它的递归求解算法； (2) 利用栈，写出它的非递归求解算法。

(14分)[24]

编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 (10分)[25]

设整数x1,x2,?,xN已存放在数组A中，编写一PASCAL递归过程，输出从这n个数中取出所有k 个数的所有组合（k<=n）。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321。 类似本题的另外叙述有：

（1）题目基本相同，只是叙述不同，要求用PASCAL语言。 (10分)[26]

设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。 (9分)[27]

设数组A[1..n]中，A[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计一个算法使A[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。

(8分)[28]

广义表GL=(a1,a2 ,?,an),其中 ak(k=1,2,...,n)或是单个数据元素（原子），或仍然是个广义表。给定如下有关广义表的类型定义： TYPE tagtype=0..1; glist=^gnode;

gnode=RECORD

link:glist; {link 域指向下一个结点}

CASE tag:tagtype OF ｛tag=0 表示原子结点｝ 0: (data :integer); 1:(sublist: glist) END;

编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表(3,(2,4,5),(6,3）) 数据域之和为23。 (9分)[29]

试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,?,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。(注:算法可用类pascal 或类c书写) (12分)[30]

二项式(a+b)n展开式的系数为

C（n，0）=1，C（n，n）=1，对于n>=0

C（n，k）=C（n-1，k）+C（n-1，k-1），对于0

(3)试写一个非递归算法，既不用数组也不用栈，对于任意的0<=k<=n计算C(n,k)

(10分)[31]

设二维数组a[1..m, 1..n] 含有m*n 个整数。

(1) 写出算法(pascal过程或c函数)：判断a中所有元素是否互不相同?输出相关信息(yes/no)；

(2) 试分析算法的时间复杂度。

(10分)[32]

给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。 类似本题的另外叙述有：

（1）给定整型数组B[0..m,0..n] 。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n.。

(2) 给定n×m矩阵A[a..b,c..d]，并设A[i,j]<=A[i,j+1]（a<=i<=b,c<=j<=d-1）知A[i,j]<=A[i+1,j],(a<=i<=b-1, c<=j<=d)。设计一算法以比O(n*m)小的最坏时间复杂性判定值x是否在A中。

(12分)[33]

请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 (10分)[34]

设原来将N个自然数1,2,?,N按某个顺序存于数组A中，经过下面的语句计算，使A[I]的值变为A[1]到A[I-1]中小于原A[I]值的个数。 FOR I:=N DOWNTO 1 DO BEGIN

C：=0；

FOR J：=1 TO I-1 DO IF A[J]

编程将经过上述处理后的A还原成原来的A。 (12分)[35]

广义表是n(n>=0)个数据元素a1,a2,a3,?,an的有限序列。其中ai (1<=i<=n)或者是单个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和子表元素结点，为了将两者统一，用了一个标志tag，当其为0时表示是原子结点，其data域存储结

点值，link域指向下一个结点，当其tag为1时表示是子表结点，其sublist为指向子表的指针。因此，广义表可采用如下结构存储： TYPE glist=^gnode; gnode=RECORD link:glist; CASE tag:0..1 OF 0:(data:char); 1:(sublist:glist) END;

（1）画出广义表((a,b),c)的存储结构；

（2）写出计算一个广义表的原子结点个数的递归算法表示式； （3）编写实现上述算法的过程或函数程序。 三、填空题(38小题,共115.0分) (1分)[1]

对矩阵压缩是为了_______。 (2分)[2]

所谓稀疏矩阵指的是_______。 (6分)[3]

n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t存储时，t的长度为 ，当i=j，a[i][j]=t[(2)],i>j,a[i][j]=t[ ],i

设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。 (6分)[5]

设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （l） 存放该数组至少需要的单元数是_______;

（2） 存放数组的第8列的所有元素至少需要的单元数是_______; （3） 数组按列存储时，元素A[5,8]的起始地址是_______。 (2分)[6]

用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第 行，第 列的元素。

(2分)[7]

假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=_______。（注：矩阵元素下标从1开始） (3分)[8]

设下三角矩阵 如果按行序为主序将下三角元素Ai j (i,j)存储在一个一维数组B[ 1..n(n+1)/2]中，对任一个三角矩阵元素Aij ,它在数组B中的下标为_______。 (1分)[9]

将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。

(2分)[10]

设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为 ;若以列序为主序顺序存储，则元素a[45,68]的存储地址为 。 (2分)[11]

设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为 ；如按列优先顺序存储,则元素A[-18,-25]的存储地址为 。 (2分)[12]

数组的存储结构采用_______存储方式。 (4分)[13]

已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。 (3分)[14]

设某广义表H=（A，（a,b,c）） ，运用head函数和tail函数求出广义表H中某元素b的运算式_______。

(6分)[15]

约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1—n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去 ，直到所有的人都出圈为止。

PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer); BEGIN

FOR i:= 1 TO n DO A[i]:=i; sl:=s;

FOR i:=n DOWNTO 2 DO

BEGIN sl:= (1)_____；//计算出圈人s1 IF sl=0 THEN (2)____； w:=A[sl]; //A[s1]出圈

FOR j:=_(3)___ DO A[j]:=A[j+1]; A[i]:=w; END;

write('出圈序列为：’)；//输出出圈序列 FOR i :=n DOWNTO 1 DO write(A[i]); writeln ； END;

(10分)[16]

完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面的程序将数列1,2,3,?,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即 (示意图编者略)。 （a）算法的PASCAL 语言程序描述（编者略）：（b）算法的C语言程序描述： #define NMAX 10

#include “stdio.h” main()

{ int i,j,n,k,p,q,m;

int a [NMAX][NMAX]; scanf(“%d”,&n); m=1;

for(k=1；(1)_____；k++) {if（k

for（i=1；i<=n;i++） { for（j=1；j<=n；j++）

printf（“M”,a[i][j]）;printf(“\\n”); } } }

(8分)[17]

已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4,6,8,15，则执行如下所示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,c的长度分别为l=5,m=4,n=9请在程序中方框内填入正确的成分，完成上述要求。 PROCEDURE sort;

VAR i, j, k, x: integer; d: ARRAY[1..m] OF integer; BEGIN

FOR i:=1 TO m DO d[i]:=(1)__________; i:=1; j:=1; k:=1;

WHILE (i<=l) AND (j<=m) DO BEGIN

IF a[i]>d[j] THEN BEGIN(2)___; (3)___END ELSE BEGIN (4)__; (5)___END; c[k]:=x;_(6)___ END; WHILE(7)____DO

BEGIN c[k]:=a[i]; k:=k+1; i:=i+1；END; WHILE(8)____DO

BEGIN c[k]:=d[j]; k:=k+1; j:=j+1；END; END. {sort} (2分)[18]

已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_______。 (4分)[19]

上三角矩阵压缩的下标对应关系为：_______。

Pot[i]=pot[i-1]+pot[i];

For(i=1;i<=a[0][2]; i++)/*对a中的每一个非零元素按pot数组的位置转置到b中*/ { col=a[i][1]; q=pot[col]; b[q][0]=a[i][1]; b[q][1]=a[i][0]; b[q][2]=a[i][2]; pot[col]=pot[col]+1; } } } (18分)[6]

答案题目的要求，是将Ａ的元素，从Ｂ的左上角开始，沿着与B的副对角线平行的各条对角线，接蛇形存放于B中。本题的难点有两点， 一个是对于副对角线及其以上部分，与它以下部分的处理方法是不同的：另一个则是从左下到右上的赋值与从右上到左下的赋值交替出现．也需设法拄制。注意到自左上角起，Ｂ中第ｋ条对角线上的元素，当ｋ≤n时，其纵、横坐标之和等于ｋ－l：当k>n时，由于第ｋ条对角线与第2ｎ－ｋ条对角线关于副对角线对称，它上面元素的纵、横坐标，等于该元素关于副对角线对称的无素的纵、横坐标各加ｎ－（２ｎ－ｋ）。 那么由以下特点，可以考虑从Ｂ的左上角开始，逐条处理这总共2ｎ－１条对角线（即每一次完成对一条对角线的赋值)，在对某条对角线上元素赋值的时候，要注意赋值的方向(从左下到右上还是从右上到左下)。由此可得算法一。此外也可以采用不同的控制手段来实现，例如算法二所示，但具思路实质上仍然是从左上角开始逐条对平行于副对角线的各条对角线进行相应的赋值操作。 算法一：

PROCEDURE yh(A：ARRAy［1．．．n＊ｎ］OF integer; VAR B：ARRAY[l..n，l..n】OF integer); VAR

i,j n, k，L，LL，m：integer;

{ k用于指示从左上角开始，第k条与副对角线平行的对角线} BEGIN

M:=1;

FOR k：=lt0 2*n-1 DO BEGIN

If k

ELSE LL:=2*n-k;

{k

BEGIN

IF (k MOD 2<>0) THEN {由k的奇偶性来控制对该对角线的赋值的方向} BEGIN

i:=LL-L+1 j:=i END ELSE

BEGIN i:=L; j:=LL- L+1 END

If(k>=n)THEN BEGIN

I:=i+n-LL J:=j+n-LL END B[i,j]:=A[m]; m:=m+1 END END END; 算法二

Void Store(){

//本算法用类c语言描述，

//为符合题目条件，A中的0号单元以及B中的第0行与第0列均未用 Int m,i,j,k，a;//k记录已经完成赋值的元素个数，a的正负控制赋值的方向 For(m=1,a=1,k=1;m<=n;m++){//对副对角线及其以上的部分赋值 if（a>0）{//a>0时从左下到右上赋值

i=m;j=1;

while(j<=m){B[i][j]=A[k];i++;j++;k++}∥完成对一条对角线的赋值 }//if else{

i=1；j=m；

while(j<=n){B[i][j]=A[k];i--;j++;k++;} }//if Else{ a=-a

}//for

For(m=2;m<=n;m++){//对副对角线以下的部分赋值 If(a>0){ I=n;j=m;

While(j<=n){B[i][j]=A[k];i--;j++;k++;} }//if Else{

I=m;j=n;

While(i<=n){B[i][j]=A[k];i++;j--;k++;} }//else a=-a; }//for }//store (12分)[7]

答案算法中可以使用两个下标变量i和j分别指向数组的开头和末尾元素，并都向数组的中间进行搜索：

(1)若A[i]为偶数、A[j]为奇数，则A[i]与A[j]进行交换，且i++;j--; (2)若A[i]为偶数、A[j]为偶数；则i保持不变，j--; (3)若A[i]为奇数、A[j]为奇数．则j保持不变，i++; (4)若A[i]为奇数、A[j]为偶数，则i++;j--; (5)当i=j时，算法结束。 void charge(int A[n]) {int i,j,c; i=0; j=n-1 while(i

{while(A[i]!=0)&&(i

while(A[j]%2==0)&&(i

if(i

(15分)[8]

答案本题的难点存在对算法的时间复杂度和空间复杂度均提出了较高的要求，但仍有多种解法，下面提供三种。一种思路是：由于每个元素，跟与它相距rxk位的元素形成了一 个“循环链”，由此便想到通过逐个处理这样的“循环链”来实现算法，本算法每次均使一个或两个元素到达指定位置，因此设置一个计数变量，用于统计当前已经到位的元素个数，当计数变量为n时说明全部元素都已到位，可结束算法；另一种思路是：当n和k的晟大公约数为P时，分别以A[0]、A[1]、?A[p-1]为“循环链”起点执行与第一种思路类似的算法，可以保证数组中每一个元素都被且仅被右移一次；还有一种思路则是先逆转前n-k个元素，再逆转后k个元素，最后逆转整个序列，同样可以达到目的。 解法一：

Void ElentMove(intA[n]，int k){

for(i=0，i

//t指向当前需要到位的元素(在链头)，s指向它应到的位置

; //使“循环链”上的一个记录到位，该位置上原有记录变换到链头处 R++；j+++; s=(t+r*k)%n

if(t==s){t++; r=1；i++; }

//若本次交换使两个记录到位，应补充计数，且需要下一 “循环链”

}for／／每执行一次循环体都至少使一个记录到位，当有n个记录到位后算法结束 }ElemMove／／ 解法二：

Void ElemMove(Int A[n]，Int k){ for(i=l；i<=k;i++)

If(n%i==0&&k%i==0) p=I;//求n和k的最大公约数p For(i=0;i

J=I;m=(i+k)%n;temp=A[i]; While (m!=i){

A[j]=temp;temp=A[m];A[m]=A[j];j=m;m=(j+k)%n; }while // 循环右移一步 A[i]=temp; }for//

}ElemMove//

解法三：

Void ElemMove(int A[n]，int k){ for(i=0；i<(n-k)/2;i++){

temp=A[i];A[i]=A[n-k-1-i]=temp; }for//逆转前n-k个元素

for(i=1ength—k;i<=2*length-k-1)/2;i++){

j=i-(length-k);temp=A[i];A[i]=A[length-1-j]; A[length-1-j]=temp; for／／逆转后k个元素 for(i=0；i

(18分)[9]

答案本题实质上是一道考查内部排序的题目，只不过需要排序的序列有m个而已。其算法思路如下：对矩阵的m行逐行进行处理对于其中的每一行，采用选择法进行排序。每次令当前最小元素到位的同时将其输出。 Void ElemSort(int A[m][n]){

For(i=0;i<[m；i++){∥处理第i行 for(j=0；j

for(min=j,k=j+1;k if(j!=min){A[i][j] A[i][min];printf(“%d”,A[i][j];)} }//for Printf(“\\n”); }//for }//ElemSort

(21分)[10]

答案 #include

class RecurveArray { //数组类声明 private:

int *Elements; //数组指针

int ArraySize; //数组尺寸

int CurrentSize; //当前已有数组元素个数 public :

RecurveArray ( int MaxSize =10 ) :

ArraySize ( MaxSize ), Elements ( new int[MaxSize] ){ } ~RecurveArray ( ) { delete [ ] Elements; } void InputArray(); //输入数组的内容 int MaxKey ( int n ); //求最大值 int Sum ( int n ); //求数组元素之和

float Average ( int n ); //求数组元素的平均值 };

void RecurveArray :: InputArray ( ){ //输入数组的内容 cout << \

for ( int i = 0; i < ArraySize; i++ ) cin >> Elements[i]; }

int RecurveArray :: MaxKey ( int n ) { //递归求最大值 if ( n == 1 ) return Elements[0]; int temp = MaxKey ( n - 1 );

if ( Elements[n-1] > temp ) return Elements[n-1]; else return temp;

}

int RecurveArray :: Sum ( int n ) { //递归求数组之和 if ( n == 1) return Elements[0];

else return Elements[n-1] + Sum (n-1); }

float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float) Elements[0];

else return ( (float) Elements[n-1] + ( n - 1) * Average ( n - 1 ) ) / n; }

int main ( int argc, char* argv [ ] ) { int size = -1;

cout << \while ( size < 1 ) cin >> size; RecurveArray ra ( size );

ra.InputArray();

cout<< \ cout<< \cout<< \return 0;

本文来源：https://www.bwwdw.com/article/mk38.html