数据结构课件题目（附答案） - 图文(3)

…

11.构造平衡二叉树

给定表{25，18，48，07，76，52，81，70，92，15}，

按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。 12.已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon）按表中元素顺序依次插入一棵初始为空的: (1) 二叉排序树;

(2) 平衡二叉排序树； (3) 最佳二叉排序树

分别求其在等概率的情况下查找成功的平均查找长度。

13.二叉查找树的查找效率与二叉树的( （1）C )有关, 在 (（2）C )时其查找效率最低 (1) A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2) A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

14.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C.(100,60,80,90,120,110,130) D.(100,80,60,90,120,130,110)

15.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR

16.设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。

（1）51,250,501,390,320,340,382,363 （2）24,877,125,342,501,623,421,363

答：序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应该出现小于501的数，但序列中出现了623，故不可能。 17.下面关于m阶B树说法正确的是( B )

①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字;

③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。

A. ①②③ B. ②③ C. ②③④ D. ③ 18.下面关于B和B+树的叙述中，不正确的是( C )

A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。 C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。 19.一棵3阶B-树中含有2047个关键字，包括叶子结点层，该树的最大深度为( B )。

A. 11 B. 12 C. 13 D. 14 20.已知2棵2-3 B-树如下（省略外结点）： 对树（a）,请分别画出先后插入26，85两个新结点后的树形；

对树（b）,请分别画出先后删除53，37两个结点后的树形。

24 4545 2461 9053 90

50 1003 1230 3761 703375370

21.下面关于哈希(Hash，杂凑)查找的说法正确的是( C ) A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

100

…

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

22.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )

A. k-1次 B. k次 C. k+1次 D. k（k+1）/2次

23.散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 24.将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会

第十章

1.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较多少次

希尔排序示例：请给出对一组记录（54,38,96,23,15,90,72,60,45,83）进行希尔排序（增量序列为5，3，1）时的排序过程。

冒泡排序示例：一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列 快速排序示例

对下列一组关键字（46,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果 堆排序示例

已知一组关键字（46,58,15,45,90,18,10,62）试写出堆排序建的初始堆和排序的过程

2.已知8个记录，其关键字分别为 (179，208，306，093，859，984，271，033) 试用基数排序法实施排序，描述其排序过程

3.以关键码序列（503，087，512，061，908，170，897，275，653，246）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：

（1）直接插入排序；（2）希尔排序（增量5，3，1）；（3）起泡排序 （4）快速排序；（5）简单选择排序（6）堆排序；（7）归并排序；（8）基数排序。 4.下列内部排序算法中：

A. 快速排序 B. 直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 (1)其比较次数与序列初态无关的算法是( CD ) (2)不稳定的排序算法是( ADF )

(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<

(4)排序的平均时间复杂度为O(n?logn)的算法是( ACF ),为O(n?n)的算法是( BDE ) 5.设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( C )。 A. O(N)， O(N)， O(N) B. O(N)， O(N*log2N), O(N*log2N) C. O(N)， O(N*log2N), O(N2) D. O(N2)，O(N*log2N), O(N2) 6.一个排序算法的时间复杂度与( B )有关。

A. 排序算法的稳定性 B. 所需比较关键字的次数C. 所采用的存诸结构 D. 所需辅助存诸空间的大小

7.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录

…

为基准得到的一次划分结果为( C )。

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) 8.有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是( A )。

A. SHELL排序（希尔排序） B. 堆排序 C. 冒泡排序 D. 快速排序

9.在下列排序方法中，( D )方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。

A、快速排序 B、冒泡排序 C、堆排序 D、插入排序

10.就分类算法所用的辅助空间而言，堆分类、快速分类和归并分类的关系是( A )。 A. 堆分类<快速分类<归并分类 B. 堆分类<归并分类<快速分类 C. 堆分类>归并分类>快速分类 D. 堆分类>快速分类>归并分类

11.设要将序列(q,h,c,y,p,a,m,s,r,d,f,x) 中的关键码按字母升序重新排序，

(1)( B )是初始步长为4的shell排序一趟扫描的结果； (2)( C )是对排序初始建堆的结果；

(3)( A )是以第一个元素为分界元素的快速一趟扫描的结果 从下面供选择的答案中选出正确答案填入括号内。 A.f,h,c,d,p,a,m,q,r,s,y,x B.p,a,c,s,q,d,f,x,r,h,m,y

C.a,d,c,r,f,q,m,s,y,p,h,x D.h,c,q,p,a,m,s,r,d, ,x,y E.h,q,c,y,a,p,m,s,d,r,f,x

12.基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是( A )。

A. O(nlogn) B. O(logn) C. O(n) D. O(n*n)

13.外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( F )

14.在外排序过程中，对长度为n的初始序列进行―置换—选择‖排序时，可以得到的最大初始有序段的长度不超过n/2。( F )

15.外排中使用置换选择排序的目的，是为了增加初始归并段的长度。T

16.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 答：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1气泡排序就可否定本题结论了。

17.设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？

答：设归并路数为k，归并趟数为s，则s=[logk100]，因为[logk100]=3，因为k为整数，故k=5,即最少5-路归并可以完成排序。

18.设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25,40,16,38,77,64,53,88,9,48,98。试根据它们做4路平衡归并，要求：

(1)指出总的归并趟数； (3分)(2)构造最佳归并树； (8分) (3)根据最佳归并树计算每一趟及总的读记录数。(5分) 答：（1）三趟归并（2）最佳归并树图略。 （3）设每次读写一个记录。 第一趟50次读写 总的读写次数：5052

[(9+16)*3+(25+38+40)*2+(48+53+64+77)*2+(88+98)]*2

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