发布时间 : 星期四 文章数据结构习题及答案2009年12月14日更新完毕开始阅读0948a4f7ba0d4a7302763aad
T M 21 124 108 32 97 92 95 89 113 113
（1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 6．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。
第8章 查找
一、选择题
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2.对线性表进行折半查找时，要求线性表必须（ ）
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
3．若要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性
4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 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) 5.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR
6. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
7. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行多少次探测？( )
13
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 8. 哈希表的地址区间为0-17,哈希函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。
A． 8 B. 9 C. 10 D. 11 二、判断题
1．哈希函数的选取平方取中法最好。( )
2. 顺序查找法适用于存储结构为顺序或链接存储的线性表。( ) 3. 折半查找法的查找速度一定比顺序查找法快 。( )
4. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。( ) 5．最优二叉树是平衡二叉树。( )
6.虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。( ) 7.二叉排序树删除一个结点后，仍是二叉排序树。( ) 三、填空题
1.在n个元素的顺序表，使用监视哨顺序查找，若查找失败，则比较关键字的次数为__ __。 2.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____。 3.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________ 4.平衡二叉树又称__________。 5.平衡因子的定义是__________。
6.__________法构造的哈希函数肯定不会发生冲突。
7.动态查找表和静态查找表的重要区别在于前者包含有____________运算，而后者不包含这两种运算。 四、应用题
1.在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
2.设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
3.设一个哈希表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键字{10,100,32,45,58,126,3,29,200,400,0}散列到表中。
（1）哈希函数采用除留余数法，用% hashsize（取余运算）将各关键码映像到表中，请指出每一个产生冲突的关键字可能产生多少次冲突。
（2）哈希函数采用先将关键字各位数字折叠相加，再用% hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字码可能产生多少次冲突。
第9章 排序
一、选择题
1．下列排序方法中，哪一个是稳定的排序方法？（ ）
A．简单选择排序 B．折半插入排序 C．希尔排序 D．快速排序 2．若要求尽可能快地对序列进行稳定的排序，则应选（ ）。
A．快速排序 B．归并排序 C．冒泡排序 D．插入排序
3．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。
A．直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序
4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84
14
则采用的排序是 ( )。A.选择 B.冒泡 C.快速 D. 插入
5．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.快速排序 B.shell排序 C.堆排序 D.冒泡排序
6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A． 冒泡 B. 希尔 C. 快速 D.堆 7.就平均性能而言，目前最好的内排序方法是( )排序法。
A.冒泡 B. 希尔插入 C.交换 D. 快速 8．下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 9.下列排序算法中，占用辅助空间最多的是：( )。
A.归并排序 B.快速排序 C.希尔排序 D.堆排序
10.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键字字的记录，加入到已排序记录的末尾，该排序方法是（ ）。
A.选择 B.冒泡 C.插入 D.堆 11．用直接插入排序方法对下面四个序列进行排序（升序），元素比较次数最少的是（ ）。
A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80 C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40
12.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( ) 。
A.l B.4 C.3 D.2 13．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
A．?n/2? B．?n/2?-1 C．1 D．?n/2? +2 14.以下序列不是堆的是( )。
A. (100,85,98,77,80,60,82,40,20,10,66) B. (100,98,85,82,80,77,66,60,40,20,10) C. (10,20,40,60,66,77,80,82,85,98,100) D. (100,85,40,77,80,60,66,98,82,10,20) 二、判断题：
1．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 2．简单选择排序算法在最好情况下的时间复杂度为O（n）。（ ） 3．在待排数据基本有序的情况下，快速排序效果最好。（ ）
4．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ ） 5．堆肯定是一棵平衡二叉树。（ ）
6．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ） 7．归并排序辅助存储空间为O（1）。（ ） 8．冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复
n
杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2),所以快速排序比冒泡排序算法效率更高。 （ ）
9．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（ ） 10．在任何情况下，归并排序都比简单插入排序快。（ ） 三、填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记
15
录的_____。
5．直接插入排序用监视哨的作用是_______。 6．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。 9．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。 四、应用题
1.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。
2．在执行某种排序算法的过程中出现了关键字朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 3．在堆排序、快速排序和合并排序中：
(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
(2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？
(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 4．设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较？ 5．奇偶交换排序如下所述：对于初始序列A[1]，A[2],?,A[n],第一趟对所有奇数i（1<=i (2)写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。 五、算法设计题： 1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。 16