首页
试卷库
试题库
当前位置：
X题卡
>
所有题目
>
题目详情
在某计算机中，假设某程序的6个页面如下图所示，其中某指令“COPY A TO B”跨两个页面，且源地址A和目标地址B所涉及的区域也跨两个页面。若地址为A和B的操作数均不在内存，计算机执行该COP...
查看本题答案
包含此试题的试卷
中级软件设计师《单选集》真题及答案
点击查看
你可能感兴趣的试题
假设某计算机的存储系统由Cache和主存组成某程序执行过程中访存1000次其中访问Cache缺失未命
5%
9.5%
50%
95%
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
某企业内部网络中一台计算机的IP地址为10.3.1.21假设该计算机请求某Internet网站的in
1
2
3
4
峰值MIPS每秒百万次指令数用来描述计算机的定点运算速度通过对计算机指令集中基本指令的执行速度计算得
8
15
0．125
0．067
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
假设某计算机中用一个字节表示一个数那么数-117的原码是反码是补码是-117与小于等于的数相加会产生
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
某计算机系统的结构如下图所示按照弗林MichaelJ.Flynn提出的分类法它属于其中PUii
单指令流单数据流计算机（SISD）
单指令流多数据流计算机（SIMD）
多指令流单数据流计算机（MISD）
多指令流多数据流计算机（MIMD）
峰值MIPS每秒百万次指令数用来描述计算机的定点运算速度通过对计算机指令集中基本指令的执行速度计算得
8
15
0.125
0.067
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
某企业内部网络中一台计算机的IP地址为10.3.1.21假设该计算机请求某Internet网站的in
1
3
7
15
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
向上兼容就是要求为某档机种编制的程序应能运行于同一系列计算机中更高档次的机种上
在某计算机中假设某程序的6个页面如下图所示其中某指令COPYATOB跨两个页面且源地址A和目标
2
3
4
5
已知某软件的信息界面如下图所示其中表示软件修订号的是
11
9
3255
某计算机字长8位采用补码表示小数若某数真值为-0.1001则它在该计算机中的机器数形式为
10111
10110111
10111000
10110000
假设某计算机的存储系统由Cache和主存组成某程序执行过程中访存1000次其中访问Cache缺失未命
5%
9．5%
50%
95%
热门试题
更多
阅读下列说明回答问题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至问题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处填
阅读下列说明和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处填
阅读下列说明回答问题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至问题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处填
阅读下列说明回答问题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处填
计算机中常采用原码反码补码和移码表示数据其中±0编码相同的是
阅读下列说明和C代码回答问题1至问题3将解答写在对应栏内 [说明] 堆数据结构定义如下 对于n个元素的关键字序列a1a2…an当且仅当满足下列关系时称其为堆 在一个堆中若堆顶元素为最大元素则称为大顶堆若堆顶元素为最小元素则称为小顶堆堆常用完全二叉树表示图21-16是一个大顶堆的例子 堆数据结构常用于优先队列中以维护由一组元素构成的集合对应于两类堆结构优先队列也有最大优先队列和最小优先队列其中最大优先队列采用大顶堆最小优先队列采用小顶堆以下考虑最大优先队列 假设现已建好大顶堆A且已经实现了调整堆的函数heapifyAnindex 对C代码中需要完善的3个函数说明如下 1heapMaximumA返回大顶堆A中的最大元素 2heapExtractMaxA去掉并返回大项堆A的最大元素将最后一个元素“提前”到堆顶位置并将剩余元素调整成大顶堆 3maxHeapInsertAkey把元素key插入到大顶堆A的最后位置再将A调整成大顶堆 优先队列采用顺序存储方式其存储结构定义如下 #definePARENTii/2 typedefstructarray int*int_arrav//优先队列的存储空间首地址 intarray_size//it先队列的长度 intcapacity//优先队列存储空间的容量 ARRAY [C代码] 1函数heapMaximum intheapMaximumARRAY*Areturn1 2函数heapExtractMax intheapExtractMaxARRAY*A intmax max=A-＞int_array[0] 2 A-＞array_size-- heapifyAA-＞array_size0//将剩余元素调整成大顶堆 returnmax 3函数maxHeapInsert intmaxHeapInsertARRAY*Aintkey inti*p ifA-＞array_size==A-＞capacity//存储空间的容量不够时扩充空间 p=int*reallocA-＞int_arrayA-＞capacity*2*sizeofint if!preturn-1 A-＞int_array=p A-＞capacity=2*A-＞capacity A-＞array_size++ i=3 whilei＞0＆＆4 A-＞int_array[i]=A-＞int_array[PARENTi] i=PARENTi 5 return0 根据以上说明和C代码填充C代码中的空1～5
阅读下列说明回答问题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处填
阅读下列说明和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处填
阅读下列说明回答问题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处的字句写在对应栏内 [说明] 栈Stack结构是计算机语言实现中的一种重要数据结构对于任意栈进行插入和删除操作的一端称为栈顶StackTop而另一端称为栈底StackBottom栈的基本操作包括创建栈NewStack判断栈是否为空IsEmpty判断栈是否已满IsFull获取栈顶数据Top压栈/入栈Push弹栈/出栈Pop 当设计栈的存储结构时可以采取多种方式其中采用链式存储结构实现的栈中各数据项不必连续存储如图21-9所示 以下C代码采用链式存储结构实现一个整数栈操作 [C代码] typedefstructList intdata//栈数据 structList*next//上次入栈的数据地址 List typedefstructStack List*pTop//当前栈顶指针 Stack Stack*NewStackreturnStack*calloc1sizeofStack intIsEmptyStack*S//判断栈S是否为空栈 if1return1 return0 intTopStack*S//获取栈顶数据若栈为空则返回机器可表示的最小整数 ifIsEmptySreturnINT_MIN return2 voidPushStack*SinttheData//将数据theData压栈 List*newNode newNode=List*calloc1sizeofList newNode-＞data=theData newNode-＞next=S-＞pTop S-＞pTop=3 voidPopStack*S//弹栈 List*lastTop ifIsEmptySreturn lastTop=S-＞pTop S-＞pTop=4 freelastTop #defineMDaa＜＜2 intmain inti Stack*myStack myStack=NewStack PushmyStackMD1 PushmyStackMD2 PopmyStack PushmyStackMD3+1 while!IsEmptymyStack printf"%d"TopmyStack PopmyStack return0 以上程序运行时的输出结果为5 3处填
阅读下列说明回答问题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处填
阅读下列说明和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将解答填入对应栏内 [说明] 快速排序是一种典型的分治算法采用快速排序对数组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将解答填入对应栏内 [说明] 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处填
阅读下列说明和C代码回答问题1至问题3将解答写在对应栏内 [说明] 对有向图进行拓扑排序的方法如下 1初始时拓扑序列为空 2任意选择一个入度为0的顶点将其放入拓扑序列中同时从图中删除该顶点以及从该顶点出发的弧 3重复2直到不存在入度为0的顶点为止若所有顶点都进入拓扑序列则完成拓扑排序否则由于有向图中存在回路无法完成拓扑排序 函数int*TopSortLinkedDigraphG的功能是对有向图G中的顶点进行拓扑排序返回拓扑序列中的顶点编号序列若不能完成拓扑排序则返回空指针其中图G中的项点从1开始依次编号顶点序列为v1v2…vn图G采用邻接表表示其数据类型定义如下 #defineMAXVNUM50/*最大顶点数*/ typedefstructArcNode/*表结点类型*/ intadjvex/*邻接顶点编号*/ StructArcNode*nextarc/*指示下一个邻接顶点*/ ArcNode typedefstructAdjList/*头结点类型*/ charvdata/*顶点的数据信息*/ ArcNode*firstarc/*指向邻接表的第一个表结点*/ AdjList typedefstructLinkedDigraph/*图的类型*/ intn/*图中顶点个数*/ AdjListVhead[MAXVNUM]/*所有顶点的头结点数组*/ LinkedDigraph 例如某有向图G如图21-13所示其邻接表如图21-14所示 函数TopSort中用到了队列结构Queue的定义省略实现队列基本操作的函数原型如表21-4所示 [C代码] int*TopSortLinkedDigraphG ArcNode*p/*临时指针指示表结点*/ QueueQ/*临时队列保存入度为0的顶点编号*/ intk=0/*临时变量用作数组元素的下标*/ intj=0w=0/*临时变量用作顶点编号*/ int*topOrder*inDegree topOrder=int*mallocG.n+1*sizeofint/*存储拓扑序列中的顶点编号*/ inDegree=int*mallocG.n+1*siZeofint/*存储图G中各顶点的入度*/ if!inDegree||!topOrderreturnNULL 1/*构造一个空队列*/ forj=1j＜=G.nj++/*初始化*/ topOrder[j]=0inDegree[j]=0 forj=1j＜=G.nj++/*求图G中各顶点的入度*/ forp=G.Vhead[j].firstarcpp=p-＞nextarc inDegree[p-＞adjvex]+=1 forj=1j＜=G.nj++/*将图G中入度为0的顶点保存在队列中*/ if0==inDegree[j]EnQueue＆Qj while!IsEmptyQ 2/*队头顶点出队列并用W保存该顶点的编号*/ topOrder[k++]=w /*将顶点w的所有邻接顶点的入度减1模拟删除顶点W及从该顶点出发的弧的操作*/ forp=G.Vhead[w].firstarepp=p-＞nextarc 3-=1 if0==4EnQueue＆Qp-＞adjvex /*for*/ /*while*/ freeinDegree if5 returnNULL returntopOrder /*TopSort*/ 对于图21-13所示的有向图G写出函数TopSort执行后得到的拓扑序列若将函数TopSort中的队列改为栈写出函数TopSort执行后得到的拓扑序列
阅读下列说明和C代码将应填入n处的字句写在对应栏内 [说明] 栈Stack结构是计算机语言实现中的一种重要数据结构对于任意栈进行插入和删除操作的一端称为栈顶StackTop而另一端称为栈底StackBottom栈的基本操作包括创建栈NewStack判断栈是否为空IsEmpty判断栈是否已满IsFull获取栈顶数据Top压栈/入栈Push弹栈/出栈Pop 当设计栈的存储结构时可以采取多种方式其中采用链式存储结构实现的栈中各数据项不必连续存储如图21-9所示 以下C代码采用链式存储结构实现一个整数栈操作 [C代码] typedefstructList intdata//栈数据 structList*next//上次入栈的数据地址 List typedefstructStack List*pTop//当前栈顶指针 Stack Stack*NewStackreturnStack*calloc1sizeofStack intIsEmptyStack*S//判断栈S是否为空栈 if1return1 return0 intTopStack*S//获取栈顶数据若栈为空则返回机器可表示的最小整数 ifIsEmptySreturnINT_MIN return2 voidPushStack*SinttheData//将数据theData压栈 List*newNode newNode=List*calloc1sizeofList newNode-＞data=theData newNode-＞next=S-＞pTop S-＞pTop=3 voidPopStack*S//弹栈 List*lastTop ifIsEmptySreturn lastTop=S-＞pTop S-＞pTop=4 freelastTop #defineMDaa＜＜2 intmain inti Stack*myStack myStack=NewStack PushmyStackMD1 PushmyStackMD2 PopmyStack PushmyStackMD3+1 while!IsEmptymyStack printf"%d"TopmyStack PopmyStack return0 以上程序运行时的输出结果为5 5处填
阅读下列说明回答问题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处填
阅读下列说明和c代码回答问题1至问题3将解答写在对应栏内 [说明] 某应用中需要对100000个整数元素进行排序每个元素的取值在0～5之间排序算法的基本思想是对每一个元素x确定小于等于x的元素个数记为m将x放在输出元素序列的第m个位置对于元素值重复的情况依次放入第m-1m-2…个位置例如如果元素值小于等于4的元素个数有10个其中元素值等于4的元素个数有3个则4应该在输出元素序列的第10个位置第9个位置和第8个位置上算法的具体步骤如下 步骤1统计每个元素值的个数 步骤2统计小于等于每个元素值的个数 步骤3将输入元素序列中的每个元素放入有序的输出元素序列 [C代码] 下面是该排序算法的c语言实现 1常量和变量说明 R常量定义元素取值范围中的取值个数如上述应用中R值应取6 i循环变量 n待排序元素个数 a输入数组长度为n b输出数组长度为n c辅助数组长度为R其中每个元素表示小于等于下标所对应的元素值的个数 2函数sort 1voidsortintninta[]intb[] 2intc[R]i 3fori=0i＜1i++ 4c[i]=0 5 6fori=0i＜ni++ 7c[a[i]]=2 8 9fori=1i＜Ri++ 10c[i]=3 11 12fori=0i＜ni++ 13b[c[a[i]]-1]=4 14c[a[i]]=c[a[i]]-1 15 16 根据C代码函数的时间复杂度和空间复杂度分别为5和6用O符号表示
阅读下列说明和C代码将应填入n处的字句写在对应栏内 [说明] 栈Stack结构是计算机语言实现中的一种重要数据结构对于任意栈进行插入和删除操作的一端称为栈顶StackTop而另一端称为栈底StackBottom栈的基本操作包括创建栈NewStack判断栈是否为空IsEmpty判断栈是否已满IsFull获取栈顶数据Top压栈/入栈Push弹栈/出栈Pop 当设计栈的存储结构时可以采取多种方式其中采用链式存储结构实现的栈中各数据项不必连续存储如图21-9所示 以下C代码采用链式存储结构实现一个整数栈操作 [C代码] typedefstructList intdata//栈数据 structList*next//上次入栈的数据地址 List typedefstructStack List*pTop//当前栈顶指针 Stack Stack*NewStackreturnStack*calloc1sizeofStack intIsEmptyStack*S//判断栈S是否为空栈 if1return1 return0 intTopStack*S//获取栈顶数据若栈为空则返回机器可表示的最小整数 ifIsEmptySreturnINT_MIN return2 voidPushStack*SinttheData//将数据theData压栈 List*newNode newNode=List*calloc1sizeofList newNode-＞data=theData newNode-＞next=S-＞pTop S-＞pTop=3 voidPopStack*S//弹栈 List*lastTop ifIsEmptySreturn lastTop=S-＞pTop S-＞pTop=4 freelastTop #defineMDaa＜＜2 intmain inti Stack*myStack myStack=NewStack PushmyStackMD1 PushmyStackMD2 PopmyStack PushmyStackMD3+1 while!IsEmptymyStack printf"%d"TopmyStack PopmyStack return0 以上程序运行时的输出结果为5 1处填
阅读下列说明回答问题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符号表示 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符号表示 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 2处填
阅读下列说明和C代码回答问题1至问题3将解答写在对应栏内 [说明] 堆数据结构定义如下 对于n个元素的关键字序列a1a2…an当且仅当满足下列关系时称其为堆 在一个堆中若堆顶元素为最大元素则称为大顶堆若堆顶元素为最小元素则称为小顶堆堆常用完全二叉树表示图21-16是一个大顶堆的例子 堆数据结构常用于优先队列中以维护由一组元素构成的集合对应于两类堆结构优先队列也有最大优先队列和最小优先队列其中最大优先队列采用大顶堆最小优先队列采用小顶堆以下考虑最大优先队列 假设现已建好大顶堆A且已经实现了调整堆的函数heapifyAnindex 对C代码中需要完善的3个函数说明如下 1heapMaximumA返回大顶堆A中的最大元素 2heapExtractMaxA去掉并返回大项堆A的最大元素将最后一个元素“提前”到堆顶位置并将剩余元素调整成大顶堆 3maxHeapInsertAkey把元素key插入到大顶堆A的最后位置再将A调整成大顶堆 优先队列采用顺序存储方式其存储结构定义如下 #definePARENTii/2 typedefstructarray int*int_arrav//优先队列的存储空间首地址 intarray_size//it先队列的长度 intcapacity//优先队列存储空间的容量 ARRAY [C代码] 1函数heapMaximum intheapMaximumARRAY*Areturn1 2函数heapExtractMax intheapExtractMaxARRAY*A intmax max=A-＞int_array[0] 2 A-＞array_size-- heapifyAA-＞array_size0//将剩余元素调整成大顶堆 returnmax 3函数maxHeapInsert intmaxHeapInsertARRAY*Aintkey inti*p ifA-＞array_size==A-＞capacity//存储空间的容量不够时扩充空间 p=int*reallocA-＞int_arrayA-＞capacity*2*sizeofint if!preturn-1 A-＞int_array=p A-＞capacity=2*A-＞capacity A-＞array_size++ i=3 whilei＞0＆＆4 A-＞int_array[i]=A-＞int_array[PARENTi] i=PARENTi 5 return0 若将元素10插入到堆A=＜151395128740621＞中调用maxHeapInsert函数进行操作则新插入的元素在堆A中第个位置从1开始
阅读下列说明和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处填
阅读下列说明和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处填
阅读下列说明回答问题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处填
热门题库
更多
中级软件设计师
初级网络管理员
初级信息处理技术员
中级数据库系统工程师
中级多媒体应用设计师
高级系统分析师
高级网络规划设计师
高级系统架构师
中级信息系统监理师
初级通信工程师
中级通信工程师
通信新技术、新业务知识
无线通信专业技术
移动通信专业技术
有线传输专业技术
电话交换专业技术
湘公网安备 43130202000226号