02142《数据结构导论》复习题.

数据结构导论摹拟试题

一、考试题型及分值分布、单项选择题本大题共小题，每小题分，共分、填空题本大题共小题，每小题分，共分、应用题本大题共小题，每小题分，共分、算法设计题本大题共小题，每小题分，共分

二、单项选择题和填空题样题参考

（一）单项选择题在二维数组中，每一个数组元素同时处于（）个向量中已知单链表长度为，单链表长度为，整体连它们分别由表头指针所指向，若将假定一个链式队列的队头和队尾指针分别为和，则判断队空的条件为接到的末尾，其时间复杂度应为（）o若让元素挨次进栈，则出栈次序不可能浮现种情况图的广度优先搜索类似于树的（）遍历先根中根后根层次下面程序段的时间复杂度为设有两个串和，求在中首次浮现的位置的运算叫做（）o求子串模式匹配串替换串联接便于单向进行插入和删除的操作节便于双向进行插入和删除的操作省空间便于销毁结构释放空间设链式栈中结点的结构为（）,且是指向栈顶的指针若想在链式栈的栈顶插入一个由指针所指的结点，则应执行操作利用双向链表作线性表的存储结构的优点是（）o一棵具有个结点的彻底二叉树的高度为假定空树的高度为O一个有个顶点和条边的无向图一定是的.连通.不连通.无回路.有回路在一个长度为的顺序表的任一位置插入一个新元素的时间复杂度为（）已知广义表为,从中取出原子的运算是（）o在一棵树的静态双亲表示中，每一个存储结点包含个域有向图中的一个顶点的度数等于该顶点的・入度•出度.入度与出度之和.入度出度2与邻接矩阵相比，邻接表更适合于存储・无向图.连通图・稀疏图.稠密图较快的数据搜索方法是（）搜索方法顺序折半单链散列在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（）引起的同义词之间发生冲突非同义词之间发生冲突同义词之偶尔非同义词之间发生冲突散列表“溢出”根据个元素建立一个有序单链表的时间复杂度为（）o假定一个顺序存储的循环队列的队头和队尾指针分别为和，则判断队空的条件为假定一棵二叉树的第层上有个结点，则第层上最多有个结点对于具有条边的无向图，它的邻接表中共有个边结点••••图的深度优先搜索遍历类似于树的（）次序遍历先根中根后根层次.栈最多能容纳个元素现有个元素按的顺序进栈问下列哪一个序列是可能的出栈序列.将一棵有个结点的彻底二叉树从根这一层开始，每一层从左到右挨次对结点进行编号，根结点编号为，则编号为的结点的左孩子的编号为对下列关键字序列用快速排序法进行排序时，速度最快的情形是.对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为顺序表用头指针表示的单循环链表用尾指针表示的单循环链表单链表.假设以第一个元素为分界元素，对字符序列（）进行快速排序，则第一次划分的结果是.下面是三个关于有向图运算的叙述:（）求有向图结点的拓扑序列，其结果必然是惟一的（）求两个指向结点间的最短路径，其结果必然是惟一的（）求网的关键路径，其结果必然是惟一的其中哪个（些）是正确的？惟独（）（）和（）都正确都不正确.若进栈序列为，则通过入出栈操作可能得到的的不同罗列个数为以下关于广义表的叙述中正确的是广义表是由个或者多个单元素或者子表构成的有限序列广义表至少有一个元素是子表广义表不能递归定义广义表不能为空表这是哪种排序方法的基本思想？快速排序冒泡排序堆排序直接插入排序・已知一个有向图的邻接矩阵表示，要删除所有从第个结点发出的边，应该:将邻接矩阵的第行删除将邻接矩阵的第行元素全部置为将邻接矩阵的第列删除将邻接矩阵的第列元素全部置为.有一个含头结点的双向循环链表,头指针为则其为空的条件是排序时扫描待排序记录序列，按次比较相邻的两个元素的大小，逆序时就交换位置在顺序表中，用折半法查找关键码值，所需的关键码比较次数为以下哪一个不是队列的基本运算？从队尾插入一个新元素从队列中删除第个元素判断一个队列是否为空读取队头元素的值.对包含个元素的哈希表进行查找，平均查找长度为不直接依赖于.将一棵有个结点的彻底二叉树从根这一层开始，每一层从左到右挨次对结点进行编号，根结点编号为，则编号最大的非叶结点的编号为.某二叉树结点的中序序列为、、、、、、，后序序列为、、、、、、,则其左子树中结点数目为・下面是顺序存储结构的优点存储密度大插入运算方便查找方便适合各种逻辑结构的存储表示.下面关于串的叙述中，是不正确的串是字符的有限序列空串是由空格构成的串模式匹配是串的一种重要运算串既可以采用顺序存储，也可以采用链式存储.的邻接矩阵是对称矩阵有向图无向图网网.用链式方式存储的队列，在进行删除运算时，O仅修改头指针仅修改尾指针头、尾指针都要修改头、尾指针可能都要修改.二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是O先序序列中序序列・下面方法可以判断出一个有向图中是否有环深度优先遍历拓朴排序求最短路径求关键路径.从未排序序列中挨次取出一个元素与已排序序列中的元素挨次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为________________排序法插入选择冒泡都不是.一个栈的入栈序列是，则栈的不可能的输出序列是O・个节点的彻底二叉树，编号为的节点是叶子结点的条件是O.向一个有个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要挪移个元素,在一个单链表中，若要在指针所指结点的后面插入一个由指针所指向的结点，则执行.对一个满二叉树，个树叶，个结点，深度为，则有O.在所有排序方法中，关键字比较的次数与记录的初始罗列次序无关的是O选择排序冒泡排序插入排序希尔排序・用链式方式存储的队列，在进行插入运算时，O仅修改头指针仅修改尾指针头、尾指针都要修改头、尾指针可能都要修改.在一个长度为的顺序存储的线性表中，向第个元素（W W）插入一个新元素时，需要从后向前挨次后移个元素.一个栈的入栈序列是，则栈的不可能的输出序列是O・个顶点的有向图最多有条弧.假定一个链队的队首和队尾指针分别为和，则判断队空的条件为O.若某线性表中最常用的操作是提取第个元素及找第个元素的前驱元素，则采用（）存储方式最省时间单链表双链表单向循环链表顺序表.将含有个结点的彻底二叉树从根开始自上向下，每层从左到右挨次编号，且设根结点的编号为，则编号的结点的双亲的编号为（）o无法确定单循环链表的主要优点是（）o再也不需要头指针了已知某结点的位置后，很容易找到其前驱在进行插入、删除运算时，能更好地保证链表不断开从表中任一结点出发都能扫描到整个链表一个栈的入栈顺序是、、、、，则此栈不可能的输出顺序为（）o串是一种特殊的线性表，其特殊性表现在（）o可以顺序存储数据元素是一个字符可以链式存储数据元素是多个字符个顶点的无向图中最多有（）条边个顶点的无向图中，至少有（）条边才干保证是一个连通图.若某线性表中最常用的操作是删除第个元素，则不宜采用（）存储方式单链表双链表单向循环链表顺序表.在一棵彻底二叉树的顺序存储方式中，若编号的结点有右孩子，则其右孩子的编号为（）o按照二叉树的定义，具有个结点的二叉树有（）种不同形态在长为的顺序表中，删除第个元素w W需要向前挪移（）个元素一个队的入队顺序是、、、、，则此队的出队顺序为（）栈是一种特殊的线性表，其特殊性表现在（）可以顺序存储只能从端点进行插入和删除可以链式存储可以在任何位置进行插入和删除一棵二叉树中，第层上最多有（）个结点一棵有个结点的二叉树，其高度最小为（）层有向图中，所有顶点入度和是所有顶点出度和的（）倍（-）填空题数据元素之间存在的相互关系称为O数据结构从逻辑上分为结构和结构线性表的顺序存储结构称为O所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为深度为的二叉树至少有个结点折半查找要求待查表为表个记录按其关键字大小递增或者递减的次序罗列起来的过程称为存储数据时不仅要存储数据元素的还要存储元素之间的相互..将一棵有个结点的彻底二叉树按层编号，则编号为的结点，其双亲（）的编号为O、一个字符串相等的充要条件是和O、在有向图的邻接表和逆邻接表表示中，每一个顶点的边链表中分别链接着该顶点的所右和结点、在一个长度为的顺序表中向第个元素（W）之前插入一个新元素时，需要向后挪移个元素、是只允许在表的一端进行插入，而在另一端进行删除的线性表、设主串=”模式串=”则第次匹配成功、在一棵二叉树中，第层上的结点数最多为___________（根的层次为）O、假设一个阶的上三角矩阵按列优先顺序压缩存储在一维数组中，其中［］存储矩阵中第个元素,则中存放的元素是O、有个结点的二叉链表中，其中空的指针域为，指向孩子的指针个数为O、二叉树后序遍历的顺序是，则该二叉树的根结点是O、对于一个具有个顶点和条边的无向图，若采用邻接表表示，则整个邻接表中的结点总数是.O、在单链表上难以实现的排序方法有和O.查找法的平均查找长度与元素个数无关、在有个元素的顺序表的任意位置插入一个元素所需挪移结点的平均次数为、是插入和删除元素都在表的同一端进行的线性表、广义表=（）则其长度为O、在树中，除跟结点外，其他结点都有且惟独一个结点、在串“”中，以为首字符的子串有个、广度优先搜索遍历类似于树的按________遍历的过程、已知一棵彻底二叉树中共有个结点为，则该树中共有个叶子结点、在有序表（）中二分查找关键字时所需进行的关键字比较次数^、两个长度分别和（）的排好序的表归并成一个排好序的表，至少要进行次键值比较通常从四个方面评价算法的质量、、和、一个算法的时间复杂度为，其数量级表示为、若用链表存储一棵二叉树时，每一个结点除数据域外，还有指向左孩子和右孩子的两个指针在这种存储结构中，个结点的二叉树共有个指针域，其中有个指针域是存放了地址，有个指针是空指针、对于一个具有个顶点和条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有个和个、在一个具有个顶点的无向彻底图中，包含有条边，在一个具有个顶点的有向彻底图中，包含有条边、在快速排序、堆排序、归并排序中，排序是稳定的

