GESP-Python七级 题库
共 24 道题
,第 2 / 2 页
· 按题型筛选,点「查看答案」核对解析
23
判断题
偏易
按照下面的规则生成一棵二叉树:以一个人为根节点,其父亲为左子节点,母亲为右子节点。对其父亲、母亲分别用同样规则生成左子树和右子树。以此类推,记录30代的直系家谱,则这是一棵满二叉树。
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
24
简答题
偏难
城市规划


答案与解析
参考答案
# tokens里面缓存了输入 tokens = [] # 这个函数将输入的内容放到tokens里面,随后再读取tokens里的第一条内容作为输入 def get_val(): while not tokens: tokens.extend(input().split()) return int(tokens.pop(0)) # 得到城市和边的数量 n = get_val() m = get_val() # 邻接表,每一个节点后面的列表表示这个节点到列表里面的节点有边 e = [[] for _ in range(n + 1)] for _ in range(m): u = get_val() v = get_val() e[u].append(v) e[v].append(u) # 假设当前在遍历节点i,则d[j]表示节点i目前发现的到j的最短距离。如果这个值为n+1则表明我们还没遍历到j,否则表示我们已经遍历到了j d = [0] * (n + 1) # 这个列表其实是队列,用在以i为中心的广度优先搜索中,记录即将被bfs遍历到的节点 q = [0] * (n + 2) # 这个数组缓存了各个城市的建设成本 mx = [0] * (n + 1) def bfs(u): # 初始化d数组,表明所有节点都还没被遍历到 for i in range(1, n + 1): d[i] = n + 1 # 初始节点已经被遍历到了 d[u] = 0 # 将初始节点入队 q[1] = u # 广度优先的队列左右边界,初始化为1,表明还没开始遍历。这个队列的长度是n+2,而一共只有n个节点,所以这个队列肯定不会被装满,一个节点只会入队不超过1次 ql, qr = 1, 1 # 只要队列还不空就继续遍历 while ql <= qr: # 将队首的元素出栈,将队首元素称为x x = q[ql] ql += 1 # 遍历从x出发能够直接到达的节点 for y in e[x]: # 如果当前找到的最短路径不如从初始节点到x再多走一步,那么就将y节点入队 if d[x] + 1 < d[y]: d[y] = d[x] + 1 # 理论上来讲,使用数组一样的数据结构存储队列元素,这里需要取模。但是这道题里面,每一个节点只会入队一次,所以qr最大就到n+1,因此不需要取模 qr += 1 q[qr] = y # 队列中最后一个弹出的元素一定是最后入队的,这个元素一定离初始节点最远,所以他的距离就是建设难度 mx[u] = d[q[qr]] ans = 1 for i in range(1, n + 1): bfs(i) # 判断当前的建设难度是否小于之前找到的最小的,如果是则更新答案 if mx[i] < mx[ans]: ans = i print(ans)