版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
Python程序员面试分类真题6(总分:100.00,做题时间:90分钟)面试题(总题数:6,分数:100.00)1.
给定一个二叉树根结点,复制该树,返回新建树的根结点。
(分数:16.50)__________________________________________________________________________________________
正确答案:(用给定的二叉树的根结点root来构造新的二叉树的方法为:首先创建新的结点dupTree,然后根据root结点来构造dupTree结点(dupTree.data=root.data),最后分别用root的左右子树来构造dupTree的左右子树。根据这个思路可以实现二叉树的复制,使用递归方式实现的代码如下:
classBiTNode:
def__init__(self):
self.data=None
self.lchild=None
self.rchild=None
defcreateDupTree(root):
ifroot==None:
returnNone
#二叉树根结点
dupTree=BiTNode()
dupTree.data=root.data
#复制左予树
dupTree.lchild=createDupTree(root.lchild)
#复制右予树
dupTree.rchild=createDupTree(root.rchild)
returndupTree
defprintTreeMidOrder(root):
ifroot==None:
return
#遍历root结点的左予树
ifroot.lchild!=None:
printTreeMidOrder(root.lchild)
#遍历root结点
printroot.data,
#遍历root结点的右子树
ifroot.rchild!=None:
printTreeMidOrder(root.rchild)
if__name__=="__main__":
root1=constructTree()
root2=createDupTree(root1)
print"原始二叉树中序遍历:",
printTreeMidOrder(root1)
print'\n'
print"新的二叉树中序遍历:",
printTreeMidOrder(root2)
程序的运行结果为:
原始二叉树中序遍历:-1396-7
新的二叉树中序遍历:-1396-7
算法性能分析:
这种方法对给定的二叉树进行了一次遍历,因此,时间复杂度为O(N),此外,这种方法需要申请N个额外的存储空间来存储新的二叉树。)解析:[考点]如何复制二叉树2.
从树的根结点开始往下访问一直到叶子结点经过的所有结点形成一条路径。找出所有的这些路径,使其满足这条路径上所有结点数据的和等于给定的整数。例如:给定如下二叉树与整数8,满足条件的路径为6->3->-1(6+3-1=8)。
(分数:16.50)__________________________________________________________________________________________
正确答案:(可以通过对二叉树的遍历找出所有的路径,然后判断各条路径上所有结点的值的和是否与给定的整数相等,如果相等,则打印出这条路径。具体实现方法可以通过对二叉树进行先序遍历来实现,实现思路为:对二叉树进行先序遍历,把遍历的路径记录下来,当遍历到叶子结点时,判断当前的路径上所有结点数据的和是否等于给定的整数,如果相等则输出路径信息,示例代码如下:
classBiTNode:
def__init__(self):
self.data=None
self.lchild=None
self.rchild=None
"""
方法功能:打印出满足所有结点数据的和等于num的所有路径
参数:root:二叉树根结点;num:给定的整数;sum:当前路径上所有结点的和
用来存储从根结点到当前遍历到结点的路径
"""
defFindRoad(root,num,sums,v):
#记录当前遍历的root结点
sums+=root.data
v.append(root.data)
#当前结点是叶子结点且遍历的路径上所有结点的和等于num
ifroot.lchild==Noneandroot.rchild==Noneandsums==num:
i=0
whilei<len(v):
printv[i],
i+=1
print'\n'
#遍历root的左子树
ifroot.lchild!=None:
FindRoad(root.lchild,num,sums,v)
#遍历root的右予树
ifroot.rchild!=None:
FindRoad(root.rchild,num,sums,v)
#清除遍历的路径
sums-=v[-1]
v.remove(v[-1])
defconstructTree():
root=BiTNode()
node1=BiTNode()
node2=BiTNode()
node3=BiTNode()
node4=BiTNode()
root.data=6
node1.data=3
node2.data=-7
node3.data=-1
node4.data=9
root.lchild=node1
root.rchild=node2
nodel.lchild=node3
nodel.rchild=node4
node2.lchild=node2.rchild=node3.lchild=node3.rchild=node4.lchild=node4.rchild=None
returnroot
if__name__=="__main__":
root=constructTree()
s=[]
print"满足路径结点和等于8的路径为:",
FindRoad(root,8,0,s)
程序的运行结果为:
满足路径结点和等于8的路径为:63-1
算法性能分析:
这种方法与二叉树的先序遍历有着相同的时间复杂度O(N),此外,这种方法用一个数组存放遍历路径上结点的值,在最坏的情况下时间复杂度为O(N)(所有结点只有左子树,或所有结点只有右子树),因此,空间复杂度为O(N)。)解析:[考点]如何在二叉树中找出与输入整数相等的所有路径3.
二叉树的镜像就是二叉树对称的二叉树,就是交换每一个非叶子结点的左子树指针和右子树指针,如下图所示,请写出能实现该功能的代码。注意:请勿对该树做任何假设,它不一定是平衡树,也不一定有序。
(分数:16.50)__________________________________________________________________________________________
正确答案:(从上图可以看出,要实现二叉树的镜像反转,只需交换二叉树中所有结点的左右孩子即可。由于对所有的结点都做了同样的操作,因此,可以用递归的方法来实现,由于需要调用printTreeLayer层序打印二叉树,这种方法中使用了队列来实现,实现代码如下:
fromcollectionsimportdeque
classBiTNode:
def__init__(self):
self.data=None
self.lchild=None
self.rchild=None
#对二叉树进行镜像反转
defreverseTree(root):
ifroot==None:
return
reverseTree(root.lchild)
reverseTree(root.rchild)
tmp=root.lchild
root.lchild=root.rchild
root.rchild=tmp
defarraytotree(arr,start,end):
root=None
ifend>=start:
root=BiTNode()
mid=(start+end+1)/2
#树的根结点为数组中间的元素
root.data=arr[mid]
#递归的用左半部分数组构造root的左子树
root.lchild=arraytotree(arr,start,mid-1)
#递归的用右半部分数组构造root的右子树
root.rchild=arraytotree(arr,mid+1,end)
else:
root=None
returnroot
defprintTreeLayer(root):
ifroot==None:
return
queue=deque()
#树根结点进队列
queue.append(root)
whilelen(queue)>0:
p=queue.popleft()
#访问当前结点
printp.data,
#如果这个结点的左孩子不为空则入队列
ifp.lchild!=None:
queue.append(p.lchild)
#如果这个结点的右孩子不为空则入队列
ifp.rchild!=None:
queue.append(p.rchild)
if__name__=="__main__":
arr=[1,2,3,4,5,6,7]
root=arraytotree(arr,0,len(arr)-1)
print"二叉树层序遍历结果为:",
printTreeLayer(root)
print'\n'
reverseTree(root)
print"反转后的二叉树层序遍历结果为:",
printTreeLayer(root)
程序的运行结果为:
二叉树层序遍历结果为:4261357
反转后的二叉树层序遍历结果为:4627531
算法性能分析:
由于对给定的二叉树进行了一次遍历,因此,时间复杂度为O(N)。)解析:[考点]如何对二叉树进行镜像反转4.
对于一棵二叉排序树,令f=(最大值+最小值)/2,设计一个算法,找出距离f值最近、大于f值的结点。例如,下图所给定的二叉排序树中,最大值为7,最小值为1,因此,f=(1+7)/2=4,那么在这棵二叉树中,距离结点4最近并且大于4的结点为5。
(分数:16.50)__________________________________________________________________________________________
正确答案:(首先需要找出二叉排序树中的最大值与最小值。由于二叉排序树的特点是:对于任意一个结点,它的左子树上所有结点的值都小于这个结点的值,它的右子树上所有结点的值都大于这个结点的值。因此,在二叉排序树中,最小值一定是最左下的结点,最大值一定是最右下的结点。根据最大值与最小值很容易就可以求出f的值。接下来对二叉树进行中序遍历。如果当前结点的值小于f,那么在这个结点的右子树中接着遍历,否则遍历这个结点的左子树。实现代码如下:
classBiTNode:
def__init__(self):
self.data=None
self.lchild=None
self.rchild=None
"""
方法功能:查找值最小的结点
输入参数:root:根结点
返回值:值最小的结点
"""
defgetMinNode(root):
ifroot==None:
returnroot
whileroot.lchild!=None:
root=root.lchild
returnroot
"""
方法功能:查找值最大的结点
输入参数:root:根结点
返回值:值最大的结点
"""
defgetMaxNode(root):
ifroot==None:
returnroot
whileroot.rchild!=None:
root=root.rchild
returnroot
defgetNode(root):
maxNode=getMaxNode(root)
minNode=getMinNode(root)
mid=(maxNode.data+minNode.data)/2
result=None
whileroot!=None:
#当前结点的值不大于f,则在右子树上找
ifroot.data<=mid:
root=root.rchild
#否则在左子树上找
else:
result=root
root=root.lchild
returnresult
if__name__=="__main__":
arr=[1,2,3,4,5,6,7]
root=arraytotree(arr,0,len(arr)-1)
printgetNode(root).data
程序的运行结果为:
5
算法性能分析:
这种方法在查找最大结点与最小结点时的时间复杂度为O(h),h为二叉树的高度,对于有N个结点的二叉排序树,最大的高度为O(N),最小的高度为O(log2N)。同理,在查找满足条件的结点的时候,时间复杂度也是O(h)。综上所述,这种方法的时间复杂度在最好的情况下是O(logN),最坏的情况下为O(N)。)解析:[考点]如何在二叉排序树中找出第一个大于中间值的结点5.
给定一棵二叉树,求各个路径的最大和,路径可以以任意结点作为起点和终点。比如给定以下二叉树:
最大和的路径为结点5→2→3,这条路径的和为10,因此返回10。
(分数:16.50)__________________________________________________________________________________________
正确答案:(本题可以通过对二叉树进行后序遍历来解决,具体思路如下:
对于当前遍历到的结点root,假设已经求出在遍历root结点前最大的路径和为max:
(1)求出以root.left为起始结点,叶子结点为终结点的最大路径和为maxLeft;
(2)同理求出以root.right为起始结点,叶子结点为终结点的最大路径和maxRight。
包含root结点的最长路径可能包含如下三种情况:
(1)leftMax=root.val+maxLeft(左子树最大路径和可能为负)。
(2)rightMax=root.val+maxRight(右子树最大路径和可能为负)。
(3)allMax=root.val+maxLeft+maxRight(左右子树的最大路径和都不为负)。
因此,包含root结点的最大路径和为tmpMax=max(leftMax,rightMax,allMax)。
在求出包含root结点的最大路径后,如果tmpMax>max,那么更新最大路径和为tmpMax。
实现代码如下:
classTreeNode:
def__init__(self,val):
self.val=val
self.left=None
self.right=None
classIntRef:
def__init__(self):
self.val=None
#求a,b,c的最大值
defMax(a,b,c):
maxs=aifa>belseb
maxs=maxsifmaxs>celseC
returnmaxs
#寻找最长路径
deffindMaxPathRecursive(root,maxs):
ifNone==root:
return0
else:
#求左子树以root.left为起始结点的最大路径和
sumLeft=findMaxPathRecursive(root.left,maxs)
#求右子树以root.right为起始结点的最大路径和
sumRight=findMaxPathRecursive(root.right,maxs)
#求以root为起始结点,叶子结点为结束结点的最大路径和
allMax=root.val+sumLeft+sumRight
leftMax=root.val+sumLeft
rightMax=root.val+sumRight
tmpMax=Max(allMax,leftMax,rightMax)
iftmpMax>maxs.val:
maxs.val=tmpMax
subMax=sumLeftifsumLeft>sumRightelsesumRight
#返回以root为起始结点,叶子结点为结束结点的最大路径和
returnroot.val+subMax
deffindMaxPath(root):
maxs=IntRef()
maxs.val=-2**31
findMaxPathRecursive(root,maxs)
returnmaxs.val
if__name__=="__main__":
root=TreeNode(2)
left=TreeNode(3)
right=TreeNode(5)
root.left=left
root.right=right
printfindMaxPath(root)
程序的运行结果为
10
算法性能分析:
二叉树后序遍历的时间复杂度为O(N),因此,这种方法的时间复杂度也为O(N)。)解析:[考点]如何在二叉树中找出路径最大的和6.
反向DNS查找指的是使用InternetIP地址查找域名。例如,如果你在浏览器中输入06,它会自动重定向到。
如何实现反向DNS查找缓存?
(分数:17.50)__________________________________________________________________________________________
正确答案:(要想实现反向DNS查找缓存,主要需要完成如下功能:
(1)将IP地址添加到缓存中的URL映射。
(2)根据给定IP地址查找对应的URL。
对于本题,常见的一种解决方案是使用字典法(使用字典来存储IP地址与URL之间的映射关系),由于这种方法相对比较简单,这里就不做详细的介绍了。下面重点介绍另外一种方法:Trie树。这种方法的主要优点如下:
(1)使用Trie树,在最坏的情况下的时间复杂度为O(1),而哈希方法在平均情况下的时间复杂度为O(1);
(2)Trie树可以实现前缀搜索(对于有相同前缀的IP地址,可以寻找所有的URL)。
当然,由于树这种数据结构本身的特性,所以使用树结构的一个最大的缺点就是需要耗费更多的内存,但是对于本题而言,这却不是一个问题,因为InternetIP地址只包含有11个字母(0到9和.)。所以,本题实现的主要思路为:在Trie树中存储IP地址,而在最后一个结点中存储对应的域名。实现代码如下:
#Trie树的结点
classTrieNode:
def__init__(self):
CHAR_COUNT=11
self.isLeaf=False
self.url=None
self.child=[None]*CHAR_COUNT#TrieNode[CHAR_COUNT]#CHAR_COUNT
i=0
whilei<CHAR_COUNT:
self.child[i]=None
i+=1
defgetIndexFromChar(c):
return10ifc=='.'else(ord(c)-ord('0'))
defgetCharFromIndex(i):
return'.'ifi==10else('0'+str(i))
classDNSCache:
def__init__(self):
self.CHAR_COUNT=11#IP地址最多有11个不同的字符
self.root=TrieNode()#IP地址最大的长度
definsert(self,ip,url):
#IP地址的长度
lens=len(ip)
pCrawl=self.root
level=0
whilelevel<lens:
#根据当前遍历到的IP中的字符,找出子结点的索引
index=getIndexFromChar(ip[level])
#如
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 不违规操办和参加“升学宴”“谢师宴”承诺书
- 2025届新高三开学摸底考地理试卷(江苏专用)(解析版)
- 第六章 动量守恒定律
- 2023年新高考天津数学高考真题(解析版)
- 成长作文之成长的烦恼150字作文
- 2024年商业交换网合作协议书
- 2024年医用中心供氧设备合作协议书
- 2013年山东省济宁市中考数学试卷
- 2024年家居护理用品项目合作计划书
- 2024年炭石墨负极材料项目建议书
- 2022年吉林长春南关区东北师范大学附属中学(新城校区)七上期中数学试卷
- 钢筋组织供应、运输、售后服务方案
- DB34∕1659-2022 住宅工程质量常见问题防治技术规程
- 辞职信个人原因辞职信
- 异质性企业贸易理论的发展课件
- BCG矩阵图文详解
- 某汽车制造公司12万辆整车项目安全预评价报告
- 红色温馨生日快乐祝福相册PPT模板课件
- 中小学落实“双减政策”,加强“五项管理”资料(全套完整)
- 光缆通信线路工程的设计毕业论文
- 3岁儿童涂色画简笔画打印版
评论
0/150
提交评论