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

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

1、1. 数据结构在计算机内存中的表示指数据结构在计算机内存中的表示指A. 数据的存储结构数据的存储结构B. 数据结构数据结构C. 数据的逻辑结构数据的逻辑结构D. 数据元素之间的关系数据元素之间的关系A2. 串是串是_ A. 不少于一个字母的序列不少于一个字母的序列B. 任意个字母的序列任意个字母的序列C. 不少于一个字符的序列不少于一个字符的序列D. 有限个字符的序列有限个字符的序列D3. 在在n个节点的线索二叉树中，线索的数目为个节点的线索二叉树中，线索的数目为 A. n-1B. nC. n+1D. 2nC4. 顺序队列在实现的时候，通常将数组看成是顺序队列在实现的时候，通常将数组看成是一个

2、首尾相连的环，这样做的目的是为了避免一个首尾相连的环，这样做的目的是为了避免产生产生_现象现象假溢出5. 设有两个串设有两个串p和和q，其中，其中q是是p的子串，求的子串，求q在在p中首次出现的位置的算法称为中首次出现的位置的算法称为_模式匹配6. 对二叉排序树进行对二叉排序树进行_遍历，可以得到按遍历，可以得到按关键字从小到大排列的节点序列关键字从小到大排列的节点序列中序7. 在一组记录的关键字为在一组记录的关键字为46,79,56,38,40,84，利用快速排序的方法，以第利用快速排序的方法，以第1个记录为基准得到个记录为基准得到的第一次划分结果为的第一次划分结果为_40,38,46,56

