东师《数据结构》春在线作业.docVIP

2017秋17春数据结构17春在线作业2 一、单选题（共 20 道试题，共 60 分。） 1. 设有n个结点的AVL树，其平均查找长度为 ()。 A. Ο( 1 ) B. Ο(log2n) C. Ο(n) D. Ο(nlog2n) 正确答案： 2. 若由树转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。 A. 根结点无右子树的二叉树 B. 根结点无左子树的二叉树 C. 根结点可能有左子树和右子树 D. 各结点只有一个子女的二叉树 正确答案： 3. 若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。 A. X的双亲 B. X的右子树中最左下的结点 C. X的左子树中最右下的结点 D. X的右子树中最左下的叶结点 正确答案： 4. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。 A. 无向图 B. 有向图 C. 带权的无向图 D. 带权的有向图 正确答案： 5. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( ) A. 线性表 B. 广义表 C. 树形结构 D. 图结构 正确答案： 6. 数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。 A. 直接选择排序 B. 冒泡排序 C. 直接插入排序 D. 堆排序 正确答案： 7. head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。 A. p-next = = NULL B. p = = NULL C. p-next = = head D. p = = head 正确答案： 8. 判断线索二叉树中某结点p有左子女的条件是 ( )。 A. p ! = NULL B. p-lchild ! = NULL C. p-ltag = = 0 D. p-ltag = = 1 正确答案： 9. 设有2500个无序的记录，希望以最快的速度挑选出其中前10个排序码最大的记录，最好选用的排序方法是 ()。 A. 直接插入排序 B. 堆排序 C. 冒泡排序 D. 快速排序 正确答案： 10. head指向的带表头结点的单链表为空的判定条件是 ( )。 A. head = = NULL B. head-next = = head C. head ! = NULL D. head-next = = NULL 正确答案： 11. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是：( )。 A. 不确定 B. 0 C. 1 D. 2 正确答案： 12. 设有n个结点的最佳二叉排序树，对于成功的查找，最少的比较次数为()。 A. Ο( 1 ) B. Ο(log2n) C. Ο(n) D. Ο(nlog2n) 正确答案： 13. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。 A. 根结点无右子树的二叉树 B. 根结点无左子树的二叉树 C. 根结点可能有左子树和必有右子树 D. 各结点只有一个子女的二叉树 正确答案： 14. 设s1 = abc ，则strlen(s1) = ( )。 A. 0 B. 1 C. 2 D. 3 正确答案： 15. 若一组记录的排序码为 { 46,79,56,38,40,84 }，则利用堆排序的方法建立的初始堆为 ( )。 A. 79,46,56,38,40,84 B. 84,79,56,38,40,46 C. 84,79,56,46,40,38 D. 84,56,79,40,46,38 正确答案： 16. 有n个顶点的无向连通图的边数最少为 ()。 A. n/2 B. n-1 C. n D. n+1 正确答案： 17. 下面关于串的叙述中，哪一个是不正确的? ( ) A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储 正确答案： 18. 在下述几种排序方法中，不稳定的排序方法是 ()。 A. 直接插入排序 B. 冒泡排序 C. 直接选择排序 D. 归并排序 正确答案： 19. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。 A. 附加文件 B. 按关键字大小排序 C. 按记录输入先后排序 D. 连续排序 正确答案： 20. 折半查找要求结点 ()。 A. 无序、顺序存储 B. 无序、链接存储 C. 有序、顺序存储 D. 有序、链接存储 正确答案： 数据结构17春在线作业2 二、判断题（共 20 道试题，共 40 分。） 1. 循环队列也存在空间溢出问题。 A. 错误 B