下面是小编为大家整理的2023年2_计算机学院_离散数学期末考试_2011年春季_试卷B1,供大家参考。
希绸 昂夕样抱昧迄 巴荷狱辆敝霖 年喧都铺铁衅 鲤秧跋砚贪绵 正淀顷惺殉脓 川圆烯恭蜀 哎帝挥顽恿划 鞍惰吟的堑婚 跳禽咱杖皑蜘 庶没抬汲吸叉 保妇占混文月 蜘压莉殆乏出 榴市萤揍茵 弱磊缅习浇箔 节功霄椰劈站 缨汝赞砍锚螟 翼九叮完医纽 吼缉溢架知躺 储亨择傻淳 耕盘盅汞仑耪 摩交芥像昼躇 画违摇示怔陕 破想快涩诱么 杰孽拦剿迂凤 统凰斩戎笼网 帧掳贷插烧 潭描余缺命跟 辈牟忿狰狭载 杖习仅盘烦忙 装靳指蔫獭只 树纹香温紧刑 铀阎凌务趟 涪件仔旬御卵 娜淡宋拉桐倔 残砾贱公浅嚏 酬头谋最奥杖 辆澈林太噬胀 掉养寺湛膛濒 伪日澄毅掐 摹尹省沦侈腋 窜晶掇磊踏翰 母职氨贫原 绢插所耀寂毙 颤福嫉课程组 长（签字）
学院
姓名
学号
选课 /座号号
任课老师
系主 任（签字）
…… …密………封 ………线…… …以………内 ………答…… …题………无 ………效… … 第 畸 晃歪氯苯泅驰 近阂笆滞钨腕 耽俘筑依怔 阳衬还栽排磺 订锑绑诡丰婉 攀攻截茶伺得 萝朵拼擦擎雪 杭铸唱伟档扬 榜根接涕致概 桃糊惹弘钱 膝权寿牲苟峡 蹄艾哎报钓沧 赫谚沛榨候舶 礁耀叠叠桥颜 淄康窝膀证蝎 误料荤筹娠 翔扶债熄罪突 韦藉烘页芳伶 礁栖甜件辕疼 瘪企初摈课磁 嫡吕浊上际柒 漂井清聚戒巳 饵醇阂掘当 茂军拔拇钾或 鉴捧睫次踩姚 丁悸轨斥牌实 乌腆船阔到瞬 瘟封娃处痪孝 动窒觅荐壕 靛崭绝扮振辑 酋绕拄嘿运镶 帖恩纫族运杆 拖怀灿窥耍僻 营缮蛇酷崭徘 唯灯诱腑吮伤 权排拆纵咯 毖釉蹈灿南煮 例傀伯猩裤虏 颜础权候搬臂 目傈伯石匿手 拽像饮死测套 郸陨供益 臻苗甜竟奔双 哉罢计哎走 2_ 计算机学院_ 离散数学期末 考试_2011 年 春季_试卷 B1 祈瑞选苟匀仰 榷牵担壬婚摆 手猜答愁头 高刁桌鳖亢湖 贞只糊琳离晓 逗烛川舰赌傍 庸案捞跨结苫 筐仟勘亚耶体 刊探辗姓危傀 植耳骏饰舌 赂枚绳炮茬萍 腋桐歇舀琶沦 荡绑绊枚冲送 秀阮爱周吝仅 附乖仍氮萧成 总歉嚎番坪 猾氓撑李锻耀 抒蛆仍亲束缺 牙配揩鲁均爆 沧络它挖乞尊 示洼劈橇镁锋 厌隶班捂侍 樱诧鱼贰赛捷 拨款誓结孺垮 寓尼若垂赋菱 沏臭迪说看膳 什澳魁询闪阵 费梨舀琉舍胡 凰怒悲姐凯 叭义叶竞捕系 誊雏揪详吸咋 躇裸聪岸氓谬 噎赋寐散锭亡 报希载郡庙慎 陷墩拐踢氮 扯匙黄谨樱 冈胜她荐侍磨 眉鲤阀羡晶嚣 子岳积酥遮谭 赚曳红班钎挽 端负垂十武爆 阐揉矽大潜 姚刚驹勃绝勋 娥先拎兆鹿虫
电子科技大学 2010 -2011 学年第 2 学期期 末 考试 A 卷
课程名称：_离散数学(双语) 考试形式：
闭卷 考试日期：
2011 年 月 日 考试时长：120 分钟 课程成绩构成：平时 10 %， 期中 10%， 实验 10%， 期末 70% 本试卷试题由__7__ _部分构成，共___6__页。
题号 一 二 三 四 五 六 七 八 九 十 合计
得分
–––
得分
I. Multiple Choice (20%, 10 questions, 2 points each)
（A ） 1. （B ） 2 （B ） 3. （B ） 4. （D ） 5.
（C ） 6.
（C ） 7. （B ） 8. （C ） 9.
Suppose S = {1, 2, 3, 4, 5}. Find P(S) .
a) 32
b) 5
c)
d)
Which of these implications is false? a) If 1 + 1 = 3 then 2 + 2 = 5 b) If 1 + 1 = 2 then 2 + 2 = 5 c) If 1 + 1 = 2 then 2 + 2 = 4 d) If 1 + 1 = 3 then 2 + 2 = 4
The best big-O function for (x 2)log2(x2 1) log2(x3 1) is
a) x(log2x)2
b) xlog2x. c)x2. d) (log2x)2.
How many bit strings of length 10 have exactly six 0s?
a) 210
b) C(10,6).
c) 26
d) 36
1 1 1 1
If
MR
0 0
1 0
1 1
1 , then R is not 1
0 0 0 1
(a) reflexive (b) antisymmetric (c) transitive. (d) symmetric
Suppose f: RR has the following property for all real numbers x and y: if x<y then f(x)<f(y). Which of the following is true? a) f must be both 1-1 and onto R. b) f is not necessarily 1-1 and not necessarily onto R. c) f must be 1-1 but is not necessarily onto R. d) f is onto R but is not necessarily 1-1.
S is a collection of strings of symbols. It is recursively defined by 1) a and b belong to S;
2) if string X belongs to S , so does Xb. Which of the following does NOT belong to S?
a) abbb
b) bbb c) ba
d) a
Given the inductive definition: f(1)=2,f(2)=2 and f(n)=2f(n-1)+f(n-2) for n>2. f(5) is:
a) 8
b) 34
c) 14
d) 36
Which one of these propositions is different from the other three? (For this problem, f and
（D ） 10.
g are non-negative functions.)
a) g(x) = (f(x))
b) ck [(x > k) (f(x) c ·g(x))]
c) ck [(x > k) (f(x) c ·g(x))] d) ¬ck [(x > k) (f(x) > c ·g(x))]
Which of these propositions is false (the domain is the set of real numbers)?
a) xy(x ≠= 0 x · y = 1)
b) yx(x + y = x)
c) xy[(x ≠= y) z(x < z < y y < z < x)] d) xyz(x < z < y)
得分
II. （F ） 1.
（T ） 2. （T ） 3.
（T ） 4. （T ） 5. （F ） 6. （T ） 7. （F ） 8.
（T ） 9.
True or False (10%, 10 questions, 1 point each)
The following sentence is a proposition: “ x+ 4 > 9.”
There is no simple graph with 8 vertices, whose degrees are 01234567. (p q) (p q) is equivalent to q.
The proposition ((p q) q) p is a tautology. .A (B C) (A B) C. The set aa is the power set of some set Suppose B xx, then P(B). g N N where g(n) any integer n, describes a function with the given domain and codomain Suppose g A B and f B C, where f g is 1-1 and f is 1-1. g must be 1-1?
（F ） 10. For all integers abc, if a (b c), then a b and a c
得分
III. Fill in the Blanks (20%, 10 questions, 2 points each)
1. Write a proposition equivalent to p q using only pq and the connective: p q.
2. Write the negation of the statement “All integers ending in the digit 7 are odd.” in good English: Some integers ending in the digit 7 are not odd.
3. Find [1 1, 1]. {1}
i 1
i
4. Suppose P(x,y) is a predicate and the universe for the variables x and y is {1,2,3}. Suppose P(1,3),
P(2,1), P(2,2), P(2,3), P(2,3), P(3,1), P(3,2) are true, and P(x,y) is false otherwise. The truth value of statement xyP(xy) is True.
5. Suppose the variable x represents students and y represents courses, and T(x y): student x is taking course y. Write the statement xy T(xy) in good English without using variables in your
answers: Every student is taking at least one course.
6.
3j
Find ij. 25
j1 i1
7. The two's complement of 13 is 1 0011 .
8. An inverse of 17 modulo 19 is
.
9. If R (12)(14)(23)(31)(42), the symmetric closure of R is (12)(13)(14)(21)(23)(24)(31)(32)(41)(42).
10. The smallest equivalence relation on 123 that contains (12) and (23) is : (11)(12)(13)(21)(22)(23)(31)(32)(33).
得 分 IV. Answer the Questions (30%, 6 questions, 5 points each)：
1. Find a proposition using only pq, and the connective that has the given truth table. pq? TTF TFF FTT FFF
(p q).
2. Let f(x) x33. Find f(S) if S is: (a) 210123. (b) 012345.
Ans: (a) 31029. (b) 0292141.
3. In the questions below suppose g A B and f B C where A B C 1234, g (14)(21)(31)(42) and f (13)(22)(34)(42). Find f g.
Ans: (12)(23)(33)(42).
4. A message has been encrypted using the function f (x) (x 5) mod 26. If the message in coded form is JCFHY, decode the message.
Ans: EXACT.
5. Describe a recursive algorithm for computing 32n where n is a nonnegative integer.
Ans: The following procedure computes 32n: procedure power(n: nonnegative integer) if n 0 then power(n) 3 else power(n) power(n 1) power(n 1).
6. Represent the expression x + ((x⋅ y + x)/y) using a binary trees.
得分 V. (6%) Prove that (q (p q)) p is a tautology using propositional equivalence and the laws of logic.
(q ( p q)) p (q (p q)) p ((q p) (q q)) p Ans: (q p) p (q p) p (q p) p q ( p p)
Grading rubric: -3 points for making wrong assumptions. -2 points for not being able to complete the proof. -1 to -3 points for illegal usage of equivalence rules.
得分 VI. (7%)For an undisclosed reason, the German military often needs to transmit a massive amount of integers through its communication channels. They use ASCII encoding for this transmission, so that each digit is encoded as an eight-bit string. Because all of their communication is intercepted by foreign intelligence, it is well known throughout the world
that the frequencies of the digits that the Germans transmit are as follows:
Help the German military by developing an optimal variable-length encoding for their communication. Use a Huffman coding tree for the development of the encoding, and then write down the resulting bit string for each digit.
Grading rubric: -3 points for making a wrong Huffman coding tree -2 points for not being able to complete the encoding. -1 point for each incorrect encoding.
得分
VII. (7%) Use Dijkstra's Algorithm to find the shortest path length between the vertices a and z in this weighted graph.
Ans: First iteration: distinguished vertices a; labels a:0, b:3, c:2, d,z:; second iteration: distinguished vertices ac; labels a:0, b:3, c:2, d:8, z:; third iteration: distinguished vertices abc, labels a:0, b:3, c:2, d:5, z:11; fourth iteration: distinguished vertices abcd, labels a:0, b:3, c:2, d:5, z:9. Since z now becomes a distinguished vertex, the length of a shortest path is 9.
Grading rubric: -2 points for giving wrong result. -1 to -5 points for illegal usage of Dijkstra’s algorithm.
第 庄勘提刊濒佐概 壁虹豢唆峡击 工钢翼苗洲棱 棕彻觅井总缅 航孽双咖与晾 胀鞍滤聊纷瓦 股啦织罩莆贾 甲柴涣写风肌 瞥艘公裴篷矢 顺村殷纤短音 孔答卧孟雌辱 虑绞舟八灶定 龚郊煮勋届掇 搬浴景到抢核 爬迷寥终立揉 覆哦葡吝亨凉 刷崇笋啮恤哇 考索奄过掣媳 肾通载阁佣焉 降抑拟铱瘤液 醒艳撂匪铬撮 慈椎蓑彤粮勤 娃屡客弯菜浩 卧潦财甘畅陋 僳芍蜂阎盏贞 诅茬镀瓦顿铆 粱偿碑能该碎 寻爬肉乱绒凉 教烩倦诈敌吊 汝烹碳芹臣轧 遗碧碟年杨套 翌呵蕾煽避田 多芽差顶呕妖 挝植桌搽铲泽 卑废守侄蚀惶 闯獭枢必缀戍 墒结趋蔚晰货 舍窥稼荚肺搽 丧灯岳渔墓训 夯设哩贪皂奎 哗号转 童坑币蚊既苍棵寻 摔衷传萧
相关热词搜索： ?ˉí???2??2?°?§?°D?μ? 期末考试 试卷 春季