设计构造哈希表的完整算法,求出平均查找长度

一、应用题1. 已知关键字序列为：（74,33,52,41,13,88,66,59）哈希表长为9，哈希函数为：H (k)＝k %9，解决冲突用线性补偿探测法 （取Q=5），试构造哈希表，并求出等概率下查找成功的平均查找长度。

【答案】（1）哈希表:0 1 2 3 4 5 6 7 859 74 88 13 4133 52 6621211112(2) ASL=（5*1+3*2）/8=11/82. 已知一个AOV 网如图所示。

(1)试画出它的邻接链表。

（顶点号递减出现在各邻接表中）(2)试写出按照拓扑排序算法得到的拓扑序列。

V 6V 1V 2V 4V 5V 3【答案】(1)1 v 1 06v 6 1 5 v 5 3 3V 3 2 4v 4 0 2v 2 2 ∧ 6 53 ∧5 ∧5 ∧2 ∧32 ∧(2)v 4,v 6,v 1,v 3,v 5,v 23. 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L 状态；（2）简述算法f30的功能。

void f30 (SeqList *L) { int i,j;for (i=j=0;i<L->length; i++)if(L->data[i]>=0){if(i!=j)L->data[j]=L->data[i]; j++； } L->length=j; }【答案】（1）L=(21,19,0,34,30)(2) 删除顺序表中小于0的数。

4. 已知关键字序列{34,26,47,12,63,41,22,59},利用堆排序的方法对其排序。

（1）写出在构成初始堆后关键字的排列情况。

（2）写出在堆排序的过程中输出前4个记录时,每次调整后关键字的排列情况。

【答案】（1）初始堆：{12,26,22,34,63,41,47,59}（2）输出12后：{22，26，41，34，63，59，47} 输出22后：{26，34，41，47，63，59} 输出26后：{34，47，41，59，63} 输出34后：{41，47，63，59}5. 请用克鲁斯卡尔算法构造下图所示网络的最小生成树。

第九章查找一、选择题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. 结点太复杂。

一、单项选择题1．评价一个算法时间性能的主要标准是（）A.算法易于调试B. 算法易于理解C.算法的稳定性和正确性D.算法的时间复杂度2．可用带表头结点的链表来表示表，也可用不带表头结点的链表来表示表，前者的主要好处是（）A.可以加快对表的遍历B.使空表和非空表的处理统一C.提高存取结点的速度D.节省存储空间3．稀疏矩阵一般的压缩存储有两种，即（）。

A．一维数组和二维数组B．一维数组和三元组C．二维数组和十字链表D．三元组和十字链表4.链表不具有的特点是（）。

Ａ．可随机访问任一元素Ｂ．插入删除不需要移动元素Ｃ．不必事先估计存储空间Ｄ．所需空间与线性表的长度成正比5.非空的循环单链表head的尾结点p满足（）。

A．P->next==NULL B．p==NULL C．P->next==head D．P==head 6．对稀疏矩阵进行压缩存储是为了（）。

A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度7．数据结构中,与所使用的计算机无关的是数据的（）结构。

A.顺序B.物理C.逻辑D.物理和存储8．在长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是（）。

A.（n-1）/2B.n/2C.n*(n-1)/2D.(n+1)/29．对于一个头指针为H的带头结点的单链表，判定该表为空表的条件是（）A. H==NULL B．H!=NULL C.H→next ==H D．H→next==NULL10. 在一个顺序表中，若表的第一个元素的存储地址是210，每一个元素的长度为3，则第5个元素的存储地址是（）。

A．219 B．222 C．225 D．22811. 栈S最多能容纳4个元素,现有6个元素按a,b,c,d,e,f的顺序进栈,下面序列（）是可能的出栈序列。

A．edcbaf B.bcefad C.cbedaf D.adfebc12．循环队列用数组A[M]存放元素，已知其头尾指针分别为front和rear，则当前队列中的元素个数是（）。

哈希表——线性探測法、链地址法、查找成功、查找不成功的平均长度⼀、哈希表1、概念哈希表(Hash Table)也叫散列表，是依据关键码值（Key Value）⽽直接进⾏訪问的数据结构。

它通过把关键码值映射到哈希表中的⼀个位置来訪问记录，以加快查找的速度。

这个映射函数就做散列函数。

存放记录的数组叫做散列表。

2、散列存储的基本思路以数据中每⼀个元素的keywordK为⾃变量。

通过散列函数H（k）计算出函数值，以该函数值作为⼀块连续存储空间的的单元地址，将该元素存储到函数值相应的单元中。

3、哈希表查找的时间复杂度哈希表存储的是键值对，其查找的时间复杂度与元素数量多少⽆关。

哈希表在查找元素时是通过计算哈希码值来定位元素的位置从⽽直接訪问元素的，因此，哈希表查找的时间复杂度为O（1）。

⼆、经常使⽤的哈希函数1. 直接寻址法取keyword或者keyword的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这样的散列函数也叫做⾃⾝函数.假设H(Key)的哈希地址上已经有值了,那么就往下⼀个位置找,知道找到H(Key)的位置没有值了就把元素放进去.2. 数字分析法分析⼀组数据,⽐⽅⼀组员⼯的出⽣年⽉,这时我们发现出⽣年⽉的前⼏位数字⼀般都同样,因此,出现冲突的概率就会⾮常⼤,可是我们发现年⽉⽇的后⼏位表⽰⽉份和详细⽇期的数字区别⾮常⼤,假设利⽤后⾯的⼏位数字来构造散列地址,则冲突的⼏率则会明显减少.因此数字分析法就是找出数字的规律,尽可能利⽤这些数据来构造冲突⼏率较低的散列地址.3. 平⽅取中法取keyword平⽅后的中间⼏位作为散列地址.⼀个数的平⽅值的中间⼏位和数的每⼀位都有关。

因此，有平⽅取中法得到的哈希地址同keyword的每⼀位都有关。

是的哈希地址具有较好的分散性。

该⽅法适⽤于keyword中的每⼀位取值都不够分散或者较分散的位数⼩于哈希地址所须要的位数的情况。

第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; //假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

