电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

数据结构期末复习题讲解VIP免费

数据结构期末复习题讲解_第1页
1/17
数据结构期末复习题讲解_第2页
2/17
数据结构期末复习题讲解_第3页
3/17
(1)若以1234作为双端队列的输入序列,则既不能由输入受限双端队列得到,也不能由输出受限双端队列得到的输出序列是()。A)1234B)4132C)4231D)4213(2)将一个A[1..100,1..100]的三对角矩阵,按行优先存入一维数组B[298]中,A中元素a66,65在B数组中的位置k为()(假设B[0]的位置是1)。A)198B)195C)197D)198(3)若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为()。A)n-1B)1mnC)11mnD)11mn(4)若一个有向图具有拓扑排序序列,并且顶点按拓扑排序序列编号,那么它的邻接矩阵必定为()。A)对称矩阵B)稀疏矩阵C)三角矩阵D)一般矩阵(5)设森林F对应的二叉树为有m个结点,此二叉树根的左子树的结点个数为k,则另一棵子树的结点个数为()。A)m-k+1B)k+1C)m-k-1D)m-k(6)假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行()次探测。A)K-1次B)K次C)K+l次D)K(K+1)/2次(7)一棵深度为k的平衡二叉树,其每个非终端结点的平衡因子均为0,则该树共有()个结点。A)2k-1-1B)2k-1C)2k-1+1D)2k-1(8)如表r有100000个元素,前99999个元素递增有序,则采用()方法比较次数较少。A)直接插入排序B)快速排序C)归并排序D)选择排序(9)如果只考虑有序树的情形,那么具有7个结点的不同形态的树共有()棵。A)132B)154C)429D)前面均不正确(10)对n(n>=2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是()。A)该树一定是一棵完全二叉树B)树中一定没有度为1的结点C)树中两个权值最小的结点一定是兄弟结点D)树中任一非叶结点的权值一定不小于下一任一结点的权值二、(本题8分)斐波那契数列Fn定义如下:F0=0,F1=1,Fn=Fn-1+Fn-2请就此斐波那契数列,回答下列问题:(1)在递归计算Fn的时候,需要对较小的Fn-1,Fn-2,⋯,F1,F0精确计算多少次?(2)若用有关大O表示法,试给出递归计算Fn时递归函数的时间复杂度是多少?三、(本题8分)证明:如果一棵二叉树的后序序列是1u,2u,⋯,nu,中序序列是1pu,2pu,⋯,npu,则由序列1,2,⋯,n可通过一个栈得到序列1p,2p,⋯,np。四、(本题8分)如下图所示为5个乡镇之间的交通图,乡镇之间道路的长度如图中边上所注。现在要在这5个乡镇中选择一个乡镇建立一个消防站,问这个消防站应建在哪个乡镇,才能使离消防站最远的乡镇到消防站的路程最短。试回答解决上述问题应采用什么算法,并写出应用该算法解答上述问题的每一步计算结果。154323964612五、(本题8分)证明一个深度为n的AVL树中的最少结点数为:Nn=Fn+2-1(n≥0)其中,Fi为Fibonacci数列的第i项。六、(本题8分)简单回答有关AVL树的问题:(北方名校经典试题)(1)在有n个结点的AVL树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)?(2)若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键字?七、(本题8分)设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用线性探测再散列解决冲突,要求插入新数据的平均查找次数不超过3次。(1)该散列表的大小m应设计多大?(2)试为该散列表设计相应的散列函数。(3)顺次将各个数据散列到表中。(4)计算查找成功的平均查找次数。八、(本题8分)已知某电文中共出现了10种不同的字母,每个字母出现的频率分别为A:8,B:5,C:3,D:2,E:7,F:23,G:9,H:11,I:2,J:35,现在对这段电文用三进制进行编码(即码字由0,l,2组成),问电文编码总长度至少有多少位?请画出相应的图。九、(本题9分)已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,⋯,Nm个度为m的结点。试问该树中有多少个叶子结点?(北方名校经典试题)十、(本题15分)试用递归法编写输出从n个数中挑选k个进行排列所得序列的算法。模拟试题(七)参考答案一、单项选择题(每小题2分,共20分)(1)参考答案:C)(2)【分析】如下所示,三对角矩阵第1行和最后1行非零元素个数为2个,其余各行的非零元素个数是3个,所知a66,65前面共有2+3*64=194个...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

数据结构期末复习题讲解

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部