《离散数学题库简答题》由会员分享，可在线阅读，更多相关《离散数学题库简答题（22页珍藏版）》请在装配图网上搜索。

1、编号题目答案题型分值大纲难度1 1设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 答: ， t (R)= , , , , , , , , 简答题84.332如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。答: 用Kruskal算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。简答题87.233设是一个群，这里+6是模6加法，Z6=0 ，1，2，3，4，5，试求出的所有子群。答: 子群有；简答题88.334权数1，4，9，16

3、347利用主析取范式，判断公式的类型。答: 它无成真赋值，所以为矛盾式。简答题82.338在二叉树中:1)求带权为2，3，5，7，8的最优二叉树T。（4分）2)求T对应的二元前缀码。（4分）答: （1）由Huffman方法,得最佳二叉树为：（2）最佳前缀码为：000，001，01，10，11简答题87.239下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。答:

24。简答题84.4411设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？答: 公式A涵义为：对任意的实数x,y,z，如果xy 则 (x-z) (y-z) A的真值为： 真（T）。简答题83.2312给定3个命

简答题83.2315简述关系的性质有哪些？自反性，对称性，传递性，反自反性，反对称性简答题84.3116假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传

6、输它们的最佳前缀码，并给出happy new year的编码信息。答:解：传输它们的最佳前缀码如上图所示，happy new year的编码信息为：10 011 1 110 111 011 000 附：最优二叉树求解过程如下：简答题87.2317用washall方法求图的可达矩阵，并判断图的连通性。答: 1：A2，1=1，； 2： A4，2=1，3： A1，3=A2，3=A4，3=1，4： Ak，4=1，k=1，2，3，4，p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。简答题86.3318设有a、b、c、d、e、f、g七个人，他

7、们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？答:用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为此图中的Hamilton回路即是圆桌安排座位的顺序。Hamilton回路为a b d f g e c

8、最佳前缀码。（答: （1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e传输它们的最优前缀码为0000，0001，001，01，10，11 。简答题87.2320构造一个结点v与边数e奇偶性相反的欧拉图。答: 简答题86.4521设A=1，2，3，4，S=1，2，3，4，为A的一个分划，求由S导出的等价关系。答: R= , , , , 简答题84.4322设，偏序集的Hass图为求 A中最小元与最大元； 的上界和上确界，下界和下确界。答: A中最大元为 ，最小元不存在； 上界 ，上确界；下界无，下确界无。简答题84.4323用Warshall算法，对集合A

简答题82.1;3.1;3.2325)、画一个有一条欧拉回路和一条汉密尔顿回路的图。)、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。)、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。答:简答题86.4326求的主合取范式。答: 简答题82.3327在下面关系中:判定关系的

10、性质。答: R自反任意实数x，x-x+20 ， x-x-20 , 所以直线y=x上的点在区域内，即 , 故R自反； R对称若 有 得 即 所以 R对称；因R自反且结点集非空，故R非反自反；因R对称且结点集非空，并非全是孤立点，故R不是反对称；由 得 所以 而 所以R4不是传递的。简答题84.3428求图的邻接矩阵和可达矩阵。答: ， ， ，。所以可达矩阵简答题86.3329已知某有向图的邻接矩阵如下： 试求：到的长度为4的有向路径的条数。答: ， ， ， ，由到长度为4的有向路径的条数为3条。简答题86.3330已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）

11、。答: 设该树有t 片树叶，总结点数为 总边数为 所以 ， 29+t=2(8+t) 即 t=13 。 该树有13片树叶。简答题87.1;7.2331设和是A上的任意二元关系，如果和是自反的，是否也是自反的，为什么？如果和是对称的，是对称的吗？答: 若是自反的，则也是自反的。因为 自反，从而 ，即也是自反的。 若是对称的，但不一定是对称的。 如：A = a , b , c，则是对称的，但不是对称的。简答题84.3432如图给出的赋权图表示六个城市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。答: 要设计一个方案使各城市间能够通讯且总造

12、价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：其最小生成树为：其树权即最小造价为：1+2+3+5+7=18。简答题87.1;7.2333设S = R - -1（R为实数集），。 说明是否构成群； 答: 1），即运算*是封闭的。 2） 而，即*可结合。 3）设S关于*有幺元e，则。而 。4） 设有逆元 。则，即 ，即 S中任意元都有逆元，综上得出，构成群。简答题88.3534将公式划为只含有联结词的等价公式。答: 原式 。简答题82.1;2.2335设和都是群的子群，问和是否是的子群并说明理由。答: 是 的子群，不一定是的子群。 都是的子群， 的子群。如：

