首页 > 职业技能鉴定

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

[主观题]

问题描述:给定一棵有向树T;树T中每个顶点u都有权值w(u),树的每条边(u,v)都有一个非负边长d(u,

问题描述:给定一棵有向树T;树T中每个顶点u都有权值w（u),树的每条边（u,v)都有一个非负边长d（u,

v).有向树T的每个顶点u可以看作客户,其服务需求量为w(u).每条边(u,v)的边长d(u,v)可以看作运输费用.如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构需付出的服务转移费用为w(u)×d(u,v).树根处已设置了服务机构,现在要在树T中增设k处独立服务机构,使得整棵树T的服务转移费用最小.服务机构的独立性是指任例两个服务机构之间都不存在有向路径.

算法设计:对于给定的有向树T:计算在树T中增设k处独立服务机构的最小服务转移费用.

数据输入:由文件input.txt.给出输入数据.第1行有2个正整数n和k.n表示有向树T的边数:k是要增设的服务机构数.有向树T的顶点编号为0,1,...,n.根结点编号为0.接下来的n行中,每行存表示有向树T的一条有向边的3个整数.第i+1行的3个整数w_i、v_i、d_i分别表示编号为i的顶点的权为w_i,相应的有向边为(i,v_i),其边长为d_i.

结果输出:将计算的最小服务转移费用输出到文件output.txt.

问题描述:给定一棵有向树T;树T中每个顶点u都有权值w（u),树的每条边（u,v)都有一个非负边长d

查看答案

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

您可能会需要：

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

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

更多“问题描述:给定一棵有向树T;树T中每个顶点u都有权值w(u)…”相关的问题

第1题

任给高度分别为g和h的两棵AVL树S和T，且S中的节点均不大于T中的节点。试设计一个算法，在O（max（g，h))时间内将它们合并为一棵AVL树。

点击查看答案

第2题

任给高度为h的一棵AVL树A，以及一个关键码e。试设计一个算法，在O（h)时间内将A分裂为一对AVL树S和T，且S中的节点均小于e，而T中的节点均不小于e。

点击查看答案

第3题

？？阅读下面的现代文，回答下列问题。一棵有毒的树矗立在路旁。第一种人大老远看见了，赶紧绕路而行，

？？阅读下面的现代文，回答下列问题。

一棵有毒的树矗立在路旁。

第一种人大老远看见了，赶紧绕路而行，他们一点也不愿接近，深怕不小心会中毒。

第二种人，来到了树边，看见这棵树，马上就想到它的毒素，急着要砍除它，以免有人受害。

第三种人有着不同的心态，愿意带着慈悲心去思索：这棵树也有生命，不要轻易地毁掉。于是在树旁圈上篱笆，注明有毒，以此避免危害到路人。

至于第四种人，在看见这棵树的时候，会说：“喔!一棵有毒的树，太好了，这正是我要的!”。他们开始研究树的毒性，提炼了毒素，与其他成分混合，制成了可以救人的药材。你认为人生是什么呢？如果有一个造句，“人生是……”或“人生像……”，你会怎么完成这个句子呢？用直觉，就是脑海里直接浮现出来的答案，我们不是在写作文或进行造句，不需要修饰成优美的语句。

“我的答案是人生如戏”，一位看起来吊儿郎当，凡事不在乎的男士可能会这样说。

“从小我看着爸爸妈妈为这个家打拼，一直认为人生是很艰辛的。”即使这位女学员没有说出来，从她愁眉不展的神情，也可以猜想得到答案。“人生是一场无休止的竞赛”，这位学员有着非常明显的“宁为鸡首，不为牛后”以及“只有第一，没有第二”的刚毅性格。难怪他说自己当年没有考上第一志愿的高中，就放弃已考上的第二志愿，毅然去当兵。

还有人说“人生是来还债”，这样的想法，虽然宽慰了受到创伤或不平待遇时的怅惘，但回答这个问题的学员，似乎有着很深的无奈。

人生到底像什么？这的确是个见仁见智的问题，然而也正是因为有这么多种对人生不同的态度，形成了各不相同的生命剧本。我们对人生的诠释，其实也就是内在潜意识的外在表现，自然也就活出那种形态的生命形式。于是我们看到，有些人终其一生，始终扮演着苦情哀怨的主角;有些人虽然会赚钱，但却始终留不住钱;有些人最擅长演出的就是悲剧英雄。

还有一位学员在课堂上赫然发现，自己不论在婚前、婚后，在家庭、公司，虽然是有女儿、太太、媳妇、职员等各种不同称呼，但总括而言，结果只有一个——为别人活，完全没有自我。“人生永远是朝向你所思考的方向前进”，就像开头故事中的那棵树，你用不同的方式对待，就会导致不同的结果。

你认为人生像什么呢？倒数第3自然段中“完全没有自我”的含义是什么？

？？

？？在第8自然段中,作者说，回答“人生是什么”的问题要“用直觉，就是在脑海中直接浮现出来的答案”,这句话的具体含义是什么？人们回答“人生是什么”的问题，出现不同答案的原因是什么？？？

第1自然段中“一棵有毒的树”比喻什么？

