首页 > 软考

网友您好，请在下方输入框内输入要搜索的题目：

请输入或粘贴题目内容搜题

搜题

拍照、语音搜题，请扫码下载APP

题目内容（请给出正确答案）

[主观题]

●试题一阅读下列算法说明和算法，将应填入（n)处的语句写在答题纸的对应栏内。【说明】为了减少

●试题一

阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。

【说明】

为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。

【算法】

1．变量声明

X：DataType

i，j，low，high，mid，R0..n

2．每循环一次插入一个R［i］

循环：i以1为步长，从2到n，反复执行

①准备

X＜-R［i］； (1) ；high＜-i-1；

②找插入位置

循环：当 (2) 时，反复执行

(3)

若X．key＜R［mid］．key

则high＜-mid-1

否则 (4)

③后移

循环：j以-1为步长，从 (5) ，反复执行

R［j+1］＜-R［j］

④插入

R［low］＜-X

3．算法结束

答案

查看答案

发布时间：2020-10-01

更多“●试题一阅读下列算法说明和算法，将应填入（n)处的语句写在答题纸的对应栏内。【说明】为了减少”相关的问题

第1题

●试题一阅读以下算法说明和流程图，回答问题1和问题2。【算法说明】下面是一段插入排序的程序，

●试题一

阅读以下算法说明和流程图，回答问题1和问题2。

【算法说明】

下面是一段插入排序的程序，将R[k+1]插入到R[1…k]的适当位置。 R[0]=R[k+1]； j=k；

while (R[j]＞R[0])

{

R[j+1]=R[j]； j--；

}

R[j+1]=R[0]；

【流程图】

●试题一阅读以下算法说明和流程图，回答问题1和问题2。【算法说明】下面是一段插入排序的程序，●

【测试用例设计】

(while循环次数为0、1、2次)

●试题一阅读以下算法说明和流程图，回答问题1和问题2。【算法说明】下面是一段插入排序的程序，●

【问题1】

指出算法的流程图中 (1) ～ (3) 处的内容。

【问题2】

指出测试用例设计中 (4) ～ (9) 处的内容。

点击查看答案

第2题

●试题四阅读下列函数说明和C代码，将应填入（n)处的字句写在答题纸的对应栏内。【说明】函数Qui

●试题四

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

函数QuickSort是在一维数组A［n］上进行快速排序的递归算法。

【函数】

void QuickSort(int A［］，int s，int t)

{int i=s，j=t+1，temp；

int x=A［s］；

do{

do i＋＋；while (1) ；

do j--；while(A［j］＞x)；

if(i＜j){temp=A［i］； (2) ； (3) ；}

}while(i＜j)；

A［a］=A［j］；A［j］=x；

if(s＜i-1) (4) ；

if(j+1＜t) (5) ；

}

点击查看答案

第3题

●试题一阅读下列说明和流程图，将应填入（n)的语句写在答题纸的对应栏内。【流程图】图1 下

●试题一

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

【流程图】

●试题一阅读下列说明和流程图，将应填入（n)的语句写在答题纸的对应栏内。【流程图】图1 下●试

图1

下面的流程图描述了对16位二进制整数求补的算法。计算过程是：从二进制数的低位(最右位)开始，依次向高位逐位查看，直到首次遇到"1"时，停止查看。然后，对该"1"位左面的更高位(如果有的话)，逐位求反，所得的结果就是对原二进制数求补的结果。

例如：对二进制整数10111001 10101000求补的结果是01000110 01011000。

设16位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的BIT［1］～BIT［16］中。例如，二进制整数10111001 10101000存放在数组BIT后，就有BIT1［1］=0，BIT［2］=0，……，BIT［15］=0，BIT［16］=1。

流程图(如图1所示)中 (1) 处按"循环变量名：循环初值，增量，循环终值"格式描述。若流程图中存在空操作，则用NOP表示。

点击查看答案

第4题

