数据结构 第5 6 章作业 图 哈希表 西安石油大学

简介: 数据结构 第5 6 章作业 图 哈希表 西安石油大学

第6章 图

1.选择题

(1)在一个图中,所有顶点的度数之和等于图的边数的(   )倍。

 A.1/2            B1             C2             D4

答案:C

(2)在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的(   )倍。

 A.1/2            B1             C2             D4

答案:B

解释:有向图所有顶点入度之和等于所有顶点出度之和。

(3)具有n个顶点的有向图最多有(   )条边。  

A.n             Bn(n-1)         Cn(n+1)       Dn2

答案:B

解释:有向图的边有方向之分,即为从n个顶点中选取2个顶点有序排列,结果为n(n-1)。

(4)n个顶点的连通图用邻接距阵表示时,该距阵至少有(   )个非零元素。

A.n             B2(n-1)         Cn/2           Dn2

答案:B

(5)G是一个非连通无向图,共有28条边,则该图至少有(   )个顶点。

A.7             B.8             C.9             D10

答案:C

解释:8个顶点的无向图最多有8*7/2=28条边,再添加一个点即构成非连通无向图,故至少有9个顶点。

(6)若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点,则该图一定是(   )图。

A.非连通       B连通         C强连通        D有向

答案:B

解释:即从该无向图任意一个顶点出发有到各个顶点的路径,所以该无向图是连通图。

(7)下面( )算法适合构造一个稠密图G的最小生成树。

A. Prim算法     BKruskal算法   CFloyd算法     DDijkstra算法

答案:A

解释:Prim算法适合构造一个稠密图G的最小生成树,Kruskal算法适合构造一个稀疏图G的最小生成树。

(8)用邻接表表示图进行广度优先遍历时,通常借助(   )来实现算法。

A.栈            B. 队列            C.              D.图

答案:B

解释:广度优先遍历通常借助队列来实现算法,深度优先遍历通常借助栈来实现算法。

(9)用邻接表表示图进行深度优先遍历时,通常借助(   )来实现算法。

A.栈            B. 队列            C.              D.图

答案:A

解释:广度优先遍历通常借助队列来实现算法,深度优先遍历通常借助栈来实现算法。

(10)深度优先遍历类似于二叉树的(   )。

A.先序遍历     B.中序遍历       C.后序遍历      D.层次遍历

答案:A

(11)广度优先遍历类似于二叉树的(   )。

A.先序遍历     B.中序遍历       C.后序遍历       D.层次遍历

答案:D

(12)图的BFS生成树的树高比DFS生成树的树高(   )。

A.小           B相等           C小或相等       D大或相等

答案:C

解释:对于一些特殊的图,比如只有一个顶点的图,其BFS生成树的树高和DFS生成树的树高相等。一般的图,根据图的BFS生成树和DFS树的算法思想,BFS生成树的树高比DFS生成树的树高小。

(13)已知图的邻接矩阵如图6.30所示,则从顶点v0出发按深度优先遍历的结果是(    )。


                           图6.30  邻接矩阵

(14)已知图的邻接表如图6.31所示,则从顶点v0出发按广度优先遍历的结果是(    ),按深度优先遍历的结果是(    )。


图6.31  邻接表

A.0 1 3 2 B.0 2 3 1 C.0 3 2 1 D.0 1 2 3

答案:D、D

(15)下面(   )方法可以判断出一个有向图是否有环。

A.深度优先遍历     B拓扑排序     C求最短路径     D求关键路径

答案:B

2.应用

(1)已知图6.32所示的有向图,请给出:

① 每个顶点的入度和出度;   ② 邻接矩阵;③ 邻接表;④ 逆邻接表。            


           


                   图6.32  有向图                          图6.33  无向网

答案:


(2)已知如图6.33所示的无向网,请给出:

邻接矩阵;    

邻接表;

最小生成树

答案:      

                                   



           

                                     

 

a

b

4

c

3

b

a

4

c

5

d

5

e

9

c

a

3

b

5

d

5

h

5

d

b

5

c

5

e

7

f

6

g

5

h

4

e

b

9

d

7

f

3

f

d

6

e

3

g

2

g

d

5

f

2

h

6

(3)已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

(4)有向网如图6.35所示,试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径,完成表6.9。

           

                      图6.34  邻接矩阵                               图6.35  有向网

表6.9

D

终点

i=1

i=2

i=3

i=4

i=5

i=6

b

15

(a,b)

15

(a,b)

15

(a,b)

15

(a,b)

15

(a,b)

15

(a,b)

c

2

(a,c)

d

12

(a,d)

12

(a,d)

11

(a,c,f,d)

11

(a,c,f,d)

e

10

(a,c,e)

10

(a,c,e)

f

6

(a,c,f)

g

16

(a,c,f,g)

16

(a,c,f,g)

14

(a,c,f,d,g)

S

终点集

{a,c}

{a,c,f}

{a,c,f,e}

{a,c,f,e,d}

{a,c,f,e,d,g}

{a,c,f,e,d,g,b}

   

(5)试对图6.36所示的AOE-网:

① 求这个工程最早可能在什么时间结束;    

