数据结构试题及答案

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！1.描述一个求解问题的抽象数据类型由？两部分组成。[填空题]*_________________________________答案：数据逻辑结构和抽象运算)2.算法具有？5个重要特征[填空题]*_________________________________答案：有穷性、确定性、可行性、输入和输出)3.一个数据结构在计算机中的？称为存储结构[填空题]*_________________________________答案：映像)4.通常从四个方面评价算法的质量？[填空题]*_________________________________答案：正确性、易读性、强壮性、高效率正确易读,强壮高效))5.算法的时间复杂度取决于？[填空题]*_________________________________答案：问题的规模和待处理数据的初态)6.在分析算法的时间复杂度时，通常认为算法的执行时间是？的函数[填空题]*_________________________________答案：问题规模)7.数据结构是一门研究程序设计中数据的元素以及他们之间的？等的学科[填空题]*_________________________________答案：关系和运算)8.算法分析的主要任务之一是？[填空题]*_________________________________答案：算法的执行时间和问题规模之间的关系)9.算法分析的目的是？[填空题]*_________________________________答案：分析算法的效率以求改进)15.单链表中设置头结点的作用是？[填空题]*_________________________________答案：n、2n-1)_________________________________答案：(n+1)/2)动元素的次数是？25.链队，在进行插入或删除运算时？[]*_________________________________答案：头、尾指针可能都要修改)26.共享栈，当？时才产生上溢[填空题]*_________________________________答案：两个栈的栈顶在栈空间的某一位置相遇)27.若某堆栈的输入序列是1，2，3，…，n，输出序列的第一个元素为n，则第i个输出元素为？[]*_________________________________答案：n-i+1)28.如果用单链表表示链式栈，则栈顶一般设在链表的？[填空题]*_________________________________答案：链头)29.链栈与顺序栈相比，比较明显的优点是？[填空题]*_________________________________答案：不会出现空间浪费问题)30.适合用作链队的链表是：_________最不适合用作链队的链表是：_________最不适合用作链栈的链表是：_________[]*空1答案：带队首指针和队尾指针的非循环单链表空2答案：只带队首指针的非循环双链表空3答案：只有表头指针没有表尾指针的循环单链表31.共享栈的好处是？填空题]*_________________________________答案：节省存储空间,降低上溢出发生的几率)32.串的长度是指？[]*_________________________________答案：串中所含字符的个数)33.含n个不同字符的串的子串个数为？[]*_________________________________答案：n(n+1)/2+1)34.在串匹配中一般将主串称为：_________将子串称为：_________[填空题]*空1答案：目标串35.两个字符串相等的充要条件是[填空题]*36.串是一种特殊的线性表，其特殊性体现在[填空题]*_________________________________答案：模式匹配)空2答案：j=0空1答案：i不变44.一维数组ai的存储地址公式：[填空题]*45.特殊矩阵包括[]*46.上三角矩阵公式[]*_________________________________答案：请设置答案)49.对角矩阵公式[]*空1答案：节省存储空间空2答案：随机存取特性空1答案：三元组和十字链表空2答案：顺序存储结构空3答案：链式存储结构52.广义表中的数据元素是有相对次序的[]*对正确答案)错53.广义表可以共享[]*对正确答案)错54.将一个n阶下（上）三角矩阵采用压缩存储，共存储[填空题]*_________________________________答案：n(n+1)/2+1)55.矩阵a[m][n]和矩阵b[n][p]相乘，其时间复杂度为[填空题]*_________________________________答案：O(mnp))56.对稀疏矩阵采用压缩存储的缺点之一是无法根据行、列号直接计算矩阵元素的存储地址[判断题]*对正确答案)错57.稀疏矩阵用十字链表表示优点在于便于实现增加或减少矩阵中非零元素的操作[判断题]*对正确答案)错58.对于含有n个结点的树（或者二叉树），无论度为多少，其分支数或所有结点度之和均为[填空题]*_________________________________答案：n-1)59.树的存储结构主要有[填空题]*空1答案：1空2答案：请设置答案空3答案：请设置答案结点[填空题]*空1答案：n+1/2空2答案：n-1/263.70.先序和中序相同的条件是二叉树中[]*对正确答案)错_________________________________答案：后序遍历)76.对正确答案)对正确答案)对正确答案)错80.顺序存储结构下的数据元素为层次遍历结果[判断题]*对正确答案)错81.完全有向图的邻接矩阵是对称的[判断题]*对正确答案)错82.深度优先遍历可以找到所有路径，而广度优先遍历可以找到最短路径[判断题]*对正确答案)错83.如果一个有向图的拓扑序列是唯一的，则图中必定[填空题]*_________________________________答案：仅有一个顶点的入度为0,一个顶点的出度为0)84.一个AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条[判断题]*对正确答案)错85.一个AOE网的关键路径不一定是唯一的，但其关键路径长度一定是唯一的[判断题]*对正确答案)错86.n个结点完全无向图的边数为：_________，n个结点完全有向图的边数为_________[填空题]*空1答案：n(n-1)/2空2答案：n(n-1)87.对于邻接矩阵而言：无向图的边数矩阵中1元素个数的和/2，有向图的边数=矩阵中1元素个数的和[判断题]*对正确答案)错88.对于邻接表而言：无向图的边数边结点个数的和/2，有向图的边数边结点个数的和[判断题]*对正确答案)错89.设图G是一个含有n个顶点的连通图，其中任意一条简单路径的长度不会超过[填空题]*_________________________________答案：n-1)90.设某无向图中有n个顶点e条边，则建立该图邻接矩阵的时间复杂度为：_________，建立该图邻接表的时间复杂度为：_________[填空题]*空1答案：O(n2)空2答案：O(n+e)91.设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是[填空题]*_________________________________答案：n-1)对正确答案)对正确答案)错101.任何一个含两个或以上顶点的带权无向图有？最小生成树[]*_________________________________答案：一颗或多颗)102.一个连通图的生成树是含有该连通图的全部顶点的[填空题]*_________________________________答案：极小连通子图)103.在用Prim和Kruskal算法构造最小生成树时，前者更适合于稠密图，后者更适合于稀疏图[判断题]*对正确答案)错104.Dijkstra算法的时间复杂度为[填空题]*_________________________________答案：O(n2))105.Dijkstra算法是按？的顺序方法求出图中从某顶点到其余顶点的最短路径[填空题]*_________________________________答案：长度递增)106.Dijkstra算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生，该算法在边上的权出现负值情况时不能正确产生最短路径。[]*对正确答案)错107.在有n个顶点的有向图中，每个顶点的度最大可达[填空题]*_________________________________答案：2(n-1))108.一个含有n个顶点的有向图仅有唯一的拓扑序列，则该图的边数为[填空题]*_________________________________答案：n-1)109.一个有n个顶点、e条边的连通图采用邻接表表示，从某个顶点v出发进行，则最大的递归深度是[填空题]*_________________________________答案：n)110.一个有n个顶点、e条边的连通图采用邻接表表示，从某个顶点v出发进行，则队列中最多的顶点个数是[填空题]*_________________________________答案：n-1)111.DFS时间复杂度为[填空题]*_________________________________答案：O(n2))112.拓扑排序的时间复杂度是[填空题]*_________________________________答案：O(n+e))113.如果图G存在拓扑排序序列，则G必为[填空题]*_________________________________答案：有向无环图)114.若含有n个顶点的无向图恰好形成一个环，则它有n棵生成树判断题]*对正确答案)错115.用邻接矩阵表示有n个顶点和e条边的无向图，矩阵中零元素的个数为：_________,采用压缩方式存储矩阵中零元素的个数为。：_________填空题]*空1答案：n*n-2e空2答案：n(n+1)/2-e116.对箱排序的改进和推广的算法是[填空题]*_________________________________答案：基数排序)对正确答案)对正确答案)空2答案：O(log2n)120.对正确答案)错123.二叉排序树的中序序列是一个递增有序序列[判断题]*对正确答案)错124.给定结点个数的平衡二叉树的高度不一定是唯一的[判断题]*对正确答案)错125.设计哈希表主要是设计哈希函数和哈希冲突解决方法[判断题]*对正确答案)错126.同义词是指两个不同关键字的元素，其哈希函数值相同，这种冲突称为同义词冲突[判断题]*对正确答案)错127.非同义词冲突是指哈希函数值不相同的两个元素争夺同一个后继哈希地址，导致出现堆积或聚集现象[判断题]*对正确答案)错128.在采用线性探测法处理冲突的哈希表中，所有同义词在表中不一定相邻[判断题]*对正确答案)错129.评价哈希函数好坏的标准是[填空题]*_________________________________答案：哈希函数的取值是否均匀)130.在哈希存储中，装填因子的值越大，则存取元素时发生冲突的可能性就越大。值越小，存取元素时发生冲突的可能性就越小[判断题]*对正确答案)错131.为了能有效地应用HASH查找技术，必须解决的两个问题是[]*_________________________________答案：构造一个好的HASH函数和确定解决冲突的方法)132.假设m个关键字互为同义词，若用线性探测法把这m个关键字存入散列表中，至少要进行的探查次数是[填空题]*_________________________________答案：m(m+1)/2)133.设二叉排序树中有n个结点，则在二叉排序树上查找或插入结点的平均时间复杂度为[填空题]*_________________________________答案：O(log2n))134.在最坏情况下，利用插入操作构造一颗二叉排序树花费的代价为[填空题]*_________________________________答案：O())135.当采用分块查找时，数据的组织方式为数据分成若干块，每块内数据无序，但块间必须有序，每块内最大或最小的数据组成索