中原有的关键字的个数是__________。 【中国科技大学 1998 一、5 （3分）】【南京理工大学 2001 二、4 （3分）】
9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。【南京理工大学 2000 二、7 （4.5分）】
10. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把结点按查找码转换为地址进行
存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。 【青岛大学 2000 六、2 （2分）】 11. 平衡二叉树又称__________，其定义是__________。【青岛大学 2001 六、3 （3分）】
12. 在哈希函数H（key）=key%p中，p值最好取__________。【青岛大学 2002 三、9 （2分）】
13. 对于长度为255的表，采用分块查找，每块的最佳长度为__________。【青岛大学 2002 三、10 （2分）】
14. 在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。【中国科技大学 1998 一、4 （3分）】
15．有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。【中国矿业大学 2000 一、6 （3分）】
16．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。
【西安电子科技大学2001软件一、7 （2分）】
17. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好：若分成25块，其平均查找长度为__________。【北京工业大学 1999 一、 5 ( 2分)】
18. 执行顺序查找时，储存方式可以是__(1)__，二分法查找时，要求线性表__(2)__，分块查找时要求线性表 __(3)__，而散列表的查找，要求线性表的存储方式是 __(4)__。【山东大学 1998 一 、1 (3分)】
19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序
树检索时，平均比较次数为__________。 【山东大学 1999 二、1 (４分)】 20. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树
中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。【山东大学 1999 二、２ (４分)】
21. 平衡因子的定义是__________【北京轻工业学院 2000 一、2 （2分）】 22. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)__查找，__(2)__查找和
__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。【华北计算机系统工程研究所 1999 一 （5分）】
23. __________法构造的哈希函数肯定不会发生冲突。【重庆大学 2000 一、3】 24. 具有N个关键字的B树的查找路径长度不会大于__________。【中科院计算机 1999 二、2】
25. 在一棵有N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况
平均时间复杂度）为________ 。 【西南交通大学 2000 一、8】
26. 假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做__________次插入和探测操作。【武汉大学 2000 一、8】
27. 高度为8的平衡二叉树的结点数至少有__________个。【武汉大学 2000 一、6】 28. 高度为5（除叶子层之外）的三阶B-树至少有__________个结点。【武汉大学 2000 一、4】
29. 假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度
为__________
【燕山大学 2001 二、4 （3分）】
30. 可以唯一的标识一个记录的关键字称为__________。【燕山大学 1998 一、7 （1分）】 31. 已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。【燕山大学 1998 一、8 （2分）】 32. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。
【厦门大学 2001 一、3 （14%/5分）】
33. 对于具有144 个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________.
【北方交通大学 2001 二、8】
34. 127阶B-树中每个结点最多有__(1)__个关键字；除根结点外所有非终端结点至少有__(2)__棵子树；65阶B+树中除根结点外所有结点至少有__(3)__个关键字；最多有__(4)__棵子树；【北方交通大学 1999 二、5 （4分）】 35. 若静态查找表的类型定义如下：
TYPE rectype=RECORD key：keytype； ??； END； ordlisttp=ARRAY[1..n] OF rectype； 请完成以下二分查找的算法：
FUNC binsrch（r：ordlisttp；k：keytype）：integer； BEGIN low:=1；hig:=n；suc:=false； WHILE ___(1)___ AND NOT（suc）DO [ mid：=__(2)____；
CASE
k>r[mid].key：low:=mid+1； k=r[mid].key：suc:=true； k IF suc THEN __(3)__ ELSE __(4)__ END； 【福州大学 1998 二、8 (2分)】 36. 顺序查找 FUNC seq(a,n,k):integer; BEGIN I:=1; A[n+1]= __(1)____; WHILE a[I]<>k DO I:=I+1; IF __(2)___ THEN return(I) ELSE return(0); END; 【中山大学 1998 四、4 (4分)】 37. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。(C语言，PASCAL语言的考生不填） #define N /*学生人数*/ int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/ { int head=1,mid,rear=N; do {mid=(head+rear)/2; if(x<=a[mid]) __(1)__ else __(2)__; }while(__(3)__); if (a[head] return head; } 【西南交通大学 2000 一、12】 38. 假设root是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树root中查找值为k 的结点；若值为k的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置success 为“真”；若值为k的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置success为“假”。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点， 既是根结点，也是叶子结点。 #include typedef struct node { int key; struct node *left， *right; } node; node *root; int k，success; void del_leaf(node **t, int k, int *sn) { node *p, *pf; p=*t; *sn=0; while(_（1）_&&!*sn) if (k==p->key) *sn =1; else { _（2）_; if (k if (*sn && p->left==NULL && p->right==null) { if (_（3）_ ) if (pf->left ==p ) pf ->left=null; else pf->right=null; else _（4）_ ; free(p); } else *sn=0; /*call form :del_leaf( &root, k, &success);*/ 【上海大学 1999 一、2 （8分）】 四、应用题 1. 名词解释： 哈希表【燕山大学 1999 一、4（2分）】【哈尔滨工业大学 1999 一、3 （3分）】【首都经贸大学 1997 一、2 （4分）】 同义词： 【山东大学 1998 二、1 (2分)】【山东工业大学 2000 二、1 （2分）】 叙述B-树定义，主要用途是什么？它和B+树的主要差异是什么？【青岛大学 2001 五 （5分）】 B-树【南开大学 1996 五、4 (3分) 1998 五、4 (4分) 2000 二、2 （2）】【山东大学 2000 三 ( 8分)】 平衡二叉树（AVL树）？【南开大学 1996 五 、3 (3分) 1998 五、3 (4分)】【厦门大学 1998 四、2 （5分）】 平衡因子【西北工业大学 1999 一、2 (3分)】 平均查找长度（ASL）【西北工业大学 1999 一 、3 (3分)】 trie树。【中山大学 1997 一、3 （3分）】 2. 回答问题并填空 （1）（2分）散列表存储的基本思想是什么？ （2）（4分）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？ （3）（４分）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方 法？他们各有何特点？ （4）（３分）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？ （5）（２分）散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。 【山东工业大学 1999 四（15分）】 3. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。 【南京航空航天大学 1996 九、2 （6分）】 4．HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？ 【中国人民大学 2000 一、4 （4分）】 5．在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？ 【西安电子科技大学2000计应用一、8 （5分）】 6. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表 长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。【东北大学 2002 二 、2 （5分）】 7. 对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探 测再散列方法解决冲突，做： （1）设计哈希函数； （2）画出哈希表； （3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法； 【东北大学 2001 六 (18分)】 8. 设哈希表a 、b分别用向量a[0..9],b[0..9]表示 ，哈希函数均为H（key）=key MOD 7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。【北京工业大学 1998 三 (8分)】 9. 采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。 【北京工业大学 2000 三 (8分)】 10. 设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=key MOD 13， 即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。【南京理工大学 1996 三、3 （5分）】 11. 设散列表长度为14 ，散列函数h(x)=?，其中 i为健值中第一个字母在字母表中 的序号，若健值的输入顺序为Jan, Feb, Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用拉链法处理冲突，要求： （1）构造散列表 （2）求出在等概率情况下，查找成功的平均查找长度。【厦门大学 2001 二、2 （24%/3分）】 12. 常用的构造哈希函数的方法有哪些？若在哈希表中删除一个记录，应如何操作？为什么？已知一组关键字为（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数 H(Key)=Key MOD 13和线性探测再散列处理冲突的方法在地址空间A[0..15]中构造哈希表。【燕山大学 1999 八 （14分）】 13. 设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。【北方交通大学 1998 三 （18分）】 14. 使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。 （1）使用线性探查再散列法来构造散列表。（5分） （2）使用链地址法构造散列表。（5分） 针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。（5分） 【清华大学 1998 五（15分）】 15. 已知长度为12 的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec) (1) 试按表中元素的顺序依次插入一棵初始为空的分类二叉树，试画出插入完成之后 的分类二叉树并计算其在等概率查找情况下，查找成功的平均查找长度。 (2) 试用以下两种方法构造两个Hash表，Hash函数H(K)=[i/2],其中i为关键字K中 第一个字母在字母表中的序号，[x]表示取整数。 a. 用线性探测开放定址法处理冲突(散列地址空间为0～16); b. 用链地址法处理,然后分别求出这两个Hash表在等概率查找情况下，查找成功的平均查找长度。 【上海海运学院 1996 五 （15分）】 222 16. 设散列函数为H（K）=K MOD 13，给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49，画出用链地址法处理冲突构造得的哈希表。【福州大学 1998 三、3 (6分)】 17. 设散列函数H(k)=K mod 7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计应用 一、5 （5分）】 18. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。 【大连海事大学2001 八 (10分)】 19. 设散列函数为H(K)=K MOD 11,解决冲突的方法为链接法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到散列表中（画出散列表的示意图）。并计算平均查找长度ASL。【首都经贸大学 1997 三 （10分）】 20. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。 【合肥工业大学 2000 四、3 （5分）】 21. 设输入的关键字序列为：22,41,53,33,46,30,13,01,67, Hash函数为：H（key）=key MOD 11。HASH表长度为11。试用线性探测法解决冲突，将各关键字按输入顺序填入Hash表中。【南京航空航天大学 1998 二 （10分）】 22. 设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题： (1) 画出哈希表示意图； (2) 若查找关键字63，需要依次与哪些关键字比较? (3) 若查找关键字60，需要依次与哪些关键字比较? (4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999 三 （10分）】 23. 试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过 2.0。并请验证你造的哈希表的实际平均查找长度是否满足要求。（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG） 【清华大学 1996 五】 24. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现： ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。 （1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。 写出上述各关键字在表中位置。【南开大学 1998 六 (10分)】 25. 对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT)，哈希函数为H（K）=（关键字中第一个字母在字母表中的序号）MOD 7，用线性探测法处理冲突，求构造一个装填因子为0.7的哈希表;并分别计算出在等概率情况下查找成功与不成功的平均查找长度。【西北大学 2000 二、3 (5分)】 26. 设散列表为HT [0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为： H0(key)=key % 13; 注:%是求余数运算(=mod) Hi=(Hi-1+REV(key+1)+1) % 13; i=1,2,3,?,m-1 其中，函数REV（x）表示颠倒10进制数x的各位，如REV（37）=73，REV（7）=7等。若插入的关键码序列为(2,8,31,20,19,18,53,27)。 (1)(8分)试画出插入这8个关键码后的散列表；(2)(5分)计算搜索成功的平均搜索长度ASL。【清华大学2000八(13分）】 27. 设一个散列表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键码{10,100,32,45,58,126,3,29,200,400,0}散列到表中。 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构考研习题-第九章集合(2)在线全文阅读。
相关推荐：