资源描述：
《数据结构第三单元测验答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构第三次单元测验答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()A．（N+1）/2B.N/2C.ND.[（1+N）*N]/22.适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()A．必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情
2、况下查找成功所需的平均比较次数为（）。A．35/12B.37/12C.39/12D.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/
3、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的链中有（）个记录。A．1B.2C.3D.411.已知一采用开放地址
4、法解决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)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1
5、）元素59存放在散列表中的地址是（）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（）。A．2B.3C.4D.514.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A.一定会B.一定不会C.仍可能会第5页共5页15.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（）个。A.1B.2C.3D.416.下列排序方法中，哪一个是稳定的排序方法？（ ）A．直接选择排序B．直接插入排序C．希尔排序D．快速排序17.在下列排序算法中,哪一个算法的时间复杂度与初始排
6、序无关（）。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
7、,46,56,79,84)D.(40,38,46,84,56,79)21.就平均性能而言，目前最好的内排序方法是()排序法。A.冒泡B.希尔插入C.交换D.快速22．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。A.插入B.选择C.希尔D.快速23.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,4
