数据结构提纲及答案

数据结构模拟试题一一、判断题（每小题1分，共15分）计算机程序处理的对象可分为数据和非数据两大类。全体自然数按大小关系排成的序列是一个线性表。在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。顺序栈是一种规定了存储方法的栈。树形结构中的每个结点都有一个前驱。在任何一棵完全二叉树中，最多只有一个度为1的分支结点。若某顶点是有向图的根，则该顶点的入度一定是零。如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。用一维数组表示矩阵可以节省存储空间。广义表的长度与广义表中含有多少个原子元素有关。分块查找的效率与线性表被分成多少块有关。散列表的负载因子等于存入散列表中的结点个数。在起泡排序过程中，某些元素可能会向相反的方向移动。按某种逻辑关系组织起来的记录的集合称为逻辑记录。索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。二、填空题（每空1分，共15分）顺序表是一种 线性表。若用Q[1卜Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行—次插入操作。栈和队列的区别在于 的不同。在高度为h（h20）的二叉树中至少有—个结点，至多有—个结点。若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有—个左指针域为空的结点，有—个右指针域为空的结点。n个顶点的有根有向图中至少有—条边，至多有—条边。10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是在归并两个长度为m的有序表时，排序码的比较次数至少是—次，至多是—次。在高度为3的6阶B-树中，至少有—个关键字，至多有—个关键字。三、选择题（每题2分，共30分）计算机所处理的数据一般具有某种内在联系性，这是指 。A•元素和元素之间存在某种关系 B.数据和数据之间存在某种关系元素内部具有某种结构D.数据项和数据项之间存在某种关系假设顺序表目前有4个元素，第i个元素放在R[i]中，1WiW4。若把新插入元素存入R[6],则 。A•会产生运行错误B.R[1]~R[6]不构成一个顺序表顺序表的长度大于顺序表元素个数，会降低存储空间利用率顺序表元素序号和数组元素下标不一致，会给使用带来麻烦设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时， A•P所指结点指针字段的值为空 B.P的值与H的值相等P所指结点的地址与H的值相等D.P所指结点指针字段的值与H的值相等TOC\o"1-5"\h\z栈的定义不涉及数据的 。A•逻辑结构B.存储结构C.运算D.逻辑结构和存储结构设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是 。A．2,4,1,3,5B．3,4,1,5,2C．3,2,4,1,5D．4,1,3,2,5若某棵二叉树结点的前序序列和中序序列相同，则该二叉树 。A•只有一个结点B.每个结点都没有左孩子 C.每个结点都没有右孩子 D.不存在7•对于一棵具有n个结点，度为3的树来说， 。A•树的高度至多是n-3B.树的高度至多是n-2 C.树的最低高度是厂log3（n+l）n至少在某一层上正好有3个结点n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图 。A•含n个强连通分量 B.有唯一的入度为0的顶点C.有多个出度为0的顶点D.是一个有根有向图特殊矩阵用行优先顺序表表示， A•简化了矩阵元素之间的逻辑关系 B.便于按行处理矩阵元素C.无法根据行列号计算矩阵元素的存储地址 D.可以节省存储空间TOC\o"1-5"\h\z对一个非空的广义表来说， 。A•可能不含任何原子元素 B.至少含一个原子元素C.其长度不小于其中任何一个子表的长度 D.至少含一个非空的子表元素在有序表（2,4,6,8,10,12,14,16,18,20）上用折半查找方法查找13，依次被比较的是 。A•10,16,12,14B.10,16,12C.12,16,14D.10,16,12,13含14个结点的平衡二叉排序树，其最大深度是 。A．4B．5 C．6 D．713•如果元素叫和R2有相同的排序码，并且进行归并排序前，叫在R2的前面，则当排序结束后， 。A．R1有可能在R2的后面B．R1一定在R2的后面C.R1一定在R2的前面D.选择R1或R2中的一个留在线性表中下面4个序列中，只有___满足堆的定义。A.13,27,49,76,76,38,85,97 B.76,38,27,49,76,85,13,97C.13,76,49,76,27,38,85,97 D.13,27,38,76,49,85,76,97下面4种排序方法中，属于不稳定的排序方法是 排序和 排序。A•快速B.归并C.简单选择D.折半插入数据结构模拟试题二判断题（每小题1分，共15分）构成数据的最小单位是数据项。空线性表的一个特性是线性表中各结点尚未赋值。非循环单向链表一定要有表头指针。顺序栈的栈顶指针是一个指针类型的变量。在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。哈夫曼树中不存在度为1的结点。在图中，与Vi相邻的顶点其序号一定是i+1或i-1。i如果是不连通的无向图，则在相应的邻接表中一定有空链表。矩阵的行数和列数可以不相等。广义表的深度与广义表中含有多少个子表元素有关。折半查找可以在有序的双向链表上进行。散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。对n个元素执行简单选择排序，排序码的比较次数总是n（n-1）/2次。物理记录的大小与逻辑记录的大小成正比。对索引文件，索引表是建立在内存的，数据区是建立在外存的。填空题（每空1分，共15分）在程序中，描述顺序表的存储空间一般用 变量。若用Q[0]~Q[100]作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r的值”作为队空的标志，则创建一个空队列所要执行的操作是 。栈和顺序栈的区别仅在于 。n个结点的二叉树最大高度是___，最小高度是___。树的存储方法主要有 、 和 三种。n个顶点的强连通图中至少有___条边。10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第___个元素。在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个元素，元素间的平均比较次数至少TOC\o"1-5"\h\z是 次，至多是 次。对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是 次，至少是___次。在B-树中，若某结点有i个孩子，则该结点中一定有___个关键字。选择题（每题2分，共30分）数据结构的研究内容不涉及 。A•算法用什么语言来描述 B.数据如何存储数据的运算如何实现 D.数据如何组织若H1是动态单向链表的表头指针，H2是动态双向链表的表头指针，则 。A•H1和H2占用同样多的内存空间B.H1和H2是同类型的变量C．H2要比H1占用更多的内存空间双向链表要比单向链表占用更多的内存空间对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用 。A•同一个数组B.某些数组元素C.同一个表头结点 D同一个表头指针最不适合用作链接栈的链表是 。A•只有表头指针没有表尾指针的循环双向链表只有表尾指针没有表头指针的循环双向链表只有表尾指针没有表头指针的循环单向链表只有表头指针没有表尾指针的循环单向链表TOC\o"1-5"\h\z栈和队列的共同点在于 。A•都对存储方法作了限制 B.都是只能进行插入、删除运算 C.都对插入、删除的位置作了限制 D.都对插入、删除两种操作的先后顺序作了限制如果5个元素的出栈的顺序是1,2,3,4,5，则进栈的顺序可能是 。A•3,5,4丄2 B.1,4,5,3,2 C.2,4,3,1,5 D.5,1,3,2,4若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树 。A•每个结点都没有右孩子 B.不存在度为2的结点C.每个结点都没有左孩子D.不存在8•对于一棵具有n个结点，度为3的树来说，树的高度至少是 。A.厂log2nq B.厂log(3n—l)qC.厂log(3n+l)q D.厂log(2n+l)q9•对n个顶点的带权连通图来说，它的最小生成树是指图中任意一个由3n-1条 。A•权值最小的边构成的子图 B.权值之和最小的边构成的子图 C.权值之和最小的边构成的连通子图 D.权值之和最小的边构成的无环子图所谓特殊矩阵是指 比较特殊。A•矩阵元素之间的关系B.矩阵的处理方法C.矩阵元素的取值 D.矩阵的存储方法TOC\o"1-5"\h\z若长度为n且有n种不同原子的广义表用链接方法存储，则时间复杂度为O(n)的运算是 。A•复制一个广义表B.求广义表的长度 C.查找某个子表 D.查找某个原子12•待查找元素关键字的值依次是47,且已存入变量k中，如果在查找过程中，和K进行比较的关键字值依次是47,32,46,25,47,则采用的查找方法 。A•是一种错误的查找方法 B.可能是分块查找 C.可能是顺序查找 D.可能是折半查找13•如果元素叫和R2有相同的排序码，并且进行堆排序前，叫在R2的前面，则当排序结束后， 。A•R1一定在R2的前面B.R1一定在R2的后面C.R1有可能在R2的后面D.选择R1或R2中的一个留在线性表中14.下面4种排序方法中，属于稳定的排序方法是 排序和 排序。A•堆B.基数C.快速D.起泡15．在线性表中元素很多，且各元素已有序排列的情况下，执行 排序或 排序，排序码比较次数最多。A•简单选择B.堆C.归并D.堆数据结构模拟试题三一．判断题(每小题1分，共10分)逻辑结构不同的数据，要采用不同的存储方法来存储。单链表中的结点只有后继，没有前驱。栈和队列具有相同的逻辑特性。二叉树中结点之间的相互关系不能用二元组来表示。关键路径是由权值最大的边构成的。在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小无关。在广义表中，每个原子必须是单个字符。在平衡二叉排序树中，每个结点的平衡因子值是相等的。只有在线性表的初始状态为逆序排列的情况下，起泡排序过程中，元素的移动次数才会达到最大值。在B+树上可以进行顺序查找。二．填空题(每空1分，共10分)若用不带表头结点的单链表来表示链接队列，则只有在 情况下，插入操作既要修改队尾指针的值，也要修改队头指针的值;只有在 情况下，删除操作仅需修改队首指针的值，不需修改队尾指针的值。无向图中边的数目等于邻接矩阵中 。在各元素查找概率相等的情况下，在含有12个元素的二叉排序树上查找其中一个元素，元素间的平均比较次数至少是 次，至多是 次。对12个元素进行快速排序，排序码的比较次数最多是___次。对B+树来说，若某个非根分支结点中有6个关键字，则在它的某个孩子结点中至少有 个关键字，至多有 个关键字。TOC\o"1-5"\h\z如果在根结点中要查到要找的关键字，则对于B-树来说，下一步应该 ，而对于B+树来说，下一步应该 。三．单选题(每题2分，共20分)线性结构采用链式存储， 。A•对插入、删除结点的操作较为有利 B.不利于进行顺序访问C.逻辑上相邻的结点在存储器中也相邻D.可以用一些不连续的存储区域来存放一个结点某算法的时间复杂度为O(2n)，表明该算法的 。A•执行时间与2n成正比B.执行时间等于2nC.问题规模是2n D.问题规模与2n成正比在长度为n的 上，删除最后一个元素，其算法的时间复杂度是O(n)。A•只有表头指针的循环双向链表 B.只有表头指针的非循环双向链表C.只有表尾指针的非循环双向链表D.只有表尾指针的循环双向链表TOC\o"1-5"\h\z在4个元素的进栈序列给定以后，由这4个元素构成的可能出栈序列共有 种。A•14 B.16C.17 D.24在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序列、后序序列中， 。A．结点b一定在a的前面B．结点a一定在结点c的前面C．结点b一定在结点c的前面D．结点a一定在结点b的6•若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是 。A•dbacefB.acbedfC.efbacdD.bafdce对稀疏矩阵采用压缩存储，其优点之一是可以 。A•减少非零元素的存储空间B.不减少访问非零元素所需时间C.减少矩阵的存储空间 D.降低非零元素间逻辑关系的复杂程度设待查找元素关键字的值是47,且已存入变量k中，如果在查找过程中，和k进行比较的关键字值依次是82,72,36,84,47,则所采用的查找方法可能是 。A•顺序查找B.分块查找C.折半查找D.平衡二叉排序树查找9．在线性表中元素很多且各元素逆序排列的情况下，执行 排序，元素的移动次数最少。A•直接插入B.起泡C.简单选择D.折半插入10.8阶方阵，每个元素占1个单元，按行优先顺序存储，起始地址为100，存储地址为135的那个元素是矩阵中每5行第___列的元素。A．2B．3C.4D.5数据结构模拟试题四一、 (共30分，每题2分)单项选择题1•循环队列用数组A[O..m-l]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为()A．(rear-front+m)modmB．rear-front+1 C．rear-front-1D．rear-front E．以上答案都不对2．数据结构中，与所使用的计算机无关的是数据的()A.存储结构 B•物理结构 C•逻辑结构D.物理结构和存储结构E•以上答案都不对3．在具有n个结点的单链表中，实现()的操作，其算法的时间复杂度都是O(n)。A.遍历链表和求链表的第i个结点B•在地址为p的结点之后插入一个结点 C•删除开始结点 D•删除地址为p的结点的后继结点E.以上答案都不对4•某二叉树的前序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为()A．JLKMNOIB．LKNJOMIC．LKJNOMID．LKNOJMIE．以上答案都不对5．设n阶方阵是一个上三角矩阵，则需存储的元素个数为()A.nB•n*nC•n*n/2D•n(n+1)/2 E.以上答案都不对6．串的“模式匹配”是指()A.判两个串是否相等 B•对两个串进行大小比较 C•找某字符在串中第一次出现位置D•找某子串在主串中第一次出现的位置 E•以上答案都不对7•有n个结点的无向图的边数最多为()A.n+1B•n(n-1)/2C•n(n+1)D•2n(n+1)E.以上答案都不对多关键字文件是指()A有多个主关键字B有多个次关键字C有一个主关键字多个次关键字D有多个主关键字和多个次关键字E以上答案都不对9．某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（）A.25000B.30000C.45000D.90000 E.以上答案都不对10．对于序列（49,38,65,97,76,13,27,50）按由小到大进行排序，（）是初始步长d=4的希尔排序法第一趟的结果。A.49,76,65,13,27,50,97,38 B.13,27,38,49,50,65,76,9797,76,65,50,49,38,27,13 D.49,13,27,50,76,38,65,97以上答案都不对11．下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在其最终位置的算法是（）A．归并排序 B．直接插入排序 C．快速排序冒泡排序 E•以上答案都不对12．关于树和二叉树的有序性，正确的结论是（）A.树和二叉树都是有序的B．树和二叉树都可能是有序的C.树和二叉树都是无序的 D•二叉树是有序的，树可能是有序的，也可能是无序的 E•以上答案都不对13．在一个图中，所有顶点的度数之和与图的边数的比是（）A.1:2B.1:1C.2:1D.4:1 E.以上答案都不对若一组纪录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个纪录为基准得到的一次划分结果为（）A 38， 40， 46， 56， 79，84 B 40，38，46，79，56，84C 40， 38， 46， 56， 79，84 D 40，38，46，84，56，79E以上答案都不对从理论上讲，将数据以（）结构存放，则查找一个数据所用时间不依赖于数据个数n。A二叉查找树B链表C二叉树D哈希表E以上答案都不对二、（共40分，每空2分）填空题二分查找算法的时间复杂度为（）在单链表中，申请到新结点p,将p指向的结点后插到s所指结点的操作，其一是p->next=s->next，其二是（）。对一般树和森林的后序遍历序列的次序与对应的二叉树的（）遍历次序相同。设二维数组A[10..20,5..10]按行优先存储，每个元素占4个单元，A[10,5]的地址为160，则A[15,10]的地址为（）。线性结构反映结点间的逻辑关系是（）的，非线性结构反映结点间的逻辑关系是（）的。赫夫曼树是带权路径长度（）的二叉树。前序为abc且后序为cba的二叉树共有（）棵。已知完全二叉树的高度为8，第7层有10个叶子结点，则二叉树的总结点数至少是（）。已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为（）。具有m个叶子结点的赫夫曼树共有（）个结点。从一棵二叉树的前序序列和（）可唯一确定这棵二叉树。设某二叉树的后序遍历为ABKCBPM，则可知该二叉树的根为（）。设广义表C=（（x,（a,b））,（（x,（a,b））,y））,则C的长度为（），深度为（）。.设有一稠密图G，则G采用（）存储较省空间。在插入和选择排序中，若初始数据基本正序，则选用（）；若初始数据基本反序，则选用（）。有n结点的二叉链表中，空指针域有（ ）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继的指针，这种附加的指针称为（ ）。数据结构模拟试题五一、（共34分，每题2分）单项选择题1、 在非空循环双链表中q所指的结点前插入一个由p所指结点的过程依次为：p->next=q；p->prior=q->prior；q->prior=p；（）；Aq->next=p B q->prior->next=p Cp->prior->next=pDp->next->prior=p E 以上答案都不对2、 已知有向图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>，<v3,v7>，<v6,v7>}，G的拓扑序列是（）。Av1,v3,v4,v6,v2,v5,v7 B v1,v3,v2,v6,v4,v5,v7Cv1,v3,v4,v5,v2,v6,v7 D v1,v2,v5,v3,v4,v6,v7E以上答案都不对3、 每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函数值对应结点的存储位置，该存储方式是（）存储方式A顺序B链接C索引D散列E以上答案都不对4、对于单链表形式的队列，队空的条件是（ ）

