数据结构期末复习题.pdf

数据结构期末复习题、选择题1.以下说法中不正确的是（D）。A.数据元素是数据的基本单位B.数据项是不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成2.计算机所处理的数据一般具备某种在联系，这是指（B）。A.数据和数据之间存在某种关系B.元素和元素之间存在某种关系C.元素部具有某种结构D.数据项和数据项之间存在某种关系3.在数据结构中，与所使用的计算机无关的是数据的（A）结构A.逻辑B.存储C.逻辑和存储D.物理4.数据的逻辑结构可以分为（C）两类。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.部结构和外部结构5.数据的逻辑结构是指（A）关系的整体。A.数据元素之间逻辑B.数据项之间逻辑C.数据类型之间D.存储结构之间6.以下数据结构中（D）属非线性结构。A.栈B.串C.队列D.平衡二叉树7.以下属于逻辑结构的是（C）。A.顺序表B.哈希表C.有序表D.单链表8.以下不属于存储结构的是（A）。A.栈B.线索二叉树C.哈希表D.双链表9.在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C）A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法10.数据结构在计算机存中的表示是指（A）。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系11.在数据的存储结构中，一个结点通常存储一个（B）A.数据项B.数据元素C.数据结构D.数据类型12.在决定选择何种类型的存储结构时，一般不多考虑（A）A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.所用编程语言实现这种结构是否方便13.计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、(B)。A.可行性、可移植性和可扩充性B.可行性、有穷性和正确性C.正确性、有穷性和稳定性D.易读性、稳定性和正确性14.以下关于算法的说确的是(D)。A.算法最终必须由计算机程序实现B.算法等同于程序C.算法的可行性是指指令不能有二义性D.以上几个都是错误的15.算法的时间复杂度与(A)有关。A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言16.算法的主要任务之一是分析(D)。A.算法是否具有较好的可读性B.算法中是否存在语法错误C.算法的功能是否符合设计要求D.算法的执行时间和问题规模之间的关系17.某算法的时间复杂度为0(n2)，表明该算法的(B)。A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比18.算法分析的目的是(C)。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性19.以下函数中时间复杂度最小的是(D)。A.nlog2n+5000nB.n2-8000nC.nlog2n-6000nD.20000log2n20.以下函数中时间复杂度最小的是(A)。A.1000g2nB.ng2n-1000g2nC.n2-1000g2nD.2ng2n-1000g2n二、判断题1.线性表中每个元素都有一个前趋元素和一个后继元素。(X)2.线性表中所有元素的排列顺序必须有小到大或由大到小。(X)3.静态链表既有顺序存储的优点，又有动态链表的优点，所以，利用它存取表中第i个元素的时间与元素个数n无关。(X)4.静态链表与动态链表在元素的插入、删除方面类似，不需做元素的移动。(V)5.线性表的顺序存储结构优于链式存储结构。(X)6.在循环单链表中，从表中任一结点出发都可以通过前后移动操作遍历整个循环链表。(X)7.在单链表中，可以从头结点开始查找任何一个结点。(V)8.在双链表中，可以从任一结点开始沿同一方向查找到任何其他结点。（X）9.顺序存储结构只能用于存放线性表。（X）10.线性表的逻辑结构总与其物理顺序一致。（X）11•顺序表具有随机存取特性。（V）12.单链表不具有随机存储特性，而双链表具有随机存取特性。（X）13.顺序栈中元素值的大小是有序的。（X）14.在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。（X）15.栈是一种对进栈、出栈操作的次序做了限制的线性表。（X）16.队列是一种对进栈、出栈操作的次序做了限制的线性表。（X）17.n个元素进队列的顺序和出队列的顺序总是一致的。（V）18.顺序队列中有多少元素，可以根据队首指针和队尾指针的值来计算。（V）19.串长度为串中不同字符的个数。（X）20.空串就是有空格构成的串。（X）三、填空题1.线索二叉树中左线索指向其（）结点，右线索指向其（）结点。前趋；后继2.有n个顶点的无向图最多有（）条边，而有向图最多有（）条弧。n（n-1）/2；n（n-1）3.图的邻接矩阵和邻接表存储结构中，邻接（）是唯一的