计算机软件技术基础试题库(2)

C) 任一结点无左孩子 D) 任一结点无右孩子

(51) 含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ）

A)3

B)4

C)5

D)6

(52) 除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ ）

A)1/2倍

B)1倍

C) 2倍

D) 3倍

(53) 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为

（ ） A)24

B)25

C)98

D)99

(54) 可以惟一地转化成一棵一般树的二叉树的特点是（ ）

A)根结点无左孩子

B)根结点无右孩子

C)根结点有两个孩子 D)根结点没有孩子

(55) 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为

（ ）。 A) 2h

B) 2h-1

C) 2h+1

D) h+1

(56) 在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个

数为（ ）。

A) 4

B) 5

C) 6

D) 7

(57) 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F

中第一棵 A)m-n

子树的结点个数是（ ）。 B)m-n-1

C) n+1

D) 条件不足，无法确定

(58) 将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，

则编号为49的节点的 左孩子编号为（）。 A) 98

B) 89

C) 50

D) 没有孩子

(59) 下列图示的顺序存储结构表示的二叉树是(A )

(60) 树最适合用来表示（ ）。

A) 有序数据元素

C) 元素之间具有分支层次关系的数据

B) 无序数据元素

D) 元素之间无联系的数据

(61) 在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。

A) 只有右子树上的所有结点 C) 只有左子树的上的部分结点

B) 只有右子树上的部分结点 D) 只有左子树上的所有结点

(62) 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序（ ）。

A) 不发生改变 B) 发生改变

C) 不能确定 D) 以上都不对

(63) 深度优先遍历类似于二叉树的（ ）。

A) 先序遍历

B) 中序遍历

C) 后序遍历

D) 层次遍历

(64) 广度优先遍历类似于二叉树的（ ）。

A) 先序遍历

B) 中序遍历

C) 后序遍历

D) 层次遍历

(65) 任何一个无向连通图的最小生成树（ ）。

A) 只有一棵

B) 一棵或多棵 C) 一定有多棵 D) 可能不存在

（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）

(66) 在分析折半查找的性能时常常加入失败节点，即外节点，从而形成扩充的二叉树。若设失败

节点i所在层次为Li，那么查找失败到达失败点时所做的数据比较次数是（ ）。 A) Li+1

B) Li+2

C) Li-1

D) Li

(67) 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ ）

个元素。

A) 8

B) 63.5

C) 63

D) 7

(68) 由同一组关键字集合构造的各棵二叉排序树( )。

A) 其形态不一定相同，但平均查找长度相同 B) 其形态不一定相同，平均查找长度也不一定相同 C) 其形态均相同，但平均查找长度不一定相同 D) 其形态均相同，平均查找长度也都相同 (69) 衡量查找算法效率的主要标准是（ ）。

A) 元素的个数

B) 所需的存储量 C) 平均查找长度 D) 算法难易程度

(70) 适合对动态查找表进行高效率查找的组织结构是（ ）。

A) 有序表

B) 分块有序表 C) 二叉排序树 D) 快速排序

(3) 能进行二分查找的线性表,必须以（ ）。

A) 顺序方式存储，且元素按关键字有序

B) 链式方式存储，且元素按关键字有序 C) 顺序方式存储，且元素按关键字分块有序 D) 链式方式存储，且元素按关键字分块有序

(71) 为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,

第一个插入的关键字应为（ ） A) 5

B)37

C) 41

D) 62

(72) 对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为 ( )。

A) (19,23,56,34,78,67,88,92) C) (19,23,34,56,67,78,88,92)

B) 23,56,78,66,88,92,19,34) D) (19,23,67,56,34,78,92,88)

(73) 用某种排序方法对关键字序列{35,84,21,47,15,27,68,25,20}进行排序时，序列的变化情况如

下：

20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则采用的方法是（ ）。

A) 直接选择排序 B) 希尔排序

C) 堆排序

D) 快速排序

(74) 一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到

的第一次划分结果为（ ）。

A) 38,40,46,56,79,84 B) 40,38,46,79,56,84

C) 40,38,46,56,79,84 D) 40,38,46,84,56,79

(75) 快速排序在最坏情况下的时间复杂度是（ ）

A) O(n2log2n)

B) O(n2)

C) O(nlog2n)

D) O(log2n)

(76) 下列排序算法中不稳定的是（ ）。

A) 直接选择排序 B) 折半插入排序 C) 冒泡排序

