数据结构与算法（Python版）第2版 习题参考答案 周元哲

目录附录D参考答案 2第2章异常处理与调试 2第3章线性表 4第4章队列和栈 5第5章串 8第6章树和二叉树 8第7章树和二叉树的应用 10第8章图论 14第9章图的应用 15第10章查找 19第11章排序 20

附录D参考答案第2章异常处理与调试1.以下是两数相加的程序：x=int(input("x="))y=int(input("y="))print("x+y=",x+y)该程序要求接收两个整数，并输出相加结果。但如果输入的不是整数（如字母），程序就会终止执行并输出异常信息。【解答】try:x=int(input("x="))y=int(input("y="))except(ValueError,Exception):print('类型错误')else:print("x+y=",x+y)2．编写函数devide(x,y)，x为被除数，y为除数，被零除时，输出”divisionbyzero!“。【解答】try:x,y=eval(input("x,y"))print(x/y)except(ZeroDivisionError,Exception):print('divisionbyzero!')3.捕获除零错误。题目描述：编写一个程序，要求用户输入两个整数，然后计算它们的除法结果。如果用户输入的第二个数是0，捕获并处理除零错误，输出相应的提示信息。【解答】try:num1=int(input("请输入第一个整数:"))num2=int(input("请输入第二个整数:"))result=num1/num2print(f"{num1}除以{num2}的结果是:{result}")exceptZeroDivisionError:print("除数不能为0，请重新输入正确的整数。")4.编写一个程序，尝试打开一个文件并读取其中的内容。如果文件不存在，则捕获FileNotFoundError异常；如果文件存在但没有读取权限，则捕获PermissionError异常，并分别输出相应的错误信息。【解答】file_path=input("请输入要读取的文件路径:")try:withopen(file_path,'r')asfile:content=file.read()print(content)exceptFileNotFoundError:print(f"文件{file_path}不存在，请检查文件路径是否正确。")exceptPermissionError:print(f"没有权限读取文件{file_path}，请检查文件权限设置。")5.异常处理与资源释放。题目描述：编写一个程序，尝试连接到一个指定的MySQL数据库，执行一个简单的查询操作。如果连接或查询过程中出现错误，捕获并处理异常，同时确保在无论是否出现异常的情况下，都正确关闭数据库连接。【解答】importmysql.connector#配置数据库连接信息config={"user":"your_username","password":"your_password","host":"your_host","database":"your_database"}try:#建立数据库连接connection=mysql.connector.connect(**config)cursor=connection.cursor()#定义简单的查询语句，这里以查询表中所有数据为例（假设表名为your_table）query="SELECT*FROMyour_table"cursor.execute(query)results=cursor.fetchall()forrowinresults:print(row)cursor.close()exceptmysql.connector.Erroraserr:print(f"数据库操作出现错误:{err}")finally:#无论是否出现异常，都关闭数据库连接ifconnection.is_connected():connection.close()print("数据库连接已关闭")6.自定义异常。题目描述：定义一个自定义异常类InvalidInputError，当用户输入的字符串长度小于5时，抛出该异常。编写一个程序，要求用户输入一个字符串，然后使用自定义异常进行处理。【解答】classInvalidInputError(Exception):"""自定义异常类，用于表示输入字符串长度小于5的情况"""passtry:input_str=input("请输入一个字符串:")iflen(input_str)<5:raiseInvalidInputError("输入的字符串长度小于5，不符合要求")print(f"你输入的字符串是:{input_str}")exceptInvalidInputErrorase:print(e)第3章线性表一.填空题O(n)2数据元素3顺序；链式。4n-i二.编程题1.给定你一个字符串s。请返回含有连续两个s作为子串的最短字符串。请注意两个s可能会有重叠部分。输入:输入一个字符串s。s含有1到50个字符（其中包括1和50）,s中每个字符都是一个小写字母（从a到z）输出:返回含有连续两个s作为子串的最短字符串举例:s="aba",返回"ababa"。【解析】defgetShortestStr(string):iflen(string)==0:returnNoneiflen(string)==1:returnstring*2repeatLength=0forfrontinrange(1,len(string)):ifstring[:front]==string[len(string)-front:]:repeatLength=frontreturnstring+string[repeatLength:]2.从键盘上输入一批数据，对这些数据进行逆置，最后按照逆置后的结果输出。【解析】将输入的数据存放在列表中，将列表的所有元素镜像对调，即第一个与最后一个对调，第二个与倒数第二个对调，……。b_list=input("请输入数据:")a_list=[]foriinb_list.split(','): a_list.append(i)print("逆置前数据为:",a_list)n=len(a_list)foriinrange(n//2):a_list[i],a_list[n-i-1]=a_list[n-i-1],a_list[i]print("逆置后数据为:",a_list)第4章队列和栈1.C是一个循环队列，初始状态为rear=front=1，画出做完下列每一组操作后队列的头尾指针的状态变化情况。d，e，b，g，h入队。d，e出队。i，j，k，l，m入队。b出队。n，o，p，q，r入队图D.1循环队列【解答】d，e，b，g，h入队,运行结果如图D.2所示。d，e出队,运行结果如图D.3所示。i，j，k，l，m入队,运行结果如图D.4所示。b出队，运行结果如图D.5所示。n，o，p，q，r入队，运行结果如图D.6所示，发生了溢出。程序运行结果如图图D.21）运行结果图D.32）运行结果图D.43）运行结果图D.54）运行结果图D.65）运行结果2.给定一个只包含字符'('、')'、'{'、'}'、'['和']'的字符串，判断字符串中的括号是否匹配。defis_valid(s):stack=[]mapping={")":"(","}":"{","]":"["}forcharins:ifcharin"({[":stack.append(char)elifcharin")}]":ifnotstackorstack.pop()!=mapping[char]:returnFalsereturnnotstack3.请定义一个队列，支持在O(1)时间复杂度内获取队列中的最大值。fromcollectionsimportdequeclassMaxQueue:def__init__(self):self.queue=deque()self.max_queue=deque()defenqueue(self,value):self.queue.append(value)whileself.max_queueandself.max_queue[-1]<value:self.max_queue.pop()self.max_queue.append(value)defdequeue(self):ifnotself.queue:returnNonevalue=self.queue.popleft()ifvalue==self.max_queue[0]:self.max_queue.popleft()returnvaluedefmax_value(self):ifnotself.max_queue:returnNonereturnself.max_queue[0]4.给定一个栈，反转栈中的元素顺序。defreverse_stack(stack):ifnotstack:returnstacktop=stack.pop()reverse_stack(stack)insert_at_bottom(stack,top)returnstackdefinsert_at_bottom(stack,item):ifnotstack:stack.append(item)else:top=stack.pop()insert_at_bottom(stack,item)stack.append(top)第5章串1采用正则表达式实现如下内容：（1）验证电子邮件地址一个简单的电子邮件地址正则表达式模式可以是^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-]+$。这个模式的大致解释如下：^：匹配字符串开头。[a-zA-Z0-9_.+-]+：匹配用户名部分，允许字母、数字、点号、下划线、加号和减号至少出现一次。@：匹配@符号。[a-zA-Z0-9-]+：匹配域名部分的主体，允许字母、数字和减号至少出现一次。\.[a-zA-Z0-9-]+：匹配域名中的顶级域名部分，点号需要转义，允许字母、数字和减号至少出现一次。$：匹配字符串结尾。（2）验证电话号码对于格式为(xxx)xxx-xxxx的电话号码，正则表达式可以是^\(\d{3}\)\d{3}-\d{4}$。其中\(`和`\)用于匹配括号，\d{3}表示匹配三位数字，-用于匹配连接符，\d{4}表示匹配四位数字。（3）匹配HTML标签模式<[a-zA-Z]+>可以匹配简单的HTML开始标签，如<div>、<p>等。其中[a-zA-Z]+用于匹配标签名称，允许字母至少出现一次。2.编写程序如下功能：（1）给定一个字符串，找出其中不含有重复字符的最长子串的长度。deflength_of_longest_substring(s):n=len(s)max_len=0start=0char_dict={}forendinrange(n):ifs[end]inchar_dictandchar_dict[s[end]]>=start:start=char_dict[s[end]]+1char_dict[s[end]]=endmax_len=max(max_len,end-start+1)returnmax_len（2）编写一个函数，统计给定字符串中每个字符出现的次数。defcount_characters(s):char_count={}forcharins:ifcharinchar_count:char_count[char]+=1else:char_count[char]=1returnchar_count（3）编写一个函数，将一个字符串按照指定的分隔符进行分割，返回分割后的字符串列表。defsplit_string(s,delimiter):result=[]start=0foriinrange(len(s)):ifs[i]==delimiter:result.append(s[start:i])start=i+1ifstart<len(s):result.append(s[start:])returnresult第6章树和二叉树一.选择题（1）D（2）D（3）B（4）A（5）C二.简答题（1）一棵二叉树利用顺序存储方法存储如图D.7所示，请给出这棵二叉树的二叉链表表示，并写出它的前序、中序、后序遍历序列。图D.7二叉树顺序存储【解答】运行结果如图D.8所示。前序：abdefcgh中序：dbfeaghc后序：dfebhgca图D.8运行结果(2)．设二叉树的存储结构如下：12345678910left00236580101dataJHFDBACEGIright0009400000其中root为根结点指针，left、right分别为结点左、右孩子指针域，data为结点的数据域。请完成下列各题：画出二叉树root的逻辑结构；写出按先序、中序和后序遍历二叉树所得到的结点序列。【解答】二叉树的逻辑结构如图D.11所示AABCEDGFHI J图D.11二叉树2)先序：ABCEDFHGIJ中序：ECBAHFDJIG后序：ECBHFJIGDA（3）已知二叉树的中序和后序遍历序列如下，试构造该二叉树。