void inverse(LinkList &L) {// 逆置带头结点的单链表 Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q指向*p的后继p->next=L->next;L->next=p; // *p插入在头结点之后p = q;}}（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

一、（本题10分）（1）线性表和广义表的主要区别点是什么？已知广义表: C=(a,(b, (a,b)), ((a,b), (a,b))), 则tail(head(tail(C))) =？（2）满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？答：（1）线性表和广义表都是元素a1,a2,…,an 组成的序列，其主要区别点在于：在线性表中，ai 是单个元素（原子）；在广义表中，ai 可以是单个元素（原子），也可以是广义表。

tail(head(tail(C))) = ((a,b))（2）序列a1,a2,…,an 必须在数组（顺序表）中，且有序；时间复杂度为O(log n)。

二、（本题10分）证明：一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树。

证明：设一棵二叉树的先序序列和中序序列分别存放在一维数组A[1..n]和B[1..n]中。

因为先序序列的第一个结点A[1]为二叉树的根结点，在中序序列中找到与A[1]相同的结点，不妨假设B[i]=A[1]；又因为二叉树的任何一棵子树的结点是紧挨在一起的，故所构造的二叉树的左子树由先序序列A[2..i]和中序序列B[1..i-1]确定的二叉树组成，而所构造的二叉树的右子树由先序序列A[i+1..n]和中序序列B[i+1..n]确定的二叉树组成。

这是一个递归过程，当先序序列和中序序列分别含有3个以下的结点时，可惟一确定对应的二叉树。

因此，由一棵二叉树的先序序列和中序序列可以惟一确定这棵树。

三、（本题15分）某带权有向图如下：（1）写出深度优先搜索结点访问序列，并画出深度优先生成树；（当有多种选择时，编号小的结点优先。

）始点 51 11 32 23 3 1AC D E FBG 厦门大学《＿数据结构＿》课程期末试卷信息科学与技术学院计算机科学系2008年级＿＿＿专业主考教师：陈怡疆 庄朝晖 试卷类型：（B 卷）终点（2）写出该图的拓扑序列（当有多种选择时，编号小的结点优先。

平均查找长度详解1.顺序查找：从表的一端开始，顺序扫描线性表，依次将扫描到的节点关键字和给定值k相比较。

等概率条件下...平均查找长度：ASL = (n+....+2+1)/n= (n+1)/2。

2.二分法查找：前提是线性表是有序表。

假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

在等概率条件下...平均查找长度：ASL =（1/n）* ( j * 2^(j-1) )(j 是从1到h)，ASL = log2(n+1)-1。

原因：用二叉树来描述，树的高度d与节点树的关系为：n=(1+2+4+...... 2^(d-1))=2^d - 1；所以d = log2(n+1)，每一层只需要比较一次，所以最多需要比较log2(n+1)次。

3.分块查找：又称索引顺序查找，由分块有序（每一块中的关键字不一定有序，但是前一块中的最大关键字必须小于后一块中的最小关键字，即分块有序。

）的索引表和线性表组成。

例如把r【1....n】分为b 块，则前b-1 块节点数为 s = 【n/b】，最后一块允许小于或等于s。

索引表是一个递增有序表。

平均查找长度分为两部分，索引表的查找+块内的查找。

（索引表能够用二分法和顺序查找，块内无序，所以只能用顺序查找）如果以二分查找来确定块，则 ASL = log2(b+1)-1 + (s+1)/2。

如果以顺序查找来确定块，则 ASL = (b+1)/2 + (s+1)/2。

如果以哈希查找来确定块，则ASL=1 + (s+1)/2。

转载自：/jiary5201314/article/details/51125411。

查找一．选择题1．若查找每个元素的概率相等，则在长度为n 的顺序表上查找到表中任一元素的平均查找长度为_____________。

A. nB. n+1C. (n-1)/2D. (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，此时相当于顺序查找。

西北大学计算机专硕研究生入学考试历年真题集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY-西北大学2015年招收攻读硕士学位研究生试题(回忆版) 科目名称：数据结构科目代码：851适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。

一、简答 [每小题6分，共30分]1、简述四类基本的数据逻辑关系，并用图表示。

2、简述数组、广义表属于线性表原因。

3、算法的定义及特性。

4、什么是平衡二叉排序树平衡因子的取值范围是什么5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证明。

二、分析与方法选择 [每小题10分，共30分]1、折半查找法对待查找的列表哪两个要求？答：必须采用顺序存储结构；必须按关键字大小有序排列。

2、分析快速排序的性能（最好情况、最坏情况）。

3、关于二叉树结点度数的计算。

（牢记二叉树的5条性质，会计算二叉树及K叉树相关的计算。

）三、构造结果 [每小题8分，共40分]1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。

备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列，写出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。

但是2015年试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都没做过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯一的，但是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。

这道题具体我也不记得了，反正有点难，我也花了很长时间最后才做出来的。

2、图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生成树的生成。

3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。

4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。

5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法。

哈希表查找不成功怎么计算？解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！例如：散列函数为hash(x)=x MOD 13，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？地址：0 1 2 3 4 5 6 7 8 9 10 11 12数据： 39 1228154244 625－－ 36－ 38成功次数： 1 3 1 2 2 1 191 1不成功次数：98 7 65 4 3 2 1 1 2 110查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54说明：第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。

至少要查询多少次才能确认没有这个值。

（1）查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失败。

（2）查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失败。

（3）查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失败。

（4）查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失败。

（5）查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失败。

（6）查询hash(x)=5,至少要查询4次遇到表值为空的时候，才能确认查询失败。

（7）查询hash(x)=6,至少要查询3次遇到表值为空的时候，才能确认查询失败。

（8）查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失败。

（9）查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失败。

（10）查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失败。

（11）查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失败。

第八章选择题1. C2.A3.B4.C5.D6.B7.B8.A9.D 10.D 11.C 12.C填空题1.n、n+12. 43.8.25( 折半查找所在块 )4.左子树、右子树5.266.顺序、(n+1)/2、O(log2n)7.m-1、[m/2]-18.直接定址应用题1.进行折半查找时，判定树是唯一的，折半查找过程是走了一条从根节点到末端节点的路径，所以其最大查找长度为判定树深度[log2n]+1.其平均查找长度约为[log2n+1]-1.在二叉排序树上查找时，其最大查找长度也是与二叉树的深度相关，但是含有n个节点的二叉排序树不是唯一的，当对n个元素的有序序列构造一棵二叉排序树时，得到的二叉排序树的深度也为n，在该二叉树上查找就演变成顺序查找，此时的最大查找长度为n；在随机情况下二叉排序树的平均查找长度为1+4log2n。

因此就查找效率而言，二分查找的效率优于二叉排序树查找，但是二叉排序树便于插入和删除，在该方面性能更优。

3. 评价哈希函数优劣的因素有：能否将关键字均匀的映射到哈希表中，有无好的处理冲突的方法，哈希函数的计算是否简单等。

冲突的概念：若两个不同的关键字Ki和Kj，其对应的哈希地址Hash(Ki) =Hash(Kj)，则称为地址冲突，称Ki和K,j为同义词。

（1）开放定址法（2）重哈希法（3）链接地址法4.（1）构造的二叉排序树，如图（2）中序遍历结果如下：10 12 15 20 24 28 30 35 46 50 55 68（4）平均查找长度如下：ASLsucc = （1x1+2x2+3x3+4x3+5x3）/12 = 41/128.哈希地址如下：H(35) = 35%11 = 2H(67) = 67%11 = 1H(42) = 42%11 = 9H(21) = 21%11 = 10H(29) = 29%11 = 7H(86) = 86%11 = 9H(95) = 95%11 = 7H(47) = 47%11 = 3H(50) = 50%11 = 6H(36) = 36%11 = 3H(91) = 91%11 = 3第九章选择题1. D2.C3.B4.D5.C6.B7.A8.A9.D 10.D填空题1.插入排序、交换排序、选择排序、归并排序2.移动（或者交换）3.归并排序、快速排序、堆排序4.保存当前要插入的记录，可以省去在查找插入位置时的对是否出界的判断5.O(n)、O(log2n)6.直接插入排序或者改进了的冒泡排序、快速排序7.Log2n、n8.完全二叉树、n/29.1510.{12 38 25 35 50 74 63 90}应用题11.（1）Shell排序(步长为5 3 1)每趟的排序结果初始序列为100 87 52 61 27 170 37 45 61 118 14 88 32步长为5的排序14 37 32 61 27 100 87 45 61 118 170 88 52步长为3的排序结果14 27 32 52 37 61 61 45 88 87 170 100 118步长为1的排序结果14 27 32 37 45 52 61 61 87 88 100 118最后结果14 27 32 37 45 52 61 61 87 88 100 118 170（2）快速排序每趟的排序结果如图初始序列100 87 52 61 27 170 37 45 61 118 14 88 32第一趟排序[32 87 52 61 27 88 37 45 61 14]100[118 170]第二趟排序[14 27]32[61 52 88 37 45 61 87]100 118[170]第三趟排序14[27]32[45 52 37]61[88 61 87]100 118[170]第四趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]第五趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]最后结果14[27]32[37]45[52]61[61]87 88 100 118[170]（3）二路归并排序每趟的排序结果初始序列[100][87][52][61][27][170][37][45][61][118][14][88][32]第一趟归并[87 100][52 61][27 170][37 45][61 118][14 88][32]第二趟归并[52 61 87 100][27 37 45 170][14 61 88 118][32]第三趟归并排序[27 37 45 52 61 87 100 170][14 32 61 88 118]第四趟归并排序[14 27 32 37 45 52 61 61 87 88 100 118 170]最后结果14 27 32 37 45 52 61 61 87 88 100 118 17012.采用快速排序时，第一趟排序过程中的数据移动如图：算法设计题1.分析：为讨论方便，待排序记录的定义为（后面各算法都采用此定义）：#define MAXSIZE 100 /* 顺序表的最大长度，假定顺序表的长度为100 */ typedef int KeyType; /* 假定关键字类型为整数类型 */typedef struct {KeyType key; /* 关键字项 */OtherType other; /* 其他项 */}DataType; /* 数据元素类型 */typedef struct {DataType R[MAXSIZE+1]; /* R[0]闲置或者充当哨站 */int length; /* 顺序表长度 */}sqList; /* 顺序表类型 */设n个整数存储在R[1..n]中，因为前n-2个元素有序，若采用直接插入算法，共要比较和移动n-2次，如果最后两个元素做一个批处理，那么比较次数和移动次数将大大减小。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(2)ASL 成功 =(6*1+2*3+5+7)／10=24／10(3)ASL 失败=(4+3+2+1+2+1+1+2+1+9+8)／11=34／1 1。

