第八章查找
查找
一．选择题
1．若查找每个元素的概率相等，则在长度为n 的顺序表上查找到表中任一元素的平均查找长度为_____________。
A. n
B. n+1
C. (n-1)/2
D. (n+1)/2
分析：本题主要考查顺序表的平均查长度的计算，在等概率下，
ASLsucc=nP1+(n-1)P2+……+2Pn-1 +Pn=[n+(n-1)+ ……+1]/n = (n+1)/2，其中：Pi 为查找第i 个元素的概率。所以答案为D。
2．折半查找的时间复杂度_____________。
A.Ｏ(n*n)
B.Ｏ(n)
C. Ｏ(nlog2n)
D. Ｏ(log2n)
分析：本题考查折半查找的基本思想和对应的判定树。因为对n 个结点的
线性表进行折半查找，对应的判定树的深度是 log2n +1，折半查找的过程就是走了一条从判定树的根到末端结点的路径，所以答案为D。
3．采用分块查找时，数据的组织方式为_____________。
Ａ. 把数据分成若干块，每块内数据有序
Ｂ. 把数据分成若干块，块内数据不必有序，但块间必须有序，每块内
最大(或最小)的数据组成索引表
Ｃ. 把数据分成若干块，每块内数据有序，每块内最大(或最小)的数据
组成索引表
Ｄ. 把数据分成若干块，每块(除最后一块外)中的数据个数相等
分析：本题主要考查分块查找的数据组织方式特点。在分块查找时，要求
块间有序，块内或者有序或者无序。这样，在查找记录所在的块时，可以
采用折半查找。所以答案为B。
4．二叉排序树的查找效率与二叉排序树的(1)
有关，当(2)
时，
查找效率最低，其查找长度为n。
(1) Ａ.高度Ｂ.结点的个数Ｃ.形状Ｄ.结点的位
置
(2) Ａ.结点太多Ｂ.完全二叉树Ｃ.呈单叉树Ｄ.结点的结
构太复杂
分析：本题主要考查二叉排序树的查找效率与二叉排序树形存在一定的关系。当二叉排序树的前 log2n 层是满二叉树时，其查找效率最高，其查找长度最大为 log2n +1；当二叉排序树呈单叉树时，其查找效率最低，其查找长度最大为n，此时相当于顺序查找。所以答案为(1)C，(2)C。
5．在一棵AVL 树(平衡二叉树)中，每个结点的平衡因子的取值范围是
_____________。
A. -1～1
B. -2～2
C. 1～2
D. 0～1
分析：本题主要考查AVL 树中的平衡因子定义，平衡二叉树中的每个结点
的平衡因子的取值为：-1，0，1。所以答案为A。
6．向一棵AVL 树(平衡二叉树)插入元素时，可能要对最小不平衡子树进行调整，此调整分为_____________种旋转类型。
A. 2
B. 3
C. 4
D. 5
分析：本题主要考查AVL 树的平衡旋转操作，其操作具体分为LL 型平衡旋转、LR 型平衡旋转、RL 型平衡旋转和RR 型平衡旋转四种类型。所以答案
为C。
7．关于m 阶B-树的说法正确的是_____________。
①.每个结点至少有两棵非空子树。
②.每个结点至多有m-1 个关键字。
③.所有叶子结点都在同一层上。
④.当插入一个元素引起一个结点分裂后，树的高度将增加一层。
Ａ. ①②③Ｂ. ②③Ｃ. ②③④Ｄ. ③
分析：本题主要考查m 阶B-树的定义。当根为叶子结点时，它就没有非空
子树；m 阶B-树的每个结点中的关键字个数在「m/2 -1 和m-1 之间；所有叶子结点都在同一层上，并且不带信息；当插入一个元素引起一个结点分
裂后，树的高度可能增加，也可能不增加。所以答案为B。
8．5 阶B-树中, 每个结点最多有_____________个关键字。
A. 2
B. 3
C. 4
D. 5
分析：本题主要考查B-树的定义。m 阶B-树的每个结点中的关键字个数最
多为m-1，最少为「m/2 -1。对5 阶B-树而言，结点最多为5-1=4 个。所以答案为C。
9．在一棵高度为h 的B-树中，插入一个新关键字时，为查找插入位置需访问_____________个结点。
A. h-1
B. h
C. h+1
D. h+2
分析: 本题主要考查B-树的查找运算。因为插入关键字总是在树的末端结
点进行，因此从B-树的树根开始到达树的末端结点共需访问h 个，所以答
案为B。
10．设哈希地址空间为0～m-1，k 为记录的关键字，哈希函数采用除留余
数法，即Hash(k) = k % p，为了减少发生冲突的频率，一般取p 为
_____________。
A. m
B. 小于或等于m 的最大质数
C. 大于m 的最小质数
D. 小于等于m 的最大合数
分析：在除留余数法中，从理论分析和试验结果证明p 应取小于存储区容
量的质数，因此答案为B。
11．对包含n 个元素的哈希表进行查找，平均查找长度_____________。
A. 为O(log2n)
B. 为O(n)
C. 与n 无关
D. 与α(装填因子)
有关
分析: 本题主要考查哈希查找的特点。在静态和动态查找中，平均查找长
度与n 有关。而对哈希表而言，一旦确定了哈希函数和处理冲突的方法，
其平均查找长度只与装填因子α有关。所以答案为D。
12．关于哈希查找的说法正确的是_____________。
Ａ. 除留余数法是最好的
Ｂ. 哈希函数的好坏要根据具体情况而定
Ｃ. 删除一个元素后，不管用哪种方法处理冲突，都只需简单地把该
元素删除即可
Ｄ. 因为冲突是不可避免的，所以装填因子越小越好
分析：本题主要考查哈希查找的基本思想。不存在最好的哈希函数，哈希
函数的好坏要根据具体情况而定；删除一个元素后，都要对该单元进行标
记,以免在查找与该关键字同义词的记录时引起查找错误；装填因子越小，
平均查找长度越小，但系统的开销越大。答案为B。
13．设哈希表长12，哈希函数为H(key)=key % 11,用二次探测法处理冲突，
表中已有元素的关键字为15,38,61,84，现要把关键字为49 的元素插入表
中，其插入位置是________。
Ａ.8 Ｂ.３Ｃ.５Ｄ.9
分析：本题主要考查哈希函数的二次探测处理冲突的方法。因为15，38，
61，84 已依次存放在第4、5、6、7 的位置上了，又H(49)=49 % 11 = 5，
冲突，加1 或减1 后仍然冲突，加4 后为9，不冲突，所以答案为D。14．若有m 个关键字互为同义词，若用线性探测法处理冲突，把这m 个元
素存入哈希表中，至少要进行_____________次探测．
Ａ. m-1 B. m C. m+1 D. m(m+1)/2
分析：本题主要考查哈希函数的冲突解决方法。第1 个元素要探测1 次，
第2 个元素要探测 2 次，……，第m 个元素要探测m 次，m 个元素则共要探测1+2+……+m=m(m+1)/2 次。所以答案为D。
二．判断题
1．进行折半查找的表必须是顺序存储的有序表。
正确
分析：本题考查折半查找的基本思想。只有符合有序的特点，才能根据比
较的结果判断要查找的记录所在的区间；只有符合顺序存储的特点，才便
于修改查找区间的上、下界。
2．折半查找所对应的判定树是一棵平衡二叉树。
正确
分析: 本题考查折半查找的基本思想和平衡二叉树的定义。折半查找所对
应的判定树上的任何结点,其左子树和右子树的深度差最大为1，所以是一
棵平衡二叉树。
3．对二叉排序树进行先序遍历得到的结点的值的序列是一个有序序列。
错误
分析: 本题考查二叉排序树的定义和二叉树的遍历。由二叉排序树的定义
可知,左子树上任何结点的值都小于其根结点的值，右子树上任何结点的值
都大于或等于其根结点的值，所以中序遍历得到的结点的值的序列才是一
个有序序列, 先序遍历得到的结点的值的序列不是一个有序序列。
4．在由n 个元素组成的有序表上进行折半查找时，对任一个元素进行查找
的长度都不会大于log2n+1。
正确
分析: 本题考查折半查找的判定树。因为其判定树的深度为 log2n +1,所以
对任一个元素进行查找的长度都不会大于log2n+1。
5．对于同一组记录，若生成二叉排序树时插入记录的次序不同，则可得到
不同结构的二叉排序树。
正确
分析：本题考查二叉排序树的定义和构造方法。因为在构造二叉排序树时，
首先把第1 个元素作为根，以后再插入时，把小于根结点的元素插入到左
子树上，把大于或等于根结点的元素插入到右左子树上。可以看出：对同
一组记录，以不同元素为根构造的二叉排序树其结构是不同的。
6．在分块查找中，在等概率情况下，其平均查找长度不仅与查找表的长度有关，而且与每块中的记录个数有关。
正确
分析：本题考查分块查找的平均查找长度。若用顺序查找确定记录所在的块，则分块查找的平均查找长度为ASL=(n/S+S)/2 + 1；若用折半查找确定
记录所在的块，则分块查找的平均查找长度为ASL≈log2(n/S+1)+ S/2(其
中：n 为线性表的长度，S 为一块中的元素个数)
7．哈希函数越复杂，随机性越好，冲突的概率越小。
错误
分析:本题考查哈希函数的优劣。不能一概而论，哈希函数应根据不同的问
题做出不同的选择。
8．在二叉排序树中插入的结点，总是叶子结点。
正确
分析: 本题考查二叉排序树的插入操作方法。在二叉排序树中插入的结点，总是叶子结点,这是二叉排序树最大的优点。
9．在一棵非空二叉排序树中，删除一个结点后，又将其插入，所得到的二叉排序树与原树形状相同。
错误
分析:本题考查从二叉排序树中删除结点的基本思想。在删除一个结点后,
剩余部分要保证仍是一棵二叉排序树,可能要对其进行调整,所以再将其插
入后,其树的结构就可能发生变化。
10．向一棵平衡二叉树插入一个结点后，必然引起树的不平衡。
错误
分析：本题考查平衡二叉树的定义和在平衡二叉排序树中插入结点的基本
思想。对一棵平衡二叉树而言，若一个结点S 的平衡因子为1，把一个结点插入到S 的右子树中，此时S 的平衡因子为0，该树仍然是平衡的。三．填空题
1．在n 个元素的线性表中顺序查找，若查找成功，则关键字的比较次数最多为
____________次；使用监视哨时，若查找失败，则关
键字的比较次数为
次。
答案：n n+1
分析：这里只讨论关键字的比较，在算法的具体实现中，前者比较不只n 次，因为每次还必须检查下标是否正确。
2．在线性表(5,12,19,21,37,56,65,75,80,88,92)中，用折半查找法查找
关键字为85 的记录，关键字的比较次数为
次，所比较的元素
依次为
。
答案：3 56 80 88
分析：本题考查折半查找的基本思想。对折半查找而言，从它的判定树可
以知道关键字的比较次数以及所比较的元素。如图8.2 所示。
图8.2 判定树
3．假定对长度n = 100 的线性表进行分块查找，并假定每块的长度均为10，每个记录的查找概率相等。若索引表和块内都采用顺序查找，则平均查找
长度为
；若索引表采用折半查找，块内采用顺序查找，则
平均查找长度约为
。
答案：11 9
分析：本题主要考查分块查找的平均查找长度。当索引表和块内都采用顺
序查找时，平均查找长度ASL=(n/S+S)/2 +1=(100/10+10)/2 + 1 = 11；当
索引表采用折半查找，块内采用顺序查找时，平均查找长度ASL≈
log2(n/S+1)+S/2=log2(100/10+1)+10/2 ≈9。(其中n 为线性表的长度，S
为每块中的元素个数)
4．在哈希查找中，装填因子为 ，若用m 表示哈希表的长度，n 表示哈希
存储的元素个数，则 等于
。
答案：n / m
分析：本题主要考查装填因子的概念。设哈希表的空间大小为m，存储的结
点总数为n，则称α=n/m 为哈希表的装填因子。
5．在一棵m 阶B-树中，若在某结点中插入一个关键字而引起该结点分裂，
则该结点中原有关键字个数为
；若删除一个关键字后引起
结点合并，则该结点中原有关键字个数为
。
答案：m-1 「m/2 -1
分析：本题主要考查B-树的定义。因为m 阶B-树中每个结点中的关键字个56
19
80
5
21
65
88
12
37
75
92
数在「m/2 -1 与m-1 之间，所以，在插入一个关键字而引起该结点分裂时，该结点中原有的关键字个数应为m-1，在删除一个关键字而引起结点合并
时，该结点中原有的关键字个数应为「m/2 -1。
6．动态查找和静态查找的主要区别在于前者包含有__________和
__________运算，而后者不包含这两种运算。
答案：插入删除
分析：本题主要考查动态查找与静态查找的主要区别。
7．顺序查找时，存储方式应是__________；折半查找时，要求线性表是
__________；分块查找时，要求线性表__________；哈希查找时，要求线性表的存储方式是__________。
答案：顺序存储或链式存储顺序存储且有序
顺序存储且块间有序
哈希存储
8．下面是二叉排序树的查找算法描述，请在划线处填上适当的句子。Typedefstruct node {
Keytype key;
Itemtypeotherinfo;
struct node *lchild, *rchild;
}bstnode，*BSTree;
BSTreeBSTSearch(BSTree BST, KeyType k) /*在二叉排序树BST 中查找
*/
{ BSTree p; /* 关键字为K的记录*/
P=BST;
while (____(1)
____)
{ if ( k
____(2)__
__；
else
p=p->rchild;
}
return(p);
}
答案：(1)p != NULL && p->key!=k (2)p=p->lchild;
分析：(1)处为控制条件，所以应填p != NULL && p->key!=k；(2)搜索p
的左孩子，所以应填p=p->lchild。
本函数返回空表示查找失败，否则返回的是关键字K 所在结点的地址。四．应用题
1．在哈希方法中, 用线性探测法处理冲突时，删除一个记录后，应做哪些后继工作，为什么？
分析与解答：删除一个记录后，把该记录对应的标志位置“删除”，以便在访问与该记录有同义词的记录时能正常进行；
2．若对有n 个元素的有序表和无序表进行顺序查找, 试就下列三种情况分别讨论，两者在相等的查找概率时的平均查找长度是否相同?
(1) 查找失败;
(2) 当表中无相同的关键字时，查找成功；
(3) 当表中有若干个相同的关键字时，要求一次查找，找出所有满足条
件的记录，查找成功。
分析与解答：
(1) 不同。在有序表查找中, 当找到比要查找关键字大(或小)的记录时就
停止查找，不必查找到表尾；而无序表必须查找到表尾才能断定查找是否
失败。因此在无序表中的查找长度大。
(2) 相同。查找到表中记录的关键字等于给定值时就停止查找，其平均查
找长度都是(n+1)/2。
(3) 不同。设表长为n，关键字为K 的记录有m 个。在有序表中，关键字相等的记录相继排列在一起，只要查找到第一个就可以连续查找到其它关键
字相同的记录，所以当要查找所有关键字为K 的记录时，其查找长度为
(n+1)/2+(m-1)，一般地，m< 必须查完整个表中记录, 所以此时的查找长度为n。 3．假定一个线性序列为(30，25，40，18，27，36，50，10，32，45 )， 按此序列中的元素顺序生成一棵二叉排序树，并求出在该二叉排序树上查 找成功时的平均查找长度。 分析与解答：二叉树的建立过程则是不断执行元素插入操作的过程，直到 序列中的元素插完为止。该二叉排序树建树过程如图8.3 所示： 图8.3 二叉排序树的建树过程示意图 查找成功时的平均查找长度ASLsucc=(1+2*2+3*4+4*3)/10=29/10=2.9 4．设有序顺序表中的元素依次为(017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908)。 (1) 试画出对其进行折半查找的判定树, 并计算查找成功时的平均查找长 度和查找不成功的平均查找长度。 30 25 40 30 25 30 40 30 25 18 40 30 25 18 27 40 30 25 18 27 36 30 25 18 27 36 40 50 30 25 18 27 36 40 50 10 30 25 18 27 36 40 50 10 32 30 25 18 27 36 40 50 10 32 45 (2) 要查找元素553，需依次比较哪几个元素？ (3) 要查找元素480，需依次比较哪几个元素？ 分析与解答： (1) 折半查找的判定树如图8.4 所示。 图8.4 判定树 查找成功时的平均查找长度：ASLsucc=(1*1 + 2*2 + 3*4 + 4*7)/14 = 45/14 查找不成功时的平均查找长度：ASLunsucc=(3*1 + 4*14)/15 = 59/15 (2) 由图8.4 所示的判定树可知，查找553 则需要与关键字509，677，533 比较，需比较3 次。 (3) 由图8.4 所示的判定树可知，查找480 则需要与关键字509，154，275，503 比较，需比较4 次。 5．对下面的关键字集合{30,15,21,40,25,26,24,20,31}，若哈希表的装填 因子为0.75，采用除留余数法和线性探测法处理冲突， (1) 设计哈希函数； (2) 画出哈希表； 509 154 677 017 275 553 897 094 170 503 512 612 765 908 (3) 计算查找成功和查找失败时的平均查找长度； 分析与解答：由于装填因子α=0.75，元素个数n=9，则表长m= 9/0.75=12。 (1) 用除留余数法，取哈希函数为H(key)=key % 11 。 (2) 首先计算出各个关键字的哈希地址，然后填入哈希表(表8-1 所示)中。H(30)=30 % 11 = 8 H(15)=15 % 11 = 4 H(21)=21 % 11 = 10 H(40)=40 % 11 = 7 H(25)=25 % 11 = 3 H(26)=26 % 11 = 4 (冲突) H1(26)=((26 % 11)+1)% 12 =5 H(24)=24 % 11 = 2 H(20)=20 % 11 = 9 H(31)=31 % 11 = 9 (冲突) H1(31)=((31 % 11)+1)% 12 = 10 (还冲突) H2(31)=((31 % 11)+2)% 12 = 11 表8-1 哈希表 哈希 地址0 1 2 3 4 5 6 7 8 9 10 11 关键 字24 25 15 26 40 30 20 21 31 比较 次数1 1 1 2 1 1 1 1 3 (3) 查找成功时的平均查找长度：ASLsucc=(1+1+1+2+1+1+1+1+3)/9 = 12/9 =4/3 要计算查找失败时的平均查找长度，根据构造表时设定的处理冲突的方 法找“下一地址”，直到哈希表中某个位置为“零”时，其哈希地址为 i(0≤i≤m-1)时的比较次数。本例中m=12，当哈希地址i=0，1，6 时， 其单元为空，故查找失败时的平均查找长度： ASLunsucc=(1+1+5+4+3+2+1+6+5+4+3+2)/12 = 37/12 6．设哈希函数为H(key)=key % 11,处理冲突的方法为链接法，试将下列关 键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到哈希表中(画 出哈希表的示意图)，并计算查找成功和查找失败时的平均查找长度。 分析与解答：首先计算出各个关键字的哈希地址，然后填入哈希表中(如图8.5 所示)。 H(35)=35 % 11 = 2 H(67)=67 % 11 = 1 H(42)=42 % 11 = 9 H(21)=21 % 11 = 10 H(29)=29 % 11 = 7 H(86)=86 % 11 = 9 H(95)=95 % 11 = 7 H(47)=47 % 11 = 3 H(50)=50 % 11 = 6 H(36)=36 % 11 = 3 H(91)=91 % 11 = 3 图8.5 用链地址法处理冲突的哈希表 查找成功时的平均查找长度：ASLsucc=(1*7+2*3+3*1)/11 = 16/11 查找不成功时的平均查找长度：ASLunsucc=(1*4+2*4+3*2+4*1)/11 = 22/11 = 2 (假设空指针比较也算一次)。 7．设有一个关键字的输入序列{ 55, 31, 11, 37, 46, 73, 63, 02, 07 }, (1) 从空树开始构造平衡二叉树, 画出每加入一个新结点时二叉树的形 态。若发生不平衡, 则指出需做的平衡旋转的类型及平衡旋转的结 果。 (2) 计算该平衡二叉树在等概率下的查找成功和查找不成功的平均查找 长度。 分析与解答：平衡二叉树的建树过程如图8.6 所示。 图8.6 二叉平衡树的建树过程示意图 查找成功时的平均查找长度：ASLsucc=(1*1+2*2+3*4+4*2)/9 = 25/9 查找不成功时的平均查找长度：ASLunsucc=(4*4+3*6)/10 = 34/10 8．图8.7 是一个3 阶B-树。试分别画出在插入65、15、40、30 之后B-树的变化情况。 分析与解答：B-树的插入操作首先是查找待插入的结点，再把关键字插入 到该结点中，具体可分为两种情况：(1) 若该结点中关键字的个数小于m-1，则插入即可；(2) 若该结点中关键字的个数大于或等于m-1，则插入后将引 起结点的分裂。这时需把结点分裂为两个，并把中间的一个关键字取出来 放到该结点双亲结点中去。若双亲结点中原来关键字的个数也是m-1，则需要再分裂。如果一直分裂到根结点，则需建立一个新的根结点，整个B-树 增加一层。具体解答过程如图8.8( a，b，c，d)所示。 图8.7 3 阶B-树 插入65 后： 55 55 31 55 31 11 55 31 11 11 31 55 37 LL 55 37 11 31 46 55 37 11 31 46 55 37 11 31 46 73 LR RR 55 37 11 31 46 73 55 37 11 31 46 73 63 55 37 11 31 46 73 63 RL 11 31 46 63 02 55 37 73 07 11 31 46 63 02 55 37 73 07 LR 80 90 45 60 70 25 35 50 85 95 55 (a)插入65 后的B-树插入15 后： (b)插入15 后的B-树插入40 后： (c)插入40 后的B-树插入30 后： 45 25 35 50 85 95 55 80 60 70 65 90 50 85 95 55 80 60 70 65 90 15 35 25 45 50 85 95 55 80 60 70 65 90 15 25 45 35 40 (d)插入30 后的B-树 图8.8 B-树的插入过程示意图 五．算法设计题 1．若把二叉排序树的定义修改成:二叉排序树或是一棵空树，或是一棵具 有下列性质的二叉树：若左子树不空，则左子树结点的值都小于根结点的值；若右子树不空，则右子树结点的值都大于或等于根结点的值；它的左 右子树也分别是二叉排序树。即允许树中有相同关键字的结点存在。编程 求出二叉排序树中关键字等于k 的结点个数。 分析：首先找到第一个等于k 的结点p，由定义可知，其它等于k 的结点都应在p 的右子树上，所以在继续查找的过程中，若当前结点等于k，则向右查找，否则向左查找，直到末端结点为止。 设结点的结构定义如下： typedefstruct node { KeyType key; Itemtypeotherinfo; struct node *lchild, *rchild; }BSTnode; typedefBSTnode *BSTree; 45 35 80 55 30 40 65 90 25 50 85 95 60 70 15 非递归算法描述如下： intBSTsearch(BSTree BST, KeyType k) /*返回等于k 的元素个数*/ { BSTree p; int count=0; p=BST; while(p!= NULL && p->key!=k ) { if(k p=p->lchild; /*查找左子树*/ else p=p->rchild; /*查找右子树*/ } if(p==NULL) return(count); /*当P 为NULL 时，查找失败,返回0*/ else { count=count+1; p=p->rchild; /*查到第一个等于k 的结点*/ } while(p!=NULL ) if(p->key==k) { count=count+1; p=p->rchild; /*继续向右下方查找*/ } else p=p->lchild; /*p->key≠k,意味着k 继续查找左孩子*/ return(count); /*结束,返回关键字为k 的结点的个数*/ } 2．在双向链表的有序表中实现顺序查找。链表的头指针为head, p 是搜索指针,可以从p 指示的结点出发沿任一方向进行。试编写一个函数search(head, p, k)，查找具有关键字k 的结点。 分析：假设有如图8.9 所示的双向链表。在双向有序表中进行顺序查找, 从p结点开始和给定的关键字k比较, 若k>p->data, 则应向右查找, 反之应 向左查找; 当搜索到头部或尾部时, 查找失败.向右查找出现k 或者向左查找出现k>p->data 时也失败。在此算法中链表的头指针head 没有用到。 图8.9 双向链表 结点定义如下： typedefstructdbnode{ DataType data; structdbnode *prior: structdbnode *next; }Dblinklist; 算法描述如下： Dblinklist *Search(Dblinklist *p, DataType k) /*在双向链表（非循环）中查找k，找不到返回NULL，否则返回关键字为k 的结点指针*/ { Dblinklist q; head p 10 20 30 40 50 60 ∧ 70 ∧ q=p; /*q 为搜索指针*/ if(k { while((q!=NULL) && (k q=q->prior; /*向左搜索*/ } else { while((q!= NULL) && (k>q->data)) q=q->next; /*向右搜索*/ } if((q!= NULL) && (q->data==k)) return(q); else return(NULL); } 3. 写一算法，判断一棵二叉树是否是一棵二叉排序树。 分析：由二叉排序树的定义知，若按中序遍历二叉排序树，必得到一个非递减序列。因此本题的设计思想是按中序遍历二叉树，若得到的是一个非递减序列，则该二叉树一定是二叉排序树。所以，只要在二叉树中序遍历算法的基础上修改一下即可。 其结点定义同算法设计题1，有关栈的定义和操作见第3 章。 算法一、用非递归描述如下： typedefintKeyType; intIs_bst(BTree t) { BTree p=t; KeyType pre=minval; /*minval为机器所能表示的最小值*/ PSeqStack s; s=Init_SeqStack( ); /*栈初始化*/ while(p||!Empty_SeqStack(s)) { if(p) { Push_SeqStack(s,p); /*p 进栈,并搜索其左子树*/ p=p->lchild; } else { Pop_SeqStack(s,&p); /*退栈*/ if(p->key else { pre=p->key; p=p->rchild; /*搜索其右子树*/ } } } return(1); /* 是二叉排序树*/ } 算法二、用递归描述如下： typedefintKeyType; KeyType pre; /* pre 表示当前结点的前驱关键字，是全局变量，初始值为机器所能表示的最小值*/ intIs_bst(BTree t) { if (!t) return 1; /*空树为排序树*/ if (Is_bst(t->lchild) /*如果左子树是排序树*/ if (t->key) /*如果当前结点的关键字大于左子树最后遍历到的 关键字*/ { pre=t->key return (Is_bst(t->rchild)); } return 0; } 4. 试用递归方法写一个在二叉排序树中插入结点的算法。假设其根结点 的指针为bst, 插入结点的指针为s。 分析：设其根结点的指针为bst, 插入结点的指针为s。若bst为空树， 则s 作为根结点插入，算法结束。否则, 若s 等于根结点，说明结点已存在，无需插入，算法结束。若s 小于根结点，则插入到左子树中；若s 大于根结点，则插入到右子树中。插入左子树或插入右子树的方法与插入整个二叉排序树的方法相同。 递归算法如下: voidInsertBST(BSTree *bst, BSTree s) { if (*bst==NULL) { s->lchild=NULL; /*s 作为根结点插入*/ s->rchild=NULL; *bst=s; return ; } else { if((*bst)->key==s->key) return; else if(s->key<(*bst)->key ) insertBST((*bst)->lchild,s); /*插入左子树 */ else insertBST((*bst)->rchild,s); /*插入右子树 */ } } 5. 设用线性探测法处理冲突，每个单元设有一标志位flag，当flag==empty 时，表示单元 为空；当flag==used 时,表示单元在使用；当flag==deleted 时，表示记 录已被删除。写出在哈希表中查找、插入、删除运算的算法。 分析：在哈希表中查找时，首先要根据给定的关键字K 计算出哈希地址i，若该单元为空，即HT[i].flag==empty，则查找失败；若HT[i].key==K， 则查找成功；若该单元的记录已被删除(即HT[i].flag==deleted)或 flag==used 并且HT[i].key≠K，则要把i 加1，继续比较，直到查找成功 或找到一个空单元(即查找失败)为止。 插入记录时，首先要根据给定的关键字K 计算出哈希地址i，对每一个 地址i，做下列工作：若HT[i].flag==empty，则把记录放置在单元HT[i] 中，并置标志位为used；若HT[i].flag==used，则要判断该记录是否是要 插入的记录，若是，无需插入；若HT[i].flag==deleted，则要记住第一次 碰到的标志为deleted 的单元地址,以备在循环结束后插入用。经n 次循环后，若仍找不到标志为empty 或deleted 的单元，则插入失败。 删除记录时，首先要根据给定的关键字K 计算出哈希地址i，若 HT[i].flag==empty，则无要删除的记录；若HT[i].flag==used，且 HT[i].key==K，则删除该记录，并置标志位为deletd；若HT[i].flag==used， 且HT[i].key≠K 或HT[i].flag==deleted，则i 加1，继续比较，直到找 到要删除的记录或找到一个标志为empty 的单元为止。 为了便于阅读,在以下三个算法中,关于标志flag的语句并非严格的C语 言语句。若读者上机实验则需做相应修改。 记录类型定义如下: typedefstruct{ KeyType key; OtherTypeotherinfo; MarkType flag; }RecType 查找算法描述如下： intHsearch(RecType HT[],int m, KeyType K) /*在长度为m 的表中查找 关键字为K 的记录*/ { i=Hash(K); /*求哈希地址*/ if(HT[i].flag==empty) return(-1); /*查找失败*/ else if(HT[i].flag==used && HT[i].key==K) return(i); /*查找 成功*/ else { j=(i+1)% m; while((j!=i) && (HT[j].flag!=empty)) /*继续查找*/ { if((HT[j].flag==used) && (HT[j].key==K)) return(j); /*查找成功*/ j=(j+1)% m; } return(-1); /*查找失败*/ } } 插入算法描述如下： intHinsert(RecType HT[],int m, KeyType K) /*在长度为m 的表中插入 关键字为K 的记录*/ { i=Hash(K); /*求哈希地址*/ j=i; t=-1; /*t记住第一次碰到的标志为deleted的单元的地址*/ do { if(HT[j].flag==used) { if(HT[j].key==K) return(-1); /*要插入的记录已 存在*/ else j=(j+1)% m; } else if(HT[j].flag==deleted) { if(t<0) t=j; j=(j+1)% m; } else { HT[j].key=K; /*找到一个标志为empty 的单 元，插入*/ HT[j].flag=used; return(j); } }while(i!=j); if(t>=0) { HT[t].key=K; /*插入到第一个标志为deleted 的单元中*/ HT[t].flag=used; return(t); } else return(-1); /*哈希表已满，插入失败*/ } 删除算法如下： inthdelete(RecType HT[],int m, KeyType K) /*在长度为M 的表中删除关键字为K 的记录*/ { i=Hash(K); /*求哈希地址*/ if(HT[i].flag==empty) return(-1); /*无要删除的记录*/ if((HT[i].flag==used) && (HT[i].key==K)) { HT[i].flag=deleted; /*删除*/ return(i); } else { j=(i+1)% m; while((j!=i) && (HT[j].flag!=empty)) /*继续查找*/ { if((HT[j].flag==used) && (HT[j].key==K)) { HT[j].flag=deleted; /*删除*/ return(j); } j=(j+1)% m; } return(-1); /*无要删除的记录*/ } } 数据结构课程（本科）第七章试题 一、单项选择题 1.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为 （）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概 率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（）。 A. 5.5 B. 5 C. 39/8 D. 19/4 3.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索 第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（）。 A. 5/3 B. 2 C. 7/3 D. 4/3 4.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度 为（）。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 5.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 6.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向下取整加一。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（） 的值除以9。 A. 20 B. 18 C. 25 D. 22 8.对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（）。 A. 3 B. 4 C. 5 D. 6 9.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。 A. n B. log2n C. (h+1)/2 D. h+1 11.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为 （）。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 《统计学》第八章课后练习题 8.4 解：由题意知，μ=100，α=0.05，n=9＜30，故选用t统计量。经计算得：x =99.9778，s=1.2122， 进行检验的过程为： H0:μ=100 H1:μ≠100 t= s n = 1.21229 =?0.0549 当α= 0.05，自由度n-1= 8，查表得tα2（8）=2.3060，因为t< tα2，样本统计量落在接收域，所以接受原假设H0，即打包机正常工作。 用P值检测，这是双侧检验，故： P=2×1?0.5215=0.957，P值远远大于α，所以不能原假设H0。 8.7 解：由题意知，μ=225，α=0.05，n=16＜30，故选用t统计量。 经计算得：x =241.5，s=98.7259， 进行检验的过程为： H0:μ≤225 H1:μ>225 t= s n = 98.725916 =0.6685 当α= 0.05，自由度n-1= 15，查表得tα（15）=2.1314，这是一个右单侧检验，因为t 即元件平均寿命没有显著大于225小时。 用P值检测，这是右单侧检验，故： P=1?0.743=0.257，P值远远大于α，所以不能拒绝原假设H0。 8.9, 解：由题意得 σA2=632，σB2=572，x A=1070，x B=1020，n A=81，n B=64，故选用z统计量。 进行检验的过程为： H0:μA?μB=0 H1: μA?μB≠0 Z=A B A B σA A +σB B = 632+572 =5 当α=0.05时，zα2=1.96，因为Z＞zα2，所以拒绝原假设H0,，即A、B两厂生产的材料平均抗压强度不相同。 用P值检测，这是双侧检验，故： P=2×1?0.9999997=0.0000006，P值远远小于α，所以拒绝原假设H0， 8.13 解：建立假设为： H0: π1=π2 H1: π1≠π2 由题意得： 统计学复习笔记 第七章参数估计 一、思考题 1．解释估计量和估计值 在参数估计中，用来估计总体参数的统计量称为估计量。估计量也是随机变量。如样本均值，样本比例、样本方差等。 根据一个具体的样本计算出来的估计量的数值称为估计值。 2．简述评价估计量好坏的标准 （1）无偏性：是指估计量抽样分布的期望值等于被估计的总体参数。 （2）有效性：是指估计量的方差尽可能小。对同一总体参数的两个无偏估计量，有更小方差的估计量更有效。 （3）一致性：是指随着样本量的增大，点估计量的值越来越接近被估总体的参数。 3．怎样理解置信区间 在区间估计中，由样本统计量所构造的总体参数的估计区间称为置信区间。置信区间的论述是由区间和置信度两部分组成。有些新闻媒体报道一些调查结果只给出百分比和误差（即置信区间），并不说明置信度，也不给出被调查的人数，这是不负责的表现。因为降低置信度可以使置信区间变窄（显得“精确”），有误导读者之嫌。在公布调查结果时给出被调查人数是负责任的表现。这样则可以由此推算出置信度（由后面给出的公式），反之亦然。 4．解释95%的置信区间的含义是什么 置信区间95%仅仅描述用来构造该区间上下界的统计量（是随机的）覆盖总体参数的概率。也就是说，无穷次重复抽样所得到的所有区间中有95%（的区间）包含参数。 不要认为由某一样本数据得到总体参数的某一个95%置信区间，就以为该区间以的概率覆盖总体参数。 5．简述样本量与置信水平、总体方差、估计误差的关系。 1. 估计总体均值时样本量n 为 （z 2 ）2 2其中： E z n n E22 其中： E z 2 n 2. 样本量n 与置信水平1- α、总体方差、估计误差E之间的关系为与置信水平 成正比，在其他条件不变的情况下，置信水平越大，所 第一章 研究对象：城市地理学主要研究在不同地理环境下城市形成、发展、组合分布和空间结构变化规律。 研究内容：（1）城市形成发展条件研究； （2）区域的城市空间组织研究；城市化、城镇体系、城市分类 （3）城市内部空间组织研究；城市功能分区、土地利用、社会空间、行为空间、市场空间等 （4）可持续发展研究 （5）新方法、新技术应用和新领域的研究GPS、RS、GIS 主要任务：P2 第二章 名词解释 都市区：它是一个大的人口核心以及与这个核心具有高度的社会经济一体化倾向的邻接社区的组合，一般以县作为基本单位。有中心县和外围县两部分组成。 大都市带：由连成一体的许多都市区组成，它们在经济、社会、文化等各方面活动上存在着密切的交互作用的巨大的城市地域复合体叫做大都市带。 城镇：镇和城市的总称。 城镇与乡村的区别 ⑴城镇是以从事非农业活动的人口为主的居民点，在产业构成上不同于乡村； ⑵城镇人口聚集规模大； ⑶城镇比乡村有较大的人口密度、建筑密度，景观上不同于乡村； ⑷城镇有便利的市政和公共服务设施，物质构成上不同乡村； ⑸职能上有别于乡村。 城市：商代货币的使用大大促进了商品经济的发展，为了经营上的方便，市逐渐被吸引到人口比较集中，又是奴隶主贵族居住的城中，并有固定的位置，真正意义上的城市才产生。经国家批准设有市建制的城镇称为城市。具有一定人口规模，并以非农业人口为主的居民集居地，是聚落的一种特殊形态。 第三、四、五章 名词解释 城市地理位置：是城市及其外部的自然、经济、政治等客观事物在空间上的结合。 规模经济：指某一生产企业，只有达到一定的生产规模后，才有可能生产收入大于生产成本，逐步达到经济合理的原则，但当生产规模超过某一最高限度后，生产成本又可能上升，以致超过生产收入，达到无利润可得，并要亏本得地步。 集聚经济：是指各种产业和经济活动在空间上集中后产生得经济效果和向心力，促使城市发展;当集中程度超过某一限度后，再集聚会带来不经济，产生离心力，需抑制或减小城市规模。 城市化：城市化是一个地域空间过程，包括区域范围内城市数量的增加和每一个城市地域的扩大两个方面。是城市对农村影响的传播过程；是全社会人口接受城市文化的过程； 是人口集中的过程，包括集中点的增加和每个集中点的扩大；是城市人口占全社会人口比例提高的过程。 推拉因模式：由于城市工业的发展提供了大量就业机会，把农村人口拉了进来，成为城市化“拉因”；由于乡村破产使乡村人口大量涌进城市，造成城市人口膨胀，成为城市化的“推因”。 统计学基础第八章相关与回归分析 【教学目的】 1.掌握相关系数的测定和性质 2.明确相关分析与回归分析的特点 3.建立回归直线方程，掌握估计标准误差的计算 【教学重点】 1.相关关系、相关分析和回归分析的概念 2.相关系数计算 3.回归方程的建立和依此进行估计和预测 【教学难点】 1.相关分析和回归分析的区别 2.相关系数的计算 3.回归系数的计算 4.估计标准误的计算 【教学时数】 教学学时为8课时 【教学内容参考】 第一节相关关系 一、相关关系的含义 宇宙中任何现象都不是孤立地存在的，而是普遍联系和相互制约的。这种现象间的相互联系、相互制约的关系即为相关关系。 相关关系因其依存程度的不同而表现出相关程度的差别。有些现象间存在着严格的数据依存关系，比如，在价格不变的条件下销售额量之间的关系，圆的面积与半径之间的关系等等，均具有显著的一一对应关系。这些关系可由数学中的函数关系来确切的描述，因而也可以认为是一种完全相关关系。有些现象间的依存关系则没有那么严格。当一种现象的数量发生变化时，另一种现象的数量却在一定的范围内发生变化，比如身高与体重的关系就是如此。一般来说，身高越高， 体重越重，但二者之间的关系并非严格意义上的对应关系，身高1.75米的人，对应的体重会有多个数值，因为影响体重的因素不只身高而已，它还会受遗传、饮食习惯等因素的制约和影响。社会经济现象中大多存在这种非确定的相关关系。 在统计学中，这些在社会经济现象之间普遍存在的数量依存关系，都成为相关关系。在本章，我们主要介绍那些能用函数关系来描述的具有经济统计意义的相关关系。 二、相关关系的特点 1.现象之间确实存在数量上的依存关系 如果一个现象发生数量上的变化，则另一个现象也会发生数量上的变化。在相互依存的两个变量中，可以根据研究目的，把其中的一个变量确定为自变量，把另一个对应变量确定为因变量。例如，把身高作为自变量，则体重就是因变量。 2.现象之间数量上的关系是不确定的 相关关系的全称是统计相关关系，它属于变量之间的一种不完全确定的关系。这意味着一个变量虽然受另一个（或一组）变量的影响，却并不由这一个（或一组）变量完全确定。例如，前面提到的身高和体重之间的关系就是这样一种关系。 三、相关关系的种类 现象之间的相互关系很复杂，它们涉及的变动因素多少不同，作用方向不同，表现出来的形态也不同。相关关系大体有以下几种分类： (一)正相关与负相关 按相关关系的方向分，可分为正相关和负相关。当两个因素（或变量）的变动方向相同时，即自变量x值增加（或减少），因变量y值也相应地增加（或减少），这样的关系就是正相关。如家庭消费支出随收入增加而增加就属于正相关。如果两个因素（或变量）变动的方向相反，即自变量x值增大（或减小），因变量y值随之减小（或增大），则称为负相关。如商品流通费用率随商品经营的规模增大而逐渐降低就属于负相关。 (二)单相关与复相关 按自变量的多少分，可分为单相关和复相关。单相关是指两个变量之间的相关关系，即所研究的问题只涉及到一个自变量和一个因变量，如职工的生活水平与工资之间的关系就是单相关。复相关是指三个或三个以上变量之间的相关关系，即所研究的问题涉及到若干个自变量与一个因 第9章查找自测卷姓名班级 一、填空题（每空1分，共10分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结 点数为；比较四次查找成功的结点数为；平均查找长度为。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n 第八章教学 第一节教学概述 一、教学概念—— 教学是教师和学生共同组成的传递和掌握社会经验的双边活动，是实施全面发展教育的基本途径。 教学的内涵；“教学”和“智育”的区别 教学与智育是两个相互关联而又有区别的概念。至于是全面发展教育的重要组成部分，是以向学生传授知识和发展学生智力为主要目标的活动，而教学则是实施智育及其他各育的基本途径。智育的实施除通过教学外，还有课外活动等。概括地说，教学和智育的关系是教育的途径和内容之间的关系。 二、教学的作用和地位 1.教学的主要作用 （1）教学对社会发展的作用 （2）教学对个体发展的作用 （3）教学是实现全面发展教育的基本途径 2.教学在学校中的地位 （1）教学是学校的中心工作 （2）教学不是唯一的活动 三、教学的任务 （1）使学生掌握系统的现代科学文化基础知识，形成基本技能、技 巧（基本任务） （2）发展学生智力，培养学生的能力和创造力 （3）发展学生体力，促进学生的健康 （4）培养学生科学的世界观、高尚的思想品德、健康的审美情绪和良好的心理素质 第二节教学过程 一、教学过程的特点和阶段 1.教学过程的本质特点 （1）教学过程是一种特殊的认识过程，具体表现在：知识的间接性；教师的指导性；教学的发展性；教学的教育性。 （2）教学过程是以认识过程为基础，促进学生全面发展的过程 2.教学过程的基本阶段（凯洛夫提出的五阶段） （1）激发学习动机 （2）感知教材 （3）理解教材 （4）巩固知识 （5）运用知识 二、教学过程的基本规律 1.间接经验与直接经验相结合规律 （1）以间接经验为主是教学活动的主要特点 （2）学习间接经验要与获得直接经验相结合 （3）坚持直接经验与间接经验相统一 2.教师主导作用与学生主体作用相统一的规律 （1）教师在教学活动中起主导作用 （2）学生是学习活动的主体 （3）坚持教师主导与学生主体相统一 3.掌握知识与发展智力相统一规律 （1）传授知识与发展智力是互相促进相互影响的 （2）知识和智力是有区别的，要是知识的掌握真正促进智力的发展是有条件的 （3）贯彻掌握知识和发展智力相统一的规律 4.传授知识与思想品德教育相统一规律（教学的教育性规律）（1）知识是思想品德形成和发展的基础 （2）学生思想品德的提高和发展又为他们积极地学习知识奠定了基础 （3）坚持传授知识和思想品德教育相统一 第三节教学原则 一、教学原则概述 1.教学原则的定义—— 教学原则是有效的进行教学必须遵循的基本要求。贯彻教学原则，正 习题八查找 一、单项选择题 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的链中有（）个 一．单项选择题 1、用于测定两个变量之间密切程度的方法是（D ）。 A、定性判断 B、相关表 C、相关图 D、相关系数 2、产品产量与单位成本的相关系数是—，单位成本与利润率的相关系数是，产量与利润的相关系数是，因此（C）。 A、产量与利润的相关程度最高 B、单位成本与利润率的相关程度最高 C、产量与单位成本的相关程度最高 D、无法判断哪对变量的相关程度最高 3、相关系数的取值范围是（D ）。 A、0≤r≤1 B、-1≤r≤0 C、r＞0 D、-1≤r≤1 4、变量x与y之间的负相关是指（C ）。 A、x值增大时y值也随之增大 B、x值减少时y值也随之减少 C、x值增大时y值随之减少，或x值减少时y值随之增大 D、y的取值几乎不受x取值的影响 5、两个变量之间的相关关系称为（ B ）。 A、复相关 B、单相关 C、曲线相关 D、直线相关 6、、正方形的边长与周长的相关系数为（A ）。 A、1 B、-1 C、0 D、无法计算 7、在一元线性回归方程中，回归系数b的含义是( B )。 A、当x=0时，y的平均值 B 、当x 变动一个单位时，y 的平均变动数额 C 、当x 变动一个单位时，y 增加的总数额 D 、当y 变动一个单位时，x 的平均变动数额 8、常用的求解一元线性回归方程的方法是( B )。 A 、相关系数法 B 、最小平方法 C 、误差绝对值最小法 D 、误差和最小法 9、下列回归方程与相关系数的对应式中，错误的是（ C ） A 、89.0,5.2170?-=-=r x y B 、94.0,8.35?-=--=r x y C 、78.0,5.036?-=+=r x y D 、98.0,9.25?=+-=r x y 10、已知变量x 与y 线性相关，x 与y 的协方差为-60，x 的方差为64，y 的方差为去100，则二者的相关系数的值为（ B ）。 A 、 B 、 C 、 D 、 11、已知变量x 与y 高度线性相关，x 与y 的协方差为-60，x 的方差为64，y 的方差为去100，则建立的y 依x 回归方程中的回归系数b 的值为（ B ）。 A 、 B 、 C 、 D 、 12、若相关系数为正值，则回归系数的值（ B ）。 A 、为负 B 、为正 C 、视a 的符号而定 D 、不能确定 13、回归估计标准误差是说明（ C ）的指标。 A 、平均数代表性 B 、现象之间相关程度 C 、回归直线代表性 D 、抽样误差平均程度 9.1 (1)无序表：顺序查找不成功时，查找长度为n+1；成功时，平均查找长度为1/(n+1)*(1+2+…+(n+1))=(n+2)/2；两者不相同。 （2）表中只有一个关键字等于给定值k 的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+…+n)=(n+1)/2；两者相同。 （3）表中只有m 个关键字等于给定值k 的记录，无序表：ASL=n+1；有序表：ASL=（n+1）/2+m ；两者不相同。 9.3 ASL=1/10（1+2*2+4*3+3*4）=2.9 9.11 9.14 6 5 2 8 3 1 9 7 4 10 删除50后 删除68后 0 1 2 3 4 5 6 7 8 9 10 ASL=（4*1+2*2+3+6）/8=17/8 9.25 int Search-Seq(SSTable ST, KeyType key){ //在顺序表ST 中顺序查找其关键字等于key 的数据元素，ST 按关键字自大至小有序， //若找到，则函数值为该元素在表中的位置，否则为0 ST.elem[ST.length+1].key=key; for (i=1; ST.elem[i].key>key; ++i); if (ST.elem[i].key==key)&&(i<=ST.length) return i else return 0 ; }//Search-Seq 9.31 TelemType Maxv(Bitree T){ //返回二叉排序树T中所有结点的最大值 for (p=T; p->rchild; p=p->rchild); return p->data; }//Maxv TelemType Minv(Bitree T){ //返回二叉排序树T中所有结点的最小值 for (p=T; p->lchild; p=p->lchild); return p->data; }//Minv Status IsBST(Bitree T){ //判别T是否为二叉排序树 if (!T) return OK; else if ((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild) 《教育学》章节练习题 第八章教学（下） 一、单项选择题 1、下列关于学生学业成绩评定叙述正确的是( A ) A 评定学生学业成绩，一般采用百分制记分法和等级制记分法 B 一般说，题的数量多、便于给小分的，用等级制较便利 C题的数量不多、开卷、理解和灵活运用的题目用百分制较方便 D 在成绩评定时，不能把等级制换算成一定的分数 2、下列关于复式教学叙述正确的是( C ) A 复式教学就是对两个以上年级的学生进行教学的一种教学组织形式 B 复式教学适用于学生多、教室少的情况下教学 C 复式教学课堂教师的教学和学生的自学或做作业同时进行 D 复式教学情景下的学生的基本技能和自学能力相对较弱 3、一节课中最基本的组成部分是（ D ） A 组织教学 B 检查复习 C 巩固新教材 D 讲授新教材 4、用于选拔性和竞赛性活动的评价属于（ A ） A 相对评价 B 绝对评价 C 个体内差异评价 D 形成性评价 5、把两个及其两个年纪以上的儿童编在一个班级，直接教学与布置、完成作业 轮流交替进行，在一节课内由一位老师对不同年级学生进行教学的组织形式是（D ） A 分层教学 B 合作学习 C 小班教学 D 复式教学 6、在下列教学组织形式中，有利于高效率、大面积培养学生的是（ B ） A 个别教学 B 班级授课 C 分组教学 D 道尔顿制 7、从评价的功能上区分，中小学教育评价的类型可分为（） A 正式评价和非正式评价 B 相对评价和绝对评价 C 形成性评价和总结性评价 D 正确评价和错误评价 8、教学工作的中心环节是（ B ） A 备课 B 上课 C 布置批改作业 D 成绩考评 9、为了分班、分组的目的所进行的测验是（ D ） -167- 第八章 层次分析法 层次分析法（Analytic Hierarchy Process ，简称AHP ）是对一些较为复杂、较为模糊的问题作出决策的简易方法，它特别适用于那些难于完全定量分析的问题。它是美国运筹学家T. L. Saaty 教授于上世纪70年代初期提出的一种简便、灵活而又实用的多准则决策方法。 §1 层次分析法的基本原理与步骤 人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互制约的众多因素构成的复杂而往往缺少定量数据的系统。层次分析法为这类问题的决策和排序提供了一种新的、简洁而实用的建模方法。 运用层次分析法建模，大体上可按下面四个步骤进行： （i ）建立递阶层次结构模型； （ii ）构造出各层次中的所有判断矩阵； （iii ）层次单排序及一致性检验； （iv ）层次总排序及一致性检验。 下面分别说明这四个步骤的实现过程。 1.1 递阶层次结构的建立与特点 应用AHP 分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型。在这个模型下，复杂问题被分解为元素的组成部分。这些元素又按其属性及关系形成若干层次。上一层次的元素作为准则对下一层次有关元素起支配作用。这些层次可以分为三类： （i ）最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层。 （ii ）中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层。 （iii ）最底层：这一层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层或方案层。 递阶层次结构中的层次数与问题的复杂程度及需要分析的详尽程度有关，一般地层次数不受限制。每一层次中各元素所支配的元素一般不要超过9个。这是因为支配的元素过多会给两两比较判断带来困难。 下面结合一个实例来说明递阶层次结构的建立。 例1 假期旅游有1P 、2P 、3P 3个旅游胜地供你选择，试确定一个最佳地点。 在此问题中，你会根据诸如景色、费用、居住、饮食和旅途条件等一些准则去反复比较3个侯选地点。可以建立如图1的层次结构模型。 图1 层次结构模型 统计学答案第八章． 三、选择题纤维的纤某厂生产的化纤纤度服从正态分布，1 根纤维的纤25.40。某天测得度的标准均值为1 度的均值=1.39，检验与原来设计的标准均值x比是否有所变化，要求的显著性水平为 α=0.05，则下列正确的假设形式是（）。A.H：μ=1.40，H：μ≠1.40 B. H：μ001≤1.40，H：μ>1.40 1C. H：μ<1.40，H：μ≥1.40 D. H：010μ≥1.40，H：μ<1.40 1 2 某一贫困地区估计营养不良人数高达20％，然而有人认为这个比例实际上还要高，要检验该说法是否正确，则假设形式为（）。 A. H：π≤0.2，H：π>0.2 B. H：π001=0.2，H：π≠0.2 1C. H：π≥0.3，H：π<0.3 D. H：π001≥0.3，H：π<0.3 1 3 一项新的减肥计划声称：在计划实施的第一周内，参加者的体重平均至少可以减轻8磅。随机位参加该项计划的样本，结果显示：样40抽 取． 32标准差为磅，则本的体重平均减少7磅，。其原假设和备择假设是（）A. H：μ≤8， H：μ>8 B. H：μ≥001 8，H：μ<8 1C. H：μ≤7，H：μ>7 D. H：μ≥0107，H：μ<7 1 4 在假设检验中，不拒绝原假设意味着（）。 A.原假设肯定是正确的 B.原假设肯定是错误的 C.没有证据证明原假设是正确的 D.没有证据证明原假设是错误的 5 在假设检验中，原假设和备择假设（）。 A.都有可能成立 B.都有可能不成立 C.只有一个成立而且必有一个成立 D.原假设一定成立，备择假设不一定成立 6 在假设检验中，第一类错误是指（）。 A.当原假设正确时拒绝原假设 B.当原假设错误时拒绝原假设 C.当备择假设正确时拒绝备择假设 D.当备择假设不正确时未拒绝备择假设 【城市地理学】复习参考 第一章 1、城市地理学的研究对象 城市地理学是研究城市空间组织规律性的科学，具体地讲，是研究在不同地理环境下，城市形成发展、组合分布和空间结构变化规律的科学。 2、城市地理学研究的主要内容 （1）城市形成发展条件研究 （2）区域的城市空间组织研究 （3）城市内部空间组织研究 （4）城市问题研究 第二章 1、都市区：一个大的人口核心以及与这个核心具有高度的社会经济一体化倾向的邻接社区 的组合，一般以县作为基本单元。中心县+外围县 大都市带：许多都市区连成一体，经济、社会、文化等活动相互作用密切，是一个巨大的城市地域复合体。 城市群：城市群是城市发展到成熟阶段的最高空间组织形式，是在地域上集中分布的若干城市和特大城市集聚而成的庞大的、多核心、多层次城市集团，是大都市区 的联合体。 2、区分城市的行政地域、实体地域、功能地域 第三章 1、简述不同类型城市的形成和发展（形成的原因、功能与特点、分类、发展条件） 中心地型城市 形成动因：商品农业 功能：满足农村的物资集散和综合服务的需要 特点：职能综合，发展稳定，等级鲜明 类别：集镇、城镇、县城 发展条件： 以交通运输职能为主的城市 形成动因：交通地理位置 功能：满足区际贸易和交通转运的需要 特点：职能较单一，发展起伏较大 类别：铁路沿线、铁路枢纽、渡口、河海港、边境和特区、综合运输枢纽城市 发展条件： 以某种专门职能为主的城市 形成动因：天赋的资源和人类特殊需要 功能：满足某种专门需要，集聚经济，规模经济 特点：职能较单一，对外联系广，联系内容单一，发展历史短但速度快，发展起伏大 类别：矿业、工矿、工业、风景旅游、科学文化城等 发展条件： 第四章 1、城市化：人口向城市集中的过程和农村地区转变为城市地区的过程。 郊区城市化：也叫城市郊区化，简称郊区化，就是人口、就业岗位和服务业从大城市中心向郊区迁移的一种分散化过程。 逆城市化：人口从大城市和主要的大都市区向小的都市区甚至非都市区迁移的一种分散化过程。 再城市化：城市出现的城市人口回流，城市中心区再现活力，而郊区出现形体再开发的过程。 2、城市化地区 3、乡村——城市人口迁移的动因分析（城乡人口迁移的推力、拉力，即推拉说、推拉理论）城市工业化的发展提供了大量的就业机会，把农村人口拉了进来，“拉因”成为城市发展的主要因素。乡村破产使乡村人口大量涌进城市，造成城市人口膨胀，“推因”成为城市发展的主导因素。 4、简述城市化的类型划分 （1）以大城市为中心来考察城市化现象：向心型城市化与离心型城市化 （2）按照城市离心扩散形式的不同：外延型城市化与飞地型城市化 （3）景观型城市化与职能型城市化 （4）积极型城市化与消极型城市化 （5）针对中国城市化状况提出来的：自上而下型城市化与自下而上型城市化 第五章 1、简述当代中国城市化的主要特征 （1）城市化进程波动性大 （2）城市规模体系的动态变化加速 （3）城市化水平的省际差异显著 （4）郊区城市化开始显现 （5）都市连绵区成为国家经济核心地区 第六章 1、划分城市经济活动的基本与非基本部分 一个城市的全部经济活动，按其服务对象来分，可分成两部分： 1）为本城市的需要服务的， 2）为本城市以外的需要服务的。 （1）基本经济活动：为外地服务的部分，是从城市以外为城市所创造收入的部分，它是城市得以存在和发展的经济基础，是导致城市展的主要动力。是为本城市以外的需要服务的。离心型的基本活动：例如，城市生产的工业产品或城市发行的书刊报纸运到城市以外销售；向心型的基本活动：例如，外地人到这个城市来旅游、购物、求学或接受医疗等。 （2）非基本的活动：满足城市内部需求的经济活动，随着基本部分的发展而发展，它被称为非基本活动部分。是为城市本身服务的活动。 （一）教学的概念 1、识记：教学概念的含义 2、领会：教学与教育、教学与智育的关系 （二）教学的地位和任务 领会：（1） 教学的地位和作用（2） 教学的任务 （三）现代教学观的演变趋向 领会：当代教学观念变革的六大走向。 （四）教学系统 1.识记：（1）教学系统的概念的含义（2）教学系统的特性（3）教学系统的要求 2.领会（1）教师中心说的含义（2）学生中心说的含义（3）学科中心说的含义 第一节、教学概述 教学：在广义上，教学就是指教的人指导学的人以一定文化为对象进行学习的活动。 在狭义上，我们所说的教学，是专指学校中教师引导学生学习的教与学相统一的活动。p262识记 教学与教育两个概念即相互联系又有区别：p262 教育指一切培养人的活动。广义的教学与教育一词没有什么区别，但在狭义上，教学专指课堂上教师的教与学生的学的活动，只是教育的一部分，已经从教育概念中分化了出来 教学与智育两个概念即相互联系但又不同的概念：p262 智育是指向受教育者传授系统的文化科学知识和技能，专门发展受教育者智力的教育活动。 教学是智育的一条主要途径，但并不等同于智育。讲教学，突出的是他是一种特殊的教育活动；而讲智育，突出的是它是教育的一个重要方面。 （一） 教学的地位p262 （二） 教学的基本作用p263~265 从教育目的看：培养德智体美 从心理发展角度： 一方面，教学的作用是促进学生认知智慧的发展，包括是学生 掌握一定的知识，形成一定的技能，发展一定的能力； 另一方面，教学的在促进学生认知发展的同时，也在促进学生 的情感智慧的发展。 教学的作用概括为如下四点： a: 授受基础知识 b：形成基本技能 动作技能和智力技能 c：发展基本能力 一是已经表现出来的实际能力和已达到的某种熟练程度，可用成就测验来测量； 二是指潜在能力，即尚未表现出来的心理能量，而通过学习和训练后可能发展起来的能力与可能达到的某种熟练程度，可用性向测验来测量。d：促进个性健康发展 p265~267 社会 工业社会 信息社会 教育 专才教育 通才教育 当代教学观念的变革主要体现为以下六大走向： （一） 从重视教师向重视学生转变“教师中心说”“学生中心说”（二） 从重视知识传授向重视能力培养转变 “授人以鱼不如授人以渔” （三） 从重视教法向重视学法转变 教法的实质是学法，教学过程实质上是学生的学习过程（四） 从重视认知向重视发展转变 传统教学观比较重视知识的掌握 现代重视儿童身体、认知和情感全面和谐发展，成了现代教学观念的基本精神。 （五） 从重视结果向重视过程转变 传统：非常重视教学的结果，忽视教学过程 现代教学观念：第一，强调激发学生的兴趣 第二，强调在教师启发引导基础上，让学生通过独立思考获得对基本知识的领悟和技能、技巧的习得； 第三，强调“知-情”对称； 第四，注重教学方法的灵活多样以及多种方式、方法的综合应用，为儿童设计出合乎年龄特点的活动，促进儿童在学习过程中得到充分发展。（六） 从重视继承向重视创新转变 传统：认为教育教学的主要功能是传承文化，学生的主要任务就是继承已有知识经验。 现代：教育教学的重要功能就是创造文化，学生的主要任务就是通过掌握知识经验，形成创造文化和创新生活的能力。 第二节 教学系统 数据结构练习第八章查找 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个结点，则在二叉排序树的平均平均查找长度为（）。 A. O(1) B. O(log 2 n) C. O(n) D. O(n2) 3．在二叉排序树中插入一个结点的时间复杂度为（）。 A. O(1) B. O(n) C. O(log 2 n) D. O(n2) 4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 A. log 2n+1 B. log 2 n-1 C. log 2 n D. log 2 (n+1) 5．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 6．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A. O(n) B. O(n2) C. O(n1/2) D. O(1og 2 n) 7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 A. O(n) B. O(n2) C. O(nlog 2n) D. O(1og 2 n) 8．（）二叉排序树可以得到一个从小到大的有序序列。 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通常情况下最好选择（）。 A. 99 B. 97 C. 91 D. 93 11．在二叉排序树中插入一个关键字值的平均时间复杂度为（）。 A. O(n) B. O(1og 2n) C. O(nlog 2 n) D. O(n2) 12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 A. A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5] ，A[3]，A[4] 13．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 A. 小于等于m的最大奇数 B.小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 14．设顺序表的长度为n，则顺序查找的平均比较次数为（）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 15．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4 选择题填空题 第八章 1，教学是教师和学生共同组成的的传递和掌握社会经验的双边活动，是实施全面发展教育的基本途径（辨析，教学是教师传授知识的过程，错误）（教学是贯彻教育方针、实施全面发展教育、实现教育目的的基本途径，看见基本途径就是教学。看见根本途径，唯一途径是教育与生产劳动相结合，详见书p80，p81） 2，教学是学校的中心工作，学校工作必须坚持以教学为主、全面安排的原则 3，理解教材是教学过程的中心环节 4，贯彻掌握知识和发展智力的相统一原则的规律：（狂+巨） 我们要防止两种倾向，既不能像形式教育论者那样，只强调训练学生的思维形式。也不能像实质教育论者那样，只向学生传授与实际生活有用的知识 5，教学原则是有效的进行教学必须遵循的基本要求（狂+巨） 6，直观教具一般分为三类：a实物直观，b模象直观，c语言直观。 7，“不愤不启，不悱不发”“道而弗牵，强而弗抑，开而弗达”体现了启发性原则 8，循序渐进原则： A按照此原则的基本要求 B在注意系统性的同时要抓住重点和难点 C教学要符合学生认识规律，由已知到未知，有具体到抽象 （选填，ABC体现了循序渐进原则） 9，备课分为个人备课和集体备课两种 10，教师备课要做好三方面的工作，既钻研教材，了解学生和设计教学 11，教师备课要做好三种计划，既学年（或学期）教学进度计划，单元（或课题）计划，课时计划（教案） 12，上课是整个教学工作的中心环节（狂+巨） 13，课的类型大致可分为单一课和综合课两大类 14，课外辅导有集体辅导和个别辅导两种形式 15，常用的检查方式有两大类：平时考查和考试 16，学业成绩评定的方法一般分为以下几种：百分之制记分法、等级制记分法、评语法17，教学的基本组织形式是：班级授课制（狂+巨） 18，班级授课制是把学生按年龄和文化程度分成班级，教师根据课程计划、学科课程标准和规定的时间进行教学的一种组织形式 19，1862年，清政府在北京开办京师同文馆中首次采用班级授课制（狂+巨） 20，教学方法是教师和学生为实现教育目的、完成教学任务所采用的手段和一整套工作方式，它包括教师教的方法和学生学的方法。 21，教学方法归并为两大类：启发式和注入式（注入式又名填压式） 22，讲授法是指教师运用口头语言系统的向学生传授知识的一种方法。它包括：讲述、讲解、讲读、讲演 23，谈话法是指教师通过和学生围绕一定的问题，相互交谈来进行教学的方法，也叫问答法，包括：复习谈话和启发谈话 24，讨论法是指在教师的指导下，有全班获小组成员围绕某一中心问题发表自己的看法，从而进行相互学习的一种方法 25，以情感陶冶为主的教学方法：a欣赏教学法（包括：自然的欣赏、人生的欣赏、艺术的欣赏），b情景教学法 26，教学手段是指教师对学生进行教学活动以及相互传递信息的、媒体或设备《数据结构》习题汇编08 第八章 查找 试题
统计学第五版(贾俊平)第八章课后习题答案
统计学第七章、第八章课后题答案
城市地理学复习资料
统计学基础 第八章 相关与回归分析
数据结构 第八章 查找自测题
教育学第八章汇总
数据结构第八章习题及答案
统计学第八章题目
第八章查找
教育学章节练习题第八章
8第八章 层次分析法
统计学答案第八章
城市地理学
《教育学》第八章讲义
数据结构练习第八章-查找
教育学第八章