16秋福建师范大学《数据结构概论》在线作业二.doc

谋学网一、单选题（共 25 道试题，共 50 分。）1. 要连通具有n个顶点的有向图，至少需要（ ）条边。. n-l. n. n+l. 2n 标准答案：2. 适用于折半查找的表的存储方式及元素排列要求为（ ）. 链接方式存储，元素无序. 链接方式存储，元素有序. 顺序方式存储，元素无序. 顺序方式存储，元素有序 标准答案：3. 已知广义表L=（x,y,z），（u，t，w），从L表中取出原子项t的运算是（ ）。. h（til（til（L）. til（h（h（til（L）. h（til（h（til（L）. h（til(h（til（til（L）)） 标准答案：4. 下面的程序段中，对x的赋值语句的频度为（ ）OR i:=1 TO n OOR j:=1 TO n O x:=x+1;. O(2n). O(n). O(n2). O(log2n) 标准答案：5. 广义表运算式Til(,),(,)的操作结果是（ ）。. (,). ,. (,). 标准答案：6. 求解最短路径的loy算法的时间复杂度为( )。. O（n）. O（n+）. O（n*n）. O（n*n*n） 标准答案：7. 算法的时间复杂度是由（ ）决定的。. 问题的规模. 待处理数据的初态. 和. 变量个数 标准答案：8. 一个算法应该是（ ）。. 程序. 问题求解步骤的描述. 要满足五个基本特性. 和. 标准答案：9. 在完全二叉树中，若一个结点是叶结点，则它没（ ）. 左子结点. 右子结点. 左子结点和右子结点. 左子结点，右子结点和兄弟结点 标准答案：10. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）. 5 4 3 6 1 2. 4 5 3 1 2 6. 3 4 6 5 2 1. 2 3 4 1 5 6 标准答案：11. 从逻辑上可以把数据结构分为（ ）两大类。. 动态结构、静态结构. 顺序结构、链式结构. 线性结构、非线性结构. 初等结构、构造型结构 标准答案：12. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列（ ）. 5 4 3 6 1 2. 4 5 3 1 2 6. 3 4 6 5 2 1. 2 3 4 1 5 6 标准答案：13. 树的后根遍历序列等同于该树对应的二叉树的（ ）. 先序序列. 中序序列. 后序序列. 都不正确 标准答案：14. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行 （ ）次比较。. 3. 10. 15. 25 标准答案：15. 在一棵二叉树上第5层的结点数最多是（ ）. 8. 16. 32. 15 标准答案：16. 以下数据结构中，（ ）是非线性数据结构. 树. 字符串. 队. 栈 标准答案：17. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。. 最大概率. 最小概率. 平均概率. 同等概率 标准答案：18. 一棵二叉树的前序遍历序列为G，它的中序遍历序列可能是（ ）. G. G. G. G 标准答案：19. 一棵二叉树的前序遍历序列为G，它的中序遍历序列可能是（ ）. G. G. G. G 标准答案：20. 若串S=sotwr,其子串的数目是（ ）. 8. 37. 36. 9 标准答案：21. 散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。. 最大概率. 最小概率. 平均概率. 同等概率 标准答案：22. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行（ ）次比较。. 3. 10. 15. 25 标准答案：23. 动态存储管理系统中，通常可有（ ）种不同的分配策略。. 1. 2. 3. 4 标准答案：24. 假设以行序为主序存储二维数组=rry1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LO5，5=（ ）。. 808. 818. 1010. 1020 标准答案：25. 下面叙述正确的是（ ）. 算法的执行效率与数据的存储结构无关. 算法的空间复杂度是指算法程序中指令(或语句)的条数. 算法的有穷性是指算法必须能在执行有限个步骤之后终止. 以上三种描述都不对 标准答案： 二、判断题（共 20 道试题，共 40 分。）1. 集合与线性表的区别在于是否按关键字排序。. 错误. 正确 标准答案：2. 直接选择排序算法在最好情况下的时间复杂度为O（N）。. 错误. 正确 标准答案：3. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。. 错误. 正确 标准答案：4. 链表中的头结点仅起到标识的作用。. 错误. 正确 标准答案：5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）. 错误. 正确 标准答案：6. 对一棵二叉树进行层次遍历时，应借助于一个栈（ ）. 错误. 正确 标准答案：7. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关。. 错误. 正确 标准答案：8. 栈是实现过程和函数等子程序所必需的结构（ ）. 错误. 正确 标准答案：9. 算法的优劣与算法描述语言无关，但与所用计算机有关（ ）. 错误. 正确 标准答案：10. 栈是实现过程和函数等子程序所必需的结构。. 错误. 正确 标准答案：11. 栈和队列都是限制存取点的线性结构。. 错误. 正确 标准答案：12. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. 错误. 正确 标准答案：13. 折半查找法的查找速度一定比顺序查找法快（ ）. 错误. 正确 标准答案：14. 若一个广义表的表头为空表，则此广义表亦为空表。. 错误. 正确 标准答案：15. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。. 错误. 正确 标准答案：16. 线性表的特点是每个元素都有一个前驱和一个后继。. 错误. 正确 标准答案：17. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）. 错误. 正确 标准答案：18. 二维以上的数组其实是一种特殊的广义表。. 错误. 正确 标准答案：19. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。. 错误. 正确 标准答案：20. 完全二叉树一定存在度为1的结点。. 错误. 正确 标准答案： 三、多选题（共 5 道试题，共 10 分。）1. 下面关于线性表的叙述中，正确的是（ ）. 线性表采用顺序存储，必须占用一片连续的存储单元。. 线性表采用顺序存储，便于进行插入和删除操作。. 线性表采用链接存储，不必占用一片连续的存储单元。. 线性表采用链接存储，便于插入和删除操作。 标准答案：2. 下面关于二分查找的叙述不正确的是（ ）. 表必须有序，表可以顺序方式存储，也可以链表方式存储. 表必须有序，而且只能从小到大排列. 表必须有序且表中数据必须是整型，实型或字符型. 表必须有序，且表只能以顺序方式存储 标准答案：3. 下面关于求关键路径的说法正确的是（ ）. 求关键路径是以拓扑排序为基础的. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差. 关键活动一定位于关键路径上 标准答案：4. 下面关于哈希(Hsh)查找的说法不正确的是( ). 哈希函数构造的越复杂越好，因为这样随机性好，冲突小. 除留