搜索
1难度系数及复杂系数说明：难度系数从易到难分别为：N1、N2、N3、N4、N5复杂系数从简到繁分别为：F1、F2、F3、F4、F5数据结构第三阶段作业第6章树和二叉树6.1单项选择题1.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B___。（N2F1）A.正确B.错误2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为B个。（N2F1）A．15B．16C．17D．473.按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。（N2F1）A.3B.4C.5D.64.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。（N3F1）A.5B.6C.30D.325.深度为5的二叉树至多有__C__个结点。（N2F1）A.16B.32C.31D.106.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__A__。（N3F1）A.2hB.2h-1C.2h+1D.h+17.对一个满二叉树，m个树叶，n个结点，深度为h，则_D___。（N3F1）A.n=h+mB.h+m=2nC.m=h-1D.n=2h-18.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__A__。（N3F1）A.不发生改变B.发生改变C.不能确定D.以上都不对9.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_C___。（N3F1）A.uwvtsB.vwutsC.wuvtsD.wutsv6.2简答题1.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。（N2F3）22.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。（N3F2）请画出该树。3.以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度。（N3F3）4.一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?（N3F2）最大深度：h=N-k+1,最小深度：logkN+1第7章图7.1单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的__C__倍。（N3F1）A.1/2B.1C.2D.42．任何一个无向连通图的最小生成树B。（N3F1）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__B__倍。（N3F1）A.1/2B.1C.2D.44．一个有n个顶点的无向图最多有_C___条边。（N2F1）A.nB.n(n-1)C.n(n-1)/2D.2n35．具有4个顶点的无向完全图有__A__条边。（N2F1）A.6B.12C.16D.206．具有6个顶点的无向图至少应有_A___条边才能确保是一个连通图。（N3F1）A.5B.6C.7D.87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要_C___条边。（N3F1）A.nB.n+1C.n-1D.n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_A___。（N3F1）A.nB.(n-1)2C.n-1D.n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①_A__；所有邻接表中的接点总数是_②_C__。（N3F1）①A.nB.n+1C.n-1D.n+e②A.e/2B.eC.2eD.n+e10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为D__①_B_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。（N3F1）①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,b7.2综合题1．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树：（N3F3）（1）图7.6图7.1一个无向图baecdfbadcef161115151516131412214（2）图7.72．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。（N3F3）图7.961213212495201516106154372543223356abdfce53．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：(1)请画出该AOE图。(2)计算完成整个计划需要的时间。(3)求出该AOE网的关键路径。（N4F4）∝645∝∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝∝97∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝答：(1)该AOE图为：(2)完成整个计划需要18天。(3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2，V5，V8，V9，）第8章查找8.1单项选择题1.顺序查找法适合于存储结构为__B__的线性表。（N2F1）A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储2.对线性表进行二分查找时，要求线性表必须_C___。（N2F1）A.以顺序方式存储B.以链接方式存储6C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为__C__.（N3F1）A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_D___。（N3F1）A．O（n2）B.O(nlog2n)C.O(n)D.O(log2n)5.二分查找和二叉排序树的时间性能__B__。（N2F1）A.相同B.不相同6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，__C__次比较后查找成功。（N3F1）A.1B.2C.4D.87.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：（N3F1）addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是__D__。A.8B.3C.5D.98.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为__B__。（N3F1）A.35/12B.37/12C.39/12D.43/129．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为C。（N2F1）A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素往开始前查找该数据元素D.与查找顺序无关10．解决散列法中出现的冲突问题常采用的方法是D。（N2F1）A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法第9章排序9.1单项选择题1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是__D__。（N2F1）A.希尔排序B.起泡排序C.插入排序D.选择排序2.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_C___排序法。（N2F1）A.起泡排序B.快速排序C.堆排序D.基数排序3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A___。（N2F1）A.插入排序B.选择排序C.快速排序D.归并排序4.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为__B__。（N3F1）A.79，46，56，38，40，80B.38，46,56，79，40，84，C.84，79，56，46，40，38D.84，56，79，40，46，385.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为__C__。（N3F1）A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，796.一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_A___。（N3F1）A.16，25，35，48，23，40，79，82，36，727B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，827.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__C__。（N2F1）A.希尔排序B.起泡排序C.插入排序D.选择排序8.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为_D___。（N2F1）A.希尔排序B.归并排序C.插入排序D.选择排序