数据结构题库(4)

C．只有一个结点 D．是任意一棵二叉树 42.树最适合用来表示 ( C ) 。

A．有序数据元素 B．无序数据元素

C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据

43. 二叉树按某种顺序线索化后?任一结点均有指向其前趋和后继的线索?这种说法(B )。 A. 正确 B. 错误 C. 不确定 D. 不存在

44. 二叉树的先序遍历序列中?任意一个结点均处在其孩子结点的前面?这种说法( A )。 A. 正确 B. 错误 C. 不确定 D. 不存在

45. 由于二叉树中每个结点的度最大为2?所以二叉树是一种特殊的树?这种说法( A )。 A. 正确 B. 错误 C. 不确定 D. 不存在

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

A. 2h B. 2h-1 C. 2h+1 D. h+1

47. 假定在一棵二叉树中?双分支结点数为15,单分支结点数为30,则叶子结点数为( C )个。 A. 45 B. 15 C. 16 D. 31

48．一颗含18个结点的二叉树的高度至少为（C）。 A、3 B、4 C、5 D、6

49.在下列关于递归遍历算法的应用举例中，错误的是（A)

A利用二叉树的前序遍历不能建立二叉树B利用前序遍历可以输出二叉树 C 利用后序遍历可以销毁一棵二叉树D利用后序遍历可以计算二叉树高度 50.下列关于二叉树遍历非递归算法的描述错误的是（C）

A利用栈实现前序遍历的非递归算法B利用栈实现中序遍历的非递归算法 C后序遍历可独立，不需要借助栈完成非递归算法D层次序遍历可独立，不需要借助栈完成。 51.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的Huffman树中带权路径长度之和为（ D ）。 A 20 B 30 C 40 D 48

第六章图

1.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（ C ） A）O(n) B）O(n＋e) C）O(n*n) D）O(n*n*n) 2.下面（ A ）算法适合构造一个稠密图G的最小生成树。

A） Prim算法 B）Kruskal算法 C）Floyd算法 D）Dijkstra算法 3.最小生成树指的是（ C ） A）由连通网所得到的边数最少的生成树 B）由连通网所得到的顶点相对较少的生成树 C）连通网中所有生成树中权值之和为最小的树 D）连通网的极小连通子图 4.求图中一个顶点到其它各个顶点最短路径的算法是（ C ）

A）Kruskal算法 B）Prim算法 C）Dijkstra算法 D）Floyd算法 5.下列哪一种图的邻接矩阵是对称矩阵？（ B ）

A．有向图 B．无向图 C．AOV网 D．AOE网 6. 下列说法不正确的是（ C ）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 7．无向图G=(V,E),其中：

V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。

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

8.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（D）。 A、n B、e C、2n D、2e

9.设某有向图中的邻接表中有n个表头结点和m个表结点，则该图中有（C）条有向边。 A、n B、n-1 C、m D、m-1 10.一个n个顶点的连通无向图，其边的个数至少为（A）。 A.n-1 B.n C.n+1 D.nlogn 11.要连通具有n个顶点的有向图，至少需要（B）条边。 A.n-1 B.n C.n+1 D.n+2 12.若邻接表中有奇数个表结点，则一定（D）。

A.图中有奇数个结点 B.图中有偶数个结点 C.图为无向图 D.图为有向图 13.设连通图G的顶点数为n，则G的生成树的边数为（A）。 A.n-1 B.n C.2n D.2n-1

14.采用邻接表存储的图广度优先搜索遍历算法类似于二叉树的（D）。 A.中序遍历 B.先序遍历 C.后序遍历 D.按层遍历

15.采用邻接表存储的图深度优先搜索遍历算法类似于二叉树的（B）。 A.中序遍历 B.先序遍历 C.后序遍历 D.按层遍历 16.设无向图的顶点个数为n，则该图最多有（）条边。B A.n-1 B.n（n-1）/2 C.N(n+1)/2 D.0 17.n个结点的完全有向图含有边的数目（）。D

A.n*n B.n（n+1） C.n/2 D.n(n-1)

18.一个有n个结点的图，最少有（）个连通分量。B A.0 B.1 C.n-1 D.n

19.在一个无向图中，所有顶点的度数之和等于边数的（）倍。B A.1/2 B.2 C.1 D.4

20.下面结构中最适于表示稀疏无向图的是（）。C A.邻接矩阵 B.逆邻接表 C.邻接多重表 D.十字链表

21、具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。 A、5 B、6 C、7 D、8

22.设一个非连通无向图有15条边，则该图至少有（C）个顶点。 A、5 B、6 C、7 D、8

23.下列关于无向连通图特征的叙述中，正确的是（A）。

①所有顶点的度之和等于偶数②边数大于顶点个数减1 ③至少有一个顶点的度为1 A、① B、② C、①② D、①③

24.带权有向图用邻接矩阵A存储，则顶点i的入度等于A中（D）。 A、第i行非?的元素之和 B、第i列非?的元素之和

C、第i行非?且非0的元素个数 D、第i列非?且非0的元素个数 25.下列说法中正确的是（B）。

①一个图的邻接矩阵表示唯一②一个图的邻接表表示唯一 ③一个图的邻接矩阵表示不唯一④一个图的邻接表表示不唯一 A、①③ B、①④ C、②③ D、②④ 26.下列有关图的存储结构的说法中错误的是（B）。 A、用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与边数无关。 B、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 C、邻接矩阵只适用于稠密图，邻接表只适用于稀疏图。

