数据结构年终复习总结

1、精品数据结构期末考试模拟题专业： 09 网络工程班级：二班姓名：黄晓兵学号： 200903060024welcome精品1设n 是描述问题规模的正整数，下面程序片段的时间复杂度是（）。i=2;while(i<n/3) i=i*3;A. O(log2n)B.O(n)C. O(log3n)D.O(n3)2. 利用栈求表达式的值时，设立运算数栈 OPEN 。假设 OPEN 只有两个存储单元，则在下列表达式中，不会发生溢出的是（）。A. A-B*(C-D)B. (A-B)*C-DC. (A-B*C)-DD. (A-B)*(C-D)3. 循环队列用数组A0 m-1 存放其元素值，头尾指针分别为fr

2、ont和rear ，front指向队头元素， rear 指向队尾元素的下一个元素，则当前队列中的元素个数是（）。A (rear-front+m)%mB (rear-front+1)%mC read-front-1D read-front4. 若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点，则该二叉树共有（ ）个叶子结点。A17B18C19D205. 某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括（ ）棵树。A. 1B. 2C. 3D. 46.下列关于散列表的说法中，不正确的有（）个。 I. 散列表的平均查找长度与处理冲突方法无关II.

3、在散列表中，“比较”操作一般也是不可避免的III. 散列表在查找成功时的平均查找长度与表长有关IV. 若在散列表中删除一个元素，只需简单地将该元素删除即可welcome精品A. 1B. 2C. 3D. 47.含有 20 个结点的平衡二叉树的最大深度为（）。A. 4B. 5C. 6D. 78. 已知有向图 G=(V ，A)，其中 V=a,b,c,d,e ，A=<a,b>，<a,c> ，<d,c> ，<d,e> ，<b,e> ，<c,e> ，对该图进行拓扑排序，下面序列中不是拓扑排序的是（ ）。A. a,d,c,b,eB. d

4、,a,b,c,eC. a,b,d,c,eD. a,b,c,d,e9. 一组经过第一趟 2-路归并排序后的记录的关键字为 25,50,15,35,80,85,20,40,36,70 ，其中包含 5 个长度为 2 的有序表，用 2-路归并排序方法对该序列进行第二趟归并后的结果为（）。A. 15,25,35,50,80,20,85,40,70,36B. 15,25,35,50,20,40,80,85,36,70C. 15,25,50,35,80,85,20,36,40,70D. 15,25,35,50,80,20,36,40,70,8510. 设线性表中每个元素有两个数据项 k1 和k2 ，现对线性

5、表按以下规则进行排序：先看数据项 k1 ，k1 值小的元素在前，大的在后；在 k1 值相同的情况下，再看 k2 ， k2 值小的在前，大的在后。满足这种要求的排序方法是（）。A. 先按 k1 进行直接插入排序，再按 k2 进行简单选择排序B. 先按 k2 进行直接插入排序，再按 k1 进行简单选择排序C. 先按 k1 进行简单选择排序，再按 k2 进行直接插入排序D. 先按 k2 进行简单选择排序，再按 k1 进行直接插入排序11. （ 15 分）已知线性表（a1, a2,a3,an ）存放在A中一。维试数设组计一个在时间和空间两方面都尽可能高效的算法，将所有奇数号元素移到所有偶数号元素前，并

6、且不得改变奇数号（或偶数号）元素之间的相对顺序，要求：welcome精品（ 1） 给出算法的基本设计思想。（ 2）根据设计思想，采用 C或 C+ 或 Java语言描述算法，关键之处给出注释。（ 3）说明你所设计算法的时间复杂度和空间复杂度。12.n 个整数存放在一维数组L1n 中。试设计一个在时间和空间两方面都尽可能高效的算法，找出数组L中的第 k小元素（即从小到大排序后处于第k个位置的元素）。要求：（ 1）给出算法的基本设计思想。（ 2）根据设计思想，采用 C或 C+ 或 Java语言描述算法，关键之处给出注释。参考答案解析选择题1【解答】 C。在程序中，执行频率最高的语句为i=i*3。设该

7、基本语句一共执行了 k 次，根据循环结束条件，有n>2*3k n/3 ，由此可得算法的时间复杂度为 O(log3n) 。2【解答】 B。利用栈求表达式的值时，可以分别设立运算符栈和运算数栈，但其原理不变。 选项 B中A入栈， B入栈，计算得 R1，C入栈，计算得 R2，D 入栈，计算得 R3，由此得栈深为 2。A、C、D依次计算得栈深为 4、3、3。3【解答】 A 。分 rear>front和rear<front两种情况讨论：当 rear>front时，队列中元素个数为 rear-front=(rear-front+m)%m；当 rear<front时，队列中元素

