福师17秋《数据结构概论》在线作业12参考
福师《数据结构概论》在线作业一一、单选题:【25道,总分:50分】
1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )(1<=i<=n+1)。 (满分:2)
A. O(0) B. O(1)
C. O(n) D. O(n^2)
2.算法的时间复杂度是由( )决定的。 (满分:2)
A. 问题的规模
B. 待处理数据的初态
C. A和B
D. 变量个数
3.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) (满分:2)
A. （N+1）/2
B. N/2
C. N
D. [（1+N）*N ]/2
4.栈在( )中应用。 (满分:2)
A. 递归调用
B. 子程序调用
C. 表达式求值
D. A，Ｂ，Ｃ
5.下列排序算法中，( )算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 (满分:2)
A. 堆排序
B. 冒泡排序
C. 快速排序
D. 插入排序
6.对于栈操作数据的原则是( ) (满分:2)
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
7.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( ) (满分:2)
A. head==NULL
B. head→next==NULL
C. head→next==head
D. head!=NULL
8.若要求尽可能快地对序列进行稳定的排序，则应选( ) (满分:2)
A. 快速排序
B. 归并排序
C. 冒泡排序
D. 堆
9.栈和队都是( ) (满分:2)
A. 顺序存储的
B. 线性结构
C. 链式存储的
D. 非线性结构
10.求解最短路径的Floyd算法的时间复杂度为( )。 (满分:2)
A. O（n）
B. O（n+c）
C. O（n*n）
D. O（n*n*n）
11.假设以行序为主序存储二维数组A=array，设每个数据元素占2个存储单元，基地址为10，则LOC=( )。 (满分:2)
A. 808
B. 818
C. 1010
D. 1020
12.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( ) (满分:2)
A. 9
B. 11
C. 15
D. 不确定
13.线索二叉树是一种( )构。 (满分:2)
A. 逻辑
B. 逻辑和存储
C. 物理
D. 线性
14.栈在( )中应用。 (满分:2)
A. 递归调用
B. 子程序调用
C. 表达式求值
D. A，Ｂ，Ｃ
15.下面有关算法说法错误的是( ) (满分:2)
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
16.线性表是具有n个( )的有限序列。 (满分:2)
A. 表元素
B. 字符
C. 数据元素
D. 数据项
17.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( ) (满分:2)
A.(rear+1) MOD n=front
B. rear=front
C. rear+1=front
D.(rear-l) MOD n=front
18.具有12个关键字的有序表，折半查找的平均查找长度( ) (满分:2)
A. 3.1
B. 4
C. 2.5
D. 5
19.计算机算法指的是( ) (满分:2)
A. 计算方法
B. 排序方法
C. 解决问题的有限运算序列
D. 调度方法
20.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 ( )次比较。 (满分:2)
A. 3
B. 10
C. 15
D. 25
21.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。 (满分:2)
A. O(n)O(n)
B. O(n)O(1)
C. O(1)O(n)
D. O(1) O(1)
22.研究数据结构就是研究( )。 (满分:2)
A. 数据的逻辑结构、存储结构及其基本操作
B. 数据的逻辑结构和存储结构
C. 数据的存储结构
D. 数据的逻辑结构
23.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( ) (满分:2)
A. 9
B. 11
C. 15
D. 不确定
24.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( ) (满分:2)
A. 13
B. 33
C. 18
D. 40
25.图中有关路径的定义是( )。 (满分:2)
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
二、判断题:【20道,总分:40分】
1.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 (满分:2)
A. 错误
B. 正确
2.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）( ) (满分:2)
A. 错误
B. 正确
3.栈是实现过程和函数等子程序所必需的结构。 (满分:2)
A. 错误
B. 正确
4.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大 (满分:2)
A. 错误
B. 正确
5.顺序存储方式只能用于存储线性结构( ) (满分:2)
A. 错误
B. 正确
6.数据元素是数据的最小单位。 (满分:2)
A. 错误
B. 正确
7.二叉树的遍历结果不是唯一的. (满分:2)
A. 错误
B. 正确
8.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好( ) (满分:2)
A. 错误
B. 正确
9.在待排数据基本有序的情况下，快速排序效果最好。 (满分:2)
A. 错误
B. 正确
10.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (满分:2)
A. 错误
B. 正确
11.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 (满分:2)
A. 错误
B. 正确
12.直接选择排序算法在最好情况下的时间复杂度为O（N）。 (满分:2)
A. 错误
B. 正确
13.若一个广义表的表头为空表，则此广义表亦为空表。 (满分:2)
A. 错误
B. 正确
14.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的( ) (满分:2)
A. 错误
B. 正确
15.循环队列也存在空间溢出问题。 (满分:2)
A. 错误
B. 正确
16.内排序要求数据一定要以顺序方式存储。 (满分:2)
A. 错误
B. 正确
17.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 (满分:2)
A. 错误
B. 正确
18.若一个广义表的表头为空表，则此广义表亦为空表( ) (满分:2)
A. 错误
B. 正确
19.队列和栈都是运算受限的线性表，只允许在表的两端进行运算。 (满分:2)
A. 错误
B. 正确
20.二维以上的数组其实是一种特殊的广义表( ) (满分:2)
A. 错误
B. 正确
三、多选题:【5道,总分:10分】
1.下面关于串的的叙述中，正确的是？( ) (满分:2)
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
2.下列哪种图的邻接矩阵不是对称矩阵？( ) (满分:2)
A. 有向图
B. 无向图
C. AOV网
D. AOE网
3.下面关于二分查找的叙述不正确的是( ) (满分:2)
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
4.下面几个符号串编码集合中，是前缀编码的是( ) (满分: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}
5.下列关于m阶B-树的说法正确的是( ) (满分:2)
A. 根结点至多有m棵子树
B. 所有叶子都在同一层次上
C. 非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树
D. 根结点中的数据是有序的
福师《数据结构概论》在线作业二
一、单选题:【25道,总分:50分】
1.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是( ) (满分:2)
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆积排序法
2.数组A中含有元素的个数( ) (满分:2)
A. 55
B. 45
C. 36
D. 16
3.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序 (满分:2)
A. 冒泡
B. 希尔
C. 快速
D. 堆
4.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 (满分:2)
A. 分快查找
B. 顺序查找
C. 折半查找
D. 基于属性
5.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是( ) (满分:2)
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定
6.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是( )排序。 (满分:2)
A. 选择
B. 快速
C. 希尔
D. 冒泡
7.若串S=’software’,其子串的数目是( ) (满分:2)
A. 8
B. 37
C. 36
D. 9
8.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ) (满分:2)
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆积排序法
9.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( ) (满分:2)
A. head==NULL
B. head→next==NULL
C. head→next==head
D. head!=NULL
10.具有12个关键字的有序表，折半查找的平均查找长度( ) (满分:2)
A. 3.1
B. 4
C. 2.5
D. 5
11.已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是( )。 (满分:2)
A. head（tail（tail（L）））
B. tail（head（head（tail（L））））
C. head（tail（head（tail（L））））
D. head（tail(head（tail（tail（L）））)）
12.对于栈操作数据的原则是( ) (满分:2)
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
13.关键路径是事件结点网络中( ) (满分:2)
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长回路
D. 最短回路
14.散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。 (满分:2)
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
15.假设以行序为主序存储二维数组A=array，设每个数据元素占2个存储单元，基地址为10，则LOC=( )。 (满分:2)
A. 808
B. 818
C. 1010
D. 1020
16.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( )。 (满分:2)
A. 13
B. 33
C. 18
D. 40
17.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是( ) (满分:2)
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;
18.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？( ) (满分:2)
A. 5 4 3 6 1 2
B. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
19.在下列存储形式中，哪一个不是树的存储形式( ) (满分:2)
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
20.设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳。 (满分:2)
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
21.一个算法应该是( ) (满分:2)
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和C.
22.具有10个叶结点的二叉树中有( )个度为2的结点， (满分:2)
A. 8
B. 9
C. 10
D. ll
23.若串S=’software’,其子串的数目是( )。 (满分:2)
A. 8
B. 37
C. 36
D. 9
24.数组A中含有元素的个数( )。 (满分:2)
A. 55
B. 45
C. 36
D. 16
25.设广义表L=（（a,b,c）），则L的长度和深度分别为( ) (满分:2)
A. 1和1
B. 1和3
C. 1和2
D. 2和3
二、判断题:【20道,总分:40分】
1.二叉树是度为2的有序树 (满分:2)
A. 错误
B. 正确
2.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表( ) (满分:2)
A. 错误
B. 正确
3.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的( ) (满分:2)
A. 错误
B. 正确
4.用树的前序遍历和中序遍历可以导出树的后序遍历( ) (满分:2)
A. 错误
B. 正确
5.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大 (满分:2)
A. 错误
B. 正确
6.栈与队列是一种特殊操作的线性表( ) (满分:2)
A. 错误
B. 正确
7.队列和栈都是运算受限的线性表，只允许在表的两端进行运算。 (满分:2)
A. 错误
B. 正确
8.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。 (满分:2)
A. 错误
B. 正确
9.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间. (满分:2)
A. 错误
B. 正确
10.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面( ) (满分:2)
A. 错误
B. 正确
11.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 (满分:2)
A. 错误
B. 正确
12.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省( )。 (满分:2)
A. 错误
B. 正确
13.顺序存储方式只能用于存储线性结构。 (满分:2)
A. 错误
B. 正确
14.顺序存储结构的主要缺点是不利于插入或删除操作( ) (满分:2)
A. 错误
B. 正确
15.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值( ) (满分:2)
A. 错误
B. 正确
16.链表中的头结点仅起到标识的作用。 (满分:2)
A. 错误
B. 正确
17.数据元素是数据的最小单位。 (满分:2)
A. 错误
B. 正确
18.折半查找法的查找速度一定比顺序查找法快( ) (满分:2)
A. 错误
B. 正确
19.二维以上的数组其实是一种特殊的广义表( ) (满分:2)
A. 错误
B. 正确
20.队列和栈都是运算受限的线性表，只允许在表的两端进行运算( )。 (满分:2)
A. 错误
B. 正确
三、多选题:【5道,总分:10分】
1.下面关于二分查找的叙述不正确的是 ( ) (满分:2)
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
2.下面关于线性表的叙述中，正确的是？( ) (满分:2)
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
B. 线性表采用顺序存储，便于进行插入和删除操作。
C. 线性表采用链接存储，不必占用一片连续的存储单元。
D. 线性表采用链接存储，便于插入和删除操作。
3.下面几个符号串编码集合中，是前缀编码的是( ) (满分: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}
4.以下数据结构中，哪些不是线性结构( ) (满分:2)
A. 广义表
B. 二叉树
C. 稀疏矩阵
D. 串
5.下面关于求关键路径的说法正确的是( ) (满分:2)
A. 求关键路径是以拓扑排序为基础的
B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上
页:
[1]