2022年数据结构复习题 .pdf
复习题（ 09DS) 一.填空选择1下面程序段的时间复杂度是_。for(i=0;in;i+) for(j=0;jn;j+) Aij=0; 2. 对于一个具有n 个结点的单链表，在已知的结点p 后插入一个新结点的时间复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。3 对于一个栈作进栈运算时，应先判别栈是否为_，作退栈运算时，应先判别栈是否为 _，当栈中元素个数为m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为_。4设有一个10 阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1 个存储地址空间，则a85的地址为 _。5在树型结构中，树根结点没有_结点，其余每个结点的有且只有_个前趋驱结点；叶子结点没有_结点。6在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。7由三个结点构成的二叉树，共有_种不同的形态。8. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过_。9根据 n个元素建立一棵二叉排序树的时间复杂度大致为_。10假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到_次存储冲突。11. 快速排序在最坏情况下的时间复杂度为_。12. 在所有排序方法中，_方法使数据的组织采用的是完全二叉树的结构。13在时间复杂度为O(nlog2n)的所有排序方法中，_排序方法是稳定的。14. 在一个图中，所有顶点的度数之和等于所有边数的_倍。15. 若要把 n 个顶点连接为一个连通图，则至少需要( )条边。A. n B. n+1 C. n-1 D. 2n16. 广义表 A= （a） ，则表尾为（） 。A.a B.( ) C.空表 D.(a) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 17一个广义表的表头总是一个（） 。A.广义表B.元素C.空表D.元素或广义表18. 广义表 A=(x,(a,B),(x,(a,B),y)，则运算 head(head(tail(A) 的结果为（） 。A.x B.(a,B) C.(x,(a,B) D.A 19. 对具有 n 个元素的有序表采用折半查找，则算法的时间复杂度为( ) 。A. O(n) B. O(n2) C. O(1) D. O(log2n) 20. 从具有n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( ) 。A. O(n) B. O(1) C. O(log2n) D. O(n2) 21. 对于长度为18 的顺序存储的有序表，若采用折半查找，则查找第15 个元素的比较次数为( ) 。A. 3B. 4C. 5D. 6 二.解答题1. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72) ，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。3. 给定一组权值（5，9，11，2，7，16） ，请构造哈夫曼树。4. 有序列26，5，77，16，1，请构造大顶堆，要求画出构造步骤。5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34) ，给出采用直接插入排序法进行排序时每一趟的排序结果。6. 已知一组记录为( 46,74,53,14,26,38,86,65,27,34) ，给出采用归并排序法进行排序时每一趟的排序结果。三.算法题1. 实现直接排序算法2. 实现简单选择排序的算法3.用求余法给出散列函数，求负载因子（保留两位小数） ，根据散列函数计算出对应的地址，列出碰撞，统计碰撞次数，并用开地址线性探查法解决碰撞，画出相应的散列表。4. 链表的添加删除操作名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 四.Answer一、1.)(2nO2.)1(O,)(nO3.栈满 ,栈空 ,m 4.Loc(ija)=Loc(00a)jii2/)1(, 故值为 41 5.前驱 ,一，后继6.中序7.3 8.1 9.O( nlog2n) 10.5 11.)(2nO12.堆排序13.归并排序14.12 15.C 16.C 17.D 18.A 19.D 20.A 21.B 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -
