宿州学院期末考试数据结构习题集.doc

个人收集整理 勿做商业用途数据结构习题一、单项选择题 1对矩阵进行压缩存储是为了（A） A节省存储空间 B提高运算速度 C便于运算 D方便存储2链式栈与顺序栈相比，一个比较明显的优点是（B） A插入操作更加方便 B通常不会出现栈满的情况 C不会出现栈空的情况 D删除操作更加方便3设输入序列为1，2,3,4，5，则借助一个队列可以得到的输出序列是（C）先进先出 A3,4，1，2，5 B1，2，3，4，5 C2，3，4，1，5 D5，4，3,2，14.一个栈的输入序列是6，5，4，3，2，1，可能的输出序列是( C ）先进后出 A4，3,2，1,5，6 B3,6，2,1，5，4 C1，2，3,5，4,6D5,4，1，3,2,65设输入序列为A，B，C，D。借助一个栈可以得到的输出序列是（A） AA，C，D，B BC，A，D，B CD,C,A，B DD,A，B，C6将含100个结点的完全二叉树从根开始,每层从左到右依次对结点编号，根结点的编号为1,则编号为71的结点的双亲结点的编号为（A） A34 B35 C36 D无法确定7已知完全二叉树有80个结点，则该二叉树有 （B) 个度为1的结点。 A0 B1 C2 D不确定8任何一个无向连通图的最小生成树（A） A只有一棵 B有一棵或多棵 C一定有多棵 D可能不存在9设图G用邻接表存储，对该图进行深度优先搜索遍历，则算法的时间复杂度为 （） A O（n) B O(n+e) C O(n2) D O（n3）10用n个键值构造一棵二叉排序树，最低高度为（） An/2 Bn C2n D2n+111如果以链表作为栈的存储结构，则执行出栈操作时（） A必须判断栈是否满 B必须判断栈是否空 C判断栈元素的类型 D对栈不作任何判断12设数组Datam作为循环队列SQ的存储空间,front为队头指针，rear为队尾指针,则执行出队操作的语句为 () Afront=front+1 Bfront=（front+1）%m Crear=(rear+1)m Dfront=(front+1)%（m+1)13线性表的长度是指（） A顺序存储方式下数组所占用的元素个数 B链表存储方式下的结点个数 C表中的元素个数 D所能存储的最大的结点个数 14设有一个无向图G（V，E)和G=（V，E)，如果G是G的生成树,则下面不正确的说法是（） AG为G的子图 BG为G的连通分量 CG为G的极小连通子图且V=V DG是G的一个无环子图15在采用线性探测法处理冲突所构成的闭散列表上进行查找,可能要探测多个位置,在查找成功的情况下，所探测的这些位置上的键值（） A一定都是同义词 B一定都不是同义词 C都相同 D不一定都是同义词16在有序表A20中按二分查找方法查找A13依次比较的元素的下标是（） A9,14，12，13 B9,15，12,13 C9，14，11,12，13 D10，15，12，1317栈和队列都是（)A顺序存储的线性表 B链式存储的线性表 C限制的线性表 D限制存储点的非线性结构18向顺序栈中压入新元素时，应当（） A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针C 先后次序无关紧要 D同时进行19若树的先序序列和中序序列正好相同，则一定是一棵 (） 的二叉树。A结点个数可能大于1且该树无左子树 B结点个数可能大于1且根结点无左孩子C结点个数可能大于1且各结点均无左孩子 D其中任意一个结点的度不为220下列算法中，在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的算法是( ）A归并排序 B直接插入排序 C快速排序 D冒泡排序21当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较元素的次数为 （）An2 Bn2n C2n Dn-122下列排序算法中,在最好情况下，时间复杂度为O（n）的算法是（） A直接选择排序 B归并排序 C快速排序 D冒泡排序23下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是（) A直接插入排序 B冒泡排序 C直接选择排序 D快速排序24对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作,直到子序列为空或只剩一个元素为止。这样的排序方法是（） A直接选择排序 B直接插入排序 C快速排序 D起泡排序25对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较. A8 B10 C15 D2526在一个具有n个结点的双链表中插入一个新结点,则该操作的时间复杂性的量级为(） AO(1) BO（n） CO(nlog2n） DO（n2) 27二分查找法要求被查找的表是 ()A顺序表 B分块有序表 C顺序表且是按键值递增或递减次序排列 D不受上述任何限制28若某线性表中最常用的操作是在最后一个元素之后插人一个元素和删除第1个元素，则采用（）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C仅有尾指针的单循环链表 D双链表29在一个顺序存储的循环队列中，队头指针指向队头元素的（) A前一个位置 B后一个位置 C队头元素位置 D队尾元素的前一个位置30设循环队列用数组An存储，头尾指针为front和rear，求解当前队列中元素个数的公式 （ )Arear-front Bfront-rear Cn-(frontrear） D（n+rear-front)n31已知完全二叉树有100个结点，则该完全二叉树共有(）个叶子结点。A 37 B 49 C 50 D不确定32下列存储形式中，(）不是树的存储形式。 A双亲表示法 B左子女右兄弟表示法 C广义表表示法D顺序表示法33在一棵具有5层的满二叉树中结点总数为（) A31 B32 C33 D1634设有100个数据元素，采用折半搜索时，最大比较次数为（） A6 B7 C8 D1035在顺序存储的线性表(a1，a2，.。,an)中,删除任意一个结点时所需移动结点的平均次数为（） An Bn/2 C(n1）/2 D（n+1）/2 36下列说法不正确的是() A数据元素是数据的基本单位 B数据项是数据中不可分割的最小标识单位 C数据可由若干个数据元素构成 D数据项可由若干个数据元素构成 37为了方便在线性结构的数据中插入一个数据元素，则其数据结构宜采用( ）方式 A顺序存储 B链式存储 C索引存储 D散列存储 38矩阵A56的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A55的地址为 (） A1120 B1125 C1140 D114539设矩阵A(aij，0i，j9）的元素满足：aij0 (ij，0i,j9） aij =0 （ir1=st1；sr1t1=s-r1； Bst1r1=sr1；s-r1t1=s-t1;Cs-r1=s-t1r1;st1=srt1； Dst1=st1r1；s-r1=s-r-t1；66。假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点（中间结点)的直接后继结点插入到该双向链表中,则下列算法段能正确完成上述要求的是（ )Aqright=s; sleft=q; q-rightleft=s; s-right=q-right；Bsleft=q； qright=s; qrightleft=s; sright=q-right;Csleft=q; s-right=qright; q-rightleft=s； qright=s;D以上都不对67。已知一个稀疏矩阵的三元组表如下：(1，2，3)，（1，6，1）,（3，1，5)，(3，2，1），(4，5，4)，（5，1，-3),则其转置矩阵的三元组表中第3个三元组为（ )A（2，1，3） B(3，1，5) C(3，2,1) D(2，3，-1）68。顺序查找法与二分查找法对存储结构的要求是（ )A. 顺序查找与二分查找均只适用于顺序表 B顺序查找只适用于顺序表C顺序查找与二分查找既适用于顺序表，也适用于链表 D二分查找只适用于顺序表69.程序段for (i=0；in； i+)for (j=1;jnextnext=head，则( ) Ap指向头结点 Bp指向尾结点 Cp的直接后继是头结点 D*P的直接后继是尾结点72.广义表A=(a，（b)，()，(c,d，e）)的长度为（ ) A4 B5 C6 D773.无向图中一个顶点的度是指图中( ) A通过该顶点的简单路径数 B与该顶点相邻接的顶点数 C通过该顶点的回路数 D与该顶点连通的顶点数74。已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( ） Aa c e f b d Ba c b d f e Ca c b d e f Da c d b f e75。设顺序存储的线性表共有123个元素,按分块查找的要求等分成3块.若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（ ) A21 B23 C41 D6276。下面的二叉树中,（ ）不是完全二叉树.77.下列说法错误的是（ ）。A一个图的邻接矩阵表示是唯一的 B一个图的邻接表表示是不唯一的C一个图的生成树必为该图的极小连通子图 D一个无环有向图的拓扑排序序列必唯一78。设有6个结点的无向图，该图至少应有（ )条边才能确保是一个连通图。A5 B6 C7 D879。二叉树在线索化后，仍不能有效求解的问题是( ) A先序线索二叉树中求先序后继 B中序线索二叉树中求中序后继 C中序线索二叉树中求中序前趋 D后序线索二叉树中求后序后继80.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素,则采用( ）排序算法最节省时间. A堆排序 B希尔排序 C快速排序 D直接选择排序81若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是（ ） AO(1） BO（n） CO(n2) DO(nlog2n）82在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较（ )个结点。 An Bn2 C(n-1)2 D（n+1）283研究数据结构就是研究( ） A数据的逻辑结构 B数据的存储结构 C数据的逻辑结构和存储结构本文为互联网收集，请勿用作商业用途本文为互联网收集，请勿用作商业用途D数据的逻辑结构、存储结构及其数据在运算上的实现84设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（ ）个结点。 A13 B12 C26 D2585.下列四种排序方法中，不稳定的方法是( ) A直接插入排序 B冒泡排序 C归并排序 D直接选择排序 86下列说法中不正确的是( ) A无向图中的极大连通子图称为连通分量 B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D有向图的遍历不可采用广度优先搜索方法87下列说法中不正确的是（） A图的遍历过程中每一顶点仅被访问一次 B遍历图的基本方法有深度优先搜索和广度优先搜索两种 C图的深度优先搜索的方法不适用于有向图 D图的深度优先搜索是一个递归过程 88对有序表(18，20，25,34，48，62，74，85）用二分查找法查找85，所需的比较次数为( ）A1次 B2次 C3次 D4次89散列表的平均查找长度（ ) A与处理冲突方法有关而与表的长度无关 B与处理冲突方法无关而与表的长度有关 C与处理冲突方法有关且与表的长度有关 D与处理冲突方法无关且与表的长度无关90.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ） A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构 91。若进栈序列为a,b,c，则通过入出栈操作可能得到的a，b,c的不同排列个数为( ) A4 B5 C6 D7 92.三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A45的存储地址为（ ） A356 B358 C360 D362 93.下列陈述中正确的是（ ） A二叉树是度为2的有序树 B二叉树中结点只有一个孩子时无左右之分 C二叉树中必有度为2的结点 D二叉树中最多只有两棵子树，并且有左右之分 94.n个顶点的有向完全图中含有向边的数目最多为（ ） An-1 Bn Cn(n1）/2 Dn（n1) 95。设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1。5,则散列存储空间应能够至少容纳（ ）个表项。（设搜索成功的平均搜索长度为Snl=(1+1/(1a)/2，其中a 为装填因子）A400 B526 C624 D67696.在有向图中每个顶点的度等于该顶点的(）A入度 B出度 C入度与出度之和 D入度与出度之差97。一个二叉树按顺序方式存储在一维数组中，如图则结点E在二叉树的第( ）层。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ABCDEFGHIJA1 B2 C3 D498设某线性链表的头结点指针为L， Ldata表示该链表的结点个数，L-next指向该链表的第一个结点，p指向新建立的结点，其类型与L相同。在建立该链表的过程中,若希望L-next始终指向新输入的结点，可采用如下的C语言语句实现：( ）A. p-next=Lnext， L-next=p，Ldata+; B。 p-next=NULL, Lnext=p, Ldata+;C. L-data+， L-next=pnext, pnext=L； D.以上都不是。99。以数组Q0.m-1存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ) Arear qulen Brear - qulen + m Cm - qulen D1 +（rear + m qulen)% m 100.设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后,则x和y的关系是( ） Ax是y的左兄弟 Bx是y的右兄弟 Cx是y的祖先 Dx是y的后代 101.对线性表进行二分查找时,要求线性表必须（ )。A以顺序方式存储 B以链接方式存储C以顺序方式存储，且结点按关键字有序排序 D以链接方式存储，且结点按关键字有序排序二、判断题(若正确在( ）内打，否则打.） （ ) 1对链表执行插入和删除操作时，不必移动结点.( ) 2双链表中只有一个结点的后继指针为空。（ ） 3数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。( ） 4线性表的逻辑顺序与物理顺序总是一致的.（ ） 5线性表的顺序存储表示优于链式存储表示.( ） 6栈是实现函数调用的必不可少的数据结构。（ ) 7线性表的长度是线性表所占用的存储空间的大小.( ） 8在带头结点的单链表中插入元素结点不会改变头指针的值.（ ) 9对链队列执行出队操作不会改变尾指针的值.（ )10树(或森林)转化为对应的二叉树后，两者的分支数相等。（ )11由给定的n个权值所构造的哈夫曼树可能不唯一,其结点个数也可能不确定。( ）12图中一个顶点i的出度等于其邻接矩阵中第i列的非0元素个数。（ )13二叉树是树的特殊情形。（ )14所谓冲突即是两个关键字的值不同的元素，其散列地址相同。（ ）15二叉树的先序序列和后序序列正好相反。（ ）16在循环队列中,若尾指针rear大于头指针front，则其元素总数为rear-front( ）17一个有向图的邻接表和逆邻接表中的结点个数一定相等。( )18在编号的完全二叉树中(根结点的编号为1)，编号为100的结点一定在其左子树中。( ）19在索引顺序表的查找中，对索引表的查找既可采用顺序查找法，也可采用二分查找法。( )20对同一组键值的不同顺序的输入序列，所构造的二叉排序树一定不同.（ ）21稀疏矩阵只能用三元组表压缩存储.( )22在一个大根堆中，关键字最大的两个元素一定在数据表的前三个元素中.（ ）23线性表采用链表存储后，线性表的长度等于链表中的结点个数（ ）24双循环链表中，任一结点的前趋指针均指向其逻辑前趋。（ ）25如果一棵二叉树的中序序列是递增有序序列，则一定是一棵二叉排序树.( )26对一个有序表作二分查找，查找每个元素所需的查找次数均比用顺序查找所需的查找次数要少。( )27对有n个元素的数据表用直接选择排序方法进行排序，最好情况下所需的时间复杂度是O(n）。（ ）28快速排序算法是所有排序算法中时间复杂度最好的一种排序算法。（ ）29顺序表用一维数组作为存储结构,因此顺序表是一维数组.（ )30通常使用两个类来协同表示单链表，即链表的结点类和链表类。（ ）31具有n个结点的完全二叉树的高度为log2(n+1)。（n=0，根结点在第0层）( ）32闭散列法通常比开散列法时间效率更高。( )33已知指针P指向单链表L中的某结点，执行语句P=Pnext不会删除该链表中的结点。（ ）34在链队列中，即使不设置尾指针也能进行入队操作。（ ）35如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ )36数据的逻辑结构与数据元素本身的内容和形式无关。（ )37从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。( )38由于希尔排序的最后一趟与直接插入排序过程相同,因此前者一定比后者花费的时间多.（ )39数据的基本单位是数据项.（ )40带权的无向连通图的最小生成树是唯一的。( )41用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。( ）42在霍夫曼编码中，当两个字符出现的频率相同时,其编码也相同，对于这种情况应当特殊处理。（ ）43。 线性表采用顺序存储表示时，必须占用一片连续的存储单元。（ ）44。 装载因子是散列表的一个重要参数,它反映了散列表的装满程度。( )45算法和程序没有区别,所以在数据结构中二者是通用的。( ）46在顺序表中无需为表示结点间的逻辑关系而增加存储空间.( )47单链表中的头结点就是单链表的第一个结点。（ )48队列和栈都是运算受限的线性表.（ ）49任何一棵二叉树中至少有一个结点的度为2。（ ）50对于n个记录的集合进行冒泡排序，所需要的平均时间是0(n）。（ )51一棵哈夫曼树中不存在度为1的结点。（ )52二叉树中的叶子结点就是二叉树中没有左右子树的结点.( )53一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( ）54由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树.（ ）55在用循环单链表表示的链式队列中,可以不设队头指针，仅在链尾设置队尾指针。（ ）56一个广义表的表尾总是一个广义表。（ )57对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序的遍历的时间复杂度为O（h）.( ）58数据结构是数据对象与对象中数据元素之间关系的集合.( )59所谓数据的逻辑结构是指数据元素之间的逻辑关系.（ ）60二维数组是其数组元素为一维数组的线性表，因此它是线性结构。( ）61若图G的最小生成树不唯一,则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数)。( )62用直接选择排序方法分别对序列S1=（1，2,3，4，5，6）和序列S2=（5，3,2，4，1，6) 进行排序，两者的比较次数不相同。( )63用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的. （ ）64当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止.( )65同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等.( )66若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果的最后一个结点.( )67如果二叉树中每个结点的值都大于其左孩子结点的值、小于其右孩子结