1、经典数据结构题目录第一部分 选择题 2第二部分 填空题 19第三部分 应用题 24第一部分 选择题1. 数据的四种基本逻辑结构是指（）A数组、链表、树、图形结构 B线性表、链表、栈、广义表C线性结构、链表、树、图形结构 D集合、线性结构、树、图形结构2. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用_表示A数据元素的相邻地址 B数据元素在表中的序号C指向后继元素的指针 D数据元素的值3. 顺序存储的线性表（a1,a2,a3an），在任一结点前插入一个新结点时所需移动结点的平均次数为 （）An Bn/2 Cn+1 D(n+1)/24栈和队列都是（）A限制存取位置的线性结构 B顺序存储
2、的线性结构C链式存储的线性结构 D限制存取位置的非线性结构5. 若有三个字符a、b、c依次入栈，入栈过程中可以出栈，而其不可能的出栈序列为（）Aa、b、c Bc、a、b Cc、b、a Db、a、c6稀疏矩阵一般采用_方法压缩存储。A三维数组 B单链表 C三元组表 D散列表7深度为5的二叉树至少有_个叶子（）A16 B15 C8 D78. 二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（）A2n个指针域，其中n个指针为NULLB2n个指针域，其中n+1个指针为NULLC2n-1个指针域，其中n个指针为NULLD2n-1个指针域，其中n+1个指针为NULL9. 具有3个结点的二叉树可有
3、_种形态。A3 B5 C6 D910. 在一个带权连通图G中，权值最小的边一定包含在G的 （）A最小生成树中 B深度优先生成树中C广度优先生成树中 D深度优先生成树中11. 能进行二分查找的线性表，必须以（）A顺序方式存储，且元素按关键字有序B链式方式存储，且元素按关键字有序C顺序方式存储，且元素按关键字分块有序D链式方式存储，且元素按关键字分块有序12. 散列文件不能（）A随机存取 B索引存取C按关键字存取 D直接存取13. 在题13图所示的各棵二叉树中，二叉排序树是（）14. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序方法，以第一个记录为基准得到的一次划分结果
4、为（）A38，40，46，56，79，84 B40，38，46，79，56，84C40，38，46，56，79，84 D40，38，46，84，56，7915. 堆排序属于一种选择排序，其时间复杂性为（）AO（1） BO（n）CO（n2） DO（log2n）16下列数据组织形式中，（ ）的结点按逻辑关系依次排列形成一个“锁链”。A.集合 B.树形结构C.线性结构 D.图状结构17数据结构可以形式化地定义为（S，），其中S指某种逻辑结构，是指（ ）A.S上的算法 B.S的存储结构C.在S上的一个基本运算集 D.在S上的所有数据元素18下列说法正确的是（ ）A.线性表的逻辑顺序与存储顺序总是一致的
5、B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算19设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（ ）A.s-next=p-next;p-next=s；B.p-next=s;s-next=p-next；C.s-next=p-next;p-next=s;交换p-data和s-data；D.p=s;s-next=p；20稀疏矩阵一般采用（ ）方法
6、压缩存储。A.三维数组 B.单链表C.三元组表 D.散列表21树若用双亲链表表示，则（ ）A.可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难22将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（ ）A.无左、右孩子 B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子23用邻接表作为有向图G的存储结构。设有n个结点、e条弧，则拓扑排序的时间复杂度为（ ）A.O(n) B.O(n+e)C.O(e) D.O(n*e)24如果从无向图的任一顶点出发进行一次深度优先搜
7、索即可访问所有顶点，则该图一定是（ ）A.完全图 B.连通图 C.有回路 D.一棵树25采用线性探测法解决冲突问题，所产生的一系列后继散列地址（ ）A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制26在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（ ）A.静态查找表 B.动态查找表C.静态查找表与动态查找表 D.两种表都不适合27由索引集、顺序集和数据集三部分组成的文件称为（ ）A.VSAM文件 B.散列文件C.顺序文件 D.索引文件28下列有关散列文件的说法中不正确的是（ ）A
8、.散列文件具有随机存放的优点B.散列文件只能按关键字存取C.散列文件需要索引区D.散列文件的记录不需要进行排序29一组记录的键值为（12，38，35，25，74，50，63，90），按2路归并排序方法对该序列进行一趟归并后的结果为（ ）A.12,38,25,35,50,74,63,90 B.12,38,35,25,74,50,63,90C.12,25,35,38,50,74,63,90 D.12,35,38,25,63,50,74,9030用快速排序方法对包含有n个关键字的序列进行排序，最坏情况下执行的时间复杂度为（ ）A.O(n) B.O(log2n)C.O(nlog2n) D.O(n2)3
9、1.下列数据结构中，( )不都是线性结构。A.栈和队列 B.队列和数组C.数组和串 D.文件和队列32.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。A.顺序存储 B.链式存储C.索引存储 D.散列存储33.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( )A.s-t1-r1=s-t1;s-r1-t1=s-r1;B.s-t1-r1=s-r1;s-r1-t1=s-t1;C.s-r1=s-t1-r1;s-t1=s-r-t1;D.s-t1=s-t1-r1;s-r1=s-r-t1;34.假设left和right为
10、双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( )A.q-right=s; s-left=q; q-right-left=s; s-right=q-right;B.s-left=q; q-right=s; q-right-left=s; s-right=q-right;C.s-left=q; s-right=q-right; q-right-left=s; q-right=s;D.以上都不对35.由下列三棵树组成的森林转换成一棵二叉树为( )36.具有10
11、0个结点的完全二叉树的深度为( )A.6 B.7 C.8 D.937.已知一个稀疏矩阵的三元组表如下：(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)38.无向图的邻接矩阵是一个( )A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵39.下列说法中正确的是( )A.一个具有n个顶点的无向完全图的边数为n(n-1)B.连通图的生成树是该图的一个极大连通子图C.图的广度优先搜索是一个递归过程D.对于非连通图的遍历过程
12、中每调用一次深度优先搜索算法都得到该图的一个连通分量40.顺序查找法与二分查找法对存储结构的要求是( )A.顺序查找与二分查找均只适用于顺序表B.顺序查找与二分查找既适用于顺序表，也适用于链表C.顺序查找只适用于顺序表D.二分查找只适用于顺序表41.在开散列表上，每个地址单元所链接的同义词表( )A.其键值相同 B.其元素值相同C.其散列地址相同 D.其含义相同42.散列文件中的记录通常成组存放，若干个记录组成一个存储单位，这个存储单位称为( )A.磁道 B.块 C.柱面 D.桶43.索引非顺序文件中的索引表是( )A.非稠密索引 B.稠密索引C.主索引 D.多级索引44.对n个记录的文件进行
13、堆排序，最坏情况下的执行时间为( )A.O(log2n) B.O(nlog2n)C.O(n) D.O(n2)45.一组记录的关键码为(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，7946下列说法正确的是（）A数据是数据元素的基本单位B数据元素是数据项中不可分割的最小标识单位C数据可由若干个数据元素构成D数据项可由若干个数据元素构成47数据结构的基本任务是（）A逻辑结构和存储结构的设计 B
14、数据结构的运算实现C数据结构的评价与选择 D数据结构的设计与实现48在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）AO（1） BO（n）CO（nlog2n） DO(n2)49顺序存储的线性表（a1,a2,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（）An Bn/2Cn+1 D(n+1)/250下列树U，经剪技运算DELETE（U，x，2）后为（）51一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（）A2，14 B2，15C3，14 D3，1552设有一5阶上三角矩阵A1.
15、5，1.5，现将其上三角中的元素按列优先顺序存放在一堆数组B1.15中。已知B1的地址为100，每个元素占用2个存储单元，则A3，4的地址为（）A116 B118C120 D12253一个带权的无向连通图的最小生成树（）A有一棵或多棵 B只有一棵C一定有多棵 D可能不存在54下列有关图遍历的说法中不正确的是（）A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C非连通图不能用深度优先搜索法D图的遍历要求每一顶点仅被访问一次55在最坏的情况下，查找成功时二叉排序树的平均查找长度（）A小于顺序表的平均查找长度 B大于顺序表的平均查找长度C与顺序表的平均查找长
16、度相同 D无法与顺序表的平均查找长度比较56闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A同义词之间发生冲突引起的B非同义词之间发生冲突引起的C同义词之间或非同义词之间发生冲突引起的D散列表“溢出”引起的57从外存设备的观点看，存取操作的基本单位是（）A逻辑记录 B数据元素C文件 D物理记录58对文件进行检索操作时，每次都要从第一个记录开始的文件是（）A顺序文件 B索引文件C顺序索引文件 D散列文件59一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（）A（14，18，38，46，65，40，20，53，86，74）
17、B（14，38，18，46，65，20，40， 53，86，74）C（14，18，20，38，40，46，53，65，74，86）D（14，86，20，38，40，46，53，65，74，18）60对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（）A选择排序 B冒泡排序C快速排序 D插入排序61下列数据组织形式中，（）的各个结点可以任意邻接。A集合 B树形结构C线性结构 D图状结构62设某二维数组A1.n，1.n，则在该数组中用顺序查找法查找一个元素的时间复杂性的量
18、级为（）AO（log2n） BO(n)CO(nlog2n) DO(n2)63在线性表的下列存储结构中，读取元素花费时间最少的是（）A单链表 B双链表C循环链表 D顺序表64将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为q=NULL;while (p!=NULL) （） p=q;Ar=q; q=p; p=p - next; q - next=r;Bq=p; r=q; p=p - next; q - next=r;Cr=q; p=p - next; q=p; q - next=r;Dq=p; p=p - next; r=q; q - next=r;65数组通
19、常具有两种基本运算，即（）A创建和删除 B索引和修改C读和写 D排序和查找66除根结点外，树上每个结点（）A可有任意多个孩子、任意多个双亲B可有任意多个孩子、一个双亲C可有一个孩子、任意多个双亲D只有一个孩子、一个双亲67具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（）个指针域为空。A50 B99C100 D10168邻接表是图的一种（）A顺序存储结构 B链式存储结构C索引存储结构 D散列存储结构69如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（）AG肯定不是完全图 BG一定不是连通图CG中一定有回路 DG有2个连通
20、分量70若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（）An/2 BnC(n+1)/2 Dn+171若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（）A该中间位置 B该中间位置1C该中间位置1 D该中间位置272散列文件不能（）A随机存取 B索引存取C按关键字存取 D直接存取73若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（）An/2 Bn Cn/4 Dlog n74下列关键码序列中，属于堆的是（）A（15，30，22，93，52，71） B（15，71，30，2
21、2，93，52）C（15，52，22，93，30，71） D（93，30，52，22，15，71）75已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（）A16，28，34，54，73，62，60，26，43，95B28，16，34，54，62，73，60，26，43，95C28，16，34，54，62，60，73，26，43，95D16，28，34，54，62，60，73，26，43，9576.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（）A.逻辑结构、存储结构、机外表示 B.存储结构
22、、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构 D.机外表示、存储结构、逻辑结构77.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（）A.对数阶量级复杂性大于线性阶量级B.对数阶量级复杂性小于线性阶量级C.对数阶量级复杂性等于线性阶量级D.两者之间无法比较78.下列关于线性表的基本操作中，属于加工型的操作是（）A.初始化、求表长度、插入操作 B.初始化、插入、删除操作C.求表长度、读元素、定位操作 D.定位、插入、删除操作79.在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是（）A.snext=pnext; pnext=s;
23、 B.pnext=snext; snext=p;C.snext=p; pnext=s; D.snext=pnext; p=s;80.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（）A.3种 B.4种C.5种 D.6种81.C语言对数组元素的存放方式通常采用（）A.按行为主的存储结构 B.按列为主的存储结构C.按行或列为主的存储结构 D.具体存储结构无法确定82.根据定义，树的叶子结点其度数（）A.必大于 0 B.必等于0C.必等于1 D.必等于283.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（）A.2n个指针域其中n个指针为NULLB.2n个指针域其中n+
24、1个指针为NULLC.2n-1个指针域其中n个指针为NULLD.2n-1个指针域其中n+1个指针为NULL84.在一个无向图中，所有顶点的度数之和等于边数的（）A.1倍 B.2倍C.3倍 D.4倍85.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（）A.先根遍历 B.中根遍历C.后根遍历 D.层次遍历86.采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为（）A.从第0个元素开始往后查找该数据元素B.从第1个元素开始往后查找该数据元素C.从第n个元素开始往前查找该数据元素D.从第n+1个元素开始往前查找该数据元素87.下列查找中，效率最高的查找方法是（）A.顺序查找 B.折半查
25、找C.索引顺序查找 D.分块查找88.索引文件通常由索引表和主文件两部分构成，其中（）A.索引表和主文件均必须是有序文件B.索引表和主文件均可以是无序文件C.索引表必须是有序文件D.主文件必须是有序文件89.直接插入排序算法，其时间复杂性为（）A.O(1) B.O(n)C.O(nlog2n) D.O(n2)90.下列排序方法中，属于稳定的排序方法是（）A.直接插入排序法 B.快速排序法C.冒泡排序法 D.堆排序法91.数据的四种基本逻辑结构是指( )A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构92.数据结构
26、中，通常采用两种方法衡量算法的时间复杂性，即( )A.最大时间复杂性和最小时间复杂性 B.最好时间复杂性和最坏时间复杂性C.部分时间复杂性和总体时间复杂性D.平均时间复杂性和最坏时间复杂性93.下列关于线性表的叙述中，不正确的是( )A.线性表是n个结点的有穷序列B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继D.线性表结点间的逻辑关系是1:1的联系94.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( )A.p=p-next B.p-next=p-nextC.p-next=p-next-next D.p-next=p95.栈和队列( )A
27、.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处96.二维数组A56采用按列为主序的存储方式，每个元素占3个存储单元，若A00的存储地址是100，则A43的存储地址是( )A.127 B.142 C.150 D.15797.深度为k的二叉树至多有( )A.2k个结点 B.2k-1个结点C.2k-1个结点 D.2k-1-1个结点98.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )A.ABCDEF B.ABECDFC.CDFBEA D.CBDAEF99.下面关于生成树的描述中，不正确的是( )A.生成树是树的一种表现形式 B.生成树一定是连通的C.生成树一定不含有环 D.若生成树顶点个数为n，则其边数一定为n-1100.图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是( )A.V1V2V3V4V5 B.V1V2V3V5V4C.V1V4V3V5V2 D.V1V3V4V5V2101.下列查找方法中，不属于动态的查找方法是( )A.二叉排序树法 B.平衡树法
