《【石油大学】数据结构第三次在线作业》由会员分享，可在线阅读，更多相关《【石油大学】数据结构第三次在线作业（8页珍藏版）》请在金锄头文库上搜索。
1、【石油大学】数据结构-第三次在线作业试卷总分:100 得分:100第1题,1.（2.5分）下面结构中最适于表示稀疏无向图的是（）A、邻接矩阵B、逆邻接表C、邻接多重表D、十字链表正确答案:C第2题,2.（2.5分）下列哪一种图的邻接矩阵是对称矩阵？（）A、有向图B、无向图C、AOV网D、AOE网正确答案:B第3题,3.（2.5分）当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。A、第j列所有元素之和B、第i行所有元素之和C、不确定D、第j列所有元素之和+第i行所有元素之和正确答案:B第4题,4.（2.5分）下面哪一方法可以判断出一个有向图是否有环（回路）：A、深度优先遍历B、拓扑排
2、序C、求最短路径D、求关键路径正确答案:B第5题,5.（2.5分）在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()A、O(n)B、O(n+e)C、O(n2）)D、O(n3）)正确答案:B第6题,6.（2.5分）求解最短路径的Floyd算法的时间复杂度为()。A、O（n）B、O（n+c）C、O（n*n）D、O（n*n*n）正确答案:D第7题,7.（2.5分）已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（）。A、V1,V3,V4,V6,V2,V5,V7B、V1,V3,V2,V6,V4,V5,V7C、V1,V3,V4,V5,V2,
3、V6,V7D、V1,V2,V5,V3,V4,V6,V7正确答案:A第8题,8.（2.5分）在用邻接表表示图时，拓扑排序算法时间复杂度为()。A、O(n)B、O(ne)C、O(n*n)D、O(n*n*n)正确答案:B第9题,9.（2.5分）关键路径是事件结点网络中（）。A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长回路D、最短回路正确答案:A第10题,10.（2.5分）下面关于求关键路径的说法不正确的是（）。A、求关键路径是以拓扑排序为基础的B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续
4、时间的差D、关键活动一定位于关键路径上正确答案:C第11题,11.（2.5分）下列关于AOE网的叙述中，不正确的是（）。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，那么整个工程将会提前完成C、所有的关键活动提前完成，那么整个工程将会提前完成D、某些关键活动提前完成，那么整个工程将会提前完成正确答案:B第12题,12.（2.5分）对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()A、（N+1）/2B、N/2C、ND、（1+N）*N /2正确答案:A第13题,13.（2.5分）下面关于二分查找的叙述正确的是()A、表必须有序，表可以顺序方式
5、存储，也可以链表方式存储B、表必须有序且表中数据必须是整型，实型或字符型C、表必须有序，而且只能从小到大排列D、表必须有序，且表只能以顺序方式存储正确答案:D第14题,14.（2.5分）折半查找的时间复杂性为（）A、O（n2）B、O（n）C、O（nlogn）D、O（logn）正确答案:D第15题,15.（2.5分）当采用分快查找时，数据的组织方式为()A、数据分成若干块，每块内数据有序B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D、数据分成若干块，每块（除最后一块外）中数据个
6、数需相同正确答案:B第16题,16.（2.5分）既希望较快的查找又便于线性表动态变化的查找方法是()A、顺序查找B、折半查找C、索引顺序查找D、哈希法查找正确答案:C第17题,17.（2.5分）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()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)正确答案:C第18题,18.（2.5分）在平衡二叉树中插入一个结点后造成了不平衡，设最低的
7、不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A、LLB、LRC、RLD、RR正确答案:C第19题,19.（2.5分）下列关于m阶B-树的说法错误的是()A、根结点至多有m棵子树B、所有叶子都在同一层次上C、非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树D、根结点中的数据是有序的正确答案:D第20题,20.（2.5分）下面关于m阶B树说法正确的是()每个结点至少有两棵非空子树；树中每个结点至多有m一1个关键字;所有叶子在同一层上;当插入一个数据项引起B树结点分裂后，树长高一层。A、B、C、D、正确答案:B第21题,21.（2.
8、5分）下面关于B和B+树的叙述中，不正确的是()A、B树和B+树都是平衡的多叉树B、B树和B+树都可用于文件的索引结构C、B树和B+树都能有效地支持顺序检索D、B树和B+树都能有效地支持随机检索正确答案:C第22题,22.（2.5分）设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。A、1B、2C、3D、4正确答案:D第23题,23.（2.5分）下面关于哈希(Hash，杂凑)查找的说法正确的是()A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留
9、余数法是所有哈希函数中最好的C、不存在特别好与坏的哈希函数，要视情况而定D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可正确答案:C第24题,24.（2.5分）关于杂凑查找说法不正确的有几个()（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A、1B、2C、3D、4正确答案:B第25题,25.（2.5分）设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个
10、，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()A、8B、3C、5D、9正确答案:D第26题,26.（2.5分）假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A、k-1次B、k次C、k+1次D、k（k+1）/2次正确答案:D第27题,27.（2.5分）某内排序方法的稳定性是指()。A、该排序算法不允许有相同的关键字记录B、该排序算法允许有相同的关键字记录C、平均时间为0（n log n）的排序方法D、以上都不对正确答案:D第28题,28.（2.5分）下面给出的四种排序法中()排序法是不稳定性排序法。A、插入B、
11、冒泡C、二路归并D、堆积正确答案:D第29题,29.（2.5分）下列排序算法中，其中（）是稳定的。A、堆排序，冒泡排序B、快速排序，堆排序C、直接选择排序，归并排序D、归并排序，冒泡排序正确答案:D第30题,30.（2.5分）若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。A、直接插入B、直接选择C、堆D、快速E、基数正确答案:A第31题,31.（2.5分）若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A、快速排序B、堆排序C、归并排序D、直接插入排序正确答案:C第32题,32.（2.5分）下面给出的四种排序方法中，排序
12、过程中的比较次数与排序方法无关的是。()A、选择排序法B、插入排序法C、快速排序法D、堆积排序法正确答案:A第33题,33.（2.5分）在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A、直接插入排序B、气泡排序C、快速排序D、直接选择排序正确答案:D第34题,34.（2.5分）下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。A、.快速排序B、shell排序C、堆排序D、冒泡排序正确答案:B第35题,35.（2.5分）一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A、(38,40,4
13、6,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)正确答案:C第36题,36.（2.5分）在下面的排序方法中，辅助空间为O（n）的是()。A、希尔排序B、堆排序C、选择排序D、归并排序正确答案:D第37题,37.（2.5分）就平均性能而言，目前最好的内排序方法是()排序法。A、冒泡B、希尔插入C、交换D、快速正确答案:D第38题,38.（2.5分）散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。A、散列函数B、除余法中的质数C、冲突处理D、散列函数和冲突处理正确答案:D第39题,39.（2.5分）下述文件中适合于磁带存储的是（）。A、顺序文件B、索引文件C、散列文件D、多关键字文件正确答案:A第40题,40.（2.5分）ISAM文件和VASM文件属于（）。A、索引非顺序文件B、索引顺序文件C、顺序文件D、散列文件正确答案:B
