阅读下列说明和流程图,填补流程图中的空缺(1)~(9),将解答填入答题纸的对应栏内。【说明】假设数组A中的各元素A⑴,A (2),…,A (M)已经按从小到大排序(M>1):数组B中的各元素B(1) , B (2) . B (N)也已经按从小到大排序(N≥1)。执行下面的流程图后,可以将数组A与数组B中所有的元素全都存入数组C中,且按从小到大排序(注意:序列中相同的数全部保留并不计排列顺序)。例

题目
阅读下列说明和流程图,填补流程图中的空缺(1)~(9),将解答填入答题纸的对应栏内。【说明】假设数组A中的各元素A⑴,A (2),…,A (M)已经按从小到大排序(M>1):数组B中的各元素B(1) , B (2) . B (N)也已经按从小到大排序(N≥1)。执行下面的流程图后,可以将数组A与数组B中所有的元素全都存入数组C中,且按从小到大排序(注意:序列中相同的数全部保留并不计排列顺序)。例如,设数组A中有元素: 2,5,6,7,9;数组B中有元素: 2,3,4,7;则数组C中将有元素: 2,2,3,4,5,6,7,7,9.

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

阅读下列说明、流程图和算法,将应填(n)处的字句写在对应栏内。

[说明]

下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A[i],并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为 low,上界为high,数组中的元素互不相同。例如,对数组(4,2,8,3,6),以4为基准数的划分过程如下:

[流程图]

[算法说明]

将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数int p(int A[],int low,int hieh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。

[算法]

void sort(int A[],int L,int H) {

if (L<H) {

k=p(A,L,R); //p()返回基准数在数组A中的下标

sort((4)); //小于基准敷的元素排序

sort((5)); //大于基准数的元素排序

}

}


正确答案:(1)j--(2)i++(3)A[i]←pivot或[j]←pivot(4) ALk-1或ALk (5)Ak+1H或AkH
(1)j--(2)i++(3)A[i]←pivot或[j]←pivot(4) A,L,k-1或A,L,k (5)A,k+1,H或A,k,H 解析:题目考查快速排序算法。快速排序采用了一种分治的策略,通常称为分治法。其基本思想是:将原问题分解为若干个规模更小,但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的具体过程为:第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为基准,将所有记录分成2组,第一组各记录的排序码都小于等于该排序码,第二组各记录的排序码都大于该排序码,并把该记录排在这2组中间,这个过程称为一次划分。第二步,采用同样的方法,对划分出来的2组元素分别进行快速排序,直到所有记录都排到相应的位置为止。
在进行一次划分时,若选定以第一个元素为基准,就可将第一个元素备份在变量pivot中,如图中的第①步所示。这样基准元素在数组中占据的位置就空闲出来了,因此下一步就从后向前扫描。如图中的第②步所示,找到一个比基准元素小的元素时为止,将其前移,如图中的第③步所示。然后再从前向后扫描,如图中的第④步所示,找到一个比基准元素大的元素时为止,将其后移,如图中的第⑤步所示。这样,从后向前扫描和从前向后扫描交替进行,直到扫描到同一个位置为止,如图中的第⑥步所示。
由题目中给出的流程图可知,以第一个元素作为基准数,并将A[low]备份至pivot,i用于从前向后扫描的位置指示器,其初值为low, j用于从后往前扫描的位置指示器,其初值为high。当i1)从后向前扫描数组A,在ipivot,就继续向前扫描(j--);如果被扫描的元素A[i]2)这时,再从前向后扫描,在ipivot就停止扫描,并将此元素的值赋给目前空闲着的A[j]。
3)这时又接第(1)步,直到i>j时退出循环。退出循环时,将pivot赋给当前的A[i](A[i]←pivot)。
递归函数的目的是执行一系列调用,直到到达某一点时递归终止。为了保证递归函数正常执行,应该遵守下面的规则:
1)每当一个递归函数被调用时,程序首先应该检查基本的条件是否满足,例如,某个参数的值等于0,如果是这种情形,函数应停止递归。
2)每次当函数被递归调用时,传递给函数一个或多个参数,应该以某种方式变得“更简单”,即这些参数应该逐渐靠近上述基本条件。例如,一个正整数在每次递归调用时会逐渐变小,以至最终其值到达0。
本题中,递归函数sort(int A[],int L, int H)有3个参数,分别表示数组A及其下界和上界。根据流程图可知,这里的L相当于流程图中的i,这里的H相当于流程图中的j。因为P()返回基准数所在数组A中的下标,也就是流程图中最后的“A[i]←pivot”中的i。根据快速排序算法,在第一趟排序后找出了基准数所在数组A中的下标,然后以该基准数为界(基准数在数组中的下标为k),把数组A分成2组,分别是A[L,…,k-1)和A[k+1,…,H),最后对这2组中的元素再使用同样的方法进行快速排序。

第2题:

阅读以下算法说明,根据要求回答问题1~问题3。

[说明]

快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。

1.分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。

2.递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。

3.合并:快速排序在原地排序,故无需合并操作。

下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。

A:待排序数组

p,r:数组元素下标,从p到r

q:划分的位置

x:枢轴元素

i:整型变量,用于描述数组下标。下标小于或等于i的元素的值,小于或等于枢轴元素的值

j:循环控制变量,表示数组元素下标


正确答案:这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进其基本思想是:通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分即PARTITION操作:根据枢轴元素的值把一个较大的数组分成两个较小的子数组一个子数组的所有元素的值小于等于枢轴元素的值一个子数组的所有元素的值大于枢轴元素的值而子数组内的元素不排序。划分时以最后一个元素为枢轴元素从左到右依次访问数组的每一个元素判断其与枢轴元素的大小关系并进行元素的交换如图2-30所示。 在[问题1]所给出的伪代码中当for循环结束后A[p..i]中的值应小于等于枢轴元素值x而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素因此A[r]与A[i+1]进行交换得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置因此返回值为i+l。
这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进,其基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分,即PARTITION操作:根据枢轴元素的值,把一个较大的数组分成两个较小的子数组,一个子数组的所有元素的值小于等于枢轴元素的值,一个子数组的所有元素的值大于枢轴元素的值,而子数组内的元素不排序。划分时,以最后一个元素为枢轴元素,从左到右依次访问数组的每一个元素,判断其与枢轴元素的大小关系,并进行元素的交换,如图2-30所示。 在[问题1]所给出的伪代码中,当for循环结束后,A[p..i]中的值应小于等于枢轴元素值x,而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素,因此A[r]与A[i+1]进行交换,得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置,因此返回值为i+l。

第3题:

阅读下列说明和流程图,将应填入(n)处的语句写在对应栏内。

【说明】

