数据结构学位考试试题

学习必备欢迎下载数据结构课程学位考试试题（参考答案在题后）判断题：判断下列各小题叙述的正误。对，在题号后的括号内填入“√”；错，在题号后填入“×”。1、数据的最小单位是数据项。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.(√)2、多重表文件中主索引为非稠密索引，次索引为稠密索引。⋯⋯⋯.(√)3、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。⋯⋯⋯.⋯⋯.(×)4、算法具有输入、输出、可行性、稳定性、有穷性五个特性。⋯⋯⋯⋯⋯⋯.(×)5、数据的基本单位是数据项。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.(×)6、算法的复杂度分为时间复杂度和效率复杂度。⋯⋯⋯⋯.(×)7、性质相同的数据元素的集合成为数据对象。⋯⋯⋯⋯⋯.(√)8、所有结点按1对1的邻接关系构成的整体就是集合结构。⋯⋯⋯.(×)9、散列文件不能顺序存取、只能按关键字随机存取。⋯⋯⋯⋯⋯.(√)10、数据的基本单位是数据元素。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.(√)11、B+树中的K个孩子的结点必有K个关键字。⋯⋯⋯.(√)12、B+树中的K个孩子的结点必有K个关键字。⋯⋯⋯.⋯⋯.(√)13、倒排表的索引项中没有头指针和链表长度项。⋯⋯⋯⋯.(√)14、磁带是顺序存取的外存储设备。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯.(×)15、索引文件只能是磁盘文件。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(√)16、顺序文件只适宜于顺序存取。⋯⋯⋯⋯⋯⋯⋯⋯⋯..⋯⋯⋯⋯.(×)17、磁带是顺序存取的外存储设备。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯.(×)18、线性的数据结构可以顺序存储，也可以链接存储。⋯⋯⋯⋯⋯.(√)19、倒排表的索引项中没有头指针和链表长度项。⋯⋯⋯⋯⋯⋯⋯.(√)20、散列文件不能顺序存取、只能按关键字随机存取。⋯.⋯⋯.(√)21、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（√）22、循环链表从任何一个结点出发，都能访问到所有结点.......(√)23、单链表从任何一个结点出发，都能访问到所有结点。⋯⋯.(×)24、线性表采用顺序存储表示时，必须占用一片连续的存储单元。(√)25、循环链表从任何一个结点出发，都能访问到所有结点。⋯⋯.(√)26、设串S的长度为n,则S的子串个数为n(n+1)/2⋯⋯.(×)27、线性表采用链接存储表示时，必须占用一片连续的存储单元。.(×)28、链接表上做删除和插入运算时的平均时间复杂度都是O(n)⋯.(×)29、线性表中的每个结点最多只有一个前驱和一个后继。⋯⋯⋯⋯⋯⋯.(√)30、顺序表上做删除和插入运算时的平均时间复杂度都是O(n).(√)31、具有n个结点的完全二叉树的高度为┖2log2n┘+1⋯⋯⋯⋯⋯.(×)32、在只有度为0和度为2的结点的二叉树中，设度为0的结点有n0个，度为2的结点有n2个，则有n0=n2+1⋯⋯⋯⋯⋯.(√)33、循环队列判断队列为满的条件是sq->front+1==sq->rear。⋯⋯(×)34、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。⋯⋯⋯.(√)35、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能惟一地确定一棵二叉树。....(√)36、有n个结点的不同的二叉树有n！棵。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯.(×)学习必备欢迎下载37、一般树和二叉树的结点数目都可以为0。................(√)38、循环队列判断队列为空的条件是sq->front==sq->rear。⋯⋯(√)39、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是3。.(√)40、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1⋯⋯⋯⋯⋯⋯.(×)41、一个连通图的生成树，是含该连通图的全部顶点的一个极小连通子图.(√)42、在二叉树的第i层上至多有2i-1个结点⋯⋯⋯.(√)43、先根遍历树和先根遍历与该树对应的二叉树，其结果不一样。...(×)44、由树转化成二叉树，其根的右子女指针总是空的⋯⋯⋯.(√)45、网络的最小代价生成树是唯一的⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯.⋯⋯⋯.(×)46、深度优先搜索遍历类似于树的先根遍历，它所用到的数据结构是队列。(×)47、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。⋯⋯⋯(√)48、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。⋯⋯⋯..⋯⋯⋯⋯.(√)49、图的深度优先搜索类似于树的先根次序遍历⋯⋯⋯⋯.(√)50、在无向图中定义顶点V与V之间的路径为从V到达V的一个顶点序列（√）ijij51、设无向连通图的顶点个数为n，则该图最多有n(n-1)/2条边⋯.(√)52、图的广度优先遍历是树的按中根遍历推广。⋯⋯⋯(×)53、设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有2种...(√)54、用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为O(n*e)⋯⋯⋯⋯.(×)55、查找表是由同一类型的数据元素(或记录)构成的集合(√)56、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯.⋯⋯.⋯⋯.⋯⋯.⋯⋯⋯.(√)57、图的深度和广度遍历两种操作的时间复杂度都为O（n*e）。⋯⋯⋯.(×)58、只有无向图，顶点数n、边数e和度数之间有如下关系：e=1n⋯⋯D(×(vi))59、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。2i1（√）60、闭散列法通常比开散列法时间效率更高。（×）61、进行折半搜索的表必须是顺序存储的有序表。（√）62、索引顺序查找的过程也是一个“缩小区间”的查找过程(√)63、设有100个数据元素，采用折半搜索时，最大比较次数为7.(×)64、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。⋯⋯.(×)65、在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。⋯⋯⋯(√)66、闭散列法通常比开散列法时间效率更高。（×）67、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。(√)68、起泡选择排序是一种不稳定的排序方法。(×)69、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。.⋯⋯⋯.(70、除留余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。×)（√）71、选择排序是一种不稳定的排序方法。(√)72、直接选择排序是不稳定的，其时间复杂性为）O(1)。⋯⋯⋯.(×)学习必备欢迎下载73、快速排序是一种不稳定的排序方法。(√)74、对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。（√）75、直接选择排序是一种不稳定的排序方法。⋯.⋯⋯.⋯⋯.⋯⋯.⋯⋯.⋯(√)76、直接插入排序是一种稳定的排序方法。(√)77、归并排序是一种不稳定的排序方法。(×)78、选择排序是一种不稳定的排序方法。(√)79、归并排序是一种不稳定的排序方法。(×)80、堆排序是一种不稳定的排序方法。(√)二、单选题：从选择的答案中选出正确的答案，将其字母编号填入下列叙述中的括号内。1、以下说法错误的是（B）数据的物理结构是指数据在计算机内实际的存储形式算法和程序没有区别，所以在数据结构中二者是通用的对链表进行插人和删除操作时，不必移动结点双链表中至多只有一个结点的后继指针为空2、下列有关散列文件的说法中不正确的是(C)A.散列文件具有随机存放的优点B.散列文件只能按关键字存取C.散列文件需要索引区D.散列文件的记录不需要进行排序3、有一个算法由3个部分的代码嵌套连接组成，每部分的时间复杂度分别为O（1）、O（n2）、O（n3）,该算法的时间复杂度为(D)A.O（1）+（n2）+（n3）B.O（n2）C.（n3）D.（n5）4、下列有关散列文件的说法中不正确的是(C)A.散列文件具有随机存放的优点B.散列文件只能按关键字存取C.散列文件需要索引区D.散列文件的记录不需要进行排序5、设单链表中结点的结构为（data,next）。已知指针q所指结点是指针p所指结事业的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（B）。A.s->next=p->next;p->next=sB．q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q6、对顺序表上的插入、删除算法的时间复杂性 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 来说，通常以（B）为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 操作A.条件判断B.结点移动C.算术表达式D.赋值语句7、在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（B）A.real和rear->next->nextB.rear->next和realC.rear->next->next和rearD.rear和rear->nextO（1）、O（n2）、O（n38、有一个算法由3个部分的线性代码连接组成，每部分的时间复杂度分别为）,该算法的时间复杂度为(C)A.O（1）+（n2）+（n3）B.O（n2）C.（n3）D.（n5）9、以下说法错误的是（A）对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表对单链表来说，只有从头结点开始才能扫描表中全部结点双链表的特点是找结点的前趋和后继都很容易D.对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋学习必备欢迎下载指针域中。10、在串的基本运算中，属于加工型运算的有（D）A.EQAL(S,T)B.LENGTH(S)C.CONCAT(S,T)D.REPLACE(S,T,R)11、线性链表不具有的特点是（A）。A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比12、以下说法正确的是（C）在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构C.顺序存储结构属于静态结构，链式结构属于动态结构D.顺序存储方式只能用于存储线性结构13、线性表是一个具有n个（C）的有限序列。A．表元素B．字符C．数据元素D．数据项14、对于顺序表，以下说法错误的是（A）顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中15、一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（C）。A.O(n)B.O(n/2)C.O(1)D.O(n2)16、单链表的一个存储结点包含（A.数据域或指针域B.D）指针域或链域C.指针域和链域D.数据域和链域17、在串的基本运算中，属于引用型运算的有（B）A.ASSIGN(S,T)B.INSERT(S1,i,S2)C.DELETE(S,i,j)D.SUBSTR(S,i,j)18、一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A）。A.O(n)B.O(n/2)C.O(1)D.O(n2)19、向顺序栈中压入新元素时，应当（A）。先移动栈顶指针，再存入元素．先存入元素，再移动栈顶指针C.先后次序无关紧要．同时进行20、顺序队列的人队操作应为(A)A.sq.rear=sq.rear+1;sq.data[sq.rear]=xB.sq.data[sq.rear]=x;sq.rear=sq.rear+1C.sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=xD.sq.data[sqrear]=x;sq.rear=(sq.rear+1)%maxsize21、头结点的单链表firstA.first==NULL;C.first->next==first;为空的判定条件是：(B)B.first->next==NULL;D.first!=NULL;22、如果以链表作为栈的存储结构，则入栈操作时（A）A、必须判别栈是否满B、必须判别栈元素的类型学习必备欢迎下载C、必须判别栈是否空D、对栈不作任何判别23、设有一个nn的对称矩阵那么第i行的对角元素A[i][i]A，将其下三角部分按行存放在一个一维数组存放于B中（A）处。B中，A[0][0]存放于B[0]中，A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/224、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（A）A.dceabB.decbaC.edcbaD.abcde25、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(A)。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL26、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（B）。A.n-2B.n-1C.nD.n+127、循环链表主要优点是（D）不再需要头指针了已知某个结点的位置后，能够容易找到它的直接前趋在进行插入、删除运算时，能更好地保证链表不断开从表中任一结点出发都能扫描到整个链表28、稀疏矩阵一般采用(C)方法压缩存储。A.三维数组B.单链表C.三元组表29、链式栈与顺序栈相比，一个比较明显的优点是（B）A插入操作更加方便B通常不会出现栈满的情况D.散列表C不会出现栈空的情况D删除操作更加方便30、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果的容量至少应该是（B）6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈A.2B.3C.5D.631、设有50行60元素A[18][25]A．3700列的二维数组A[50][60]的存储地址为（A）。B．4376，其元素长度为4字节，按行优先顺序存储，基地址为200，则C．3900D．462032、设C语言数组DATA[m+1]作为循环队列队操作的语句为（D）SQ的存储空间，front为对头指针rear为对尾指针，则执行出A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%mD..front=(front+1)%(m+1)33、循环队列的队满条件为(C)A.(sq.rear+1)%mazsize==(sq.front+1)%maxsize;B.(sq.rear+1%maxsize==sq.front+1C.sq.(rear+1)%maxsize==sq.frontD.sq.rear==sq.front34、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（A）。A.2B.1C.0D.–135、具有A．865个结点的完全二叉树的高度为（B．7C．6B）。（根的层次号为D．50）36、对某二叉树进行前序遍历的结果为A．DBFEACB．DFEBCAABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（B）学习必备欢迎下载C．BDFECAD．BDEFAC37、循环队列的出队操作为(A)A.sq.front=(sq.ftont+1)%maxsizeB.sq.front=sq.front+1C.sq.rear=(sq.rear+)%maxsizeD.sq.rear=sq.rear+138、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（C）个。A．n-1B．nC．n+1D．n+239、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序(B)A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同40、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为(B)A.R-FB.(n+R-F)modnC.(R-F+1)modnD.n+R-F41、以下说法错误的是(A)树形结构的特点是一个结点可以有多个直接前趋线性结构中的一个结点至多只有一个直接后继树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构42、以下说法错误的是(B)。二叉树可以是空集二叉树的任一结点都有两棵子树二叉树与树具有相同的树形结构D.二叉树中任一结点的两棵子树有次序之分43、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（C）A．nB．n-1C．n+1D．2*n44、下列说法中正确的是（A）。A.一棵二叉树的度可以小于2B.二叉树中任何一个结点的度都为2C.二叉树的度为2D.任何一棵二叉树中至少有一个结点的度为245、在一棵具有5层的满二叉树中结点数为（A）A31B32C33D1646、一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCDEFGHIJ则结点E在二叉树的第（C）层。A.1B.2C.3D.447、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（D）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历48、任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置(C)A.肯定发生变化B.有时发生变化C.肯定不发生变化D.无法确定49、在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(B)。A.2h+1B.2h-1C.2h-1D.2h学习必备欢迎下载50、树若用双亲链表表示，则(A)可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难51、任何一个带权的无向连通图的最小生成树（B）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在52、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（B）。A．O（nlog2eC．O(ne)）DB．O（n+e）．O(n2)53、以下说法正确的是（A）连通图的生成树，是该连通图的一个极小连通子图。无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。任何一个有向图，其全部顶点可以排成一个拓扑序列。有回路的图不能进行拓扑排序。54、以下说法错误的是(D)一般在哈夫曼树中，权值越大的叶子离根结点越近哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树55、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是(B)A.完全图B.连通图C.有回路D.一棵树56、将一棵有50个结点的完全二叉树按层编号，则对编号为A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子25的结点x，该结点(B)57、深度为6的二叉树最多有(B)个结点A.64B.63C.32D.3158、一个有序顺表有A、128B、127C255个对象，采用顺序搜索法查表，搜索长度为（、126D、255A）。59、在有向图中每个顶点的度等于该顶点的（A.入度B.出度C.入度与出度之和D.入度与出度之差C）。60、具有n个顶点的有向无环图最多可包含(A．n-1B．nC．n(n-1)/261、用邻接表作为有向图G的存储结构。设有D)条有向边。D．n(n-1)n个顶点、e条弧，则拓扑排序的时间复杂度为(B)A.O(n)B.O(n+e)C.O(e)D.O(n*e)62、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（A）。A、128B、127C、126D、25563、在有向图中，所有顶点的入度之和是所有顶点出度之和的（B）倍。A.0.5B.1C.2D.464、以下说法错误的是（B）A.用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。学习必备欢迎下载C.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了D.用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第i行第j列的元素是否为0即可。65、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（A）A.先根遍历B.中根遍历C.后根遍历D按层次遍历66、在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍。A．3B．2C．1D．1/267、在无向图中，所有顶点的度数之和是所有边数的（C）倍。A.0.5B.1C.2D.468、设有6个结点的无向图，该图至少应有（B）条边能确保是一个连通图。A.5B.6C.7D.869、以下说法正确的是（D）连通分量是无向图中的极小连通子图。强连通分量是有向图中的极大强连通子图。C.在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。D.对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。70、对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（C）。A．R[0]，R[1]，R[2]，R[3]B．R[0]，R[13]，R[2]，R[3]C．R[6]，R[2]，R[4]，R[3]D．R[6]，R[4]，R[2]，R[3]71、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为99的结点时，经（C）次比较后查找成功。A.2B.3C.4C.1272、设有100个数据元素，采用折半搜索时，最大比较次数为（B）A6B7C8D1073、对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（B）A．n/2B．(n+1)/2C．(n–1)/2D．n/474、对采用二分查找法进行查找运算的查找表，要求按（C）方式进行存储。A顺序存储B链式存储C顺序存储且结点按关键字有序D链式存储且结点按关键字有序75、二分查找法适用于存储结构为（A）的，且按关键字排序的线性表A.顺序存储B.链接存储C.顺序存储或链接存储D.索引存储76、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B）A.O(n)B.O(n/2)C.O(1)2D.O(n)77、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于(C)A.静态查找表B.动态查找表C.静态查找表与动态查找表D.两种表都不适合78、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（B）A．O(n)B．O(1)C．O(n2)D．O(log2n)79、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（C）次比较后查找成功。A2B3C4D1280、静态查找表与动态查找表两者的根本差别在于（C）学习必备欢迎下载A逻辑结构不同B存储实现不同C施加的操作不同D数据元素的类型不同81、以下时间复杂性不是O(n2)的排序方法是（B）A.直接插入排序B.二路归并排序C.冒泡排序D.直接选择排序82、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（C）。A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}83、用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为（C）A.O（n2）B.O(nlog2n)C.O（n）DO(log2n)84、用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：258421471527683520152021254727683584152021253527476884152021252735476884则采取的排序方法是（C）A.直接选择排序B.冒泡排序C.快速排序D.二路归并排序85、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（C）。A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}86、顺序查找法适合于（D）存储结构的查找表。A.压缩B.散列C.索引D.顺序或链式87、以下说法错误的是（C）A.直接插入排序的空间复杂度为O(1)。B.快速排序附加存储开销为O(log2n)。C.堆排序的空间复杂度为O(n)。D.二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。88、对于大文件的排序要研究在外设上的排序技术，即（C）A.快速排序法B.内排序法C.外排序法D.交叉排序法89、对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（C）的值除以9。A.20B.18C.25D.2290、具有24个记录的序列，采用冒泡排序至少的比较次数是（B）A.1B.23C.24D.52991、当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（A）A.n-1B.log2nC.2log2nD.n292、排序的目的是为了以后对已排序的数据元数进行（D）操作。A.打印输出B.分类C.合并D.查找93、以下稳定的排序方法是（B）A.快速排序B.冒泡排序C.直接选择排序D.堆排序94、（B）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。A.归并排序B.插入排序C.快速排序D.选择排序学习必备欢迎下载95、在文件局部有序或文件长度较小的情况下，最佳的排序方法是（A）A.直接插入排序B.冒泡排序C.直接选择排序D.归并排序96、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（C）方法最快。A．起泡排序B．快速排序C．堆排序D．直接选择排序97、对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（C）方法。C.直接选择排序D.快速排序98、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（C）A直接选择排序B直接插入排序C快速排序D起泡排序99、以下不稳定的排序方法是（C）A.直接插入排序B.冒泡排序C.直接选择排序D.二路归并排100、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B）A.O(n)B.O(n/2)C.O(1)D.O(n2)三、填空题1、有一个算法由3个部分的线性代码连接组成，每部分的时间复杂度分别为O（n）、O（n2）、O（n4）,该算法的时间复杂度为(O（n4）)。2、数据的基本单位是(数据元素)。3、计算机中的算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、可行性、(确定性)和(有穷性)等5个特征4、所有结点按1对1的邻接关系构成的整体就是(线性)结构5、数据元素之间的关联方式或称“邻接关系”称为(逻辑)关系。6、有一个算法由3个部分的代码嵌套连接组成，每部分的时间复杂度分别为O（n）、O（n2）、O（n4）,该算法的时间复杂度为(O（n7）)。7、数据元素之间逻辑关系的整体称为(逻辑结构)。8、对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和(事后测试)。9、算法的复杂度分为(时间复杂度)和(空间复杂度)两种。10、数据在计算机中的存储表示（机内表示）称为数据的(存储结构)。11、文件的检索有顺序存取、直接存取和(按关键字存取)三种方式。12、文件的检索有顺序存取、直接存取和(按关键字存取)三种方式。13、在顺序表中插入或删除一个元素，需要平均移动((n+1)/2)元素，具体移动的元素个数与()有关。14、VSAM文件结构由三部分组成：索引集、(顺序集)和数据集。15、ISAM文件是由多级主索引、柱面索引、磁道索引和(主文件索引)组成。16、已知：s1=〃I’mateacher〃，s2=〃teacher〃，s3=〃student〃，则等于(I’mateacher)。REPLACE(s1,s2,s3)17、如果文件中的每个记录都有一个索引项，则这样的索引称为(稠密索引)。18、如果文件中多个记录只有一个索引项，则这样的索引称为(非稠密索引)。19、在双链表中，每个结点有两个指针域，一个指向(前驱)，另一个指向(后继)。20、当且仅当两个串的(长度)相等并且各个对应位置上的字符都相同时，这两个串相等。一个串中任意个学习必备欢迎下载连续字符组成的序列称为该串的(子串)串。21、VSAM文件结构由三部分组成：索引集、(顺序集)和数据集。22、串的顺序存储有两种方法：一种是每个单元只存一个字符，称为(非紧缩格式)格式，另一种是每个单元存放多个字符，称为(紧缩格式)格式。23、线性表的常见链式存储结构有单链表、(双向链表)和(循环链表)。24、线性表典型的基本运算包括初始化、(插入)、(删除)、查找定位、求长度、存取等六种。25、已知：s1=〃I’mateacher〃，s2=〃teacher〃，s3=〃student〃，则SUBSTR(s1,7,7)等于(student)。26、已知：s1=〃I’mateacher〃，s2=〃teacher〃，s3=〃student〃，则DELETE(s1,4,10)等于(I’m)。27、已知：s1=〃I’mateacher〃，s2=〃teacher〃，s3=〃student〃，则EQUAL(s1,s2)等于(0)。28、顺序表中逻辑上相邻的元素的物理位置(必须)紧邻。单链表中逻辑上相邻的元素的物理位置(不需要)紧邻。29、四维数组是一种非线性结构，其中的每一个数组元素最多有(4)个直接前驱（或直接后继）30、一般地，栈和线性表类似有两种实现方法，即(顺序)实现和(链接)实现。31、含零个字符的串称为(空串)串，用(Ф)表示。32、栈是一种限定在表的一端进行插入和删除的线性表，又被称为(后进先出)线性表。33、在栈的顺序实现中，设栈顶指针为top，栈空的条件为(top=0)。34、若已知一个栈的入栈序列是1，2，3，4，⋯，n，其输出序列是P1，P2，P3，⋯，Pn，若P1=n，则Pi为(n-i+1)。35、对于顺序存储的栈，因为栈的空间是有限的，在进行(后进)运算时，可能发生栈的上溢，在进行(先出)运算时，可能发生栈的下溢。36、(栈)可以作为实现递归函数调用的一种数据结构。37、对任何二叉树，若度为2的节点数为n2，则叶子数n0=(n2+1)。38、队列中允许进行删除的一端称为(对头)。39、一般地，一个n维数组可视为其数据元素为(n)维数组的线性表。数组通常只有(删除)和(插入)两种基本运算。40、二叉树有不同的链式存储结构，其中最常用的是41、以下运算实现在顺序栈上的进栈，请在()(二叉链表)与(三叉链表处用适当的语句予以填充。)。IntPush(SqStackTp*sq,DataTypex){if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{(sq->top++):(sq->data[sq->top])=x;return(1);}}42、深度为90的满二叉树上，第11层有(210)个结点。43、已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，1个度为3的结点，则该树中有(6)个叶子结点。44、深度优先搜索遍历类似于树的(先根)遍历，它所用到的数据结构是(栈)。45、具有n个结点的完全二叉树的深度为([log2n]＋1)。46、(树)中结点的最大度数允许大于2，而(二叉树)中结点的最大度数不允许大于247、一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有(右)子女。48、深度为k(k>=1)的二叉树至多有(2k-1)个结点。49、有m个叶子结点的哈夫曼树，其结点总数为(2m-1)。学习必备欢迎下载50、在一棵树中，(根)结点没有前驱结点。51、对无向图，其邻接矩阵是一个关于(对角线)对称的矩阵。52、n(n﹥0)个顶点的有向连通图最多有(n(n-1))条边，最少有(n-1)条边53、设无向连通图G的顶点数为n，则G最少有(n-1)条边。54、遍历图的基本方法有(深度)优先搜索和(广度)优先搜索两种。55、在集合这种逻辑结构中，任何结点之间都不存在(逻辑)关系，这是集合这种逻辑结构的基本特点。56、一个有向图G中若有弧,、和,则在图G的拓扑序列中，顶点Vi、Vj和Vk的相对位置为(省略)。57、广度优先搜索遍历类似于树的(层次)遍历，它所用到的数据结构是(队列)。58、由(树)转换成二叉树时，其根结点的右子树总是空的。59、设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有种(2)。60、任何连通图的连通分量只有一个，即(本身)。61、向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的(左子树)上。62、对有序表(25，30，32，38，47，54，62，68，90，95)用二分查找法查找32，则所需的比较次数为(3)。63、静态查找表包括(建表)、(查找)、(读元素)三种基本运算。64、动态查找表包括建表、查找、读元素、(插入)、(删除)五种基本运算。65、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当插入到值为(50)的结点时需要进行旋转调整。66、平衡二叉排序树上任一结点的平衡因子只可能是(0)、(1)或(-1)。67、在二叉排序树上插入新结点时，不必移动其它结点，仅需使某结点的指针域由(空)变为(指向该结点)即可。68、在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过(1)。69、在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为(1)。70、快速排序是不稳定的，其时间复杂性为(O（nlog2n）)71、直接选择排序是不稳定的，其时间复杂性为(O（n2))。72、按排序过程中依据的不同原则对内部排序方法进行分类，主要有：插入排序、(选择排序)、(交换排序)、归并排序等四类73、归并排序的空间复杂度为(O(1))。74、二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值(大)于其左孩子（及其子孙）的键值且(小)于其右孩子（及其子孙）的键值。75、归并排序的时间复杂度是(O（nlog2n）)。76、简单排序的时间复杂性为(O（n2))，空间复杂度为(O(1))。77、二叉树第i（i>=1）层至多有(2i-1)个节点。278、直接插入排序是稳定的，它的时间复杂性为(O（n))，空间复杂度为(O（1))。79、归并排序要求待排序列由若干个(有序)的子序列组成。80、按照排序过程涉及的存储设备的不同，排序可分为(内)排序和（外)排序。四、计算题1、设二维数组A8*9的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a78的起始地址为多少？按行和按列优先存储时，a45的起始地址分别为多少？答案：（(1）288；（2）1284；（3）行：1164列：1176)学习必备欢迎下载2、设二维数组A8*9的每个元素占4个字节，行下标i的范围从1到8，列下标j的范围从0到8已知Loc（a10）=1000，A共占多少个字节？A的终端结点a78的起始地址为多少？按行和按列优先存储时，a65的起始地址分别为多少？答案：（1）288；（2）1284；（3）行：1200列：11803、设二维数组A8*9的每个元素占5个字节，行下标i的范围从0到7，列下标j的范围从1到9已知Loc（a01）=2000，A共占多少个字节？A的终端结点a78的起始地址为多少？按行和按列优先存储时，a45的起始地址分别为多少？答案：（1）360；（2）2355；（3）行：2200列：21854、设二维数组A11*9的每个元素占7个字节，行下标i的范围从0到10，列下标j的范围从1到9已知Loc（a01）=2500，A共占多少个字节？A的终端结点a109的起始地址为多少？按行和按列优先存储时，a75的起始地址分别为多少？（1）693；（2）3186；（3）行：2969列：2857答案：5、设二维数组A7*9的每个元素占4个字节，已知Loc（a11）=2000，A共占多少个字节？A的终端结点a68的起始地址为多少？按行和按列优先存储时，a55的起始地址分别为多少？答案：（1）252；（2）2208；（3）行：2160列：21286、设二维数组A8*9的每个元素占8个字节，已知Loc（a00）=2000，A共占多少个字节？A的终端结点a78的起始地址为多少？答案：（1）576；（2）25687、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵学习必备欢迎下载中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[7][5]在B[]中位置为多少？答案：338、设二维数组A10*9的每个元素占4个字节，已知Loc（a00）=2000，按行和按列优先存储时，a56的起始地址分别为多少？答案；（1）2024；（2）22609、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中位置为多少？答案：4110、设二维数组A10*9的每个元素占7个字节，已知Loc（a00）=1500，A共占多少个字节？A的终端结点a98的起始地址为多少？答案：（1）630；（2）212311、设有一个10阶的对称矩阵A[20][20]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[14][12]在B[]中位置为多少？答案：11712、设二维数组A6*7的每个元素占5个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a56的起始地址为多少？按行和按列优先存储时，a46的起始地址分别为多少？答案：（1）210；（2）1205；（3）行：1170列：120013、设二维数组A12*9的每个元素占4个字节，已知Loc（a11）=2000，A共占多少个字节？A的终端结点a118的起始地址为多少？按行和按列优先存储时，a85的起始地址分别为多少？学习必备欢迎下载答案:（1）432；（2）2428；（3）行：2268列：2220五、综合题1、给出下列二叉树的前序序列、中序序列、后序序列。答案：前序：CABEFDHG中序：BAFECHDG后序：BFEAHGDC2、假定用于通信的电文仅由4个字母a，b，c，d,e组成，各个字母在电文中出现的频率分别为7，6,5，2，4。试为这5个字母设计Huffman树且写出对应的Huffman编码。答案:bcadea:10b:00c:01d:110e:1113、把下面的森林转换为对应的二叉树。EHKADGICJB学习必备欢迎下载答案：EAHDGKCJIB4、使用普里姆算法构造出如图所示的图G的一棵最小生成树。答案：学习必备欢迎下载5、设散列表的长度ｍ＝１３；散列函数为Ｈ（Ｋ）＝Ｋmodm，给定的关键码序列为19，14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度。0123456789101112搜索成功时的平均搜索长度为：ASLsucc=答案：012345678910111214016827551920842311解：H（19）=19mod13=6H（14）=14mod13=1H（23）=23mod13=10H（01）=01mod13=1a.elem[1]不空，所以第一次冲突处理后的地址为H（01）=（01+1）mod13=2H（68）=68mod13=3H（20）=20mod13=7H（84）=84mod13=6a.elem[6]不空，所以第一次冲突处理后的地址为H（84）=（84+1）mod13=7a.elem[7]不空，所以第二次冲突处理后的地址为H（84）=（68+2）mod13=8H（27）=27mod13=1a.elem[1]不空，所以第一次冲突处理后的地址为H（27）=（27+1）mod13=2学习必备欢迎下载a.elem[2]不空，所以第二次冲突处理后的地址为H（27）=（27+2）mod13=3a.elem[3]不空，所以第三次冲突处理后的地址为H（27）=（27+3）mod13=4H（55）=55mod13=3a.elem[3]不空，所以第一次冲突处理后的地址为H（55）=（55+1）mod13=4a.elem[4]不空，所以第二次冲突处理后的地址为H（55）=（55+2）mod13=5H（11）=11mod13=11平均搜索长度ASLsucc=1/10(1*6+2*1+3*2+4*1)=1.86、已知待排序记录的关键字序列为{83，69，41，22，15，33，8}，要求：（1）用直接插入排序法按从小到大顺序写出每趟排序的结果，直到排序结束；答案：第一趟：83，69，41，22，15，33，8第二趟：69，83，41，22，15，33，8第三趟：41，69，83，22，15，33，8第四趟：22，41，69，83，15，33，8第五趟：15，22，41，69，83，33，8第六趟：15，22，33，41，69，83，8第七趟：8，15，22，33，41