●试题一阅读下列算法说明和算法，将应填入（n)处的字句写在答题纸的对应栏内。【算法说明】为便

●试题一

阅读下列算法说明和算法，将应填入(n)处的字句写在答题纸的对应栏内。

【算法说明】

为便于描述屏幕上每个像素的位置，在屏幕上建立平面直角坐标系。屏幕左上角的像素设为原点，水平向右方向设为X轴，垂直向下方向设为Y轴。

设某种显示器的像素为128×128，即在每条水平线和每条垂直线上都有128个像素。这样，屏幕上的每个像素可用坐标(x，y)来描述其位置，其中x和y都是整数，0≤x≤127，0≤y≤127。

现用一维数组MAP来存储整个一屏显示的位图信息。数组的每个元素有16位二进位，其中每位对应一个像素，"1"表示该像素"亮"，"0"表示该像素"暗"。数组MAP的各个元素与屏幕上的像素相对应后，其位置可排列如下：

MAP(0)，MAP (1) ，…，MAP (7)

MAP (8) ，MAP (9) ，…，MAP (15)

MAP(1016)，MAP(1017)，…，MAP(1023)

下述算法可根据用户要求，将指定坐标(x，y)上的像素置为"亮"或"暗"。

在该算法中，变量X，Y，V，S，K都是16位无符号的二进制整数。数组BIT中的每个元素BIT(K)(K=0，...，15)的值是左起第K位为1，其余位均为0的16位无符号二进制整数，即BIT(K)的值为215-k。

【算法】

第1步根据用户指定像素的位置坐标(x，y)，算出该像素的位置所属的数组元素MAP(V)。这一步的具体实现过程如下：

1.将x送变量X，将y送变量Y；

2.将Y左移 (1) 位，仍存入变量Y；

3.将X右移 (2) 位，并存入变量S；

4.计算Y+S，存入变量V，得到像素的位置所属的数组元素MAP(V)。

第2步算出指定像素在MAP(V)中所对应的位置K(K=0，…，15)。这一步的具体实现过程如下：将变量X与二进制数 (3) 进行逻辑乘运算，并存入变量K。

第3步根据用户要求将数组元素MAP(V)左起第K位设置为"1"或"0"。这一步的具体实现过程如下：

1.为把指定像素置"亮"，应将MAP(V)与BIT(K)进行逻辑 (4) 运算，并存入MAP(V)。

2.为把指定像素置"暗"，应先将BIT(K)各位取反，再将MAP(V)与BIT(K)进行逻辑 (5) 运算，并存入MAP(V)。

点击查看答案

第5题

●试题二阅读下列函数说明和C代码，将应填入（n)处的字句写在答题纸的对应栏内。【说明】函数pri

●试题二

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

函数print(BinTreeNode*t；DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。

【函数】

void print(BinTreeNode*t；DateType ＆x){

stack ST；int i，top；top=0；∥置空栈

while(t!=NULL ＆＆t-＞data!=x‖top!=0)

{while(t!=NULL ＆＆ t-＞data!=x)

{

∥寻找值为x的结点

(1) ；

ST［top］．ptr=t；

ST［top］．tag=0；

(2) ；

}

if(t!=Null ＆＆ t-＞data==x){∥找到值为x的结点

for(i=1； (3) ；i＋＋)

printf("％d"，ST［top］．ptr-＞data)；}

else{

while((4) )

top--；

if(top＞0)

{

ST［top］．tag=1；

(5) ；

}

}

}

点击查看答案

第6题

试题一（共 15分）阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。[说明]假设

试题一（共 15分）

阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。

[说明]

假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j)处的颜色，颜色值为0到k 的整数。下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同的上、下、左、右可连通的点组成同色邻接区域。

例如，一幅8×9 像素的图像如图1-1 所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方 (4,5)、右方(3,6)邻接点的颜色值都为0，因此这些点属于点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点（见图1-1 中的阴影部分）。将上述同色区域的颜色替换为颜色值7所得的新图像如图1-2 所示。

试题一（共 15分）阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。[说明]假设

[算法]

输入：矩阵 G，点的坐标(i0,j0)，新颜色值newcolor。

输出：点(i0,j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。

算法步骤(为规范算法，规定该算法只在第七步后结束)：

第一步：若点(i0,j0)的颜色值与新颜色值newcolor相同,则(1) ；

第二步：点(i0,j0)的颜色值→oldcolor；创建栈S，并将点坐标(i0,j0)入栈；

第三步：若 (2) ，则转第七步；

第四步：栈顶元素出栈→(x,y)，并(3) ；

第五步：1) 若点(x,y-1)在图像中且G[x,y-1]等于oldcolor，则(x,y-1)入栈S；

2) 若点(x,y+1)在图像中且G[x,y+1]等于oldcolor，则(x,y+1)入栈S；