下列流程图用于从数组K中找出一切满足:K(I)+K(J)=M的元素对(K(I),K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列,M是给定的常数。

【流程图】

此流程图1中,比较“K(I)+K(J):M”最少执行次数约为(5)。


正确答案:(1) (2) (3)I+1->I (4)J-1->J (5)[N/2]
(1) (2) (3)I+1->I (4)J-1->J (5)[N/2] 解析:该算法的思路是:设置了两个变量I和J,初始时分别指向数组K的第一个元素和最后一个元素。如果这两个元素之和等于M时,输出结果,并这两个指针都向中间移动;如果小于M,则将指针I向中间移动(因为数组K已按从小到大的顺序排列);如果大于M,则将指针J向中间移动(因为数组K已按从小到大的顺序排列)。当IJ时,说明所有的元素都搜索完毕,退出循环。
根据上面的分析,(1)、(2)空要求填写循环结束条件,显然,(1)空处应填写“”,(2)空处应填写“”。这里主要要注意I=J的情况,当I=J时,说明指两个指针指向同一元素,应当退出循环。
(3)空在流程图有两处,一处是当K(I)+K(J)=M时,另一处是当K(I)+K(J)M时,根据上面分析这两种情况都要将指针I向中间移动,即“I+1->I”。同样的道理,(4)空处应填写“J-1->J”。
比较“K(I)+K(J):M”最少执行次数发生在第1元素与第N个元素之和等于M、第2元素与第N-1个元素之和等于M、……,这样每次比较,两种指针都向中间移动,因此最小执行次数约为“N-2”。

第4题:

阅读以下说明和流程图将应填入(n)处的字句写在答题纸的对应栏内

【说明】

在一个矩阵中如果其零元素的个数远远多于其非零元素的个数时称这样的矩阵为稀疏矩阵稀疏矩阵通常采用三元组数组表示每个非零元素用一个三元组来表示即非零元素的行号列号和它的值然后按某种顺序将全部非零元素的三元组存于一个数组中例如对于以下二维数组

其中三元数组a的第行元素的值分别存储稀疏矩阵x的行数列数和非零元素的个数

下面的流程图描述了稀疏矩阵转换的过程

【流程图】


答案:


解析:


本题考查程序流程图及数组的操作



结合流程图中三个判断语句的结构和作用来分析第(5)空应该是i++它的作用是保证能取到稀疏矩阵中每一行的元素

第5题:

阅读下列说明和流程图,将应填入(n)处的语句写在对应栏内。

【说明】

有数组A(4,4),把1到16个整数分别按顺序放入A(1,1),…,A(1,4),A(2,1),…,A(2,4),A(3,1),…,A(3,4),A(4,1),…,A(4,4)中,下面的流程图用来获取数据并求出两条对角线元素之积。

【流程图】


正确答案:(1)141 (2)141 (3)1 (4)s×A[ii] (5)s×A[5-ii]
(1)1,4,1 (2)1,4,1 (3)1 (4)s×A[i,i] (5)s×A[5-i,i] 解析:本题考查用程序流程图描述数组及求对角线的和。
题目要求把1到16个整数分别按顺序放入A(1,1),…,A(1,4),A(2,1),…,A(2,4), A(3,1),…,A(3,4),A(4,1),…,A(4,4)中,那么数组中的元素刚好构成一个方阵,用流程图求出这个方阵的对角线之积。下面来具体分析流程图。
第(1)空与第(2)空应该结合起来完成,它们都是一个循环判断语句的条件,从图中可以看出,如果这两个条件都成立,则读出当前数组中的元素值,根据题目要求,数组中的元素个数是每行4个每列4个,那么循环的上界应该是4,而下标是从1开始的,因此这两个空答案为1,4,1。
第(3)空是一个赋值语句,给变量s赋一个初值,从图中后面的语句不难看出s中存放的是求积的结果,那么在求积以前,s的值应该为1,因此此空答案为1。
第(4)空也是一个赋值语句,是在循环条件判断语句下,我们已经知道变量s中存放的是每次求积的结果,那么此空很明显是用来求积的,用当前取到的对角线元素乘以变量s中存放的值,因此此空答案为s×A[i,i]。
第(5)空和上一空非常相似,但它是用来求另外一条对角线的积的,它也是在一个循环下来实现的,这条对角线的元素位置与上面那条具有对称的特点,因此此空答案为s×A[5-i,i]。

第6题:

阅读以下说明和流程图,回答问题将解答填入对应栏。

[说明]

本流程图采用“双向冒泡法”实现对数组a[n]的排序。双向冒泡法就是在逐步缩小的数组内,分别从数组的两端开始向内搜索,同时将大数往上浮,小数往下沉,每次交换一组数。flag是一个标志,发生过交换就置为1,当这个循环过程都不再发生交换时,则数组排序完成。

注:流程中循环开始的说明按照“循环变量:循环初值,循环终值,增量”格式描述;

定义swAP[a,b]为将a和b两数交换。

[问题]

将流程图的(1)~(5)处补充完整。


正确答案:(1) leftright&&flag==l; (2) leftright-11; (3) a[i]>a[i+1]; (4) flag=1; (5) a[Right-i]a[Right-i-1]
(1) leftright&&flag==l; (2) left,right-1,1; (3) a[i]>a[i+1]; (4) flag=1; (5) a[Right-i]a[Right-i-1] 解析:本题目考查的是流程图。
先题目中已经给出算法说明,是分别从数组的两端同时向内搜索,每次交换一组数,所以,可以判断,(1)中的条件应该由两部分组成,首先是leftright,因为这样才能构成一个数组,第二个条件是flag==1,如果它成立,则说明还有交换,要继续排序,如果flag==0,则说明没有交换了,排序完成,所以(1)要填入“leftright&&fla==1”。内循环开始,从数组两端,两两比较数的大小,所以(2)应填入“left,right-1,1”,在left端,当a[i]>a[i+1]时,将两数交换,交换后将flag置1,即(3)填入“a[i]>a[i+1]”,(4)填入“flag=1”;在right端,当a[Right-i]a[Right-i-1]时,将两数交换,flag置1,所以(5)应填入“a[Right-i]a[Right-i-1]”。

第7题:

阅读以下说明和流程图,填补流程图中的空缺(1)~(9),将解答填入对应栏内。

【说明】

假设数组A中的各元素A(1),A(2),…,A(M)已经按从小到大排序(M≥1);数组B中的各元素B(1),B(2),…,B(N)也已经按从小到大排序(N≥1)。执行下面的流程图后,可以将数组A与数组B中所有的元素全都存入数组C中,且按从小到大排序 (注意:序列中相同的数全部保留并不计排列顺序)。例如,设数组A中有元素:2,5, 6,7,9;数组B中有元素2,3,4,7:则数组C中将有元素:2,2,3,4,5,6,7, 7, 9。

【流程图】


正确答案:(1)1 (2)A(i) (3)B(j) (4)i (5)j (6)B(j) (7)A(i) (8)j (9)i
(1)1 (2)A(i) (3)B(j) (4)i (5)j (6)B(j) (7)A(i) (8)j (9)i 解析:这是最常见的一种合并排序方法。为对较大的序列进行排序,先将其分割成容量相当的几个部分,分别进行排序,最后再合并在一起。当然,这些排序要么都是升序,要么都是降序。本题全部是按升序排序的。
例如,为了将整副扑克牌按升序进行排序,先将其分割成两个部分(数量大致相当),对每个部分完成升序排序后,就形成了两叠已排序的牌。如何将其合并呢?办法如下。
每次都比较各叠最上面的两张牌,取出比较小的,放入新堆,再继续比较。直到其中一堆空了,就将另一堆剩余的牌逐张放入新堆。新堆就是合并后的已完成排序的序列。
在数据排序时,遇到相同的数比较时,任取一个就可以了。
对本题来说,i、j、k是数组A、B、C的下标,初始时,都应该是1。因此,空(1)处应填写1。
将A(i)与B(j)进行比较后,如果A(i)≤B(j),那么应该将A(i)→C(k)。这是升序的要求。因此,空(2)处应填A(i)。如果A(i)>B(j),则应将B(j)→C (k)。因此,空(3)处应填B(j)。
在A(i)→C(k)后,i应增加1,为下次取A(i)再比较做准备(k也需要增加1,为下次存入C(k)做准备)。这时,需要比较数组A是否已经取完,即判断i>M是否成立。如果i>M,则表示数组A中的元素已经全部取出,需要将数组B中剩余的元素逐个移入C(k)。因此,空(4)处应填i,空(6)处应填B(j)。数组B处的元素何时移完呢?这就需要判断i>N是否成立。因此,空(8)处应填j。
同样,空(3)处将B(j)存入C(k),直到,j>N时数组B中的元素取完。此时,需要将数组A中剩余的元素逐个移入C(k),直到i>M时全部完成。因此,空(5)处应填j,空(7)处应填A(i),空(9)处应填i。

第8题:

阅读以下说明和流程图,回答问题将解答填入对应栏。

[说明]

本流程图实现采用递归函数来求一个整数数组中从元素0到元素n中的最小值。该算法思想是这样的,首先我们假设有一个求数组中最小元素的函数,然后,在求某一具有n的元素的数组的最小值时,只要求将前n-1的元素的最小值与第n个元素比较即可。不断地重复这一过程,直到数组中只剩下一个元素,那么它必定是最小值。

注:int min(int X,int y)为返回两数中最小数的函数。

int minInArray(int a[],int n)为返回数组中最小数的函数。

minA为数组中最小值。

[问题l]

将流程图的(1)~(4)处补充完整。

[问题2]

min()函数的定义为(5)。


正确答案:(1) minInArray(an); (2) 1; (3) minA=a[n-1]; (4) minA=min(minInArray(an-1)a[n]); (5) xy?x:y;
(1) minInArray(a,n); (2) 1; (3) minA=a[n-1]; (4) minA=min(minInArray(a,n-1),a[n]); (5) xy?x:y; 解析:本题目考查流程图。
题目是利用递归来求数组中的最小值,则一定是反复的调用一个求数组最小值的函数,直到比较数组中最后只剩下两个数,则(1)中填入的应是“minlnArray(a,n)”,然后,判断n的值是否为1,如果是,则说明数组中只有一个数,则它一定就是最小值,可以直接输出,所以(2)应填入“1”,(3)应填入“minA=a[n]”;如果n的值不是1,则说明要继续递归,则再次调用求数组最小值的函数,把数组前n-1项的最小值同第n项做比较,所以(4)填入“minA=min(minInArray(a,n-1),a[n])”,由于min()是一个比较函数,返回两数中较小的数,我们可以用三元运算符直接定义为x y?x:y。

第9题:

阅读下列说明、流程图和算法,将应填入(n)处的字句写在对应栏内。

【流程图说明】

下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法;以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于Array[i],并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为low,上界为high,数组中的元素互不相同。

【算法说明】

将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数int p(int Array[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[],int L,int H)的功能是实现数组Array中元素的递增排序。

【算法】

void sort(int Array[],int L,int H){

if (L<H) {

k=p(Array,L,H);/*p()返回基准数在数组Array中的下标*/

sort((4));/*小于基准数的元素排序*/

sort((5));/*大于基准数的元素排序*/

}

}


正确答案:(1)j←j-1
(1)j←j-1

第10题:

阅读下列说明和流程图,将应填入(n)处的语句写在对应栏内。

【说明】

设学生(学生数少于50人)某次考试的成绩按学号顺序逐行存放于某文件中,文件以单行句点“.”为结束符。下面的流程图用于读取该文件,并把全部成绩从高到低排序到数组B[50]中。

【流程图】


正确答案:(1)B[0]←a (2)i←0 (3)a="." (4)aB[j] (5)j--
(1)B[0]←a (2)i←0 (3)a="." (4)aB[j] (5)j-- 解析:本题考查用程序流程图来描述排序。
题目要求将文件中学生的成绩读出,并把全部成绩从高到低排序到数组B[50]中。这里面涉及两个问题,第一是从文件中读数,文件中的数据是以单行句点“.”为结束符的,在未读到此符号前,应该将继续取数据。第二是排序,每取到一个学生的成绩都要与数组的学生成绩比较,按照从高到低的顺序在数组中找到合适的位置存放。下面来具体分析流程图。
第(1)空在条件判断为假的情况下执行流程中,如果条件为假说明从文件中取到的数据是学生成绩。从程序流程图中可以看到,从文件中读的数据存放在变量a中,而此空是第一次取数据,应该存放数组B的第一个位置,因此此空答案为B[0]←a。
第(2)空是紧接着第(1)空来的,在上面已经把从文件中读到的第一个数存放到了数组中,接下来应该处理数组的下标问题,从后面的流程中可以推断出变量i是存放数组当前下标的,而且没有初值,那么此空的任务应该是用来给变量i赋一个初值,而对数组的操作应该从头开始,因此此空答案为i←0。
第(3)空是循环的判断条件,如果条件成立则结束,在这之前又对文件进行了一次读数,根据我们上面的分析只有在读到了结束符时程序才结束,那么此空肯定是判断从文件中读到的数据是否为结束符,因此此空答案为a="."?。
第(4)空也是一个循环的判断条件,如果条件成立,则将取到的数存放到数组的当前下标位置;如果不成立,则循环找到合适的位置再存放。从这里我们不难推断出,流程图中是将从文件取到的成绩与当前数组中的最小成绩进行比较的,而当前数组中的最小成绩存放在位置j中,因此此空答案为aB[i]?。
第(5)空在循环体中,这个循环的作用是为当前从文件中读到的成绩在已经排好序的数组元素中找到合适的位置,找到了就要插入,数组中的元素是按从大到小排列的,在查找合适位置时是从后往前依次比较,因此此空的任务应该是将数组的下标往前移动,所以此空答案为“i--”。

更多相关问题