搜索
数据结构一、【单项选择题】1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用（）存储方式最节省时间。[C]带头结点的双循环链表2、队列操作的原则是（）。[D]先进先出3、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。[B]高度等于其结点数4、在下列排序方法中，（）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)。[C]快速排序5、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左、右孩子中，其左孩子编号小于右孩子编号。则可采用（）次序的遍历实现编号。[C]后序6、若线性表中采用二分查找法查找元素，该线性表应该（）。[C]元素按值有序，且采用顺序存储结构7、对待排序数据的初始状态不作任何要求的排序方法有（）。[A]插入和快速排序8、已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最节省时间。[B]插入排序9、以下哪一个不是队列的基本运算？（）[B]从队列中删除第i个元素10、广度优先遍历类似于二叉树的（）。[D]层次遍历1．程序段：sum=0;for(i=1;in*n;i++)Sum++;的平均情况下时间代价的表达式是（）。[C](n2)2．数据结构通常是研究数据的（）及它们之间的联系。[A]存储和逻辑结构3．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（）。[A]984．在有n个叶结点的Huffman树中,其结点总数为（）。[A]2n-15．设有100个元素，用折半查找法进行查找时，最大比较次数是（）。[D]76．快速排序在（）情况下最易发挥其长处。[C]被排序数据完全无序7．由两个栈共享一个向量空间的好处是（）。[B]节省存储空间,降低上溢发生的机率8．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。[C]用尾指针表示的循环单链表9．图的深度优先遍历类似于二叉树的（）。[A]先序遍历10．设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（）。[C]O(n)1、在一个图中，所有顶点的度数之和等于图的边数的（）倍。[C]22、采用顺序查找方法查找长度为n的线性表，平均查找长度为（）。[C](n+1)/23、线性链表不具有的特点是（）。[A]随机访问[A](1)[B](n)[C](n2)[D](nlogn)4、删除长度为n的非空顺序表的第i个数据元素之前需要移动表中（）个数据元素。[A]n-i5、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。[A]不发生改变6、若用数组S[n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S[n]全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。[C]S1的栈底位置为0，S2的栈底位置为n－17、对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。[C]中序8、在下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。[D]插入排序9、采用邻接表存储的图的广度优先算法类似于二叉树的（）。[D]层次遍历10、具有6个顶点的无向图至少应有（）条边才能保证图的连通性。[B]51、数据结构在计算机内存中的表示是指（）。[A]数据的存储结构2、若不带头结点的单循环链表的头指针为head，则该链表只有一个结点的判定条件是（）。[D]head-next==head3、设listarray[size]为一个顺序存储的栈,变量top指示栈中第一个空闲位置,栈为空的条件是（）。[B]top=04、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。[A]n–i+15、在数据结构中，与所使用的计算机无关的是数据的（）结构。[A]逻辑6、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。[C]dceab7、若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（）。[C]88、由同一关键字集合构造的各棵二叉排序树（）。[B]其形态不一定相同，平均查找长度也不一定相同。9、具有n个顶点的无向连通图最少有（）条边。[C]n-110、若某文件经内部排序得到100个初始归并段，若使用K路归并三趟完成，则（）。[C]K=41．算法分析的目的是（）。[C]分析算法的效率以求改进2．散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（）方法是散列文件的关键。[D]散列函数和冲突处理3．在需要经常查找结点的前驱与后继的场合中，使用（）比较合适。[B]双链表4．下面关于线性表的叙述中，错误的为（）。[D]在链表中，每个结点只有一个链域5．一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（）。[C]36．若需要利用形参直接访问实参，则应把形参变量说明为（）参数。[B]引用7．已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（）。[C]O(n)8．在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于（）。[D]2h9．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。[D]front==NULL10．在一棵树中，（）没有前驱结点。[C]树根结点二、【判断题】11、线性表的逻辑顺序与物理顺序总是一致的。F12、在链式存储的栈的头部必须要设头结点。F13、在二叉树中插入结点，则该项二叉树便不再是二叉树。F14、由二叉树结点的先序序列和后序序列可以唯一确定一棵二叉树。F15、栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F16、有向图的邻接矩阵一定不是对称的。F17、在AOE网中，关键路径是唯一的。F18、若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。T19、索引顺序存取方法ISAM是一种专门为磁盘存取设计的索引顺序文件的组织方法T20、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形。F11．树的父链表示就是用数组表示树的存储结构。T12．栈和队列逻辑上都是线性表。T13．单链表从任何一个结点出发，都能访问到所有结点。F14．AOE网中，只有一个入度为0的顶点（起始点），只有一个出度为0的顶点（结束点）。T15．关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。F16．删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。F17．一般树和二叉树的结点数目都可以为0。T18．堆栈在数据中的存储原则是先进先出。F19．线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。T20．非空线性表中任意一个数据元素都有且仅有一个直接后继元素。F11、线性表的顺序存储表示优于链式存储表示。F12、在外部分类中使用K路平衡归并，采用选择树法时,归并效率与K有关。F13、对于n个记录的集合进行归并分类，最坏情况下所需要时间为O(n)。F14、倒排文件与多重表文件的次关键字索引结构不同。T15、将一棵树转换成二叉树后，根结点没有左子树。F16、用树的前序遍历序列和中序遍历序列可以导出树的后序遍历序列。T17、即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得到的序列也一定相同。18、哈夫曼(Huffman)树是带权路径长度最短的树。路径上权值较大的结点离根较近。T19、对于任一个图，从某顶点出发进行一次深度或广度优先搜索，可以访问图中每一个顶点。F20、带权的无向连通图的最小生成树是唯一的。F11、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。T12、任何二叉树都唯一对应一个森林，反之亦然。T13、有向图的邻接矩阵一定是对称的。F14、线性表的链式存储结构优于顺序存储结构。F15、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。F16、顺序存储方式只能用于存储线性结构。F17、用循环链表作为存储结构的队列就是循环队列。F18、倒排文件的主要优点为便于节省空间。F19、一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84。F20、算法分析的目的是分析算法的易读性。F11.线性表中的每个结点最多只有一个前驱和一个后继。F12.每种数据结构都应具备三种基本运算：插入、删除和搜索。F13.在单链表P指针所指结点之后插入S结点的操作是：P-next=S;S-next=P-next。F14.假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。T15.对于任何待排序序列来说，快速排序均快于起泡排序。F16.直接选择排序是一种不稳定的排序方法。T17.顺序表用一维数组作为存储结构，因此顺序表是一维数组。F18.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。T19.闭散列法通常比开散列法时间效率更高。F20.一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。F三、【填空题】21、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（O(n2)）。22、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（n）。23、设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是（p-lchild==NULL&&p-rchild==NULL；）。24、设一棵二叉树的前序序列为ABC，则有（5）种不同的二叉树可以得到这种序列。25、为了给n个字母编码而建立起来的Huffman树一共有（2n－1）个结点。26、n个顶点的连通图用相邻矩阵表示时，该矩阵至少有（n－1）个非零元素。27、对于一个具有n个顶点和e条边的无向图，在其对应的邻接表中，所含边结点有（2e）个。28、冒泡排序在最好情况下的元素交换次数为（0）。29、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的外部路径权重为（71）。30、栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是（后进先出）。21．《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和（运算）。22．若要在单链表结点*P后插入一结点*S，执行的语句（s-next=p-next;p-next=s）。23．折半搜索只适合用于（有序表）。24．栈结构允许进行删除操作的一端为（栈顶）。25．设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为（1130）。26．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为（69）。27．一棵具有５层满二叉树中节点总数为（31）。28．从树中一个结点到另一个结点之间的分支构成这两个结点之间的（路径）。29．在无向图中，若从顶点A到顶点B存在（路径），则称A与B之间是连通的。30．若图的邻接矩阵是对称矩阵，则该图一定是（无向图）。21、如果n个顶点的图是一个环，则它有（n）棵生成树。22、设在等概率情形下,对有n个元素的顺序表进行插入（插入位置i取0到n范围内的整数）,平均需要移动（n/2）个元素。23、具有96个结点的完全二叉树的高度为（7）。24、如果一棵树有n1个度为1的结点,有n2个度为2的结点,…,nm个度为m的结点,则度为0的结点有（n2+2n3+…..+(m-1)nm+1）个。25、若二叉树的中序序列与后序序列相同，则该二叉树是空树或（只有根节点的二叉树）。26、若一棵完全二叉树有500个结点，则该二叉树的深度为（9）。27、用邻接矩阵表示无向图时，若图中有1000个顶点，1000条边，