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

[主观题]

如果对于某个n值,n后问题无解,则算法将陷入死循环.（1)证明或否定下述论断:对于n≥4,n后问题有解.（2)是否存在正数δ,使得对所有n≥4算法成功的概率至少是δ？

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“如果对于某个n值,n后问题无解,则算法将陷入死循环.（1)证…”相关的问题

第1题

试题四（共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 道解答。

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

点击查看答案

第2题

在某个算法时间复杂度递归式T（n)=T（n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（），若

在某个算法时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（），若问题的规模增加了16倍，则运行时间增加（）倍。

A.Θ(n) B.Θ(nlgn) C.Θ(n2) D.Θ(n2lgn) A.16 B.64 C.256 D.1024

点击查看答案

第3题

●CSMA（载波监听多路访问)控制策略中有三种坚持退避算法，其中一种是"一旦介质空闲就发送数据，假如

●CSMA(载波监听多路访问)控制策略中有三种坚持退避算法，其中一种是"一旦介质空闲就发送数据，假如介质是忙的，则继续监听，直到介质空闲后立即发送数据；如果有冲突就退避，然后再尝试"这种退避算法称为 (37) 算法。这种算法的主要特点是 (38) 。

CSMA/CD在CSMA的基础上增加了冲突检测功能。网络中的某个发送站点一旦检测到冲突，它就立即停止发送，并发送一个冲突码，其他站点都会 (39) 。如果站点发送时间为1，任意两个站之间的传播延迟为t，若能正常检测到冲突，对于基带总线网络，t的值应为 (40) ；对于宽带总线网络，t的值应为 (41) 。

(37) A．I-坚持CSMA

B．非坚持CSMA

C．P-坚持CSMA

D．O-坚持CSMA

(38) A．介质利用率低，但可以有效避免冲突

B．介质利用率高，但无法避免冲突

C．介质利用率低，且无法避免冲突

D．介质利用率高，且可以有效避免冲突

(39) A．处于待发送状态

B．相继竞争发送权

C．接收到阻塞信号

D．有可能继续发送数据

(40) A．t≤0.5

B．t＞0.5

C．t≥1

D．0.5＜t＜1

(41) A．t＞0.25

B．t≥0.5

C．t≤0.25

D．0.25＜t＜0.5

点击查看答案

第4题

CSMA（载波监听多路访问)控制策略中有3种坚持退避算法，其中一种是：“一旦介质空闲就发送数据，假如

CSMA(载波监听多路访问)控制策略中有3种坚持退避算法，其中一种是：“一旦介质空闲就发送数据，假如介质是忙的，继续监听，直到介质空闲后立即发送数据；如果有冲突就退避，然后再监听”这种退避算法称为(36)算法。这种算法的主要特点是(37)。

CSMA/CD在CSMA的基础上增加了冲突检测功能。网络中的某个发送站点一旦检测到冲突，它就立即停止发送，并发冲突码，其他站点都会(38)。如果站点发送时间为1，任意两个站之间的传播延迟为t，若能正常检测到冲突，对于基带总线网络，t的值应为(39)；对于宽带总线网络，t的值应为(40)。

A．I-坚持CSMA

B．非坚持CSMA

C．P-坚持CSMA

D．O-坚持CSMA

点击查看答案

第5题

阅读以下某旅馆客房管理系统的算法说明和程序流程图，根据要求回答问题1～问题4。 [算法说明] 某旅

阅读以下某旅馆客房管理系统的算法说明和程序流程图，根据要求回答问题1～问题4。

[算法说明]

某旅馆共有N间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED和 STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(占用)。客房是以房间(不是床位)为单位出租的。

程序流程图(见图6-21)所反映的算法是，根据几个散客的要求预订一间空房。程序的输入为：人数M，房间等级要求 R(R=0表示任意等级都可以)。程序的输出为：所有可供选择的房间号。

在程序流程图(见图6-21)中，若要某个房间I被选中，则需要满足什么条件？

点击查看答案

第6题

问题描述:设磁盘上有n个文件每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是且磁头从

问题描述:设磁盘上有n个文件每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是且磁头从当前磁道移到被检信息磁道所需的时间可用这两个磁道之间的径向距离来度量.如果文件fi存放在第i(1≤i≤n)道上,则检索这n个文件的期望时间是.式中,d(i,j)是第i道与第j道之间的径向距离|i-j|.

磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置,使期望检索时间达到最小.试设计一个解此问题的算法,并分析算法的正确性与计算复杂性.

算法设计:对于给定的文件检索概率,计算磁盘文件的最优存储方案.

数据输入:由文件input.txt给出输入数据.第1行是正整数n,表示文件个数.第2行有n个正整数a,表示文件的检索概率.实际上第k个文件的检索概率应为

结果输出:将计算的最小期望检索时间输出到文件output.txt.

点击查看答案

第7题

问题描述:设I是一个n位十进制整数.如果将I划分为k段,则可得到k个整数.这k个整数的乘积称为I的

一个k乘积.试设计一个算法,对于给定的I和k,求出I的最大k乘积.

算法设计:对于给定的I和k,计算I的最大k乘积.

数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).

结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.

点击查看答案

第8题

问题描述:给定一个赋权无向图G=（V,E),每个顶点都有权值w（v).如果,且对任意（u,V)∈E有u∈U或v∈U,

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

点击查看答案

第9题

试题一（共 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 所示。