数据结构习题1

数据结构习题一、单选题1.研究数据结构就是研究A)数据的逻辑结构B)数据的逻辑结构和存储结构C)数据的存储结构D)数据的逻辑结构、存储结构及其数据在运算上的实现2.下面关于算法的说法，错误的是。A)算法最终必须由计算机程序实现B)为解决某问题的算法与为该问题编写的程序含义是相同的C)算法的可行性是指指令不能有二义性D)以上几个都是错误的3.计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备5个特性输入、输出、。A)可执行性、可移植性和可扩充性B)可执行性、有穷性和确定性C)确定性、有穷性和稳定性D)易读性、稳定性和确定性4.以下属于逻辑结构的概念是。A)顺序表B)哈希表C)有序表D)单链表5.具有线性结构的数据结构是。A)图B)树C)广义表D)栈6.数据的存储结构包括顺序、链接、散列和种基本类型。A)向量B)数组C)集合D)索引7.根椐数据元素之间关系的不同特性，以下4类基本逻辑结构反映了4类基本数据组织形式。下列解释错误的是。A)集合中任何两个结点之间都有逻辑关系，但组织形式松散B)线性结构中结点按逻辑关系依次存储成一行C)树型结构具有分支、层次特性，其形态有点像自然界中的树D)图状结构中各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接8.在数据结构中，从逻辑上可以把数据结构分成。A)动态结构和静态结构B)紧凑结构和非紧凑结构C)线性结构和非线性结构D)内部结构和外部结构9.与数据元素本身的形式、内容、相对位置、个数无关的是数据的。A)存储结构B)存储实现C)逻辑结构D)运算实现10.以下说法错误的是。A)程序设计的实质是算法设计B)数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C)运算实现是完成运算功能的算法或这些算法的设计D)算法设计思想总是与数据的某种相应存储形式相联系11.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。A)单链表B)仅有头指针的单循环链表C)双链表D)仅有尾指针的单循环链表12.单链表的主要优点是。A)便于随机查询B)存储密度高C)逻辑上相邻的元素在物理上也是相邻的D)插入和删除比较方便13.线性表采用链式存储时，其地址。A)必须连续B)一定不连续C)部分连续D)连续与否均可14.对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该。A)以顺序方式存储B)以链接方式存储C)以散列方式存储D)以上均可15.若线性表中最常用的操作是取第i个的前趋元素，采用存储方式最节省时间。A)顺序表B)单链表C)双链表D)单循环链表16.若用单链表来表示队列，则应该选用。A)带尾指针的非循环链表B)带尾指针的循环链表C)带头指针的非循环链表D)带头指针的循环链表17.若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。从队列中出队一个元素，再进队两个元素后，rear和front的值分别为A)1和5B)2和4C)4和2D)5和118.设栈的输入序列是(1、2、3，4)，则不可能输出的序列。A)1243B)2134C)1432D)431219.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是。A)23415B)54132C)23145D)1543220.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是。A)6B)4C)3D)221.一般情况下，将递归算法转换成等价的非递增归算法应该设置。A)堆栈B)队列C)堆栈或队列D)数组22.设栈的输入序列是1、2、…、n，若输出序列的第一个元素是n，则第i个输出元素。A)不确定B)n-i+lC)cD)n-i23.假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是。A)front+1==rearB)front==rear+1C)front==OD)front==rear24.假定一个顺序循环队列存储于数组a[n]中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是。A)(rear-1)％n==frontB)rear==(front-1)％／nC)(rear+1)％n==frontD)rear==(front+1)％／n25.采用数据结构设计一个判别表达式中左、右括号是否配的算法最佳。A)线性表的顺序存储结构B)队列C)线性表的链式存储结构D)栈26.在下列算法描述中，涉及到队运算的算法是。A)表达式求值算法B)深度优先搜索C)二叉树前中后序遍历D)广度优先搜索27.当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为。A)N-2B)N-1C)ND)N+l28.链栈与顺序栈相比有一个明显的优点，即。A)插入操作更加方便B)通常不会出现栈满的情况C)不会出现栈空的情况D)删除操作更加方便29.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。A)所有的结点均无左孩子B)所有的结点均无右孩子C)只有一个叶子结点D)是任意一棵二叉树30.一棵完全二叉树上有1001个结点，其中叶子结点的个数是。A)250B)500C)505D)50131.以下说法正确的是。A)若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点B)若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点C)在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点D)在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点32.以下说法错误的是。A)哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近B)若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点C)己知二叉树的前序遍历和后序遍历并不能惟一地确定这棵树，因为不知道树的根结点是哪一个D)在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的33.二叉树在线索化后，仍不能有效求解的问题是。A)前序线索二叉树中求前序后继B)中序线索二叉树中求中序后继C)中序线索二叉树中求中序前趋D)后序线索二叉树中求后序后继34.若二叉树采用链式存储结构，要交换其所有分支结点左、右子树的位置，利用遍历方法最合适。A)前序B)中序C)后序D)层次35.一棵有124个叶结点的完全叉树，最多有个结点。A)247B)248C)249D)25036.设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是A)a在b的右方B)a在b的左方C)a是b的祖先D)a是b的子孙37.在一棵具有n个结点的完全二叉树中，分枝结点的最大编号为。A)((n+1)／2)下限取整B)((n-1)／2)下限取整C)(n／2)下限取整D)(n／2)上限取整38.在N个结点的线索二叉树中，线索的数目为。A)N-1B)NC)N+1D)2N39.设深度为K的二叉树上只有度为0和2的结点，则这类二叉树上所含的结点总数至少为。A)K+1B)2KC)2K-1D)2K+140.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。A)13B)12C)26D)2541.以下说法错误的是。A)存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B)二叉树是树的特殊情形C)由树转换成二叉树，其根结点的右子树总是空的D)在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树42.若二叉树是则从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序。A)二叉排序树B)哈夫曼树C)堆D)退化二叉树43.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组A[1．．n)中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数组A中的位置是。A)A[2i](2i≤nB)A[2i+1)(2i+1≤n)C)A[i/2]D)条件不充分，无法确定44.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是。A)4B)5C)6D)745.下列有关二叉树的说法正确的是。A)二叉树的度为2B)一棵二叉树度可以小于2C)二叉树中至少有一个结点的度为2D)二叉树中任一个结点的度都为246.某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是。，A)EGFACDBB)EACBDGFC)EAGCFBDD)上面的都不对47.对二叉排序树进行遍历，可以得到该二叉树所有结点构成的排序序列A)前序B)中序C)后序D)按层次48.的遍历仍需要栈的支持。A)前序线索树B)中序线索树C)后序线索树D)层次遍历49.在一棵深度为h的完全二叉树中，所含结点的个数不小于。A)2hB)2h+1C)2h-1D)2h-150.在一棵具有n个结点的二叉树第i层上，最多具有个结点。A)2iB)2i+1C)2i-1D)2n51.树最适合用来表示。A)有序数据元素B)无序数据元素C)元素之间具有分支层次关系的数据D)元素之间无联系的数据52.以下说法错误的是。A)一般在哈夫曼树中，权值越大的叶子离根结点越近B)哈大曼树中没有度数为1的分支结点C)若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n-1个结点D)若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下最终的哈夫曼树53.以下说法错误的是。A)二叉树可以是空集B)二叉树的任一结点都可以有两棵子树C)二叉树与树具有相同的树形结构D)二叉树中任一结点的两棵子树有次序之分54.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是的二叉树。A)空或只有一个结点B)任一结点无左子树C)高度等于其结点数D)任一结点无右子树55.设无向图的顶点个数为n，则该无向图最多有条边。A)n-1B)n(n-1)/2C)n(n+1)/2D)0E)n256.采用邻接表存储的图，其深度优先遍历类似于二叉树的。A)中序遍历B)先序遍历C)后序遍历D)按层次遍历57.采用邻接表存储的图，其广度优先遍历类似于二叉树的。A)按层次遍历B)中序遍历C)后序遍历D)先序遍历，58.一个图中包含有七个连通分量，若按深度优先(DFS)遍历,必须调用次深度优先遍历算法。A)kB)1C)k-1D)k+159.下列说法中不正确的是A)无向图中的极大连通子图称为连通分量B)连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C)图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D)有向图的遍历不可采用广度优先搜索方法60.具有n个顶点的有向图最多有条边。A)nB)n(n-1)C)n(n+1)D)n261.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是。A)G中有弧Vi，VjB)G中有一条从Vi到Vj的路径C)G中没有弧Vi，VjD)G中有一条从Vj到Vi的路径62.一个n个顶点的连通无向图，其边的个数至少为。A)n-1B)nC)n+lD)nlog2n63.下列说法中，正确的有。A)最小生成树也是哈夫曼树。B)最小生成树惟一C)普里姆(Prim)最小生成树算法时间复杂度为O(n2)D)克鲁斯卡尔(Kruskal)最小生成树算法比普里姆算法更适合于边稠密的网64.判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用。A)求关键路径的方法B)求最短路径的Dijkstra方法C)深度优先遍历算法D)广度优先遍历算法65.在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为。A)sB)s-1C)s+lD)n66.在一个无向图中，若两个顶点之间的路径长度为k条边，则该路径上的顶点数为。A)kB)k+lC)k+2D)2k67.一个有n个顶点的无向连通图，它所包含的连通分量个数为。A)0B)1C)nD)n+168.对于一