计算机二级创建节,全国计算机等级考试二级公共基础第一章节.ppt

﹏ヽ暗。殇╰゛Y 2023-01-23 12:50 58阅读 0赞

全国计算机等级考试二级公共基础第一章节

【例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的元素组成的)分别进行直接插入排序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况)，效率是很高的