第八章查找
习题
9．1 判断题(在你认为正确的题后的括号中打√，否则打X)。
(1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。( )
(2)查找成功与否的关键在于是否按主关键字查找。( )
(3)顺序文件必须用一片地址连续的存储空间来存放。( )
(4)只有在顺序存储结构上才能采用顺序查找方法。( )
(7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。( )
(8)建立稠密索引的优点是节省存储空间。( )
(9)分块查找的效率与文件中的记录被分成多少块有关。( )
(10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。( )
(11)B-树和B十树都是用来实现动态索引的。( )
(12)在B-树上可以进行顺序查找。( 1
(13)在B+树上可以进行顺序查找。／ 1
(14)采用散列方法存储线性表，不能存储数据元素之间的关系。( )
(15)在散列文件中进行查找不涉及关键字的比较。( )
(16)散列冲突是指同一个关键字对应了多个不同的散列地址。( )
(17)散列表的负载因子等于存人散列表中的关键字的个数。( )
(18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。( )
(19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。
(20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。( )
9．2单项选择题。
(1)衡量查找算法性能好坏的主要标准是。
A．参加比较的关键字值的多少
B．被查找的关键字值在关键字序列中的位置
C.关键字序列中是否存在被查找关键字值
D．关键字值的平均比较次数的多少
(2)顺序查找方法的优点之一是—。·
A．对于被查找对象几乎没有限制B．适合排序连续顺序文件的查找
C.适合链接顺序文件的查找D．查找时间效率高
(3)对线性表采用折半查找，该线性表必须。
A．元素按值有序排列B．采用顺序结构
C．元素按值有序排列，并且采用顺序存储结构
n元素按值有序排列，并且采用链式存储结构
(4)下面的说法中，不正确的是——。
A．折半查找方法不适用于按值有序链接的链表的查找
B．折半查找方法适用于按值有序的顺序表的查找
C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找
D．折半查找方法适用于排序连续顺序文件的查找
(5)在有序表(k1，k2，…，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。
A．K99 B．k50 C．K49 D．k1
(6)为了实现分块查找，线性表必须采用——结构。
A．顺序存储B．链式存储
C．索引存储D．散列存储
(7)只能在顺序存储结构上才能实现的查找方法是法。
A．顺序查找B．树型查找
C．折半查找D．散列查找
(8)在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录，需要进行——次关键字的比较。
A．0 B．4 C．5 D．15
(9)若在100个记录中查找其中任意一个记录，最多只要比较5次，则所采用的查找方法可能是——。
A．折半查找B．树型查找
C．分块查找D．散列查找
(10)若在n个记录中查找其中任意一个记录至少要比较2次，则所采用的查找方法可能是
A．分块查找B‘折半查找C．树型查找D．散列查找
(11)折半查找过程可以利用一棵称之为判定树的二叉树来描述。在长度为12的序列中进行折半查找对应的判定树的根结点的右孩子的值(某元素在序列中的位置)是——。
A．7 B．8 C．9 D．10
(12)若在序列中采用折半查找方法进行查找，用来描述该查找过程的判定树的形状与——有关。
A．序列中元素的值B．序列中元素的排列次序
C．序列中元素的类型D．序列中元素的个数
(13)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置只能是——。
A．10，15，12，18，19 B．10，15，12，13，14
C．10，15，16，18，19 D．10，15，11，13，14
(14)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置不可能是——。
A．10，5，7，8，9 B．10，5，2，1
C．10，5，6，7，8 D．10，5，7，6
(15)将数据元素2，4，6，8，10，12，14，16，18，20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为——。
A．10，16，12 B．10，12，16 C．4，7，5 D．4，5，7
(16)索引文件中的索引表具有的特点是————。
A．索引项按关键字值有序，并且由用户提供
B．索引项按关键字值有序，并且由系统提供
C．索引项按关键字值无序，并且由用户提供
D．索引项按关键宇值无序，并且由系统提供
(17)m阶B-树中的m是指——。
A．每个结点至少具有m棵子树
B．每个结点最多具有m棵子树
C．分支结点中包含的关键字的个数
D．m阶B-树的深度
(18)下面关于B-树和B+树的叙述中，不正确的是——。
A．B-树和B+树都是平衡的多分树
B．B-树和B+树都可以用于文件的索引结构
D．B—树和B+树都能有效地支持随机检索
(19)下面的命题中，不成立的是。
A．m阶B-树中的每一个分支结点的子树的数量都小于或等于m。
B．m阶B-树中的每一个分支结点的子树的数量都大于或等于m／2上取整
C．m阶B-树中的任何一个结点的子树的深度都相等。
D．m阶B—树中有k个子树的分支结点包含k—1个关键字。
(20)评价散列函数质量好坏的标准是——。
A．函数是否简单B．计算是否快
C．是否是解析式D．函数的取值是否均匀
(21)在一个初始状态为空的散列表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SA T，SUN)，散列函数为H(key)：i％7，其中，i为关键字key的第一个字母在英文字母表中的序号，地址值域为[0：6]，采用线性再散列法处理冲突。
(22)在具有n个元素的序列中进行查找，平均查找长度为O(n)的方法是——。
A．顺序查找方法B．散列查找方法
C．分块查找方法D．树型查找方法
9．3 填空题。
(1)文件的逻辑结构是指——，文件的物理结构是指——。
(2)文件在物理结构中通常有——、——和——三种组织方式。
(3)文件的关键字是——。
(4)文件最基本操作是和。
(5)对线性表采用折半查找方法，该线性表必须采用——存储结构，并且——。
(6)在按值有序的线性表(5，8，11，12，15，20，32，41，57)中采用折半查找法查找20需要进行——次元素间的比较。
(7)具有n个结点的判定树的深度h = ——。
(8)若每个记录的查找概率相等，则在具有n个记录的顺序文件中采用顺序查找法的平均查找长度ASL=——。
(9)在具有n个记录的排序连续顺序文件中采用折半查找法的平均查找长度ASL=？
(10)索引文件的索引表中的一个索引项是——之间的对照关系。
(11)索引文件包括——和——两个部分。
(12)索引表的特点是——，并且——。
(13)在索引文件中查找一个记录的过程是先查——，然后——。
(14)具有144项的表分成——块最好，若每块的最佳长度为8，则平均查找长度为——
(15)在3阶B-树上，每个分支结点包含的子树的数目最多为——，最少为——。
(16)一棵B+树上通常有两个头指针(即查找的人口指针)，其中一个指向——，另一个指向——。
(17)散列函数建立了——之间的对应关系。
(18)设计一个散列表通常应包括三个内容，分别是——、——和——。
(19)一个好的散列函数是指——。处理冲突的方法通常有——、——和——一O
(20)一个待散列存储的线性表为K二(18，25，63，50，42，32，9)，散列函数为H(k)：k％9，则与元素18发生冲突的元素有——个。
9．4 试叙述索引顺序文件与顺序文件相比较的优缺点，指出一种适用于索引顺序文件的
外存设备。
9．5 已知一个长度为12的线性表(Dec，Feb，Nov，Oct，Jul，Sept，Aug,Apr，May,Jun,Jan，Mar)。
(1)按该线性表中元素的顺序构造出一棵二叉排序树；
(2)若每个元素的查找概率均等，查找此二叉排序树中任意一个结点的平均查找长度ASL是多少?
(3)若对线性表的元素按字典顺序从小到大排列以后，再用折半查找方法，则查找其中任意一个元素的平均查找长度ASL是多少?
(4)画出相应的平衡二叉树。
9．6 折半查找过程可以利用一棵判定树来描述。请画出n‘13时的判定树。
9．7 何谓散列冲突?何谓冲突处理?简要说明冲突处理的过程。
9．8 已知散列函数为H(k)二k％7，并采用线性探测再散列方法处理冲突，所建立的散列表如下所示，请依次将关键字17，27填人表中。
9．9 在初始为空的散列表中依次插入以下关键字序列：Jan，Feb，Mar,Apr，May，Jun，Jul，Aug，Sept，Oct，Nov，Dec。散列函数为H(k)：i％p，其中，i为关键字的第一个字母在英文字母表中的序号。请分别画出按以下两种情况构成的散列表：
(1)散列地址空间为[0，12]，p=13，用线性再散列法处理冲突；
(2)散列地址空间为[0，6]，p=7，用链地址法处理冲突。
9．10 在散列函数与散列地址范围都分别相同的前提下，采用链地址法处理冲突比采用开放地址法处理冲突的时间效率要高，为什么?
9．11 已知有长度为M的散列表HT[0，M-1]，散列函数为H(k)，并且采用线性探测再散列方法处理冲突。请写出在该散列表中查找关键字值为key的元素存在与否的算法。若存在，则给出它在表中的位置，否则给出相应的信息。
9．12 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k)，处理冲突的方法为线性再散列法。
9．13 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k)，处理冲突的方法为链地址法。
9．14 已知一长度为n的线性表A和待散列地址空间为[0，m—1)，其中m≥n。若采用除留余数法构造散列函数与步长为根号下N下取整的线性探测再散列法处理冲突，请分别写出建立该散列表和在该散列表上进行查找的算法。
9．15 已知散列函数为H(k)=(3*k)％11，采用线性探测再散列法处理冲突。对下列关键字值序列构造一个散列地址空间为[0，10]的散列表，并求出ASL。
(22，41，53，8，46，30，1，3l，66)
历年考试题
11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（）
A．该中间位置B．该中间位置－1
C．该中间位置＋1 D．该中间位置／2
12．散列文件不能（）
A．随机存取B．索引存取
C．按关键字存取D．直接存取
13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的
平均访问外存次数为（）
A．n/2 B．n
C．n/4 D．log n
10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（）
A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度
C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较
11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）
A．同义词之间发生冲突引起的
B．非同义词之间发生冲突引起的
C．同义词之间或非同义词之间发生冲突引起的
D．散列表“溢出”引起的
12．从外存设备的观点看，存取操作的基本单位是（）
A．逻辑记录B．数据元素
C．文件D．物理记录
13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（）
A．顺序文件B．索引文件
C．顺序索引文件D．散列文件
5、考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上的一切结点的值。
现把9个数1，2，3，…8，9填入下图所示的二叉树的9个结点中，并使之具有上述性
质。此时，n
1的值是＿A＿，n
2
的值是＿B＿，n
9
的值是＿C＿。现欲把101/2放入此树，并
使该树保持前述性质，增加的一个结点可以放在＿D＿或＿E＿。 o n
1
/ \
o n
2 o n
3
/ \ \
o n
4 o n
5
o n
6
/ \ \
o n
7 o n
8
o n
9
供选择的答案
A～C：①1 ②2 ③3 ④4 ⑤5 ⑥6
⑦7 ⑧8 ⑨9
D、E：①n
7下面②n
8
下面③n
9
下面④n
6
下面
⑤n
1与n
2
之间⑥n
2
与n
4
之间⑦n
5
与n
9
之间⑧n
3
与n
6
之间
1、散列法存储的基本思想是根据_A_来决定_B_ , 碰撞 (冲突) 指的是_C_ , _D_越大, 发生碰撞的可能性也越大。处理碰撞的两类主要方法是_E_。
供选择的答案
A 、
B 、D ：①存储地址②元素的序号③元素个数④关键码值
⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间
C ：①两个元素具有相同序号
②两个元素的关键码值不同, 而非码属性相同
③不同关键码值对应到相同的存储地址
④负载因子过大⑤数据元素过多
E ：①线性探查法和双散列函数法②建溢出区法和不建溢出区法
③除余法和折叠法④拉链法和开地址法
(试题1)
如图所示的二叉树，有下列性质：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上一切结点的值。这是一棵__A__树。
现有一菲波那契数列｛a
n ｝,a
=a
1
=1,a
k
=a
k-1
+a
k-2
,k=2,3……。若把｛a
1
,a
2
,……,a
9
}填入
该二叉树，一般可采用__B__遍历法遍历该树上全部结点，得到由结点的值组成的从小到大
顺序排列的序列。对本题给出的二叉树图形填入｛a
1,……,a
9
｝后，其结点n
8
的值为__C__，
根结点的值为__D__。若欲插入｛a
1,……,a
9
｝的平均值，则应该在__E__增加一个结点。
o n
1 / \
o n
2 o n
3
/ \ \
o n
4 o n
5
o n
6
/ \ \
o n
7 o n
8
o n
9
供选择的答案
Ａ：①穿线树②最佳查找树③Ｂ－树④查找树Ｂ：①前序②中序③后序④广度Ｃ：①３②８③21 ④57 Ｄ：①８②21 ③34 ④66
Ｅ：①n
2与n
4
之间②n
6
下③n
５
与n
9
之间④n
9
下
●已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Key mod 7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(11) ；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(12) 。
(11) A、1.5 B、1.7 C、2.0 D、2.3
(12) A、1.0 B、7/6 C、4/3 D、3/2
(试题5 )
在二叉排序树中，每个结点的关键码值__A__，__B__一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序树，最佳二叉排序树在结构上的特点是__C__，__D__不是二叉排序树，__E__是最佳二叉排序树。
供选择的答案
A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小；
②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大；
③比左右子树的所有结点的关键码值大；
④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系。
B：①前序遍历②中序（对称）遍历③后序遍历④层次遍历C：①除最下两层可以不满外，其余都是充满的；
②除最下一层可以不满外，其余都是充满的；
③每个结点的左右子树的高度之差的绝对值不大于1 ；
④最下层的叶子必须在左边。
D、E：如图所示。
①⑤②⑤③⑤
/ \ / \ / \
②⑥②⑧④⑦
/ \ \ / \ / \ / / \
①④⑩①④⑥⑨②⑥⑧
/ / / \ \ / \ \
③⑦③⑦⑩①③⑨
\ \
⑨⑩
/
⑧
④⑤⑤⑤⑥⑦
/ \ / \ / \
④⑨④⑩④⑧
/ / \ / \ ∣ / \ \
②⑦⑩②⑥⑦②⑤⑨
/ \ / \ / \ \ / \ \ \
①③⑥⑧①③⑧①③⑥⑩
\
⑨
24．在含20个关键字的3阶B树（2－3树）上查找一个关键字，至多需要访问___________次外存。
23．动态查找表在开散列表上通常采用_____________来解决冲突问题。
24．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。
25．查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于______________。23．查找表的数据结构有别于线性表、树型结构等，其逻辑结构为________________。24．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为________________。
25．在开散列表上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指________________中查找该结点。
26．文件的检索有顺序存取、________________和按关键字存取三种方式。
25.若要找出所有工资低于1500元，职称是副教授，及所有工资低于2000元，职称是教授的记录，则查询条件是________。
29.在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。
(5) 利用关键码分别为10, 20, 30, 40的四个结点，能构造出（⑧）种不同的二叉搜索树。
28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是
hi = (h(key) + i(key%5+1))%7 0≤i≤6
（1）画出构造所得的散列表；
（2）求出在等概率情况下查找成功时的平均查找长度。
32．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=k mod 6，采用线性探测法解决冲突，要求：（7分）
（1）构造散列表；
（2）求查找数34需要的比较次数。
32．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）
元素下标
比较次数
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。
单元测验4 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）队列是限制在两端进行操作的线性表。 （√）（2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 （×）（3）在链队列上做出队操作时，会改变front指针的值。（√）（4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。 （×）（5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。 （√）（6）链队列在一定范围内不会出现队满的情况。 （×）（7）在循环链队列中无溢出现象。 （×）（8）栈和队列都是顺序存储的线性结构。 （×）（9）在队列中允许删除的一端称为队尾。 （×）（10）顺序队和循环队关于队满和队空的判断条件是一样的。 二．填空题 （1）在队列中存取数据应遵循的原则是先进先出。（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 （3）在队列中，允许插入的一端称为队尾。 （4）在队列中，允许删除的一端称为队首（或队头）。（5）队列在进行出队操作时，首先要判断队列是否为空。 （6）顺序队列在进行入队操作时，首先要判断队列是否为满。 （7）顺序队列初始化后，front=rear= -1 。 （8）解决顺序队列“假溢出”的方法是采用循环队列。（9）循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front == rear 。
（10）链队列LQ为空时，LQ->front->next= NULL 。（11）设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O（n）。 （12）设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0（1）。 （13）在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。 （14）设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间 为MAXLEN，则队满标志为： front==(rear+1)%MAXLEN 。 （15）在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为： front==rear && front !=NULL 。 ( 或front==rear && front <>NULL ) （16）向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。（17）读队首元素的操作不改变（或不影响）队列元素的个数。 （18）设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。 （L= (N＋rear－front)% N=（40＋19－11）% 40=8）（19）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0 。 （20）队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。 三．选择题 （1）队列是限定在（ D ）进行操作的线性表。
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 第八章查找 习题 9．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。( ) (2)查找成功与否的关键在于是否按主关键字查找。( ) (3)顺序文件必须用一片地址连续的存储空间来存放。( ) (4)只有在顺序存储结构上才能采用顺序查找方法。( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。( ) (8)建立稠密索引的优点是节省存储空间。( ) (9)分块查找的效率与文件中的记录被分成多少块有关。( ) (10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。( ) (11)B-树和B十树都是用来实现动态索引的。( ) (12)在B-树上可以进行顺序查找。( 1 (13)在B+树上可以进行顺序查找。／ 1 (14)采用散列方法存储线性表，不能存储数据元素之间的关系。( ) (15)在散列文件中进行查找不涉及关键字的比较。( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。( ) (18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。( ) (19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。 (20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。( ) 9．2单项选择题。 (1)衡量查找算法性能好坏的主要标准是。 A．参加比较的关键字值的多少 B．被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D．关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是—。· A．对于被查找对象几乎没有限制B．适合排序连续顺序文件的查找 C.适合链接顺序文件的查找D．查找时间效率高 (3)对线性表采用折半查找，该线性表必须。 A．元素按值有序排列B．采用顺序结构 C．元素按值有序排列，并且采用顺序存储结构 n元素按值有序排列，并且采用链式存储结构 (4)下面的说法中，不正确的是——。 A．折半查找方法不适用于按值有序链接的链表的查找 B．折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D．折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1，k2，…，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 第1章概述 一、简答题 1．简述以下术语的含义并说明它们之间的关系。 数据类型、数据结构、逻辑结构、存储结构 2．简述算法时间效率和空间效率的概念。 3．简述数据结构课程的目的和意义。 二、选择题 1．以下数据结构中，逻辑结构属于线性结构的是 A）有向图B）链式栈C）二叉树D）二叉排序树 2．下列与数据元素有关的叙述中错误的是 A）数据元素是有独立含义的数据最小单位B）数据元素是描述数据的基本单位C）数据元素可以称做结点D）数据元素可以称做记录 3．设问题的规模为n，分析以下程序段： a=10; b=100; while (b>0) { a++; b- -; } 以上程序段的算法时间复杂度是 A）O(1) B）O(n) C）O(n2) D）O() 三、填空题 1．数据结构包括的三方面内容分别是：数据的[1] 、数据的[2] 和数据的运算。2．数据元素是数据的基本单位，在某些情况下也可以称为[1] 、[2] 和[3] 。3．数据逻辑结构的4种基本形态包括集合结构、[1] 结构、[2] 结构和[3] 结构。 4．一个正确的算法应该具有5个特性：[1] 、[2] 、[3] 、[4] 和[5] 。5．数据的存储结构包括顺序、[1] 、[2] 和[3] 四种。 6．一个数据结构在计算机中的映象称为[1] 。 7．一个算法的效率主要是指该算法的[1] 效率和[2] 效率。 8．以下程序段的时间复杂度T（n）= 。 sum=0; for(i=0 ; i 单元练习8 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）图可以没有边，但不能没有顶点。 （ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。 （ㄨ）（3）邻接表只能用于有向图的存储。 （√）（4）一个图的邻接矩阵表示是唯一的。 （ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。 （ㄨ）（6）有向图不能进行广度优先遍历。 （√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。 （√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。 （ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。 二．填空题 （1）图常用的存储方式有邻接矩阵和邻接表等。 （2）图的遍历有：深度优先搜和广度优先搜等方法。 （3）有n条边的无向图邻接矩阵中，1的个数是 _2n____。 （4）有向图的边也称为 _ 弧___ 。 （5）图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。 （6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。 （7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n2）。 （8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。 （9）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。 （10）设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。 （11）图的逆邻接表存储结构只适用于 __有向____图。 （12） n个顶点的完全无向图有 n(n-1)/2_ 条边。 （13）有向图的邻接表表示适于求顶点的出度。 （14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V i的入度。 （15）对于具有n个顶点的图，其生成树有且仅有n-1 条边。 （16）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e 个结点。 （17）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。 （18）无向图的邻接矩阵一定是对称矩阵。 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 一、单项选择题 1.逻辑关系是指数据元素间的（） 2.A．类型 B．存储方式 C．结构 D．数据项 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构 为( ) A．顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 4.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear 为队尾指针，则执行出队操作后其头指针front值为（）5. A．front=front+1 B．front= (front+1)%(m-1) 6. C．front=(front-1)%m D．front=(fro nt+1)%m 7.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队满的条件为( )。 A．rear％n==front B．(front+l)％n==rear C．rear％n-1==front D．(rear+l)％n==front 8.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队空的条件为( )。 A．rear％n==front B．front+l=rear C．rear==front D．(rear+l)％n=front 9.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。 ( ) 10.A. 90 B. 91 C. 92 D. 93 11.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。 12.A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 13.C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 14.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。 A. n B. 2n C. n/2 D. n*n 15.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利 用（）。 A. 求关键路径的方法 B.求最短路径的方法 C. 深度优先遍历算法 D.广度优先遍历算法 16.对线性表进行二分查找时，要求线性表必须( )。 习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 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) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个 空间数据结构 摘要：空间数据模型和空间数据结构是地理信息系统（GIS）课题的中心内容。本文对空间数据结构的定义、分类进行了一定的研究性的归纳与总结。 关键词：空间数据结构，矢量数据，栅格数据 引言 GIS中空间数据结构和空间数据模型是紧密相关的。数据模型的建立必须通过一定的数据结构，但两者之间也有非常大的区别。数据模型是一个总得概念，是人为概念化的真实，是对现实世界的提取，对现实世界的认识和选择。而数据结构指数据元素之间的相互关系，它是软件常规内涵，根据空间数据结构和数据模型的特点及其关系，可以建立空间数据库系统。 空间数据结构定义 空间数据结构是带有空间数据单元的集合。这些数据单元是数据的基本单 位，一个数据单元可以有几个数据项组成，数据单元之间存在某种联系叫做结构。 所以，研究空间数据结构，是指空间目标间的相互关系，包括几何和非几何的关 系，数据结构是数据模型的表述，数据结构往往通过一系列的图表和矩阵，以及 计算机码的数据记录来说明。 空间数据结构的分类 矢量数据结构 定义 矢量数据结构是基于矢量模型，利用欧几里得(EUCLID)几何学中的点、线、 面及其组合体来表示地理实体的空间分布，是通过记录坐标的方式，尽可能精确 地表示点线多边形等地理实体，自然地理实体的位置是用其在坐标参考系中的空 间位置来定义的，坐标空间设为连续，允许任意位置长度和面积的精确定义，其 特点是定位明显，属性隐含。 GIS采用的矢量数据结构模型，是将空间地质实体抽象成点、线、面三种几 何要素，矢量数据结构通过优化拓扑结构表达空间实体的相关关系，为空间数据 库建立基本框架。 矢量数据结构的特点 优点：数据按照点、线或多边形为单元进行组织，结构简单、直观、易实现 以实体为单位的运算和显示。 缺点： 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D ????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 查找-数据结构练习第八章． 数据结构练习第八章查找 1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 2．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 2A. O(1) B. O(logn) C. O(n) D. O(n) 23．在二叉排序树中插入一个结点的时间复杂度为（）。 2) D. O(n C. O(logn) A. O(1) B. O(n)24．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 A.logn+1 B. logn-1 C. logn D. log(n+1) 22225．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。A. 25 B. 10 C. 7 D. 1 6．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。 21/2) D. O(1og C. O(n B. O(nn) ) A. O(n)27．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 2) C. O(nlogn) D. O(1og A. O(n) B. O(n n)228．（）二叉排序树可以得到一个从小到大的有序序列。 A. 先序遍历 B.中序遍历 C. 后序遍历 D. 层次遍历 9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 A. 1 B. 2 C. 3 D. 4 10．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template数据结构练习8
数据结构实验十一：图实验
数据结构 练习题
中国铁道出版社数据结构(第二版)单元8练习参考答案
数据结构实验---图的储存与遍历
数据结构练习附
数据结构第八章习题及答案
空间数据结构
数据结构实验报告图实验
数据结构-图习题
数据结构实验
数据结构图习题
(完整版)数据结构练习题(含答案)
数据结构 第六章 图 练习题及答案详细解析
数据结构练习第八
数据结构实验报告图实验
相关主题
文本预览