当前位置：文档之家 › 习题9查找及其答案

习题9查找及其答案

  • 格式：pdf
  • 大小：243.56 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

基本逻辑门电路及其应用典型练习题9

基本逻辑门电路及其应用典型练习题9

基本逻辑门电路及其应用典型练习题9注意事项：1．答题前填写好自己的姓名、班级、考号等信息2．请将答案正确填写在答题卡上1．如图所示，试判断这是一个什么逻辑门电路。

A、B、C闭合时记“1”，断开时记“0”，P 灯亮记“1”不亮记“0”，试完成真值表。

【答案】“或”门电路【详解】由图可知，开关A、B、C只要有一个闭合时，灯泡便亮，所以这个电路满足“或”门电路逻辑，即当几个条件中只要有一个或一个以上具备就能出现某一结果，所以这是一个“或”门电路，其真值表：2．如图为包含某逻辑电路的一个简单电路图，L为小灯泡，光照射电阻R'时，其阻值将变得远小于R。

该逻辑电路是__________（选填“与”、“或”或“非”）门电路。

当电阻R'受到光照时，小灯泡L将__________（选填“发光"或“不发光”）。

【答案】非发光【详解】[1][2]该逻辑电路为非门电路，非门电路的特点是输入状态和输出状态相反，当电阻R'受到光照时，其阻值将变得远小于R，则R两端的电势差大，R'两端的电势差小，则输入端为低电势，那么输出端为高电势，小灯泡L发光。

3．如图所示为一个逻辑门的输入端A、B上和输出端Z上的电信号，此逻辑电路为__________门电路，该逻辑门的符号是__________。

【答案】与【详解】[1][2]由图象知输入端都为高电势时，输出端才为高电势，此逻辑电路为与门电路，该逻辑门的符号是4．电子电路中的信号可以分为___________信号和___________信号。

数字信号的两个工作状态可以用“___________”和“___________”来表示。

在数字电路中分别代表___________电压和___________电压。

【答案】 数字 模拟 0 1 低 高【详解】[1][2]电子电路中的信号可以分为数字信号和模拟信号。

[3][4]数字信号的两个工作状态可以用“0 ”和“1”来表示。

传感器应用技能实训习题答案_9

传感器应用技能实训习题答案_9

技能训练九湿度传感器1．填空题（1）湿度传感器是基于某些材料能产生与湿度有关的物理效应或化学反应，将湿度的变化转换成某种电量的变化的器件。

（2）湿度传感器的种类很多，在实际应用中主要有电阻式和电容式两大类。

在湿度传感器的基片上覆盖一层感湿材料制成感湿膜，当空气中的水蒸气吸附在感湿膜上时，基片的电阻率和电阻值发生变化，利用这一特性即可测量湿度。

（3）湿敏电阻是一种电阻值随环境湿度的变化的湿度传感器，它由基片、电极和感湿膜组成。

（4）湿敏电阻传感器的感湿层在吸收了水蒸气之后，引起两个电极之间的电阻率和电阻值发生变化，这样就能直接将湿度变化转换为电阻的变化。

（5）当空气湿度发生改变时，电容式湿度传感器的两个电极间的介电常数发生变化，使得它的电容值也发生变化，电容的变化与相对湿度成正比。

（6）湿度传感器工作电源需要采用交流电源，其原因是以防氯化锂溶液发生电解，导致传感器性能劣化甚至失效。

2．选择题（1）湿敏电阻用交流电作为激励电源是为了（ b ）。

a．提高灵敏度b．防止产生极化及电解作用c．减小交流电桥平衡的难度（2）当空气湿度发生改变时，电容式湿度传感器两个电极间的（ a ）发生变化，使其（ b ）也发生变化。

a．介电常数b．电容量c．电阻值（3）洗手后，将湿手靠近自动干手机，机内的传感器便驱动电热器加热，有热空气从机内喷出，将湿手烘干，手靠近自动干手机能使传感器工作，是因为（ d ）。

a．改变了湿度b．改变了温度c．改变了磁场d．改变了电容（4）相对湿度测量空气中的（ a ）。

a．水蒸气的含量b．气体成分（5）电容式湿度传感器只能测量（ a ）湿度。

a．相对b．绝对c．任意d．水分3．问答题（1）湿敏电阻的基本工作原理是什么？答：当空气中的水蒸气吸附在感湿膜上时，基片的电阻率和电阻值都发生变化，电阻式温度传感器利用这种特性测量湿度。

