数据结构课件第6章 二叉树和树.ppt
《数据结构课件第6章 二叉树和树.ppt》由会员分享,可在线阅读,更多相关《数据结构课件第6章 二叉树和树.ppt(185页珍藏版)》请在文库网上搜索。
1、是否构成群 。4、 设G是n阶完全图,则G的边数m= 。5、 如果有一台计算机,它有一条加法指令,可计算四数的和。现有28个数需要计算和,它至少要执行 次这个加法指令。十、 选择 20% (每小题 2分)1、 在有理数集Q上定义的二元运算*,有,则Q中满足( )。A、 所有元素都有逆元; B、只有唯一逆元; C、时有逆元; D、所有元素都无逆元。2、 设S=0,1,*为普通乘法,则是( )。A、 半群,但不是独异点; B、只是独异点,但不是群;C、群; D、环,但不是群。3、图 给出一个格L,则L是( )。A、分配格; B、有补格; C、布尔格; D、 A,B,C都不对。3、 有向图D= ,则
2、长度为2的通路有( )条。A、0; B、1; C、2; D、3 。4、 在Peterson图中,至少填加( )条边才能构成Euler图。A、1; B、2; C、4; D、5 。十一、 判断 10% (每小题 2分)1、 在代数系统中如果元素的左逆元存在,则它一定唯一且。( )2、 设是群的子群,则中幺元e是中幺元。( )3、 设, +,为普通加法和乘法,则代数系统是域。( )4、 设G=是平面图,|V|=v, |E|=e,r为其面数,则v-e + r=2。( )5、 如果一个有向图D是欧拉图,则D是强连通图。( )四、证明 46%1、 设,是半群,e是左幺元且,使得,则是群。(10分)2、 循
3、环群的任何非平凡子群也是循环群。(10分)3、 设aH和bH是子群H在群G中的两个左陪集,证明:要末,要末 。(8分)4、 设,是一个含幺环,|A|3,且对任意,都有,则不可能是整环(这时称是布尔环)。(8分)5、 若图G不连通,则G的补图是连通的。(10分)五、布尔表达式 8%设是布尔代数上的一个布尔表达式,试写出其的析取范式和合取范式。六、图的应用 16%1、 构造一个结点v与边数e奇偶性相反的欧拉图。(6分)2、 假设英文字母,a,e,h,n,p,r,w,y出现的频率分别为12%,8%,15%,7%,6%,10%,5%,10%,求传输它们的最佳前缀码,并给出happy new year的
4、编码信息。(10分)答案十一、 填空 10%(每小题2分)+30120012112022011、;2、,;3、 是;4、;5、9十二、 选择 10%(每小题 2分)题目12345答案CBDBD十三、 判断 10%(每小题2分)题目12345答案NYYNY十四、 证明 46%1、(10分)证明:(1)(2) e 是之幺元。事实上:由于e是左幺元,现证e是右幺元。(3)由(2),(3)知:为群。2、(10分)证明:设是循环群,G=(a),设是的子群。且,则存在最小正整数m,使得:,对任意,必有,故: 即:所以但m是使的最小正整数,且,所以r=0即:这说明S中任意元素是的乘幂。 所以是以为生成元的循
5、环群。3、(8分)证明:对集合,只有下列两种情况:(1); (2)对于,则至少存在,使得,即有,这时任意,有,故有同理可证:所以 4、(8分)证明:反证法:如果,是整环,且有三个以上元素,则存在即有:这与整环中无零因子条件矛盾。因此不可能是整环。5、(10分)证明:因为G=不连通,设其连通分支是,则有两种情况:(1) u , v,分别属于两个不同结点子集Vi,Vj,由于G(Vi) , G(Vj)是两连通分支,故(u , v)在不G中,故u , v 在中连通。(2) u ,v ,属于同一个结点子集Vi,可在另一结点子集Vj中任取一点w,故(u , w),(w , v )均在中,故邻接边( u ,
6、w ) ( w , v ) 组成的路连接结点u和v,即u , v在中也是连通的。五、布尔表达式 8%函数表为:00000011010001111000101111011111析取范式:合取范式:六、 树的应用 16%1、(6分)解:2、(10分)解:根据权数构造最优二叉树:传输它们的最佳前缀码如上图所示,happy new year的编码信息为:10 011 0101 0101 001 110 111 0100 001 111 011 000 附:最优二叉树求解过程如下:试卷十五试题与答案十二、 填空 20% (每空 2分)1、 如果有限集合A有n个元素,则|2A|= 。2、 某集合有101个
7、元素,则有 个子集的元素为奇数。3、 设S=a1,a2,,a8,Bi是S的子集,由B17表达的子集为 , 子集a2,a6,a7规定为 。4、 由A1,A2,,An,生成的最小集的形式为 ,它们的并为 集,它们的交为 集。5、 某人有三个儿子,组成集合A=S1,S2,S3,在A上的兄弟关系具有 性质。6、每一个良序集必为全序集,而 全序集必为良序集。7、若是函数,则当f是的 ,是f的逆函数。十三、 选择 15% (每小题 3分)1、 集合的幂集为( )。A、;B、;C、;D、2、 下列结果正确的是( )。A、;B、;C、;D、;E、;F、AA=A 。3、 集合的最小集范式为( )(由A、B、C生
8、成)。A、 ; B、;C、 ; D、。4、 在( ) 下有。A、;B、;C、;D、5、 下列二元关系中是函数的有( )。A、;B、;C、。三、 15% 用Warshall算法,对集合A=1,2,3,4,5微软等公司数据结构微软等公司数据结构+算法面试算法面试 100 题题(第第 1-100 题题)首次完整亮相首次完整亮相 作者:July、2010 年 12 月 6 日。 1. 更新: 现今, 这 100 题的答案已经全部整理出来了, 微软面试 100 题 2010 年版全部答案集锦: 2. 关于此 100 道面试题的所有一切详情,包括答案,资源下载,帖子维护, 答案更新,都请参考此文:横空出世
9、,席卷横空出世,席卷 Csdn 评微软等数据结构评微软等数据结构+ 算法面试算法面试 100 题题。 3. 以下 100 题中有部分题目整理自何海涛的博客 ( - 微软等 100 题系列 V0.1 版终于结束了。 从 2010 年 10 月 11 日当天最初发表前 40 题以来, 直至此刻, 整理这 100 题, 已有近 2 个月。 2 个月,因为要整理这 100 题,很多很多其它的事都被我强迫性的搁置一旁, 如今,要好好专心去做因这 100 题而被耽误的、其它的事了。 这微软等数据结构+算法面试 100 题系列系列(是的,系列),到底现在、或此刻、或未来,对初 学者有多大的意义, 在此,我就
10、不给予评说了。 由他们自己来认定。所谓,公道自在人心,我相信这句话。 任何人,对以下任何资料、题目、或答案,有任何问题,欢迎联系我。 作者邮箱: zhoulei0907 786165179 作者声明: 转载或引用以下任何资料、或题目,请注明作者本人 July 及出处。 向您的厚道致敬,谢谢。 好了,请享受这完完整整的 100 题吧,这可是首次完整亮相哦。:D。 - 1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 8 12 16 转换成双向链
11、表 4=6=8=10=12=14=16。 首先我们定义的二元查找树 节点的数据结构如下: struct BSTreeNode int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node ; 2.设计包含 min 函数的栈(栈) 定义栈的数据结构,要求添加一个 min 函数,能够得到栈的最小元素。 要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。 3.求子数组的最大和(数组) 题目: 输入一个整形数组,数
12、组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为 O(n)。 例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为 3, 10, -4, 7, 2, 因此输出为该子数组的和 18。 4.在二元树中找出和为某一值的所有路径(树) 题目:输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如 输入整数 22 和如下二元树 10 / / 5 12 / 4 7 则打印出两条路径:10, 12 和 10,
13、5, 7。 二元树节点的数据结构定义为: struct BinaryTreeNode / a node in the binary tree int m_nValue; / value of node BinaryTreeNode *m_pLeft; / left child of node BinaryTreeNode *m_pRight; / right child of node ; 5.查找最小的 k 个元素(数组) 题目:输入 n 个整数,输出其中最小的 k 个。 例如输入 1,2,3,4,5,6,7 和 8 这 8 个数字,则最小的 4 个数字为 1,2,3 和 4。 第 6 题(
14、数组) 腾讯面试题: 给你 10 分钟时间,根据上排给出十个数,在其下排填出对应的十个数 要求下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下: 【0,1,2,3,4,5,6,7,8,9】 举一个例子, 数值: 0,1,2,3,4,5,6,7,8,9 分配: 6,2,1,0,0,0,1,0,0,0 0 在下排出现了 6 次,1 在下排出现了 2 次, 2 在下排出现了 1 次,3 在下排出现了 0 次. 以此类推. 第 7 题(链表) 微软亚院之编程判断俩个链表是否相交 给出俩个单向链表的头指针,比如 h1,h2,判断这俩个链表是否相交。 为了简化问题,我们假设俩个链表均不带
15、环。 问题扩展: 1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列? 第 8 题(算法) 此贴选一些 比较怪的题,由于其中题目本身与算法关系不大,仅考考思维。特此并作一 题。 1.有两个房间,一间房里有三盏灯,另一间房有控制着三盏灯的三个开关, 这两个房间是 分割开的,从一间里不能看到另一间的情况。 现在要求受训者分别进这两房间一次,然后判断出这三盏灯分别是由哪个开关控制的。 有什么办法呢? 2.你让一些人为你工作了七天,你要用一根金条作为报酬。金条被分成七小块,每天给出一 块。 如果你只能将金条切割两次,你怎样分给这些工人? 3. 用一种算法来颠倒一个链接表的顺序。现在在
16、不用递归式的情况下做一遍。 用一种算法在一个循环的链接表里插入一个节点,但不得穿越链接表。 用一种算法整理一个数组。你为什么选择这种方法? 用一种算法使通用字符串相匹配。 颠倒一个字符串。优化速度。优化空间。 颠倒一个句子中的词的顺序,比如将“我叫克丽丝”转换为“克丽丝叫我”, 实现速度最快,移动最少。 找到一个子字符串。优化速度。优化空间。 比较两个字符串,用 O(n)时间和恒量空间。 假设你有一个用 1001 个整数组成的数组,这些整数是任意排列的,但是你知道所有 的整数都在 1 到 1000(包括 1000)之间。此外,除一个数字出现两次外,其他所有数字只出 现一次。假设你只能对这个数组
17、做一次处理,用一种算法找出重复的那个数字。如果你在运 算中使用了辅助的存储方式,那么你能找到不用这种方式的算法吗? 不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。 第 9 题(树) 判断整数序列是不是二元查找树的后序遍历结果 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回 true,否则返回 false。 例如输入 5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果: 8 / / 6 10 / / / / 5 7 9 11 因此返回 true。 如果输入 7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回 fals
18、e。 第 10 题(字符串) 翻转句子中单词的顺序。 题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。 句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。 例如输入“I am a student.”,则输出“student. a am I”。 第 11 题(树) 求二叉树中节点的最大距离. 如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的, 我们姑且定义距离为两节点之间边的个数。 写一个程序, 求一棵二叉树中相距最远的两个节点之间的距离。 第 12 题(语法) 题目:求 1+2+n, 要求不能使用乘除法、 for、 while、 if、 else、
19、 switch、 case 等关键字以及条件判断语句 (A?B:C) 。 第 13 题(链表): 题目:输入一个单向链表,输出该链表中倒数第 k 个结点。链表的倒数第 0 个结点为链表 的尾指针。 链表结点定义如下: struct ListNode int m_nKey; ListNode* m_pNext; ; 第 14 题(数组): 题目:输入一个已经按升序排序过的数组和一个数字, 在数组中查找两个数,使得它们的和正好是输入的那个数字。 要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。 例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=
20、15,因此输出 4 和 11。 第 15 题(树): 题目:输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点。 用递归和循环两种方法完成树的镜像转换。 例如输入: 8 / / 6 10 / / 5 7 9 11 输出: 8 / / 10 6 / / 11 9 7 5 定义二元查找树的结点为: struct BSTreeNode / a node in the binary search tree (BST) int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构课件 第6章 二叉树和树 数据结构 课件 二叉