微信

使用微信服务,更方便

职友集>程序员面试题 > 算法笔试题

算法笔试题

2015-07-03 06:30:01 阅读( 67 )

1731人 收藏本页

标签:程序员面试题

1. [25 points] A binary tree is full if all of its vertices have either zero or two children. Let Bn
denote the number of full binary trees with n vertices.
(a) By drawing out all full binary trees with 3, 5, and 7 vertices, determine the exact values
of B3 , B5 , and B7 .
(b) Why have we left out full binary trees with even number of vertices, like B4, in part (a)?
(c) For general n, derive a recurrence relation for Bn .
(d) Show by induction (substitution) that Bn is 2
(n) .
2. [25 points] Consider the problem of merging two sorted arrays A and B of n elements each
into one sorted array C of 2n elements. This problem asks you to prove that the minimum
number of comparisons to perform this task is 2n − 1. The problem is split into two parts:
a) Show that if two elements x ∈ A and y ∈ B are consecutive in C, then they must be
compared.
b) Given the result from part (a), show that the lower bound on the number of comparisons
for merging A and B is 2n − 1.

来自IT公司面试手册

下一篇:一网友自己设计的面试题

上一篇:湖南科创面试题

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题