2015福师《数据结构概论》在线作业一90分

1、窗体顶端一、单选题（共25道试题，共50分。）V 1.已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ ）。 A. head（tail（tail（L）B. tail（head（head（tail（L）C. head（tail（head（tail（L）D. head（tail(head（tail（tail（L）)）满分：2分2.下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序B. 快速排序C. 希尔排序D. 堆排序满分：2分3.由3 个结点可以构造出多少种不同的二叉树（ ） A. 2B. 3C. 4D. 5满分：2分4.具有12个关键字的有序表，折半查

2、找的平均查找长度（ ） A. 3.1B. 4C. 2.5D. 5满分：2分5.数组A0.4,-1.-3,5.7中含有元素的个数（ ）。 A. 55B. 45C. 36D. 16满分：2分6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ） A. 13B. 33C. 18D. 40满分：2分7.树的后根遍历序列等同于该树对应的二叉树的（ ） A. 先序序列B. 中序序列C. 后序序列D. 都不正确满分：2分8.下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1

3、TO n DO x:=x+1; A. O(2n)B. O(n)C. O(n2)D. O(log2n)满分：2分9.对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ） A. (2,5,12,16)26(60,32,72)B. (5,16,2,12)28(60,32,72)C. (2,16,12,5)28(60,32,72)D. (5,16,2,12)28(32,60,72)满分：2分10.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。 A. 插入B. 选择C. 希尔D. 二路

4、归并满分：2分11.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1=i=n+1)。 A. O(0)B. O(1)C. O(n)D. O(n2)满分：2分12.广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ ）。 Head(Tail(Head(Tail(Tail(A) A. （a）B. AC. aD. d满分：2分13.要连通具有n个顶点的有向图，至少需要（ ）条边。 A. n-lB. nC. n+lD. 2n满分：2分14.字符串ababaabab 的nextval 为（ ） A. (0,1,0,1,04,1,0,1)B. (

5、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分15.已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ ） A. head（tail（tail（L）B. tail（head（head（tail（L）C. head（tail（head（tail（L）D. head（tail(head（tail（tail（L）)）满分：2分16.具有10个叶结点的二叉树中有（ ）个度为2的结点， A. 8B. 9C. 10D. ll满分：2分17.具有10个叶结点的二叉树中有（ ）个度为2的结点

6、， A. 8B. 9C. 10D. ll满分：2分18.对于栈操作数据的原则是（ ） A. 先进先出B. 后进先出C. 后进后出D. 不分顺序满分：2分19.就平均性能而言，目前最好的内排序方法是( )排序法。 A. 冒泡B. 希尔插入C. 交换D. 快速满分：2分20.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ） A. CABDEFGB. ABCDEFGC. DACEFBGD. ADCFEG满分：2分21.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ） A. m-nB. m-n-1C. n+1D. 条件

7、不足，无法确定满分：2分22.有n个叶子的哈夫曼树的结点总数为（ ）。 A. 不确定B. 2nC. 2n+1D. 2n-1满分：2分23.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=frontB. rear=frontC. rear+1=frontD. (rear-l) MOD n=front满分：2分24.在下面的排序方法中，辅助空间为O（n）的是（ ） A. 希尔排序B. 堆排序C. 选择排序D. 归并排序满分：2分25.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。 A. 直接插入

8、B. 直接选择C. 堆D. 快速满分：2分窗体底端窗体顶端二、判断题（共20道试题，共40分。）V 1.数据结构的抽象操作的定义与具体实现有关。 A. 错误B. 正确满分：2分2.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ） A. 错误B. 正确满分：2分3.顺序查找法适用于存储结构为顺序或链接存储的线性表。 A. 错误B. 正确满分：2分4.折半查找法的查找速度一定比顺序查找法快（ ） A. 错误B. 正确满分：2分5.顺序存储结构的主要缺点是不利于插入或删除操作（ ） A. 错误B. 正确满分：2分6.线性表的特点是每个元素都有一个前驱和一个后继（ ） A. 错误B. 正确满分

9、：2分7.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。 A. 错误B. 正确满分：2分8.对一棵二叉树进行层次遍历时，应借助于一个栈 A. 错误B. 正确满分：2分9.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 A. 错误B. 正确满分：2分10.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。 A. 错误B. 正确满分：2分11.若一个广义表的表头为空表，则此广义表亦为空表（ ） A. 错误B. 正确满分：2分12.循环链表不是线性表（ ） A. 错误B. 正确满分：2分13.数据的逻辑结构说明

10、数据元素之间的顺序关系,它依赖于计算机的储存结构. A. 错误B. 正确满分：2分14.在顺序存储结构中，有时也存储数据结构中元素之间的关系。 A. 错误B. 正确满分：2分15.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 A. 错误B. 正确满分：2分16.二维以上的数组其实是一种特殊的广义表。 A. 错误B. 正确满分：2分17.二叉树是度为2的有序树 A. 错误B. 正确满分：2分18.查找相同结点的效率折半查找总比顺序查找高 A. 错误B. 正确满分：2分19.循环队列也存在空间溢出问题。 A. 错误B. 正确满分：2分20.循环链表不是线性表. A. 错误B.

11、正确满分：2分窗体底端窗体顶端三、多选题（共5道试题，共10分。）V 1.下列关于m阶B-树的说法正确的是( ) A. 根结点至多有m棵子树B. 所有叶子都在同一层次上C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树D. 根结点中的数据是有序的满分：2分2.下面说法正确的是( )。 A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构满分：2分3.下面关于串的的叙述中，正确的是（ ） A. 串是字符的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储满分：2分4.某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是