发布时间 : 星期二 文章数据结构习题集2015更新完毕开始阅读
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 25
3、 求下图的最小生成树，要求画出最小生成树的生成过程。 16 21 21 11 5 6 19 6 3 33 14 5 4 6 4 答：
4、试利用Dijkstra算法求图7-5中顶点A到其他各顶点之间的最短路径。
4 B 15 2 6 E 8 9 A 12 C 5 4 G 10 D F 3 图7-5
成绩____________ 日期____________________
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 26
第9章 查找
一、选择题：
1、二叉排序树中，关键字值最大的结点（ ）
A．左指针一定为空 B．右指针一定为空 C．左、右指针均为空 D．左、右指针均不为空 2、顺序查找法适合于存储结构为 的线性表。（ ） A．散列存储 B．顺序存储或链接存储 C．压缩存储 D．索引存储
3、在查找过程中，若同时还要做增、删工作，这种查找则称为（ ） A．静态查找 B．动态查找 C．内查找 D．外查找 4、对线性表进行二分查找时，要求线性表必须（ ） A．以顺序方式存储 B．以顺序方式存储且元素有序 C．以链接方式存储 D．以链接方式存储且元素有序
5、一棵二叉排序树T，用（ ）方法进行遍历，可以得到各结点键值的递增序列 A．先根遍历 B．中根遍历 C．层次遍历 D．后根遍历
6、散列表的地址区间为0～16，散列函数为H1（K）=K，采用线性探测法解决冲突，将关键字序列26，25，72，38，1，18，59依次存储到散列表中。元素59存放在散列表中的地址为（ ）。 A．8 B. 9 C. 10 D. 11 7、索引顺序表的特点是顺序表中的数据（ ）。
A．有序 B．无序 C．块间有序 D．散列 8、静态查找表与动态查找表两者的根本差别在于（ ）。
A．逻辑结构不同 B．存储实现不同 C．施加的操作不同 D．数据元素的类型不同
9、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经（ ）次比较后查找成功。
A．2 B．3 C．4 D．12 10、索引顺序表中包含（ ）。
A．顺序表 B．索引表 C．顺序表和索引表 D．索引 11、与其他查找方法相比，散列查找法的特点是（ ）。
A．通过关键字比较进行查找
B．通过关键字计算记录存储地址,并进行地址的比较。 C．通过关键字计算记录存储地址，并进行一定的比较查找 D．通过关键字比较进行查找，并计算记录存储地址
12、在散列函数H(k)=k MOD m中，一般来讲，m应取（ ）。
A．奇数 B．偶数 C．素数 D．充分大的数 13、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素
时，检索成功需比较的次数是（ ）。 A．1 B．2 C．3 D．4 14、由同一组关键字集合构造的各棵二叉排序树( )。
A． 其形态不一定相同，但平均查找长度相同
B．其形态不一定相同，平均查找长度也不一定相同 C．其形态均相同，但平均查找长度不一定相同 D．其形态均相同，平均查找长度也都相同 15、衡量查找算法效率的主要标准是（ ）。
A． 元素的个数 B．所需的存储量 C．平均查找长度 D．算法难易程度
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 27
二、填空题：
1、对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的 上继续查找。
3、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 4、散列法存储的基本思想是由 决定数据的存储地址。
5、由于查找算法的基本运算是关键字之间的比较操作，所以可用 来衡量查找算法的性能。 6、查找有静态查找和动态查找，当查找不成功时动态查找会 。 7、顺序查找法中设置监视哨，可以起到 的作用。
8、假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为： 。 9、折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是 的
顺序表。
10、在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为 。 11、折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它将依次与表中元素
比较大小。
12、当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）
=H（k2），这种现象称为 .
13、设哈希表长m=14, 哈希函数H(key)=key MOD11.表中已有4个结点；addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是 。
三、判断题：
1、采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。 （ ） 2、散列法中的冲突指的是具有不同关键字的元素对应于相同的存储地址。 （ ） 3、中序遍历二叉排序树的结点不能得到排好序的结点序列。 （ ）
四、应用题：
1、已知散列函数为H（k）=k mod 13，关键值序列为19，01，23，14，55，20，84，27，68，11，10，
77，处理冲突的方法为线性探测法，散列表长度为13，试画出该散列表。
0 1 2 3 4 5 6 7 8 9 10 11 12
2、己知一个有序表为{12,18,20,25,29,32,40,62,83,90,95,98},当二分查找法为29和90的元素时,分别需要多少次比较才能查找成功?若采用顺序查找时,分别需要多少次比较才能查找成功? 答：
3、已知一组元素为(46、25、78、62、18、34、12、40、73)，试画出按元素排列顺序输入而生成的一棵二叉排序树。 答：
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 28
4、采用哈希函数Ｈ(k)=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关
键字序列22,15,40,46,17,13,14,28,38 （1）构造哈希表（画示意图）； （2）装填因子；
（3）等概率下成功的平均查找长度 答： 散列地址 关键字 比较次数 0 1 2 3 4 5 6 7 8 9 10 11 12 （2）装填因子= （3）ASLsucc =
5、设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放
地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 散列地址 关键字 比较次数
平均查找长度：ASLsucc=
五、 程序设计题： 1、写出折半查找算法。
成绩____________ 日期____________________
0 1 2 3 4 5 6 7 8 9