2010年自考数据库及其应用重点知识讲解.doc

选择题、填空、判断1 数据项可以是数据元素的集合。 2. 递归过程不可以转换成非递归过程。3.深度为K的二叉树中结点总数2k-1。 4.二叉排序树是动态查找表。5.队列的存储结构只能用链表。 6. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。7. 在待排数据基本有序的情况下，快速排序效果最好。 8有序表可以使用顺序查找。9. 线性表在链式存储时，查找第i个元素的时间同i的值成正比10. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。11. 顺序查找法适用于存储结构为顺序或链接存储的线性表。12. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 13. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。14. 线性表的特点是每个元素都有一个前驱和一个后继。 15堆栈是先进先出的线性表。 16. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i n)，右儿子是2i+1（2i+1n）。17. 度为二的树就是二叉树。( ) 18. Huffman树的形状必是唯一的。19如频繁对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构？。20. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。21. 线性表就是顺序存储的表。 22.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。1. 数据的逻辑结构可归结为哪四类？ 算法的五个重要特性分别是哪些?2. 下面程序段的时间复杂度是_。for (i=0;in;i+)for (j=0;jnext=H BP-next= H-next CP=H DP=H-next25. 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是_。 A空或只有一个结点 B。完全二叉树 C。二叉排序树 D。高度等于其结点数26. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。27以下属于逻辑结构的是（ ）。A顺序表 B. 哈希表 C.有序表 D. 单链表29. 利用二叉链表存储树，则根结点的右指针指向哪？。20. 在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。30高度为 K的二叉树最大的结点数为（ ）。31树的后根遍历序列等同于该树对应的二叉树的( ). 32. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )33当采用分快查找时，数据的组织方式要求为 ？ 34快速排序方法在何情况下最不利于发挥其长处。35. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。题集6.26 设计哈夫曼编码、哈夫曼树题集6.27 画树 题集6.19 6.21 树、森林与对应的二叉树的转换题集9.3 折半查找算法及判定树图的邻接表、深度优先搜索遍