（2）湿敏电容的基本工作原理是什么？答：空气中的水分子透过多孔金电极被感湿膜吸附，使得两电极间的介电常数发生变化，环境湿度越大，感湿膜吸附的水分子就越多，使湿度传感器的电容量增加得越多，根据电容量的变化可测得空气的相对湿度。

习题第九章查找答案

习题第九章查找答案

第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。

【北京航空航天大学 2000 一、8 （2分）】A． (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) 【南京理工大学1998一、7（2分）】A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/23. 下面关于二分查找的叙述正确的是 ( D ) 【南京理工大学 1996 一、3 （2分）】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储4. 对线性表进行二分查找时，要求线性表必须（ B ）【燕山大学 2001 一、5 （2分）】A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序5．适用于折半查找的表的存储方式及元素排列要求为( D ) 【南京理工大学 1997 一、6 （2分）】A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序 D．顺序方式存储，元素有序6．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减【南京理工大学 1997 一、7 （2分）】7．当采用分快查找时，数据的组织方式为 ( B ) 【南京理工大学 1996 一、7 （2分）】A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同8. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2）C)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

《随机过程及其在金融领域中的应用》习题九答案

《随机过程及其在金融领域中的应用》习题九答案

2、求积分
1
0 tdBt
的均值与方差。
答：
已知，若 X 是非随机的，且
T 0
X
2 s
ds

，则对任何 t
， Yt

t 0
X sdBs
是正态
分布的随机变量。即Yt , 0 t T 是 Gauss 过程。
所以，
t 0
E

X
2 s

ds

t 0
X
2 s
ds

，则 Yt
Mt Xt
dYt dt
aYt
be
1 2
cBt

1 4
c2t
Yt
由此可以证明得： dYt dt
aYt
be
1 2
cBt

1 4
c2t
Yt
（3）
令 Xt Wt ，则 Xt Wt2 ，dXt dWt2 2WtdWt 2 Xt d Xt
d
Xt

2
1 Xt
t 0

a 2
Zs

b 2
e
1 2
cBs

1 4
c2
s

ds
，
Zt
Yt ,Yt Mt Xt
Zt
Mt Xt ,
Xt
Zt Mt
其中 b X ,t ct Dt x, B X ,t E t F t x
当线性随机微分方程的一般形式为：
d

Xt


d
t e2
cos
Bt

大学物理课后习题答案整理(杨晓峰版)-习题9-15答案

大学物理课后习题答案整理(杨晓峰版)-习题9-15答案

习题9-15解答：
解：基本思路：带电体产生的电场不具有应用高斯定理求解电场强度的对称性，不能直接应用高斯定理求解。

但通过补偿法可使电荷分布球对称。

具体做法是假设球形空腔内同时均匀充满体密度为ρ和ρ−的电荷，原带电体产生的电场等效于电荷体密度为ρ的大均匀带电球体产生的电场和电荷体密度为ρ−的小均匀带电球产生的电场的叠加，此时大带电球体和小带电球体产生的电场分别关于自己的球心呈球对称分布，可用高斯定理求解。

