Python程序员面试分类真题6

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])

#如