第8章查找
第八章查找
?基本概念
?线性表的查找
?树表的查找
?散列(Hash)技术
8.1 查找的基本概念
查找（Searching）的定义是：给定一个关键字值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。
?查找表的数据结构表示
若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。
若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。
平均查找长度 ASL（Average Search Length）的定义为：
其中：
1、n是结点的个数；
2、Pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即
pl = p2…… = pn = 1/n
3、ci是找到第i个结点所需进行的比较次数。（i=1,2, ··· ,n）
8.2线性表的查找
?顺序查找(Sequential Search)
基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。
基于顺序结构的顺序查找算法
类型说明
typedef struct
{ KeyType key； /* KeyType由用户定义 */
InfoType otherinfo；/* 此类型依赖于应用 */
}NodeType；
typedef NodeType Seqlist[n+1]；
/*0号单元用作监视哨*/
具体算法
int SeqSearch(Seqlist R，KeyType K)
{ /*在顺序表R[1..n]中顺序查找关键字为K的结点，成功时返回找到的结点位置，失败时返回0*/
int i；
R[0].key=K； /*设置监视哨*/
for(i=n；R[i].key!=K;i--)； /*从表后往前找*/
return i； /*若i为0，表示查找失败，否则R[i]为要找的结点*/
} /*SeqSearch*/
?算法分析
查找成功时的顺序查找的平均查找长度：
ASL= =pi =np1+(n-
1)p2+…+2pn-1+pn （式8.2）
在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长度为
(n+…+2+1)/n=(n+1)/2
即查找成功时的平均比较次数约为表长的一半。
?顺序查找的优点
算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。
?顺序查找的缺点
查找效率低。
二分查找
?二分查找又称折半查找，它是一种效率较高的查找方法。
?二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
二分查找的基本思想是：
（1）首先确定该区间的中点位置：
（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。
例如: key = 64的查找过程如下
low指示查找区间的下界;
high指示查找区间的上界;
mid = (low+high)/2。
二分查找算法
int BinSearch(SeqList R，KeyType K)
{int low=1，high=n，mid；
while(low<=high)
{mid=(low+high)/2；//求得中间元素
if(R[mid].key==K) return mid；//找到
if(R[mid].key>K) //设定下次查找区间
high=mid-1;
else
low=mid+1；
}
return 0；
}
二分查找判定树
二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。
分析折半查找的平均查找长度
先看一个具体的情况，假设：
n=11
二分查找判定树的组成
?圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。
?外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。
?当查找时找到外部节点时，表示查找的值没有在该有序表中。
二分查找的平均查找长度
?二分查找成功时的平均查找长度为： ASLbn≈lg(n+1)-1
?二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：
二分查找的优点和缺点
?虽然二分查找的效率高，但是要将表按关键字排序。
?二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。
分块查找
?分块查找表存储结构
?分块查找表由"分块有序"的线性表和索引表组成。
?分块查找的基本思想：
?首先查找索引表
索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。
?然后在已确定的块中进行顺序查找
由于块内无序，只能用顺序查找。
索引顺序表
在建立顺序表的同时，建立一个索引。
例如：顺序表
算法分析
?分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。
以二分查找来确定块，分块查找成功时的平均查找长度
?ASLblk=ASLbn+ASLsq
?≈log2(b+1)-1+(s+1)/2≈log2(n/s+1)+s/2
以顺序查找确定块，分块查找成功时的平均查找长度
?ASL’blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)
?分块查找的优点
?①在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。
?②因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。
综合以上讨论的几种查找表的特性：
可得如下结论：
1）从查找性能看，最好情况能达
O(logn)，此时要求表有序；
2）从插入和删除的性能看，最好
情况能达O(1)，此时要求存储
结构是链表。
树表的查找
一、二叉排序树（二叉查找树）
二、二叉平衡树
三、B - 树
四、B+树
五、键树
一、二叉排序树
（二叉查找树）
1．定义
2．查找算法
3．插入算法
4．删除算法
5．查找性能的分析
1．定义：
二叉排序树或者是一棵空树；或者
是具有如下特性的二叉树：
（1）若它的左子树不空，则左子树上
所有结点的值均小于根结点的值；
（2）若它的右子树不空，则右子树上
所有结点的值均大于根结点的值；
（3）它的左、右子树也都分别是二叉
排序树。
不是二叉排序树。
通常，取二叉链表作为
二叉排序树的存储结构
2．二叉排序树的查找算法：
若二叉排序树为空，则查找不成功；
否则
?1）若给定值等于根结点的关键字，则查找成功；
?2）若给定值小于根结点的关键字，则继续在左子树上进行查找；
?3）若给定值大于根结点的关键字，则继续在右子树上进行查找。
查找关键字==50，35，90，95，
从上述查找过程可见，
在查找过程中，生成了一条查找路径:
从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功
或者
从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。
——查找不成功
算法描述如下：
Status SearchBST (BiTree T, KeyType kval,
BiTree f, BiTree &p ) {
// 在根指针 T 所指二叉排序树中递归地查找其
// 关键字等于 kval 的数据元素，若查找成功，
// 则返回指针 p 指向该数据元素的结点，并返回
// 函数值为 TRUE; 否则表明查找不成功，返回
// 指针 p 指向查找路径上访问的最后一个结点，
// 并返回函数值为FALSE, 指针 f 指向当前访问
// 的结点的双亲，其初始调用值为NULL
… … … …
}
// SearchBST
非递归查找
3．二叉排序树的插入算法
根据动态查找表的定义，“插入”操作在查找不成功时才进行;
若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。
4．二叉排序树的删除算法
和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。
可分三种情况讨论：
?（1）被删除的结点是叶子；
?（2）被删除的结点只有左子树或者只有右子树；
?（3）被删除的结点既有左子树，也有右子树。
（1）被删除的结点是叶子结点
其双亲结点中相应指针域的值改为“空”
（2）被删除的结点只有左子树或者只有右子树
其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。 （3）被删除的结点既有左子树，也有右子树
算法描述如下：
其中删除操作过程如下所描述：
// 右子树为空树则只需重接它的左子树 q = p; p = p->lchild; delete
(q);
// 左子树为空树只需重接它的右子树
q = p; p = p->rchild; delete(q);
// 左右子树均不空
5．查找性能的分析
对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。
例如：
由关键字序列 1，2，3，4，5构造而得的二叉排序树， ASL =（1+2+3+4+5）/ 5= 3
由关键字序列 3，1，2，5，4构造而得的二叉排序树 ASL =（1+2+3+2+3）
/ 5 = 2.2
二、二叉平衡树(课后自学) 何谓“二叉平衡树”？ 如何构造“二叉平衡树” 二叉平衡树的查找性能分析
二叉平衡树是二叉查找树的另一种形式，其特点为：
三、 B - 树 1．定义 2．查找过程 3．插入操作 4．删除操作
5．查找性能的分析
B-树结构的C 语言描述如下: typedef struct BTNode {
int keynum; // 结点中关键字个数，结点大小 struct BTNode *parent;
// 指向双亲结点的指针 KeyType key[m+1]; // 关键字（0号单元不用） struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指针向量 } BTNode, *BTree; // B 树结点和B 树的类型
非叶结点中的多个关键字均自小至大有序排列，即：K1< K2 < … < Kn ;
? 且 Ai-1 所指子树上所有关键字均小于Ki ;
Ai 所指子树上所有关键字均大于Ki ;---查找树的特性
?
? 树中所有叶子结点均不带信息，且在树中的同一层次上; ? 根结点或为叶子结点，或至少含有两棵子树;
?其余所有非叶结点均至少含有?m/2?棵子树，至多含有m棵子树;
-------------平衡树的特性
?
2.查找过程：
从根结点出发，沿指针搜索结点和在
结点内进行顺序（或折半）查找两个过程
交叉进行。
若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；
若查找不成功，则返回插入位置。
假设返回的是如下所述结构的记录:
typedef struct {
BTNode *pt; // 指向找到的结点的指针
int i; // 1..m，在结点中的关键字序号
int tag; // 标志查找成功(=1)或失败(=0)
} Result; // 在B树的查找结果类型
Result SearchBTree(BTree T, KeyType K) {
// 在m 阶的B-树 T 中查找关键字 K, 返回
// 查找结果 (pt, i, tag)。若查找成功，则
// 特征值 tag=1, 指针 pt 所指结点中第 i 个
// 关键字等于 K; 否则特征值 tag=0, 等于
// K 的关键字应插入在指针 pt 所指结点
// 中第 i 个关键字和第 i+1个关键字之间
} // SearchBTree
p=T; q=NULL; found=FALSE; i=0;
while (p && !found) {
n=p->keynum; i=Search(p, K);
// 在p->key[1..keynum]中查找 i ，p->key[i]<=K
else { q=p; p=p->ptr[i]; } // q 指示 p 的双亲
}
if (found) return (p,i,1); // 查找成功
else return (q,i,0); // 查找不成功
3．插入
在查找不成功之后，需进行插入。
显然，关键字插入的位置必定在最下
层的非叶结点，有下列几种情况：
1）插入后，该结点的关键字个数n 不修改指针; 例如 2）插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = ?m/2?， 在原结点中保留 （A0，K1，。。。， Ks-1，As-1）； 建新结点 （As，Ks+1，。。。，Kn，An）； 将（Ks，p）插入双亲结点；例如 3）若双亲为空，则建新的根结点。 例如 4．删除 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之 后，结点中关键字的个数不能小于?m/2?-1，否则，要从其左(或右)兄弟结点“借调” 关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须 进行结点的“合并”。 试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20,30,50,52,60,68,70.如果此后删除50和68，画出每一步执行后2-3树的状态。 四、B+树 是B-树的一种变型 1．B+树的结构特点： ※每个叶子结点中含有n个关键字和n个指向记录的指针；并且，所有叶 子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点； ※每个非叶结点中的关键字Ki 即为其相应指针Ai 所指子树中关键字的最大值； ※所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于?m/2?和m 之间。 2．查找过程 ※在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找； ※在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； ※若在结点内查找时，给定值≤Ki，则 应继续在Ai 所指子树中进行查找； 3．插入和删除的操作 类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。 五、键树 1.键树的结构特点 2. .双链树 3. Trie树 1.键树的结构特点： ※关键字中的各个符号分布在从根结点到叶的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字集合的大小无关; ※键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘$’小于任何其它符号。 typedef struct DLTNode { char symbol; struct DLTNode *next; // 指向兄弟结点的指针 NodeKind kind; union { Record *infoptr; // 叶子结点内的记录指针 struct DLTNode *first; // 分支结点内的孩子链指针 } } DLTNode, *DLTree; // 双链树的类型 #define MAXKEYLEN 16 //关键字的最大长度 typedef struct { char ch[MAXKEYLEN]; // 关键字 int num; // 关键字长度 } KeysType; // 关键字类型 在双链树中查找记录的过程: 假设: T 为指向双链树根结点的指针， K.ch[0..K.num-1] 为待查关键字 (给定值)。 则查找过程中的基本操作为进行下列比较: K.ch[i] =? p->symbol 其中: p 指向双链树中某个结点， 0 ≤ i ≤ K.num-1 初始状态: p=T->first; i = 0; 若 ( p && p->symbol == K.ch[i] && i 则继续和给定值的下一位进行比较 p=p->first; i++; 若 ( p && p->symbol != K.ch[i] ) 则继续在键树的同一层上进行查找 p=p->next; 若 ( p == NULL) 则表明查找不成功，返回“空指针”; 若 ( p && p->symbol==K.ch[i] && i==K.num-1) 则查找成功，返回指向相应记录的指针 p->infoptr 9.3 哈希表 一、哈希表是什么？ 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作 六、对静态查找表，。。。 一、哈希表是什么？ 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系， 查找的过程为给定值依次和关键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数。 用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同。 对于频繁使用的查找表， 希望 ASL = 0。 只有一个办法：预先知道所查关键字在表中的位置， 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。 例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份)。 若以下标为000 ~ 999 的顺序表表示之。 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。 但是，对于动态查找表而言， 1) 表长不确定； 2) 在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。 因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。 从这个例子可见， 1) 哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可; 2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1≠ key2，而 f(key1) = f(key2)。 3) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突”的方法。 哈希表的定义: 根据设定的哈希函数 H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。 1.直接定址法 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a ? key + b 此法仅适合于： 地址集合的大小 = = 关键字集合的大小 2.数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成(u1, u2, …, us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。 此方法仅适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度。 3. 平方取中法 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。 4. 折叠法 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。 此方法适合于: 关键字的数字位数特别多。 5. 除留余数法 设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子 为什么要对 p 加限制？ 例如： 给定一组关键字为: 12, 39, 18, 24, 33, 21， 若取p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3 可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。 6.随机数法 设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。 三、处理冲突的方法 “处理冲突”的实际含义是： 为产生冲突的地址寻找下一个哈希地址 1. 开放定址法 2. 链地址法 1. 开放定址法 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs1≤ s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, …, s 对增量di有三种取法： ?1) 线性探测再散列 di = c? i最简单的情况c=1 ?2) 平方探测再散列 di = 12, -12, 22, -22, …, ?3) 随机探测再散列 di 是一组伪随机数列或者 ?di=i×H2(key) (又称双散列函数探测) 注意：增量di应具有“完备性” 即：产生的Hi 均不相同，且所产生的 s(m-1)个 Hi值能覆盖哈希表中所有 地址。则要求： ※平方探测时的表长m 必为形如4j+3 的素数（如: 7, 11, 19, 23, … 等）； ※随机探测时的m和di 没有公因子。 四、哈希表的查找 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为: 对于给定值 K, 计算哈希地址 i = H(K) 若 r[i] = NULL 则查找不成功 若 r[i].key = K 则查找成功 否则 “求下一地址 Hi ” ，直至 r[Hi] = NULL (查找不成功) 或 r[Hi].key = K (查找成功) 为止。 //--- 开放定址哈希表的存储结构 --- 哈希表查找的分析: 从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。 决定哈希表查找的ASL 的因素： ? 1) 选用的哈希函数; ? 2) 选用的处理冲突的方法; ? 3) 哈希表饱和的程度，装载因子 α=n/m 值的大小（n —记录数，m —表的长度） 一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL 时，可以不考虑它的因素。 因此，哈希表的ASL 是处理冲突方法和装载因子的函数。 例如：前述例子 可以证明：查找成功时有下列结果： 线性探测再散列 随机探测再散列 链地址法 从以上结果可见， 哈希表的平均查找长度是 α 的函数，而不是 n 的函数。 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 α ，使得平均查找长度限定在某个范围内。 —— 这是哈希表所特有的特点。 五、哈希表的删除操作 从哈希表中删除记录时，要作特殊处理，相应地，需要修改查找的算法。 六、哈希表也可以用来构造静态查找表。 并且，对静态查找表，有时可以找到不发生冲突的哈希函数。即，此时的哈希表的 ASL=0, 称此类 哈希函数为理想（perfect ）的哈希函数。 数据结构课程（本科）第七章试题 一、单项选择题 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第八章 层次分析法
统计学答案第八章
城市地理学
《教育学》第八章讲义
数据结构练习第八章-查找
教育学第八章