Python程序员面试分类真题3

Python程序员面试分类真题3

(总分：100.00,做题时间：90分钟)

面试题(总题数：5,分数：1C0.00)

1.实现一个栈的数据结构，使其具有以下方法：压栈、弹栈、取校顶元素、判断栈是否为空以及获取

栈中元素个数。

(分数:20,00)

正确答案：(栈的实现有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种

方法。

方法一：数组实现

在采用数组来实现栈的时候，栈空间是•段连续的空间.实现思路3F图所示。

从上图中可以看出，可以把数组的首元素当做栈底，同时记录校中元素的个数size,假设数组首地

址为arr,从上图可以看出，压栈的操作其实是把待压栈的元索放到数组air[size]中，然后执行size+

操作：同理，弹栈操作其实是取数组andsize-1]元索，然后执行size-操作。根据这个原理可以非常容

易实现栈，示例代码如卜.：

classMyStack:

#模拟栈

definit(seif):

self,itcms=[]

#撑判断栈是否为空

defisEmpty(self):

return1on(self,iterns)==0

#返回栈的大小

defsize(self):

returnlen(self.ilems)

#返回栈顶元素

deftop(self):

ifnotself.isEmplyO:

returnelf.iterns[len(self,iterns)-1]

else:

returnNone

*弹栈

defpop(self):

iflen(self.items)>0:

returnself,items.pop()

else:

print”栈已经为空”

returnNone

*压栈

defpush(seif,item):

self,items,append(item)

namemam

s=MyStack()

s.push(4)

print"栈顶元素为："+str(s.topO)

print”栈大小为:"+str(s.size。)

s.pop()

prml"弹栈成功”

s.popO

方法二：链表实现

在创建链表的时候经常采用一种从头结点插入新结点的方法，可以采用这种方法来实现栈，最好使

用带头结点的链表，这样可以保证对每个结点的操作都是相同的，实现思路如下图所示。

在上图中，在进行压栈操作的时候，首先需要创建新的结点,把待乐栈的元素放到新结点的数据域

中，然后只需要(1)和(2)两步就实现了压栈操作(把新结点加到了链表首部)。同理，在弹枝的时候，只需

要进行⑶的操作就可以删除鞋表的第一个元素，从而实现弹栈操作。实现代码如下：

classLNode:

def_new_(self,x):

self.data=x

self.next=None

classMyStack:

def_init_(self):

#pHead=LNode0

self.data=None

self.nexRJone

#判断stack是否为空,如果为空返回true,否则返回false

defempty(seif):

ifself.next==None:

returnTrue

else:

returnFalse

#获取栈中元素的个数

defsize(self):

size=0

p=self.next

whilep!=None:

p=p.next

size+=l

returnsize

#入栈：把e放到栈顶

defpush(self,e):

p=LNode

p.data=e

p.next=self.next

self.next=p

#山栈,同时返同栈顶元素

dofpop(self):

tmp=scll.next

iftmp!=None:

self.next=tmp.next

returntmp.data

print”栈已经为空”

return

#取得栈顶元素

deftop(self):

ifself.next!=None:

returnself.next,data

print”栈已经为空”

returnNone

if_name_=*_main_":

stack=MyStack()

stack,push(l)

print”栈顶元素为:"+str(stack.topO)

print"栈大小为:"+str(stack.size())

stack.pop()

print”弹栈成功”

stack.pop()

程序的运行结果为：

栈顶元素为：1

栈大小为：1

弹栈成功

栈已经为空

两种方法的对比：

采用数组实现栈的优点是：一个元素值占用一个存储空间：它的缺点为：如果初始化申请的存储空

间太大，会造成空间的浪费，如果申请的存储空间太小，后期会经常需要扩充存储空间，扩充存储空间是

个费时的操作，这样会造成性能的下降。

采用链表实现栈的优点是：使用灵活方便，只有在需要的时候才会申请空间。它的缺点为：除了要

存储元素外，还需要额外的存储空间存储指针信息。

算法性能分析；

这两种方法压栈与弹栈的时间复杂度都为0(1)。)

解析：［考点］如何实现栈

2.实现•个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。

(分数:20.00)

