数据结构和算法常见试题分享|S34 _常见问题

GATE CS 2014考试中提出了以下问题。
1)考虑下面给出的伪代码。 DoSomething()函数将指向以leftMostChild-rightSibling表示形式表示的任意树的根作为指针的参数。树的每个节点的类型为treeNode。

typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value = http://www.srcmini.com/0; if (tree != NULL) { if (tree-> leftMostChild == NULL) value = 1; else value = DoSomething(tree-> leftMostChild); value = value + DoSomething(tree-> rightSibling); } return (value); }

将指向树根的指针作为DoSomething的参数传递时, 该函数返回的值对应于
(A)树中的内部节点数。
(二)树的高度。
(C)树中没有右兄弟的节点数。
(D)树中叶节点的数量。
答案：(D)
【数据结构和算法常见试题分享|S34】在此问题中要注意的重要事项是树的表示形式。树表示为最左侧的子级和右侧的同级窗体。因此, 如果某个节点的最左侧子节点为NULL, 则该节点没有子节点。如果我们看一下函数, 我们会注意到该函数仅对叶节点将” 值” 增加1。
2)假设发现了一种多项式时间算法, 该算法可以正确计算给定图中的最大集团。在这种情况下, 下列哪一项代表复杂度等级P, NP和NP Complete(NPC)的正确维恩图？

文章图片
(A)A
(B)B
(C)C
(D)D
答案：(D)
最大团是一个NP完全问题。如果一个NP完全问题可以在多项式时间内解决，那么所有的NP完全问题都可以在多项式时间内解决。所以NPC集合等于P。
以下是填空题
3)找到最小和最大100个数字所需的最小比较数为____。
答案：147
n个数字所需的最小比较数为3n/2 – 3。请参考方法3
使用最少数量的比较的数组的最大值和最小值
更多细节。
4)考虑两个字符串A =” qpqrr” 和B =” pqprqrp” 。设x为A和B之间最长公共子序列的长度(不一定是连续的), 而y为A和B之间最长公共子序列的数目。则x + 10y = ___。
答案：34
最长为4。有3个LCS, 长度为4″ qprr” , ” pqrr” 和” qpqr” 。
5)假设P, Q, R, S, T是长度分别为20、24、30、35、50的排序序列。通过一次将两个序列合并在一起, 将它们合并为一个序列。在最坏的情况下, 最佳算法执行此操作所需的比较次数为____。
答案：358
要合并大小为m和n的两个列表, 在最坏的情况下我们需要进行m + n-1比较。由于我们需要一次合并2个, 因此最佳策略是首先获取最小大小的列表。选择最小的两个项目的原因是要携带最少的项目以便在合并中重复。
我们首先合并20和24, 并使用43个最坏情况的比较得出44的列表。然后, 我们使用64种最坏情况的比较将30和35合并为65的列表。然后, 我们使用93个比较将50和44合并为94的列表。最后, 我们使用158个比较合并94和65。因此比较总数为43 + 64 + 93 + 158, 即358。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。