(۰۹ اسفند ۱۳۹۰ ۱۰:۱۰ ق.ظ)aliebtehaj نوشته شده توسط: (09 اسفند ۱۳۹۰ ۰۲:۰۱ ق.ظ)LordAriana نوشته شده توسط: مجموعه مهندسی کامپیوتر
سوال ۵۰ ساختمان داده گزینه ۳ صحیح می باشد که در دفترچه A اشتباه زده شده
سوال ۱۱۱ با مفروضات مساله جواب (E+V) نمی شود، تنها اگر مقدار C=1بوده و یا ذکر شده باشد که وزن تمام یال ها برابر با C هست، این جواب صحیح می باشد
سوال ۱۱۴ ازلحاظ مفهومی ایراد دارد، چون در سایت دانشگاه UCLA روش حل Diameter هم با DFS و هم با BFS وجود دارد و محقق آن اعلام کرده که هردو دارای یک مرتبه هستند (حالا این طراح گلابی رفته ۱ تمرین تو CLRS دیده این سوال رو مثلا طرح کرده)
سوال ۱۲۰ هوش مصنوعی در جوابش ابهام هست
سوال ۱۲۱ هوش مصنوعی در سوالش ابهام هست که بسته به زاویه دید دوستان، یکسری B=2 و عده ای بین ۲/۳ اعلام کردند و راه حل هاشون موجود است و می توانند اعتراض کنند، شاید این سوال حذف شود
دقیقاً همینه که شما میگید در ضمن ۴۷ به دلیل ابهام باید ۲ تا گزینه درست بزنند و ۶۰ هم گزینه ۴ و همچنین ۱۱۲ هم شک داره نه ۱ درسته نه ۴ (به دلیل اینکه گفته فاصله هر راس از خودش ۰ است اینو واسه قشنگی که اون پایین سوال نزاشتن در غیر اینصورت ابهام داشته)
بچه ها فقط من یه چیو بگم دقت کنید سوالات مشترک که خوب یک سری ها معلومه که مشکل دارن و باید اعتراض کنید ولی سوالات تخصصی هم حتماً یادتون باشه چون حتی اگه یک سوال بنفعمون بشه یعنی غلطمون بشه درست نزدیک ۹ درصد میایم بالا
و کلی رتبه ها جابجا می شه پس خیلی روی تخصصی ها مانور بدین (هر چند حرف ما مهم نیس بلکه سلیقه طراح مهمه
)
اینم برای سوال ۱۱۴
۱/ Consider a connected, positively weighted, undirected graph, we define the “length”
between two nodes as the (weighted) length of the shortest path connecting them.
The diameter of a graph is then the longest such length over all pair of nodes. Since
the graph is connected, the diameter won’t be infinity. In the questions below, |V| =
number of nodes in the graph.
a. [5] Give an O(|V|^3) algorithm that will find the diameter of a graph.
b. [5] Give an O(|V|) algorithm that will find the diameter of an unweighted tree.
(recall that a tree is a connected acyclic undirected graph)
For part a, we can find all the shortest paths, and find the maximum one.
e.g.:
{۲} Get all shortest paths.
{۳} With Floyd-Warshall, that takes O(|V|^3) time. An extra O(|V|^2) time to search
the shortest paths between all pairs will give the answer.
For part b, we can use BFS and / or DFS
Using BFS:
{۳} Choose arbitrary start point, s . Run a BFS to find the furthest node, say u .
{۲} Run a second BFS from u , and the distance to the furthest node is the diameter.
(Prove it!)
Using DFS:
{۳} Run DFS from arbitrary start point. At each node keep track of the length of it’s
longest leaf (LLF). Do this by taking the maximum LLF of its children + 1.
{۲} Calculate what’s the longest path that go through each node, by adding up the two
distinct children with the largest LLF’s. (If there isn’t enough children, use 0).
Note: In both cases, DFS/BFS runs in O(|V| + |M|) = O(|V|) since M = V-1 for a tree.
(Use adjacency list).
چند تا از سوال های سیستم عامل فقط ۱۰ دقیقه وقت می خواست تا صورت سوال بخوانیم .
