没有合适的资源?快使用搜索试试~ 我知道了~
程序员面试题精选100题(自己整理)
4星 · 超过85%的资源 需积分: 49 88 下载量 17 浏览量
2008-11-19
16:19:57
上传
评论 2
收藏 536KB DOC 举报
温馨提示
试读
64页
程序员面试题精选100题,以前下过的不全,自己在网上搜了搜,整理了一下。
资源推荐
资源详情
资源评论
程序员面试题精选 (01) -把二元查找树转变成排序的双向链表
题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
比如将二元查找树
转换成双向链表
。
分析:本题是微软的面试题。很多与树相关的题目都是用递归的思路来解
决,本题也不例外。下面我们用两种不同的递归思路来分析。
思路一:当我们到达某一结点准备调整以该结点为根结点的子树时,先调
整其左子树将左子树转换成一个排好序的左子链表,再调整其右子树转换右子
链表。最近链接左子链表的最右结点(左子树的最大结点)、当前结点和右子
链表的最左结点(右子树的最小结点)。从树的根结点开始递归调整所有结点。
思路二:我们可以中序遍历整棵树。按照这个方式遍历树,比较小的结点
先访问。如果我们每访问一个结点,假设之前访问过的结点已经调整成一个排
序双向链表,我们再把调整当前结点的指针将其链接到链表的末尾。当所有结
点都访问过之后,整棵树也就转换成一个排序双向链表了。
参考代码:
首先我们定义二元查找树结点的数据结构如下:
!"#$"%
& '(%#"%"%
& ')*#*"%
+#
思路一对应的代码:
,$--"-"."
/'0'-%
)*-1'*"%'
2'0%)*3"-
"*-
&,$4&'3")*5
%46'5
7((#
&'(%7((#
&')*7((#
,$"%-
%4'-8 '(%5
'(%,$4'-8 '(%3%"5#
,*"%-
%4'(%5
'(%-8 ')*'#
'-8 '(%'(%#
+
,$*-
%4'-8 ')*5
')*,$4'-8 ')*35#
,"*-
%4')*5
'-8 ')*')*#
')*-8 '(%'#
+
&'''#
/%*"%'3
"1
%4)*5
1"4''-8 '(%5
''''-8 '(%#
+
/%"%"%'3
*1
"
1"4''-8 ')*5
''''-8 ')*#
+
''#
+
,$"-"."
/'0%
2'0%"-"."
&,$4&'92%5
:11%"-"."3
1'
,$4'92%35#
+
思路二对应的代码:
,$--"-"."
/'0'-%
'(/(-"%"-"."
$,$4&'3&;
'(/(5
%4'7((5
#
&','#
,$"%-
%4',-8 '(%67((5
,$4',-8 '(%3'(/(5#
<"-"."
',-8 '(%'(/(#
%4'(/(67((5
'(/(-8 ')*',#
'(/(',#
,$*-
%4',-8 ')*67((5
,$4',-8 ')*3'(/(5#
+
,$"-"."
/'0'92%-%
2'0%"-"."
&,$ "4&'92%5
&'(/(7((#
,$4'92%3'(/(5#
=%"-"."
&'92%('(/(#
1"4'92%(;;'92%(-8 '(%5
'92%('92%(-8 '(%#
'92%(#
+
程序员面试题精选 (02) -设计包含
min
函数的栈
题目:定义栈的数据结构,要求添加一个 函数,能够得到栈的最小元素。
要求函数 、' 以及 '' 的时间复杂度都是 245。 分析:这是去年
**" 的一道面试题。
我看到这道题目时,第一反应就是每次 ' 一个新元素时,将栈里所有逆序
元素排序。这样栈顶元素将是最小元素。但由于不能保证最后 ' 进栈的元
素最先出栈,这种思路设计的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素(或最小元素的位置)。每次 ' 一
个新元素进栈的时候,如果该元素比当前的最小元素还要小,则更新最小元素。
乍一看这样思路挺好的。但仔细一想,该思路存在一个重要的问题:如果当前
最小元素被 '' 出去,如何才能得到下一个最小元素?
因此仅仅只添加一个成员变量存放最小元素(或最小元素的位置)是不够的。
我们需要一个辅助栈。每次 ' 一个新元素的时候,同时将最小元素(或最
小元素的位置。考虑到栈元素的类型可能是复杂的数据结构,用最小元素的位
置将能减少空间消耗)' 到辅助栈中;每次 '' 一个元素出栈的时候,同
时 '' 辅助栈。
参考代码:
>"?@8
>"?A8
'"?'8",.BC
'"0
,.BC4$5+
$"D,.BC4$5+
;'4$5#
;'4$5#
$'4;$"5#
$''4$5#
;4$5#
'$0
8 #"%.
E 8 /F#%"
+#
*""%".
'"?'8;,.BC?800'45
A.45#
+
*""%-".
'"?'8;,.BC?800'45
A.45#
+
"%.
'"?'8$,.BC?800'4;
$"5
''%
A' .4$"5#
F%" %
/F
%4 /FAE455
/FA' .45#
"
%4$"? G /FA.45H5
/FA' .4 AE45-5#
"
/FA' .4 /FA.455#
+
+
"%.
剩余63页未读,继续阅读
xinguo128
- 粉丝: 2
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页