13、G = 1，5，7，11，：模12乘，则为群。且H = 1，5，K = 1，7，皆为的子群，但， 不是的子群。因为 ，即运算不封闭。简答题88.3536设，从A到B的关系，试给出R的关系图和关系矩阵，并说明此关系是否为函数？为什么？A答: 则R的关系图为：R的关系矩阵为 关系R不是A到B的函数，因为元素2，4的象不唯一（或元素9无象）。简答题85.2;4.2437设是半群，是左零元，对任是否是左零元？为什么？答: 仍是左零元。因为，由于是左零元，所以，又 为半群，所以*可结合。 所以，所以，仍是左零元。简答题88.1338某次会议有20人参加，其中每人至少有10个朋友，

14、这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）答: 可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知， ，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。简答题86.4339通过主合取范式，求出使公式的值为F的真值指派。答: 使公式的值为F的真值指派为： ； ； 。简答题82.2;2.3340设，A上的关系 ，求出。答: ， ， ，。简答题84.1;4.3341已知，为模7乘法。试说明是否构成群？是否为循环群？若是，生成元是什么？答: 既构成群，又构成循环群，

15、其生成元为3，5。因为：的运算表为： 1）由运算表知，封闭；2）可结合（可自证明）3）1为幺元；4），综上所述，构成群。 由，。所以，3为其生成元，3的逆元5也为其生成元。故为循环群。简答题88.1;8.3542用等值演算法求下面公式的主析取范式，并求其成真赋值。答: 原式 使其成真赋值为： ， ， ， ， ，简答题82.1;2.3343集合上的关系，写出关系矩阵，画出关系图并讨论R的性质。答: R的关系图为 R是自反、对称的。简答题84.1;4.3344一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。（1）T中有几个结点；（2）画出具有上述度数的所有非同构的无向图。答: （1）设

16、该树树叶数为t，则树T的结点数为，又边数 = 结点数 1， ， 即 ， ， （1）和（2）都不是A的划分。（3）是A的划分。其诱导的等价关系是I,。简答题84.4346设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路

