《数据结构》期末考试复习题库（含答案）

PAGEPAGE1《数据结构》期末考试复习题库（含答案）一、单选题1.根据使用频率为5个字符设计的哈夫曼编码不可能是()。A、000，001，010，011，1B、0000，0001，001，01，1C、000，001，01，10，11D、00，100，101.110，111答案：D2.单链表的存储密度（)。A、大于1B、等于1C、小于1D、不能确定答案：C3.一个顺序表所占用存储空间的大小与()无关。A、顺序表长度B、顺序表中元素的数据类型C、顺序表中元索各数据项的数据类型D、顺序表各元素的存放次序答案：D4.下列关于串的叙述中，不正确的是（)。A、串是宁符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储,也可以采用链式存储答案：B5.队列的插入操作是在()进行。A、队首B、队尾C、队前D、队后答案：B6.已知一棵完全二叉树的第6层(设根为第一层)有8个叶子结点，则该完全二叉树的结点个数最少是()。A、89B、52C、111D、119答案：A7.顺序表和链表相比存储密度较大，这是因为()。A、顺序表不需要增加指针来表示元素之间的逻辑关系B、顺序表的存储空间是预先分配的C、链表中所有结点的地址是连续的D、顺序表中所有元素的存储地址是不连续的答案：A8.从逻辑上可以把数据结构分为()两大类。A、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构答案：C9.顺序查找法适合于存储结构为()的线性表。A、哈希存储B、顺序存储和链式存储C、压缩存储D、索引存储答案：B10.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为()A、规则B、结构C、集合D、运算答案：B11.以下（）是"abcd321ABCD串的子串。A、abcdB、321ABC、"abcABC"D、“21AB答案：D12.顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有()可分配的存储空间。A、m个B、m个连续C、n+m个D、n+m个连续答案：D13.在数据结构中，从逻辑上可以把数据结构分成()。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构答案：C14.没有向图G=(VE)，顶点集V=V。V.V-V.E=(<VV2><VV:>,V-V.>V.V.>)，若从顶点V,开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是()。A、2B、3C、4D、5答案：D15.由权值分别为9、2、7、5的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为()。A、23B、44C、37D、27答案：B16.比较次数与排序的初始状态无关的排序方法是()。A、直接插入排序B、起泡排序C、快速排序D、简单选择排序答案：D17.在一个具有n个结点的单链表中查找值为m的某结点若查找成功，则平均比较()个结点。A、nB、n/2C、(n-1)/2D、(n+1)/2答案：D18.设有向图G=(V.E)，顶点集V={V0,V1,V2,V3},E={<V0,V>,<V0,V2><V0,V3><V1,V3>，若从顶点V0,开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是()。A、2B、3C、4D、5答案：D19.连续存储设计时，存储单元的地址()。A、一定连续B、一定不连续C、不定连续D、部分连续，部分不连续答案：A20.设栈S和队列Q的初始状态为空，元素e1,e2，e3,e4,e5和e6依次进入栈S,一个元素出栈后即进入Q，若6个元素出队的序列是e2,e4,e3,e6,e5和e1,则栈S的容量至少应该是()A、2B、3C、4D、6答案：B21.下面（)算法适合用于构造―个稠密图的最小生成树。A、Dijkstra算法B、Prim算法C、Floyd算法D、Kruskal算法答案：B22.线性表(a,a,-,a,)以链接方式存储时，访问第i个位置上元素的时间复杂度为()。A、O(i)B、O(1)C、O(n)D、O(i-1)答案：C23.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是()。A、41B、32C、113D、122答案：B24.以下不属于存储结构的是()。A、栈B、二叉链表C、哈希表D、双向链表答案：A25.一个图中包含有k个连通分星,若按深度优先(DFS)搜索方法访问所有结点.则必须调用()次深度优先遍历算法。A、kB、1C、k-1D、k+1答案：A26.若编号1~7的7个数按照5274163的次序进栈进栈的中间可以出栈则出栈序列不可能是()。A、5217463B、5714623C、2471536D、5143672答案：A27.用不带头结点的单链表存储队列时，其队头指针指向队头结点其队尾指针指向队尾结点则在进行删除操作时()。A、仅修改队头指针B、仅修改队尾指针C、队头、队尾指针都要修改D、队头、队尾指针都可能要修改答案：D28.两个栈采用顺序存储结构时，共享同一个数组空间的好处是()。A、减少存取时间，降低下溢出发生的机率B、节省存储空间，降低上溢出发生的机率C、减少存取时间，降低上溢出发生的机率D、节省存储空间，降低下溢出发生的机率答案：B29.某二叉树中序序列为abcdefg.,后序列动为bafg.则前序序列是()。A、egfacdbB、eacbdgfC、eagcfbdD、其它的都不对答案：B30.冒泡排序最少关键字移动的次数是()。A、0B、nC、1D、3n(n-1)/2答案：A31.串的长度是指()。A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数答案：B32.快速排序在()情况下最不利于发挥其长处。A、排序的数据量太大B、排序的数据个数为奇数C、排序的数据中含有多个相同值D、排序的数据已基本有序答案：D33.假设以行序为主序存储二维数组A=array[1..100,1.100]，设每个数据元素占2个存储单元，基地址为10，则LOC[55]=()。A、808B、818C、1010D、1020答案：B34.两个字符串相等的条件是()。A、串的长度相等B、含有是每个人字符集C、都是非空串D、串的长度相等且对应的字符相同答案：D35.数据结构的研究内容不涉及()。A、数据如何组织B、数据如何存储C、数据运算如何实现D、算法用什么语言来描述答案：D36.将算术表达式"1+6/(8-5)*3*转换成后缀表达式，在求后缀表达式的过程中，当遇到*时，运算数栈(从栈顶到栈底次序)为()。A、861B、581C、321D、361答案：C37.将10阶对称矩阵A压缩存储到―维数组B中，则数组B的长度最少为（)。A、100B、40C、80D、55答案：D38.线性表有一个特点()。A、至少有两个元素，即开始元素和终端元素B、若没有开始元素，则一定没有终端元素C、每个元素必须有一个前趋元素D、任何一个元素都可能既是开始元素又是终端元素答案：B39.在含有n个结点的二叉排序中查找某关键字的结点时，最多进行()次比较。A、n/2B、log2nC、log2n+1D、n答案：D40.设串s为一个长度为n的串，其中各字符不相同，则s中真子串的数目是()。A、n(n-1)/2B、n(n+1)/2C、n(n+1)/2+1D、n(n-1)/2+1答案：B41.对下图所示的有向图进行拓扑排序，可以得到不同的拓扑序列的个数是()A、4B、3C、2D、1答案：B42.二叉排序树中，最大关键字结点()。A、没有左孩子结点B、没有右孩子结点C、一定没有左右孩子结点D、一定存在左右孩子结点答案：B43.设哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。A、99B、100C、101D、102答案：B44.串是—种特殊的线性表,其特殊性体现在()。A、可以顺序存储B、数据元素是单个字符C、可以链式存储D、数据元素可以是多个字符答案：B45.堆的形状是一棵()。A、满二叉树B、二叉判定树C、平衡二叉树D、完全二叉树答案：D46.对如下图所示的有向图进行拓扑排序，得到的拓扑序列可能是()A、3，1，4，2.6,5B、3,1，2，4，5，6C、3,1，2，4，6.5D、3，1，4，2，5，6答案：A47.对于只在表的首尾两端进行插入操作的线性表宜采用的存储结构为()。A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表答案：C48.一个n个顶点的连通无向图.其边的个数至少为()。A、n-1B、nC、n+1D、nlog2n答案：A49.稳定的排序方法是()。A、直接插入排序和快速排序B、折半插入排序和起泡排序C、简单选择排序和四路归并排序D、树形选择排序和hel排序答案：B50.以下()方法在数据基本有序时效率最好。A、快速排序B、冒泡排序C、堆排序D、希尔排序答案：B51.n个顶点的连通图的生成树有()个顶点。A、n-1B、nC、n+1D、不确定答案：B52.有一组数据(15.9.7.8.20.-1,7.4).用快速排序的划分方法进行一趟划分后数据的排序为()(按递增序)。A、其它选项都不对B、9.7.8.4-1.7.15.20C、20.15,8.9.7-1.4.7D、9.4.7.87.-1.15,20答案：A53.在排序算法中，每次从未排序的记录中挑出最小(或最大)关键码字的记录,加入到已排序记录的末尾该排序方法是()。A、选择B、冒泡C、插入D、堆答案：A54.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用()存储方式节省时间。A、单链表B、双链表C、单循环链表D、顺序表答案：D55.对特殊矩阵采用压缩存储的主要目的是（)。A、表达变得简单B、对矩阵元素的存取变得简单C、去掉矩阵中多余的元素D、减少不必要的存储空间答案：D56.链接存储的存储结构所占存储空间（)。A、分为两部分，一部分存放结点值,另一部分存放表示结点间关系的指针B、只有一部分，存放结点值C、只有一部分,存储表示结点间关系的指针D、分两部分，—部分存放结点值，另一部分存放结点所占单元数答案：A57.n个顶点的连通图的生成树有()条边。A、nB、n-1C、n+1D、不确定答案：B58.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()。A、数组的元素处在行和列两个关系中B、数组的元素必须从左到右顺序排列C、数组的元素之间存在次序关系D、数组是多维结构，内存是一维结构答案：D59.哈希查找的基本思想是根据()来决定元素的存储地址。A、元素的序号B、元素个数C、关键字值D、非关键字属性值答案：C60.若元素a、b、C、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是()。A、dcebfaB、cbdaefC、bcaefdD、afedcb答案：D61.若从无向图的任意一个顶点出发进行一次深度优先搜索，可以访问图中所有的顶点，则该图一定是（）图。A、非连通B、连通C、强连通D、有向答案：B62.数据结构是具有()的数据元素的集合。A、性质相同B、相同物理结构C、数据项D、相互关系答案：D63.函数(f(x:y)定义如下:

F(xy)=f(x-1.y)+f(x,y-1)当x>0且y>0

F(xy)=x+y否则

则f(2,1)的值是()。A、1B、2C、3D、4答案：D64.以下关于哈希查找的叙述中错误的是（)。A、用拉链法解决冲突易引起堆积现象B、用线性探测法解决冲突易引起堆积现象C、哈希函数选得好可以减少冲突现象D、哈希函数H(k)=kMODp，p通常取小于等于表长的素数答案：A65.有数据(30.37.1245.24.963.从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小则应选择下面哪个序列输入?()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,53答案：B66.线性表中哪些元素只有一个直接前驱和一个直接后继?()A、首元素B、尾元素C、中间元素D、所有的元素答案：C67.内排序方法的稳定性是指()。A、经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变B、经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变C、排序算法的性能与被排序元素的数量关系不大D、排序算法的性能与被排序元素的数量关系密切答案：A68.为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。A、队列B、栈C、线性表D、有序表答案：A69.设栈的输入序列是1、2、...、m.若输出序列的第一个元素是n.,则第i个输出元素是()。A、不确定B、n-i+1C、iD、n-i答案：B70.表达式的.2(42024215*求值过程中当扫描到时，对象栈和算符栈为(),其中为乘幂，为表达式开始和结束的界定符。A、3,2.4,1,1;#*^(+*-B、3,2.8;#*^-C、3,2.4,2,2;#*^-D、3.2.8;*^<-答案：D71.若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是()。A、257B、258C、384D、385答案：C72.下列四个序列中，哪一个是堆?()A、75.65.30.15.25.45.20.10B、75,6545.10.3025.20.15C、7545.65.30.15.25.20.10D、75.45,65,10.25.30,20,15答案：C73.一棵含有n个结点的线索二叉树中，其线索个数为()。A、2nB、n-1C、n+1D、n答案：C74.在一个无向图中，所有顶点的度数之和等于图的边数的()倍。A、1/2B、1C、2D、4答案：C75.把一棵树转化为二叉树后，这棵二叉树的形态是()。A、唯一的B、有多种C、有多种，但根结点没有左孩子D、有多种，但根结点没有右孩子答案：A76.一棵具有1025个结点的二叉树的高h为()。A、10B、11C、11至1025之间D、10至1024之间答案：C77.已知一棵完全二叉树的第6层(设根为第一层)有8个叶子结点，则该完全二叉树的结点个数最多是()。A、39B、52C、111D、119答案：C78.采用顺序查找方法查找长度为n的线性表时，成功查找的平均查找长度为()。A、nB、n/2C、(n+1)/2D、(n-1)/2答案：C79.哈希查找方法一般适用于()情况下的查找。A、查找表为链表B、查找表为有序表C、关键字集合比地址集合大得多D、关键字集合与地址集合之间存在着某种对应关系答案：D80.分别以下列序列构造二叉排序数，与用其他三个序列所构造的结果不同的是（)。A、(100,80,90,60，120，110，130)B、(100，120，110，130,80，60,90)C、(100,6o,80,90，120,110，130)D、(100，80，60，90,120，130,110)答案：C81.以下与数据的存储结构无关的术语是()。A、循环队列B、链表C、哈希表D、栈答案：D82.设散列表的长m-14.散列函数为a(太=以%11,表中已有4个记录如表所示),如果采用二次探测再苏敞列采处理冲突则天键子力+9的记录具仔储地址是()。A、8B、3C、5D、9答案：D83.若一个栈以向量V[1-n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是()。A、top++;V[top]=x;B、V[top]=x;top++;C、top--;V[top]=x;D、V[top]=x;top--;答案：C84.二维数组A的每个元素是由10个字符组成的串，其行下标-=1..8.列下标=1.2,:-;10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素()的起始地址相同。设每个字符占1个字节。A、A[8,5]B、A[3,10]C、A[5,8]D、A[0.9]答案：B85.对序列{15.9.7.8.20-1.4.3.用希尔排序方法排序,经一趟后序列变为{15,-1.4.8,20.9.7}.则该次采用的增量是()。A、1B、4C、3D、2答案：B86.在含有n(n>2)个数据结点的数据结构中，终端结点是指()的结点。A、没有前趋结点B、含有一个或多个前趋结点C、没有后继结点D、含有一个或多个后继结点答案：B87.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()。A、0(1)B、O(n)C、O(m)D、O(m+n)答案：C88.设有数组A[iu，数组的每个元素长度为3个字节i的值为1~8，j的值为1~10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8]的存储首地址为A、BA+141B、BA+180C、BA+222D、BA+225答案：B89.下面几个符号串编码集合中，不是前缀编码的是()。A、{0.10.11.111}B、{11.10,001,101,0001}C、{00,010,0110,1000}D、{b.c.aa,ac,aba,abb,abc}答案：B90.在一个图中，每个顶点的前趋顶点和后继顶点数可以有()。A、1个B、2个C、任意多个D、0个答案：C91.在一个具有n个结点的有序单链表中插入-个新结点并使插入结点后的单链表仍然有序则该操作的时间复杂性量级是()。A、O(1)B、O(n)C、O(nlog2n)D、O(n2)答案：B92.在线性表的下列运算中，不改变数据元素之间结构关系的运算是()。A、插入B、删除C、排序D、定位答案：D93.某队列允许在其两端进行入队操作，但仅允许在-端进行出队操作，元素abcde依次入队列，则不可能得到的出队顺序是()。A、bacdeB、dbaceC、dbcaeD、ecbad答案：C94.折半查找有序表(4.6.10,12.20,30,50,70,88,100)。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。A、20,70,30,50B、30,88,70,50C、20,50D、30,88,50答案：A95.具有n个顶点的有向图最多有()条边。A、nB、n(n-1)C、n(n+1)D、n*n答案：B96.正确的递归算法应包含()。A、递归出口B、递归体C、递归出口和递归体D、以上都不包含答案：C97.已知图的邻接表如下图所示，则从顶点V,出发按深度优先遍历的结果是（)。A、1032B、0123C、0321D、0231答案：B98.设森林F中有3棵树，第一、第二和第三棵树的结点个数分别为9、8和7，则与森林F对应的二叉树根结点的右子树上的结点个数是()。A、16B、15C、7D、17答案：B99.以下排序中，()不需要进行关键字的比较。A、快速排序B、归并排序C、基数排序D、堆排序答案：C100.线性表(a1，a2，…,an)以链接方式存储时，访问第i个位置上元素的时间复杂度为（)。A、O(i)B、O(1)C、o(n)D、O(i-1)答案：C101.对n阶对称矩阵压缩存储时，需要表长为()的顺序表。A、n/2B、n2/2C、n(n+1)/2D、n(n-1)/2答案：C102.以下数据结构中,哪一个是线性结构?()A、广义表B、二叉树C、稀疏矩阵D、串答案：D103.以下叙述中错误的是()。A、图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次B、图的深度优先遍历适合无向图C、图的深度优先遍历不适合有向图D、图的深度优先遍历是一个递归过程答案：C104.若需在o(nlogn)的时间内完成对数组的排序,且要求排序是稳定的.则可选择的排序方法是()。A、快速排序B、堆排序C、归并排序D、直接插入排序答案：C105.设图的邻接矩阵A如下图所示。各顶点的度依次是()A、1，2，1.2B、2,2，1，1C、3,4，2，3D、4，4，2，2答案：C106.查找效率低的数据结构是（）A、有序顺序表B、二叉排序树C、堆D、二叉平衡树答案：C107.对序列{15,9,7,8,20,-1,4}进行排序,经一趟排序后的排列为{9.15,7,8,20,-1.4]}.则采用的是()排序。A、选择B、堆C、直接插入D、冒泡答案：C108.下图的深度优先搜索序列为()。A、DFS(A)-ABEDCFB、DFS(A):AEFCDBC、DFS(A):ABCEDFD、DFS(A):ACBDEF答案：B109.线性表的顺序存储结构是一种()。A、随机存取的存储结构B、顺序存取的存储结构C、索引存取的存储结构D、散列存取的存储结构答案：A110.一个栈的入栈序列是.b,c.d.e.则栈的不可能的输出序列是()。A、edcbaB、decbaC、dceabD、abcde答案：C111.如图所示的循环队列中元素数目是()。

其中tail=32指向队尾元素head=15指向队头元素的前一个空位置队列空间m=60。A、42B、16C、17D、41答案：C112.若森林F有15条边、25个结点，则F包含树的个数是()。A、8B、9C、10D、11答案：C113.队列的删除操作是在()进行。A、队首B、队尾C、队前D、队后答案：A114.一个递归算法必须包括（)。A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分答案：B115.设有100个元素的有序表，用折半查找时，不成功时最大的比较次数是()。A、25B、50C、10D、7答案：D116.线性表中各元素之间的关系是()关系。A、层次B、网状C、有序D、集合答案：C117.下面（）算法适合用于构造一个稠密图的最小生成树。A、Dijkstra算法B、Prim算法C、Floyd算法D、Kruskal算法答案：B118.在一棵深度为h的具有n个元素的二叉排序树中,查找所有元素的最长查找长度为()。A、nB、1og2nC、(h+1)/2D、h答案：D119.静态查找与动态查找的根本区别在于()。A、它们的逻辑结构不一样B、施加在其上的操作不同C、所包含的数据元素的类型不-样D、存储实现不一样答案：B120.设串长为n,模式串长为m.则KMP算法所需的附加空间为()。A、o(m)B、o(0)C、O(nlog'm)D、o(m*n)E、其他答案：A121.下面的叙述中不正确的是()。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成将使整个工程提前完成C、所有关键活动都提前完成，则整个工程将提前完成D、某些关键活动若提前完成将使按个工程提前完成答案：B122.在—棵平衡二叉树中,每个结点的平衡因子取值范围是()。A、-1~1B、-2~2C、1~2D、0~1答案：A123.5个字符有如下4种编码方案，不是前缀编码的是()。A、01，0000，0001，001，1B、011，000，001，010，1C、000，001，010，011，100D、0，100，110.1110.1100答案：D124.下列说法中,正确的有()A、最小生成树也是哈夫曼树B、最小生成树唯一C、普里姆(Prim)最小生成树算法时间复杂变为0(2)D、克鲁斯卡尔(Kruska)最小生成树算法比普里姆算法更适合于边稠密的网答案：C125.以下不属于内排序方法的是()。A、二路归并排序B、拓扑排序C、堆排序D、直接插入排序答案：B126.快速排序方法在(情况下最不利于发挥其长处。A、要排序的数据量太大B、要排序的数据中含有多个相同值C、要排序的数据个数为奇数D、要排序的数据已基本有序答案：D127.图的遍历是指()。A、访问图的所有顶点B、以某种次序访问图的所有顶点C、从一个顶点出发访问图中所有顶点且每个顶点只能访问一次D、从一个顶点出发访问图中所有顶点但每个顶点可以访问多次答案：C128.在一棵深度为的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为()。A、nB、1og2nC、(h+1)/2D、h答案：D129.某算法的空间复杂度为O(1)，则()。A、该算法执行不需要任何辅助空间B、该算法执行所需辅助空间大小与问题规模n无关C、该算法执行不需要任何空间D、该算法执行所需全部空间大小与问题规模n无关答案：B130.表达式#3*2^(4+2*2-6*3)-5#求值过程中当扫描到6时,对象栈和算符栈为(),其中^为乘幂,#为表达式开始和结束的界定符。A、3,2,4,1,1;#*^(+*-B、3,2,8;#*^-C、3,2,4,2,2;#*^(-D、3,2,8;#*^(-答案：D131.栈和队列的主要区别在于()。A、它们的逻辑结构不一样B、它们的存储结构不一样C、所包含的运算不--样D、插入、删除运算的限定不一样答案：D132.将一个A[..100.1.10o]的三角矩阵.按行优先存入一维数组B...298]中.A中素af6,f(即该元素下标i=66j=-65),在B数组中的位置k为()。A、198B、195C、197D、199答案：B133.下面关于散列查找的说法，不正确的是()。A、采用链地址法处理冲突时，查找任何一个元素的时间都相同B、采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的C、用链地址法处理冲突，不会引起二次聚集现象D、用链地址法处理冲突，适合表长不确定的情况答案：A134.以下说法错误的是()。A、存在这样的二叉树,对它采用任何次序遍历其结点访问序列均相同B、二叉树是树的特殊情形C、由树转换成二叉树,其根结点的右子树总是空的D、在二叉树只有一棵子树的情况下也耍明确指出该子树是左子树还是右子树答案：B135.在单链表的一个结点中有()个指针。A、1B、2C、3D、4答案：A136.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是()。A、存在，且唯一B、存在，且不唯一C、存在，可能不唯一D、无法确定是否存在答案：C137.假定一个顺序循环队列存储于数组A[]中.其队首和队尾指针分别用from和rear表示则判断队满的条件是()。A、(rcar-1)%n==frontB、(rear+1)%n=-frontC、rear==(front-1)%nD、rear==(front+1)%n答案：B138.利用逐点插入法建立序列50.724385.75.20.35.45.,65,30}对应的二叉排序树以后查找元素35要进行()元素间的比较。A、4次B、5次C、7次D、10次答案：A判断题1.无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下(或上)三角阵。()A、正确B、错误答案：A2.顺序查找只能在顺序存储结构上进行。A、正确B、错误答案：B3.循环链表不是线性表。A、正确B、错误答案：B4.递归算法转换为非递归算法时，通常借助于队列来实现。A、正确B、错误答案：B5.队列逻辑上是一个下端和上端既能增加又能减少的线性表。()A、正确B、错误答案：A6.数据的逻辑结构与各数据元素在计算机中如何存储有关。A、正确B、错误答案：B7.线性表的逻辑顺序与物理顺序总是—致的。()A、正确B、错误答案：B8.二叉树就是结点度为2的树。()A、正确B、错误答案：B9.栈是一种特殊的线性表，其特殊之处在于栈的存储结构比较特殊。A、正确B、错误答案：B10.任何数据结构都具备3个基本运算:插入、删除和查找。A、正确B、错误答案：B11.稀疏矩阵压缩存储后，必会失去随机存取功能。()A、正确B、错误答案：A12.对一个堆按二叉树层次进行遍历可以得一个有序列。()A、正确B、错误答案：B13.二叉树中每个结点至多有两个孩子结点，而一般树没有这种限制，所以二叉树是树的特殊情形。A、正确B、错误答案：B14.哈夫曼树中是带权路径长度最短的二叉树，权值越大的结点离根结点越远。A、正确B、错误答案：B15.栈具有先进后出的特点，其中数据的逻辑结构是任意的。A、正确B、错误答案：B16.影响外排序的时间因素主要是内存与外存交换信息的次数。A、正确B、错误答案：A17.由二叉树的中序遍历序列和后序遍历序列,能够唯―确定该二叉树。A、正确B、错误答案：A18.二叉排序树是用来进行排序的。A、正确B、错误答案：B19.由二叉树的先序遍历序列和后序遍历序列，能够唯一确定该二叉树。A、正确B、错误答案：B20.散列表的结点中包含数据元素自身的信息,不包含任何指针。()A、正确B、错误答案：B21.在任意一棵非空二叉树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉树排序树相同。()A、正确B、错误答案：B22.一种逻辑结构的数据只有一种对应的存储结构。A、正确B、错误答案：B23.数据的运算描述是定义在数据的逻辑结构上的。A、正确B、错误答案：A24.由一棵二叉树的前序序列和后序序列可以唯一确定它。()A、正确B、错误答案：B25.队列是一种对进队、出队操作的次数做了限制的线性表。A、正确B、错误答案：B26.栈和队列逻辑上都是线性表。A、正确B、错误答案：A27.顺序查找方法只能从顺序表的前端向后端查找。A、正确B、错误答案：B28.n个元素进队的顺序和出队的顺序总是一致的。A、正确B、错误答案：A29.直接选择排序算法在最好情况下的时间复杂度为O(n)。()A、正确B、错误答案：B30.用棉尔咖方法排序时，若关键字的初始排序杂乱无序则排序效率就低。A、正确B、错误答案：B31.空栈是指栈中元素没有赋值。A、正确B、错误答案：B32.给定一棵树,可以找到唯一的一棵二叉树与之对应。()A、正确B、错误答案：A33.线性表中所有元素的数据类型必须相同。A、正确B、错误答案：A34.将二叉树变为线索二叉树的过程称为线索化。A、正确B、错误答案：A35.哈夫曼树中结点个数可以是偶数也可以是奇数。A、正确B、错误答案：B36.从逻辑关系上讲.数据结构主要分为两大类:线性结构和非线性结构。()A、正确B、错误答案：A37.递归的算法简单、易懂、容易编写，而且执行效率也高。A、正确B、错误答案：B38.二路归并排序算法的时间复杂度与初始数据序列的顺序无关。A、正确B、错误答案：A39.对于有N个结点的二叉树,其高度为1og2n。()A、正确B、错误答案：B40.顺序存储的线性表可以随机存取。()A、正确B、错误答案：A41.哈夫曼树中是带权路径长度最短的二叉树，权值越大的结点离根结点越远。A、正确B、错误答案：B42.数据运算的实现是基于数据的逻辑结构的。A、正确B、错误答案：B43.二叉排序树可以是一棵空树。A、正确B、错误答案：A44.非空二叉树的中序序列的最后一个结点一定是叶子结点。A、正确B、错误答案：B45.循环队列通常用指针来实现队列的头尾相接。()A、正确B、错误答案：B46.哈希表发生冲突是由于选取的解决冲突的方法不当造成的。A、正确B、错误答案：B47.只要是算法，肯定可以在有限的时间内完成。A、正确B、错误答案：A48.在二叉树的第i层上至少有2i-1个结点(i>=1)。()A、正确B、错误答案：B49.一棵树中的叶子数-定等于与其对应的二叉树的叶子数。()A、正确B、错误答案：B50.在队空间大小为n的非循环队列中，最多只能进行n次进队操作。A、正确B、错误答案：A51.任何一个图，一旦指定源点，其深度优先遍历序列是唯一的。A、正确B、错误答案：B52.在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点。()A、正确B、错误答案：B53.一个图中的简单路径是指该路径上的边不重复出现。A、正确B、错误答案：B54.线性表中的结点按前趋、后继关系可以排成一个线性序列。A、正确B、错误答案：A55.用链表(link-rlink)存储包含个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。A、正确B、错误答案：A56.栈的定义不涉及数据的逻辑结构。A、正确B、错误答案：B57.在有向图中，如果顶点i到顶点j有路径，而顶点到顶点k没有路径，则顶点j到顶点k也没有路径。A、正确B、错误答案：A58.线性表的顺序存储结构优于链式存储结构。A、正确B、错误答案：B59.在单链表中要访问某个结点只要知道该结点的指针即可:因此，单链表是一种随机存储结构。A、正确B、错误答案：B60.栈在算法设计中用于保存临时数据,这些数据具有先进后出的特点，如果某算法中只产生一个临时数据，那么用栈和队列都可以。A、正确B、错误答案：A61.在无向图中，如果顶点i到顶点j有路径，而顶点j到顶点k没有路径，则顶点i到顶点k也没有路径。A、正确B、错误答案：A62.对于无向图生成树，从同一顶点出发所得到的生成树一定是相同的。A、正确B、错误答案：B63.非空二叉树的后序序列的最后一个结点一定是叶子结点。A、正确B、错误答案：B64.循环队列也存在空间溢出问题。(,A、正确B、错误答案：A65.外排序与外部设备的特性无关。A、正确B、错误答案：B66.图的深度优先搜索序列和广度优先搜索序列不是唯一的。()A、正确B、错误答案：A67.在线性表的顺序存储结构中插入和删除元素时，移动元素的个数与该元素的位置有关。A、正确B、错误答案：A68.由二叉树的先序遍历序列和中序遍历序列，能够唯一确定该二叉树。A、正确B、错误答案：A69.KMP算法的最大特点是指示主串的指针不需回溯。()A、正确B、错误答案：A70.调用自身的函数称为递归函数。A、正确B、错误答案：A71.如果连通网中存在相同权值的边，则最小生成树不唯一。()A、正确B、错误答案：A72.用链表(link-rlink)存储包含n个结点的二叉树结点的2n个指针区域中有n-1个空指针。A、正确B、错误答案：B73.队列是一种对进队、出队操作的次序做了限制的线性表。A、正确B、错误答案：B74.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。A、正确B、错误答案：B75.一个递归算法可以没有递归体，但必须包含递归出口部分。A、正确B、错误答案：B76.在初始数据表已经有序时:快速排序算法的时间复杂度为0(1og2n)。()A、正确B、错误答案：B77.二叉树中不存在度大于2的结点当某个结点只有一棵予树时无所谓左、右子树之分。A、正确B、错误答案：B78.空串是由空格构成的串。A、正确B、错误答案：B79.内排序过程在数据量很大时就变成了外排序过程。A、正确B、错误答案：B80.用邻接矩阵存储一个图时，所占用的存储空间大小只与图中结点的个数有关而与图的边数无关。()A、正确B、错误答案：A81.二叉排序树的任意-棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。A、正确B、错误答案：A82.线性表的长度是线性表占用的存储空间的大小。A、正确B、错误答案：B83.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入删除等操作。A、正确B、错误答案：B84.无向图的邻接矩阵一定是对称矩阵,且有向图的邻接矩阵一定是非对称矩阵。()A、正确B、错误答案：B85.二叉树就是度为2的有序树。A、正确B、错误答案：B86.哈希冲突是指同一个关键宇对应多个不同的哈希地址。A、正确B、错误答案：B87.对于无向图生成树，其深度优先生成树和广度优先生成树一定不相同。A、正确B、错误答案：B88.数据的逻辑结构是指数据的各数据项之间的逻辑关系。()A、正确B、错误答案：B89.图的遍历就是访问图中所有顶点。A、正确B、错误答案：B90.连通分量是无向图中的极小连通子图。()A、正确B、错误答案：B填空题1.如果结点A有3个兄弟，而且B是A的双亲则B的度是()。答案：42.字符串中任意个连续的字符组成的子序列称为该串的()。答案：子串3.已知一无向图G=(,),其中V={a,b,c,d,e},E={(a,b)（a，d）（a，c）（d，c）（b，e）}，现用某一种遍历方法从顶点a开始遍历图，得到的序列为adbce,则采用的是()遍历方法。答案：广度优先4.根据二叉树的定义.具有三个结点的二叉树有()种不同的形态。答案：55.下面程序段的时间复杂度是()。

I=0;

S=0;.

While(s<n)

{

I++;

S+=1;

}答案：0(√n)6.含有n个顶点的无向图都连通全部顶点至少需要()条边。答案：n-17.顺序表中第一个元素的存储地址为100，每个元素的长度为2.则第五个元素的存储地址为()。答案：1088.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,那么它的先序遍历序列是()。答案：|cedba9.用一维数组存放一棵完全二叉树:ABCDEFGHIJKL.则后序遍历该二叉树的结点序列为()。答案：HIDJKEBLFGCA10.对于一棵具有n个结点的树.该树中所有结点的度数之和为()。答案：n-111.在有n个顶点的有向图中,每个顶点的度最大可达()。答案：2(n-1)12.设正文串长度为n,模式串长度为m，则串匹配的KMP算法的时间复杂度为()。答案：O(n+m)13.有一个循环队列Q，存储空间的大小为10，起始时Q.front=O，Q.rear=5，执行进队3个数据元素，再出队2个数据元素以后Qfront的值为(),Q.rear的值为（）答案：2|814.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,那么它的先序遍历序列是()。答案：|cedba15.组成串的数据元素只能是()。答案：字符16.设有序表有100个元素用折半查找法查找最大比较次数为().最小比较次数为()。答案：|7|117.两个串相等的充分必要条件是()。答案：两个串的长度相等且对应的字符相同18.图中所有顶点的度之和为图中边数的()倍。答案：219.有n个顶点的无向图最多有（）条边。答案：n(n-1)/220.数据结构是一门研究非数值计算的程序设计问题中计算机的()以及它们之间的()和运算的学科。答案：操作对象|关系21.空格串是()，其长度等于()。答案：由一个或多个空格字符组成的串|其包含的空格个数22.已知有序表为12.12435.47562,3.9.115,134).当用二分法查找90时，需进行()次查找可确定成功查找100时,需进行()次查找才能确定不成功。答案：2|323.一棵完全二叉树有999个结点它的深度是()。答案：1024.如下图的树中.结点H的祖先为()。答案：A、D、G25.二叉树共有()种不同的形态。答案：526.肚分法查找一个线性表时，该线性表必须具有的特点是().而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的,但块与块之间()。答案：顺序存储且有序|有序27.设有一个顺序共享栈S[0:n-1]，其中第一个栈顶指针top1的初值为-1,第二个栈顶指针top22的初值为n，则判断共享栈满的条件是()。答案：Top1+1==top228.一棵含有50个结点的二叉树，它的最小高度是（)。答案：629.算法具有5个特性，分别是有零个或多个输入有一个或多个输出，().().()。答案：有穷性|确定性|可行性30.具有10个顶点的无向图.边的总数最多为()。答案：4531.一棵含有50个结点的二叉树，它的最大高度是()答案：5032.已知一无向图G=(V,E).其中V={a,b,c,d,e},E={(a,b),(a,d),(a,c),(d,c),(b,e)},现用某一种遍历方法从顶点a开始遍历图，得到的序列为adbce,则采用的是()遍历方法。答案：|深度优先|简答题1.编写算法实现:有一个长度大于2的整数单链表L，设计一个算法查找L的中间位置的元素。例如:L=(1,2,3),返回元素2;L=(1,2,3.4)，返回元素为2。

要求:

(1)写出单链表的Python语言定义;

(2)描述算法的基本设计思想

(3)根据设计思想，完成算法代码的编写。答案：(1)单链表的存储结构的定义如下:

ClassLinkNode:

#单链表结点类

Def_init_(self,data=None):

Self.data=data

Self.next=None

ClassLinkList.

#单链表类

Def_init_(self):

Self.head=LinkNode(

Self.head.next=None

(2)算法的基本思想(参考):

1)计算出单链表L的长度n;

2）若首结点的编号为1，则中间位置的元素编号为(n-1)/2+1，置j=1,p指向首结点，让其后移(n-1)/2-1个结点即可;

3）返回p的数据元素。

(3)参考算法:

DefMiddle1(L):

J=1

N=L.getsize(

P=Lhead.next

Whilej<=(n-1)//2:

J+=1

P=p.next

Returnp.data2.简述栈和队列的相同点和不同点。答案：

相同点:从数据的逻辑结构角度来看，栈和队列都是线性结构;从操作的角度来看，栈和队列都是操作受限的线性表。

不同点:栈是限定仅在表