8、个数为 m-(front-rear) =(rear-front+m)%m。综合、可知， A 选项正确。4【解答】A。完全二叉树第 5 层共有 24=16个结点。第 6 层最左边有 3 个叶子结点，对应第 5 层最左边 2 个结点，所以第 5 层右边有 16-2=14个叶子welcome精品结点，因此共有17 个叶子结点。5【解答】 C。根据后序序列， A 是二叉树的根结点。根据中序遍历序列，则二叉树的形态一定如下图左所示。 对于 A 的左子树，由后序序列可知，因为 B 比D 后被访问，因此， B 必为 D 的父结点，又由中序序列可知，D 是 B 的右儿子。对于 A 的右子树，同理可确定结点E、

9、 C、 F 的关系。6【解答】 C。不同冲突处理方法对应的平均查找长度是不同的，I 错误。散列查找的思想是通过散列函数计算地址，然后再比较关键字确定是否查找成功，II 正确。平均查找长度与填装因子（即表中记录数与表长之比）有关，III 错误。在开放定址的情况下，不能随便删除表中的某个元素（只能标记为删除状态），否则可能会导致搜索路径被众多，IV 错误。7【解答】 C。在平衡二叉树的结点最少情况下，递推公式为N0=0 ，N1=1 ，N2=2 ，Nh=1+Nh-1+Nh-2（h 为平衡二叉树高度， Nh 为构造此高度的平衡二叉树所需最少结点数） 。通过递推公式可得，构造5 层平衡二叉树至少需12个

10、结点，构造 6 层至少需要 20 个。8【解答】 C。选项 C 中，删去 a、b 及其对应的出边后， c 的入度不为 0，此有边 <d,c> ，故不是拓扑序列。选项A、B、D 均为拓扑序列。9【解答】 D 。筛选法初始建堆为 8,17,23,52,25,72,68,71,60，输出8 后重 建 的 堆 为 17,25,23,52,60,72,68,71， 输 出17后 重 建 的 堆 为23,25,68,52,60,72,71。10 【解答】首先应确定k1 ，k2的排序顺序，若先排k1 再排 k2 ，则排序结果不符合题意， 排除 AC。再考虑算法的稳定性， 当 k2 排好序后，再对

11、 k1 排序，若对 k1 排序采用的算法是不稳定的，则对于k1 相同， 而 k2 不同的元welcome精品素可能会改变相对次序， 从而不一定能满足题设要求。 直接插入排序算法是稳定的，而简单选择排序算法是不稳定的。程序设计题11. （1 ）算法的基本设计思想： 在数组尾部从后往前，找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元素块。暂存中块前面的偶数号元素，将块内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素块。暂存中块前面的偶数号元素，将块内奇数号结点依次前移，然后将暂存的偶数号结

12、点复制到空出来的数组单元中。就形成了四个连续的奇数号元素块。如此继续，直到前一步的块前没有元素为止。（ 2）算法的设计如下：void Bubble_Swap(ElemType A ,int n) int i=n,v=1; /i为工作指针，初始假设 n 为奇数， v 为“块”的大小ElemType temp;/ 辅助变量if(n%2=0) i=n-1;/ 若 n 为偶数，则令 i 为 n-1while(i>1)/ 假设数组从 1 开始存放。当 i=1 时，气泡浮出水面temp=Ai-1;/ 将“块”前的偶数号元素暂存for(int j=0;j<v;j+)/ 将大小为 v 的“块”整体

13、向前平移welcome精品Ai-1+j=Ai+j/ 从前往后依次向前平移Ai+v-1=temp;/ 暂存的奇数号元素复制到平移后空出的位置i-;v+;/ 指针向前，块大小增1/while3）一共进行了n/2次交换，每次交换的元素个数从1n/2 ，因此时间复杂度为 O(n2) 。虽然时间复杂度为O(n2) ，但因 n2前的系数很小，实际达到的效率是很高的。算法的空间复杂度为O(1) 。12 （1 ）算法的主要设计思想：从数组L1n 中选择枢轴pivot （随机地或者直接取第一个）进行和快速排序一样的划分操作后，表L1n 被划分为L1 m-1 和 Lm+1n ，其中L(m)=pivot。讨论 m

14、与 k 的大小关系：当 m=k 时，显然 pivot就是所要寻找的元素，直接返回pivot 即可。当 m<k时，则所要寻找的元素一定落在Lm+1n 中，从而可以对Lm+1n 递归地查找第k 小的元素。当m>k时，则所要寻找的元素一定落在L1 m-1 中，从而可以对L1 m-1 递归地查找第 k 小的元素。（2）算法的实现如下：int kth_elem(int a,int low,int high,int k) int pivot=alow;welcome精品int low_temp=low;/ 由于下面会修改low 与 high, 在递归时又要用到它们int high_temp=high;while(low<high) while(low<high&&ahigh>pivot) -high;alow=ahigh;while(low<high&&alow<pivot) +low;ahigh=alow;alow=pivot;/ 上面即为快速排序中的划分算法/