正确答案：(与实现栈的方法类似，队列的实现也有两种方法，分别为采用数组来实现和采用链表来实

现。下面分别详细介绍这两种方法。

方法一：数组实现

下图给出了一种最简电的实现方式，用front来记录队列首元素的位置，用rear来记录队列尾元素

往后一个位置。人队列的时候只需要将待人队列的兀索放到数组卜标为rear的位宜，同时执行rear+,

出队列的时候只需要执行frond即可。

示例代码如下:

classMyQueuc:

def_init_(self):

self.arr=[]

self.front=0#队列头

self.rear=O#队列尾

#判断队列是否为空

defisEmpty(self):

returnself.front==self.rear

#返回队列的大小

defsize(self):

returnself,rear-self,front

#返回队列首元素

defgetFront(self):

ifself.isEmpty0:

returnNone

returnseif.arr[self.frontJ

#返回队列尾元素

defgctBack(self):

ifself.isEmpty():

returnNone

returnself,arrfself.rear-1]

#删除队列头元素

defdeQueue(self):

ifself,rear>self,front:

self.front+=l

else:

print”队列已经为空”

#把新元素加入队列尾

defenQueue(self,item):

self.arr.append(item)

self.rear+=l

if_name_=*_main_*:

queue=MyQueue()

queue.enQueue(l)

queue.enQueue(2)

print”队列头元索为："+str(queue.getFront0)

print”队列尾元素为:"+str(queue.gctBackO)

print”队列大小为:"+str(qneue.size。)

程序的运行结果为：

队列头元素为：I

队列尾元素为：2

队列大小为：2

以上这种实现方法最大的缺点为：出队列后数组前半部分的空间不能被充分地利用，解决这个问题的

方法为把数组看成一个环状的空间(循环队列)。泻数组最后一个位置被占用后，可以从数组首位置开始循

环利用，具体实现方法可以参考数据结构的课本。

方法二：链表实现

采用链表实现队列的方法与实现校的方法类似,分别用两个指针指向队列的首元素与尾元素，如下

图所示。用pHead米指向队列的首元索，用pEnd来指向队列的尾元案。

在上图中，刚开始队列中只有元素1、2和3,当新元索4要进队列的时候，只需要上图中(1)和(2)

两步，就可以把新结点连接到链表的尾部，同时修改pEnd指针指向新增加的结点。出队列的时候只需要

步骤(3),改变pHead指针使其指向pHcad.ncxt,此外也需要考虑结点所占空间释放的问题。在入队列与

出队列的操作中也需要考虑队列尾空的时候的特殊操作，实现代码如下所示：

classLNode:

def_new_(self,x):

self.data=x

self.next=None

classMyQueue:

#分配头结点

def_inil_(self):

self.pHead=None

self.pEnd=None

#判断队列是否为空,如果为空返回true,否则返回false

defempty(self):

ifself.pHead=None:

returnTrue

else:

returnFalse

#获取栈中元索的个数

defsize(self):

size=()

p=self.pHead

whi1cp!=Nonc:

p=p.next

size+=l

returnsize

*入队列：把元素e加到队列尾

defcnQucue(self,e):

p=LNode()

p.data=e

p.next=None

ifself.pHead==None:

self.pHead=self.pEnd=p

else:

self.pEnd.next=p

selfpEnd=p

#出队列，删除队列首元素

defdeQueue(self):

ifself.pllead==None:

print”出队列失败，队列已经为空”

self.pHead=self.pHead.next

ifsclf.pHead==Nonc:

self.pEnd=Nonc

#取得队列首元素

defgetFront(self):

ifseif.pHead==None:

print”获取队列百元素失败，队列己经为空”

returnNone

returnself.pHcad.data

#取得队列尾元素

defgetBack(self):

ifself.pEnd==None:

print”获取队列尾元素失败,队列已经为空”

returnNone

returnself.pEnd.data

if_name_="_main_*:

queue=MyQueue()

queue.enQueue(I)

queue.enQueue(2)

print”队列头元素为：*+str(queue.gctFront())

print”队列尾元素为："+str(queue.gelBackO)

print”队列大小为:*+str(queue.sizeO)

程序的运行结果为：

队列头元素为：1

队列尾元素为：2

队列大小为：2

显然用链表来实现队列有更好的灵活性，与数组的实现方法相比，它多/用来存储结点关系的指针空

间。此外，也可以用循环跳表来实现队列，这样只需要一个指向彼表最后一个元素的指针即可，因为通过

指向链表尾元素可以非常容易地找到鞋表的首结点。)

解析：［考点］如何实现队列

3.翻转(也叫颠倒)栈的所有元素，例如输入栈｛1，2,3,4,5｝,其中，1处在栈顶，翻转之后的栈为

