ZJU离散数学及其应用 2023春夏回忆题

本试卷内容由个人回忆，可能有误。实际上的试题是全英文的，部分内容由于具体表达记不清了用中文表述

个人笔记:https://birchtree2.github.io/categories/%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6/

一、判断题(10*2=20pts)

二、单项选择题(10*2=20pts)

三、填空题(5*3=15pts)

  1. 把infix notation转成prefix notation
  2. 求包含关系R的最小等价关系
  3. \(4\times 4\)有标号的棋盘, 放4个不同物体,两个物体不能在同一行或同一列，求方案数
  4. 求使得\(C_n\)与\(C_n\)的补图同构的n
  5. 求29在模37下的逆元

四、解答题 5.(15pts) \(a_n\) denotes the number of ternary string of length n containing 2 consecutive 0s (a)find the recursive relation of \(a_n\) (b)solve the recurrence using characteristic roots (c)solve the recurrence using generating function

6.(5pts): \(R\) is a relation on set \(A\) . \(S=\{(a,b)|a\in A,b\in A,\existssss c \ (a,c)\in R \wedge (c,b)\in R\}\). Prove that if \(R\) is an equivalence relation, then \(S\) is also an equivalence relation

7.(10pts): 给出A,B,C,D,E,F,G,H的出现频率 (a)计算哈夫曼编码 (b)计算平均编码长度

8.(15pts): a directed graph

image-20230621132426499

(a) Find the number of routes of length 4 in the directed graph (b) Find whether the directed graph is strongly connected. If not, find all the connected components. (c) Is the underlying undirected graph a Hamilton Graph? Give your reasons. (d)Use backtrace method to find the chromatic number of the underlying undirected graph (e)Use breadth-first search to find the spanning tree of the underlying undirected graph with root \(v_1\)

Comments