17、总数。答: M= M2= G中长度为2的路总数为18，长度为2的回路总数为6。简答题86.3447设A=1,2,3,4,5,A上偏序关系R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序关系R的哈斯图(2)令B=1,2,3,5，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。答: 偏序关系R的哈斯图为 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4， 下确界4； 上界：无，上确界：无 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4， 下确界4； 上界：无，上确界：无简答题84.4448求(PQ

简答题83.2350设A=a,b,c ，P（A）是A的幂集，是集合对称差运算。已知是群。在群中，找出其幺元。找出任一元素的逆元。求元素x使满足ax=b。答:e=; 任一元素x的逆元x-1;x=a-1b=ab=a,b。简答题88.1;8.33

2007 级 管理类 本科A卷 课程名称 管理运筹学 课程号（3520070）考试形式（ 闭卷 ） 时间（ 120 分钟）

题 目 一 二 三 四 总 分 统分人 复核人 得 分 注意：①提醒考生自带直尺等绘图工具。

②解题过程要步骤明确，字迹清晰。

得分 评卷人 一、单项选择题(每小题1分，共20分) 1. 在不确定性决策中，( )不正确。 A .有两个或两个以上可供选择的可行方案

B .决策目标是使利润最大

C .有两种或两种以上的自然状态，且各状态出现的概率未知

D .可以预测或估计出不同的可行方案在各自然状态下的收益值或损失值2. 有关线性规划，( )是错误的。

A .当最优解多于一个时，最优解必有无穷多个 B .当有可行解时必有最优解

C .当有最优解时必有在可行集顶点达到的最优解 D .当有可行解时必有可行基解

3. 对同一种资源来讲，影子价格与市场价格之间的关系为( )。 A .影子价格就是市场价格 B .影子价格高于市场价格 C .影子价格低于市场价格

D .影子价格与市场价格没有关系，只是反映了资源的利用是否充分 4. 对乐观系数决策标准而言，乐观系数a＝1即为( )决策标准，a＝0即为( )决策标准。

A .乐观，悲观 B .悲观，乐观 C .悲观，悲观 D .乐观，乐观

5. 设LP是线性规划问题，DP是其对偶问题，则( )不正确。 A .LP有最优解，DP不一定有最优解

B .若LP和DP都有最优解，则二者最优值肯定相等 C .若LP无可行解，则DP无有界最优解 D .DP的对偶问题为LP

6. 动态规划方法中，状态变量的“无后效性”是指 ( )。 A .给定阶段的状态与任何以前的状态有关

B .给定阶段状态后，过程以后的发展与任何以前的状态无关

C .给定阶段的状态后，过程以后的发展与任何以前的状态有关

D .给定阶段的状态与任何以前的状态无关

7. PERT网络图中，关键工序是指( )。 A .最先开始的工序 B .最后结束的工序

C .工序单时差为零的工序

D .关键路线上工序总时差为零的所有工序 8. 二人零和对策中“零和”的含义是指 ( )。 A .甲方的赢得值为零 B .乙方的赢得值为零 C .二人的赢得值都是零

D .二人的得失相加为零

9. 甲乙两城市之间存在一公路网络，为了判断在两小时内能否有3600辆车从甲城到乙城，应借助（ ） A .树的生成法 B .求最小树法 C .求最短路法 D .求最大流法

10. 若运输问题在总供应量大于总需要量时，( )。 A .必须用线性规划单纯形法求最优解 B .不存在可行解 C .虚设一个需求点 D .虚设一个供应点 11. 运筹学模型，( )。

A .在任何条件下均有效

B .只有符合模型的简化条件时才有效 C .可以解答管理部门提出的任何问题 D .是定性决策的主要工具

12. 线性规划问题中只满足约束条件的解称为 ( )。 A .基本解 B .最优解 C .可行解 D .基本可行解 13. 在图论中，( )不正确。

A .若树T有n个点，则其边数为n-1 B .树中若多出一边，必出现圈 C .树中点与点可以不连通 D .树中若除去一边，必不连通

14. 在ABC分析法中，B类物资需用价值约占全部物资需用价值总额的( ) A .约10％

15. 决策树法是—种( )条件下的决策方法。 A .确定性 B .不确定性 C .风险

16. 传统的求解线性规划的单纯形法的基本原理是 ( )。 A .插值法 B .迭代法 C .分支定界 D .黄金分割

17. 最大流问题中同一段弧上的实际流量与容量之间的关系是( )。 A .流量大于容量 B .流量等于容量 C .流量小于容量

D .流量与容量没有什么关系

18. 在中美篮球比赛（对策论问题）中，称为局中人的是 ( )。 A .双方领导人 B .双方的教练 C .两个国家的人民 D .中日参赛的国家队

19. 能够采用图解法的进行求解的简单线性规划问题的变量个数为 ( )。 A .1个 B .2个 C .3个 D .4个

20. 动态规划是解决（ ）决策过程最优化问题的一种方法。

B、基本可行解一定是基本解；

C、线性规划一定有可行解； D、线性规划的最优值至多有一个。

2、运输问题的基本可行解有特点（ ）。 A、有m＋n－1个基变量； B、有m+n个位势；

C、产销平衡； D、不含闭回路。 3、下面命题正确的是（ ）。

A、线性规划标准型要求右端项非负； B、任何线性规划都可化为标准形式；

C、线性规划的目标函数可以为不等式； D、可行线性规划的最优解存在。 4、单纯形法计算中哪些说法正确（ ）。 A、非基变量的检验数不为零； B、要保持基变量的取值非负；

C、计算中应进行矩阵的初等行变换； D、要保持检验数的取值非正。

5、线性规划问题的灵敏度分析研究（ ）。 A、对偶单纯形法的计算结果；

B、目标函数中决策变量系数的变化与最优解的关系； C、资源数量变化与最优解的关系；

D、最优单纯形表中的检验数与影子价格的联系。

6、在运输问题的表上作业法选择初始基本可行解时，必须注意（ A、针对产销平衡的表；

B、位势的个数与基变量个数相同；

C、填写的运输量要等于行、列限制中较大的数值； D、填写的运输量要等于行、列限制中较小的数值。 7. 存储问题中的不允许缺货模型的假设中，包括 ( )。 A .单位时间的需求量不变

B .供货速度为常数且大于需求速度 C .各种费用为常数 D .存储量为常数

8. 应用决策树法进行决策，以下错误的是( ) A .确定型决策 B .不确定型决策

C .与期望值的表格．计算法一致

D .与期望值的表格计算法是本质上不同的两种计算方法

。 ） 9. 在决策树方法中，图中的小方框表示决策（ ），由它引出的分枝称为（ ）分枝。

B .方案，决策 C .决策，决策 D .方案，方案

10. 风险条件下的决策，不可采用( )

A .乐观主义决策标准 B .决策树法

C .折衷主义决策标准

D .最小最大遗憾值决策标准 题号 1 2 3 4 5 6 7 8 9 10 答案 得分 评卷人 三、解答下列各题（每小题5分，共30分） 1、简述线性规划模型的三个基本特征。 1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。 2）存在一组线性等式或不等式的约束条件。 3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。 2、考虑线性规划问题

3、某咨询公司，受厂商委托，对新上市的一种新产品进行消费者反映的调查。该公司采用了挨户调查的方法，委托他们调查的厂商以及该公司的市场研究专家对该调查提出下列几点要求： （1）必须调查2000户人家；

（2）在晚上调查的户数和白天调查的户数相等； （3）至少应调查700户有孩子的家庭； （4）至少应调查450户无孩子的家庭。 每会见一户家庭，进行调查所需费用为

家庭 白天会见 晚上会见 有孩子 25元 30元 无孩子 20元 24元 问为使总调查费用最少，应调查各类家庭的户数是多少？（只建立模型）标准答案：

设xij表示i时会见的j种家庭的人数 目标函数：（2分）

在可行基B2、B3、B5、B6、B9、B10中，最优基为B2，最优解为： 是基础可行解，目标函数值为：

5、用图解法求解下列问题

6、请指出M/M/S/K排队模型中各字符的含义；并指出什么时候是损失制排队模型，什么时候是等待制排队模型。(3分)

第一个M表示顾客到达的时间间隔服从负指数分布； 第二个M服务时间为负指数分布；S个服务台；系统容量为K的排队模型 。 当 K= S 时为损失制排队模型； 当 K= ? 时为等待制排队模型。 得分 评卷人 四、计算题（共40分）

1、（ 10 分）某报亭出售某种报纸，每售出一百张可获利

15元，如果当天不能售出，每一百张赔20元。每日售出该

报纸份数的概率为 ，根据以往经验如下表所示。试问报亭每日定购多少张该种报纸能使其赚钱的期望值最大？

满足条件，所以当报亭每日购800张报纸能使其赚钱的期望最大。(3分)

2、（ 10 分）下述线性规划问题

先用单纯形法求出最优解，然后分析在下列条件下，最优解分别有什么变化？ （ 1 ）约束条件①的右端常数由 20 变为 30 ； （ 2 ）约束条件②的右端常数由 90 变为 70 ； （ 3 ）目标函数中的 x3 的系数由 13 变为 8 ； （ 4 ）增加一个约束条件③ 2x1+3x2+5x3 ≤ 50 （ 5 ）将原有约束条件②变为 10x1+5x2+10x3 ≤ 100 参考答案

目标函数最优值为: 100

3、（ 10 分）某地区有三个化肥厂，除供应外地区需要外，估计每年可供应本地区的数字为：化肥厂 A —7 万吨， B —8 万吨， C —3 万吨。有四个产粮区需要该种化肥，需要量为：甲地区—6 万吨，乙地区—6 万吨，丙地区—3 万吨，丁地区—3 万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下表所示（单位：元 / 吨）：

参考答案 最优解如下:

2 6 2 0 0 3 0 0 3 0 此运输问题的成本为: 89 4、（10分）有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表： 项目 投入资金 A B C 1万元 15万吨 13万吨 11万吨 2万元 28万吨 29万吨 30万吨 3万元 40万吨 43万吨 45万吨 4万元 51万吨 55万吨 58万吨 求对三个项目的最优投资分配，使总投资效益最大。（要求建立动态规划模型，详细列出求解过程）

3、参考答案（8分） 1）建模过程（4分） 写出状态转移方程得2分

阶段k：每投资一个项目作为一个阶段k=3；(A/B/C) （0.5分） 状态变量xk：投资第k个项目前的资金数； （0.5分） 决策变量dk：第k个项目的投资；（0.5分） 决策允许集合：0≤dk≤xk（0.5分） 状态转移方程：xk+1=xk-dk（1分） 写出动态规划基本方程得2分 阶段指标：vk(xk ,dk)； （0.5分）

2）求解过程（4分，每步1分，写出结果得1分） k=4，f4(x4)=0

即项目A投资1万元，项目B投资0万元，项目C投资3万元，最大效益为60万吨。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库07运筹学试卷A答案在线全文阅读。

[版权声明] 本站所有资料由用户提供并上传，若内容存在侵权，请联系邮箱。资料中的图片、字体、音乐等需版权方额外授权，请谨慎使用。网站中党政主题相关内容(国旗、国徽、党徽)仅限个人学习分享使用，禁止广告使用和商用。