3、,79,848. 设设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; )(6) 1() 13(12n/31in/31in3inOnnin=+= 9. 二维数组二维数组A44(即即A0.30.3)的元素起始的元素起始地址是地址是LOC(A00)=1000，元素的长度为，元素的长度为2，则则LOC(A22)为多少？为多少？（2*4+2）*2+1000=102010. 如果一棵哈夫曼树如果一

4、棵哈夫曼树T有有n0个叶子节点，那么，个叶子节点，那么，树树T有多少个节点，要求给出求解过程有多少个节点，要求给出求解过程n=2n2+n1+1且n0=n2+1，得n=2n0+n1-1哈夫曼树n1=0，则n=2n0-111. 有一个有序表有一个有序表R1.13=1,3,9,12,32,41,45,62,75,77,82,95,100，当用二分查找法查找关键字为当用二分查找法查找关键字为82的节点时，经的节点时，经多少次比较后查找成功，依次与哪些关键字进多少次比较后查找成功，依次与哪些关键字进行比较行比较判定树(略)，总共比较4次，依次关键字为：45,77,95,8212. 以关键字序列以关键字序

5、列265,301,751,129,937,863,742,694,76,438为例，为例，给出归并排序算法的各趟排序结束时关键字序给出归并排序算法的各趟排序结束时关键字序列的状态列的状态第一趟：265,301,751,129,937,863,742,694,76,438第二趟：129,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,93713. 链表不具备的特点是链表不具备的特点是A. 可随机访问任一节点可随机访问

6、任一节点B. 插入删除不需要移动元素插入删除不需要移动元素C. 不必事先估计存储空间不必事先估计存储空间D. 所需空间与其长度成正比所需空间与其长度成正比A14. 一个栈的进栈序列是一个栈的进栈序列是abcde，则栈的不可能，则栈的不可能的输出序列是的输出序列是 A. edcbaB. decbaC. dceabD. abcdeC15. 用直接插入序列对下面用直接插入序列对下面4个序列进行递增排个序列进行递增排序，元素比较次数最少的是序，元素比较次数最少的是 A. 94,32,40,90,80,46,21,69B. 32,40,21,46,69,94,90,80C. 21,32,46,40,80

7、,69,90,94D. 90,69,80,46,21,32,94,40C16. 以下序列不是堆以下序列不是堆(大根或小根大根或小根)的是的是 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,20D17. 广义表广义表(),a,(a),(a)的长度是的长度是_，深度，深度是是_4, 318. 具有具有n个节点的二叉树采用二叉链存储结构，个节点的二叉树采用二叉链存储

8、结构，共有共有_个空指针域个空指针域 n+119.在有在有n个顶点的有向图中，每个顶点的度最个顶点的有向图中，每个顶点的度最大可达大可达_2(n-1)20. 设设n是偶数，试计算运行下列程序段后是偶数，试计算运行下列程序段后m的的值并给出该程序段的时间复杂度值并给出该程序段的时间复杂度 int m =0,i,j for(i=1;i=n;i+) for(j=2*i;j=2)个权值均不同的字符构成的哈个权值均不同的字符构成的哈夫曼树，关于该树的叙述中，错误的是夫曼树，关于该树的叙述中，错误的是_A. 该树一定是一棵完全二叉树该树一定是一棵完全二叉树B. 该树中一定没有度为该树中一定没有度为1的节点

9、的节点C. 树中两个权值最小的节点一定是兄弟节点树中两个权值最小的节点一定是兄弟节点D. 树中任一非叶子节点的权值一定不小于下一层树中任一非叶子节点的权值一定不小于下一层任一节点的权值任一节点的权值A46. 已知一个长度为已知一个长度为16的顺序表，其元素按关键的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存字有序排序，若采用折半查找法查找一个不存在的元素，则比较的次数最多是在的元素，则比较的次数最多是 A. 4B. 5C. 6D. 7B47. 将关键字序列将关键字序列7,8,30,11,18,9,14散列存储到散列存储到散列表中，散列表的存储空间是一个下标从散列表中，散列表的存

10、储空间是一个下标从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

11、d1 = 10123456789714811301891211133ASL成功成功 = (4+2+6)/7 = 12/7ASL失败失败 = (3+2+1+2+1+5+4+3+2+1)/10 = 12/548. 为实现快速排序法，待排序序列宜采用存储为实现快速排序法，待排序序列宜采用存储方式是方式是A. 顺序存储顺序存储B. 散列存储散列存储C. 链式存储链式存储D. 索引存储索引存储A49. 将一棵有将一棵有80个节点的完全二叉树按层编号，个节点的完全二叉树按层编号，根节点的编号为根节点的编号为1，则对编号为，则对编号为40的结点的结点x，该，该节点节点 A. 无左、右孩子无左、右孩子B. 有

12、左孩子，无右孩子有左孩子，无右孩子C. 有右孩子，无左孩子有右孩子，无左孩子D. 有左、右孩子有左、右孩子B50. 一个一个10阶对称矩阵阶对称矩阵A，采用行优先顺序压缩，采用行优先顺序压缩存储上三角元素，存储上三角元素，a00为第一个元素，其存储地为第一个元素，其存储地址为址为0，每个元素占有，每个元素占有1个存储地址空间，则个存储地址空间，则a45的地址为的地址为_一个一个10阶对称矩阵阶对称矩阵A，采用行优先顺序压缩存，采用行优先顺序压缩存储下三角元素，储下三角元素，a00为第一个元素，其存储地址为第一个元素，其存储地址为为0，每个元素占有，每个元素占有1个存储地址空间，则个存储地址空间

13、，则a45的的地址为地址为_35，1951. 假定一棵二叉树的节点数为假定一棵二叉树的节点数为22，则它的最小，则它的最小深度为深度为_，最大深度为，最大深度为_ 5， 2252. 构造构造n个节点的强连通图，至少有个节点的强连通图，至少有_条弧条弧A. nB. n/2C. n+1D. n-1A53. 在一个具有在一个具有n个顶点的无向图中，要连通全个顶点的无向图中，要连通全部顶点至少需要部顶点至少需要_条边条边 A. nB. n+1C. n-1D. n/2C54. 将整数序列将整数序列30,15,21,40,25,26,36,37中的数中的数依次插入到一棵空的二叉排序树中，试构造相依次插入到

14、一棵空的二叉排序树中，试构造相应的二叉排序树，给出构造过程应的二叉排序树，给出构造过程 3015402136253755. 以数据集合以数据集合2,5,7,9,13为权值构造一棵哈夫为权值构造一棵哈夫曼树，并计算其带权路径曼树，并计算其带权路径长度长度 WPL=(2+5)*3+(7+9+13)*2=79362214772513956. 设设A、B、C、D、E这这5个字母出现的频率分个字母出现的频率分别为别为2,5,7,9,13，要求根据这，要求根据这5个字母设计个字母设计Huffman编码，并画出对应的编码，并画出对应的Huffman树树3622147725139A: 010B: 011C: 00D: 10E: 1100001111