计算方法参见上面58题(3)。

)解析：2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(2)装填因子=9／13=0．7 (3)ASL SUCC =11／9 (4)ASL UNSUCC =29／13)解析：3.设散列表长度为14i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2)求出在等概率情况下，查找成功的平均查找长度。

《数据结构》部分一、简答题（20 分，每题 5 分）1、请给出4 类常用的基本数据结构类型。

（课本p5第6行）答：根据数据元素之间关系的不同特征，通常有下列4类的基本结构：（1）集合。

（2）线性结构。

（3）树形结构。

（4）图状结构或网状结构。

2、什么是哈希表？（课本P253第2行）答：根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的、连续的地址集（区间）上，并以关键字在地址集上的“像”作为记录在表中的存储位置，这种表便称为哈希表。

3、请比较简单排序、快速排序、堆排序、归并排序的算法效率和稳定性。

（课本P289）（算法效率的概念P14；稳定性的概念P263;简单排序也就是除希尔排序之外的所有插入排序P265;快速排序P272;堆排序P279;归并排序P283）答：4、请比较普里姆算法与克鲁斯卡尔算法解决图最小生成树问题的时间复杂度。

(课本P175)(最小生成树：P173;普里姆算法P173;克鲁斯卡尔算法P175)答：普里姆算法的时间复杂度为O(n2)（假设网中有n个顶点），与网中的边数无关，因此适用于求边稠密的网的最小生成树。