［5,4,3,2,1),其中，5处在栈顶。

(分数:20,00)

正确答案；(

最容易想到的办法是申请•个额外的队列，先把栈中的元索依次出栈放到队列里，然后把队列里的元素按

照出队列顺序入栈，这样就可以实现栈的翻转，这种方法的块点是需要，请额外的空间存储队列，因此，

空间复杂度较高。卜面介绍•种空间复杂度较低的递归的方法。

递归程序布•两个关键因索需要注意：递归定义和递归终止条件。经过分析后，很容易得到该问题的

递归定义和递归终止条件。递归定义：将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后对不

包含栈顶元素的子栈进行同样的操作。终止条件：递归下去，直到栈为空。递归的调用过程如下图所示：

在上图中，对于栈｛1,2,3,4,5｝,进行翻转的操作为：首先把栈底元素移动到栈顶得到栈(5,

1,2,3,4｝,然后对不包含栈顶元素的子栈进行递归调用(对子栈元素进行翻转)，了栈｛】，2,3,41翻

转的结果为｛4,3,2,1｝,因此，最终得到翻转后的栈为｛5,4,3,2,1),>

此外，由于栈的后进先出的特点，使得只能取栈顶的元素，因此，要把栈底的元素移动到栈顶也需

要递归调用才能完成，主要思路为：把不包含该栈顶元素的于栈的栈底的元素移动到于栈的栈顶，然后把

栈顶的元素与子栈栈顶的元素(其实就是与栈顶相邻的元素)进行交换。

为了更容易理解递归调用，可以认为在进行递归调用的时候，子栈已经把栈底元素移动到了栈顶，

在上图中,为了把栈U,2,3,4,5｝的栈底元素5移动到栈顶，首先对子栈｛2,3,1,5),进行递归调

用，调用的结果为｛5,2,3,4｝,然后对子栈顶元素5,与栈顶元素1进行交换得到栈(5,1,2,3,

4),实现了把栈底元素移动到栈顶。

实现代码如下：

python中没有栈的模块,所以先新建一个栈类

classStack:

，模拟栈

def_init_(self):

self.items=[]

#判断栈是否为空

defempty(self):

returnlen(self.items)=0

#返回栈的大小

defsize(self):

returnlen(self.items)

力返回栈顶元素

defpeek(self):

ifnotself,empty():

returnself,itoms[1on(self,iterns)-!]

else:

returnNone

#一栈

defpop(self):

iflen(self.items)^0:

returnself,iterns.pop()

else:

priiic”栈已经为空”

returnNone

#压栈

defpush(self,item):

self,items,append(item)

方法功能：把栈底元素移动到栈顶

参数：s栈的引用

