二级access笔试之数据结构基础.ppt

【例1-25】设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点为_______。 A）8 B）7 C）6 D）5 答案 A 【例1-26】某二叉树中度为2的结点有18个，则该二叉树中有 个叶子结点。（2005年4月） 答案 19 【例1-27】具有88个结点的二叉树，其深度至少为______。 答案 7 【例1-28】在深度为7的满二叉树中，叶子结点的个数为（2006年4月） A）32 B）31 C）64 D）63 答案 C 【例1-29】设一棵完全二叉树共有700个结点，则在该二叉树中有________个叶子结点。 答案 350 【例1-30】对如图1-30所示的二叉树，进行后序遍历的结果为 。（2006年4月） A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA 答案 D 【例1-31】假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 。 答案：ABDEGHJCFI 【例1-32】对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_____。（2005年4月） A）log2n B）n/2 C）n D）n+l 答案 C 【例1-33】下列数据结构中，能用二分法进行查找的是 。（2005年9月） A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 答案 A 【例1-34】已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当使用二分法查找值为90的元素时，查找成功的比较次数为 。 A）1 B）2 C）3 D）9 答案 B 【例1-35】对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 。（2006年4月） 答案 45 【例1-36】在排序算法中，两两比较待排序的记录，当发现不满意顺序要求时，变更它们的相对位置，这就是 排序。 A）希尔排序 B）交换排序 C）插入排序 D）选择排序 答案 B 【例1-37】设待排序关键码序列为（33，18，9，25，67，82，53，95，12，70），要按关键码值递增的顺序排序，采取以第一个关键码为基准元素的快速排序法，第一趟排序完成后关键码33被放到了第_______位置。 A）3 B）5 C）7 D）9 答案 B 【例1-38】对于给定的一组关键字（12，2，16，30，8，28，4，10，20，6，18），按照希尔排序（增量为 5 ）算法进行递增排序，第一趟排序后得到的结果是 。 答案 12，2，10，20，6，28，4，16，30，8，18 【例1-39】对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72。该排序采用的方法是_________。 A）简单插入排序法 B）冒泡排序法 C）简单选择排序法 D）快速排序法 答案 C 【例1-40】以下各组序列中，属于堆的是_______。 A）19，34，26，97，56，75 B）97，26，34，75，19，56 C）19，56，26，97，34，75 D）19，75，34，26，97，56 答案 A 【例1-41】对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_____。（2005年4月） A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2 答案 D 1．简单插入排序法 基本思想： 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。 在最坏的情况下，需要n(n-1)/2次比较。 2．希尔排序 基本思想 先将整个待排元素序列分割成若干个子序列（由相隔某个增量h的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的