首页
试卷库
试题库
当前位置：
X题卡
>
所有题目
>
题目详情
某进程有5个页面，页号为0～4，页面变换表如下所示。表中状态位等于0和1分别表示页面不在内存或在内存。若系统给该进程分配了3个存储块，当访问的页面3不在内存时，应该淘汰表中页号为 (9) 的页面...
查看本题答案
包含此试题的试卷
中级软件设计师《单选集》真题及答案
点击查看
你可能感兴趣的试题
试题12进程P有6个页面页号分别为0～5页面大小为4K页面变换表如下所示表中状态位等于1和0分
165H
3165H
5165H
6165H
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存或在内存
2C25H
4096H
4C25H
8C25H
试题12进程P有6个页面页号分别为0～5页面大小为4K页面变换表如下所示表中状态位等于1和0分
1
2
5
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存和在内存
2C25H
4096H
4C25H
8C25H
进程P有6个页面页号分别为0～5页面大小为4K页面变换表如下所示表中状态位等于1和0分别表示页面在内
1
2
5
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存或在内存
1
2
4
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存和在内存
2C25H
4096H
4C25H
8C25H
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存和在内存
1
2
4
某系统采用请求页式存储管理方案假设某进程有6个页面系统给该进程分配了4个存储块其页面变换表如下表所
3
4
5
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存和在内存
1
2
4
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存或在内存
1
2
4
某系统采用请求页式存储管理方案假设某进程有6个页面系统给该进程分配了4个存储块其页面变换表如下
3
4
5
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存或在内存若系
0
1
2
4
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存和在内存
2C25H
4096H
4C25H
8C25H
进程P有6个页面页号分别为0～5页面大小为4K页面变换表如下所示表中状态位等于1和0分别表示页
1
2
5
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存和在内存
1
2
4
进程P有6个页面页号分别为0～5页面大小为4K页面变换表如下所示表中状态位等于1和0分别表示页
165H
3165H
5165H
6165H
进程P有6个页面页号分别为0～5页面大小为4K页面变换表如下所示表中状态位等于1和0分别表示页面在内
1165H
3165H
5165H
6165H
某进程有5个页面页号为0～4页面变换表如下所示表中状态位等于0和1分别表示页面不在内存或在内存若系
2C25H
4096H
4C25H
8C25H
某系统采用请求页式存储管理方案假设某进程有6个页面系统给该进程分配了4个存储块其页面变换表如下
2
5
8
12
热门试题
更多
阅读下列说明回答问题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处填
阅读以下说明和C语言函数将应填入n处的字句写在对应栏内 [说明] 在一个分布网络中资源石油天然气电力等可从生产地送往其他地方在传输过程中资源会有损耗例如天然气的气压会减少电压会降低我们将需要输送的资源信息称为信号在信号从信源地送往消耗地的过程中仅能容忍一定范围的信号衰减称为容忍值分布网络可表示为一个树形结构如图21-7所示信号源是树根树中的每个结点除了根表示一个可以放置放大器的子结点其中某些结点同时也是信号消耗点信号从一个结点流向其子结点 每个结点有一个d值表示从其父结点到该结点的信号衰减量例如在图21-7中结点wpq的d值分别为213树根结点表示信号源其d值为0 每个结点有一个M值表示从该结点出发到其所有叶子结点的信号衰减量的最大值显然叶子结点的M值为0对于非叶子结点jM[j=maxMk+dkk是j的孩子结点在此公式中要计算结点的M值必须先算出其所有子结点的M值 在计算M值的过程中对于某个结点i其有一个子结点k满足dk+Mk大于容忍值则应在k处放置放大器否则从结点i到某叶子结点的信号衰减量会超过容忍值使得到达该叶子结点时信号不可用而在结点i处放置放大器并不能解决到达叶子结点的信号衰减问题 例如在图21-7中从结点p到其所有叶子结点的最大衰减值为4若容忍值为3则必须在s处放置信号放大器这样可使得结点p的M值为2同样需要在结点qv处放置信号放大器如图21-8中阴影结点所示若在某结点放置了信号放大器则从该结点输出的信号与信号源输出的信号等价 函数placeBoostersTreeNode*root的功能是对于给定树形分布网络中各个结点计算其信号衰减量的最大值并确定应在树中的哪些结点放置信号放大器 全局变量Tolerance保存信号衰减容忍值 树的结点类型定义如下 typedefstructTreeNDde intid/*当前结点的识别号*/ intchildNum/*当前结点的子结点数目*/ intd/*父结点到当前结点的信号衰减值*/ structTreeNde**childptr/*向量存放当前结点到其所有子结点的指针*/ intM/*当前结点到其所有子结点的信号衰减值中的最大值*/ boolboost/*是否在当前结点放置信号放大器的标志*/ TreeNode [C语言函数] voidplaceB00stersTreeNode*root /*计算root所指结点处的衰减量如果衰减量超出了容忍值则放置放大器*/ TreeNode*p intidegradation if1 degradation=0root-＞M=0 i=0 ifi＞=root-＞ChildNum return p=2 fori＜root-＞ChildNum＆＆pi++p=3 p-＞M=0 4 ifp-＞d+p-＞M＞Tolerance/*在p所指结点中放置信号放大器*/ p-＞Doost=true p-＞M=0 ifp-＞d+p-＞M＞degradation degradation=p-＞d+p-＞M root-＞M=5 5处填
阅读下列说明回答问题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处填
阅读以下说明图和C代码将应填入n处的字句写在对应栏内 [说明] 一般的树结构常采用孩子一兄弟表示法表示即用二叉链表作为树的存储结构链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点例如如图21-6a所示的树的孩子一兄弟表示如图21-6b所示 函数LevelTraverse0的功能是对给定树进行层序遍历例如对如图21-6a所示的树进行层序遍历时结点的访问次序为DBAEFPC 对树进行层序遍历时使用了队列结构实现队列基本操作的函数原型如表21-1所示 BoolStatus类型定义如下 typedefenumFALSE=0TRUE=1Bool typedefenumOVERFLOW=-2UNDERFLOW=-1ERROR=0OK=1Status树的二叉链表结点定义如下 typedefstructNode chardata structNode*fimstchild*nextbrother Node*TreeNode [本题函数] StatusLeveiTraverseTreeNoderoot /*层序遍历树树采用孩子一兄弟表示法root是树根结点的指针*/ QueuetemQ TreeNodeptrbrotherptr if!root returnERROR InitQueue＆tempQ 1 brotherptr=root-＞nextbrother whilebrotherptr EnQueue＆tempQbrotherptr 2 /-end-while*/ while3 4 printf"%c/t"ptr-＞data if5continue 6 brotherptr=ptr-＞firstchild-＞nextbrother whilebrotherptr EnQueue＆tempQbrotherptr 7 /*end-while*/ /*end-while*/ returnOK /*LevelTraverse*/ 2处填
阅读以下说明和C语言函数将应填入n处的字句写在对应栏内 [说明] 在一个分布网络中资源石油天然气电力等可从生产地送往其他地方在传输过程中资源会有损耗例如天然气的气压会减少电压会降低我们将需要输送的资源信息称为信号在信号从信源地送往消耗地的过程中仅能容忍一定范围的信号衰减称为容忍值分布网络可表示为一个树形结构如图21-7所示信号源是树根树中的每个结点除了根表示一个可以放置放大器的子结点其中某些结点同时也是信号消耗点信号从一个结点流向其子结点 每个结点有一个d值表示从其父结点到该结点的信号衰减量例如在图21-7中结点wpq的d值分别为213树根结点表示信号源其d值为0 每个结点有一个M值表示从该结点出发到其所有叶子结点的信号衰减量的最大值显然叶子结点的M值为0对于非叶子结点jM[j=maxMk+dkk是j的孩子结点在此公式中要计算结点的M值必须先算出其所有子结点的M值 在计算M值的过程中对于某个结点i其有一个子结点k满足dk+Mk大于容忍值则应在k处放置放大器否则从结点i到某叶子结点的信号衰减量会超过容忍值使得到达该叶子结点时信号不可用而在结点i处放置放大器并不能解决到达叶子结点的信号衰减问题 例如在图21-7中从结点p到其所有叶子结点的最大衰减值为4若容忍值为3则必须在s处放置信号放大器这样可使得结点p的M值为2同样需要在结点qv处放置信号放大器如图21-8中阴影结点所示若在某结点放置了信号放大器则从该结点输出的信号与信号源输出的信号等价 函数placeBoostersTreeNode*root的功能是对于给定树形分布网络中各个结点计算其信号衰减量的最大值并确定应在树中的哪些结点放置信号放大器 全局变量Tolerance保存信号衰减容忍值 树的结点类型定义如下 typedefstructTreeNDde intid/*当前结点的识别号*/ intchildNum/*当前结点的子结点数目*/ intd/*父结点到当前结点的信号衰减值*/ structTreeNde**childptr/*向量存放当前结点到其所有子结点的指针*/ intM/*当前结点到其所有子结点的信号衰减值中的最大值*/ boolboost/*是否在当前结点放置信号放大器的标志*/ TreeNode [C语言函数] voidplaceB00stersTreeNode*root /*计算root所指结点处的衰减量如果衰减量超出了容忍值则放置放大器*/ TreeNode*p intidegradation if1 degradation=0root-＞M=0 i=0 ifi＞=root-＞ChildNum return p=2 fori＜root-＞ChildNum＆＆pi++p=3 p-＞M=0 4 ifp-＞d+p-＞M＞Tolerance/*在p所指结点中放置信号放大器*/ p-＞Doost=true p-＞M=0 ifp-＞d+p-＞M＞degradation degradation=p-＞d+p-＞M root-＞M=5 1处填
阅读下列说明回答问题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处填
阅读下列说明回答问题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处填
阅读以下说明和C语言函数将应填入n处的字句写在对应栏内 [说明] 在一个分布网络中资源石油天然气电力等可从生产地送往其他地方在传输过程中资源会有损耗例如天然气的气压会减少电压会降低我们将需要输送的资源信息称为信号在信号从信源地送往消耗地的过程中仅能容忍一定范围的信号衰减称为容忍值分布网络可表示为一个树形结构如图21-7所示信号源是树根树中的每个结点除了根表示一个可以放置放大器的子结点其中某些结点同时也是信号消耗点信号从一个结点流向其子结点 每个结点有一个d值表示从其父结点到该结点的信号衰减量例如在图21-7中结点wpq的d值分别为213树根结点表示信号源其d值为0 每个结点有一个M值表示从该结点出发到其所有叶子结点的信号衰减量的最大值显然叶子结点的M值为0对于非叶子结点jM[j=maxMk+dkk是j的孩子结点在此公式中要计算结点的M值必须先算出其所有子结点的M值 在计算M值的过程中对于某个结点i其有一个子结点k满足dk+Mk大于容忍值则应在k处放置放大器否则从结点i到某叶子结点的信号衰减量会超过容忍值使得到达该叶子结点时信号不可用而在结点i处放置放大器并不能解决到达叶子结点的信号衰减问题 例如在图21-7中从结点p到其所有叶子结点的最大衰减值为4若容忍值为3则必须在s处放置信号放大器这样可使得结点p的M值为2同样需要在结点qv处放置信号放大器如图21-8中阴影结点所示若在某结点放置了信号放大器则从该结点输出的信号与信号源输出的信号等价 函数placeBoostersTreeNode*root的功能是对于给定树形分布网络中各个结点计算其信号衰减量的最大值并确定应在树中的哪些结点放置信号放大器 全局变量Tolerance保存信号衰减容忍值 树的结点类型定义如下 typedefstructTreeNDde intid/*当前结点的识别号*/ intchildNum/*当前结点的子结点数目*/ intd/*父结点到当前结点的信号衰减值*/ structTreeNde**childptr/*向量存放当前结点到其所有子结点的指针*/ intM/*当前结点到其所有子结点的信号衰减值中的最大值*/ boolboost/*是否在当前结点放置信号放大器的标志*/ TreeNode [C语言函数] voidplaceB00stersTreeNode*root /*计算root所指结点处的衰减量如果衰减量超出了容忍值则放置放大器*/ TreeNode*p intidegradation if1 degradation=0root-＞M=0 i=0 ifi＞=root-＞ChildNum return p=2 fori＜root-＞ChildNum＆＆pi++p=3 p-＞M=0 4 ifp-＞d+p-＞M＞Tolerance/*在p所指结点中放置信号放大器*/ p-＞Doost=true p-＞M=0 ifp-＞d+p-＞M＞degradation degradation=p-＞d+p-＞M root-＞M=5 3处填
阅读下列说明和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处填
阅读下列说明图和C代码将应填入n处的字句写在对应栏内 [说明1] B树是一种多叉平衡查找树一棵m阶的B树或为空树或为满足下列特性的m叉树 ①树中每个结点至多有m棵子树 ②若根结点不是叶子结点则它至少有两棵子树 ③除根之外的所有非叶子结点至少有[m/2]棵子树 ④所有的非叶子结点中包含下列数据信息 nA0K1A1K2A2…K11A11 其中Ki=12…n为关键字且K＜Ki+1i=12…n-1Aii=01…n为指向子树根结点的指针且指针Ai-1所指子树中所有结点的关键字均小于KiAi+1所指子树中所有结点的关键字均大于Kin为结点中关键字的数目 ⑤所有的叶子结点都出现在同一层次上并且不带信息可以看作是外部结点或查找失败的结点实际上这些结点不存在指向这些结点的指针为空 例如一棵4阶B树如图21-4所示结点中关键字的数目省略 B树的阶mBool类型关键字类型及B树结点的定义如下 #defineM4/*B树的阶数*/ typedefenumFALSE=0TRUE=1bool typedefintE1emKeyType typedefstructBTreeNode intnumkeys/*结点中关键字的数目*/ structBTreeNode*parent/*指向父结点的指针树根的父结点指针为空*/ StructBTreeNode*A[M]/*指向子树结点的指针数组*/ ElemKeyTypeK[M]/*存储关键字的数组K[0]闲置不用*/ BTreeNode 函数SearchBtreeBTreeNode*rootElemKeyTypeakeyBTreeNode**ptr的功能是在给定的一棵m阶B树中查找关键字akey所在结点若找到则返回TRUE否则返回FALSE其中root是指向该m阶B树根结点的指针参数ptr返回akey所在结点的指针若akey不在该B树中则ptr返回查找失败时空指针所在结点的指针例如在如图21-4所示的4阶B树中查找关键字akey时ptr返回指向结点e的指针 注在结点中查找关键字akey时采用二分法 [本题函数] boolSearchBtreeBTreeNode*rootElemKeyTypeakeyBTreeNode**ptr intlwhikmid BTreeNode*P=root *ptr=NULL whilep lw=1hi=1 whilelw＜=hi mid=lw+hi/2 ifp-＞K[mid]==akey *ptr=p returnTRUE else if2 hi=mid-1 else lw=mid+1 *ptr=p p=3 returnFALSE [说明2] 在m阶B树中插入一个关键字时首先在最接近外部结点的某个非叶子结点中增加一个关键字若该结点中关键字的个数不超过m-1则完成插入否则要进行结点的“分裂”处理所谓“分裂”就是把结点中处于中间位置上的关键字取出来并插入其父结点中然后以该关键字为分界线把原结点分成两个结点“分裂”过程可能会一直持续到树根若树根结点也需要分裂则整棵树的高度增1 例如在如图21-4所示的B树中插入关键字25时需将其插入结点e中由于e中已经有3个关键字因此将关键字24插入结点e的父结点b中并以24为分界线将结点e分裂为e1和e2两个结点结果如图21-5所示 函数IsgrowingBTreeNode*rootElemKeyTypeakey的功能是判断在给定的m阶B树中插入关键字akey后该B树的高度是否增加若增加则返回TRUE否则返回FALSE其中root是指向该m阶B树根结点的指针 在函数Isgrowing中首先调用函数SearchBtree查找关键字akey是否在给定的m阶B树中若在则返回FALSE表明无须插入关键字akey树的高度不会增加否则通过判断结点中关键字的数目考察插入关键字akey后该B树的高度是否增加 [本题函数] boolIsgrowingBTreeNode*rootElenlKeyTypeakey BTreeNode*t*f if!SearchBtree4 t=f while5 t=t-＞parent if!t returnTRUE:// returnFALSE:// 1处填
阅读以下说明图和C代码将应填入n处的字句写在对应栏内 [说明] 一般的树结构常采用孩子一兄弟表示法表示即用二叉链表作为树的存储结构链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点例如如图21-6a所示的树的孩子一兄弟表示如图21-6b所示 函数LevelTraverse0的功能是对给定树进行层序遍历例如对如图21-6a所示的树进行层序遍历时结点的访问次序为DBAEFPC 对树进行层序遍历时使用了队列结构实现队列基本操作的函数原型如表21-1所示 BoolStatus类型定义如下 typedefenumFALSE=0TRUE=1Bool typedefenumOVERFLOW=-2UNDERFLOW=-1ERROR=0OK=1Status树的二叉链表结点定义如下 typedefstructNode chardata structNode*fimstchild*nextbrother Node*TreeNode [本题函数] StatusLeveiTraverseTreeNoderoot /*层序遍历树树采用孩子一兄弟表示法root是树根结点的指针*/ QueuetemQ TreeNodeptrbrotherptr if!root returnERROR InitQueue＆tempQ 1 brotherptr=root-＞nextbrother whilebrotherptr EnQueue＆tempQbrotherptr 2 /-end-while*/ while3 4 printf"%c/t"ptr-＞data if5continue 6 brotherptr=ptr-＞firstchild-＞nextbrother whilebrotherptr EnQueue＆tempQbrotherptr 7 /*end-while*/ /*end-while*/ returnOK /*LevelTraverse*/ 4处填
阅读下列说明回答问题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处填
阅读下列说明图和C代码将应填入n处的字句写在对应栏内 [说明1] B树是一种多叉平衡查找树一棵m阶的B树或为空树或为满足下列特性的m叉树 ①树中每个结点至多有m棵子树 ②若根结点不是叶子结点则它至少有两棵子树 ③除根之外的所有非叶子结点至少有[m/2]棵子树 ④所有的非叶子结点中包含下列数据信息 nA0K1A1K2A2…K11A11 其中Ki=12…n为关键字且K＜Ki+1i=12…n-1Aii=01…n为指向子树根结点的指针且指针Ai-1所指子树中所有结点的关键字均小于KiAi+1所指子树中所有结点的关键字均大于Kin为结点中关键字的数目 ⑤所有的叶子结点都出现在同一层次上并且不带信息可以看作是外部结点或查找失败的结点实际上这些结点不存在指向这些结点的指针为空 例如一棵4阶B树如图21-4所示结点中关键字的数目省略 B树的阶mBool类型关键字类型及B树结点的定义如下 #defineM4/*B树的阶数*/ typedefenumFALSE=0TRUE=1bool typedefintE1emKeyType typedefstructBTreeNode intnumkeys/*结点中关键字的数目*/ structBTreeNode*parent/*指向父结点的指针树根的父结点指针为空*/ StructBTreeNode*A[M]/*指向子树结点的指针数组*/ ElemKeyTypeK[M]/*存储关键字的数组K[0]闲置不用*/ BTreeNode 函数SearchBtreeBTreeNode*rootElemKeyTypeakeyBTreeNode**ptr的功能是在给定的一棵m阶B树中查找关键字akey所在结点若找到则返回TRUE否则返回FALSE其中root是指向该m阶B树根结点的指针参数ptr返回akey所在结点的指针若akey不在该B树中则ptr返回查找失败时空指针所在结点的指针例如在如图21-4所示的4阶B树中查找关键字akey时ptr返回指向结点e的指针 注在结点中查找关键字akey时采用二分法 [本题函数] boolSearchBtreeBTreeNode*rootElemKeyTypeakeyBTreeNode**ptr intlwhikmid BTreeNode*P=root *ptr=NULL whilep lw=1hi=1 whilelw＜=hi mid=lw+hi/2 ifp-＞K[mid]==akey *ptr=p returnTRUE else if2 hi=mid-1 else lw=mid+1 *ptr=p p=3 returnFALSE [说明2] 在m阶B树中插入一个关键字时首先在最接近外部结点的某个非叶子结点中增加一个关键字若该结点中关键字的个数不超过m-1则完成插入否则要进行结点的“分裂”处理所谓“分裂”就是把结点中处于中间位置上的关键字取出来并插入其父结点中然后以该关键字为分界线把原结点分成两个结点“分裂”过程可能会一直持续到树根若树根结点也需要分裂则整棵树的高度增1 例如在如图21-4所示的B树中插入关键字25时需将其插入结点e中由于e中已经有3个关键字因此将关键字24插入结点e的父结点b中并以24为分界线将结点e分裂为e1和e2两个结点结果如图21-5所示 函数IsgrowingBTreeNode*rootElemKeyTypeakey的功能是判断在给定的m阶B树中插入关键字akey后该B树的高度是否增加若增加则返回TRUE否则返回FALSE其中root是指向该m阶B树根结点的指针 在函数Isgrowing中首先调用函数SearchBtree查找关键字akey是否在给定的m阶B树中若在则返回FALSE表明无须插入关键字akey树的高度不会增加否则通过判断结点中关键字的数目考察插入关键字akey后该B树的高度是否增加 [本题函数] boolIsgrowingBTreeNode*rootElenlKeyTypeakey BTreeNode*t*f if!SearchBtree4 t=f while5 t=t-＞parent if!t returnTRUE:// returnFALSE:// 5处填
阅读以下说明和C代码将应填入n处的字句写在对应栏内 [说明] 在一个简化的绘图程序中支持的图形种类有点point和圆ckcle在设计过程中采用面向对象思想认为所有的点和圆都是一种图形shape并定义了类型shape_tpoint_t和circle_t分别表示基本图形点和圆并且点和圆具有基本图形的所有特征 [C代码] typedefenumpointcircleshape_type/*程序中的两种图形点和圆*/ typedefstruct/*基本的图形类型*/ shape_typetype/*图形种类标识点或者圆*/ void*destroy/*销毁图形操作的函数指针*/ void*draw/*绘制图形操作的函数指针*/ shape_t typedefstructshape_tcommonintxintypoint_t /*定义点类型xy为点坐标*/ voiddestroyPointpoint_t*thisfreethisprintf"Pointdestoryed!/n" /*销毁点对象*/ voiddrawPointpoint_t*thisprintf"P%d%d"this-＞xthis-＞y /*绘制点对象*/ shape_t*createPointva_list*ap/*创建点对象并设置其属性*/ point_t*p_point ifp_point=point_t*mallocsizeofpoint_t==NULLreturnNULL p_point-＞common.type=pointp_point-＞common.destroy=destroyPoint p_point-＞common.draw=drawPoint p_point-＞x=va_arg*apint/*设置点的横坐标*/ p_point-＞y=va_arg*apint/*设置点的纵坐标*/ returnshape_t*p_point/*返回点对象指针*/ typedefstruct/*定义圆类型*/ shape_tcommon point_t*center/*圆心点*/ intradius/*圆半径*/ circle_t voiddestroyCircleCircle_t*this free1freethisprintf"Circledestoryed!/n" voiddrawCircleCircle_t*this printf＜"C＜"＞ 2.drawthis-＞center/*绘制圆心*/ printf".%d"this-＞radius shape_t*createCircleva_list*ap/*创建一个圆并设置其属性*/ Circle_t*p_circle ifp_circle=circle_t*mallocSizeofcircle_t==NULLreturnNULL p_circle-＞common.type=circlep_circle-＞common.destroy=destroyCircle p_circle-＞common.draw=drawCircle 3=createPointap/*设置圆心*/ p_circle-＞radius=va_arg*apint/*设置圆半径*/ returnp_circle shape_t*createShapeshape_typest…/*创建某一种具体的图形*/ va_listap/*可变参数列表*/ shape_t*p_shape=NULL 4apst ifst==pointp_shape=createPoint＆ap/*创建点对象*/ ifst==circlep_shape=createCircle＆ap/*创建圆对象*/ va_endap returnp_shape intmain inti/*循环控制变量用于循环计数*/ shape_t*shapes[2]/*图形指针数组存储图形的地址*/ shapes[0]=createShapepoint23/*横坐标为2纵坐标为3*/ shapes[1]=createShapeCircle204010 /*圆心坐标为2040半径为10*/ fori=0i＜2i++shapes[i]-＞drawshapes[i]printf"/n" /*绘制数组中图形*/ fori=1i＞=0i--shapes[i]-＞destroyshapes[i] /*销毁数组中图形*/ return0 [运行结果] P23 5 Circledestoryed! Pointdestoryed! 2处填
阅读下列说明回答问题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处填
阅读下列说明和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处填
阅读以下说明图和C代码将应填入n处的字句写在对应栏内 [说明] 一般的树结构常采用孩子一兄弟表示法表示即用二叉链表作为树的存储结构链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点例如如图21-6a所示的树的孩子一兄弟表示如图21-6b所示 函数LevelTraverse0的功能是对给定树进行层序遍历例如对如图21-6a所示的树进行层序遍历时结点的访问次序为DBAEFPC 对树进行层序遍历时使用了队列结构实现队列基本操作的函数原型如表21-1所示 BoolStatus类型定义如下 typedefenumFALSE=0TRUE=1Bool typedefenumOVERFLOW=-2UNDERFLOW=-1ERROR=0OK=1Status树的二叉链表结点定义如下 typedefstructNode chardata structNode*fimstchild*nextbrother Node*TreeNode [本题函数] StatusLeveiTraverseTreeNoderoot /*层序遍历树树采用孩子一兄弟表示法root是树根结点的指针*/ QueuetemQ TreeNodeptrbrotherptr if!root returnERROR InitQueue＆tempQ 1 brotherptr=root-＞nextbrother whilebrotherptr EnQueue＆tempQbrotherptr 2 /-end-while*/ while3 4 printf"%c/t"ptr-＞data if5continue 6 brotherptr=ptr-＞firstchild-＞nextbrother whilebrotherptr EnQueue＆tempQbrotherptr 7 /*end-while*/ /*end-while*/ returnOK /*LevelTraverse*/ 6处填
阅读下列说明回答问题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代码将应填入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处填
阅读以下说明和C代码将应填入n处的字句写在对应栏内 [说明] 在一个简化的绘图程序中支持的图形种类有点point和圆ckcle在设计过程中采用面向对象思想认为所有的点和圆都是一种图形shape并定义了类型shape_tpoint_t和circle_t分别表示基本图形点和圆并且点和圆具有基本图形的所有特征 [C代码] typedefenumpointcircleshape_type/*程序中的两种图形点和圆*/ typedefstruct/*基本的图形类型*/ shape_typetype/*图形种类标识点或者圆*/ void*destroy/*销毁图形操作的函数指针*/ void*draw/*绘制图形操作的函数指针*/ shape_t typedefstructshape_tcommonintxintypoint_t /*定义点类型xy为点坐标*/ voiddestroyPointpoint_t*thisfreethisprintf"Pointdestoryed!/n" /*销毁点对象*/ voiddrawPointpoint_t*thisprintf"P%d%d"this-＞xthis-＞y /*绘制点对象*/ shape_t*createPointva_list*ap/*创建点对象并设置其属性*/ point_t*p_point ifp_point=point_t*mallocsizeofpoint_t==NULLreturnNULL p_point-＞common.type=pointp_point-＞common.destroy=destroyPoint p_point-＞common.draw=drawPoint p_point-＞x=va_arg*apint/*设置点的横坐标*/ p_point-＞y=va_arg*apint/*设置点的纵坐标*/ returnshape_t*p_point/*返回点对象指针*/ typedefstruct/*定义圆类型*/ shape_tcommon point_t*center/*圆心点*/ intradius/*圆半径*/ circle_t voiddestroyCircleCircle_t*this free1freethisprintf"Circledestoryed!/n" voiddrawCircleCircle_t*this printf＜"C＜"＞ 2.drawthis-＞center/*绘制圆心*/ printf".%d"this-＞radius shape_t*createCircleva_list*ap/*创建一个圆并设置其属性*/ Circle_t*p_circle ifp_circle=circle_t*mallocSizeofcircle_t==NULLreturnNULL p_circle-＞common.type=circlep_circle-＞common.destroy=destroyCircle p_circle-＞common.draw=drawCircle 3=createPointap/*设置圆心*/ p_circle-＞radius=va_arg*apint/*设置圆半径*/ returnp_circle shape_t*createShapeshape_typest…/*创建某一种具体的图形*/ va_listap/*可变参数列表*/ shape_t*p_shape=NULL 4apst ifst==pointp_shape=createPoint＆ap/*创建点对象*/ ifst==circlep_shape=createCircle＆ap/*创建圆对象*/ va_endap returnp_shape intmain inti/*循环控制变量用于循环计数*/ shape_t*shapes[2]/*图形指针数组存储图形的地址*/ shapes[0]=createShapepoint23/*横坐标为2纵坐标为3*/ shapes[1]=createShapeCircle204010 /*圆心坐标为2040半径为10*/ fori=0i＜2i++shapes[i]-＞drawshapes[i]printf"/n" /*绘制数组中图形*/ fori=1i＞=0i--shapes[i]-＞destroyshapes[i] /*销毁数组中图形*/ return0 [运行结果] P23 5 Circledestoryed! Pointdestoryed! 4处填
阅读下列说明图和C代码将应填入n处的字句写在对应栏内 [说明1] B树是一种多叉平衡查找树一棵m阶的B树或为空树或为满足下列特性的m叉树 ①树中每个结点至多有m棵子树 ②若根结点不是叶子结点则它至少有两棵子树 ③除根之外的所有非叶子结点至少有[m/2]棵子树 ④所有的非叶子结点中包含下列数据信息 nA0K1A1K2A2…K11A11 其中Ki=12…n为关键字且K＜Ki+1i=12…n-1Aii=01…n为指向子树根结点的指针且指针Ai-1所指子树中所有结点的关键字均小于KiAi+1所指子树中所有结点的关键字均大于Kin为结点中关键字的数目 ⑤所有的叶子结点都出现在同一层次上并且不带信息可以看作是外部结点或查找失败的结点实际上这些结点不存在指向这些结点的指针为空 例如一棵4阶B树如图21-4所示结点中关键字的数目省略 B树的阶mBool类型关键字类型及B树结点的定义如下 #defineM4/*B树的阶数*/ typedefenumFALSE=0TRUE=1bool typedefintE1emKeyType typedefstructBTreeNode intnumkeys/*结点中关键字的数目*/ structBTreeNode*parent/*指向父结点的指针树根的父结点指针为空*/ StructBTreeNode*A[M]/*指向子树结点的指针数组*/ ElemKeyTypeK[M]/*存储关键字的数组K[0]闲置不用*/ BTreeNode 函数SearchBtreeBTreeNode*rootElemKeyTypeakeyBTreeNode**ptr的功能是在给定的一棵m阶B树中查找关键字akey所在结点若找到则返回TRUE否则返回FALSE其中root是指向该m阶B树根结点的指针参数ptr返回akey所在结点的指针若akey不在该B树中则ptr返回查找失败时空指针所在结点的指针例如在如图21-4所示的4阶B树中查找关键字akey时ptr返回指向结点e的指针 注在结点中查找关键字akey时采用二分法 [本题函数] boolSearchBtreeBTreeNode*rootElemKeyTypeakeyBTreeNode**ptr intlwhikmid BTreeNode*P=root *ptr=NULL whilep lw=1hi=1 whilelw＜=hi mid=lw+hi/2 ifp-＞K[mid]==akey *ptr=p returnTRUE else if2 hi=mid-1 else lw=mid+1 *ptr=p p=3 returnFALSE [说明2] 在m阶B树中插入一个关键字时首先在最接近外部结点的某个非叶子结点中增加一个关键字若该结点中关键字的个数不超过m-1则完成插入否则要进行结点的“分裂”处理所谓“分裂”就是把结点中处于中间位置上的关键字取出来并插入其父结点中然后以该关键字为分界线把原结点分成两个结点“分裂”过程可能会一直持续到树根若树根结点也需要分裂则整棵树的高度增1 例如在如图21-4所示的B树中插入关键字25时需将其插入结点e中由于e中已经有3个关键字因此将关键字24插入结点e的父结点b中并以24为分界线将结点e分裂为e1和e2两个结点结果如图21-5所示 函数IsgrowingBTreeNode*rootElemKeyTypeakey的功能是判断在给定的m阶B树中插入关键字akey后该B树的高度是否增加若增加则返回TRUE否则返回FALSE其中root是指向该m阶B树根结点的指针 在函数Isgrowing中首先调用函数SearchBtree查找关键字akey是否在给定的m阶B树中若在则返回FALSE表明无须插入关键字akey树的高度不会增加否则通过判断结点中关键字的数目考察插入关键字akey后该B树的高度是否增加 [本题函数] boolIsgrowingBTreeNode*rootElenlKeyTypeakey BTreeNode*t*f if!SearchBtree4 t=f while5 t=t-＞parent if!t returnTRUE:// returnFALSE:// 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符号表示 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函数将应填入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处填
热门题库
更多
中级网络工程师
中级信息系统管理工程师
初级程序员
中级软件设计师
初级网络管理员
初级信息处理技术员
中级数据库系统工程师
中级多媒体应用设计师
高级系统分析师
高级网络规划设计师
高级系统架构师
中级信息系统监理师
初级通信工程师
中级通信工程师
通信新技术、新业务知识
无线通信专业技术
湘公网安备 43130202000226号