5-6 家谱处理 (30分)

发表于 分类,标签:
 人类学研究对于家族很感兴趣,于是研究人员搜集了一些家族的家谱进行研究。实验中,使用计算机处理家谱。为了实现这个目的,研究人员将家谱转换为文本文件。下面为家谱文本文件的实例:John  Robert    Frank    Andrew  Nancy    David家谱文本文件中,每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代,而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例,John这个家族最早的祖先,他有两个子女Robert和Nancy,Robert有两个子女Frank和Andrew,Nancy只有一个子女David。...

5-8 树的同构 (25分)

发表于 分类,标签:
 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。  图1图2现给定两棵树,请你判断它们是否是同构的。 输入格式:输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数NN (\le10≤10),即该树的结点数(此时假设结点从0到N-1N−1编号);随后NN行,第ii行对应编号第ii个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。输出格式:如果两棵树是同构的,输出“Yes”,否则输出“No”。输入样例1(对应...

#1014 : Trie树

发表于 分类,标签:
 http://hihocoder.com/problemset/problem/1014时间限制:10000ms单点时限:1000ms内存限制:256MB描述小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。这一天,他们遇到了一本词典,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能对于每一个我给出的字符串,都在这个词典里面找到以这个字符串开头的所有单词呢?”身经百战的小Ho答道:“怎么会不能呢!你每给我一个字符串,我就依次遍历词典里的所有单词,检查你给我的字符串是不是这个单词的前缀不就是了?”小Hi笑道:“你啊,还是太年轻了!~假设这本词典里有10万个单词,我询问你一万次,你得要算到哪年哪月去?”小Ho低头算了一算,看着那一堆堆的0,顿时感觉自己这辈子都要花在上面了...小Hi看着小Ho的囧样...

L3-002. 堆栈

wang 发表于 分类,标签: 天梯赛
 大家都知道“堆栈”是一种“先进后出”的线性结构,基本操作有“入栈”(将新元素插入栈顶)和“出栈”(将栈顶元素的值返回并从堆栈中将其删除)。现请你实现一种特殊的堆栈,它多了一种操作叫“查中值”,即返回堆栈中所有元素的中值。对于N个元素,若N是偶数,则中值定义为第N/2个最小元;若N是奇数,则中值定义为第(N+1)/2个最小元。输入格式:输入第一行给出正整数N(<=105)。随后N行,每行给出一个操作指令,为下列3种指令之一:Push keyPopPeekMedian其中Push表示入栈,key是不超过105的正整数;Pop表示出栈;PeekMedian表示查中值。输出格式:对每个入栈指令,将key入栈,并不输出任何信息。对每个出栈或查中值的指令,在一行中打印相应的返回结果。若指令非法,就打印“Invalid”。输入样例:17PopPeekMedian...

L3-010. 是否完全二叉搜索树

wang 发表于 分类,标签: 天梯赛二叉树
 将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。输入格式:输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。输出格式:将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出“YES”,如果该树是完全二叉树;否则输出“NO”。输入样例1:938 45 42 24 58 30 67 12 51输出样例1:38 45 24 58 42 30 12 67 51YES输入样例2:838&nbs...

L2-011. 玩转二叉树(天梯赛)

发表于 分类,标签: 天梯赛
 给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式:输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。输出格式:在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。输入样例:71 2 3 4 5 6 74 1 3 2 6 5 7输出样例:4 6 1 7 5 3 2思路:根据二叉树的前序遍历和中序遍历恢复二叉树后遍历,不过恢复时将左右节点交换一下就行...

PAT (Advanced Level)1115. Counting Nodes in a BST (30)

发表于 分类,标签: pat二叉树
 ABinarySearchTree(BST)isrecursivelydefinedasabinarytreewhichhasthefollowingproperties:Theleftsubtreeofanodecontainsonlynodeswithkeyslessthanorequaltothenode'skey.Therightsubtreeofanodecontainsonlynodeswithkeysgreaterthanthenode'skey.Boththeleftandrightsubtreesmustalsobebinarysearchtrees.Insertasequenceofnumbersintoani...

PAT (Advanced Level)1119. Pre- and Post-order Traversals (30)

发表于 分类,标签: pat二叉树
 Supposethatallthekeysinabinarytreearedistinctpositiveintegers.Auniquebinarytreecanbedeterminedbyagivenpairofpostorderandinordertraversalsequences,orpreorderandinordertraversalsequences.However,ifonlythepostorderandpreordertraversalsequencesaregiven,thecorrespondingtreemaynolongerbeunique.Nowgivenapairofpostorderandpreordertraversa...

1102. Invert a Binary Tree (25)(pat甲级)

发表于 分类,标签: pat二叉树
 ThefollowingisfromMaxHowell@twitter:Google:90%ofourengineersusethesoftwareyouwrote(Homebrew),butyoucan'tinvertabinarytreeonawhiteboardsofuckoff.Nowit'syourturntoprovethatYOUCANinvertabinarytree!InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinegivesapositiveintegerN(<=10)whichisthetotalnumbe...

1110. Complete Binary Tree (25)(pat甲级)

发表于 分类,标签: pat二叉树
 Givenatree,youaresupposedtotellifitisacompletebinarytree.InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinegivesapositiveintegerN(<=20)whichisthetotalnumberofnodesinthetree--andhencethenodesarenumberedfrom0toN-1.ThenNlinesfollow,eachcorrespondstoanode,andgivestheindicesoftheleftandrightchild...