中序：ACBDHGEF

后序：ABCDEFGH【解答】二叉树如图D.13所示。图D.13二叉树第7章树和二叉树的应用1.给定数集w={2，3，4，7，8，9}，试构造关于w的一棵哈夫曼树，并求出其加权路径长度WPL。【解答】运行结果如图D.12所示WPL=(2+3)*4+4*3+(7+8+9)*2=80885794923151833图D.12程序运行结果2.给定一组字符及其频率，构建哈夫曼树，并为每个字符生成哈夫曼编码。importheapqclassNode:def__init__(self,char=None,freq=0,left=None,right=None):self.char=charself.freq=freqself.left=leftself.right=rightdef__lt__(self,other):returnself.freq<other.freqdefbuild_huffman_tree(char_freqs):pq=[]forchar,freqinchar_freqs.items():node=Node(char,freq)heapq.heappush(pq,node)whilelen(pq)>1:left=heapq.heappop(pq)right=heapq.heappop(pq)new_freq=left.freq+right.freqnew_node=Node(freq=new_freq,left=left,right=right)heapq.heappush(pq,new_node)returnpq[0]defhuffman_coding(root):code_table={}deftraverse(node,code=""):ifnode.char:code_table[node.char]=codereturntraverse(node.left,code+"0")traverse(node.right,code+"1")traverse(root)returncode_table#测试示例char_freqs={'a':5,'b':9,'c':12,'d':13,'e':16,'f':45}huffman_tree_root=build_huffman_tree(char_freqs)huffman_codes=huffman_coding(huffman_tree_root)print(huffman_codes)3.给定一个二叉树的根节点，判断它是否是平衡二叉树。平衡二叉树定义为：二叉树的每个节点的左右子树的高度差的绝对值不超过1。classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefheight(node):ifnotnode:return0returnmax(height(node.left),height(node.right))+1defis_balanced(root):ifnotroot:returnTrueleft_height=height(root.left)right_height=height(root.right)ifabs(left_height-right_height)>1:returnFalsereturnis_balanced(root.left)andis_balanced(root.right)#测试示例root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)print(is_balanced(root))4.给定一个升序排序的数组，将其转换为一个平衡二叉搜索树。classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefsorted_array_to_bst(nums):ifnotnums:returnNonemid=len(nums)//2root=TreeNode(nums[mid])root.left=sorted_array_to_bst(nums[:mid])root.right=sorted_array_to_bst(nums[mid+1:])returnroot5.写出此棵树的后根遍历，并把图D.9中的树转换成二叉树。图D.9树【解答】(1)后根遍历序列为：EFBCKNLMGHIJKDA(2)转换后的二叉树如图D.10所示。图D.10转化后的二叉树第8章图论一.填空题（1）第i列非零元素个数（2）n-1（3）1（4）先序遍历（5）起点（6）层次（7）（栈）（数据结构）二．选择题ABD三．编程题1.使用深度优先搜索算法遍历给定的图（以邻接表表示），并输出遍历的顺序。classGraph:def__init__(self,vertices):self.V=verticesself.graph=[[]for_inrange(vertices)]defadd_edge(self,v,w):self.graph[v].append(w)self.graph[w].append(v)defdfs(self,start,visited=None):ifvisitedisNone:visited=[False]*self.Vvisited[start]=Trueresult=[start]foriinself.graph[start]:ifnotvisited[i]:result.extend(self.dfs(i,visited))returnresult#测试示例g=Graph(6)g.add_edge(0,1)g.add_edge(0,2)g.add_edge(1,3)g.add_edge(1,4)g.add_edge(2,4)g.add_edge(3,5)print(g.dfs(0))2.给定一个无向图（以邻接表表示），判断该图是否是连通图。连通图是指图中任意两个顶点之间都存在路径。classGraph:def__init__(self,vertices):self.V=verticesself.graph=[[]for_inrange(vertices)]defadd_edge(self,v,w):self.graph[v].append(w)self.graph[w].append(v)defis_connected(self):visited=[False]*self.Vself.dfs(0,visited)foriinvisited:ifnoti:returnFalsereturnTruedefdfs(self,start,visited):visited[start]=Trueforiinself.graph[start]:ifnotvisited[i]:self.dfs(i,visited)#测试示例g1=Graph(4)g1.add_edge(0,1)g1.add_edge(0,2)g1.add_edge(1,3)g1.add_edge(2,3)print(g1.is_connected())g2=Graph(4)g2.add_edge(0,1)g2.add_edge(0,2)print(g2.is_connected())第9章图的应用（1）请给出图D.14的邻接表，并利用克鲁斯卡尔算法手工构造下图的最小成生树。图D.14图【解答】运行结果如图D.15所示。图D.15运行结果（2）如图D.16所示的有向图，写出使用Dijkstra算法求顶点2到其他各个顶点的最短路径时，算法的动态执行情况，并计算最短路径。图D.16有向图【解答】（3）如图D.17所示的有向图，要求实现如下：1）写出该图的一个拓扑有序序列，要求优先输出序号小的顶点；2）使用Dijkstra算法求顶点1到其他各个顶点的最短路径，写出算法动态过程中各步的状态。图D.17有向图【解答】（1）拓扑有序序列：13542（2）算法执行各步的状态如下：目标顶点2345求出最短路径1{1,2}100{1,3}10∞{1,5}30{1,3}102{1,2}100{1,3,4}60{1,5}30{1,5}303{1,5,2}90{1,5,4}40{1,5,4}404{1,5,4,2}60{1,5,4,2}602.给定一个无权图（以邻接表表示），计算从给定的起始顶点到目标顶点的最短路径长度。如果不存在路径，则返回-1。fromcollectionsimportdequeclassGraph:def__init__(self,vertices):self.V=verticesself.graph=[[]for_inrange(vertices)]defadd_edge(self,v,w):self.graph[v].append(w)self.graph[w].append(v)defshortest_path_length(self,start,end):visited=[False]*self.Vqueue=deque()queue.append((start,0))visited[start]=Truewhilequeue:vertex,dist=queue.popleft()ifvertex==end:returndistforiinself.graph[vertex]:ifnotvisited[i]:visited[i]=Truequeue.append((i,dist+1))return-1#测试示例g=Graph(6)g.add_edge(0,1)g.add_edge(0,2)g.add_edge(1,3)g.add_edge(1,4)g.add_edge(2,4)g.add_edge(3,5)print(g.shortest_path_length(0,5))第10章查找1折半查找算法的存储结构有什么特点？【解答】折半查找算法的存储结构必须是顺序存储结构，而且需要按关键字有序。2顺序查找法适合于什么样的存储结构的线性表？【解答】顺序存储或链式存储3设有一个长度为100的已排好序的表，用折半查找进行查找，若查找不成功，至少比较多少次？【解答】至少比较7次4.对于关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，47}，使用哈希函数H(key)=keyMod11将其中的元素依次散列到哈希表中HT[11]中，并采用链地址法解决冲突，画出最终的哈希表。【解答】5.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：

