二叉排序树最坏情况下深度_二叉排序树最坏情况下树的高度

树、图、查找、排序习题一 　　第一部分 选择题 　　1、  在树的结构中，如果结点A有3个兄弟，而且B是A的双亲，则B的度是     　　A.   3         B.  1             C. 4                 D. 5 　　2、在具有6个顶点的无向简单图中，当边数至少为       条时，才能确保该图是连通图。 　　A．  7        B.  8              C. 11               D. 12 　　3、在内部排序中，平均比较次数最少的一种是        　　A． 插入排序        B.快速排序      C. 选择排序      D. 归并排序 　　4、具有65个结点的完全二叉树其浓度为         。 　　A. 8         B.  7          C. 6            D. 5 　　5、若表r在排序前已按素键值递增顺序排列，采用       方法比较次数最少。 　　A. 直接插入排序  B. 快速排序   C. 归并排序    D. 选择排序 　　6、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中         　　A. 第i行非∞素之和              B. 第i列非∞素之和 　　C. 第i行非零且非∞素个数        D. 第i列非零且非∞素个数 　　7、下列排序算法中，       排序在每趟结束后不一定能选出一个素放到其排好序的最终位置上。 　　A. 选择       B. 冒泡    C. 归并     D.  堆 　　8、对有14个素的有序表A[1..14]作二分查找，查找素A[4]时的被比较素依次为 　　A．A[1],A[2],A[3],A[4]               B.A[1],A[14],A[7],A[4] 　　C. A[7],A[3],A[5],A[4]               D.A[7],A[5],A[3],A[4] 　　9、以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为 　　A.2n-1     B. n-1     C. n+1      D. 2n+1 　　10、关键路径是事件节点网络中 　　A.从起点到终点的最长路径       B. 从起点到终点的最短路径 　　C.最长的回路                   D. 最短的回路 　　11、设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为 　　A. O(nlog2e)     B.O(en)      C. O(elog2n)    D. O(n+e) 　　12、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用     查找方法。 　　A. 分块       B. 顺序      C. 折半      D. 基于属性 　　13、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个素，其存储地址为1，每个素占一个地址空间，则a85的地址为 　　A.  13         B.  33        C. 18       D. 40 　　14、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有           个。 　　A.  n-1        B. n          C. n+1      D. n+2 　　15、设有100个素，采用二分法查找时，最大比较次数是 　　A． 7          B. 25        C. 10        D. 50 　　16、已知关键序列为：3，7，6，9，8，1，4，5，2，进行排序的最小交换次数是 　　A．6           B. 7          C. 8          D. 20 　　17、        文件主要在磁盘上生成，在建立文件时，记录可不必顺序存放，只要采用某种方式进行记录标识，标识到记录的物理地址变换。 　　A. 标识       B. 分区        C. 直接        D. 链接 　　18、任何一个带权的无向连通图的最小生成树 　　A. 只有一棵    B. 有一棵或多棵    C.一定有多棵   D. 可能不存在 　　19、下列存储形式中，哪一个不是树的存储形式 　　A. 双亲表示法    B.孩子链表表示法   C. 孩子兄弟表示法  D.顺序存储表示法 　　20、对n个记录的文件进行堆排序，最坏情况下的执行时间为 　　A. O(nlog2n)    B.O(n)       C.O(nlog2n)     D. O(n2) 　　21、一个记录的关键字为{46，79，56，38，40，84}，采用快速排序以一个记录为基准得到的第一次划分结果为 　　A．{38,40,46,56,38,79,84}        B.{40,38,46,79,56,84} 　　C.{40,38,46,56,79,84}            D.{40,38,46,56,79} 　　22、对5个不同的数据进行排序，最多需要比较        次 　　A．8             B. 10            C. 15           D. 25 　　23、设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为 　　A．O(nlog2e)     B. O(n+e)       C.O(en)       D.O(ne) 　　24、从未排序序列中挑选素，将其放在已排序序列的一端，这种排序方法称为 　　A．选择排序    B. 插入排序    C.快速排序    D. 冒泡排序 　　25、若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个 　　A.一般矩阵    B.对称矩阵    C.对角矩阵     D. 稀疏矩阵 　　26、一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为 　　A．n*n     B. n*n/2      C. (n+1)*n/2    D.(n+1)*(n+1)/2 　　27、在一个图中，所有顶点的度数之和等于所有边数的       倍 　　A. 1/2      B. 1        C. 2          D. 4 　　28、下列排序方法中，排序趟数与序列的原始状态有关的方法是 　　A．选择排序   B.希尔排序    C.堆排序     D. 冒泡排序 　　29、在一棵具有五层的满二叉树中，结点的总数为 　　A．31        B. 32        C. 33         D. 16 　　30、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为 　　A．O(1)      B. O(n)     C. O(n2)      D.O(nlog2n) 　　31、当两个素比较出现反序时就相互交换位置的排序方法称为 　　A．归并排序   B.选择排序   C. 交换排序    D.插入排序 　　32、对线性表进行二分查找时，要求线性表必须 　　A．以顺序方式存储               B.以顺序方式存储且素有序 　　C．以链接方式存储               D.以链接方式存储且素有序 　　33、在一棵二叉树中，第5层上的结点数最多为 　　A． 8      B. 15      C. 16      D. 32 　　34、由分别带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 　　A．23     B.  37     C. 44     D.  46 　　35、导致图的遍历序列不唯一的因素是 　　A.出发点不同，遍历方法不同      B. 出发点不同，存储结构不同 　　C．遍历方法不同，存储结构不同   D.出发点不、存储结构不同、遍历方法不同 　　36、折半查找算法的时间复杂度为 　　A．O(n2)     B. O(n)     C. O(nlog2n)      D.O(log2n) 　　37、在归并排序过程中，需要归并的趟数为 　　A. n       B. n         C. n2        D. nlog2n 　　38、已知8个数据素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉树后，最后两层上的结点总数为 　　A．1     B.  2     C.  3     D. 4 　　39、对下列关键字序列用快速排序法进行排序时，速度最快的情形是 　　A．{21，25，5，17，9，23，30}          B.{25，23，30，17，21，5，9} 　　C. {21，9，17，30，25，23，5}          D.{5，9，17，21，23，25，30} 　　40、堆的形状是一棵 　　A．二叉排序树     B.满二叉树      C.完全二叉树    D.不是二叉树 　　41、如右图所示的图，若从顶点a出发按深度优先搜索进行遍历，则可以得到 　　A．  abecdf 　　B．  acfebd 　　C．  aebcfd 　　D．  aedfcb 　　42、以下哪个术语与数据的存储结构无关？ 　　A.栈      B. 散列表     C.穿线树      D.双链表 　　43、顺序查找法适用于存储结构为          的线性表。 　　A．散列存储     B.压缩存储    C.链接存储    D.索引存储 　　44、就平均时间而言，下列排序方法中最佳的一种是 　　A．堆排序   B.快速排序    C.归并排序     D.选择排序 　　45、比较次数与待排序记录的初始排列状态无关的是 　　A．插入排序  B.二分法插入排序   C.快速排序   D.冒泡排序 　　46、         是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 　　A． 归并排序     B.堆排序     C.折半排序     D.选择排序 　　47、由二叉树的     遍历，可以唯一确定一棵二叉树。 　　A．前序和后序  B.前序和中序   C.后序     D.中序 　　48、设有一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较         次。 　　A． 9      B. 8     C. 7    D.6 　　49、一棵二叉排序树T，用      方法进行遍历，可以得到各结点的递增序列。 　　A．先根遍历  B.中根遍历  C.层次遍历    D.后根遍历 　　50、下列四种排序方法中，不稳定的方法是 　　A．直接插入排序  B.冒泡排序   C.归并排序   D.直接选择排序 　　51、散列函数有一个共同的性质，即函数值应当以       来取值。 　　A．最大概率   B.最小概率    C.平均概率     D.同等概率 　　52、排序算法好坏的最重要标志是 　　A．  附加空间的开销  B.执行时间的开销  C.算法的复杂程序  D.算法执行中的比较次数 　　53、散表函数不是一对一的关系，因此选用好的         方法是散列文件的关键。 　　A.散列函数   B.除余法中的质数   C.冲突处理   D.散列函数和冲突处理 　　54、有文件局部有序或文件长度较小的情况下，最佳内部排序方法是 　　A.直接插入排序  B.冒泡排序  C.简单选择排序   D.归并排序 　　55、具有n个顶点的有向完全图中，边的总数为        　　A.n(n+1)  B. n(n-1)    C. n(n-1)/2     D. n(n+1)/2 　　56、下述排序算法中，稳定的是 　　A．直接选择排序  B.直接插入排序   C.快速排序   D.堆排序 　　57、倒排文件的主要优点是 　　A．便于进行插入和删除运算。   B.便于进行文件的合并 　　C.能大大提高基于非关键码数据项的查找速度 　　D.能大大节省存储空间 　　58、设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是 　　A．x是y的左兄弟                B.x是y的右兄弟 　　C. x是y的祖先                  D.x是y的后代 　　59、下称四种排序方法中，不稳定的方法是 　　A．直接插入排序  B.冒泡排序   C.归并排序   D.直接选择排序 　　60、用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某一时刻，已选取的顶点集合U={1,2,3},边的集合TE={(1,2),(2,3)},要选取下一条权值最小的边，应当从         组中选取。 　　A．{（1，4），（3，4），（3，5），（2，5）}  B.{（4，5），（1，3），（3，5）} 　　C．{（1，2），（2，3），（3，5）}     D. {（3，4），（3，5），（4，5），（1，4）}