首页 › 福建师范大学 › 福师13春《数据结构概论》在线作业一二答案

黄老师 发表于 2013-8-3 07:42:01

福师13春《数据结构概论》在线作业一二答案

福师13春《数据结构概论》在线作业一
试卷总分：100   测试时间：--
一、单选题（共25道试题，共50分。）
1.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
A. p->next=s;s->next=p->next;
B. s->next=p->next;p->next=s;
C. p->next=s;p->next=s->next;
D. p->next=s->next;p->next=s;
满分：2分
2.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A. 5
B. 6
C. 7
D. 8
满分：2分
3.具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
C. 10
D. ll
满分：2分
4.一个算法应该是（ ）
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和C.
满分：2分
5.字符串‘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分
6.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. ADCFEG
满分：2分
7.若串S=’software’,其子串的数目是（ ）
A. 8
B. 37
C. 36
D. 9
满分：2分
8.一个递归算法必须包括（ ）
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
满分：2分
9.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
A. 前序
B. 中序
C. 后序
D. 按层次
满分：2分
10.已知广义表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分
11.要连通具有n个顶点的有向图，至少需要（ ）条边。
A. n-l
B. n
C. n+l
D. 2n
满分：2分
12.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A. 直接插入
B. 直接选择
C. 堆
D. 快速
满分：2分
13.下面的程序段中，对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分
14.下面叙述正确的是（ ）
A. 算法的执行效率与数据的存储结构无关
B. 算法的空间复杂度是指算法程序中指令(或语句)的条数
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 以上三种描述都不对
满分：2分
15.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
C. 匹配
D. 求串长
满分：2分
16.设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
满分：2分
17.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
满分：2分
18.连续存储设计时，存储单元的地址（ ）
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
满分：2分
19.对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
满分：2分
20.求解最短路径的Floyd算法的时间复杂度为（ ）。
A. O（n）
B. O（n+c）
C. O（n*n）
D. O（n*n*n）
满分：2分
21.图中有关路径的定义是（ ）
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
满分：2分
22.下面有关算法说法错误的是（ ）
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
满分：2分
23.设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）
A. 1和1
B. 1和3
C. 1和2
D. 2和3
满分：2分
24.散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
满分：2分
25.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定
满分：2分
二、判断题（共20道试题，共40分。）
1.在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
A. 错误
B. 正确
满分：2分
2.对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
B. 正确
满分：2分
3.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）
A. 错误
B. 正确
满分：2分
4.二叉树是度为2的有序树（ ）
A. 错误
B. 正确
满分：2分
5.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
A. 错误
B. 正确
满分：2分
6.线性表的特点是每个元素都有一个前驱和一个后继（ ）
A. 错误
B. 正确
满分：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.栈与队列是一种特殊操作的线性表（ ）
A. 错误
B. 正确
满分：2分
14.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）
A. 错误
B. 正确
满分：2分
15.栈和队列都是限制存取点的线性结构（ ）
A. 错误
B. 正确
满分：2分
16.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素（ ）
A. 错误
B. 正确
满分：2分
17.循环队列通常用指针来实现队列的头尾相接（ ）
A. 错误
B. 正确
满分：2分
18.线性表只能用顺序存储结构实现（ ）
A. 错误
B. 正确
满分：2分
19.顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）
A. 错误
B. 正确
满分：2分
20.对一棵二叉树进行层次遍历时，应借助于一个栈（ ）
A. 错误
B. 正确
满分：2分
三、多选题（共5道试题，共10分。）
1.以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
B. 线性表
C. 二叉树
D. 栈
满分：2分
2.下面几个符号串编码集合中，是前缀编码的是（ ）
A. {0,10,110,1111}
B. {11,10,001,101,0001}
C. {00,010,0110,1000}
D. {b,c,aa,ac,aba,abb,abc}
满分：2分
3.下面说法正确的是（ ）
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构
D. 广义表可以是一个多层次的结构
满分：2分
4.下述哪些不是顺序存储结构的优点（ ）
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 可方便地用于各种逻辑结构的存储表示
满分：2分
5.以下数据结构中（ ）不是线性结构
福师13春《数据结构概论》在线作业二
试卷总分：100   测试时间：--
一、单选题（共25道试题，共50分。）
1.适用于折半查找的表的存储方式及元素排列要求为（ ）
A. 链接方式存储，元素无序
B. 链接方式存储，元素有序
C. 顺序方式存储，元素无序
D. 顺序方式存储，元素有序
满分：2分
2.假设以行序为主序存储二维数组A=array，设每个数据元素占2个存储单元，基地址为10，则LOC=（ ）
A. 808
B. 818
C. 1010
D. 1020
满分：2分
3.由3 个结点可以构造出多少种不同的二叉树（ ）
A. 2
B. 3
C. 4
D. 5
满分：2分
4.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）Head(Tail(Head(Tail(Tail(A)))))
A. （a）
B. A
C. a
D. (b)
满分：2分
5.具有12个关键字的有序表，折半查找的平均查找长度（ ）
A. 3.1
B. 4
C. 2.5
D. 5
满分：2分
6.一个递归算法必须包括（ ）
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
满分：2分
7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A. 直接插入
B. 直接选择
C. 堆
D. 快速
满分：2分
8.数组A中含有元素的个数（ ）
A. 55
B. 45
C. 36
D. 16
满分：2分
9.链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
满分：2分
10.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A. O（i）
B. O（1）
C. O（n）
D. O（i-1）
满分：2分
11.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）
A. 13
B. 33
C. 18
D. 40
满分：2分
12.连续存储设计时，存储单元的地址（ ）
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
满分：2分
13.下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A. 堆排序
B. 冒泡排序
C. 快速排序
D. 插入排序
满分：2分
14.线索二叉树是一种（ ）构。
A. 逻辑
B. 逻辑和存储
C. 物理
D. 线性
满分：2分
15.在完全二叉树中，若一个结点是叶结点，则它没（ ）
A. 左子结点
B. 右子结点
C. 左子结点和右子结点
D. 左子结点，右子结点和兄弟结点
满分：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.对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
满分：2分
20.算法的计算量的大小称为计算的（ ）
A. 效率
B. 复杂性
C. 现实性
D. 难度
满分：2分
21.已知广义表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分
22.广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）
A. (c,d)
B. c,d
C. ((c,d))
D. d
满分：2分
23.下面的程序段中，对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分
24.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A. 9
B. 11
C. 15
D. 不确定
满分：2分
25.在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
A. O(n)
B. O(n＋e)
C. O(n*n)
D. O(n*n*n)
满分：2分
二、判断题（共20道试题，共40分。）
1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）
A. 错误
B. 正确
满分：2分
2.二维以上的数组其实是一种特殊的广义表（ ）
A. 错误
B. 正确
满分：2分
3.循环队列也存在空间溢出问题（ ）
A. 错误
B. 正确
满分：2分
4.在待排数据基本有序的情况下，快速排序效果最好（ ）
A. 错误
B. 正确
满分：2分
5.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素（ ）
A. 错误
B. 正确
满分：2分
6.对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
B. 正确
满分：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.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）
A. 错误
B. 正确
满分：2分
14.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。
A. 错误
B. 正确
满分：2分
15.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）
A. 错误
B. 正确
满分：2分
16.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）
A. 错误
B. 正确
满分：2分
17.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）
A. 错误
B. 正确
满分：2分
18.算法的优劣与算法描述语言无关，但与所用计算机有关（ ）
A. 错误
B. 正确
满分：2分
19.通常使用队列来处理函数或过程的调用（ ）
A. 错误
B. 正确
满分：2分
20.二叉树是度为2的有序树（ ）
A. 错误
B. 正确
满分：2分
三、多选题（共5道试题，共10分。）
1.下面关于线性表的叙述中，正确的是（ ）
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
B. 线性表采用顺序存储，便于进行插入和删除操作。
C. 线性表采用链接存储，不必占用一片连续的存储单元。
D. 线性表采用链接存储，便于插入和删除操作。
满分：2分
2.下面关于二分查找的叙述不正确的是（ ）
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
满分：2分
3.下列说法正确的是（ ）
A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B. 图的深度遍历不适用于有向图
C. 遍历的基本算法有两种：深度遍历和广度遍历
D. 图的深度遍历是一个递归过程
满分：2分
4.下面关于哈希(Hash)查找的说法不正确的是（ ）
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
满分：2分
5.以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
B. 线性表
C. 二叉树
D. 栈
满分：2分

查看完整版本: 福师13春《数据结构概论》在线作业一二答案