您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 期末复习题_数据结构
1中国石油大学(北京)远程教育学院期末复习题一、选择题(本大题共15小题,每小题2分,共30分)1.以下与数据的存储结构无关的术语是()A、循环队列B、链表C、哈希表D、栈2.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()A、110B、108C、100D、1203.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是()A、head==NULLB、head–next==NULLC、head–next==headD、head!=NULL4.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是()A、2,4,3,1,5,6B、3,2,4,1,6,5C、4,3,2,1,5,6D、2,3,5,1,6,45.下列关键字序列中,构成小根堆的是()A、{12,21,49,33,81,56,69,41}B、{81,69,56,49,41,33,21,12}C、{81,49,69,41,21,56,12,33}D、{12,21,49,33,81,41,56,69}6.下列数据结构中,不属于二叉树的是()A、B树B、AVL树C、二叉排序树D、哈夫曼树7.用顺序存储的方法来存储一棵二叉树,存放在一维数组A[1..N]中,若结点A[i]有右孩子,则其右孩子是()。A、A[2i]B、A[2i-1]C、A[2i+1]D、A[i/2]8.设树T的高度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中叶子数为()2A、5B、6C、7D、89.有数据{53,30,37,12,45,24,96},从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择下面哪个序列输入()A、45,24,53,12,37,96,30B、37,24,12,30,53,45,96C、12,24,30,37,45,53,96D、30,24,12,37,45,96,5310.对下面有向图给出了四种可能的拓扑序列,其中错误的是()A、1,5,2,6,3,4B、1,5,6,2,3,4C、5,1,6,3,4,2D、5,1,2,6,4,311.m阶B-树中所有非终端(除根之外)结点中的关键字个数必须大于或等于()A、[m/2]+1B、[m/2]-1C、[m/2]D、m12.散列文件也称为()A、顺序文件B、索引文件C、直接存取文件D、间接存取文件13.数据结构是()A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合14.从逻辑关系来看,数据元素的直接前驱为0个或1个的数据结构只能是()A、线性结构B、树形结构C、线性结构和树型结构D、线性结构和图状结构15.设p为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用p→llink和p→rlink表示,则同样表示p指针所指向结点的表达式是()A、p→llinkB、p→rlinkC、p→llink→llinkD、p→llink→rlink16.若栈采用顺序存储方式存储,现两栈共享空间V[1..m],top[i]代表第i个栈(i=1,2)3栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是()A、|top[2]-top[1]|=0B、top[1]+1=top[2]C、top[1]+top[2]=mD、top[1]=top[2]17.若一棵二叉树有11个叶子结点,则该二叉树中度为2的结点个数是()A、10B、11C、12D、不确定的18.树的先根序列等同于与该树对应的二叉树的()A、先序序列B、中序序列C、后序序列D、层序序列19.下面关于哈希(Hash,杂凑)查找的说法正确的是()A、哈希函数构造的越复杂越好,因为这样随机性好,冲突小B、除留余数法是所有哈希函数中最好的C、不存在特别好与坏的哈希函数,要视情况而定D、若需在哈希表中删去一个元素,解决冲突都只要简单的将该元素删去即可20.下列序列中,()是执行第一趟快速排序后所得的序列。A、[68,11,18,69][23,93,73]B、[68,11,69,23][18,93,73]C、[93,73][68,11,69,23,18]D、[68,11,69,23,18][93,73]21.下列关键字序列中,构成小根堆的是()A、(84,46,62,41,28,58,15,37)B、(84,62,58,46,41,37,28,15)C、(15,28,46,37,84,41,58,62)D、(15,28,46,37,84,58,62,41)22.ISAM文件和VASM文件属于()A、索引非顺序文件B、顺序文件C、索引顺序文件D、散列文件23.下面程序段的时间复杂度为()for(i=0;im;i++)for(j=0;jn;j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)24.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为()4A、q-next=s-next;s-next=p;B、s-next=p;q-next=s-next;C、p-next=s-next;s-next=q;D、s-next=q;p-next=s-next;25.为便于判别有向图中是否存在回路,可借助于()A、广度优先搜索算法B、最小生成树算法C、最短路径算法D、拓扑排序算法26.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是()A、SXSSXXXXB、SXXSXSSXC、SXSXXSSXD、SSSXXSXX27.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是()A、2B、3C、5D、628.假设以数组A[m]存放循环队列的元素。已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位置为()。A、(rear-length+m+1)%mB、(rear-length+m)%mC、(rear-length+m-1)%mD、(rear-length)%m29.在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为()。A、s-next=rear;rear=s;B、front=front-next;C、s-next=front;front=s;D、rear-next=s;rear=s;30.对于哈希函数H(key)=key%13,被称为同义词的关键字是()A、35和41B、23和39C、15和44D、25和5131.采用二叉链表存储的n个结点的二叉树,共有空指针()个。A、n+1B、nC、n-1D、2n-132.连通网的最小生成树是其所有生成树中()A、顶点集最小的生成树B、边集最小的生成树C、顶点权值之和最小的生成树D、边的权值之和最小的生成树33.对记录序列(314,298,508,123,486,145)依次按个位和十位进行两趟基数排序之后所得结果为()A、123,145,298,314,486,508B、508,314,123,145,486,2985C、486,314,123,145,508,298D、298,123,508,486,145,31434.任何一个无向连通图的最小生成树()。A、一定有多棵B、可能不存在C、一棵或多棵D、只有一棵35.无向图的邻接矩阵是一个()A、对角矩阵B、上三角矩阵C、对称矩阵D、零矩阵36.设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树,则下列说法中不正确的是()。A、G’为G的无环子图B、G’为G连通分量C、G’为G极小连通子图且V’=VD、G’为G的子图37.以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是()A、v1,v2,v3,v4,v5,v6,v7B、v1,v2,v5,v4,v3,v7,v6C、v1,v2,v3,v4,v7,v5,v6D、v1,v2,v5,v6,v7,v3,v438.下面几个符号串编码集合中,不是前缀编码的是()A、{0,10,110,1111}B、{0,1,00,11}C、{00,010,0110,1000}D、{b,c,aa,ac,aba,abb,abc}39.希尔排序的增量序列必须是()。A、递增的B、递减的C、随机的D、非递减的40.采用起泡排序法对n个关键字进行升序排序,若要使排序过程中比较关键字的次数最多,则初始时的序列应满足条件()A、关键字完全无序B、关键字基本有序C、关键字从小到大排列D、关键字从大到小排列41.在下列内部排序中()是不稳定的。A、希尔排序B、起泡排序C、直接插入排序D、归并排序42.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是()。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)43.在查找过程中,冲突指的是()。A、两个元素具有相同序号B、两个元素的键值不同C、不同键值对应相同的存储地址D、两个元素的键值相同644.对有14个元素的有序表A[1..14]作二分查找,查找元素A[4]时的被比较元素依次为()。A、A[1],A[2],A[3],A[4]B、A[1],A[14],A[7],A[4]C、A[7],A[5],A[3],A[4]D、A[7],A[3],A[5],A[4]45.以v1为起始结点对下图进行广度度优先遍历,正确的遍历序列是()A、v1,v2,v3,v4,v5,v6,v7B、v1,v2,v5,v6,v7,v3,v4C、v1,v2,v5,v6,v7,v3,v4D、v1,v4,v5,v7,v6,v2,v3二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)1.数据的物理结构包括的存储和的存储。2.若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度为。3.下面程序段的时间复杂度是。i=1;while(i=n)i=i*3;4.循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列的元素个数是。5.在单链表中设置头结点的作用是____。6.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是_。7.已知一无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是遍历方法。8.如果排序过程不改变之间的相对次序,则称该排序方法是稳定的。9.从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需一个位置。10.当问题的规模n趋向无穷大时,算法执行时间T(n)的数量级被称为算法的。11.若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数即为顶点vi7的。12.一棵含999个结点的完全二叉树的深度为。13.假设S和X分别表示进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,则由“a*b+c/d”得到“ab*cd/+”的操作序列为。14..如图所示的有向无环图可以排出种不同的拓扑序列。15.从空树起,依次插入关键字1l,27,35,48,52,66和73构造所得的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度为。16.带头结点的双循环链表L中只有一个元素结点的条件是。17.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中的数目正相关。18.已知一棵完全二叉树中共有768结点,则该树中
本文标题:期末复习题_数据结构
链接地址:https://www.777doc.com/doc-2322762 .html