商大计算机专业天津商业练习

1、练习九数据结构Data Structure11.A)B)C)D)成功的折半查找其时间复杂度为 。O(log2n) O(log2n/2) O(n)O(n/2)Data Structure2数据结构2.A)B)C)D)成功的折半查找所需最少时间为。O(1)O(2) O(n-1) O(n+1)Data Structure3数据结构3.A)B)C)D)）是指 。在使用散列法时，碰撞（不同的关键码值对应到相同的两个元素具有相同序号地址两个元素的关键码值不同，而非码属性相同负载因子太大Data Structure4数据结构4.从理论上讲，将数据以 结构存放，则查找一个数据所用时间不依赖于数据的个数。散列二

2、叉查找树链表 二叉树A)B)C)D)Data Structure5数据结构5.A)B)C)D)对线性表采用折半查找法，该线性表必须。采用顺序采用顺序采用链式采用链式结构，且元素按值有序结构结构结构，且元素按值有序Data Structure6数据结构6.设哈希表长m=14,哈希函数H(key)=key%11。表中已有4个结点: addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7其余地址为空，如用二次探测再散列处理为49的结点的地址是。，关键字A）8B）9 C）5 D）3Data Structure7数据结构7.采用顺序查找方法查找长度为n的线性表时,每

3、个元素的平均查找长度为 。n/2 (n+1)/2n(n-1)/2A)B)C)D)Data Structure8数据结构8.有一个有序表(2，5，9，14，36，54，68，72，77， 82，95，99)，当采用折半查找值为82的结点时， 次比较后查找成功。2468A)B)C)D)Data Structure9数据结构9.性表的散列中，添装因子是哈希表装满程度的标志。若用m表示哈希表的长度，n表示待元素的个数，则等于 。m/n n/m m/(n-1)(n-1)/mA)B)C)D)Data Structure10数据结构10.设哈希表的表长为14，哈希函数为H(key)=key%13，表中已有4

4、个结点: H(15)=2, H(16)=3, H(43)=4,H(83)=5，其余地址为空，如用二次探测再散列处理冲突，关键字为28的结点的地址是 。0167A)B)C)D)Data Structure11数据结构11.A)B)C)D)结构的是。以下术语，不属于顺序表有序表 Hash表单链表Data Structure12数据结构12.中，下面不是处理性表的散列方法。开放地址法再哈希法 折半查找法公共溢出区法的A)B)C)D)Data Structure13数据结构13.A)以下说法错误的是。哈希址的基本是由关键字的值决定数据的地B)填装因子是哈希法的一个重要参数，它反映哈希表的填装程度哈希表

5、的结点中只包含数据元素本身的信息，不包含任何指针哈希表的查找效率主要取决于哈希表构造时选取的哈希C)D)函数和处理的方法Data Structure14数据结构14.A)B)C)D)下面不是静态查找表的表示方法。顺序表有序表线性表静态树表Data Structure15数据结构15.A)B)C)D)下面是动态查找表的表示方法。顺序表散列表平衡二叉树静态树表Data Structure16数据结构16.A)B)C)D)动态查找表的表示方法是。顺序表 散列表 静态树表二叉排序树Data Structure17数据结构二、判断题1.2.查找表中数据元素的任何数据项都可以作为关键字。动态查找表适合用于

6、检索与修改(行的场合。Hash表的平均查找长度与处理和删除)交叉进3.4.的方法无关。折半查找法的查找速度一定比顺序查找法快。(注意特例)5.二叉树排序树中下面。一个新结点，总是到叶结点6.二叉树排序树删除一个结点后，仍是二叉树排序树。Data Structure18数据结构三、填空题1.由1000个数据元素组成的有序表，假设比较表中一个元素所需时间为0.5毫秒，则顺序查找时，平均查找一个元素的时间约为毫秒。2502.设线性表（a1,a2,a500）中所有元素的值由小到大排列，对一个给定的值k，用二分法查找表中与k相等的元素，在查找不成功的情况下，至多需要比较次。9Data Structure

