考研课件：机试指南（非线性数据结构）
王道考研-机试指南王道考研-机试指南第章线性数据结构叉树叉排序树线性数据结构优先队列散列表叉树叉排序树线性数据结构优先队列散列表叉树ABCDEEmpty SetRootLeft Subtree Right Subtree叉树D数据域左右叉树ABCDEEmpty SetRootLeft Subtree Right Subtree叉树ABC先序遍历层次遍历DE中序遍历后序遍历叉树ABC先序遍历层次遍历DE中序遍历后序遍历ABC先序遍历DEA B D E C1.Root2.Left Subtree3.Right Subtree叉树ABC先序遍历层次遍历DE中序遍历后序遍历叉树ABC先序遍历层次遍历DE中序遍历后序遍历ABC2.RootDED B E A C1.Left Subtree3.Right Subtree中序遍历叉树ABC先序遍历层次遍历DE中序遍历后序遍历叉树ABC先序遍历层次遍历DE中序遍历后序遍历后序遍历ABC2.Right SubtreeDED E B C A1.Left Subtree3.Root叉树ABC先序遍历层次遍历DE中序遍历后序遍历叉树ABC先序遍历层次遍历DE中序遍历后序遍历层次遍历ABCACEBDDE叉树ABC先序遍历层次遍历DE中序遍历后序遍历例题10.2 叉树遍历题题描述：描述：叉树的前序、中序、后序遍历的定义。前序遍历：对任意棵树，先访问根，然后遍历其左树，最后遍历其右树；中序遍历：对任意棵树，先遍历其左 树，然后访问根，最后遍历其右树；后序遍历：对任意棵树，先遍历其左树，然后遍历其右树，最后访问根。给定棵叉树的前序遍历和中序遍历，求其后序遍历 输输：两个字符串，其度n均于等于26。第为前序遍历，第为中序遍历。叉树中的结点名称以写字A,B,C,表示，最多26个结点。输输出：出：输样例可能有多组，对于每组测试样例，输出，为后序遍历的字符串。样样例例输输：ABC BAC FDXEAG XDEFAG样样例例输输出：出：BCA XEDGAF例题10.2 叉树遍历先序遍历 中序遍历 后序遍历 中序遍历 层次遍历 中序遍历先序遍历后序遍历满叉树例题10.2 叉树遍历先序遍历 中序遍历 后序遍历 中序遍历 层次遍历 中序遍历先序遍历后序遍历满叉树例题10.2 叉树遍历先序遍历中序遍历RootLeft SubtreeRight SubtreeRootLeft SubtreeRight Subtree叉树叉排序树线性数据结构优先队列散列表叉树叉排序树线性数据结构优先队列散列表叉排序树Left Subtree RootRoot 节点109325优先队列1093查询出队52队优先队列1093查询出队52队O(1)优先队列1093查询出队526队优先队列1096查询h出队523队O(logn)优先队列1096查询出队523队优先队列1096查询出队523队优先队列1096查询队3出队52优先队列1036查询队9出队52优先队列1036查询队9出队52优先队列1056查询队9hO(logn)出队32priority_queue队出队 判空访问队顺序问题优先队列哈夫曼树顺序问题优先队列哈夫曼树例题10.5 复数集合题题描述：描述：有个复数集合(x+iy)，作在该集合上的操作有两种：1.Pop，表示读出集合中复数模值最的那个复数。若集合为空，则输出empty；若 集合不为空，则输出最的那个复数并从集合中删除那个复数，再输出集合的SIZE。2.Insert a+ib指令（a,b表示实部和虚部），将a+ib加集合，输出集合的SIZE；最初要读个int n，表示接下来n中的每都是条命令。输输：输有多组数据。每组输个n（1 n 1000），然后再输n条指令。输输出：出：根据指令输出结果。模相等的，输出b较的复数。a和b都是负数。样样例例输输：3PopInsert 1+i2 Pop样样例例输输出：出：4顺序问题优先队列哈夫曼树顺序问题优先队列哈夫曼树哈夫曼树多个带权值叶结点构造的 带权路径度和最叉树例题10.6 哈夫曼树题题描述：描述：哈夫曼树，第输个数n，表示叶结点的个数。需要这些叶结点成哈夫曼 树，根据哈夫曼树的概念，这些结点有权值，即weight，题需要输出所有结点的值与权 值的乘积之和。输输：输有多组数据。每组第输个数n，接着输n个叶结点（叶结点的权值不超 过100，2 n 1000）。输输出：出：输出权值。样样例例输输：51 2 2 5 9样样例例输输出：出：37例题10.6 哈夫曼树531221293例题10.6 哈夫曼树52325129例题10.6 哈夫曼树5532551012910例题10.6 哈夫曼树325510919129例题10.6 哈夫曼树12392551019例题10.6 哈夫曼树12392551019 weight*height1*4+2*4+2*3+5*2+9*1=373+5+10+19=37叉树叉排序树线性数据结构优先队列散列表叉树叉排序树线性数据结构优先队列散列表关键字 key存储值 value散列表Mapping映射mapred black treehash table unoreder_map查询 O(logn)插 O(logn)删除 O(logn)内部有序查询 O(1)插 O(1)删除 O(1)内部序map查询插 删除 遍历例题10.7 查找学信息题题描述：描述：输N个学的信息，然后进查询。输输：输的第为N，即学的个数（N 1000）。接下来的N包括N个学的信息，信息格式如下：01 李江 男 212.刘唐 男 233.张军 男 194.王娜 19然后输个M(M 10000)，接下来会有M，代表M次查询，每输个学号，格式如下：02030104输输出：出：输出M，每包括个对应于查询的学的信息。如果没有对应的学信息，则输 出“No Answer!”例题10.7 查找学信息样样例例输输：41.李江 男 212.刘唐 男 233.张军 男 194.王娜 1950203010403样样例例输输出：出：2.刘唐 男 233.张军 男 1901 李江 男 2104 王娜 1903 张军 男 19例题10.7 查找学信息01 李江 男 21keyvalue叉树叉排序树线性数据结构优先队列散列表叉树叉排序树线性数据结构优先队列散列表王道考研-机试指南第章线性数据结构王道考研-机试指南