D、对同一个有向图来说，邻接表中的边结点数与逆邻接表中的边结点数相等。 27.对同一个有向图，若一个顶点的度为m，出度为n，则对应逆邻接表中该顶点的入度为（C）。 A、m B、n C、m-n D、m+n

28.图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中每个顶点最多进队（A）次。

A、1 B、2 C、3 D、4 29.下面（A）算法可用于求无向图的连通分量。

A、广度优先遍历 B、拓扑排序 C、求最短路径 D、求关键路径 30.任何一个连通图的最小生成树（B）。

A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在

第七章查找

1．线性表只要以（ C ）方式存储就能进行折半查找。

A．链接 B．顺序 C．关键字有序的顺序 D．二叉树

2.对12个记录的有序表作折半查找，当查找失败时，最多需要比较（B）次关键字。 (A)3 (B)4 (C)5 (D) 6 3.对线性表进行二分查找时，要求线性表必须（ C ）。 (A)以顺序方式存储 (B)以链接方式存储

(C)以顺序方式存储，且数据元素有序 (D)以链接方式存储，且数据方式有序

4.在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45，89和12的结点时，所需进行的比较次数分别为（ B ）。

(A)4，4，3 (B)4， 3， 3 (C)3，4，4 (D)3，3，4 5.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（ C ）次比较后查找成功。 (A) 2 (B) 3 (C) 4 (D) 12 6.单链表适用于( A )查找

(A)顺序查找 (B)折半查找 (C)顺序查找，也能折半查找 (D)随机 7.在索引顺序表中查找一个元素，可用的且最快的方法是（ C ）。

(A)用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 (B)用顺序查找法确定元素所在块，再用二分查找法在相应块中查找

(C)用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 (D)用二分查找法确定元素所在块，再用二分查找法在相应块中查找 8.适于对动态查找表进行高效率查找的组织结构是（ D ）。

(A)有序表 (B)分块有序表 (C)二叉排序树 (D) 线性链表 9.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。C

A．(n-1)/2 B. n/2 C. (n+1)/2 D. n 10. 用二分（对半）查找表的元素的速度比用顺序法( ) 。D A．必然快B. 必然慢C. 相等D. 不能确定 11. 具有12个关键字的有序表，折半查找的平均查找长度（ ）。A A. 3.1 B. 4 C. 2.5 D. 5 12．当采用分块查找时，数据的组织方式为( )。B A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） 的数据组成索引块

C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D.数据分成若干块，每块（除最后一块外）中数据个数需相同

13.对有18个元素的有序表作二分(折半)查找,则查找A[3]的比较序列的下标为_D___. A) 1,2,3 B) 9,5,2,3 C) 9,5,3 D) 9,4,2,3

14.若在线性表中采用折半查找法查找元素,该线性表应该___C_. A)元素按值有序

B)采用顺序存储结构

C)元素按值有序且采用顺序存储结构 D)元素按值有序且采用链式存储结构

15.在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与___B__量级相当.

A) 顺序查找 B) 折半查找 C) 前两者均不正确

16.假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行_D__次探测.

A) k-1 B) k C) k+1 D) k(k+1)/2

17.在采用线性探测法处理冲突的闭散列表上，假定装填因子α的值为0.5,则查找任一元素的平均查找长度为__B__.

A) 1 B) 1.5 C) 2 D) 2.5

18.采用顺序查找方式查找长度为n的顺序表时，平均查找长度为（C）。 A、n B、n/2 C、（n+1）/2 D、（n-1）/2

19.如果有5个关键字{a，b，c，d，e}放在顺序表中，它们的查找概率分别为{0.35，0.25，0.20，0.15，0.05}，按照（C）顺序存放可使查找成功的平均查找长度达到最小。 A、d，a，b，c，e B、e，d，c，b，a C、a，b，c，d，e D、a，c，e，d，b 20.关于静态查找和动态查找，说法正确的是（B）。 A、静态查找表上可以做一般的查找和插入操作。

B、动态查找表上不仅可以做查找和检索操作，还可以做插入和删除操作。 C、所谓静态查找表，是指待查的表以顺序存储方式存储。 D、所谓动态查找表，是指待查的表以动态方式存储。

21.采用分块查找法查找时，若线性表中共有225个元素，查找每个元素的概率相同，当采用顺序查找法来确定与给定值匹配的元素所在分块时，每块应分（B）个元素最佳。 A、10 B、15 C、5 D、225 22.已知一棵3阶B树又15个关键字，并且使每个结点的关键字达到最少，则该树的高度是（B）。

A、3 B、4 C、5 D、6

23.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D ）个记录。

A．1 B. 2 C. 3 D. 4

24.一个有序表为{13,18,24,35,47,50,62,83,90,115,134}，当二分查找（搜索）值为90的结点时，查找成功时的比较次数为（B）。 A.1 B.2 C.3 D.4

25.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个， A．1 B．2 C．3 D．4

26．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B ）次。 (A) 25 (B) 10 (C) 7 (D) 1

27.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ C ）次比较。 (A) 1 (B) 2 (C) 3 (D) 4

28.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ D）。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题库(4)在线全文阅读。