② 求每个活动的最早开始时间和最迟开始时间;

③ 确定哪些活动是关键活动

答案:按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l,根据l - e = 0? 来确定关键活动,从而确定关键路径。

¸

·

 4 ¹

º

»

Ve

0

19

15

29

38

43

Vl

0

19

15

37

38

43

<1, 2>

<1, 3>

<3, 2>

<2, 4>

<2, 5>

<3, 5>

<4, 6>

<5, 6>

e

0

0

15

19

19

15

29

38

l

17

0

15

27

19

27

37

38

-e

17

0

0

8

0

12

8

0

此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>

第7章  查找

1.选择题

(1)对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为(   )

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

答案:C

解释:总查找次数N=1+2+3+…+n=n(n+1)/2,则平均查找长度为N/n=(n+1)/2

(2)适用于折半查找的表的存储方式及元素排列要求为(   )

 A.链接方式存储,元素无序            B.链接方式存储,元素有序

C.顺序方式存储,元素无序            D.顺序方式存储,元素有序

答案:D

解释:折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

(3)如果要求一个线性表既能较快的查找,又能适应动态变化的要求,最好采用(    )查找法。

A.顺序查找 B.折半查找

C.分块查找 D.哈希查找

答案:C

解释:分块查找的优点是:在表中插入和删除数据元素时,只要找到该元素对应的块,就可以在该块内进行插入和删除运算。由于块内是无序的,故插入和删除比较容易,无需进行大量移动。如果线性表既要快速查找又经常动态变化,则可采用分块查找。

(4)折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中(   )比较大小,查找结果是失败。

A.20,70,30,50                    B.30,88,70,50

C.20,50                            D.30,88,50

答案:A

解释:表中共10个元素,第一次取ë(1+10)/2û=5,与第五个元素20比较,58大于20,再取ë(6+10)/2û=8,与第八个元素70比较,依次类推再与30、50比较,最终查找失败。

(5)对22个记录的有序表作折半查找,当查找失败时,至少需要比较(   )次关键字。

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

答案:B

解释:22个记录的有序表,其折半查找的判定树深度为 ëlog222û + 1=5,且该判定树不是满二叉树,即查找失败时至多比较5次,至少比较4次。

(6)折半搜索与二叉排序树的时间性能(   )。

 A.相同                              B.完全不同        

C.有时不相同                        D.数量级都是O(log2n)

答案:C

(7)分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是(   )。

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)

答案:C

解释:A、B、C、D四个选项构造二叉排序树都以100为根,易知A、B、D三个序列中第一个比100小的关键字为80,即100的左孩子为80,而C选项中100的左孩子为60,故选C。

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

A.LL           B.LR          C.RL          D.RR

答案:C

(9)下列关于m阶B-树的说法错误的是(   )。

A.根结点至多有m棵子树    

B.所有叶子都在同一层次上

C.非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树  

D.根结点中的数据是有序的

答案:D

(10)下面关于B-和B+树的叙述中,不正确的是(   )。

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

C.B-树和B+树都能有效地支持顺序检索 D.B-树和B+树都能有效地支持随机检索

答案:C

(11)m阶B-树是一棵(   )。

A.m叉排序树                        B.m叉平衡排序树  

C.m-1叉平衡排序树                  D.m+1叉平衡排序树

答案:B

(12)下面关于哈希查找的说法,正确的是(   )。        

A.哈希函数构造的越复杂越好,因为这样随机性好,冲突小      

B.除留余数法是所有哈希函数中最好的  

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

D.哈希表的平均查找长度有时也和记录总数有关

答案:C

(13)下面关于哈希查找的说法,不正确的是(   )。              

 A.采用链地址法处理冲突时,查找一个元素的时间是相同的

 B.采用链地址法处理冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的

 C.用链地址法处理冲突,不会引起二次聚集现象

 D.用链地址法处理冲突,适合表长不确定的情况

答案:A

解释:在同义词构成的单链表中,查找该单链表表中不同元素,所消耗的时间不同

(14)设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的元素加到表中,用二次探测法解决冲突,则放入的位置是(   )。

 A.8             B.3              C.5            D.9

答案:D

解释:关键字15放入位置4,关键字38放入位置5,关键字61放入位置6,关键字84放入位置7,再添加关键字49,计算得到地址为5,冲突,用二次探测法解决冲突得到新地址为6,仍冲突,再用用二次探测法解决冲突,得到新地址为4,仍冲突,再用用二次探测法解决冲突,得到新地址为9,不冲突,即将关键字49放入位置9。

(15)采用线性探测法处理冲突,可能要探测多个位置,在查找成功的情况下,所探测的这些位置上的关键字 (    )。

A.不一定都是同义词                  B.一定都是同义词      

C.一定都不是同义词                  D.都相同

答案:A

解释:所探测的这些关键字可能是在处理其它关键字冲突过程中放入该位置的。

2.应用

(1)假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:

 画出描述折半查找过程的判定树;

 若查找元素54,需依次与哪些元素比较?

 若查找元素90,需依次与哪些元素比较?

假定每个元素的查找概率相等,求查找成功时的平均查找长度。

