python数据结构题目

作者: Rain师兄 | 来源:发表于2022-04-20 21:29 被阅读0次

在图的邻接表存储结构下（基于顶点列表和单链表实现），本题要求图类里实现2个方法函数 def addVertex(self, vex_val): def addEdge(self, f, t, cost=0):

在这里描述函数接口。例如：
 def addVertex(self, vex_val):

def addEdge(self, f, t, cost=0):

在这里解释接口参数。例如：其中 f和t分别是构成边的顶点在列表中的序号。
裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：
class arcnode:
    def __init__(self,adjvex,weight,link=None):
        self.adjvex = adjvex
        self.weight = weight
        self.link=link

class vexnode:
    def __init__(self,data,first_arc=None):
        self.data = data
        self.first_arc = first_arc

class Graph:
    def __init__(self):
        self.vex_list=[]
        self.vex_num=0
        self.edge_num=0
    # 请在这里填写答案
        
        
   # 请在这里填写答案
     
     
    def print_graph(self):
        for i in range(self.vex_num):
            print(self.vex_list[i].data,end="->")
            cur = self.vex_list[i].first_arc
            while cur:
                print("adj:{},weight:{}".format(cur.adjvex,cur.weight),end="->")
                cur = cur.link
            print('None')

if __name__ =="__main__":
    g = Graph()
    s =input()
    for vertex in s:
        g.addVertex(vertex)

    g.addEdge(0,1,11)
    g.addEdge(0,2,55)
    g.addEdge(2,3,88)
    g.addEdge(0,3,33)
    g.addEdge(1,2,44)
    g.print_graph()

image.png

输出样例：
在这里给出相应的输出。例如：

A->adj:3,weight:33->adj:2,weight:55->adj:1,weight:11->None
B->adj:2,weight:44->adj:0,weight:11->None
C->adj:1,weight:44->adj:3,weight:88->adj:0,weight:55->None
D->adj:0,weight:33->adj:2,weight:88->None

在图的邻接表存储结构下（基于顶点列表和单链表实现），本题要求图类里实现方法函数广度优先搜索遍历

函数接口定义：
在这里描述函数接口。例如：
def bfs(self,start):
在这里解释接口参数。例如：其中 f和t分别是构成边的顶点在列表中的序号。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：

visited_list = [False]*7
class arcnode:
    def __init__(self,adjvex,weight,link=None):
        self.adjvex = adjvex
        self.weight = weight
        self.link=link

class vexnode:
    def __init__(self,data,first_arc=None):
        self.data = data
        self.first_arc = first_arc

class Graph:
    def __init__(self):
        self.vex_list=[]
        self.vex_num=0
        self.edge_num=0
    def addVertex(self, vex_val):
        self.vex_num += 1  # 因为增加了一个顶点，所以顶点总数要+1
        self.vex_list.append( vexnode(vex_val) )  # 顶点列表加一个顶点元素
    def addEdge(self, f, t, cost=0):  #加一条边
        edge_node1 = arcnode(t,cost)
        edge_node2 = arcnode(f,cost)
        edge_node1.link = self.vex_list[f].first_arc
        self.vex_list[f].first_arc = edge_node1
        edge_node2.link = self.vex_list[t].first_arc
        self.vex_list[t].first_arc = edge_node2
        self.edge_num += 1
    def print_graph(self):
        for i in range(self.vex_num):
            print(self.vex_list[i].data,end="->")
            cur = self.vex_list[i].first_arc
            while cur:
                print("adj:{}".format(cur.adjvex),end="->")
                cur = cur.link
            print('None')

#  请在此处填写答案
            
        
        
    

if __name__ =="__main__":
    g = Graph()
    s =input()
    for vertex in s:
        g.addVertex(vertex)

    g.addEdge(0,2)
    g.addEdge(0,3)
    g.addEdge(0,4)
    g.addEdge(3,1)
    g.addEdge(3,2)
    g.addEdge(5,2)
    g.addEdge(5,1)
    g.addEdge(5,4)
    g.addEdge(5,6)
    
    g.print_graph()
    g.bfs(0)

输入例子：

image.png

输出样例：
在这里给出相应的输出。例如：

0->adj:4->adj:3->adj:2->None
1->adj:5->adj:3->None
2->adj:5->adj:3->adj:0->None
3->adj:2->adj:1->adj:0->None
4->adj:5->adj:0->None
5->adj:6->adj:4->adj:1->adj:2->None
6->adj:5->None
0 4 3 2 5 1 6

在图的邻接矩阵存储结构下，本题要求图的深度优先搜索遍历函数注意（非类的方法函数）

