16春季福师《数据结构概论》在线作业二.doc

谋学网福师数据结构概论在线作业二一、单选题（共 25 道试题，共 50 分。）1. 树的后根遍历序列等同于该树对应的二叉树的（ ）. 先序序列. 中序序列. 后序序列. 都不正确正确答案：2. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。. (2,5,12,16)26(60,32,72). (5,16,2,12)28(60,32,72). (2,16,12,5)28(60,32,72). (5,16,2,12)28(32,60,72)正确答案：3. 连续存储设计时，存储单元的地址（ ）. 一定连续. 一定不连续. 不一定连续. 部分连续，部分不连续正确答案：4. 下面给出的四种排序法中( )排序法是不稳定性排序法。. 插入. 冒泡. 二路归并. 堆正确答案：5. 设广义表L=（,），则L的长度和深度分别为（ ）. 1和1. 1和3. 1和2. 2和3正确答案：6. 线索二叉树是一种（ ）构。. 逻辑. 逻辑和存储. 物理. 线性正确答案：7. 有n个叶子的哈夫曼树的结点总数为（ ）。. 不确定. 2n. 2n+1. 2n-1正确答案：8. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序. 冒泡. 希尔. 快速. 堆正确答案：9. 链表不具有的特点是（ ）. 插入、删除不需要移动元素. 可随机访问任一元素. 不必事先估计存储空间. 所需空间与线性长度成正比正确答案：10. 串的长度是指（ ）. 串中所含不同字母的个数. 串中所含字符的个数. 串中所含不同字符的个数. 串中所含非空格字符的个数正确答案：11. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。. 直接插入. 直接选择. 堆. 快速正确答案：12. 若要求尽可能快地对序列进行稳定的排序，则应选（. 快速排序. 归并排序. 冒泡排序. 堆正确答案：13. 表达式*(+)-的后缀表达式是( )。. *+-. +*-. *+-. -+*正确答案：14. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）. 9. 11. 15. 不确定正确答案：15. 在完全二叉树中，若一个结点是叶结点，则它没（ ）。. 左子结点. 右子结点. 左子结点和右子结点. 左子结点，右子结点和兄弟结点正确答案：16. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ). （N+1）/2. N/2. N. （1+N）*N /2正确答案：17. 栈和队都是（ ）. 顺序存储的. 线性结构. 链式存储的. 非线性结构正确答案：18. 在下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n OFOR j:=1 TO n O x:=x+1;. O(2n). O(n). O(n2). O(log2n)正确答案：19. 数组0.4,-1.-3,5.7中含有元素的个数（ ）. 55. 45. 36. 16正确答案：20. 对于一个头指针为h的带头结点的单链表，判定该表为空表的条件是（ ）. h=NULL. hnxt=NULL. hnxt=h. h!=NULL正确答案：21. 广义表（,）的表头是（ ），表尾是（ ）。. . （）. （,）. （,）正确答案：22. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）. 求子串. 联接. 匹配. 求串长正确答案：23. 下面叙述正确的是（ ）. 算法的执行效率与数据的存储结构无关. 算法的空间复杂度是指算法程序中指令(或语句)的条数. 算法的有穷性是指算法必须能在执行有限个步骤之后终止. 以上三种描述都不对正确答案：24. 对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ ）排序。. 选择. 快速. 希尔. 冒泡正确答案：25. 关键路径是事件结点网络中（ ）. 从源点到汇点的最长路径. 从源点到汇点的最短路径. 最长回路. 最短回路正确答案： 福师数据结构概论在线作业二二、判断题（共 20 道试题，共 40 分。）1. 线性表的特点是每个元素都有一个前驱和一个后继。. 错误. 正确正确答案：2. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止. 错误. 正确正确答案：3. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）. 错误. 正确正确答案：4. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。. 错误. 正确正确答案：5. 循环链表不是线性表（ ）. 错误. 正确正确答案：6. 循环队列通常用指针来实现队列的头尾相接。. 错误. 正确正确答案：7. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。. 错误. 正确正确答案：8. 顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）. 错误. 正确正确答案：9. 任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（ ）. 错误. 正确正确答案：10. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大. 错误. 正确正确答案：11. 栈和队列都是限制存取点的线性结构（ ）. 错误. 正确正确答案：12. 二叉树的遍历结果不是唯一的. 错误. 正确正确答案：13. 算法的优劣与算法描述语言无关，但与所用计算机有关（ ）. 错误. 正确正确答案：14. 算法的优劣与算法描述语言无关，但与所用计算机有关。. 错误. 正确正确答案：15. 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。. 错误. 正确正确答案：16. 直接选择排序算法在最好情况下的时间复杂度为O（N）。. 错误. 正确正确答案：17. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。. 错误. 正确正确答案：18. 在待排数据基本有序的情况下，快速排序效果最好。. 错误. 正确正确答案：19. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）. 错误. 正确正确答案：20. 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素. 错误. 正确正确答案： 福师数据结构概论在线作业二三、多选题（共 5 道试题，共 10 分。）1. 在下列情况中，不能为二叉树的是（ ）. 每个结点至多有两棵子树的树. 哈夫曼树. 每个结点至多有两棵子树的有序树. 每个结点只有一棵右子树正确答案：2. 以下数据结构中属于线性数据结构的有哪些（ ）. 队列. 线性表. 二叉树. 栈正确答案：3. 有关二叉树下列说法不正确的是（ ）. 二叉树的度为2. 一棵二叉树的度可以小于2. 二叉树中至少有一个结点的度为2. 二叉树中任何一个结点的度都为2正确答案：4. 下面关于哈希(Hsh)查找的说法不正确的是( ). 哈希函数构造的越复杂越好，因为这样随机性好，冲突小. 除留余数法是所有哈希函数中最好的. 不存在特别好与坏的哈希函数，要视情况而定. 若需在哈希表中删去一个元素，不管用何种方法解决冲突