计算过程：应用高斯定理0
1
d i
q
ε∑∫∫i E S =
，
大带电球体内部有 31041d 32
1r E4r ρππε∫∫i E S ==
大带电球体在其内部任一点产生的电场强度为 1
031ρεr E =
小带电球体在其内部任一点产生的电场强度为 2
32ρε−r E = 小带电球体在其外部产生的电场满足
3
014d 32
33r E 4r ρππε−∫∫i E S ==
小带电球体在其外部产生的电场强度为3
0333
33
r r ρε−E =r 球心O ′处，1'10033O d ρρεε=
=E r i ，02O'E =，该点电场强度为 '1'0
3O O d ρε==E E i 球体内P 点处的电场强度为
3333
13122
000004(3333(2)34P P P 333r r r d d r d d ρρρρρεεεεε−+=−=−E =E E r r i +i =i。

测量学习题及其参考答案9-

测量学习题及其参考答案9-

习题91．如何根据建筑方格网进行建筑物的定位放线?为什么要没置轴线桩?1．建筑方格网一般是精心测量的矩形控制网，可根据建筑方格网点坐标和建筑物定位点的设计坐标，用直角坐标法测设建筑物轴线交点，详见第8章直角坐标法内容。

由于建筑物定位后，轴线交点位置在基础开挖时被挖掉，所以在基础开挖前，应把轴线交点桩位引测到施工范围以外适当地方，作为基础基槽开挖后各阶段施工中确定轴线位置的依据。

2．对柱子安装测量有何要求?如何进行校正?2．要求保证柱子平面和高程位置符合设计要求，柱身铅直。

预制钢筋混凝土柱子插人杯形基础的杯口后，柱子三面的中心线与杯口中心线对齐吻合，并固定。

使用严格检验校正的经纬仪在整平后，在柱轴线两个互为垂直方向上安置经纬仪进行校正，先用十字丝竖丝瞄准柱子根部的中心线，制动照准部，缓缓抬高望远镜，观察柱子中心线偏离纵丝的方向，指挥工作人员用钢丝绳拉直柱子，直至从两台经纬仪中观测到的柱子中心线从下而上都与十字丝纵丝重合为止。

3．如何控制吊车梁安装时的中心线位置和高程?3．吊车梁安装时根据柱子上所画±0.000标志的高程，用水准测量方法进行控制，以使修平或加垫牛腿面，保证吊车梁顶面的标高应符合设计要求。

吊车梁安装时的中心线应与牛腿面上的中心线对齐，一般按设计数据在地面上定出吊车梁中心线的两端点，打大木桩标志。

然后用经纬仪将吊车梁中心线投测到每个柱子的牛腿面的侧边上，并弹以墨线。

4．建筑施工测量中的主要问题是什么?目前常用哪些方法?4．建筑物施工测量中的主要问题是轴线投测，保证建筑物轴线正确，控制垂直度。

目前常用有外控法和内控法。

其次是高程控制，保证建筑物标高正确，目前常用有水准测量法，悬吊钢尺法和钢尺直接丈量法。

5．简述建筑物沉降观测的目的和方法。

5．沉降观测的目的是保证工程建筑物在施工、使用和运行中的安全，以及为建筑设计积累资料。

沉降观测的方法有：以水准测量方法为主，也可用光电测距三角高程方法。

金属学与热处理课后习题答案9

第九章钢得热处理原理91 金属固态相变有哪些主要特征？哪些因素构成相变得阻力？答:固体相变主要特征:1、相变阻力大2、新相晶核与母相晶核存在一定得晶体学位向关系。

3、母相中得晶体学缺陷对相变其促进作用。

4、相变过程中易出现过渡相。

相变阻力构成:1、表面能得增加。

2、弹性应变能得增加,这就是由于新旧两相得比体积不同,相变时必然发生体积得变化,或者就是由于新旧两相相界面得不匹配而引起弹性畸变,都会导致弹性应变能得增加。

3、固态相变温度低,原子扩散更困难,例如固态合金中原子得扩散速度为107—108cm/d,而液态金属原子得扩散速度为107 cm/s。

92 何谓奥氏体晶粒度？说明奥氏体晶粒大小对钢得性能影响？答:奥氏体晶粒度:就是奥氏体晶粒大小得度量。

当以单位面积内晶粒得个数或每个晶粒得平均面积与平均直径来描述晶粒大小时,可以建立晶粒大小得概念。

通常采用金相显微镜100倍放大倍数下,在645mm2范围内观察到得晶粒个数来确定奥氏体晶粒度得级别。

对钢得性能得影响:奥氏体晶粒小:钢热处理后得组织细小,强度高、塑性好,冲击韧性高。

奥氏体晶粒大:钢热处理后得组织粗大,显著降低钢得冲击韧性,提高钢得韧脆转变温度,增加淬火变形与开裂得倾向。

当晶粒大小不均匀时,还显著降低钢得结构强度,引起应力集中,容易产生脆性断裂。

93 试述珠光体形成时钢中碳得扩散情况及片、粒状珠光体得形成过程？答:珠光体形成时碳得扩散:珠光体形成过程中在奥氏体内或晶界上由于渗碳体与铁素体形核,造成其与原奥氏体形成得相界面两侧形成碳得浓度差,从而造成碳在渗碳体与铁素体中进行扩散,简言之,在奥氏体中由于碳得扩散形成富碳区与贫碳区,从而促使渗碳体与铁素体不断地交替形核长大,直至消耗完全部奥氏体。

片状珠光体形成过程:片状珠光体就是渗碳体呈片状得珠光体。

首先在奥氏体晶界形成渗碳体晶核,核刚形成时与奥氏体保持共格关系,为减小形核得应变能而呈片状。

渗碳体长大得同时,使其两侧得奥氏体出现贫碳区,从而为铁素体在渗碳体两侧形核创造条件,在渗碳体两侧形成铁素体后,铁素体长大得同时造成其与奥氏体体界面处形成富碳区,这又促使形成新得渗碳体片。

实验室安全知识习题 (9)多选

A.伤处不能用手抚摸，也不能用水洗涤
B.不作处理，直接就医
C.轻伤可以涂紫药水、红药水、碘酒等
D.必要时可用消炎药粉涂抹，用绷带包扎
参考
答案:
C,D
14
6
1." [多选题]下面哪组溶剂属易燃类液体（闪点在25℃以下）
A.甲醇、乙醇
B.四氯化碳、乙酸丁酯、石油醚
C.丙酮、甲苯
D.异丙醇、二甲苯
参考
答案:
C.使用个体防护设备(护目镜、面罩、个体呼吸保护用品或其他防溅出保护设备)
D.用过的工作服应先在实验室中消毒，然后统一洗涤或丢弃
参考
答案:
A,B,C
14
4
3." [多选题]超级恒温水浴内的加热用水一定要使用
A.去离子水
B.蒸馏水
C.自来水
参考
答案:
A,B
14
4
4." [多选题]化学危险药品对人身会有刺激眼睛、灼伤皮肤、损伤呼吸道、麻痹神经、燃烧爆炸等危险，一定要注意化学药品的使用安全，应做到下列哪项?
A,B,C,D
14
7
3." [多选题]对于大多数目的，下列哪些组合可以确保正确装载的高压灭菌器的灭菌效果：
A.134℃、3min
B.126℃、10min
C.121℃、15min
D.115℃、25min
参考
答案:
A,B,C,D
14
7
4." [多选题]过氧化酸、硝酸铵、硝酸钾、高氯酸及其盐、重铬酸及其盐、高锰酸及其盐、过氧化苯甲酸、五氧化二磷等强氧化剂，在适当条件下可放出氧发生爆炸，在使用这类强氧化性化学试剂时，应注意什么：
A.用干净的毛巾擦拭

金属学与热处理课后习题答案9

第九章钢的热处理原理9-1 金属固态相变有哪些主要特征？哪些因素构成相变的阻力？答：固体相变主要特征：1、相变阻力大2、新相晶核与母相晶核存在一定的晶体学位向关系。

3、母相中的晶体学缺陷对相变其促进作用。

4、相变过程中易出现过渡相。

相变阻力构成：1、表面能的增加。

2、弹性应变能的增加，这是由于新旧两相的比体积不同，相变时必然发生体积的变化，或者是由于新旧两相相界面的不匹配而引起弹性畸变，都会导致弹性应变能的增加。

3、固态相变温度低，原子扩散更困难，例如固态合金中原子的扩散速度为10-7—10-8cm/d，而液态金属原子的扩散速度为10-7 cm/s。

9-2 何谓奥氏体晶粒度？说明奥氏体晶粒大小对钢的性能影响？答：奥氏体晶粒度：是奥氏体晶粒大小的度量。

当以单位面积内晶粒的个数或每个晶粒的平均面积与平均直径来描述晶粒大小时，可以建立晶粒大小的概念。

通常采用金相显微镜100倍放大倍数下，在645mm2范围内观察到的晶粒个数来确定奥氏体晶粒度的级别。

对钢的性能的影响：奥氏体晶粒小：钢热处理后的组织细小，强度高、塑性好，冲击韧性高。

奥氏体晶粒大：钢热处理后的组织粗大，显著降低钢的冲击韧性，提高钢的韧脆转变温度，增加淬火变形和开裂的倾向。

当晶粒大小不均匀时，还显著降低钢的结构强度，引起应力集中，容易产生脆性断裂。

9-3 试述珠光体形成时钢中碳的扩散情况及片、粒状珠光体的形成过程？答：珠光体形成时碳的扩散：珠光体形成过程中在奥氏体内或晶界上由于渗碳体和铁素体形核，造成其与原奥氏体形成的相界面两侧形成碳的浓度差，从而造成碳在渗碳体和铁素体中进行扩散，简言之，在奥氏体中由于碳的扩散形成富碳区和贫碳区，从而促使渗碳体和铁素体不断地交替形核长大，直至消耗完全部奥氏体。

片状珠光体形成过程：片状珠光体是渗碳体呈片状的珠光体。

首先在奥氏体晶界形成渗碳体晶核，核刚形成时与奥氏体保持共格关系，为减小形核的应变能而呈片状。

渗碳体长大的同时，使其两侧的奥氏体出现贫碳区，从而为铁素体在渗碳体两侧形核创造条件，在渗碳体两侧形成铁素体后，铁素体长大的同时造成其与奥氏体体界面处形成富碳区，这又促使形成新的渗碳体片。

第9章习题及其答案

题 9-12 图
9-13 已知题图 9-13 所示的凸轮机构，在图上标出以下各项：1）画出基圆半径 ro；2）
标出从动件图示位置的位移 s、凸轮转角δ 和压力角α ；3）当δ = 900 时，标出从动件位移 s′ 和压力角α ′ 。
ω1 题图 9-13
α=0 °
F,v
δ=90 °
s
δ 69°
ro
F,v
答：不可行。因为推杆偏置的大小，方向的改变会直接影响推杆的运动规律，而原凸轮 机构推杆的运动规律应该是不允许擅自改动的。
9-6 用作图法求出题图 9-6 所示两凸轮机构从图示位置转过 45°时的压力角。
45° ω
ω
（a）
（b）
题图 9-6
解：用反转法原理，从动件以- ω 方向例转 45°，即为凸轮转动 45°时与从动件的相对
B'
α
s
O O' B
B s
K''
α'
δ' o
B'
K
δ
o'
B''
K'
α'
题图 9-15-1
9-16 在题图 9-16 示的凸轮机构中，圆弧底摆动推杆与凸轮在 B 点接触。当凸轮从图示 位置逆时针转过 90º 时，试用图解法标出：(1)推杆在凸轮上的接触点；(2)摆杆位移角的大 小；(3)凸轮机构的压力角。
速一绰减速回剧运动规律； ϕ4 ~ 2π 段为停歇段。补足线题图 9-9-1。
9-9 如题图 9-9 中给出了某直动推杆盘形凸轮机构的推杆的速度线图。要求：
（1）定性地画出其加速度和位移线图；
（2）说明此种运动规律的名称及特点（v、a 的大小及冲击的性质）； （3）说明此种运动规律的适用场合。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

p i ci
i 1
n
4. log2(n+1)，O(log2n) 6. 1，3 8. (n/s+s)/2+1 10. 小于，大于 12. 查找成功，左子树，右子树 14. O(nlog2n) 16. 5 18. n/m
三、应用题 1. 折半查找判定树如图 7-3 所示，平均查找长度等于 29/10。图 7-3 中的结点与有序表中元 素的对应关系如下表所示。 5 2 1 3 4 6 9 8 7 10
4. H(K)=K % 11，哈希表如图 7-5 所示，平均查找长度 17/12。 0 ∧
图 7-5
四、算法设计题 1. 设计思路：进入判别算法之前，pre 取初值为 min(小于树中任一结点值)，fail=FALSE, 即认为 bt 是二叉排序树。按中序遍历 bt，并在沿向根结点，与前趋比较，若逆序，则 fail 为 TRUE,则 bt 不是二叉排序树。
二、填空题 1. 以顺序查找方法从长度为 n 的顺序表或单链表中查找一个元素时，平均查找长度为 ________，时间复杂度为________。 2. 对长度为 n 的查找表进行查找时，假定查找第 i 个元素的概率为 pi,查找长度（即在 查找过程中依次同有关元素比较的总次数） 为 ci， 则在查找成功情况下的平均查找长度的计 算公式为________。 3. 假定一个顺序表的长度为 40，并假定查找每个元素的概率都相同，则在查找成功情 况下的平均查找长度________，在查找不成功情况下的平均查找长度________。 4. 以折半查找方法从长度为 n 的有序表中查找一个元素时，平均查找长度约等于 ________的向上取整减 1，时间复杂度为________。 5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的 ________表。 6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找 43 和 56 元素时，其比较次数 分别为________和________。 7. 假定对长度 n=50 的有序表进行折半查找，则对应的判定树高度为________，最后一 层的结点数为________。 8. 假定在索引查找中，查找表长度为 n，每个子表的长度相等，设为 s，则进行成功查 找的平均查找长度为____________。 9. 在索引查找中，假定查找表（即主表）的长度为 96，被等分为 8 个子表，则进行索 引查找的平均查找长度为________。 10. 在一棵二叉排序树中， 每个分支结点的左子树上所有结点的值一定________该结点 的值，右子树上所有结点的值一定________该结点的值。 11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。 12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 _______，若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的 值，则继续向________查找。 13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结 点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。 14. 根据 n 个元素建立一棵二叉排序树的时间复杂度大致为________。 15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超 过________。 16. 假定对线性表(38,25,74,52,48)进行哈希存储，采用 H(K)=K % 7 作为哈希函数， 采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。 17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用 H(K)=K % 7 作为哈希函数， 采用线性探测法处理冲突，则平均查找长度为________。 18. 在线性表的哈希存储中，装填因子又称为装填系数，若用 m 表示哈希表的长度， n 表示线性表中的元素的个数，则等于________。 19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用 H(K)=K % 9 作为哈希 函数，则哈希地址为 0 的元素有________个，哈希地址为 5 的元素有________个。 三、应用题 1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)， 试画出对应的折 半查找判定树，求出其平均查找长度。 2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序
图 7-3
1 15
2 26
3 34
4 39
5 45
6 56
7 58
8 63
9 74
10 76
2. 二叉排序树如图 7-4 所示，平均查找长度等于 32/10。 38 25 16 30 68 54
图 7-4
52 74 90 72
3. H(K)=K % 13 平均查找长度为 14/10，其余解答如下。 元素 初始哈希地址 最终哈希地址 0 1 哈希表 2 32 75 29 63 48 94 25 46 18 70 6 10 3 11 9 3 12 7 5 5 6 10 3 11 9 4 12 7 5 8 3 4 5 6 7 8 9 10 11 12 29 94 18 32 46 70 48 75 63 25
{ if (low<high) else { mid=(low+high)/2; if (k= =st.elem[mid].key) else if (k<st.elem[mid].key) else } } //search-bin return (st,k,low,mid-1); return(st,k,mid+1,high); return (mid) ; //成功 return (0); //不成功
{ } } }
pre=bt->data_key; bisorttree(bt->rchild,pre,fail); //判断右子树
} //bisorttree
2.
说明：较为直观的方法，可套用中序遍历非递归算法。 int search_bin(SeqTable st , keytype k , int low , int high)
3
4
5
6
7
8
9 10 11 12
习题 9 参考答案
一、单项选择题 1. D 2. A 3. B 4. C 5. D 6. D 二、填空题 1. (n+1)/2, O(n) 3. 5. 7. 9. 11. 13. 15. 17. 19. 20.5, 41 顺序 有序 6， 19 11 有序序列 左子树，右子树 1 2 3， 2 2. 7. A 8. C 9. A 10. A 11.找每个元素的概率相等，则在长度为 n 的顺序表上查找任一元素的平均查找长 度为( )。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2. 对于长度为 9 的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找 长度为( )的 9 分之一。 A. 20 B. 18 C. 25 D. 22 3. 对于长度为 18 的顺序存储的有序表，若采用折半查找，则查找第 15 个元素的比较 次数为( )。 A. 3 B. 4 C. 5 D. 6 4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元 素 26 的比较次数为( )。 A. 2 B. 3 C. 4 D. 5 5. 对具有 n 个元素的有序表采用折半查找，则算法的时间复杂度为( )。 2 A. O(n) B. O(n ) C. O(1) D. O(log2n) 6. 在索引查找中，若用于保存数据元素的主表的长度为 n，它被均分为 k 个子表，每个 子表的长度均为 n/k，则索引查找的平均查找长度为( )。 A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+1 7. 在索引查找中，若用于保存数据元素的主表的长度为 144，它被均分为 12 子表，每 个子表的长度均为 12，则索引查找的平均查找长度为( )。 A. 13 B. 24 C. 12 D. 79 8. 从具有 n 个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致 为( )。 2 A. O(n) B. O(1) C. O(log2n) D. O(n ) 9. 从具有 n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为 ( )。 2 A. O(n) B. O(1) C. O(log2n) D. O(n ) 10. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( )。 A. -11 B. -22 C. 12 D. 01 11. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用 h(K)=K%13 计算哈希 地址，则元素 64 的哈希地址为( )。 A. 4 B. 8 C. 12 D. 13 12. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表， 采用 h(K)=K%7 计算哈希地 址，则哈希地址等于 3 的元素个数( )。 A. 1 B. 2 C. 3 D. 4 13. 若根据查找表建立长度为 m 的哈希表，采用线性探测法处理冲突，假定对一个元素 第一次计算的哈希地址为 d，则下一次的哈希地址为( )。 A. d B. d+1 C. (d+1)/m D. (d+1)%m
void bisorttree(bitree bt,keytype pre, bool &fail) { //fail 初值为 FALSE，若非二叉序树，则 fail 值 TRUE if (!fail) { if (bt) { bisosrttree(bt->lchild,pre,fail); if (bt->data_key<pre) else //判断左子树 fail=TRUE;