35、.中序遍历二叉排序树所得到的序列是序列3637快速排序的最坏时间复杂度为，平均时间复杂度为设一组初始记录关键字序列为，，，，，，，，则利用筛选法建立的初始堆为.数据的物理结构主要包括和两种情况设一棵彻底二叉树中有个结点，则该二叉树的深度为；若用二叉链表作为该彻底二叉树的存储结构，则共有个空指针域、设输入序列为、、，则经过栈的作用后可以得到种不同的输出序列、设有向图用邻接矩阵作为存储结构，则该邻接矩阵中第行上所有元素之和等于顶点的，第列上所有元素之和等于顶点的设哈夫曼树中共有个结点，则该哈夫曼树中有个度数为的结点设有向图中有个顶点条有向边，所有的顶点入度数之和为，则和的关系为遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或者后序）设查找表中有个元素，如果用二分法查找方法查找数据元素，则最多需要比较次就可以断定数据元素是否在查找表中不管是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为设有个结点的彻底二叉树，如果按照从自上到下、从左到右从开始顺序编号，则第个结点的双亲结点编号为，右孩子结点的编号为设一组初始记录关键字为，，，，，，，则以记录关键字为基准的一趟快速排序结果为设有向图中有向边的集合，，，，，，，，，，则该图的一种拓扑序列为下列算法实现在顺序散列表中查找值为的关键字，请在下划线处填上正确的语句下列算法实现在二叉排序树上查找关键值，请在下划线处填上正确的语句设有个无序的记录关键字，则直接插入排序的时间复杂度为，快速排序的平均时间复杂度为设指针变量指向双向循环链表中的结点，则删除结点需要执行的语句序列为分别为和根据初始关键字序列,,,,建立的二叉排序树的）O高度为深度为的彻底二叉树中至少有个结点设初始记录关键字序列为，，…，素开始,则用筛选法思想建堆必须从第个元进行筛选、设哈夫曼树中共有个结点，则该树中有存个叶子结点；若采用二叉链表作为储结构，则该树中有个空指针域、设有一个顺序循环队列中有个存储单元，则该循环队列中最多能够存储个队（设结点中的两个指针域列元素；当前实际存储个队列元素（设头指针指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）、设顺序线性表中有个数据元素，则第个位置上插入一个数据元素需要挪移表中个数据元素；删除第个位置上的数据元素需要挪移表中个元素、设一组初始记录关键字序列为，，，，，，则以为中轴的一趟快速排序结果为、设一组初始记录关键字序列为，，，，，，则根据这些初始关键字序列建成的初始堆为、设无向图对应的邻接矩阵为，则中第上非元素的个数第列上非元素的个数（填等于，大于或者小于）、设前序遍历某二叉树的序列为，中序遍历该二叉树的序列为，则后序遍历该二叉树的序列为、设散列函数，解决冲突的方法为链地址法要求在下列算法划线处填上正确的语句完成在散列表中查找关键字值等于的结点，成功时返回指向关键字的指针，不成功时返回标志

三、应用题主要考点、二叉树的遍历与恢复（即已知二叉树对其遍历、已知遍历序列恢复二叉树）、哈夫曼树的构造、图的存储结构（邻接矩阵、邻接表）、图的应用（最小生成树、拓扑排序）、各种查找方法（二叉排序树、散列表、平均查找长度）、各种排序方法

四、算法设计题主要考点、线性表的简单算法顺序表和单链表的基本运算、二叉树的简单应用算法如二叉树的遍历、求二叉树的高度、二叉树中叶子节点数等、查找算法（顺序查找、二分查找）、排序算法（如插入、交换、选择排序等）。