数据结构年终复习总结

数据结构期末考试模拟题专业：09网络工程 班级：二班 姓名：黄晓兵 学号：4 1设n 是描述问题规模的正整数，下面程序片段的时间复杂度是（ ）。 i=2; while(in/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-D C. (A-B*C)-D D. (A-B)*(C-D)3. 循环队列用数组A0m-1存放其元素值，头尾指针分别为front 和rear，front指向队头元素，rear指向队尾元素的下一个元素，则当前队列中的元素个数是（ ）。 A(rear-front+m)%m B(rear-front+1)%m Cread-front-1 Dread-front4. 若一棵深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树共有（ ）个叶子结点。 A17 B18 C19 D205. 某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括（ ）棵树。 A. 1 B. 2 C. 3 D. 46. 下列关于散列表的说法中，不正确的有（ ）个。 I. 散列表的平均查找长度与处理冲突方法无关 II. 在散列表中，“比较”操作一般也是不可避免的 III. 散列表在查找成功时的平均查找长度与表长有关 IV. 若在散列表中删除一个元素，只需简单地将该元素删除即可 A. 1 B. 2 C. 3 D. 47. 含有20个结点的平衡二叉树的最大深度为（ ）。 A. 4 B. 5 C. 6 D. 78. 已知有向图G=(V，A)，其中V=a,b,c,d,e，A=，对该图进行拓扑排序，下面序列中不是拓扑排序的是（ ）。 A. a,d,c,b,e B. d,a,b,c,e C. a,b,d,c,e D. 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,36 B. 15,25,35,50,20,40,80,85,36,70 C. 15,25,50,35,80,85,20,36,40,70 D. 15,25,35,50,80,20,36,40,70,8510. 设线性表中每个元素有两个数据项k1和k2，现对线性表按以下规则进行排序：先看数据项k1，k1值小的元素在前，大的在后；在k1值相同的情况下，再看k2，k2值小的在前，大的在后。满足这种要求的排序方法是（ ）。 A. 先按k1进行直接插入排序，再按k2进行简单选择排序 B. 先按k2进行直接插入排序，再按k1进行简单选择排序 C. 先按k1进行简单选择排序，再按k2进行直接插入排序 D. 先按k2进行简单选择排序，再按k1进行直接插入排序11. （15分）已知线性表（a1, a2,a3,an）存放在一维数组A中。试设计一个在时间和空间两方面都尽可能高效的算法，将所有奇数号元素移到所有偶数号元素前，并且不得改变奇数号（或偶数号）元素之间的相对顺序，要求： （1） 给出算法的基本设计思想。 （2）根据设计思想，采用C或C+或Java语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。 12.n个整数存放在一维数组L1n中。试设计一个在时间和空间两方面都尽可能高效的算法，找出数组L中的第k小元素（即从小到大排序后处于第k个位置的元素）。要求： （1）给出算法的基本设计思想。 （2）根据设计思想，采用C或C+或Java语言描述算法，关键之处给出注释。 参考答案解析选择题1【解答】C。在程序中，执行频率最高的语句为i=i*3。设该基本语句一共执行了k 次，根据循环结束条件，有n2*3kn/3，由此可得算法的时间复杂度为O(log3n)。2【解答】B。利用栈求表达式的值时，可以分别设立运算符栈和运算数栈，但其原理不变。选项B中A入栈，B入栈，计算得R1，C入栈，计算得R2，D入栈，计算得R3，由此得栈深为2。A、C、D依次计算得栈深为4、3、3。3【解答】A。分rearfront 和rearfront 时，队列中元素个数为rear-front=(rear-front+m)%m；当rearfront 时，队列中元素个数为m-(front-rear) =(rear-front+m)%m。综合、可知，A 选项正确。4【解答】A。完全二叉树第5 层共有24=16 个结点。第6 层最左边有3 个叶子结点，对应第5 层最左边2 个结点，所以第5 层右边有16-2=14 个叶子结点，因此共有17 个叶子结点。5【解答】C。根据后序序列，A 是二叉树的根结点。根据中序遍历序列，则二叉树的形态一定如下图左所示。对于A 的左子树，由后序序列可知，因为B 比D 后被访问，因此，B 必为D 的父结点，又由中序序列可知，D 是B 的右儿子。对于A 的右子树，同理可确定结点E、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个结点，构造6层至少需要20个。8【解答】C。选项C中，删去a、b 及其对应的出边后，c 的入度不为0，此有边，故不是拓扑序列。选项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 排好序后，再对k1 排序，若对k1 排序采用的算法是不稳定的，则对于k1 相同， 而k2 不同的元素可能会改变相对次序，从而不一定能满足题设要求。直接插入排序算法是稳定的，而简单选择排序算法是不稳定的。程序设计题11.（1）算法的基本设计思想： 在数组尾部从后往前，找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元素块。 暂存中块前面的偶数号元素，将块内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素块。 暂存中块前面的偶数号元素，将块内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素块。 如此继续，直到前一步的块前没有元素为止。 （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-1 while(i1) /假设数组从1开始存放。当i=1时，气泡浮出水面 temp=Ai-1; /将“块”前的偶数号元素暂存 for(int j=0;jv;j+) /将大小为v的“块”整体向前平移 Ai-1+j=Ai+j /从前往后依次向前平移 Ai+v-1=temp; /暂存的奇数号元素复制到平移后空出的位置 i-;v+; /指针向前，块大小增1 /while 3）一共进行了n/2 次交换，每次交换的元素个数从1n/2，因此时间复杂度为O(n2)。虽然时间复杂度为O(n2)，但因n2 前的系数很小，实际达到的效率是很高的。算法的空间复杂度为O(1)。12（1）算法的主要设计思想： 从数组L1n中选择枢轴pivot（随机地或者直接取第一个）进行和快速排序一样的划分操作后，表L1n被划分为L1m-1和Lm+1n，其中L(m)=pivot。 讨论m与k的大小关系： 当m=k时，显然pivot就是所要寻找的元素，直接返回pivot即可。 当mk时，则所要寻找的元素一定落在L1m-1中，从而可以对L1m-1递归地查找第k小的元素。 （2）算法的实现如下： int kth_elem(int a,int low,int high,int k) int pivot=alow; int low_temp=low; /由于下面会修改low与high,在递归时又要用到它们 int high_temp=high; while(lowhigh) whi