数据结构期末复习习题.pptx

《数据结构期末复习习题.pptx》由会员分享，可在线阅读，更多相关《数据结构期末复习习题.pptx（59页珍藏版）》请在课桌文档上搜索。

1、期末复习习题集,1.数据结构在计算机内存中的表示指A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系,A,2.串是_ A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列,D,3.在n个节点的线索二叉树中，线索的数目为 A.n-1B.nC.n+1D.2n,C,4.顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为了避免产生_现象,假溢出,5.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为_,模式匹配,6.对二叉排序树进行_遍历，可以得到按关键字从小到大排列的节点序列,中序,7.在一组记录的关键

2、字为46,79,56,38,40,84，利用快速排序的方法，以第1个记录为基准得到的第一次划分结果为_,40,38,46,56,79,84,8.设n为3的倍数，分析以下算法的时间复杂度 void fun(int n)int i,j,x,y;for(i=1;i=n;i+)if(3*i=n)for(j=3*i;j=n;j+)x+;y=3*x+2;,9.二维数组A44(即A0.30.3)的元素起始地址是LOC(A00)=1000，元素的长度为2，则LOC(A22)为多少？,（2*4+2）*2+1000=1020,10.如果一棵哈夫曼树T有n0个叶子节点，那么，树T有多少个节点，要求给出求解过程,n=

3、2n2+n1+1且n0=n2+1，得n=2n0+n1-1哈夫曼树n1=0，则n=2n0-1,11.有一个有序表R1.13=1,3,9,12,32,41,45,62,75,77,82,95,100，当用二分查找法查找关键字为82的节点时，经多少次比较后查找成功，依次与哪些关键字进行比较,判定树(略)，总共比较4次，依次关键字为：45,77,95,82,12.以关键字序列265,301,751,129,937,863,742,694,76,438为例，给出归并排序算法的各趟排序结束时关键字序列的状态,第一趟：265,301,751,129,937,863,742,694,76,438第二趟：129

4、,265,301,751,863,937,694,742,76,438第三趟：129,265,301,694,742,751,863,937,76,438第四趟：76,129,265,301,438,694,742,751,863,937,13.链表不具备的特点是A.可随机访问任一节点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比,A,14.一个栈的进栈序列是abcde，则栈的不可能的输出序列是 A.edcbaB.decbaC.dceabD.abcde,C,15.用直接插入序列对下面4个序列进行递增排序，元素比较次数最少的是 A.94,32,40,90,80,46

5、,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40,C,16.以下序列不是堆(大根或小根)的是 A.100,85,98,77,80,60,82,40,20,10,66B.100,98,85,82,80,77,66,60,40,20,10C.10,20,40,60,66,77,80,82,85,98,100D.100,85,40,77,80,60,66,98,82,10,20,D,17.广义表(),a,(a),(a)的长度是_，深度是_,4,3,18.具有n个节点的二叉树采用二叉链存储

6、结构，共有_个空指针域,n+1,19.在有n个顶点的有向图中，每个顶点的度最大可达_,2(n-1),20.设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度 int m=0,i,j for(i=1;i=n;i+)for(j=2*i;j=n;j+)m+;,O(n2),21.下述函数中对应的时间复杂度最小是A.T1(n)=nlog2n+5000nB.T2(n)=n2-8000nC.T3(n)=D.T4(n)=1000log2n,D,22.以下各种存储结构中，最适合用做链队的链表是 A.带队首指针和队尾指针的循环单链表B.带队首指针和队尾指针的非循环单链表C.只带队首指针的非循环单链

7、表D.只带队首指针的循环单链表,B,23.设二维数组A610，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a35的存储地址为1000，则a00的存储地址是_ A.872B.860C.868D.864,B,24.一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为 A.ACBEDB.DECABC.DEABCD.CEDBA,D,25.顺序队和链队的区别仅在于_不同,存储结构,26.一棵完全二叉树上有1001个节点，其中叶子节点的个数是多少？,501,27.下列说法中，不正确的是A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可

8、由若干个数据元素构成D.数据项可由若干个数据元素构成,D,28.广义表(a,b,c,d)的表头是_，表尾是_ A.aB.()C.(a,b,c,d)D.(a,b,c,d),C，B,29.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 A.O(1)B.O(log2n)C.O(n2)D.O(n),D,30.有一种排序方法，它每趟都从未排序序列中挑选出最小元素，并将其放入已排序序列的一端，该排序方法是_ A.希尔排序B.归并排序C.直接插入排序D.简单选择排序,D,31.设高度为h(根节点为第1层)的二叉树上只有度为0和度为2的节点，则此类二叉树中所包含的节点数至少为 A.2hB.2h-1

