《笔试-数据结构与算法2》由会员分享，可在线阅读，更多相关《笔试-数据结构与算法2（65页珍藏版）》请在金锄头文库上搜索。
1、2.3多维数组、稀疏矩阵和广义表,2004年7月16日,考点1 多维数组顺序存储,一行n个元素,a11,2004年7月16日,考点2 稀疏矩阵存储,下三角矩阵 行优先数组存储,还可用三元组存储、十字链表,3,2004年7月16日,考点3 广义表,广义线性表，零个或多个单元素或子表组成 表中含表,2004年7月16日,考题,1、以下关于广义表的叙述中，哪一条是正确的？ A广义表是0个或多个单元素或子表组成的有限序列 B广义表至少有一个元素是子表 C广义表不可以是自身的子表 D广义表不能为空表 A 2、如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述 I.该稀疏矩阵有5行 II.该
2、稀疏矩阵有4列 III.该稀疏矩阵有6个非0元素 这些叙述中_是正确的。 A）仅I B）I和II C）仅III D）全部 C,2.4树形结构（重点）,2004年7月16日,考点1 树的定义,树是一种重要的树型结构,叶子结点,该树的度为3,度为3,度为2,该树的深度为3,2004年7月16日,考点2 二叉树,二叉树是另一种树形结构 空树或由根和左右子树组成，左右子树也是一棵二叉树,左支树,右支树,根结点,2004年7月16日,二叉树和树的区别：二叉树不是树的特殊情况， 树和二叉树之间最主要的区别是，二叉树的结点的子树要区分左子树和右子树， 即使在结点只有一棵子树的情况下也要明确指出该子树是左子树
3、还是右子树。,2004年7月16日,满二叉树,完全二叉树,思考：给出完全二叉树有n个结点，问有多少个叶子结点？,深度是多少呢？,满二叉树：每一层结点数达到最大,完全叉树：除最后一层外，其余每一层结点数达到最大，最后一层结点或满，或右边连续缺少若干结点,最后一个非叶子结点 n/2,二叉树性质,性质1：二叉树的第i层上至多有2 i-1（i 1）个结点，满二叉树的第k层上有2 k-1个结点； 性质2：深度为h的二叉树中至多含有2 h-1个结点，深度为h的满二叉树共有2 h-1个结点； 性质3：若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1； 性质4：具有n个结点的二
4、叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分；,2004年7月16日,考点3 树和二叉树的转换,连兄弟，断父子 顺时针旋转45,二叉树转换为树，断右子女，连父亲,2004年7月16日,森林转换为二叉树,A,B,C,D,E,F,2004年7月16日,考点4 二叉树和树的周游（遍历）,遍历：按一定次序访问所有结点，并且每个结点只被访问一次 二叉树的周游（遍历） 按访问根的次序：二叉树的周游主要有三种方式 前序法(NLR)：访问根，按前序周游左子树，按前序周游右子树 后序法(LRN)：按后序周游左子树，按后序周游右子树，访问根 对称（中序）法(LNR)：按对称序周游左子
5、树，访问根，按对称序周游右子树,2004年7月16日,N L R,先序遍历序列：A B D C,前序遍历:,2004年7月16日,L N R,中序遍历序列：B D A C,中序遍历:,2004年7月16日,L R N,后序遍历序列： D B C A,后序遍历:,2004年7月16日,周游树和森林 对树和森林的周游分为按深度优先和按广度优先两种方式 树深度优先：先根次序（对应二叉树的前序）和后根次序（对应二叉树的中序序）周游 森林的先序和后序号对应二叉树的先序和中序 树广度优先：按层次访问,2004年7月16日,考点5 二叉树的存储和线索二叉树,二叉树的llink-rlink法存储表示,指向右子
6、树根,指向左子树根,2004年7月16日,线索二叉树，n个结点，n+1个空指针（n个结点，2n个指针，n-1个指针指向结点）,中序遍历 DBGEACHFI,2004年7月16日,完全二叉树存储 完全二叉树中除最下面一层外，各层都被结点充满了，每一层结点个数是上一层结点个数的2倍。,i,2i,2i+1,2004年7月16日,考点6 哈夫曼树（huffman)(霍夫曼树）,最优二叉树 树的带权路径长度最小的树,树的带权路径长度：各个叶子结点到根的路径长度与结点权值乘积之和,WPL=,2004年7月16日,Huffman 算法求最优二叉树,10,12,16,21,30,结点权值如下：,10,12,2
7、4,16,21,30,第一步（最小的两棵树构成新树,单结点森林,2004年7月16日,10,12,24,16,21,30,37,第二步,10,12,24,16,21,30,37,第三步,54,10,12,24,16,21,30,37,第四步,54,91,求WPL,2004年7月16日,考题,1、下列关于二叉树周游的叙述中，哪一条是正确的？ A）若一个结点是二叉树的对称序最后一个结点，则它必是该二叉树的前序最后一个结点 B）若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的对称序最后一个结点 C）若一个树叶是某二叉树的对称序最后一个结点，则它必是该二叉树的前序最后一个结点 D）若一个树叶
8、是某二叉树的前序最后一个结点，则它必是该二叉树的对称序最后一个结点 C 2009.04 （右子树为空）,A,B,对称序BA 前序AB,2004年7月16日,2、按层次次序将一棵有n个结点的完全二叉树的所有结点从1到n编号，当in/2时，编号为i的结点的左子女的编号为 A）2i-1 B）2i C）2i+1 D）不确定 B 2009.04,2004年7月16日,1）该二叉树对应的树林包括几棵树？2008。04 A、1 B、2 C、3 D、4 C （根结点右子树转换为树） 2）如果用llink-rlink存储该二叉树，则各结点指针域共包含多少空指针 A、0 B、4 C、8 D、12 C N+1 3）
9、如果将该二叉树存储为对称序线索二叉树，则结点C的左线索指向哪个结点？ A、结点A B、结点B C、结点E D、结点G 对称序：DBGEACF A,2004年7月16日,试题（12）（14）基于如下所示的二叉树。 2007.04 （12）该二叉树对应的树林包括几棵树？ A）1 B) 2 C）3 D）4 B 去掉右子树与父亲连线 （13）按后根次序周游该二叉树对应的树林，所得到的结点序列为 A）DBAFEGC B）ABCDEFG C）DBFGECA D）ACBEGDF A 后根访问第一课树的子树，访问第一棵树的根，后根访问其他树（二叉树的中序 （14）按层次次序周游该二叉对应的树林，所得到的结点序
10、列为 A）DBAFEGC B）ABCDEFG C）DBFGECA D）ACBEGDF D,2004年7月16日,填空,1、一棵二叉树结点的前序序列为A、B、D、E、G、C、F、H、I，对称序序列为D、B、G、E、A、C、H、F、I，则该二叉树结点的后序序列为 【4】 A为根结点，对称序列中D，B，G，E为左子树，B为左子树根,A,B,D,E,G,C,F,H,I,2004年7月16日,一棵二叉树的度为2的结点为9，则该二叉树的叶结点个数为【1】 N0=N2+1 10,2.5查找,在数据结构中找出满足条件的结点的过程,2004年7月16日,考点1 顺序查找,逐个依次查找，对逻辑次序无要求（不必排序
11、），可以是顺序存储也可以是链式存储 优点：简单 缺点：速度慢，检索长度与结点N成正比,2004年7月16日,考点2 二分查找,线性表结点必须按关键码值排序，以顺序存储方式存储的（考概念） 二分查找过程（查找612）,2004年7月16日,例题1：对线性表进行二分法检索，其前提条件是：线性表以 【1】 方式存储，并且按关键码值排好序。,2004年7月16日,考点3 分块查找,线性表分块 每块不必有序 块间有序 查找过程 1、在索引表中确定记录所在块 2、在块中查找记录,索引表,2004年7月16日,考点4 散列表的存储和查找（重点）,散列表（哈希表）：利用散列法构建的线性表，是一种重要的存储方式
12、和检索方式 基本思想： 1、由结点的关键码k通过散列函数f(k)决定结点的存储地址 2、将结点存入该地址，查找的时候，通过该散列函数取得地址，读取结点数据,2004年7月16日,由于采用函数值作为地址，不同关键码函数值可能相同，即K1K2,但f(k1)=f(k2)，这就产生了碰撞（冲突） 碰撞处理：开放地址法（线性探测法）和拉链法 开放地址法：当在d地址发生碰撞时，按如下序列进行探查d+1,d+2,m-1,0,1,d-1,2004年7月16日,例题1：设散列表的地址空间为0到12，散列函数为h（k）=k mod 13, 用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值14, 95,
13、24, 61，27, 82, 69, 则最后一个关键码69的地址为【4】。,求地址：h(14)=1,地址,数据,h(95)=4,h(24)=11,h(61)=9,h(27)=1 产生冲突 地址+1,h(82)=4 产生冲突 地址+1,h(69)=4 产生冲突 地址+1，+1,14,27,95,82,69,61,24,2004年7月16日,负载因子（装填因子）,上题的负载因子 7/13 =,2004年7月16日,考点5 树形结构与查找,二叉排序树（适合内存查找） 特点：结点左子树所有结点关键码都小于该结点关键码，右子树所有结点都大于该结点关键码,中序周游（遍历） 为有序序列,2004年7月16日
14、,极端情况，检索达 n次,2004年7月16日,B树和B+树（适合于外存查找） B树是一种平衡多路查找树,2004年7月16日,至少有M/2-1个关键码,NULL,2004年7月16日,B树的插入结点和删除结点仍然要满足B树特征,2004年7月16日,以下两题基于图3-8所示的5阶B树结构,1、向该B树中插入关键码72后，该B树第2层结点数为（） A、6 B、7 C、8 D、9 C 2、从该B树中删除关键码15后，该B树的第2层结点数为 ( ) A、6 B、7 C、8 D、9 B,2004年7月16日,结点分支多于5个，需要分为两个结点 每个结点至少含2个关键码（分裂）,64 70 72 73
15、 78,45 60 72 82,38 41,47 53,60 70,73 78,86 95,中间关键码至少为5/2-1 2,最多4个,2004年7月16日,删除15结点 只剩一个关键码，不满足要求 从右边移一个元素（合并）,35,10 18,45 60 82,2 5 8,11 15,23 26 30,38 41,47 53,64 70 73 78,86 95,11 15,10 23,2 5 8,11 18,26 30,中间关键码至少为5/2-1 2,最多4个,2004年7月16日,2004年7月16日,B树和B+树的特点。 B树和B+树用于组织文件的动态索引结构。 B树和B+树都是平衡的多分支树。 B树只适用于随机检索，不适用于顺序检索，而B+树适用于顺序检索和随机检索。,2.6排序,直接插入排序 选择排序 交换排序 归并排序,2004年7月16日,考点1 插入排序,直接插入排序 待排序记录插入到已排序记录中,i=1 (12) 20 18 8 9 18 23 16,排序结果： （ 8 9 12 16 18 18 20 23 ）,i=2 (12 20) 18 8 9 18 23 16,i=3 (12 18 20) 8 9 18 23
