资源描述:
《数据结构和c++程序设计题库完整》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、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个元素
2、的存储地址是()A)112B)144C)148D)4125.下面关于线性表的叙述中,错误的是()A)顺序表使用一维数组实现的线性表B)顺序表必须占用一片连续的存储单元.C)顺序表的空间利用率高于链表D)在单链表中,每个结点只有一个链域.6.在需要经常查找结点的前驱与后继的情况下,使用()比较合适A)单链表B)双链表C)顺序表D)循环链表7.队列通常采用的两种存储结构是()A)顺序存储结构和链式存储结构B)散列方式和索引方式C)链表存储结构和线性存储结构D)线性存储结构和非线性存储结构8.在一个单链表中,若删除p所指结点的后继结点,则执行
3、() 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)3B)4C)5D)611.任何一棵二叉树的叶结点在先序、中序和后
4、序遍历序列中的相对次序()A)发生改变B)不发生改变C)不能确定D)以上都不对12.深度为5的二叉树至多有()个结点A)16B)32C)31D)1013.在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,那么度为0的结点数为()个。 A)4 B)5 C)6 D)714.对于一个具有n个顶点的无向图,若采用邻接表表示,则存放表头结点的数组(顶点表)的大小为()精心整理学习帮手word完美格式A)nB)n+1C)n-1D)n/215.静态查找表和动态查找表二者的根本差别在于()A)它们的
5、逻辑结构不同B)施加在其上的操作不同C)所包含的数据元素的类型不一样D)存储实现不一样二.填空1.某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为________。2.线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同,则插入一个新元素平均需要移动的元素个数是_________。3.对于一株具有n个结点的树,该树中所有结点的度数之和为______。4.在一个图中,所有顶点的度数之和等于所有边数的______________倍。5.一棵二叉树有67个结点,这些结点的度要么是0,要么是2
6、。这棵二元树中度数为2的结点有______________个。6.在一个无向图的邻接表中,若表结点的个数是m,则图中边的条数是_____。7.采用堆排序、快速排序、冒泡排序,对初态有序的表,最省时间的是______。8.设二叉树结点的先根序列为ABDECFGH,中根序列为DEBAFCHG,则二元树中叶结点是_________.9.一个哈夫曼(Huffman)树有19个结点,则其叶结点的个数是______。10.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈,一个元素出栈后即进入队列Q,若6个元素出队列的
7、顺序是a3,a5,a4,a6,a2,a1,则栈S至少应该容纳_______个元素。三.判断1.线性表的链式存储结构优于顺序行储结构。()2.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。()3.对于n个记录的集合进行归并排序,存最坏的情况下所需要的时间是O(n^2)。()4.表中的每一个元素都有一个前驱和后继元素。()5.进栈操作push(x,s)作用于链接栈时,无须判满。()6.只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。()7.在索引顺序表查找方法中,对索引顺序表可以使用顺序表查找
8、方法,也可以使用二分查找方法。()8.数据元素是数据的最小单位。()9.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。()10.按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。()四.