D) 快速排序

(77) 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排

序操作，直到子序列为空或只剩下一个元素为止。这样的排序方法是（ ）。 A) 直接选择排序 B) 直接插入排序 C) 快速排序 (78) 将5个不同的数据进行排序，至多需要比较（ ）次。

A) 8 B) 9 C) 10

D) 25 D) 冒泡排序

(79) 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）。

A)选择排序

B)快速排序

C)冒泡排序

D)插入排序

(80) 排序算法中，不稳定的排序是（ ）。

A)直接插入排序

B)冒泡排序

C)堆排序

D)选择排序

(81) 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，

将其放入已排序序列的正确位置上的方法，称为（ ）.

A) 希尔排序 B) 冒泡排序 C) 插入排序 D) 选择排序

(82) 从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为

（ ）。

A) 希尔排序 B) 归并排序 C) 插入排序 D) 选择排序 (83) 对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。（ ）

A) 从小到大排列好的 C) 元素无序

B) 从大到小排列好的 D) 元素基本有序

(84) 对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（ ）。

A) n+1 B) n

C) n-1 D) n(n-1)/2

(85) 快速排序在下列哪种情况下最易发挥其长处。（ ）

A) 被排序的数据中含有多个相同排序码 B) 被排序的数据已基本有序 C) 被排序的数据完全无序

D) 被排序的数据中的最大值和最小值相差悬殊

(86) 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（ ）。

A) O(n)

B) O(n2)

C) O(nlog2n)

D) O(n3)

(87) 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基

准得到的一次划分结果为（ ）。

A) 38, 40, 46, 56, 79, 84 B) 40, 38, 46 , 79, 56, 84 C) 40, 38，46, 56, 79, 84 D) 40, 38, 46, 84, 56, 79 (88) 下列关键字序列中，（ ）是堆。

A) 16, 72, 31, 23, 94, 53 C) 16, 53, 23, 94，31, 72 (89) 堆是一种（ ）排序。

A) 插入 B) 选择 (90) 堆的形状是一棵（ ）。

A) 二叉排序树 B) 满二叉树

C) 完全二叉树 D) 平衡二叉树 C) 交换

D) 归并

B) 94, 23, 31, 72, 16, 53 D) 16, 23, 53, 31, 94, 72

(91) 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ ）。

A) 79, 46, 56, 38, 40, 84 C) 84, 79, 56, 46, 40, 38

B) 84, 79, 56, 38, 40, 46 D) 84, 56, 79, 40, 46, 38

(92) 下述几种排序方法中，要求内存最大的是（ ）。

A) 插入排序 B) 快速排序 C) 归并排序 D) 选择排序

(93) 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（ ）。

A) -1，4，8，9，20，7，15，7

B) -1，7，15，7，4，8，20，9

C) -1，4，7，8，20，15，7，9 D) A，B，C 均不对。

(94) 51．下列四个序列中，哪一个是堆（ ）。

A) 75,65,30,15,25,45,20,10 C) 75,45,65,30,15,25,20,10 (95) 以下序列不是堆的是( )。

A) (100,85,98,77,80,60,82,40,20,10,66) C) (10,20,40,60,66,77,80,82,85,98,100)

B) (100,98,85,82,80,77,66,60,40,20,10) D) (100,85,40,77,80,60,66,98,82,10,20)

B) 75,65,45,10,30,25,20,15 D) 75,45,65,10,25,30,20,15

(96) 快速排序方法在（ ）情况下最不利于发挥其长处。

A) 要排序的数据量太大

B) 要排序的数据中含有多个相同值 D) 要排序的数据已基本有序

C) 要排序的数据个数为奇数

(97) 对关键码序列28，16，32，12，60，2，5，72 快速排序，从小到大一次划分结果为（ ）。

A) (2,5,12,16)26(60,32,72) C) (2,16,12,5)28(60,32,72)

B) (5,16,2,12)28(60,32,72) D) (5,16,2,12)28(32,60,72)

(98) 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ）。

A) {21,25,5,17,9,23,30} C) {21,9,17,30,25,23,5} 二、填空题

(99) 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。

(100) 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

(101) 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。

(102) 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 (103) 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

(104) 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。

(105) 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。

(106) 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。

(107) 数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。

(108) 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。

B){25,23,30,17,21,5,9} D) {5,9,17,21,23,25,30}

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算机软件技术基础试题库(2)在线全文阅读。