vwqAAA数据结构练习题

单选、填空、判断为各章课后题。下面列出项目四到项目八部分部分习题答案（说明：红色字为正确答案）1. 对于一个10阶对称矩阵，若按行序存储下三角（包括对角线）的元素，则矩阵第6行3列的元素地址是一维数组中的第（18）个元素。A.9B.12C.13D.182. 广义表（a,b）,c,d）的表头是（c），表尾是（d）。A.aB.dC.（a,b）D.（c,d）3. 广义表（a,（b，（）,c）,（d），e）的长度是（1）。A.1B.2C.3D.44. 稀疏矩阵一般是指（D）。A.非零元素和零元素都较少B.非零元素较多C.零元素较多D.非零元素和零元素都较多5. 按照二叉树的定义，具有3个结点的二叉树有（5）中形态。A.3B.4C.5D.66. 若一棵二叉树有n个结点，m个叶子及诶单，深度为h，则下面关系中正确的是（B）。A.n=h+mB.n=2h-1C.m=n/2D.n=m+17. 已知某二叉树的先序遍历序列为cedba，中序遍历序列为debac，则它的后序遍历序列为（B）。A.acbedB.dabecC.deabcD.decab8. 有权值分别为3，8，6，5，2的叶子结点生成一棵哈夫曼树，则它的带权路径长度为（C）。A.48B.72C.55D.249. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要（B）条边。A,nB.n-1C.n+1D.2n10. 若具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵一定为一个（D）。A.一般矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵11. 有向图的邻接表的第i个链表中的边界点数目是第i个顶点的（C）。A.度数B.入度C.出度D.边数12. 若无向图的任意一个顶点出发进行一次深度优先遍历便可以访问该图的所有顶点，则该图一定是一个（B）图。A.非连通B.连通C.强连通D.子13. 在AOV网进行拓扑排序时，所有入度为0的顶点被链接称为一个（A）结点。A.堆栈B.队列C.数组D.线性表14. 已知某有向图G=（V，E），其中V=V0，V1，V 2，V 3，V 4，V 5，E=，G的拓扑序列为（A）。A.V 2V0V 3V 4 V1V 5B.V 2V 3 V0V 4 V1V 5C.V0V 2V 3V 4 V1V 5D.V0V 3V 2V 4 V1V 515. 衡量查找算法性能好坏的主要标准是（D）。A.参加比较的关键字值的多少B.被查找的关键字值在关键字序列中的位置C.关键字序列中是否存在被查找关键字的值D.关键字的平均比较次数的多少16. 在一个具有15个数据元素的有序顺序表中，采用折半查找方法查找一个表中不存在的记录，需要进行（B）次关键字的比较。A.0B.4C.5D.1517. 将数据元素2，4，6，8，10，12，14，16，18，20一次存放一个一维数组中，然后采用折半查找元素12，被比较过的数据元素的下标依次为（C）。A.10，16，12B.10，12，16C.4，7，5D.4，5，7填空题：1. 字符串是一个特殊的线性表，其特殊性体现在串中的元素为字符型数据2. 两个串相等的条件是两个串的长度相等，并且各个对应位置的字符都相等3. 从字符串的内部存储来看，常用的存储方法有定长顺序存储，堆存储和块链存储，其中堆存储常用语实现可变长字符串。4. 若有数组定义为int a67，假设一个整型数据占4个字节，已知该数组的首地址为1000，则按行存储时数组元素a34的地址为1100。5. 在一个稀疏矩阵的三元组表中，每个非零元素对应的三元组包括行号、列号和元素值三项。6. 稀疏矩阵常用的压缩存储方法有两种，分别是三元组和十字链表链式。7. 广义表的链式存储结构中存在两种结构的结点，分别是元素结点和表结点。8. 任何非空树中有且只有一个结点没有前驱结点，该结点是树的根结点。9. 深度为5的满二叉树的结点个数为31，其中第4层的结点个数为8，叶子结点个数为16。10. 若具有n各结点的非空二叉树，具有n0个叶子结点，则该二叉树中度为2的结点个数为n0-1，度为1的结点个数为n-2 n0+1。11. 对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为i/2，其左孩子的编号为2i，右孩子的编号为2i+1。12. 若具有n个结点的二叉树采用链式存储结构，则该链表中有2n，个指针域，其中n-1个指针域用于连接孩子结点，n+1个指针域为NULL。13. 二叉树的遍历方式通常有先序遍历、中序遍历、后序遍历和层次遍历四种。14. 已知某完全二叉树采用顺序存储结构，结点的存放次序为A，B，C，D，E，F，G，H，I，J，则该完全二叉树的后序遍历序列为HIDJEBFGAC。15. 线索二叉树中，每个结点的空的左孩子指针用于保存某种遍历次序下该结点的前驱地址。16. 哈夫曼二叉树又成为最优二叉树，是相同叶子结点所构成的二叉树中带权路径长度最短的二叉树。其特点是：权值越大的叶子结点离根越近。17. 有向图的常用存储结构有邻接矩阵、临接表和十字链表。18. 有向图的常用存储结构有邻接矩阵、临接表和邻接多重表。19. 若无向图中有m条边，则表示该表的邻接表中有2m个结点。20. 在表示有向图的邻接矩阵中，第i行中非零元素的个数等于顶点的出度，第i列中非零元素的个数等于定点的入度。21. 在无权图G的邻接矩阵A中，若Aij等于1，则Aji等于1。22. 通过拓扑排序能够得到拓扑序列的图一定是无回路的有向图。23. 在AOV网中，顶点表示活动，边表示活动之间的优先关系。24. 对线性表采用折半查找方法时，该线性表必须采用顺序存储结构，并且数据元素按关键字有序排列。25. 对二叉排序树进行中序遍历，可以得到按关键字递增排列的有序序列。n个数据元素使用冒泡排序算法进行排序时，最坏情况下的比较次数为n（n-1）/2。程序：线性顺序表L的第i个位置插入一个新的数据元素e线性顺序表L的第i个位置删除一个新的数据元素e顺序栈的进栈、出栈顺序存储结构的线性静态查找表L进行折半查找关键字为Key的算法对顺序存储结构的线性静态查找表L进行顺序查找关键字为Key的算法直接插入排序冒泡排序简答：1. 请计算一下程序的时间复杂度：S=0For(i=0;i=n;i+)P=1;For(j=1;j=i;j+)p =p*j;S+=p;要求写出必要步骤或计算说明。标准答案：本段程序的时间复杂度主要取决于语句p =p*j的执行次数 该语句的执行次数为取决于内层循环的循环次数为：1+2+3+n=n*（n-1）/2 1. 所以，时间复杂度为O（n2）2. 已知某二叉树中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，试画出该二叉树。答案：3. 给定一组权值W=11,15,6,3,20,7，试构造出相应的哈夫曼树，并计算其带权路径长度WPL。标准答案： 4. 假设用于通信的电文有字符集a，b，c，d，e，f，g，h中的字母构成，这8个字母在电文中出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计相应的哈夫曼编码。答案：5. 对于下图所示的无向图，请构造其最小生成树。答案：6. 对于下图所示的AOE网，试求出各活动的最早开始时间与最晚开始时间，所有的管家路径，以及该工程完成的最短时间。答案：7. 已知一组元素为45，20，70，56，15，37，69，30，画出顺序输入生成的二叉排序树并写出其中序遍历的结果。答案：中序遍历结果为：15,20,30,37,45,56,69,708. 对于下图所示的有向图，试