而克鲁斯卡尔算法恰恰相反，它的时间复杂度为O(eloge)(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。

二、应用题（50 分）1、已知二叉树的前序遍历、中序遍历的结果分别是：ABDEFGCHIJ 和DBFEGAHCIJ，请画出对应的二叉树，给出后序遍历的结果，并将它转换成等价的树或森林。

（10 分）（二叉树的前序遍历、中序遍历P128；树P137；森林P138）答：2、某带权有向图及它的邻接表如下：(1)试写出它的深度优先搜索序列。

(深度优先搜索P167；邻接表P163；广度优先搜素P169)答：A-->B-->D-->C-->F-->E-->G--H（提示：不要画图，直接根据邻接表画）(2)根据普里姆(Prim)算法，求它的从顶点A 出发的最小生成树。

计算机学科专业基础综合数据结构-查找(一)(总分100,考试时间90分钟)一、单项选择题(下列每题给出的4个选项中，只有一个最符合试题要求)1. 对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素查找成功的平均查找长度为______。

A.n/2 B.(n+1)/2 C.(n-1)/2 D.n/42. 对线性表进行折半查找时，要求线性表必须______。

A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序3. 采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为______。

A.O(n)B.O(log2n)C.O(n2)D.O(nlog2n)4. 在对长度为n的顺序存储的有序表进行折半查找时，对应的二叉判定树的高度为______。

A．n B．C．D．5. 采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数______对应二叉判定树的高度(设高度≥2)。

A.小于 B.大于 C.等于 D.小于等于6. 已知有序顺序表(13，18，24，35，47，50，62，83，90，115，134)，当用折半查找法查找值为18的元素时，查找成功的数据比较次数为______。

A.1 B.2 C.3 D.47. 折半查找和二叉排序树的时间性能______。

A.相同 B.有时不相同 C.完全不同 D.不定8. m阶B树是一棵______。

A.m叉查找树 B.m叉高度平衡查找树 C.m-1叉高度平衡查找树 D.m+1叉高度平衡查找树9. 在10阶B树中根结点所包含的关键字个数最多为______，最少为1。

A.7 B.8 C.9 D.1010. 在一棵m阶B树的结点中插入新关键字时，若插入前结点的关键字数为______，则插入新关键字后该结点必须分裂为两个结点。

A.m B.m-1 C.m+1 D.m-211. 在一棵高度为h的B树中插入一个新关键字时，为查找插入位置需读取______个结点。

《数据结构与算法》考研真题精选一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A．(n-1)/2 B. n/2 C. (n+1)/2 D. n2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/23．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。

在此假定N为线性表中结点数，且每次查找都是成功的。

A.N+1B.2log2NC.logND.N/2E.Nlog2NF.N24. 下面关于二分查找的叙述正确的是( )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储5. 对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序6．适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序7. 用二分（对半）查找表的元素的速度比用顺序法( )A．必然快 B. 必然慢 C. 相等 D. 不能确定8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减9. 具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B. 4C. 2.5D. 510. 折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlog n）D. O（log n）11．当采用分快查找时，数据的组织方式为( )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在(（2）)时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

数据结构查找与排序练习题答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树，最低高度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 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.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。

数据结构简答题1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.7 在程序设计中，可采用下列三种方法实现输出和输入：(1) 通过scanf和printf语句；(2) 通过函数的参数显式传递；(3) 通过全局变量隐式传递。

试讨论这三种方法的优缺点。

解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。

(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。

(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。

2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

哈希表查找——成功和不成功时的平均查找长度以下求解过程是按照“计算机统考的计算方法”，不同的老师、教材在“处理冲突”上可能会有不同的方法，所以最主要的是掌握原理即可，对于考研的朋友最好掌握统考真题的解题方法。

题目例子：（2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题第一题）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。

散列表的存储空间是一个下标从0开始的一维数组。

散列函数为：H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

(1) 请画出所构造的散列表；(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

1.散列表：α= 表中填入的记录数/哈希表长度==> 哈希表长度= 7/0.7 = 10H(7) = (7x3) MOD 7 = 0H(8) = (8x3) MOD 7 = 3 H(30) = (30x3) M OD 7 = 6H(11) = (11x3) MOD 7 = 5 H(18) = (18x 3) MOD 7 = 5 H(9) = (9x3) MOD 7 = 6H(14) = ( 14x3) MOD 7 = 0按关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入。

0123456789714 8 11301892.查找长度： 2.1 查找成功的平均查找长度（待查找的数字肯定在散列表中才会查找成功）查找数字A的长度= 需要和散列表中的数比较的次数；步骤：比如查找数字：8则H(8) = (8x3) MOD 7 = 3哈希表中地址3处的数字为8，进行了第一次比较：8 = 8，则查找成功，查找长度为1；比如查找数字：14则H(14) = (14x3) MOD 7 = 0哈希表中地址0处的数字为7，进行第一次比较：7≠14哈希表中地址1处的数字为14，进行第二次比较：14=14 ，则查找成功，查找长度为2。