数据结构第三单测验答案.docVIP

数据结构第三次单元测验答案 一、 选择题 1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 2.适用于折半查找的表的存储方式及元素排列要求为 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度 A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。 A35/12 B.37/12 C.39/12 D.43/12 5.折半查找的时间复杂性为（ ） A. O（n2） B. O（n） C. O（nlogn）D. O（logn） 6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（ ） A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，3 7.设有序表的关键字序列为 1，4，6，10，18，35，42，53，67，71，78，84，92，99 ，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。 A.2 B. 3 C. 4 D.12 8.用n个键值构造一棵二叉排序树，最低高度为（ ） A.n/2 B.、n C.logn D.logn+1 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.设有一组记录的关键字为 19，14，23，1，68，20，84，27，55，11，10，79 ，用链地址法构造散列表，散列函数为H（key） key% 13,散列地址为1的链中有（ ）个记录。 A．1 B. 2 C. 3 D. 4 11.已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除出一个记录，正确的做法是 ） A.将该元素所在的存储单元清空。 B.将该元素用一个特殊的元素代替 C.将与该元素有相同Hash地址的后继元素顺次前移一个位置。 D.用与该元素有相同Hash地址的最后插入表中的元素替代。 12.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？ A．k-1次 B. k次C. k+1次D. k（k+1）/2次 13.散列表的地址区间为0-17,散列函数为H K K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的地址是（ ）。 A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要有哪些信誉好的足球投注网站的次数是（ ）。 A． 2 B. 3 C. 4 D. 5 14.将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会 15.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K） K %7作为散列函数，则散列地址为0的元素有（ ）个。 A.1 B.2 C.3 D.4 16.下列排序方法中，哪一个是稳定的排序方法？（ 　） A．直接选择排序 B．直接插入排序 C．希尔排序 D．快速排序 17.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。 A.直接插入排序 B.气泡排序 C. 快速排序 D.直接选择排序 18.比较次数与排序的初始状态无关的排序方法是 。 A.直接插入排序 B.起泡排序 C.快速排序 D.简单选择排序 19.对序列 15，9，7，8，20，-1，4 进行排序，进行一趟后数据的排列变为 4，9，-1，8，20，7，15 ；则采用的是（ ）排序。 A.选择 B.快速 C.希尔 D.冒泡 20.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 A. 38,40,46,56,79,84 B. 40,38,46,79,56,84 C. 40,38,46,56,79,84 D. 40,38,46,84,56,79