数据结构选择判断题库汇总最后版本(无填充色)20130704--version-1-

章节题干答案难度1顺序存储方式只能用于存储线性结构。N中1数据元素是数据的最小单位。N低1数据的逻辑结构是指数据的各数据项之间的逻辑关系。N低1记录是数据处理的最小单位。N中1算法的优劣与算法描述语言无关，但与所用计算机有关。N高1健壮的算法不会因非法的输入数据而出现莫名其妙的状态。Y中1数据结构的抽象操作的定义与具体实现有关。N中1在顺序存储结构中，有时也存储数据结构中元素之间的关系。Y高1顺序存储方式的优点是存储密度大，且插入、删除运算效率高。N中1数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。Y高1数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。N中1数据的物理结构是指数据在计算机内的实际存储形式。Y中1程序一定是算法。N高1算法的时间复杂度是问题规模的函数。Y低1数据的物理结构包括数据的表示和元素关系的表示。Y中1数据结构中评价算法的两个重要指标是时间复杂度和运行效率。N低1对于给定的n个元素，可以构造出的逻辑结构有集合、线性结构、图状结构和网状结构四种。N低1抽象数据类型的定义仅取决于它的一组逻辑操作，而与其在计算机内部如何表示和实现无关。Y中1算法的时间复杂度是算法执行时间的绝对度量。N中1数据结构是带有结构的数据元素的集合。Y中1算法的正确性是指算法不存在错误。N高1顺序存储结构的主要缺点是不利于插入或删除操作。Y低1算法的效率与存储空间需求均与问题的规模有关。Y低1算法分析的目的是分析算法的效率以求改进。Y低1算法的时间复杂度都是以算法中执行频度最高的语句的执行次数来确定。N高2在链表中，头结点就是开始结点。N中2顺序查找法适用于存储结构为顺序或链接存储的线性表。Y低2一个循环链表可以由所给定的头指针或者尾指针唯一地确定。Y低2线性表的逻辑顺序与物理顺序总是一致的。N中2线性表的顺序存储表示优于链式存储表示。N中2线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。Y中2顺序存储的线性表可以按序号随机存取。Y低2顺序表的插入和删除一个数据元素，每次操作平均有近一半的元素需要移动。Y低2线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。Y中2在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。N中2在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。Y低2线性表的链式存储结构优于顺序存储结构。N中2在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。Y中2线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素。Y低2在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。N中2在单链表P指针所指结点之后插入S结点的操作是：P-next=S;S-next=P-next;N中2在以HL为表头指针的带附加结点的单链表和循环单链表中，链表为空的条件分别为HL-next==NULL和HL==HL-next。Y高2链表中的头结点仅起到标识的作用。N低2线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。N低2顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。N低2对任何数据结构链式存储结构一定优于顺序存储结构。N低2集合与线性表的区别在于是否按关键字排序。N低2所谓静态链表就是一直不发生变化的链表。N低2线性表的特点是每个元素都有一个前驱和一个后继。N低2取线性表的第i个元素的时间同i的大小有关.N低2循环链表不是线性表.N低2线性表只能用顺序存储结构实现。N低2线性表就是顺序存储的表。N低2为了很方便的插入和删除数据，可以使用双向链表存放数据。Y低2链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。Y低2链表的每个结点中都恰好包含一个指针。N低2链表的物理存储结构具有同链表一样的顺序。N低2链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动将后续各个单元向前移动。N低2线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。N低2顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。N低2线性表在物理存储空间中也一定是连续的。N低2线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。N低2线性表的逻辑顺序与存储顺序总是一致的。N低2有序表就是顺序表，顺序表就是有序表。N低3栈和队列都是限制存取点的线性结构。Y易3Datacanbeinsertedanddeletedatanywhereinstracksandqueues.N易3PUSH和POP命令常用于栈操作Y易3Thepostfixexpressionis‘abcdef*/-*+’.Itsinfixexpressionisa+b*[c-d/(e*f)]Y中3Thestacktakesoncharacteroffirstinfirstout.N中3不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。Y中3不同的入栈和出栈组合可能得到相同的输出序列。N中3从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行HS=HS-next操作。Y中3带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点。Y中3队列和栈都是运算受限的线性表，只允许在表的两端进行运算。N中3队列逻辑上是一个两端既能增加又能减少的线性表。N中3队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。N易3队列只能在队头插入和删除元素。N易3对一个顺序栈，当栈为非空时，栈顶指针top始终指向栈顶元素的下一位置。Y中3即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。N易3任何一个递归过程都可以转换成非递归过程。Y中3若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。N难3若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.Y难3通常使用队列来处理函数或过程的调用。N中3循环队列通常用指针来实现队列的头尾相接。N中3循环队列也存在空间溢出问题。Y中3循环队列只能用数组实现，而不能用链表实现。N中3用下标0开始的N元数组实现循环队列时，为实现下标变量m加1后在数组有效下标范围内循环，可采用的表达式是（m+1）%N。Y难3在对不带头结点的链队列作出队操作时，不会改变头指针的值。N中3栈的顺序存储结构即顺序栈，是利用一组地址连续的存储单元来依次存放自栈底至栈顶的数据元素。Y易3栈的特点是先进先出。N易3栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。Y中3栈和队列都是线性表，只是在插入和删除时受到了一些限制。Y中3栈和队列是两种重要的线性结构。Y易3栈与队列是一种特殊操作的线性表。Y易3栈只能在栈中某一位置插入和删除元素。N中4KMP算法的最大特点是指示主串的指针不需要回溯。Y中4串的存储只能用定长顺序存储。N中4串的堆分配存储中，是以一组连续的存储单元存放串字符序列，存储空间动态分配而得。Y易4串的块链存储结构中，每个结点必须存储80个字符。N中4串的块链存储结构中，每个结点只能存储一个字符。N中4串的长度不能为零。N中4串是一种数据对象和操作都特殊的线性表。Y中4串是一种特殊的线性表，其特殊性体现在可以顺序存储。N易4串是一种特殊的线性表。Y易4串中的元素只能是字符。Y中4串中可以包含有空白字符。Y中4二维数组和多维数组均不是特殊的线性结构。N易4空串和空白串是相同的。N易4空格串不是空串。（）Y易4空格串的长度为1。N易4两个串相等必有串的长度相等。Y中4两个串相等就是串的长度相等。N中4两个串相等就是两个串包含的字符相同。N中4两个串相等则各位置上字符必须对应相等。Y中4设有串t='Iamastudent',s='good',那么Concat(t,s)='Iamastudentgood'。Y难4数组元素的下标值越大，存取时间越长。N易4稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。Y易4一个广义表的表头总是一个广义表。N中4一个广义表的表尾总是一个广义表。Y中4长度为1的串等价于一个字符型常量。N中4子串“ABC”在主串“AABCABCD”中的位置为2。Y中4子串是主串中字符构成的有限序列。Y中5二叉树中每个结点都必须有两个孩子结点，而对一般的树则无此限制。N易5二叉树就是结点度为2的树。N易5二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。N易5当k≥1时，高度为k的二叉树至多有2(K-1)个结点。N易5完全二叉树的某结点若无左孩子，则它必是叶结点。Y中5用一维数组存放二叉树时，总是以前序遍历顺序存储结点。N中5若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。N中5存在这样的二叉树，对它采用任何次序的遍历，结果相同。Y中5中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。Y中5将一棵树转换成二叉树后，根结点没有左子树。N易5由树转换成二叉树，其根结点的右子树总是空的。Y中5在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。N易5在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。N中5霍夫曼树一定是满二叉树。N易5树的度是树内各结点的度之和。N易5由二叉树的结点构成的集合可以是空集合。Y易5一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。N易5具有n个结点的二叉树，采用二叉链表存储，共有n+1个空链域。Y中5对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中指针域总数为2n+1个。N难5对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中指针域总数为2n个，其中n-1个用于链接孩子结点。Y难5对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中指针域总数为2n个，其中共有n+1个空闲着。Y难5一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶子结点个数为(n(k-1)+1)/k。Y难5从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。Y中5对于一个具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度。Y易5对于一个具有n个结点的二叉树，当它为一棵单支树时具有最大高度，即为n。Y易5设只包含根结点的二叉树高度为0，则高度为k的二叉树最大结点数为2k+1。N中5设只包含根结点的二叉树高度为0，则高度为k的二叉树最小结点数为k+1。Y中58层完全二叉树至少有128个结点。Y易5拥有100个结点的完全二叉树的最大层数为7。Y易5二叉树通常有顺序存储结构和链式存储结构。Y易5二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。Y易5线索二叉树的左线索指向其某种遍历序列的直接前驱结点，右线索指向其某种遍历序列的直接后继结点。Y中5用树的孩子兄弟表示法存储，可以将一棵树转换成一棵二叉树。Y中5遍历一棵二叉树包括访问根结点、遍历左子树和遍历右子树三个方面。Y易5已知树的广义表形式为A{B[E，F]，C，D[G（H，I）]}，则该树的度为3。Y中5已知树的广义表形式为A{B[E，F]，C，D[G（H，I）]}，从根开始的前序遍历所得序列为ABEFCDGHI。Y中5森林定义为m(m=0) 棵互不相交的树的集合。Y中6在n个结点的无向图中，若边数n-1，则该图必是连通图。N中6邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。N中6图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。Y中6有回路的图不能进行拓扑排序。Y易6任何AOV网拓扑排序的结果