函数接口定义：

在这里描述函数接口。例如：
def dfs(graph,start):

在这里解释接口参数。例如：其中 f和t分别是构成边的顶点在列表中的序号。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：
class mGraph:
    def __init__(self,vertex,mat):   #vertex 为顶点列表， mat为邻接矩阵 列表的列表
        self.vertex = vertex
        self.vnum = len(vertex)    #图顶点的个数
        self.mat = mat      #  [mat[i][:] for i in range(self.vnum) ]

def create_mGraph():
    nodes = ['0','1','2','3','4','5','6']
    martrix = [[0,0,1,1,1,0,0],
               [0,0,0,1,0,1,0],
               [1,0,0,1,0,1,0],
               [1,1,1,0,0,0,0],
               [1,0,0,0,0,1,0],
               [0,1,1,0,1,0,1],
               [0,0,0,0,0,1,0] ]
    myGraph = mGraph(nodes,martrix)
    return myGraph

# 请在此写答案

if __name__ == "__main__":
    g1=create_mGraph()
    visited_list=[0]*g1.vnum
    while sum(visited_list)<g1.vnum:
        dfs(g1,visited_list.index(0))

输入样例：

在这里给出一组输入。例如：

[图片上传失败...(image-aa9642-1650461164505)]

输出样例：

在这里给出相应的输出。例如：

0 2 3 1 5 4 6

在图的邻接表存储结构下（基于顶点列表和单链表实现），本题要求图类里实现方法函数深度优先搜索遍历

函数接口定义：

在这里描述函数接口。例如：
    def dfs(self,start):

在这里解释接口参数。例如：其中 f和t分别是构成边的顶点在列表中的序号。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：
visited_list = [False]*7
class arcnode:
    def __init__(self,adjvex,weight,link=None):
        self.adjvex = adjvex
        self.weight = weight
        self.link=link

class vexnode:
    def __init__(self,data,first_arc=None):
        self.data = data
        self.first_arc = first_arc

class Graph:
    def __init__(self):
        self.vex_list=[]
        self.vex_num=0
        self.edge_num=0
    def addVertex(self, vex_val):
        self.vex_num += 1  # 因为增加了一个顶点，所以顶点总数要+1
        self.vex_list.append( vexnode(vex_val) )  # 顶点列表加一个顶点元素
    def addEdge(self, f, t, cost=0):  #加一条边
        edge_node1 = arcnode(t,cost)
        edge_node2 = arcnode(f,cost)
        edge_node1.link = self.vex_list[f].first_arc
        self.vex_list[f].first_arc = edge_node1
        edge_node2.link = self.vex_list[t].first_arc
        self.vex_list[t].first_arc = edge_node2
        self.edge_num += 1
    def print_graph(self):
        for i in range(self.vex_num):
            print(self.vex_list[i].data,end="->")
            cur = self.vex_list[i].first_arc
            while cur:
                print("adj:{}".format(cur.adjvex),end="->")
                cur = cur.link
            print('None')

#  请在此处填写答案

if __name__ =="__main__":
    g = Graph()
    s =input()
    for vertex in s:
        g.addVertex(vertex)

    g.addEdge(0,2)
    g.addEdge(0,3)
    g.addEdge(0,4)
    g.addEdge(3,1)
    g.addEdge(3,2)
    g.addEdge(5,2)
    g.addEdge(5,1)
    g.addEdge(5,4)
    g.addEdge(5,6)

    g.print_graph()
    g.dfs(0)

输入样例：

在这里给出一组输入。例如：

image.png

输出样例：

在这里给出相应的输出。例如：

0->adj:4->adj:3->adj:2->None
1->adj:5->adj:3->None
2->adj:5->adj:3->adj:0->None
3->adj:2->adj:1->adj:0->None
4->adj:5->adj:0->None
5->adj:6->adj:4->adj:1->adj:2->None
6->adj:5->None
0 4 5 6 1 3 2

编程题
布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：
对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。

输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例：
No problem
OK
OK but...
No way

在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）

设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。

输入格式：
首先第一行给出两个正整数：鳄鱼数量 N（≤100）和007一次能跳跃的最大距离 D。随后 N 行，每行给出一条鳄鱼的 (x,y) 坐标。注意：不会有两条鳄鱼待在同一个点上。

输出格式：
如果007有可能逃脱，就在一行中输出"Yes"，否则输出"No"。

输入样例 1：
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
输出样例 1：
Yes
输入样例 2：
4 13
-12 12
12 12
-12 -12
12 -12
输出样例 2：
No

python数据结构题目

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读