2020年春【中石油】数据结构第三次在线作业（100分）

skystar

【石油大学】数据结构-第三次在线作业
试卷总分:100    得分:100
第1题,1.（2.5分）下面结构中最适于表示稀疏无向图的是（）
A、邻接矩阵
B、逆邻接表
C、邻接多重表
D、十字链表
正确答案:


第2题,2.（2.5分）下列哪一种图的邻接矩阵是对称矩阵？（）
A、有向图
B、无向图
C、AOV网
D、AOE网
正确答案:


第3题,3.（2.5分）当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。
A、第j列所有元素之和
B、第i行所有元素之和
C、不确定
D、第j列所有元素之和+第i行所有元素之和
正确答案:


第4题,4.（2.5分）下面哪一方法可以判断出一个有向图是否有环（回路）：
A、深度优先遍历
B、拓扑排序
C、求最短路径
D、求关键路径
正确答案:


第5题,5.（2.5分）在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()
A、O(n)
B、O(n+e)
C、O(n²）)
D、O(n³）)
正确答案:


第6题,6.（2.5分）求解最短路径的Floyd算法的时间复杂度为()。
A、O（n）
B、O（n+c）
C、O（n*n）
D、O（n*n*n）
正确答案:


第7题,7.（2.5分）已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
A、V1,V3,V4,V6,V2,V5,V7
B、V1,V3,V2,V6,V4,V5,V7
C、V1,V3,V4,V5,V2,V6,V7
D、V1,V2,V5,V3,V4,V6,V7
正确答案:


第8题,8.（2.5分）在用邻接表表示图时，拓扑排序算法时间复杂度为()。
A、O(n)
B、O(n＋e)
C、O(n*n)
D、O(n*n*n)
正确答案:


第9题,9.（2.5分）关键路径是事件结点网络中（）。
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长回路
D、最短回路
正确答案:


第10题,10.（2.5分）下面关于求关键路径的说法不正确的是（）。
A、求关键路径是以拓扑排序为基础的
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D、关键活动一定位于关键路径上
正确答案:


第11题,11.（2.5分）下列关于AOE网的叙述中，不正确的是（）。
A、关键活动不按期完成就会影响整个工程的完成时间
B、任何一个关键活动提前完成，那么整个工程将会提前完成
C、所有的关键活动提前完成，那么整个工程将会提前完成
D、某些关键活动提前完成，那么整个工程将会提前完成
正确答案:


第12题,12.（2.5分）对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()
A、（N+1）/2
B、N/2
C、N
D、[（1+N）*N ]/2
正确答案:


第13题,13.（2.5分）下面关于二分查找的叙述正确的是()
A、表必须有序，表可以顺序方式存储，也可以链表方式存储
B、表必须有序且表中数据必须是整型，实型或字符型
C、表必须有序，而且只能从小到大排列
D、表必须有序，且表只能以顺序方式存储
正确答案:


第14题,14.（2.5分）折半查找的时间复杂性为（）
A、O（n²）
B、O（n）
C、O（nlogn）
D、O（logn）
正确答案:


第15题,15.（2.5分）当采用分快查找时，数据的组织方式为()
A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
正确答案:


第16题,16.（2.5分）既希望较快的查找又便于线性表动态变化的查找方法是()
A、顺序查找
B、折半查找
C、索引顺序查找
D、哈希法查找
正确答案:


第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)
正确答案:


第18题,18.（2.5分）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。
A、LL
B、LR
C、RL
D、RR
正确答案:


第19题,19.（2.5分）下列关于m阶B-树的说法错误的是()
A、根结点至多有m棵子树
B、所有叶子都在同一层次上
C、非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树
D、根结点中的数据是有序的
正确答案:


第20题,20.（2.5分）下面关于m阶B树说法正确的是()①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字;③所有叶子在同一层上;④当插入一个数据项引起B树结点分裂后，树长高一层。
A、①②③
B、②③
C、②③④
D、③
正确答案:


第21题,21.（2.5分）下面关于B和B+树的叙述中，不正确的是()
A、B树和B+树都是平衡的多叉树
B、B树和B+树都可用于文件的索引结构
C、B树和B+树都能有效地支持顺序检索
D、B树和B+树都能有效地支持随机检索
正确答案:


第22题,22.（2.5分）设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。
A、1
B、2
C、3
D、4
正确答案:


第23题,23.（2.5分）下面关于哈希(Hash，杂凑)查找的说法正确的是()
A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B、除留余数法是所有哈希函数中最好的
C、不存在特别好与坏的哈希函数，要视情况而定
D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
正确答案:


第24题,24.（2.5分）关于杂凑查找说法不正确的有几个()（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集
A、1
B、2
C、3
D、4
正确答案:


第25题,25.（2.5分）设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()
A、8
B、3
C、5
D、9
正确答案:


第26题,26.（2.5分）假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()
A、k-1次
B、k次
C、k+1次
D、k（k+1）/2次
正确答案:


第27题,27.（2.5分）某内排序方法的稳定性是指()。
A、该排序算法不允许有相同的关键字记录
B、该排序算法允许有相同的关键字记录
C、平均时间为0（n log n）的排序方法
D、以上都不对
正确答案:


第28题,28.（2.5分）下面给出的四种排序法中()排序法是不稳定性排序法。
A、插入
B、冒泡
C、二路归并
D、堆积
正确答案:


第29题,29.（2.5分）下列排序算法中，其中（）是稳定的。
A、堆排序，冒泡排序
B、快速排序，堆排序
C、直接选择排序，归并排序
D、归并排序，冒泡排序
正确答案:


第30题,30.（2.5分）若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。
A、直接插入
B、直接选择
C、堆
D、快速
E、基数
正确答案:


第31题,31.（2.5分）若需在O(nlog₂n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A、快速排序
B、堆排序
C、归并排序
D、直接插入排序
正确答案:


第32题,32.（2.5分）下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。()
A、选择排序法
B、插入排序法
C、快速排序法
D、堆积排序法
正确答案:


第33题,33.（2.5分）在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。
A、直接插入排序
B、气泡排序
C、快速排序
D、直接选择排序
正确答案:


第34题,34.（2.5分）下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。
A、.快速排序
B、shell排序
C、堆排序
D、冒泡排序
正确答案:


第35题,35.（2.5分）一组记录的关键码为（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)
正确答案:


第36题,36.（2.5分）在下面的排序方法中，辅助空间为O（n）的是()。
A、希尔排序
B、堆排序
C、选择排序
D、归并排序
正确答案:


第37题,37.（2.5分）就平均性能而言，目前最好的内排序方法是()排序法。
A、冒泡
B、希尔插入
C、交换
D、快速
正确答案:


第38题,38.（2.5分）散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。
A、散列函数
B、除余法中的质数
C、冲突处理
D、散列函数和冲突处理
正确答案:


第39题,39.（2.5分）下述文件中适合于磁带存储的是（）。
A、顺序文件
B、索引文件
C、散列文件
D、多关键字文件
正确答案:


第40题,40.（2.5分）ISAM文件和VASM文件属于（）。
A、索引非顺序文件
B、索引顺序文件
C、顺序文件
D、散列文件
正确答案: