数据结构和C++程序设计题库完整.doc

word完美格式 精心整理 学习帮手 《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（ ） ???A）数据项???? B）数据类型???? C）数据元素???? D）数据变量 2．算法分析的目的是（ ） A）找出数据结构的合理性 B）研究算法的输入/输出关系 C）分析算法的效率以求改进 D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ） ??? A）O(1)???? B）0(n)???? C）O(n^2)???? D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（ ） A）112 B）144 C）148 D 5．下面关于线性表的叙述中，错误的是（ ） A） 顺序表使用一维数组实现的线性表 B） 顺序表必须占用一片连续的存储单元. C） 顺序表的空间利用率高于链表 D） 在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（ ）比较合适 A） 单链表 B）双链表 C） 顺序表 D）循环链表 7．队列通常采用的两种存储结构是（ ） A） 顺序存储结构和链式存储结构 B）散列方式和索引方式 C） 链表存储结构和线性存储结构 D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（ ） ??? A）p-next=p-next-next； B）p=p-next；p-nex=p-next-next； C）p-next=p-next；???? D）p=p-next-next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间 ?? ?A）单链表???? B）仅有头指针的单循环链表???? C）双链表???? D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（ ）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ） A）发生改变 B）不发生改变 C）不能确定 D）以上都不对 12．深度为5的二叉树至多有（ ）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（ ）个。 ??? A）4?? B）5? ??? C）6? ??? D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（ ） A）n B）n+1 C）n-1 D） 15．静态查找表和动态查找表二者的根本差别在于（ ） A）它们的逻辑结构不同 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样 二．填空 1．某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为________。 2．线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_________ 。 3. 对于一株具有n个结点的树，该树中所有结点的度数之和为______。 4. 在一个图中,所有顶点的度数之和等于所有边数的______________倍。 5. 一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二元树中度数为2的结点有______________个。 6．在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_____。 7．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是______ 。 8．设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是_________. 9．一个哈夫曼(Huffman