笔试-数据结构与算法2.ppt

2.3多维数组，稀疏矩阵和广义表，2004年7月16日，存储测试点1多维数组顺序，一个n个元素行，a11，2004年7月16日，存储测试点2稀疏矩阵，存储子三角矩阵行优先数组，存储3个组，交叉列表，3，2004年7月16日考试问题，1，对以下广义表的说明a .广义表由0个以上的单个元素或子表组成的有限序列b .广义表中至少有一个元素不能是子表c .广义表自身的子表d .广义表。 广义表不能是空表A2。以下是稀疏矩阵的三元组表示法存储表示法以及基于此表示法的相关描述I .稀疏矩阵有5行：这个稀疏矩阵有四列。这个稀疏矩阵有六个非零元素。在此叙述中，_ _ _ _ _ _ _ _ _是正确的。a)仅限IB)I和IIC)仅限IID)所有C、2.4树结构(重点)，2004年7月16日，测试点1树的定义，树是重要的树结构，叶节点，此树的深度为3，度3，度2，树的深度为3，左分支树，右分支树，根节点，2004年7月16日，二进制树和树之间的区别：二进制树不是特例，树和二进制树之间的主要区别在于，即使节点是一个子树，也可以区分左子树和右子树。2004年7月16日，完整的二叉树，完整的二叉树，思想：提供完整的二叉树n个节点，有多少个叶节点？深度是多少？整个二进制树：每个层次中的节点数最大值；整个树：除最后一个层次外，每个其馀层次中的节点数最大值、最后一个或全部或右侧连续缺少的节点数；最后一个非叶节点n/2；二进制树属性；特性1:二进制树的I层次中的最大值为2i-1 (i1)节点；以及特性2:深度为h的二进制树最多包含2h-1个节点，深度为h的整个二进制树总共包含2h-1个节点。性质3:如果其中一个二进位树状结构包含n0个分叶节点，N2为2的节点，则n0=N2 1；属性4:具有深度大于log2n 1的n个节点的二叉树。其中log2n表示log2n的整数部分。2004年7月16日，测试点3树和二叉树转换，兄弟，破碎的父子顺时针方向45，将二叉树转换成树，破碎的右孩子，甚至父亲，2004年7月16日，森林转换成二叉树，a，二叉树旅行主要由三种方法完成：NLR(前序方法):根访问，左子树前游，右子树前游后序(LRN):左子树旅行，右子树后游，根对称(中间序)方法(LNR):左子树：2004年7月16日，LRN，向后遍历序列：DBCA，向后遍历3360，2004年7月16日，树和树系之间的移动分为深度优先级和宽度优先级。 树深度是第一个根顺序(二进制树的前导顺序)和下一个根顺序(二进制树的中间顺序)，第一个和下一个顺序编号对应于二进制树的优先级和中间顺序树的宽度。分层访问，2004年7月16日，测试点5二进制树的存储和线索二进制树，二进制树的link-rlink式存储表示，右侧子根，左侧子根，2004年7月16日，线索二进制树，n节点，n 1个空指针(n节点，I，2i，2i 1，2004年7月16日，测试点6半路径树(哈夫曼树)，最佳二叉树最小加权路径长度树，树加权路径长度：从每个叶节点到根的路径长度乘以节点权重，WPL=，2004年7月16日， 54，10，12，24，16，21，30，37，步骤4，54，91，WPL，2004年7月16日，考试问题，1，二进制树巡回赛的以下说明中哪个是正确的？ A)如果节点是二进制树对称顺序中的最后一个节点，则该二进制树中第一个顺序中的最后一个节点B)如果节点是二进制树中第一个顺序中的最后一个节点c)如果叶是二进制