3) 若点(x-1,y)在图像中且G[x-1,y]等于oldcolor，则(x-1,y)入栈S；

4) 若点(x+1,y)在图像中且G[x+1,y]等于oldcolor，则(x+1,y)入栈S；

第六步：转 (4) ；

第七步：算法结束。

[问题]

是否可以将算法中的栈换成队列？回答： (5) 。

点击查看答案

第7题

试题四（共15分）阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】模式匹

试题四（共15分）

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。

如果匹配成功，返回s在t中的位置，否则返回-1 。

KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：

1．在串t和串s中，分别设比较的起始下标i=J=O

2．如果串t和串s都还有字符，则循环执行下列操作：

（1）如果j=-l或者t[i]-s[j]，则将i和j分别加1，继续比较t和s的下一个字符；

（2）否则，将j向右滑动到next[j]的位置，即j =next[J]

3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回一1．

其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。

【C代码】

（1）常量和变量说明

t，s：长度为悯铂Is的字符串

next:next数组，长度为Is

（2）C程序

include ＜stdio．h＞

nclude ＜stdliB．h＞

include ＜string．h＞

／*求next【】的值*/

void get_next（int *next, char *s, int Is） {

int i=0，j=-1；

next[0]=-1；/*初始化next[0]*／

while（i＜ ils）{/*还有字符*／

if（j=-1l ls[i]=s[j]）{／*匹配*／

j++；

i++；

if（s[i]一s[jl）

next [i]- next[j];

else

Next[i]=j；

}

else

J= next[j]；

}

}

int kmp（int *next, char *t ,char *s, int.lt, int Is ）

{

inti= 0,j =0 ;

while （i＜lt && （1 ） {

if（j=-1 II 2_） {

i++ ;

j ++ ;

} else

（3） :

}

if （j＞= ls）

Retum （4）

else .

retum-1；

【问题1】（8分）

根据题干说明，填充C代码中的空（1）～（4）.

【问题2】（2分）

根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）(主串和子的长度分别为It和Is，用O符号表示）。

【问题3】（5分）

根据C代码，字符串“BBABBCAC”的next数组元素值为（6） (直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC则函数Kmp的返回值是（7）

点击查看答案

第8题

●试题一阅读下列说明和流程图，将应填入（n)的字句写在答题纸的对应栏内。【说明】下列流程图（

●试题一

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

【说明】

下列流程图(如图4所示)用泰勒(Taylor)展开式

sinx=x-x3／3!+x5／5!-x7／7!+…+(-1)n×x 2n+1／(2n+1)!+…

【流程图】

●试题一阅读下列说明和流程图，将应填入（n)的字句写在答题纸的对应栏内。【说明】下列流程图（●

图4

计算并打印sinx的近似值。其中用ε(＞0)表示误差要求。

点击查看答案

第9题

试题四（共15 分）阅读下列说明和C代码，回答问题 1 至问题3，将解答写在答题纸的对应栏内。【说明】

试题四（共15 分）

阅读下列说明和C代码，回答问题 1 至问题3，将解答写在答题纸的对应栏内。

【说明】

某应用中需要对100000 个整数元素进行排序，每个元素的取值在 0～5 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x的元素个数(记为m)，将 x放在输出元素序列的第m 个位置。对于元素值重复的情况，依次放入第 m-l、m-2、…个位置。例如，如果元素值小于等于4 的元素个数有 10 个，其中元素值等于 4 的元素个数有3个，则 4 应该在输出元素序列的第10 个位置、第 9 个位置和第8 个位置上。

算法具体的步骤为：

步骤1：统计每个元素值的个数。

步骤2：统计小于等于每个元素值的个数。

步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。

【C代码】

下面是该排序算法的C语言实现。

(1)常量和变量说明

R:常量，定义元素取值范围中的取值个数，如上述应用中 R值应取6i：循环变量

n：待排序元素个数

a：输入数组，长度为n

b：输出数组，长度为n

c：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。

(2)函数sort

1 void sort(int n,int a[ ]，intb[ ]){

2 int c[R]，i；

3 for (i=0；i＜ (1) ；i++){

4 c[i]=0；

5 }

6 for(i=0；i＜n；i++）{

7 c[a[i]] = (2) ；

8 }

9 for(i=1；i＜R；i++）{

10 c[i]= （3）；

11 }

12 for(i=0；i＜n；i++）{

13 b[c[a[i]]-1]= (4) ；

14 c[a[i]]=c[a[i] ]-1；

15 }

16 }

【问题1】（8 分）

根据说明和C代码，填充 C代码中的空缺(1)～(4)。

【问题2】（4 分）

根据C代码，函数的时间复杂度和空间复杂度分别为 (5) 和 (6) （用 O符号

表示）。

【问题3】（3 分）

根据以上C代码，分析该排序算法是否稳定。若稳定，请简要说明（不超过 100 字）；

若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。

从下列的2 道试题（试题五和试题六）中任选 1 道解答。

如果解答的试题数超过道，则题号小的道解答有效。

点击查看答案

第10题

阅读下列算法说明和流程图，将应填入（n)处的字句写在对应栏内。【算法说明】本算法按照算符优先关

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

【算法说明】

本算法按照算符优先关系，实现对算术四则混合运算表达式(可含小括号)的求值。处理对象是以字符串形式给出的、语法正确且不含变量的整数表达式。

算符优先关系见表5.1(§1，§2为按顺序出现的两个运算符)

阅读下列算法说明和流程图，将应填入（n)处的字句写在对应栏内。【算法说明】本算法按照算符优先关阅

说明：“”是假设的表达式开始符和结束符，不可用。

为实现算法，使用了两个堆栈分别寄存运算符和运算数(中间结果值)。算法基本思路如下：首先置操作数栈S1为空，表达式起始符“”设为运算符栈S2的栈底元素；依次读入表达式的各符号，若是数字字符则连接在一起转换为int型操作数进S1栈；若是运算符§2，则和S2栈的栈顶运算符51比较优先级后作相应操作，直至整个表达式求值结束。算法流程图5.1如下：

阅读下列算法说明和流程图，将应填入（n)处的字句写在对应栏内。【算法说明】本算法按照算符优先关阅

【问题】请将流程图补充完整。

点击查看答案

账号：尚未登录

登录没有账号？去注册

购买搜题卡

考试指南全部 >

2024年甘肃人力资源考试倒计时：5天备考攻略，助你轻松应战！人力资源管理师所报名费详解及报名流程 2024年教师资格证认定需要什么材料？教师资格证幼儿园面试考试科目自考大专人力资源管理有哪些科目人力资源二级证书属于什么职称 2024上半年教资面试真题及答案小学语文 2024上半年甘肃中小学教师资格考试面试报名入口：http://ntce.neea.edu.cn 人力资源管理师属于什么行业教师资格考试面试成绩查询

下载APP

关注公众号

TOP