b******i
发帖数: 914 | 1 在翻看以前的面经
看到两道题是这样的：
1.Given a binary tree of integers, give an ascii representation of the tree
so that people can visually see the structure of the tree. An ascii
representation is a single string, so that printing out this single string
gives the required tree.
2.Given a graph, there are some nodes with degree 1. These nodes are called
terminators. There are a several terminators in the graph. There are single
/multiple paths from each terminators to each other terminators. Compute the
average path length of all such paths.
没有什么思路。请牛人指教！ |
m*****n
发帖数: 2152 | 2 1. 貌是serialize tree?
2. 什么叫 nodes degree 1？ 是一维的意思？
tree
called
single
the
【在 b******i 的大作中提到】
: 在翻看以前的面经
: 看到两道题是这样的：
: 1.Given a binary tree of integers, give an ascii representation of the tree
: so that people can visually see the structure of the tree. An ascii
: representation is a single string, so that printing out this single string
: gives the required tree.
: 2.Given a graph, there are some nodes with degree 1. These nodes are called
: terminators. There are a several terminators in the graph. There are single
: /multiple paths from each terminators to each other terminators. Compute the
: average path length of all such paths.
|
b******i
发帖数: 914 | 3 不知道是不是serialize tree就行了，还是得把indentation也考虑进去，最后print出
来是一棵pretty print的树。node degree 1就是只有一条边连着其他node的点吧。不
过题目没有说是有向图还是无向图，先假设是无向图吧。
原帖在这里：
http://www.mitbbs.com/article_t/JobHunting/32816677.html
【在 m*****n 的大作中提到】
: 1. 貌是serialize tree?
: 2. 什么叫 nodes degree 1？ 是一维的意思？
:
: tree
: called
: single
: the
|
U***A
发帖数: 849 | 4 第二题是不是先找出所有的degree为1的node，然后用dfs找出所有的路径长度然后求
平均值。 |
m*****n
发帖数: 2152 | 5 node degree 1就是只有一条边连着其他node的点吧
还是不懂, 比如 A->B->C, B算几条边?
【在 b******i 的大作中提到】
: 不知道是不是serialize tree就行了，还是得把indentation也考虑进去，最后print出
: 来是一棵pretty print的树。node degree 1就是只有一条边连着其他node的点吧。不
: 过题目没有说是有向图还是无向图，先假设是无向图吧。
: 原帖在这里：
: http://www.mitbbs.com/article_t/JobHunting/32816677.html
|
b******i
发帖数: 914 | 6 看我给的原帖的link，这个没详细说，
我估计图也有可能是无向的，有向图还真不知道准确定义是什么 （入+出 == 1 ?）
【在 m*****n 的大作中提到】
: node degree 1就是只有一条边连着其他node的点吧
: 还是不懂, 比如 A->B->C, B算几条边?
|
r****7
发帖数: 2282 | 7 2肯定是无向图吧，有向图的话degree 1就没法从一个到别的了
从一个terminator开始找到不同的terminators记下所有的路就可以了
tree
called
single
the
【在 b******i 的大作中提到】
: 在翻看以前的面经
: 看到两道题是这样的：
: 1.Given a binary tree of integers, give an ascii representation of the tree
: so that people can visually see the structure of the tree. An ascii
: representation is a single string, so that printing out this single string
: gives the required tree.
: 2.Given a graph, there are some nodes with degree 1. These nodes are called
: terminators. There are a several terminators in the graph. There are single
: /multiple paths from each terminators to each other terminators. Compute the
: average path length of all such paths.
|
m*****n
发帖数: 2152 | 8 无向有环怎么办? 比如 S-A-B-C-D-E-F-A D-P, S到P的avg path是多少? 这可以在里
面转N圈,每多一圈就是一条新路?
【在 r****7 的大作中提到】
: 2肯定是无向图吧，有向图的话degree 1就没法从一个到别的了
: 从一个terminator开始找到不同的terminators记下所有的路就可以了
:
: tree
: called
: single
: the
|
b******i
发帖数: 914 | 9 恩，你说的有道理，这题首先定义就不是很清晰。我估计说的是无环图里面两两
terminators之间的shortest path。不过这些都是我们瞎猜的。
【在 m*****n 的大作中提到】
: 无向有环怎么办? 比如 S-A-B-C-D-E-F-A D-P, S到P的avg path是多少? 这可以在里
: 面转N圈,每多一圈就是一条新路?
|
