首页
试卷库
试题库
当前位置：
X题卡
>
所有题目
>
题目详情
语音信号的带宽为300～3400Hz，量化精度为8位，单声道输出，则每秒钟的数据量至少为（）。
查看本题答案
包含此试题的试卷
中级软件设计师《相同项单选集》真题及答案
点击查看
你可能感兴趣的试题
人们说话所产生的语音信号经过数字化之后才能由计算机进行存储传输和处理语音信号的带宽大约为300～34
8kHz和8bit
8kHz和16bit
16kHz和8bit
16kHz和16bit
人们说话所产生的语音信息必须经过数字化之后由计算机进行存储和处理语音信号的带宽通常为300~3400
若语音信号的带宽为50～400Hz采样频率为50kHz量化精度为8位双声道计算2小时的数据量为52
2880MB
360MB
720MB
45MB
人们说话时发出的语音信号必须经过数字化才能由计算机进行存储处理和传输语音信号的带宽为300～3400
230MB
115MB
461MB
29MB
对带宽为300~3400Hz的语音若采样频率为8kHz.量化位数为8位.单声道 则其未压缩时的码率约
64kb/s
64kB/s
128kb/s
128kB/s
人们说话所产生的语音信息必须经过数字化之后才能由计算机进行存储和处理语音信号的带宽通常为300～34
64KB
32KB
128KB
8KB
人们说话所产生的语音信息必须经过数字化之后才能由计算机进行存储和处理语音信号的带宽通常为300～34
64KB
32KB
128KB
8KB
人们说话时发出的语音信号必须经过数字化才能由计算机进行存储处理和传输语音信号的带宽为300-3400
230MB
115MB
461 MB
29MB
若语音信号的带宽为50～400Hz采样频率为50kHz量化精度为8位双声道计算2小时的数据量为___
2880MB
360MB
720MB
45MB
语音信号的带宽为300～3400Hz采用频率为8kHz量化精度为8位单声道输出则每秒钟的数据量为
3KB
4KB
6KB
8KB
设语音信号的采样频率为16kHz量化精度为10位单声道输出则每小时的数据量约为______MB
160
80
68.66
9.37
声音信号的带宽通常为300～3400Hz量化精度为8b单声道输出那么每小时传输的数据量约为_____
11MB
14MB
28MB
56MB
人们说话所产生的语音信息必须经过数字化之后才能由计算机进行存储和处理语音信号的带宽通常为300～34
8KB
16KB
64KB
256KB
人们说话所产生的语音信息必须经过数字化之后才能由计算机进行存储和处理语音信号的带宽通常为300Hz～
64KB
32KB
128KB
8KB
人们说话所产生的语音信息必须经过数字化之后由计算机进行存储和处理语音信号的带宽通常为300～3400
语音信号的带宽通常为300Hz～3400Hz若采样频率为10kHz8bit量化经过数字化之后每秒钟产
64kb
80kb
100kb
78kb
热门试题
更多
阅读下列说明回答问题1和问题2将解答填入对应栏内 [说明] 0-1背包问题可以描述为有n个物品i=12…n第i个物品价值为vi重量为wivi和wi为非负数背包容量为WW为非负数选择其中一些物品装入背包使装入背包物品的总价值最大即且总重量不超过背包容量即其中xi∈01xi=0表示第i个物品不放入背包xi=1表示第i个物品放入背包 [问题1] 用回溯法求解此0-1背包问题请填充伪代码中的空缺1～4 回溯法是一种系统的搜索方法在确定解空间后回溯法从根结点开始按照深度优先策略遍历解空间树搜索满足约束条件的解对每一个当前结点若扩展该结点已经不满足约束条件则不再继续扩展为了进一步提高算法的搜索效率往往需要设计一个限界函数判断并剪枝那些即使扩展了也不能得到最优解的结点现在假设已经设计了BOUNDvwkw函数其中vwk和W分别表示当前已经获得的价值当前背包的重量已经确定是否选择的物品数和背包的总容量对应于搜索树中的某个结点该函数值表示确定了部分物品是否选择之后对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值若该价值小于等于当前已经得到的最优解则该结点无须再扩展 下面给出0-1背包问题的回溯算法伪代码 函数参数说明如下 W背包容量n物品个数w重量数组v价值数组fw获得最大价值时背包的重量fp背包获得的最大价值X问题的最优解 变量说明如下 cw当前的背包重量cp当前获得的价值k当前考虑的物品编号Y当前已获得的部分解 BKNAPWnwvfwfpX 1cw←cp←0 21 3fp←-1 4Whiletrue 5whilek≤nandcw+w[k]≤Wdo 62 7cp←cp+v[k] 8Y[k]←1 9k←k+1 10ifk＞nthen 11iffp＜cpthen 12fp←cp 13fw←cw 14k←n 15X←Y 16elseYk←0 17whileBOUNDcpcwkW≤fpdo 18whilek≠0andYk≠1do 193 20ifk=0thenreturn 21Y[k]←0 22cw←cw←w[k] 23cp←cp←v[k] 244 [问题2] 考虑表21-3所示的实例假设有3个物品背包容量为22图21-12是根据上述算法构造的搜索树其中结点的编号表示搜索树生成的顺序边上的数字I/O分别表示选择/不选择对应物品除了根结点之外每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值为获得最优解应该选择物品5获得的价值为6 对于表21-3所示的实例若采用穷举法搜索整个解空间则搜索树的结点数为7而采用上述的回溯法搜索树的结点数为8 8处填
阅读下列说明回答问题1和问题2将解答填入对应栏内 [说明] 现需要在某城市中选择一个社区建一个大型超市使该城市的其他社区到该超市的距离总和最小用图模型表示该城市的地图其中顶点表示社区边表示社区间的路线边上的权重表示该路线的长度 现设计一个算法来找到该大型超市的最佳位置即在给定图中选择一个顶点使该顶点到其他各顶点的最短路径之和最小首先算法需要求出每个顶点到其他任一顶点的最短路径即需要计算任意两个顶点之间的最短路径然后对每个顶点计算其他各顶点到该顶点的最短路径之和最后选择最短路径之和最小的顶点作为建大型超市的最佳位置 [问题1] 本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径已知图G的顶点集合为V=12…nW=Wijn*n为权重矩阵 设为从顶点i到顶点j的一条最短路径的权重 当k=0时不存在中间顶点因此当k＞0时该最短路径上所有的中间顶点均属于集合12…k 若中间顶点包括顶点k则若中间顶点不包括顶点k则 于是得到如下递归式 因为对于任意路径所有的中间顶点都在集合12…n内因此矩阵给出了任意两个顶点之间的最短路径即对所有ij∈V表示顶点i到顶点j的最短路径 下面是求解该问题的伪代码请填充其中的空缺1～6 伪代码中的主要变量说明如下 W权重矩阵 n图的顶点个数 SP最短路径权重之和数组SP[i]表示顶点i到其他各顶点的最短路径权重之和i取值为1～n min_SP最小的最短路径权重之和 min_v具有最小的最短路径权重之和的顶点 i循环控制变量 j循环控制变量 k循环控制变量 LOCATE-SHCPPINGNALLWn 1D0=W 2for1 3fori=1ton 4forj=1ton 5if 62 7else 83 9fori=1ton 10SP[i]=0 11forj=1ton 124 13min_SP=SP[1] 145 15fori=2ton 16ifmin_SP＞SP[i] 17min_SP=SP[i] 18min_v=i 19return6 [问题2] 问题1中伪代码的时间复杂度为7用O符号表示 2处填
设计模式117将抽象部分与其实现部分相分离使它们都可以独立地变化图5-10为该设计模式的类图其中118用于定义实现部分的接口 117处填
阅读下列说明回答问题1和问题2将解答填入对应栏内 [说明] 0-1背包问题可以描述为有n个物品i=12…n第i个物品价值为vi重量为wivi和wi为非负数背包容量为WW为非负数选择其中一些物品装入背包使装入背包物品的总价值最大即且总重量不超过背包容量即其中xi∈01xi=0表示第i个物品不放入背包xi=1表示第i个物品放入背包 [问题1] 用回溯法求解此0-1背包问题请填充伪代码中的空缺1～4 回溯法是一种系统的搜索方法在确定解空间后回溯法从根结点开始按照深度优先策略遍历解空间树搜索满足约束条件的解对每一个当前结点若扩展该结点已经不满足约束条件则不再继续扩展为了进一步提高算法的搜索效率往往需要设计一个限界函数判断并剪枝那些即使扩展了也不能得到最优解的结点现在假设已经设计了BOUNDvwkw函数其中vwk和W分别表示当前已经获得的价值当前背包的重量已经确定是否选择的物品数和背包的总容量对应于搜索树中的某个结点该函数值表示确定了部分物品是否选择之后对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值若该价值小于等于当前已经得到的最优解则该结点无须再扩展 下面给出0-1背包问题的回溯算法伪代码 函数参数说明如下 W背包容量n物品个数w重量数组v价值数组fw获得最大价值时背包的重量fp背包获得的最大价值X问题的最优解 变量说明如下 cw当前的背包重量cp当前获得的价值k当前考虑的物品编号Y当前已获得的部分解 BKNAPWnwvfwfpX 1cw←cp←0 21 3fp←-1 4Whiletrue 5whilek≤nandcw+w[k]≤Wdo 62 7cp←cp+v[k] 8Y[k]←1 9k←k+1 10ifk＞nthen 11iffp＜cpthen 12fp←cp 13fw←cw 14k←n 15X←Y 16elseYk←0 17whileBOUNDcpcwkW≤fpdo 18whilek≠0andYk≠1do 193 20ifk=0thenreturn 21Y[k]←0 22cw←cw←w[k] 23cp←cp←v[k] 244 [问题2] 考虑表21-3所示的实例假设有3个物品背包容量为22图21-12是根据上述算法构造的搜索树其中结点的编号表示搜索树生成的顺序边上的数字I/O分别表示选择/不选择对应物品除了根结点之外每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值为获得最优解应该选择物品5获得的价值为6 对于表21-3所示的实例若采用穷举法搜索整个解空间则搜索树的结点数为7而采用上述的回溯法搜索树的结点数为8 4处填
阅读下列说明回答问题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] 下面是快速排序的伪代码请填补其中的空缺 伪代码中的主要变量说明如下 A待排序数组 pr数组元素下标从p到r q划分的位置 x枢轴元素 i整型变量用于描述数组下标下标小于或等于i的元素的值小于或等于枢轴元素的值 j循环控制变量表示数组元素下标 QUICKSORTAPr ifp＜r q=PARTITIONApr QUICKSORTApq-1 QUICKSORTAq+1r PARTITIONApr X=A[r]i=p-1 forj=pj≤r-1j++ ifA[j]≤x i=i+1 交换A[j]和A[j] 交换1和2//注空1和空2答案可以互换但两个空全部答对方可得分 return3 [问题2] 1假设要排序包含n个元素的数组请给出在各种不同的划分情况下快速排序的时间复杂度用O记号最佳情况为4平均情况为5最坏情况为6 2假设要排序的n个元素都具有相同值时快速排序的运行时间复杂度属于哪种情况7最佳平均最坏 [问题3] 1待排序数组是否能被较均匀地划分对快速排序的性能有重要影响因此枢轴元素的选取非常重要有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作请填充其中的空缺处其中RANDOMij表示随机取i到j之间的一个数包括i和j RANDOMIZED-PARTITIONApr i=RANDOMpr 交换8和9//注空8和空9答案可以互换但两个空全部答对方可得分 returnPARTITIONApr 2随机化快速排序是否能够消除最坏情况的发生10是或否 8处填
阅读下列说明回答问题1和问题2将解答填入对应栏内 [说明] 现需要在某城市中选择一个社区建一个大型超市使该城市的其他社区到该超市的距离总和最小用图模型表示该城市的地图其中顶点表示社区边表示社区间的路线边上的权重表示该路线的长度 现设计一个算法来找到该大型超市的最佳位置即在给定图中选择一个顶点使该顶点到其他各顶点的最短路径之和最小首先算法需要求出每个顶点到其他任一顶点的最短路径即需要计算任意两个顶点之间的最短路径然后对每个顶点计算其他各顶点到该顶点的最短路径之和最后选择最短路径之和最小的顶点作为建大型超市的最佳位置 [问题1] 本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径已知图G的顶点集合为V=12…nW=Wijn*n为权重矩阵 设为从顶点i到顶点j的一条最短路径的权重 当k=0时不存在中间顶点因此当k＞0时该最短路径上所有的中间顶点均属于集合12…k 若中间顶点包括顶点k则若中间顶点不包括顶点k则 于是得到如下递归式 因为对于任意路径所有的中间顶点都在集合12…n内因此矩阵给出了任意两个顶点之间的最短路径即对所有ij∈V表示顶点i到顶点j的最短路径 下面是求解该问题的伪代码请填充其中的空缺1～6 伪代码中的主要变量说明如下 W权重矩阵 n图的顶点个数 SP最短路径权重之和数组SP[i]表示顶点i到其他各顶点的最短路径权重之和i取值为1～n min_SP最小的最短路径权重之和 min_v具有最小的最短路径权重之和的顶点 i循环控制变量 j循环控制变量 k循环控制变量 LOCATE-SHCPPINGNALLWn 1D0=W 2for1 3fori=1ton 4forj=1ton 5if 62 7else 83 9fori=1ton 10SP[i]=0 11forj=1ton 124 13min_SP=SP[1] 145 15fori=2ton 16ifmin_SP＞SP[i] 17min_SP=SP[i] 18min_v=i 19return6 [问题2] 问题1中伪代码的时间复杂度为7用O符号表示 4处填
阅读下列说明和C函数代码将应填入n处的字句写在对应栏内 [说明] 对二叉树进行遍历是二叉树的一个基本运算遍历是指按某种策略访问二又树的每个结点且每个结点仅访问一次的过程函数InOrder借助栈实现二叉树的非递归中序遍历运算 设二叉树采用二叉链表存储结点类型定义如下 typedefstructBtNode ElemTypedata/*结点的数据域ElemType的具体定义省略*/ structBtNode*lchiid*rchiid/*结点的左右孩子指针域*/ BtNode*BTree 在函数InOrderO中用栈暂存二叉树中各个结点的指针并将栈表示为不含头结点的单向链表简称链栈其结点类型定义如下 typedefstructStNode/*链栈的结点类型*/ BTreeelem/*栈中的元素是指向二叉链表结点的指针*/ StructStNode*link StNode 假设从栈顶到栈底的元素为enen-1…e1则不含头结点的链栈示意图如图21-11所示 [C函数] intInOrderBTreeroot/*实现二叉树的非递归中序遍历*/ BTreeptr/*ptr用于指向二叉树中的结点*/ StNode*q/*q暂存链栈中新创建或待删除的结点指针*/ StNode*stacktop=NULL/*初始化空栈的栈顶指针stacktop*/ ptr=root/*ptr指向二叉树的根结点*/ while1||stacktop!=NULL whileptr!=NULL q=StNode*mallocSizeofStNode ifa==NULL return-1 q-＞elem=ptr 2 stacktop=q/*stacktop指向新的栈顶*/ ptr=3/*进入左子树*/ q=stacktop 4/*栈顶元素出栈*/ visitq/*visit是访问结点的函数其具体定义省略*/ ptr=5/*进入右子树*/ freeq/*释放原栈顶元素的结点空间*/ return0 /*Inorder*/ 1处填
阅读下列说明和c函数将应填入n处的字句写在对应栏内 [说明] 已知集合A和B的元素分别用不含头结点的单链表存储函数Difference用于求解集合A与B的差集并将结果保存在集合A的单链表中例如若集合A=51020152530集合B=5153525如图21-10a所示运算完成后的结果如图21-10b所示 链表结点的结构类型定义如下 typedefstructNode ElemTypeelem structNode*next NodeType [C函数] voidDifferenceNodeType**LANodeType*LB NodeType*pa*pb*pre*q pre=NULL 1 whilepa pb=LB while2 pb=pb-＞next if3 if!pre *LA=4 else 5=pa-＞next q=pa pa=pa-＞next freeq else 6 pa=pa-＞next 6处填
不同的对象收到同一消息可以产生完全不同的结果这一现象叫做94绑定是把过程调用和响应调用所需要执行的代码加以结合的一个过程在一般的程序设计语言中绑定在编译时进行叫做95而96则在运行时进行即一个给定的过程调用和执行代码的结合直到调用发生时才进行
阅读下列说明回答问题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] 下面是快速排序的伪代码请填补其中的空缺 伪代码中的主要变量说明如下 A待排序数组 pr数组元素下标从p到r q划分的位置 x枢轴元素 i整型变量用于描述数组下标下标小于或等于i的元素的值小于或等于枢轴元素的值 j循环控制变量表示数组元素下标 QUICKSORTAPr ifp＜r q=PARTITIONApr QUICKSORTApq-1 QUICKSORTAq+1r PARTITIONApr X=A[r]i=p-1 forj=pj≤r-1j++ ifA[j]≤x i=i+1 交换A[j]和A[j] 交换1和2//注空1和空2答案可以互换但两个空全部答对方可得分 return3 [问题2] 1假设要排序包含n个元素的数组请给出在各种不同的划分情况下快速排序的时间复杂度用O记号最佳情况为4平均情况为5最坏情况为6 2假设要排序的n个元素都具有相同值时快速排序的运行时间复杂度属于哪种情况7最佳平均最坏 [问题3] 1待排序数组是否能被较均匀地划分对快速排序的性能有重要影响因此枢轴元素的选取非常重要有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作请填充其中的空缺处其中RANDOMij表示随机取i到j之间的一个数包括i和j RANDOMIZED-PARTITIONApr i=RANDOMpr 交换8和9//注空8和空9答案可以互换但两个空全部答对方可得分 returnPARTITIONApr 2随机化快速排序是否能够消除最坏情况的发生10是或否 2处填
阅读下列说明和c函数将应填入n处的字句写在对应栏内 [说明] 已知集合A和B的元素分别用不含头结点的单链表存储函数Difference用于求解集合A与B的差集并将结果保存在集合A的单链表中例如若集合A=51020152530集合B=5153525如图21-10a所示运算完成后的结果如图21-10b所示 链表结点的结构类型定义如下 typedefstructNode ElemTypeelem structNode*next NodeType [C函数] voidDifferenceNodeType**LANodeType*LB NodeType*pa*pb*pre*q pre=NULL 1 whilepa pb=LB while2 pb=pb-＞next if3 if!pre *LA=4 else 5=pa-＞next q=pa pa=pa-＞next freeq else 6 pa=pa-＞next 2处填
阅读下列说明回答问题1至问题3将解答填入对应栏内 [说明] 希赛公司供应各种标准的营养套餐假设菜单上共有n项食物m1m2…mn每项食物mi的营养价值为vi价格为pi其中i=12…n套餐中每项食物至多出现一次客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐 [问题1] 下面是用动态规划策略求解该问题的伪代码请填充其中的空缺12和3 伪代码中的主要变量说明如下 n总的食物项数 v营养价值数组下标从1到n对应第1项到第n项食物的营养价值 p价格数组下标从1到n对应第1项到第n项食物的价格 M总价格标准即套餐的价格不超过M x解向量数组下标从1到n其元素值为0或1其中元素值为0表示对应的食物不出现在套餐中元素值为1表示对应的食物出现在套餐中 nvn+1行M+1列的二维数组其中行和列的下标均从0开始nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值问题最终要求的套餐的最大营养价值为nv[n][M] 伪代码如下 MaxNutrientValuenvpMx 1fori=0ton 2nv[i][0]=0 3forj=1toM 4nv[0][j]=0 5fori=1ton 6forj=1toM 7ifj＜p[i]//若食物mi不能加入到套餐中 8nv[i][j]=nv[i-1][j] 9elseif1 10nv[i][j]=nv[i-1][j] 11else 12nv[i][j]=nv[i-1][j-p[i]]+v[i] 13j=M 14fori=ndownto1 15if2 16x[i]=0 17else 18x[i]=1 193 20returnxandnv[n][M] [问题2] 现有5项食物每项食物的营养价值和价格如表21-2所示 若要求总价格不超过100的营养价值最大的套餐则套餐应包含的食物有4用食物项的编码表示对应的最大营养价值为5 [问题3] 问题1中伪代码的时间复杂度为6用O符号表示 4处填
阅读下列说明回答问题1至问题3将解答填入对应栏内 [说明] 希赛公司供应各种标准的营养套餐假设菜单上共有n项食物m1m2…mn每项食物mi的营养价值为vi价格为pi其中i=12…n套餐中每项食物至多出现一次客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐 [问题1] 下面是用动态规划策略求解该问题的伪代码请填充其中的空缺12和3 伪代码中的主要变量说明如下 n总的食物项数 v营养价值数组下标从1到n对应第1项到第n项食物的营养价值 p价格数组下标从1到n对应第1项到第n项食物的价格 M总价格标准即套餐的价格不超过M x解向量数组下标从1到n其元素值为0或1其中元素值为0表示对应的食物不出现在套餐中元素值为1表示对应的食物出现在套餐中 nvn+1行M+1列的二维数组其中行和列的下标均从0开始nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值问题最终要求的套餐的最大营养价值为nv[n][M] 伪代码如下 MaxNutrientValuenvpMx 1fori=0ton 2nv[i][0]=0 3forj=1toM 4nv[0][j]=0 5fori=1ton 6forj=1toM 7ifj＜p[i]//若食物mi不能加入到套餐中 8nv[i][j]=nv[i-1][j] 9elseif1 10nv[i][j]=nv[i-1][j] 11else 12nv[i][j]=nv[i-1][j-p[i]]+v[i] 13j=M 14fori=ndownto1 15if2 16x[i]=0 17else 18x[i]=1 193 20returnxandnv[n][M] [问题2] 现有5项食物每项食物的营养价值和价格如表21-2所示 若要求总价格不超过100的营养价值最大的套餐则套餐应包含的食物有4用食物项的编码表示对应的最大营养价值为5 [问题3] 问题1中伪代码的时间复杂度为6用O符号表示 2处填
UML的设计视图包含了类接口和协作其中设计视图的静态方面由22和23表现动态方面由交互图24表现
类描述了一组对象共同的特性下列叙述中正确的是______
阅读下列说明回答问题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] 下面是快速排序的伪代码请填补其中的空缺 伪代码中的主要变量说明如下 A待排序数组 pr数组元素下标从p到r q划分的位置 x枢轴元素 i整型变量用于描述数组下标下标小于或等于i的元素的值小于或等于枢轴元素的值 j循环控制变量表示数组元素下标 QUICKSORTAPr ifp＜r q=PARTITIONApr QUICKSORTApq-1 QUICKSORTAq+1r PARTITIONApr X=A[r]i=p-1 forj=pj≤r-1j++ ifA[j]≤x i=i+1 交换A[j]和A[j] 交换1和2//注空1和空2答案可以互换但两个空全部答对方可得分 return3 [问题2] 1假设要排序包含n个元素的数组请给出在各种不同的划分情况下快速排序的时间复杂度用O记号最佳情况为4平均情况为5最坏情况为6 2假设要排序的n个元素都具有相同值时快速排序的运行时间复杂度属于哪种情况7最佳平均最坏 [问题3] 1待排序数组是否能被较均匀地划分对快速排序的性能有重要影响因此枢轴元素的选取非常重要有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作请填充其中的空缺处其中RANDOMij表示随机取i到j之间的一个数包括i和j RANDOMIZED-PARTITIONApr i=RANDOMpr 交换8和9//注空8和空9答案可以互换但两个空全部答对方可得分 returnPARTITIONApr 2随机化快速排序是否能够消除最坏情况的发生10是或否 10处填
阅读下列说明回答问题1和问题2将解答填入对应栏内 [说明] 现需要在某城市中选择一个社区建一个大型超市使该城市的其他社区到该超市的距离总和最小用图模型表示该城市的地图其中顶点表示社区边表示社区间的路线边上的权重表示该路线的长度 现设计一个算法来找到该大型超市的最佳位置即在给定图中选择一个顶点使该顶点到其他各顶点的最短路径之和最小首先算法需要求出每个顶点到其他任一顶点的最短路径即需要计算任意两个顶点之间的最短路径然后对每个顶点计算其他各顶点到该顶点的最短路径之和最后选择最短路径之和最小的顶点作为建大型超市的最佳位置 [问题1] 本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径已知图G的顶点集合为V=12…nW=Wijn*n为权重矩阵 设为从顶点i到顶点j的一条最短路径的权重 当k=0时不存在中间顶点因此当k＞0时该最短路径上所有的中间顶点均属于集合12…k 若中间顶点包括顶点k则若中间顶点不包括顶点k则 于是得到如下递归式 因为对于任意路径所有的中间顶点都在集合12…n内因此矩阵给出了任意两个顶点之间的最短路径即对所有ij∈V表示顶点i到顶点j的最短路径 下面是求解该问题的伪代码请填充其中的空缺1～6 伪代码中的主要变量说明如下 W权重矩阵 n图的顶点个数 SP最短路径权重之和数组SP[i]表示顶点i到其他各顶点的最短路径权重之和i取值为1～n min_SP最小的最短路径权重之和 min_v具有最小的最短路径权重之和的顶点 i循环控制变量 j循环控制变量 k循环控制变量 LOCATE-SHCPPINGNALLWn 1D0=W 2for1 3fori=1ton 4forj=1ton 5if 62 7else 83 9fori=1ton 10SP[i]=0 11forj=1ton 124 13min_SP=SP[1] 145 15fori=2ton 16ifmin_SP＞SP[i] 17min_SP=SP[i] 18min_v=i 19return6 [问题2] 问题1中伪代码的时间复杂度为7用O符号表示 6处填
UML类图中类与类之间的关系有5种依赖关联聚合组合与继承若类A需要使用标准数学函数类库中提供的功能那么类A与标准类库提供的类之间存在101关系若类A中包含了其他类的实例且当类A的实例消失时其包含的其他类的实例也消失则类A和它所包含的类之间存在102关系若类A的实例消失时其他类的实例仍然存在并继续工作那么类A和它所包含的类之间存在103关系
UML类图中类与类之间的关系有5种依赖关联聚合组合与继承若类A需要使用标准数学函数类库中提供的功能那么类A与标准类库提供的类之间存在101关系若类A中包含了其他类的实例且当类A的实例消失时其包含的其他类的实例也消失则类A和它所包含的类之间存在102关系若类A的实例消失时其他类的实例仍然存在并继续工作那么类A和它所包含的类之间存在103关系
阅读下列说明回答问题1和问题2将解答填入对应栏内 [说明] 0-1背包问题可以描述为有n个物品i=12…n第i个物品价值为vi重量为wivi和wi为非负数背包容量为WW为非负数选择其中一些物品装入背包使装入背包物品的总价值最大即且总重量不超过背包容量即其中xi∈01xi=0表示第i个物品不放入背包xi=1表示第i个物品放入背包 [问题1] 用回溯法求解此0-1背包问题请填充伪代码中的空缺1～4 回溯法是一种系统的搜索方法在确定解空间后回溯法从根结点开始按照深度优先策略遍历解空间树搜索满足约束条件的解对每一个当前结点若扩展该结点已经不满足约束条件则不再继续扩展为了进一步提高算法的搜索效率往往需要设计一个限界函数判断并剪枝那些即使扩展了也不能得到最优解的结点现在假设已经设计了BOUNDvwkw函数其中vwk和W分别表示当前已经获得的价值当前背包的重量已经确定是否选择的物品数和背包的总容量对应于搜索树中的某个结点该函数值表示确定了部分物品是否选择之后对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值若该价值小于等于当前已经得到的最优解则该结点无须再扩展 下面给出0-1背包问题的回溯算法伪代码 函数参数说明如下 W背包容量n物品个数w重量数组v价值数组fw获得最大价值时背包的重量fp背包获得的最大价值X问题的最优解 变量说明如下 cw当前的背包重量cp当前获得的价值k当前考虑的物品编号Y当前已获得的部分解 BKNAPWnwvfwfpX 1cw←cp←0 21 3fp←-1 4Whiletrue 5whilek≤nandcw+w[k]≤Wdo 62 7cp←cp+v[k] 8Y[k]←1 9k←k+1 10ifk＞nthen 11iffp＜cpthen 12fp←cp 13fw←cw 14k←n 15X←Y 16elseYk←0 17whileBOUNDcpcwkW≤fpdo 18whilek≠0andYk≠1do 193 20ifk=0thenreturn 21Y[k]←0 22cw←cw←w[k] 23cp←cp←v[k] 244 [问题2] 考虑表21-3所示的实例假设有3个物品背包容量为22图21-12是根据上述算法构造的搜索树其中结点的编号表示搜索树生成的顺序边上的数字I/O分别表示选择/不选择对应物品除了根结点之外每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值为获得最优解应该选择物品5获得的价值为6 对于表21-3所示的实例若采用穷举法搜索整个解空间则搜索树的结点数为7而采用上述的回溯法搜索树的结点数为8 6处填
阅读下列说明回答问题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] 下面是快速排序的伪代码请填补其中的空缺 伪代码中的主要变量说明如下 A待排序数组 pr数组元素下标从p到r q划分的位置 x枢轴元素 i整型变量用于描述数组下标下标小于或等于i的元素的值小于或等于枢轴元素的值 j循环控制变量表示数组元素下标 QUICKSORTAPr ifp＜r q=PARTITIONApr QUICKSORTApq-1 QUICKSORTAq+1r PARTITIONApr X=A[r]i=p-1 forj=pj≤r-1j++ ifA[j]≤x i=i+1 交换A[j]和A[j] 交换1和2//注空1和空2答案可以互换但两个空全部答对方可得分 return3 [问题2] 1假设要排序包含n个元素的数组请给出在各种不同的划分情况下快速排序的时间复杂度用O记号最佳情况为4平均情况为5最坏情况为6 2假设要排序的n个元素都具有相同值时快速排序的运行时间复杂度属于哪种情况7最佳平均最坏 [问题3] 1待排序数组是否能被较均匀地划分对快速排序的性能有重要影响因此枢轴元素的选取非常重要有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作请填充其中的空缺处其中RANDOMij表示随机取i到j之间的一个数包括i和j RANDOMIZED-PARTITIONApr i=RANDOMpr 交换8和9//注空8和空9答案可以互换但两个空全部答对方可得分 returnPARTITIONApr 2随机化快速排序是否能够消除最坏情况的发生10是或否 4处填
阅读下列说明和c函数将应填入n处的字句写在对应栏内 [说明] 已知集合A和B的元素分别用不含头结点的单链表存储函数Difference用于求解集合A与B的差集并将结果保存在集合A的单链表中例如若集合A=51020152530集合B=5153525如图21-10a所示运算完成后的结果如图21-10b所示 链表结点的结构类型定义如下 typedefstructNode ElemTypeelem structNode*next NodeType [C函数] voidDifferenceNodeType**LANodeType*LB NodeType*pa*pb*pre*q pre=NULL 1 whilepa pb=LB while2 pb=pb-＞next if3 if!pre *LA=4 else 5=pa-＞next q=pa pa=pa-＞next freeq else 6 pa=pa-＞next 4处填
阅读下列说明和C函数代码将应填入n处的字句写在对应栏内 [说明] 对二叉树进行遍历是二叉树的一个基本运算遍历是指按某种策略访问二又树的每个结点且每个结点仅访问一次的过程函数InOrder借助栈实现二叉树的非递归中序遍历运算 设二叉树采用二叉链表存储结点类型定义如下 typedefstructBtNode ElemTypedata/*结点的数据域ElemType的具体定义省略*/ structBtNode*lchiid*rchiid/*结点的左右孩子指针域*/ BtNode*BTree 在函数InOrderO中用栈暂存二叉树中各个结点的指针并将栈表示为不含头结点的单向链表简称链栈其结点类型定义如下 typedefstructStNode/*链栈的结点类型*/ BTreeelem/*栈中的元素是指向二叉链表结点的指针*/ StructStNode*link StNode 假设从栈顶到栈底的元素为enen-1…e1则不含头结点的链栈示意图如图21-11所示 [C函数] intInOrderBTreeroot/*实现二叉树的非递归中序遍历*/ BTreeptr/*ptr用于指向二叉树中的结点*/ StNode*q/*q暂存链栈中新创建或待删除的结点指针*/ StNode*stacktop=NULL/*初始化空栈的栈顶指针stacktop*/ ptr=root/*ptr指向二叉树的根结点*/ while1||stacktop!=NULL whileptr!=NULL q=StNode*mallocSizeofStNode ifa==NULL return-1 q-＞elem=ptr 2 stacktop=q/*stacktop指向新的栈顶*/ ptr=3/*进入左子树*/ q=stacktop 4/*栈顶元素出栈*/ visitq/*visit是访问结点的函数其具体定义省略*/ ptr=5/*进入右子树*/ freeq/*释放原栈顶元素的结点空间*/ return0 /*Inorder*/ 3处填
阅读下列说明回答问题1至问题3将解答填入对应栏内 [说明] 希赛公司供应各种标准的营养套餐假设菜单上共有n项食物m1m2…mn每项食物mi的营养价值为vi价格为pi其中i=12…n套餐中每项食物至多出现一次客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐 [问题1] 下面是用动态规划策略求解该问题的伪代码请填充其中的空缺12和3 伪代码中的主要变量说明如下 n总的食物项数 v营养价值数组下标从1到n对应第1项到第n项食物的营养价值 p价格数组下标从1到n对应第1项到第n项食物的价格 M总价格标准即套餐的价格不超过M x解向量数组下标从1到n其元素值为0或1其中元素值为0表示对应的食物不出现在套餐中元素值为1表示对应的食物出现在套餐中 nvn+1行M+1列的二维数组其中行和列的下标均从0开始nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值问题最终要求的套餐的最大营养价值为nv[n][M] 伪代码如下 MaxNutrientValuenvpMx 1fori=0ton 2nv[i][0]=0 3forj=1toM 4nv[0][j]=0 5fori=1ton 6forj=1toM 7ifj＜p[i]//若食物mi不能加入到套餐中 8nv[i][j]=nv[i-1][j] 9elseif1 10nv[i][j]=nv[i-1][j] 11else 12nv[i][j]=nv[i-1][j-p[i]]+v[i] 13j=M 14fori=ndownto1 15if2 16x[i]=0 17else 18x[i]=1 193 20returnxandnv[n][M] [问题2] 现有5项食物每项食物的营养价值和价格如表21-2所示 若要求总价格不超过100的营养价值最大的套餐则套餐应包含的食物有4用食物项的编码表示对应的最大营养价值为5 [问题3] 问题1中伪代码的时间复杂度为6用O符号表示 6处填
下面关于面向对象的描述正确的是______
阅读下列说明回答问题1和问题2将解答填入对应栏内 [说明] 0-1背包问题可以描述为有n个物品i=12…n第i个物品价值为vi重量为wivi和wi为非负数背包容量为WW为非负数选择其中一些物品装入背包使装入背包物品的总价值最大即且总重量不超过背包容量即其中xi∈01xi=0表示第i个物品不放入背包xi=1表示第i个物品放入背包 [问题1] 用回溯法求解此0-1背包问题请填充伪代码中的空缺1～4 回溯法是一种系统的搜索方法在确定解空间后回溯法从根结点开始按照深度优先策略遍历解空间树搜索满足约束条件的解对每一个当前结点若扩展该结点已经不满足约束条件则不再继续扩展为了进一步提高算法的搜索效率往往需要设计一个限界函数判断并剪枝那些即使扩展了也不能得到最优解的结点现在假设已经设计了BOUNDvwkw函数其中vwk和W分别表示当前已经获得的价值当前背包的重量已经确定是否选择的物品数和背包的总容量对应于搜索树中的某个结点该函数值表示确定了部分物品是否选择之后对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值若该价值小于等于当前已经得到的最优解则该结点无须再扩展 下面给出0-1背包问题的回溯算法伪代码 函数参数说明如下 W背包容量n物品个数w重量数组v价值数组fw获得最大价值时背包的重量fp背包获得的最大价值X问题的最优解 变量说明如下 cw当前的背包重量cp当前获得的价值k当前考虑的物品编号Y当前已获得的部分解 BKNAPWnwvfwfpX 1cw←cp←0 21 3fp←-1 4Whiletrue 5whilek≤nandcw+w[k]≤Wdo 62 7cp←cp+v[k] 8Y[k]←1 9k←k+1 10ifk＞nthen 11iffp＜cpthen 12fp←cp 13fw←cw 14k←n 15X←Y 16elseYk←0 17whileBOUNDcpcwkW≤fpdo 18whilek≠0andYk≠1do 193 20ifk=0thenreturn 21Y[k]←0 22cw←cw←w[k] 23cp←cp←v[k] 244 [问题2] 考虑表21-3所示的实例假设有3个物品背包容量为22图21-12是根据上述算法构造的搜索树其中结点的编号表示搜索树生成的顺序边上的数字I/O分别表示选择/不选择对应物品除了根结点之外每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值为获得最优解应该选择物品5获得的价值为6 对于表21-3所示的实例若采用穷举法搜索整个解空间则搜索树的结点数为7而采用上述的回溯法搜索树的结点数为8 2处填
面向对象开发方法的基本思想是尽可能按照人类认识客观世界的方法来分析和解决问题______方法不属于面向对象方法
阅读下列说明和C函数代码将应填入n处的字句写在对应栏内 [说明] 对二叉树进行遍历是二叉树的一个基本运算遍历是指按某种策略访问二又树的每个结点且每个结点仅访问一次的过程函数InOrder借助栈实现二叉树的非递归中序遍历运算 设二叉树采用二叉链表存储结点类型定义如下 typedefstructBtNode ElemTypedata/*结点的数据域ElemType的具体定义省略*/ structBtNode*lchiid*rchiid/*结点的左右孩子指针域*/ BtNode*BTree 在函数InOrderO中用栈暂存二叉树中各个结点的指针并将栈表示为不含头结点的单向链表简称链栈其结点类型定义如下 typedefstructStNode/*链栈的结点类型*/ BTreeelem/*栈中的元素是指向二叉链表结点的指针*/ StructStNode*link StNode 假设从栈顶到栈底的元素为enen-1…e1则不含头结点的链栈示意图如图21-11所示 [C函数] intInOrderBTreeroot/*实现二叉树的非递归中序遍历*/ BTreeptr/*ptr用于指向二叉树中的结点*/ StNode*q/*q暂存链栈中新创建或待删除的结点指针*/ StNode*stacktop=NULL/*初始化空栈的栈顶指针stacktop*/ ptr=root/*ptr指向二叉树的根结点*/ while1||stacktop!=NULL whileptr!=NULL q=StNode*mallocSizeofStNode ifa==NULL return-1 q-＞elem=ptr 2 stacktop=q/*stacktop指向新的栈顶*/ ptr=3/*进入左子树*/ q=stacktop 4/*栈顶元素出栈*/ visitq/*visit是访问结点的函数其具体定义省略*/ ptr=5/*进入右子树*/ freeq/*释放原栈顶元素的结点空间*/ return0 /*Inorder*/ 5处填
不同的对象收到同一消息可以产生完全不同的结果这一现象叫做94绑定是把过程调用和响应调用所需要执行的代码加以结合的一个过程在一般的程序设计语言中绑定在编译时进行叫做95而96则在运行时进行即一个给定的过程调用和执行代码的结合直到调用发生时才进行
阅读下列说明回答问题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] 下面是快速排序的伪代码请填补其中的空缺 伪代码中的主要变量说明如下 A待排序数组 pr数组元素下标从p到r q划分的位置 x枢轴元素 i整型变量用于描述数组下标下标小于或等于i的元素的值小于或等于枢轴元素的值 j循环控制变量表示数组元素下标 QUICKSORTAPr ifp＜r q=PARTITIONApr QUICKSORTApq-1 QUICKSORTAq+1r PARTITIONApr X=A[r]i=p-1 forj=pj≤r-1j++ ifA[j]≤x i=i+1 交换A[j]和A[j] 交换1和2//注空1和空2答案可以互换但两个空全部答对方可得分 return3 [问题2] 1假设要排序包含n个元素的数组请给出在各种不同的划分情况下快速排序的时间复杂度用O记号最佳情况为4平均情况为5最坏情况为6 2假设要排序的n个元素都具有相同值时快速排序的运行时间复杂度属于哪种情况7最佳平均最坏 [问题3] 1待排序数组是否能被较均匀地划分对快速排序的性能有重要影响因此枢轴元素的选取非常重要有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作请填充其中的空缺处其中RANDOMij表示随机取i到j之间的一个数包括i和j RANDOMIZED-PARTITIONApr i=RANDOMpr 交换8和9//注空8和空9答案可以互换但两个空全部答对方可得分 returnPARTITIONApr 2随机化快速排序是否能够消除最坏情况的发生10是或否 6处填
热门题库
更多
初级程序员
中级软件设计师
初级网络管理员
初级信息处理技术员
中级数据库系统工程师
中级多媒体应用设计师
高级系统分析师
高级网络规划设计师
高级系统架构师
中级信息系统监理师
初级通信工程师
中级通信工程师
通信新技术、新业务知识
无线通信专业技术
移动通信专业技术
有线传输专业技术
湘公网安备 43130202000226号