"""

defmoveBottomToTop(s):

ifs.empty():

return

topl=s.peck()

s.popO#弹出栈项元素

ifnots.empty():

并递归处埋不包含栈顶元素的于栈

moveBoltomToTop(s)

top2-s.peek()

s.pop()

#交换栈顶元素与予栈栈顶元素

s.push(topl)

s.push(top2)

else:

s.push(topl)

defreverse_stack(s):

ifs.empty():

return

#把栈底元素移动到栈顶

movcBottomToTop(s)

top=s.peek()

s.pop()

#递归处理子栈

reverse_stack(s)

s.push(top)

ifname=*main*:

s=Stack()

s.push(5)

s.push(4)

s.push(3)

s.push(2)

s.push(l)

reverse_stack(s)

print"翻转后出栈呦序为:二

whilenots.empty():

prints.peek(),

s.pop0

程序的运行结果为：

翻转后出栈顺序为：54321

算法性能分析：

把栈底元索移动到栈顶操作的时间复杂度为000,在翻转操作中对每个子栈都进行了把栈底元素移

动到栈顶的操作，因此，翻转算法的时间复杂度为0(M).

)

解析：［考点］如何翻转栈的所有元素

4.输入两个整数序列，其中一个序列表示栈的push(入)顺序，判断另一个序列有没有可能是对应的

pop(出)顺序。

(分数：20.00)

正确答案：(假如输入的push序列是I、2、3、4、5,那么3、2、5、4、1就有可能是一个pop序列，但

5、3、4、1、2就不可能是它的一个pop序列。

主要思路是使用一个栈来模拟入栈顺序，具体步骤如下：

(D把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素，然后栈顶元素出栈，pop序

列移动到第二个元素：

(2)如果栈顶继续等于pop序列现在的元素，则继续出栈井pop后移:否则对push序列继续入栈。

(3)如果push序列已经全部入栈，但是pop序列未全部遍历，而且极顶元素不等于当前pop元素，

那么这个序列不是一个可能的出栈序列。如果栈为空，而且pop序列也全部被遍历过，则说明这是一个可

能的pop序列。下图给出一个合理的pop序列的判断过程。

在上图中，(1)〜(3)三步，由于栈顶元素不等于pop序列第一个元素3,因此，1,2,3依次入栈，

当3入栈后，栈顶元素等于pop序列的第一个元素3,因此，第(4)步执行3出栈，接下来指向第二个pop

序列2,且栈顶元素等于pop序列的当前元素，因此，第(5)步执行2出校：接着由于栈顶元素4不等于

当前pop序列5,因此，接下来⑹和(7)两步分别执行4和5人栈：接着由于栈顶元素5等于pop序列的

当前值,因此，第(8)步执行5出极，接下来(9)和(10)两步栈项元素都等于当前pop序列的元素,因此,

都执行出栈操作。最后由于栈为空，同时pop序列都完成了遍历，因此，｛3,2,5,%1)是一个合理的

出栈序列。

实现代码如下：

classStack:

力模拟栈

def_init_(self):

selfitems=[]

*判断栈是否为空

defempty(self):

return1en(self,items)==0

#返回栈的大小

defsize(self):

returnlen(self.items)

*返回栈顶元索

defpeek(self):

ifnotsolf.empty():

returnself,items[lcn(sclf.iterns)-1]

else:

returnNone

力弹栈

defpop(self):

iflen(self.items)>0:

returnself,iterns,pop()

else:

print”栈己经为空”

returnNone

*压栈

defpush(self,item):

self,items,append(Hem)

defisPopSerial(push,pop):

ifpush==Noneorpop==None:

returnFalse

pushLcn=1on(push)

popLcn=lon(pop)

itpushLen!=popLcn:

returnFalse

pushIndex-0

poplndex=0

stack=Stack()

whilepushIndcxVpushLen:

»把push序列依次入栈,直到校顶元素等于pop序列的第一个元素

stack,push(push[pushIndex])

pushlndex+=l

力栈顶元素出栈，pop序列移动到下一个元素

while(notstack,empty())andstack.peekO==pop[poplndex]:

stack.pop()

poplndex+=l

外栈为空，且pop序列中元素都被遍历过

returnstack,empty()andpopIndex==popLen

if_name_=*_main_*:

push="12345"

pop=*32541*

ifisPopScrial(push,pop):

printpop+"是"+push+”的一个pop序列”

else:

printpop+"不是"+push+”的一个pop序列”

程序的运行结果为：

32541是12345的一个pop序列

算法性能分析：

这种方法在处理一个合理的pop序列的时候需要操作的次数最多，即把push序列进行一次压栈和出

栈操作，操作次数为2N,因此，时间豆杂度为0(N),此外，这种方法使用「额外的栈空间，因此，空间

豆杂度为0(N).)

解析：［考点］如何根据入栈序列判断可能的出校序列

5.如何用0(1)的时间复杂度求栈中最小元素

《分数；20.00)

正确答案：(由广栈具有后进先出的特点，因此，push和pop只需要对栈顶元素进行操作。如果使用上述

的实现方式，只能访问到栈顶的元素，无法得到栈中最小的元素。当然，可以用另外一个变量来记录栈底

的位置，通过遍历栈中所有的元索找出最小值，但是这种方法的时间曳杂度为0(N),那么如何才能用

0(1)的时间复杂度求出栈中最小的元素呢？

在算法设计中，经常会采用空间换取时间的方式来提高时间复杂度，也就是说，采用额外的存储空间

来降低操作的时间复杂度。具体而言，在实现的时候使用两个栈结构，一个栈用来存储数据，另外一个栈

用来存储栈的最小元素。实现思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个位压入

保存最小元素的栈中：在出校的时候，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶

元素也出校，使得当前最小值变为当前最小值入栈之前的那个最小也。为了简引起见，可以在栈中保存

int类型。

实现代码如下：

力模拟栈

classStack:

def_init_(self):

self.items=[]

口判断栈是否为空

defempty(self):

returnlen(self.iterns)--0

»返回栈的大小

defsize