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

《16秋福建师范大学《数据结构概论》在线作业二》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、单选题（共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（ti

2、l（L）））)）标准答案：4.下面的程序段中，对x的赋值语句的频度为（）ORi:=1TOnOORj:=1TOnOx:=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.一个算法应该

3、是（）。.程序.问题求解步骤的描述.要满足五个基本特性.和.标准答案：9.在完全二叉树中，若一个结点是叶结点，则它没（）.左子结点.右子结点.左子结点和右子结点.左子结点，右子结点和兄弟结点标准答案：10.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）.543612.453126.346521.234156标准答案：11.从逻辑上可以把数据结构分为（）两大类。.动态结构、静态结构.顺序结构、链式结构.线性结构、非线性结构.初等结构、构造型结构标准答案：12.有六个元

4、素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列（）.543612.453126.346521.234156标准答案：13.树的后根遍历序列等同于该树对应的二叉树的（）.先序序列.中序序列.后序序列.都不正确标准答案：14.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。.3.10.15.25标准答案：15.在一棵二叉树上第5层的结点数最多是（）.8.16.32.15标准答案：16.以下数据结构中，（）是非线性数据结构.树.字符串.队.栈

5、标准答案：17.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。.最大概率.最小概率.平均概率.同等概率标准答案：18.一棵二叉树的前序遍历序列为G，它的中序遍历序列可能是（）.G.G.G.G标准答案：19.一棵二叉树的前序遍历序列为G，它的中序遍历序列可能是（）.G.G.G.G标准答案：20.若串S=’sotwr’,其子串的数目是（）.8.37.36.9标准答案：21.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。.最大概率.最小概率.平均概率.同等概率标准答案：22

6、.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。.3.10.15.25标准答案：23.动态存储管理系统中，通常可有（）种不同的分配策略。.1.2.3.4标准答案：24.假设以行序为主序存储二维数组=rry[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LO[5，5]=（）。.808.818.1010.1020标准答案：25.下面叙述正确的是（）.算法的执行效率与数据的存储结构无关.算法的空间复杂度是指算法程序中指令(或语句)

7、的条数.算法的有穷性是指算法必须能在执行有限个步骤之后终止.以上三种描述都不对标准答案：二、判断题（共20道试题，共40分。）1.集合与线性表的区别在于是否按关键字排序。.错误.正确标准答案：2.直接选择排序算法在最好情况下的时间复杂度为O（N）。.错误.正确标准答案：3.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。.错误.正确标准答案：4.链表中的头结点仅起到标识的作用。.错误.正确标准答案：5.在顺序存储结构中，有时也存储数据结构中元素之间的关系（）.错误.正确标准答案：6.对一棵二叉树

8、进行层次遍历时，应借助于一个栈（）.错误.正确标准答案：7.两分法插入排序所需比较次数与待排序记录的初始排列状态相关。.错误.正确标准答案：8.栈是实现过程和函数等子程序所必需的结构（）.错误.正确标准答案：9.算法的优劣与算法描述语言无关，但与所用计算机有关（）.错误.正确标准答案：10.栈是实现过程和函数等子程序所必需的结构。.错误.正确标准答案：11.栈和队列都是限制存取点的线性结构。.错误.正确标准答案：12.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于