数据结构c语言版期末考试复习试题(无串)(6)

78．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是

A．9 B．11 C．15 D．不能确定

79．具有10个叶子结点的二叉树中有2的结点。

A．8 B．9 C．10 D．11

80．在一个无向图中，所有顶点的度数之和等于所有边数的

A．1/2 B 1 C 2 D 4

81．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的

A．1/2 B 1 C 2 D 4

82．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：

A．3 B．2 C．4 D．5

83．已知一算术表达式的中缀形式为A＋B *C–D/E，后缀形式为ABC *+DE/–，其前缀形式为

A．–A+B*C/DE B．–A+B*CD/E C –+*ABC/DE D．–+A*BC/DE

84．已知一个图，如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为____D___；按广度搜索法进行遍历，则可能得到的一种顶点序列为___A___； ①A．a，b，e，c，d，f B．a，c，f，e，b，d

C．a，e，b，c，f，d， D．a，e，d，f，c，b ②A．a，b，c，e，d，f B．a，b，c，e，f，d

C．a，e，b，c，f，d， D．a，c，f，d，e，b

85．采用邻接表存储的图的深度优先遍历算法类似于二叉树的。

A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历

86．采用邻接表存储的图的广度优先遍历算法类似于二叉树的。

A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历

87．具有n 个结点的连通图至少有

A． n-1 B． n C． n(n-1)/2 D． 2n

88．广义表（（a），a）的表头是，表尾是。

A．a B （） C （a） D （（a））

89．广义表（（a））的表头是，表尾是。

A．a B （） C （a） D （（a））

90．顺序查找法适合于存储结构为的线性表。

A 散列存储 B 顺序存储或链式存储 C 压缩存储 D 索引存储

91．对线性表进行折半查找时，要求线性表必须

A 以顺序方式存储 B 以顺序方式存储，且结点按关键字有序排列

C 以链式方式存储 D 以链式方式存储，且结点按关键字有序排列

92．采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为

A O(n2) B O(nlog2n) C O(n) D O(log2n)

93．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时， C 次比较后查找成功。

A． 11 B 5 C 4 D 8

94．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法 B 。

A 正确 B 错误

95．下面关于B树和B+树的叙述中，不正确的结论是。

A B树和B+树都能有效的支持顺序查找 B B树和B+树都能有效的支持随机查找

C B树和B+树都是平衡的多叉树 D B树和B+树都可用于文件索引结构

96．以下说法错误的是

A．散列法存储的思想是由关键字值决定数据的存储地址

B．散列表的结点中只包含数据元素自身的信息，不包含指针。

C．负载因子是散列表的一个重要参数，它反映了散列表的饱满程度。

D．散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。

97．查找效率最高的二叉排序树是。

A．所有结点的左子树都为空的二叉排序树。

B．所有结点的右子树都为空的二叉排序树。

C．平衡二叉树。

D．没有左子树的二叉排序树。

98．排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 C 。

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

99．在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是

A．希尔排序 B．冒泡排序 C．直接插入排序 D．直接选择排序

100．堆是一种有用的数据结构。下列关键码序列是一个堆。

A．94,31,53,23,16,72 B．94,53,31,72,16,23

C．16,53,23,94,31,72 D．16,31,23,94,53,72

101．堆排序是一种

A．插入 B．选择 C．交换 D．归并

102．在链表中进行操作比在顺序表中进行操作效率高。

A．顺序查找 B．折半查找 C．分块查找 D．插入

103．直接选择排序的时间复杂度为（n 为元素个数）

A．O（n) B．O(log2n) C．O(nlog2n) D． O(n2)

二、填空题。

1．数据逻辑结构包括、和三种类型，树形结构和图状结构合称 非线性结构 。

2．数据的逻辑结构分为 、种。

3．在线性结构中，第一个结点前驱结点，其余每个结点有且只有最后一个结点 有 后续结点，其余每个结点有且只有 1 个后续结点。

4．线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在 多对多 关系。

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

6．数据结构的基本存储方法是和 。

7．衡量一个算法的优劣 …… 此处隐藏：506字，全部文档内容请下载后查看。喜欢就下载吧 ……