首页
试卷库
试题库
当前位置：
X题卡
>
所有题目
>
题目详情
在软件开发过程中进行风险分析时，（）活动目的是辅助项目组建立处理风险的策略，有效的策略应考虑风险避免、风险监控、风险管理及意外事件计划。
查看本题答案
包含此试题的试卷
中级软件设计师《单选集》真题及答案
点击查看
你可能感兴趣的试题
项目管理工具用来辅助项目经理实施软件开发过程中的项目管理活动它不能12就是一种典型的项目管理工具空白
需求分析工具
成本估算工具
软件评价工具
文档分析工具
下列描述中正确的是
软件工程只是解决软件项目的管理问题
软件工程主要解决软件产品的生产率问题
软件工程的主要思想是强调在软件开发过程中应用工程化原则
软件工程只是解决软件开发过程中的技术问题
论文论模型驱动的软件开发方法及其应用模型驱动架构MDA是对象管理组织OMG提出的一种新的软件开发方
论模型驱动的软件开发方法及其应用模型驱动架构MDA是对象管理组织OMG提出的一种新的软件开发方法它强
软件风险是指在软件开发过程中面临的一些不确定性和可能造成的损失软件风险大致可以分为3类项目风险技术风
软件的开发时间可能会超出预期时间
采用的开发技术过于先进，技术本身尚不稳定
软件开发过程中需求一直未能稳定下来
软件开发过程没有得到预算或人员上的保证
论迭代式软件开发过程与方法 软件项目的成功实施离不开有效的软件开发过程与开发方法相对于传统的瀑
论模型驱动的软件开发方法及其应用模型驱动架构MDA是对象管理组织OMG提出的一种新的软件开发方法它强
项目管理工具用来辅助项目经理实施软件开发过程中的项目管理活动它不能____________就是一种典
需求分析工具
成本估算工具
软件评价工具
文档分析工具
下列描述中正确的是
软件工程只是解决软件项目的管理问题
软件工程主要解决软件产品的生产率问题
软件工程的主要思想是强调在软件开发过程中需要应用工程化原则
软件工程只是解决软件开发过程中的技术问题
项目管理工具用来辅助项目经理实施软件开发过程中的项目管理活动它不能2627就是一种典型的项目管理工具
需求分析工具
成本估算工具
软件评价工具
文档分析工具
论迭代式软件开发过程与方法 软件项目的成功实施离不开有效的软件开发过程与开发方法相对于传统的瀑
在软件开发过程中进行风险分析时活动的目的是辅助项目组建立处理风险的策略有效的策略应考虑风险避免风险监
风险识别
风险预测
风险评估
风险控制
软件风险是指在软件开发过程中面临的一些不确定性和可能造成的损失软件风险大致可以分为三类项目风险技术风
软件的开发时间可能会超出预期时间
采用的开发技术过于先进，技术本身尚不稳定
软件开发过程中需求一直未能稳定下来
软件开发过程没有得到预算或人员上的保证
论迭代式软件开发过程与方法 软件项目的成功实施离不开有效的软件开发过程与开发方法相对于传统的瀑
软件风险是指在软件开发过程中面临的一些不确定性和可能造成的损失软件风险大致可以分为三类项目风险技术风
软件的开发时间可能会超出预期时间
采用的开发技术过于先进，技术本身尚不稳定
软件开发过程中需求一直未能稳定下来
软件开发过程没有得到预算或人员上的保证
热门试题
更多
下面关于校验方法的叙述是正确的
阅读下列说明回答问题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 5处填
编写汇编语言程序时下列寄存器中程序员可访问的是
若内存容量为4GB字长为32则
阅读下列说明回答问题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符号表示 7处填
阅读下列说明和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*/ 根据以上说明和C代码填充C代码中的空1～5
以下关于CPU的叙述中错误的是
设指令由取指分析执行3个子部件完成每个子部件的工作周期均为△t采用常规标量单流水线处理机若连续执行10条指令则共需时间△t
阅读下列说明和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代码函数heapMaximumheapExtractMax和maxHeaplnsert的时间复杂度的紧致上界分别为67和8用0符号表示
阅读下列说明回答问题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 7处填
计算机指令一般包括操作码和地址码两部分为分析执行一条指令其
处理机主要由处理器存储器和总线组成总线包括
海明校验码是在n个数据位之外增设k个校验位从而形成一个k+n位的新的码字使新的码字的码距比较均匀地拉大n与k的关系是
在输入输出控制方法中采用可以使得设备与主存间的数据块传送无需CPU干预
在CPU中可用于传送和暂存用户数据为ALU执行算术逻辑运算提供工作区
浮点数的一般表示形式为N=2E×F其中E为阶码F为尾数以下关于浮点表示的叙述中错误的是1两个浮点数进行相加运算应首先2 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*/ 2处填
内存采用段式存储管理有许多优点但不是其优点
计算机在进行浮点数的相加减运算之前先进行对阶操作若x的阶码大于y的阶码则应将
若某计算机采用8位整数补码表示数据则运算将产生溢出
以下关于cache的叙述中正确的是
阅读下列说明回答问题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 1处填
阅读下列说明和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*/ 设某有向无环图的顶点个数为n弧数为e那么用邻接表存储该图时实现上述拓扑排序算法的函数TopSort的时间复杂度为6若有向图采用邻接矩阵表示例如图21-13所示的有向图的邻接矩阵如图21-15所示且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作那么对于有n个顶点e条弧的有向无环图实现上述拓扑排序算法的时间复杂度为7[*]
是指按内容访问的存储器
阅读下列说明回答问题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 3处填
阅读下列说明和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*/ 4处填
为实现程序指令的顺序执行CPU中的值将自动加1
阅读下列说明和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代码分析该排序算法是否稳定若稳定请简要说明不超过100字若不稳定请修改其中代码使其稳定给出要修改的行号和修改后的代码
阅读下列说明和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代码填充C代码中的空缺1～4
设用2K×4位的存储器芯片组成16K×8位的存储器地址单元为0000H～3FFFH每个芯片的地址空间连续则地址单元0BIFH所在芯片的最小地址编号为
热门题库
更多
中级网络工程师
中级信息系统管理工程师
初级程序员
中级软件设计师
初级网络管理员
初级信息处理技术员
中级数据库系统工程师
中级多媒体应用设计师
高级系统分析师
高级网络规划设计师
高级系统架构师
中级信息系统监理师
初级通信工程师
中级通信工程师
通信新技术、新业务知识
无线通信专业技术
湘公网安备 43130202000226号