9、C.2h+1D.h+1,B,32.无向图的邻接矩阵是一个_A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵,A,33.对线性表进行二分查找时，要求线性表必须_ A.以顺序方式存储B.以链式方式存储C.以顺序方式存储且节点按关键字有序排序D.以链表方式存储且节点按关键字有序排序,C,34.在以下排序算法中，_不能保证每趟排序至少能将一个元素放到其最终位置上 A.快速排序B.希尔排序C.堆排序D.冒泡排序,B,35.一个n*n的对称矩阵，如果采用压缩存储放入内存，则容量为A.n2B.n2/2C.n(n+1)/2D.(n+1)2/2,C,36.一个图中包含k个连通分量，若按深度优先搜索方法访问所有节

10、点，则必须调用_次深度优先遍历算法 A.kB.1C.k-1D.k+1,A,37.对于有18个元素的有序表R1.18进行二分查找，则查找R3的比较序列的下标为A.1、2、3B.9、5、2、3C.9、5、3D.9、4、2、3,D,38.在下列排序算法中，_可能出现下列情况：在最后一趟开始之前，所有的元素都不一定在其最终的位置上A.堆排序B.冒泡排序C.直接插入排序D.快速排序,C,39.若一棵哈夫曼树的叶子节点个数为5，则该树的总节点个数为多少？,9,40.对给定的数列R=7,16,4,8,20,9,6,18,5，构造一棵二叉排序树，求：（1）给出按中序遍历得到的数列R1（2）给出按后序遍历得到的

11、数列R2,中序遍历：4,5,6,7,8,9,16,18,20后序遍历：5,6,4,9,8,18,20,16,7,41.在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为_A.4B.5C.6D.7,B,9,20,8,5,6,16,4,7,18,42.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是_A.空或只有一个节点B.完全二叉树C.二叉排序树D.高度等于其节点数,D,43.有一个长度为12的有序表R0.11，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功和查找失败所需的平均比较次数是多少？,5,2,8,0,3,6,10,1,4,7

12、,11,9,ASL成功=37/12，ASL失败=49/13,44.已知一棵完全二叉树的第6层(设根为第一层)有8个叶子节点，则该完全二叉树的节点个数最多是_ A.39B.52C.111D.119,C,45.对由n(n=2)个权值均不同的字符构成的哈夫曼树，关于该树的叙述中，错误的是_A.该树一定是一棵完全二叉树B.该树中一定没有度为1的节点C.树中两个权值最小的节点一定是兄弟节点D.树中任一非叶子节点的权值一定不小于下一层任一节点的权值,A,46.已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则比较的次数最多是 A.4B.5C.6D.7,B,47.将

13、关键字序列7,8,30,11,18,9,14散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为H(key)=(key*3)mod7，处理冲突采用线性探测散列法，要求装填因子为0.7（1）请画出所构造的散列表（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度,n=7，0.7=n/m，因此m=10 H(7)=0 H(8)=3 H(30)=6 H(11)=5 H(18)=5 d1=6，d2=7 H(9)=6 d1=7，d2=8 H(14)=0 d1=1,ASL成功=(4+2+6)/7=12/7ASL失败=(3+2+1+2+1+5+4+3+2+1)/10=12/5

14、,48.为实现快速排序法，待排序序列宜采用存储方式是A.顺序存储B.散列存储C.链式存储D.索引存储,A,49.将一棵有80个节点的完全二叉树按层编号，根节点的编号为1，则对编号为40的结点x，该节点 A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子,B,50.一个10阶对称矩阵A，采用行优先顺序压缩存储上三角元素，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为_一个10阶对称矩阵A，采用行优先顺序压缩存储下三角元素，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为_,35，19,51.假定一棵二

15、叉树的节点数为22，则它的最小深度为_，最大深度为_,5，22,52.构造n个节点的强连通图，至少有_条弧A.nB.n/2C.n+1D.n-1,A,53.在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边 A.nB.n+1C.n-1D.n/2,C,54.将整数序列30,15,21,40,25,26,36,37中的数依次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，给出构造过程,30,15,40,21,36,25,37,55.以数据集合2,5,7,9,13为权值构造一棵哈夫曼树，并计算其带权路径长度 WPL=(2+5)*3+(7+9+13)*2=79,36,22,14,7,7,2,5,13,9,56.设A、B、C、D、E这5个字母出现的频率分别为2,5,7,9,13，要求根据这5个字母设计Huffman编码，并画出对应的Huffman树,36,22,14,7,7,2,5,13,9,A:010B:011C:00D:10E:11,0,0,0,0,1,1,1,1,