7、19数据结构三、填空题3.在用散列表进行检索时，处理的方法有几种，它们是、再哈希法、链地址法和建立公共溢出区法。开放地址法在用散列表进行检索时，处理4.的方法有几种，它们是开放地址法、再哈希法、和建立公共溢出区法。链地址法数据结构Data Structure20三、填空题5.查找表按其所包含的不同运算，可以分为找表和动态查找表。查静态6.查找表按其所包含的不同运算，可以分为静态查找表和查找表。动态Data Structure21数据结构三、填空题7.在关键字序列（07，12，15，18，27，32，41，92）中用二分法查找和给定值07相等的关键字时，查找过程中依次和“07”比较的关键字是。1

8、812078.以折半查找方法查找一个线性表时，此线性表必须是顺的表 。序有序Data Structure22数据结构三、填空题在索引查找方法中，首先查找，然后再查对应的块。索引对一棵二叉排序树进行中序遍历时，得到的结点序一个 。有序序列找相列是数据结构Data Structure23三、填空题以顺序查找方法从长度为n的线性表中查找一个元时间复杂度为 。O(n)素的数据结构Data Structure24四、应用题1简述顺序查找法、折半查找法和索引顺序表查找法对查找表中元素的要求，每种查找法对长度为n的表的等概平均查找长度是多少？被率数据结构Data Structure25四、应用题1参考：(1

9、)顺序查找：表中元素可以任意存放，查找成功平均查找长度为( n+1)/2折半查找：表中元素必须以关键字值的升序或降序进行有序排列，并且只能存放在顺序表中。查找成功平均查找长度为log2( n+1)-1。索引查找：索引表有两部分组成，一个索引表和一个顺序表。顺序表中元素被划分成一些子表（块），子表内数据不要求有序；但对于任意两个子表块来说，(2)(3)排面的子表中的任意数据的键值不能大于或小于排在后面的子表中的所有数据元素的键值。若用顺序查找确定所在的块，每块含s个元素。平均查找长度为( n/s+ s)/2+1。Data Structure26数据结构四、应用题1已知一个散列表如下图所示：其散列

10、函数为H(key)=key%13，即d0=H(key)；处理的方法为双重散列法，探查序列为： di=(H(key)+i*H1(key)%13，i=1,2,12其中 H1(key)=key%11+1，回答下列问题：(1)写出对表中关键字8，15，21和34进行查找时的操作过程，所需进行的比较次数各为多少？该散列表在等概率查找时查找成功的平均查找长度为多少？(2)23456789101112数据结构Data Structure27四、应用题： di=(H(key)+i*H1(key)%13, i=1,2,12参考8 ： d0=H(8)=8, d1=(8+1*(8%11+1)%13 =4,查找成功，

11、比较2次。15：d0=H(15)=2, 查找成功，比较1次。21：d0=H(21)=8, 查找成功，比较1次。34：d0=H(34)=8, d1=(8+1*(34%11+1)%13=10,d2=(8+2*(34%11+1)%13=12,查找成功，比较3次。23：d0=H(23)=10，查找成功，比较1次AVL=(2+1+1+1+3)/5=1.623456789101112Data Structure28数据结构四、应用题2. 设散列函数为H(k)=k%7，散列表的地址空间为0-6；对关键字序列32，13，49，55，22，38，21按线性探测法解决的方法构造散列表，并查找每个关键字要进行几次比

12、较？参考散列表Data Structure29数据结构比较次数关关键字552238322113比较次数1321161495522383221五、编程用折半查找法在有序表ST中查找某一关键值，若找到，则返回该元素在顺序表中的位置；否则，返回0。请用C语言编制实现该算法的函数。有序表的结点类型定义为：typedef structKeyType key; Element; typedef struct Element *elem;length; SSTable;函数首部为：Search_Bin(SSTable ST, KeyType key)Data Structure30数据结构五、编程参考：Search_Bin(SSTable ST, KeyT