分别用不超过4个字的词语概括文中所述四种人的特点。

(1)第一种人：__________

(2)第二种人：__________

(3)第三种人：__________

(4)第四种人：__________

本文开头描述四种人对有毒的树的不同心态的作用是什么？

请帮忙给出每个问题的正确答案和分析，谢谢！

点击查看答案

第4题

下列关于语法树的描述中，错误的是（)。A语法树的根结由开始符号所标记B一棵语法树表示了一个句型

下列关于语法树的描述中，错误的是()。

A语法树的根结由开始符号所标记

B一棵语法树表示了一个句型所有的不同推导过程

C一棵语法树是不同推导过程的共性抽象，是它们的代表

D一个句型不是只有唯一的一棵语法树

点击查看答案

第5题

问题描述:试设计一个用优先队列式分支限界法搜索排列空间树的函数,其参数包括结点可行性判定

雨数和上界的数等必要的函数,并将此函数用于解批处理作业调度问题.给定n个作业的集合

.每个作业J_i都有2项任务分别在2台机器上完成.每个作业必须先由机器1处理,再由机器2处理.作业J_i需要机器j的处理时间为t_ij(=1,2,...,n;j=1,2).对于一个确定的作业调度,设F_ij是作业i在机器j上完成处理的时间.所有作业在机器2上完成处理的时间和

称为该作业调度的完成时间和.

批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.

算法设计:对于给定的n个作业,计算最佳作业调度方案.

数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.

结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.

点击查看答案

第6题

所谓半无穷范围查询（semi-infinite range query)，是教材8.4节中所介绍一般性范围查询的特例，具

所谓半无穷范围查询(semi-infinite range query)，是教材8.4节中所介绍一般性范围查询的特例，具体地，这里的查询区域是某一侧无界的广义矩形区域，比如R=[-1，+1]x[0，﹢∞)，即是对称地包含正半y坐标轴、宽度为2的一个广义矩形区域，当然，对查询的语义功能要求依然不变——从某一相对固定的点集中，找出落在任意指定区域R内部的所有点。

范围树(176页习题[8-20])稍作调整之后，固然也可交持半无穷范围查询，但若能针对这一特定问题所固有的性质，改用优先级搜索树(priority search tree，PST)之类的数据结构，则不仅可以保持O(r+logn)的最优时间效率，而且更重要的是，可以将空间复杂度从范围树的O(nlogn)优化至O(n)。

如图x10.3所示，优先级搜索树除了首先在拓扑上应是一棵二叉树，还同时遵守以下三条规则。

①首先，各节点的y坐标均不小于其左右孩子(如果存在)——因此，整体上可以视作为以y坐标为优先级的二叉堆。

②此外，相对于任一父节点，左子树中节点的x坐标均不得大于右子树中的节点。

③最后，互为兄弟的每一对左、右子树，在规模上相差不得超过一。

a)试按照以上描述，用C/C++定义并实现优先级搜索树结构;

b)试设计一个算法，在O(nlogn)时间内将平面上的n个点组织为一棵优先级搜索树;

c)试设计一个算法，利用已创建的优先级搜索树，在O(r+logn)时间内完成每次半无穷范围查询，其中r为实际命中并被报告的点数。

点击查看答案

第7题

问题描述:试设计一个用回溯法搜索子集空间树的函数.该函数的参数包括结点可行性判定函数和上

界函数等必要的函数,并将此函数用于解装载问题.

装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的重量为wi.找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.

算法设计:对于给定的n个集装箱的重量和轮船的重量,计算最优装载方案.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.

结果输出:将计算的最大装载重量输出到文件output.txt.

点击查看答案

第8题

问题描述:假设煤在足够多的会场里运排一批活动,并希望使用尽可能少的会场.设计一个有效的贪心

算法进行安排.(这个问题实际上是著名的图着色问题.若将每个活动作为图的一个顶点,不相容活动间用边相连.使相邻顶点着有不同颜色的最小着色数,相当于要找的最小会场数.)

算法设计:对于给定的k个待安排的活动,计算使用最少会场的时间表.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待安排的活动.接下来的k行中,每行有2个正整数,分别表示k个待安排的活动的开始时间和结束时间.时间以0点开始的分钟计.

结果输出:将计算的最少会场数输出到文件output.txt.

点击查看答案

第9题

给定文法G=（{σ,A},{0,1},P,σ),其中P:a→0_σ,a→1A,σ→0,A→0A,A→1_σ,A→1,描述L（G),写出00101的派生过程并画出派生树。

点击查看答案

第10题

下列有关树的叙述中不正确的是【】

A.二叉树中每个结点有两个子结点，而树无此限制，因此二叉树是树的特殊情况

B.当K≥1时高度为K的二叉树至多有2k-l个结点

C.将一棵树转换成二叉树后，根结点没有左子树

D.哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近

点击查看答案

第11题

对于图7-41,利用Kruskal算法求一棵最小生成树。

点击查看答案

长沙图香大数据有限公司版权所有 ©2024

湘ICP备20011576号-2 营业执照

违法和不良信息举报电话：400-118-7898

举报/反馈/投诉邮箱：deng＃ujigu.com（请将＃替换成@）