A.F=R=nil B.F=R C.FHnil且R=nil D.R—F=lE．以上答案都不对5、采用邻接表存储的图的深度优先遍历算法类似于树的（ ）。A．中根遍历 B．先根遍历C．后根遍历D．按层次遍历E．以上答案都不对6、对于序列（49,38,65,97,76,13,27,50）按由小到大进行排序，（ ）是初始步长d=4的希尔排序法第一趟的结果。A．49,76,65,13,27,50,97,38B．13,27,38,49,50,65,76,97C．97,76,65,50,49,38,27,13D．49,13,27,50,76,38,65,97E．以上答案都不对TOC\o"1-5"\h\z7、 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。A．O（n） B．O（1） C．O（n2） D．O（log2n）E．以上答案都不对8、设n阶方阵是一个上三角矩阵，则需存储的元素个数为（ ）。A．n B．n*n C．n*n/2 D．n（n+1）/2 E．以上答案都不对9、树中所有结点的度等于所有结点数加（ ）。A．0B．1 C．－1 D．2 E．以上答案都不对10、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。A．起泡排序 B．快速排序 C．堆排序D．直接选择排序E．以上答案都不对11、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（ ）。A．（rear-front+m）modm B．rear-front+1 C．rear-front-1D．rear-front E．以上答案都不对12、若线性表最常用的运算是查找第i个元素及其前驱的值，则采用（）存储方式节省时间。A．单链表 B．双链表 C．单循环连表D．顺序表E．以上答案都不对TOC\o"1-5"\h\z13、树最适合用来表示（ ）A．有序数据元素 B．无序数据元素 C．元素之间无联系的数据D．元素之间有分支层次关系 E．以上答案都不对14、多关键字文件是指（ ）A．有多个主关键字B．有多个次关键字 C．有一个主关键字多个次关键字D．有多个主关键字和多个次关键字 E．以上答案都不对15、有m个叶子结点的赫夫曼树所具有的结点数为（ ）A．m B．m+1 C．2m D．2m-1 E．以上答案都不对、有n个结点的有向完全图的边数为（ ）A．n*n B．2n C．n（n-1） D．2n（n+1） E．以上答案都不对17、判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。A．求关键路径的方法B．求最短路径的DIJKSTRA方法C．深度优先遍历算法D．广度优先遍历算法E．以上答案都不对二、（共30分，每空2分）填空题1、在进行直接插入排序时,其数据比较次数与数据的初始排列（）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（）关。2、对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为（），所有边链表中边结点的总数为（）。3、数据的逻辑结构可形式地用一个二元组B=（K,）来表示，其中K是（ ）,是（ ）。4、链表适用于（ ）查找。4、链表适用于（ ）查找。5、 通常程序在调用另一个程序时，都需要使用一个（空间以及返回地址。6、 对一般树和森林的后序遍历序列的次序与对应的二叉树的（7、 前序为abc且后序为cba的二叉树共有（）棵。8、 设广义表C=（（x,（a,b））,（（x,（a,b））,y））,则C的长度为（9、 快速排序的平均时间复杂度是（ ）。）来保存被调用程度内分配的局部变量、形式参数的存储）遍历次序相同。），深度为（）。）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继TOC\o"1-5"\h\z10、有n结点的二叉链表中，空指针域有（的指针，这种附加的指针称为（ ）。）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继三：（共11分,每题1分）判断题（下列各题，你认为正确的，请打“J”，错的打“氷”）1、线性表采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（ ）2、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。（ ）3、 二叉排序树或者是一颗空二叉树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值若它的右子树非空，则根结点的值小于其左孩子的值。（ ）4、 凡是递归定义的数据结构都可以用递归算法来实现它的操作。（ ）5、 当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（）6、 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为05）。（）7、 在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。（ ）8、 执行某个排序算法过程中，最初相邻的结点排序后也相邻，则算法是稳定的。（ ）9、 对具有n个顶点的连通图进行深度优先遍历，所得定点序列是唯一的。（）10、由于在线性表的链接存储表示中增加了指针字段，所以它比线性表的顺序表示更浪费空间。 （）11、 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵则一定是非对称矩阵。（ ）数据结构模拟题一参考答案一.判断题1、氷2、氷3、氷4、J5、氷6、J7、氷.8、J9、