数据结构(C语言版)复习知识点.doc

《数据结构(C语言版)复习知识点.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、参考与知识点一、判断题1.数据元素是数据结构中讨论的最小单位。()2.二叉排序树是静态查找表。（）3.有序表不可以使用顺序查找。（）4.用折半查找方法查找一个线性表时，要求该线性表必须具有的特点是顺序存储且有序。（）5.队列的存储结构只能用顺序表。()6.堆栈是后进先出的线性表。（）7.如频繁对一个线性表进行插入和删除操作，则该线性表宜采用顺序存储结构。()8.树的深度是树中叶子结点所在的层次之和。()9.在二叉树的第i层上至多有2i-1个结点。()10.算法设计与数据的存储结构有关。()11循环

2、链表不是线性表.()12线性表在链式存储时，查找第i个元素的时间同i的值成正比。（）13顺序表中逻辑上相邻的元素物理位置不一定相邻。()二、填空题1.数据的逻辑结构可归结为以下四类:1.2.算法的五个重要特性分别是3.下面程序段的时间复杂度是_____________。for(i=0;i

3、插入一个元素时，需要后移___________个元素。6.树型结构中________无前驱，_________无后继。7.具有n个顶点的有向图，每个顶点的度最大可达________。8.在数据结构中，与所使用计算机无关的是数据的_______结构。9.在一个图中,所有顶点的度之和等于所有边数的________倍。10.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___________存储结构。11.一棵有n个结点的满二叉树有_________

4、个度为1的结点12.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.13.在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______三、单项选择题1.计算机算法指的是_______________。A.计算方法B.解决问题的有限指令序列C.排序方法D.调度方法2.一个栈的进栈序列是a,b,c,d,e，则栈的不可能输出序列是__________A．edcbaB．decbaC

5、．dceabD．abcde3.链表不具备的特点是___________。A．可随机访问任一结点B.插入删除不需要移动数据元素C．不必事先估计存储空间D.所需空间与其长度成正比4.P和Q是指向单链表的两个元素的指针，P所指的元素是Q所指元素的前驱的条件是_________________。A.P==QB.P->next==Q->nextC.Q->next==PD.P->next==Q5.二叉查找树的查找效率与二叉树的形状有关,在()时其查找效率最低。A.结点太多B.完全二叉树C.呈单枝树D.结点太复

6、杂。6.树最合适用来表示_________。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系系的数据7.设高度为h的二叉树上只有度为0和2的结点，则此类二叉树中所包含的结点数至少为__________。A．2hB.2h-1C.2h+1D.h+18.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是_______。A．空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数9.在线索化二叉中，t所指结点没有左子树的充要条件是_________。

7、A．t->left==NULLB.t->ltag==1C.t-ltag==1且t->left==NULLD.以上都不对10.一个有n个顶点的无向图最多有_________条边。A．nB.n(n-1)C.n(n-1)/2D.2411.有一个长度为12的有序表，用折半查找对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_________。A．35/12B．37/12C．39/12D．43/1212.具有6个顶点的无向图至少应有______条边能确保是一个连通图。A．5B.6C.7D

8、.813.采用邻接表存的图的深度优先搜索遍历算法类似于二叉树的________。14.在下列存储形式中，树的存储形式有哪些？（）15.当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。A.n-1B.nC.n+1D.n/21.设计哈夫曼编码2.画树(已知一棵二叉树的先序序列和中序序列，请画出该树)3.树、森林与对应的二叉树的转换4.画出11个元素有序表的折半查找的判定树,ASL5.图的连接表存储结构、深度优先搜索遍历广度优先搜索遍历6.给定一组数,构造二叉排序树,计