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

《数据结构(C语言版)复习知识点.doc》由会员分享，可在线阅读，更多相关《数据结构(C语言版)复习知识点.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、同i的值成正比。（ ）13顺序表中逻辑上相邻的元素物理位置不一定相邻。( )二、填空题1. 数据的逻辑结构可归结为以下四类:2. 2.算法的五个重要特性分别是3.下面程序段的时间复杂度是_。for (i=0;in;i+)for (j=0;jm;j+)Aij=0;4.在线性结构中，第一个结点_前驱结点，其余结点有且只有_个前驱结点。5.向一个长度为n的顺序表中的第i个元素(0=inext=Q-next C.Q-next=P D.P-next=Q5. 二叉查找树的查找效率与二叉树的形状有关, 在 ( )时其查找效率最低。A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 6.树最

3、合适用来表示_。A.有序数据元素 B. 无序数据元素 C.元素之间具有分支层次关系的数据 D. 元素之间无联系系的数据7.设高度为h的二叉树上只有度为0和2的结点，则此类二叉树中所包含的结点数至少为_。 A2h B.2h-1 C.2h+1 D.h+18.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是_。 A空或只有一个结点 B.完全二叉树 C.二叉排序树 D.高度等于其结点数9.在线索化二叉中，t所指结点没有左子树的充要条件是_。 At-left=NULL B.t-ltag=1 C.t-ltag=1 且t-left=NULL D.以上都不对10.一个有n个顶点的无向图最多有_条

4、边。An B.n(n-1) C.n(n-1)/2 D.2411.有一个长度为12的有序表，用折半查找对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_。 A35/12 B37/12 C39/12 D43/1212.具有6个顶点的无向图至少应有_条边能确保是一个连通图。 A5 B. 6 C.7 D.813.采用邻接表存的图的深度优先搜索遍历算法类似于二叉树的_。14. 在下列存储形式中，树的存储形式有哪些？（ ）15. 当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。 A. n-1 B. n C. n+1 D. n/2 1.设计哈夫曼编码2. 画树(已知一棵二叉树的先序序列和中序序列，请画出该树)3. 树、森林与对应的二叉树的转换4. 画出11个元素有序表的折半查找的判定树,ASL5.图的连接表存储结构、深度优先搜索遍历 广度优先搜索遍历6. 给定一组数,构造二叉排序树,计算ASL,遍历