数据结构期末考试题总

《数据结构期末考试题总》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、判断题1、栈是限定仅在表尾进行插入和删除操作的线性表。（√）2、引入循环队列的目的是为了克服假溢出时大量移动数据元素。(√)3、区分循环队列的满与空，有牺牲一个存储单元和设标记两种方法。（√）4、若一个栈的输入序列为1，2，3，则3，1，2是不可能的栈输出序列。（√）5、表达式求值是队列应用的一个典型例子。（×）6、任何一个递归过程都可以转换成非递归过程。（　√　）7、循环队列也存在空间溢出问题。（√）8、栈和队列都是线性表，只是在插入和删除时受到了一些限制。（√）9、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（√）10、串是一种数据对象和操作

2、都特殊的线性表。（√）11、对称矩阵压缩存储后不会失去随机存取功能。（√）12、数组可看成线性结构的一种推广，可以对它进行插入，删除等操作。（×）13、一个稀疏矩阵Am×n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则完成了Am×n的转置运算。（×）14、二维以上的数组其实是一种特殊的广义表。（√）15、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（×）16、若一个广义表的表头为空表，则此广义表亦为空表。（×）17、广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。(×）18、所谓取广义表的表

3、尾就是返回广义表中最后一个元素。（×）19、广义表的同级元素具有线性关系。（√）20、一个广义表可以为其它广义表所共享。（√）21、压缩存储的三角矩阵和对称矩阵的存储空间相同。()解答：压缩存储的三角矩阵比压缩存储的对称矩阵多一个存储空间，用来存储常量c。答案：×22、广义表中的数据元素类型可以不相同。()解答：广义表的不同元素可以有不同的结构，即数据元素类型可以不相同。答案：√23、广义表的元素不可以是广义表。()解答：广义表的元素可以是子表，子表的元素还可以是子表，即广义表是一个多层次的结构。答案：×24、两个稀疏矩阵的和仍为稀疏矩阵。()解答：两个稀疏矩

4、阵的和不一定是稀疏矩阵。例如，当两个稀疏矩阵和的非0元个数等于这两个稀疏矩阵非0元个数之和时，这两个矩阵的和不一定是稀疏矩阵。答案：×25、数组用顺序存储方式存储时，存取每个元素的时间相同。()解答：数组用顺序存储方式存储时，只要知道起始结点的存放地址(即基地址)、维数和每维的上、下界，以及每个数组元素所占用的字节数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。答案：√26、队列这种结构是不允许在中间插入和删除数据的。（）解答：队列也是一种特殊的线性表，它只允许在一端进行插

5、入操作，在另一端进行删除操作，不允许在中间插入和删除数据。答案：√4027、循环队列只能用顺序表实现。（）解答：使用循环队列的目的是解决顺序队列的假溢出现象，所以循环队列只能用顺序表实现。答案：√28、顺序栈的“栈满”与“上溢”是没区别的，“栈空”与“下溢”是有区别的。（）解答：栈满时若有元素入栈，将产生上溢。栈空时若进行出栈操作，将产生下溢。由此可知，“栈满”与“上溢”有区别的，“栈空”与“下溢”也有区别。答案：×29、顺序队列的“假溢出”现象是可以解决的。（）解答：顺序队列的“假溢出”现象可以利用循环队列或通过移动元素的方式解决。答案：√30、空串与空格串

6、是一样的。（）解答：空串中没有字符，其长度为0；空格串中含有空格字符，其长度为空格的个数。答案：×31、单链表中指针p所指向结点存在后继结点的条件是p!=NULL.。×32、双循环链表从任何结点出发可以访问该结点的直接前驱和直接后继。√33、队列是特殊的线性表，在队列的两端可以进行同样的操作。×34、双向循环链表从任意结点出发可以访问链表中的任意结点。√35、头指针一定要指向头结点。（）解答：若链表有头结点，则头指针指向头结点；若链表没有头结点，则头指针指向第一个结点（链表不空），或指向空（链表为空）。答案：×36、链表中结点数据域占的存储空间越多，存储密度越

7、大。√37、栈是线性表，线性表的所有操作均适用于栈。×38、一个三维数组可以看作为是数组元素为二维数组的线性表。√密39、广义表中的数据元素类型可以不相同。√40、串是一种数据对象和操作都特殊的线性表。√41、两个稀疏矩阵的和仍为稀疏矩阵。×42、串中任意个字符组成的子序列称为该串的子串。×密43、压缩存储的三角矩阵和对称矩阵的存储空间相同。×44、如果两个串含有相同的字符，则这两个串相等。×密45、数组不适合作为任何二叉树的存储结构。×46、在前序遍历二叉树的序列中，任何结点的子树的所有结点都直接跟在该结点之后。√47、若一个树叶是某子树的中序遍历序列中的最

8、后一个结点，则它必是该子树的前序遍历序