已阅读5页,还剩1页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
电子科技大学 2010 -2011 学年第 2 学期期 末 考试 A 卷 课程名称:_离散数学(双语) 考试形式: 闭卷 考试日期: 2011 年 月 日 考试时长:_120 分钟 课程成绩构成:平时 10 %, 期中 10%, 实验 10%, 期末 70% 本试卷试题由_7 _部分构成,共_6 _页。 题号 一 二 三 四 五 六 七 八 九 十 合计 得分 I. Multiple Choice (20%, 10 questions, 2 points each) ( A) 1. Suppose U = 1, 2, ., 9, A = all multiples of 2, B = all multiples of 3, and C = 3, 4, 5, 6, 7. Then C - (B - A)= a) 4,5,6,7 b) 3,4,5,6 c) 4,6 d) 5,7 ( B) 2 Which of these implications is false? a) If 1 0, then 3 4. b) If 1 1 2 or 1 1 3, then 2 2 3 and 2 2 4. c) If 2 1 3, then 2 3 1. d) 1 1 3 if and only if 2 2 3. ( C) 3 Which of these propositions is not logically equivalent to the other three? a) (p q) (r q) b) (p r) q c) (pr) q d) The contrapositive of q (p r) ( B) 4. The best big-O function for n3 sin(n7). a) n7 b) n3 c) n5 d) n6 ( C) 5. How many different license plates are available if a license plate consists of 3 decimal digits(from 0 to 9) followed by 4 uppercase letters? a) P(10,3) P(26,4) b) C(10,3) C(26,4) c) 103 264 d) 3 10+4 26 ( D) 6. Suppose R1 and R2 be transitive on A. Which of the following is transitive? a) R1R 2 b) R1oR2 c) R2oR1 d) R1R 2 ( A) 7. If , then R is 01RM a) reflexive b) symmetric c) antisymmetric d) transitive. (A ) 8. Which of the following set is uncountable? a) The set of real numbers between 172 and 173. b) The set of integers c) The set of integers not divisible by 3. d) The union of two countable sets. 得 分 (A ) 9. Determine which of the following sequences are graphic,i.e. arise as the degree sequence of a simple graph G. a) 2,1,1,1,1 b) 3,3,2,2,1 c) 4,4,3,2,1 d) 4,4,3,3,3 (A ) 10. If all sets are finite, which of the following must be true? a) If a function is bijective, its domain and co-domain have the same cardinality. b) If a function is one-to-one, its domain and co-domain have the same cardinality. c) If a function is onto, its domain and co-domain have the same cardinality. d) If a function is neither one-to-one nor onto, its domain and co-domain do not have the same cardinality. II. True or False (10%, 10 questions, 1 point each) (F ) 1. The following sentence is a proposition: “Take two aspirin.” (F ) 2. A bipartite graph with an odd number of vertices that has a Hamilton circuit. (F ) 3. p (q r) is equivalent to (p q) r. (F ) 4. The proposition (p q) p) q is a tautology. (T ) 5. A B A (B A). (T ) 6. The set a is the power set of some set (F ) 7. Suppose B xx, then x B. (F ) 8. f N N where describes a function with the given domain and codomain.()fn (F ) 9. Suppose g A B and f B C, where f g is 1-1 and g is 1-1. Then f must be 1-1. (F ) 10. For all integers abcd, if a b and c d, then (ac) (b d). III. Fill in the Blanks (20%, 10 questions, 2 points each) 1. Find ( ). 1i ,. 2. Write the negation of the statement “Some bananas are yellow.” in good English: No bananas are yellow. 3. Suppose the variable x represents students and y represents courses, and T(x,y): student x is taking course y. Write the statement “Every student is taking at least one course.” using these predicates and any needed quantifiers:xy T(xy). 4. Find -84 61(2).ii 5. The twos complement of 12 is 0 1100 . 得 分 得 分 课程组长(签字) 系主任(签字) 学院 姓名 学号 选课/座号号 任课老师 密封线以内答题无效 第 3 页 共 6 页 6. An inverse of 5 modulo 12 is 5 . 7. If R=(12)(14)(23)(31)(42), the reflexive closure of R is (11)(12)(14)(22)(23)(31)(33)(42)(44). 8. Write a proposition equivalent to p q using only pq and the connective : (p q). 9. The negation of the statement xy (xy = 0) is xy (xy 0) . 10. The vertex-chromatic number for bipartite K77 is 2 . IV. Answer the Questions (30%,6 questions, 5 points each): 1. Suppose f R R where f(x) x2. (a) If S x 1 x 6, find f(S). (b) If T 345, find f1(T). Ans: (a) 0123 (b) 612). 2. Use the definition of big-oh to prove that 13 23 n3 is O(n4). Ans: 13 23 n3 n3 n3 n3 n n3 n4. 3. Given that gcd(662414) 2, write 2 as a linear combination of 662 and 414. Ans: 662 (5) 414 8. 4. Give a recursive algorithm for computing na, where n is a positive integer and a is a real number. Ans: The following procedure computes na: procedure mult(a: real number, n: positive integer) if n 1 then mult(an) a else mult(an) a mult(an 1). 得 分 5. Represent the expression (x + xy) + (x/y) using a binary trees. 6. Determine whether these two graphs are isomorphic, and explain the reason. Ans: The graphs are isomorphic: label the graph clockwise from the top with 2,3,6,5,4,1. V. (6%) Prove that the distributive law A1 (A2 An) (A1 A2) (A1 An) is true for all n 3. Ans: The second form of mathematical induction is used. P(3) is true since it is the ordinary distributive law for intersection over union. P(3) P(n) P(n 1): A1 (A2 An 1) A1 (A2 An) An 1) A1 (A2 An) (A1 An 1) (A1 A2) (A1 An) (A1 An 1) (A1 A2) (A1 An 1). Grading rubric: -3 points for making wrong assumptions. 得 分 课程组长(签字) 系主任(签字) 学院 姓名 学号 选课/座号号 任课老师 密封线以内答题无效 第 5 页 共 6 页 -2 points for not being able to complete the proof. -1 to -3 points for illegal usage of inference rules. VI. (7%) Use Dijkstras algorithm to compute the shortest path from A to I, where edge labels indicate the distance (or cost) between vertices. For each iteration, write down the shortest path (i.e., its length and the vertices in it) from A to each vertex that has been found so far, and also indicate which vertices are currently in the set S. Vertices in S are shown in bold font. (1) A: 0; B: ; C: ; D: ; E: ; F: ; G: ; H: ; I: (2) A: 0; B: 3 (A); C: ; D: 7 (A); E: ; F: ; G: ; H: ; I: (3) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: ; G: ; H: ; I: (4) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: 15 (A, B, C); G: ; H: ; I: (5) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: 15 (A, B, C); G: 8 (A, D); H: ; I: (6) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: 15 (A, B, C); G: 8 (A, D); H: 10 (A, D, G); I: (7) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 15 (A, B, C); G: 8 (A, D); H: 10 (A, D, G); I: 16 (A, D, G, H) (8) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 13 (A, D, G, H, E); G: 8 (A, D); H: 10 (A, D, G); I: 16 (A, D, G, H) (9) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 13 (A, D, G, H, E); G: 8 (A, D); H: 10 (A, D, G); I: 14 (A, D, G, H, E, F) (10) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 13 (A, D, G, H, E); G: 8 (A, D); H: 10 (A, D, G); I: 14 (A, D, G, H, E, F) The shortest path passes through the vertices A, D, G, H, E, F, and I, and it covers a total distance of 14. Grad
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2030年中国充气膜建筑行业市场现状分析及竞争格局与投资发展研究报告
- 2024-2030年中国儿童护肤品行业市场发展分析及前景趋势与投资研究报告
- 2024-2030年中国催化剂载体活性炭行业销售态势与盈利前景预测报告
- 脚手架工程承包合同范文(16篇)
- 2024-2030年中国保温冷藏车行业发展分析及发展前景与趋势预测研究报告
- 2024-2030年中国供应链可视化解决方案行业发展策略与前景动态预测报告
- 老住房装修合同规定(21篇)
- 绿化工程承包合同书16篇()
- 2024-2030年中国亚麻箱包面料行业发展分析及发展趋势预测与投资风险研究报告
- 2024-2030年中国二氢叶酸行业市场发展趋势与前景展望战略分析报告
- 公益林护林员培训
- (高清版)DZT 0292-2016 海洋多波束水深测量规程
- 人保财险在线测评试题及答案
- 2024版国开电大专科《ECEL在财务中的应用》在线形考(形考作业一至四)试题及答案
- 犯罪学智慧树知到期末考试答案2024年
- 大学学院“十四五”师资队伍建设规划(2021-2025)
- 食品监管业务培训课件
- 智慧高校大数据平台解决方案
- 2024年国家能源集团国源电力神东电力公司招聘笔试参考题库含答案解析
- NGS市场行业分析
- 生殖内分泌的现状与发展主要内容
评论
0/150
提交评论