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

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广义表不能为空表A2、如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述I.该稀疏矩阵有5行II.该稀疏矩阵有4列III.该稀疏矩阵有6个非0元素这些叙述中_是正确的。A）仅IB）I和IIC）仅IIID）全部C,2.4树形结构（重点）,2004年7月16日,考点1树的定义,树是一种重要的树型结构,叶子结点,该树的度为3,度为3,度为2,该树的深度为3,2004年7月16日,考点2二叉树,二叉树是另一种树形结构空树或由根和左右子树组成，左右子树也是一棵二叉树,左支树,右支树,根结点,2004年7月16日,二叉树和树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是，二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。,2004年7月16日,满二叉树,完全二叉树,思考：给出完全二叉树有n个结点，问有多少个叶子结点？,深度是多少呢？,满二叉树：每一层结点数达到最大,完全叉树：除最后一层外，其余每一层结点数达到最大，最后一层结点或满，或右边连续缺少若干结点,最后一个非叶子结点n/2,二叉树性质,性质1：二叉树的第i层上至多有2i-1（i1）个结点，满二叉树的第k层上有2k-1个结点；性质2：深度为h的二叉树中至多含有2h-1个结点，深度为h的满二叉树共有2h-1个结点；性质3：若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1；性质4：具有n个结点的二叉树，其深度至少为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)：按对称序周游左子树，访问根，按对称序周游右子树,2004年7月16日,NLR,先序遍历序列：ABDC,前序遍历:,2004年7月16日,LNR,中序遍历序列：BDAC,中序遍历:,2004年7月16日,LRN,后序遍历序列：DBCA,后序遍历:,2004年7月16日,周游树和森林对树和森林的周游分为按深度优先和按广度优先两种方式树深度优先：先根次序（对应二叉树的前序）和后根次序（对应二叉树的中序序）周游森林的先序和后序号对应二叉树的先序和中序树广度优先：按层次访问,2004年7月16日,考点5二叉树的存储和线索二叉树,二叉树的llink-rlink法存储表示,指向右子树根,指向左子树根,2004年7月16日,线索二叉树，n个结点，n+1个空指针（n个结点，2n个指针，n-1个指针指向结点）,中序遍历DBGEACHFI,2004年7月16日,完全二叉树存储完全二叉树中除最下面一层外，各层都被结点充满了，每一层结点个数是上一层结点个数的2倍。,i,2i,2i+1,312312661525163569334988,123456789101112,2004年7月16日,考点6哈夫曼树（huffman)(霍夫曼树）,最优二叉树树的带权路径长度最小的树（扩充二叉树）,树的带权路径长度：各个叶子结点到根的路径长度与结点权值乘积之和,WPL=,2004年7月16日,Huffman算法求最优二叉树,10,12,16,21,30,结点权值如下：,10,12,22,16,21,30,第一步（最小的两棵树构成新树,单结点森林,2004年7月16日,10,12,22,16,21,30,37,第二步,10,12,22,16,21,30,37,第三步,52,10,12,24,16,21,30,37,第四步,52,89,求WPL,2004年7月16日,考题,1、下列关于二叉树周游的叙述中，哪一条是正确的？A）若一个结点是二叉树的对称序最后一个结点，则它必是该二叉树的前序最后一个结点B）若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的对称序最后一个结点C）若一个树叶是某二叉树的对称序最后一个结点，则它必是该二叉树的前序最后一个结点D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的对称序最后一个结点C2009.04（右子树为空）,A,B,对称序BA前序AB,2004年7月16日,2、按层次次序将一棵有n个结点的完全二叉树的所有结点从1到n编号，当in/2时，编号为i的结点的左子女的编号为A）2i-1B）2iC）2i+1D）不确定B2009.04,2004年7月16日,1）该二叉树对应的树林包括几棵树？2008。04A、1B、2C、3D、4C（根结点右子树转换为树）2）如果用llink-rlink存储该二叉树，则各结点指针域共包含多少空指针A、0B、4C、8D、12CN+13）如果将该二叉树存储为对称序线索二叉树，则结点C的左线索指向哪个结点？A、结点AB、结点BC、结点ED、结点G对称序：DBGEACFA,2004年7月16日,试题（12）（14）基于如下所示的二叉树。2007.04（12）该二叉树对应的树林包括几棵树？A）1B)2C）3D）4B去掉右子树与父亲连线（13）按后根次序周游该二叉树对应的树林，所得到的结点序列为A）DBAFEGCB）ABCDEFGC）DBFGECAD）ACBEGDFA后根访问第一课树的子树，访问第一棵树的根，后根访问其他树（二叉树的中序（14）按层次次序周游该二叉对应的树林，所得到的结点序列为A）DBAFEGCB）ABCDEFGC）DBFGECAD）ACBEGDFD,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+110,2.5查找,在数据结构中找出满足条件的结点的过程,2004年7月16日,考点1顺序查找,逐个依次查找，对逻辑次序无要求（不必排序），可以是顺序存储也可以是链式存储优点：简单缺点：速度慢，检索长度与结点N成正比,2004年7月16日,考点2二分查找,线性表结点必须按关键码值排序，以顺序存储方式存储的（考概念）二分查找过程（查找612）,时间复杂度Log2n,2004年7月16日,例题1：对线性表进行二分法检索，其前提条件是：线性表以【1】方式存储，并且按关键码值排好序。,2004年7月16日,考点3分块查找,线性表分块每块不必有序块间有序查找过程1、在索引表中确定记录所在块2、在块中查找记录,索引表,2004年7月16日,考点4散列（哈希）表的存储和查找（重点）,散列表（哈希表）：利用散列法构建的线性表，是一种重要的存储方式和检索方式基本思想：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）=kmod13,用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值14,95,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日,极端情况，检索达n次,2004年7月16日,B树和B+树（适合于外存查找）B树是一种平衡多路查找树,2004年7月16日,至少有M/2-1个关键码最多M-1个关键码,NULL,2004年7月16日,B树的插入结点和删除结点仍然要满足B树特征,2004年7月16日,以下两题基于图3-8所示的5阶B树结构,1、向该B树中插入关键码72后，该B树第2层结点数为（）A、6B、7C、8D、9C2、从该B树中删除关键码15后，该B树的第2层结点数为()A、6B、7C、8D、9B,2004年7月16日,结点分支多于5个，需要分为两个结点每个结点至少含2个关键码（分裂）,6470727378,45607282,3841,4753,6070,7378,8695,中间关键码至少为5/2-12,最多4个,2004年7月16日,删除15结点只剩一个关键码，不满足要求从右边移一个元素（合并）,35,1018,456082,258,1115,232630,3841,4753,64707378,8695,1115,1023,258,1118,2630,中间关键码至少为5/2-12,最多4个,2004年7月16日,2004年7月16日,B树和B+树的特点。B树和B+树用于组织文件的动态索引结构。B树和B+树都是平衡的多分支树。B树只适用于随机检索，不适用于顺序检索，而B+树适用于顺序检索和随机检索。,2.6排序,直接插入排序选择排序交换排序归并排序,2004年7月16日,考点1插入排序,直接插入排序待排序记录插入到已排序记录中,i=1(12)201889182316,排序结果：（89121618182023）,i=2(1220)1889182316,i=3(121820)89182316,i=4(8121820)9182316,i=5(89121820)182316,i=6(8912181820)2316,i=7(891218182023)16,i=8(89121618182023),直接插入排序过程示意,时间复杂度O(n2),2004年7月16日,二分插入排序时间复杂度O(nlog2n）,2004年7月16日,希尔Shell(缩小增量）排序,先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,2004年7月16日,例对下列序列采用希尔排序,49386597761327495504,第一趟希尔排序增量为5,49,38,65,97,76,13,27,49,55,04,13,49,27,38,49,65,97,55,04,76,0123456789,2004年7月16日,例对下列序列采用希尔排序,49386597761327495504,第二趟希尔排序增量为3,13,49,27,38,49,65,97,55,04,76,13,38,55,76,04,27,65,49,49,97,0123456789,2004年7月16日,例对下列序列采用希尔排序,49386597761327495504,第三趟希尔排序增量为1,13,38,55,04,27,65,49,49,97,76,04,13,27,38,49,49,55,65,76,97,0123456789,2004年7月16日,选择排序,15,12,53,45,65,第1趟,12,15,53,45,65,第2趟,12,15,53,45,65,第3趟,12,15,45,53,65,第3趟,12,15,45,53,65,2004年7月16日,堆排序（完全二叉树）,2004年7月16日,时间复杂度O(nlog2n),2004年7月16日,交换排序冒泡排序:相邻俩俩比较，交换，大数沉底72，73，71，23，94第一趟：72，73，71，23，94737172717323947323727123739473947271237394,2004年7月16日,快速排序,2004年7月16日,以第一个元素为基准,2004年7月16日,归并排序要求待排序文件基本有序，将待排序文件分成若干子文件，两两归并,2004年7月16日,2004年7月16日,2004年7月16日,考题,1、在待排序文件已基本有序的前提下，下列排序方法中效率最高的是A）起泡排序B）直接选择排序C）快速排序D）归并排序A2009.032、下列_关键码序列不符合堆的定义。A）A、C、D、G、H、M、P、Q、R、XB）A、C、M、D、H、P、X、G、Q、RC）A、D、P、R、C、Q、X、M、H、GD）A、D、C、G、P、H、M、Q、R、XC2008.09,2004年7月16日,3、设待排序关键码序列为（25，18，9，33，67，82，53，95，12，70），要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码95被放到第几个位置？A）7B）8C）9D）10,25，18，9，33，67，82，53，95，12，70,12，18，9，33，67，82，53，95，25，70,12，18，9，33，67，82，53，95，25，70,12，18，9，33，67，82，53，95，25，70,12，18，9，25，67，82，53，95，33，70,12，18，9，25，67，82，53，95，33，70,2004年7月16日,4、对N个记录的文件进行起泡排序，所需辅助空间为A、O（1）B、O（logn)C、O(N)D、O(N2)A,2004年7月16日,（7）数据结构概念一般包括三个方面的内容，它们是A)数据的逻辑结构、数据的传输结构、数据的分析挖掘B)数据的逻辑结构、数据的存储结构、数据的运算C)数据的存储结构、数据的展示方式、数据的运算D)数据的传输结构、护具的展示方式、数据的分析挖掘（8）下列关于链式存储结构的叙述中，哪些是不正确的？.逻辑上相邻的结点物理上不比邻接.每个结点都包含好一个指针域.用指针来提现数据元素之间逻辑上的联系.结点中的指针都不能为空.可以通过计算直接确定第i个结点的存储地址A)仅、和B)仅、和C)仅、和D)仅、和,2004年7月16日,栈结构不适用与下列哪一种应用？A)表达式求值B)树的层次次序周游算法的实现C)二叉树对称序周游算法的实现D)快速排序算法的实现（10）下列哪一个不是从列的基本运算？A)从队尾插入一个新元素B)判断一个队列是否为空C)从队列中删除第1个元素D)读取队头元素的值,2004年7月16日,（11）顺序存储下上角矩阵,2004年7月16日,（12）在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最短？A)线性表按顺序方式存储，查找关键码值为900的结点B)线性表按链接方式存储，查找关键码值为900的结点C)线性表按顺序方式存储，查找线性表中第900个结点D)线性表按链接方式存储，查找线性表中第900个结点（