笔试-数据结构与算法2

《笔试-数据结构与算法2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.3多维数组、稀疏矩阵和广义表考点1多维数组顺序存储aij一行n个元素a11考点2稀疏矩阵存储下三角矩阵行优先数组存储还可用三元组存储、十字链表3000700-100-1-200000000000203123451245考点3广义表广义线性表，零个或多个单元素或子表组成表中含表考题1、以下关于广义表的叙述中，哪一条是正确的？A．广义表是0个或多个单元素或子表组成的有限序列B．广义表至少有一个元素是子表C．广义表不可以是自身的子表D．广义表不能为空表A2、如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述I

2、.该稀疏矩阵有5行II.该稀疏矩阵有4列III.该稀疏矩阵有6个非0元素这些叙述中______是正确的。A）仅IB）I和IIC）仅IIID）全部C2.4树形结构（重点）考点1树的定义树是一种重要的树型结构ABCDEFGHIJKLM根结点父结点结点D的子结点叶子结点该树的度为3第0层第1层第2层第3层结点B的两棵子树度为3度为2该树的深度为3考点2二叉树二叉树是另一种树形结构空树或由根和左右子树组成，左右子树也是一棵二叉树abcdefg左支树右支树根结点二叉树和树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是

3、，二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。123114589121367101415123114589126710满二叉树完全二叉树思考：给出完全二叉树有n个结点，问有多少个叶子结点？深度是多少呢？满二叉树：每一层结点数达到最大完全叉树：除最后一层外，其余每一层结点数达到最大，最后一层结点或满，或右边连续缺少若干结点最后一个非叶子结点[n/2]二叉树性质423167891011121314155性质1：二叉树的第i层上至多有2i-1（i1）个结点，满二

4、叉树的第k层上有2k-1个结点；性质2：深度为h的二叉树中至多含有2h-1个结点，深度为h的满二叉树共有2h-1个结点；性质3：若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1；性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分；考点3树和二叉树的转换连兄弟，断父子顺时针旋转45二叉树转换为树，断右子女，连父亲森林转换为二叉树ABCDEFABCDEFABCDEF考点4二叉树和树的周游（遍历）遍历：按一定次序访问所有结点，并且每个结点只

5、被访问一次二叉树的周游（遍历）按访问根的次序：二叉树的周游主要有三种方式①前序法(NLR)：访问根，按前序周游左子树，按前序周游右子树②后序法(LRN)：按后序周游左子树，按后序周游右子树，访问根③对称（中序）法(LNR)：按对称序周游左子树，访问根，按对称序周游右子树ADBCNLRANLRNLR>B>>D>>CNLR先序遍历序列：ABDC前序遍历:ADBCLNRBLNRLNR>A>>D>>CLNR中序遍历序列：BDAC中序遍历:ADBCLRNLRNLRN>A>>D>>CLRN后序遍历序列：DBCA后序遍历:B周游树和森

6、林对树和森林的周游分为按深度优先和按广度优先两种方式树深度优先：先根次序（对应二叉树的前序）和后根次序（对应二叉树的中序序）周游森林的先序和后序号对应二叉树的先序和中序树广度优先：按层次访问先根后根广度考点5二叉树的存储和线索二叉树二叉树的llink-rlink法存储表示指向右子树根指向左子树根线索二叉树，n个结点，n+1个空指针（n个结点，2n个指针，n-1个指针指向结点）中序遍历DBGEACHFI完全二叉树存储完全二叉树中除最下面一层外，各层都被结点充满了，每一层结点个数是上一层结点个数的2倍。i2i2i+1考点6哈

7、夫曼树（huffman)(霍夫曼树）最优二叉树树的带权路径长度最小的树树的带权路径长度：各个叶子结点到根的路径长度与结点权值乘积之和WPL=Huffman算法求最优二叉树1012162130结点权值如下：101224162130第一步（最小的两棵树构成新树10122416213037第二步单结点森林10122416213037第二步10122416213037第三步5410122416213037第四步5491求WPL考题1、下列关于二叉树周游的叙述中，哪一条是正确的？A）若一个结点是二叉树的对称序最后一个结点，则它必是

8、该二叉树的前序最后一个结点B）若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的对称序最后一个结点C）若一个树叶是某二叉树的对称序最后一个结点，则它必是该二叉树的前序最后一个结点D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的对称序最后一个结点C2009.04（右子树为空）AB对称序BA前序AB