1）查找不成功，即表中无关键字等于给定值K的记录；

2）查找成功，即表中有关键字等于给定值K的记录。【解答】1）查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表一样。2）查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。6.设有序表为(a,b,c,d,e,f,g,h,i,j,k,p,q),请分别画出对给定值b,g进行折半查找的过程。

【解答】1）查找b的过程如下第一次比较：[a

b

c

d

e

f

(g)

h

i

j

k

p

q]

第二次比较：[a

b(c)d

e

f]

g

h

i

j

k

p

q

第三次比较：[a(b)]c

d

e

f

g

h

i

j

k

p

q

经过三次比较，查找成功。2）查找g的过程如下：第一次比较：[a

b

c

d

e

f

(g)

h

i

j

k

p

q]

一次比较成功。说明：方括号表示当前查找区间，圆括号表示当前比较的关键字7.设哈希表地址为HT[0..10]，关键字的集合为key={24,38,23,70,56,53,43,64,36}，哈希函数使用“除留余数法”，求哈希表。【解答】Key243823705653436436K%1125141910938．关键字集合为{47，7，29，11，16，92，22，8，3},表长为11。选取哈希函数：Hash(key)=keymod11，用线性探测法处理冲突，构造哈希表，并求其查找成功时的平均查找长度。【解答】由给定的哈希函数得到的初始哈希地址如下：关键字477291116922283地址377054083分析可知，关键字为47和7直接存入地址。对于关键字29，Hash（29）=7的地址发生冲突，根据探测序列，H1=（Hash（29）+1）%11=8，地址为空，存入。以此类推，构造哈希表如下所示。012345678910112247921637298对关键字为47、7、11、16、92的查找只需1次比较，对关键字为29、8、22的查找需2次比较，对关键字为3的查找需比较4次。故，平均查找长度为：ASL=（1*5+2*3+4*1）/9=15/9第11章排序一．选择题1．C2．C3．B二．简答题（1）已知序列{503，87，512，61，908，170，897，275，653，462}，写出采用快速排序法对该序列升序排序的第一趟的结果。【解答】（2）已知序列{10，18，4，6，12，1，9，16}，请使用堆排序对该序列做升序排序，要求写出每一趟的排序后的结果。【解答】第1次调整为堆：18,16,9,10,12,1,4,6=>（6,16,9,10,12,1,4）,18第2次调整为堆：（16,12,9,10,6,1,4）,18=>（4,12,9,10,6,1）,16,18第3次调整为堆：（12,10,9,4,6,1）16,18=>（1,10,9,4,6,）,12,16,18第4次调整为堆：（10,6,9,4,1）,12,16,18=>（1,6,9,4）,10,12,16,18第5次调整为堆：（9,6,1,4）,10,12,16,18=>（4,6,1）,9,10,12,16,18第6次调整为堆：（6,4,1）,9,10,12,16,18=>（1,4）,6,9,10,12,16,18第7次调整为堆：（4,1）,6,9,10,12,16,18=>（1）,4,6,9,10