答案:

先画出判定树如下(注:mid=ë(1+12)/2û=6):

30

5            6

3       7       42      87

             4     24       54  72   95

查找元素54,需依次与30, 63, 42, 54 元素比较;

查找元素90,需依次与30, 63,87, 95元素比较;

求ASL之前,需要统计每个元素的查找次数。判定树的前3层共查找1+2×2+4×3=17次;

但最后一层未满,不能用8×4,只能用5×4=20次,

所以ASL=1/12(17+20)=37/12≈3.08

(2)在一棵空的二叉排序树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉排序树。

答案:

12

  1.    12

  2     11       16  21              

   4  9        13

验算方法:  用中序遍历应得到排序结果:2,4,7,9,11,12,13,16,17,21

(3)已知如下所示长度为12的表:(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec

 试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

 若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

 按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

答案:

   

(4)对图7.31所示的3B-树,依次执行下列操作,画出各步操作的结果。

 插入90      插入25     插入45    删除60  

                     

   

(5)设哈希表的地址范围为0~17,哈希函数为:H(key)=key%16。用线性探测法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49),构造哈希表,试回答下列问题:

画出哈希表的示意图;

若查找关键字63,需要依次与哪些关键字进行比较?

若查找关键字60,需要依次与哪些关键字比较

假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

答案:

画表如下:

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

32

17

63

49

24

40

10

30

31

46

47

查找63,首先要与H(63)=63%16=15号单元内容比较,即63与31比较 ,不匹配;

然后顺移,与46,47,32,17,63相比,一共比较了6次!

查找60,首先要与H(60)=60%16=12号单元内容比较,但因为12号单元为空(应当有空标记),所以应当只比较这一次即可。

对于黑色数据元素,各比较1次;共6次;

对红色元素则各不相同,要统计移位的位数。“63”需要6次,“49”需要3次,“40”需要2次,“46”需要3次,“47”需要3次,

所以ASL=1/11(6+2+3×3+6)=23/11

(6)设有一组关键字(901231455208427),采用哈希函数:Hkey=key %7 ,表长为10,用开放地址法的二次探测法处理冲突。要求:对该关键字序列构造哈希表,并计算查找成功的平均查找长度。

答案:

散列地址

0

1

2

3

4

5

6

7

8

9

关键字

14

1

9

23

84

27

55

20

 

 

比较次数

1

1

1

2

 3  

4

1

2

 

 

平均查找长度:ASLsucc=1+1+1+2+3+4+1+2/8=15/8

以关键字27为例:H27=27%7=6(冲突)   H1=6+1%10=7(冲突)

H2=6+22%10=0(冲突)   H3=6+33%10=5   所以比较了4次。

7)设哈希函数H(K)=3 K mod 11,哈希地址空间为010,对关键字序列(321349243821412),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsuccASLunsucc

 线性探测法;

 链地址法。

答案:

散列地址

0

1

2

3

4

5

6

7

8

9

10

关键字

 

4

  

12

49

38

13

24

32

21

 

比较次数

  

1

 

1

1

2

1

2

1

2

 

ASLsucc =1+1+1+2+1+2+1+2/8=11/8

ASLunsucc=1+2+1+8+7+6+5+4+3+2+1/11=40/11

ASLsucc =1*5+2*3)/8=11/8

ASLunsucc=1+2+1+2+3+1+3+1+3+1+1)/11=19/11

目录
相关文章
|
1月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
53 0
数据结构与算法学习十五:哈希表
|
2月前
|
存储 Java Serverless
【数据结构】哈希表&二叉搜索树详解
本文详细介绍了二叉搜索树和哈希表这两种数据结构。二叉搜索树是一种特殊二叉树,具有左子树节点值小于根节点、右子树节点值大于根节点的特点,并且不允许键值重复。文章给出了插入、删除和搜索等方法的具体实现。哈希表则通过哈希函数将键名映射为数组下标,实现快速查找,其插入、删除和查找操作时间复杂度理想情况下为O(1)。文中还讨论了哈希函数的设计原则、哈希冲突的解决方法及哈希表的实现细节。
52 8
【数据结构】哈希表&二叉搜索树详解
|
1月前
|
存储 缓存 Java
【数据结构】哈希表
【数据结构】哈希表
29 1
|
5月前
|
存储 算法
数据结构===图
数据结构===图
|
3月前
|
存储 Java
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
这篇文章通过Java代码示例展示了如何实现哈希表,包括定义结点类、链表类、数组存储多条链表,并使用简单的散列函数处理冲突,以及如何利用哈希表存储和查询学生信息。
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
|
4月前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
【7月更文挑战第12天】图的遍历利器:DFS 和 BFS。Python 中,图可表示为邻接表或矩阵。DFS 沿路径深入,回溯时遍历所有可达顶点,适合找路径和环。BFS 层次遍历,先近后远,解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习,掌握这些算法,图处理将游刃有余。
65 3
|
4月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
41 1
|
5月前
|
存储 NoSQL 算法
redis数据结构—哈希表
redis数据结构—哈希表
54 0
|
5月前
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
|
5月前
|
存储 算法
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
39 0