2015福师《数据结构概论》在线作业二92分.doc

窗体顶端 一、单选题（共?25?道试题，共?50?分。） V 1.??字符串‘ababaabab’ 的nextval 为（ ） A. (0,1,0,1,04,1,0,1) B. (0,1,0,1,0,2,1,0,1) C. (0,1,0,1,0,0,0,1,1) D. (0,1,0,1,0,1,0,1,1 ) ??????满分：2??分 2.??下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 ??????满分：2??分 3.??连续存储设计时，存储单元的地址（ ）。 A. 一定连续 B. 一定不连续 C. 不一定连续 D. 部分连续，部分不连续 ??????满分：2??分 4.??动态存储管理系统中，通常可有（ ）种不同的分配策略。 A. 1 B. 2 C. 3 D. 4 ??????满分：2??分 5.??若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A. 9 B. 11 C. 15 D. 不确定 ??????满分：2??分 6.??线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A. O（i） B. O（1） C. O（n） D. O（i-1） ??????满分：2??分 7.??下面给出的四种排序法中（ ）排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆 ??????满分：2??分 8.??求解最短路径的Floyd算法的时间复杂度为( )。 A. O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） ??????满分：2??分 9.??广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 Head(Tail(Head(Tail(Tail(A))))) A. （a） B. A C. a D. d ??????满分：2??分 10.??广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。 A. a B. （） C. （a,b,c,d） D. （b,c,d） ??????满分：2??分 11.??设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ） A. 求子串 B. 联接 C. 匹配 D. 求串长 ??????满分：2??分 12.??一个算法应该是（ ）。 A. 程序 B. 问题求解步骤的描述 C. 要满足五个基本特性 D. A和C. ??????满分：2??分 13.??栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 E. 限制存取点的线性结构 F. 限制存取点的非线性结构 ??????满分：2??分 14.??图中有关路径的定义是（ ） A. 由顶点和相邻顶点序偶构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是 ??????满分：2??分 15.??下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1; A. O(2n) B. O(n) C. O(n2) D. O(log2n) ??????满分：2??分 16.??串的长度是指（ ） A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 ??????满分：2??分 17.??设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A. 5 B. 6 C. 7 D. 8 ??????满分：2??分 18.??就平均性能而言，目前最好的内部排序方法是（ ）排序法。 A. 冒泡 B. 希尔插入 C. 交换 D. 快速 ??????满分：2??分 19.??在一棵二叉树上第5层的结点数最多是（ ） A. 8 B. 16 C. 32 D. 15 ??????满分：2??分 20.??散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 ??????满分：2??分 21.??树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 D. 都不正确 ??????满分：2??分 22.??下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ) A. 选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法 ??????满分：