大工17秋《数据结构》在线作业123资料
大工17秋《数据结构》在线作业1一、单选题：
1.下面关于串的概念的叙述中错误的是()。 (满分:5)
A.串是字符的有限序列
B.串既可以采用顺序存储，也可以采用链式存储
C.空串是由空格构成的串
D.模式匹配是串的一种重要运算
正确答案:——C——
2.一个有n个结点的有序单链表中,删除一个结点并仍然使链表有序的时间复杂度是()。 (满分:5)
A.O(1)
B.O(n)
C.O(n^2)
D.O(nlog2n)
正确答案:——B——
3.序列{a,b,c,d}顺序进栈,其出栈的顺序不可能为()。 (满分:5)
A.dcba
B.cdab
C.adcb
D.abcd
正确答案:——B——
4.以下四种数据结构中()不是线性结构。 (满分:5)
A.队列
B.线性表
C.栈
D.二叉树
正确答案:————
5.最适合用做链式队列的链表是()。 (满分:5)
A.带队首指针和队尾指针的循环单链表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的非循环单链表
D.只带队首指针的循环单链表
正确答案:————
6.栈的插入与删除操作均在( )进行。 (满分:5)
A.栈底
B.栈顶
C.任意位置
D.指定位置
正确答案:————
7.线性表在()情况下最适合采用链表表示。 (满分:5)
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素的个数不变
D.表中元素需要占据一片连续的存储空间
正确答案:————
8.以下算法的时间复杂度为（）：for(i=0;i<n;i++){for(j=1,sum=a;j<=i;j++){sum+=a;}cout<<\\\sum for subarray 0 through\\\<<i<<\\\is\\\<<sum<<endl;} (满分:5)
A.O(1)
B.O(n)
C.O(n^2)
D.O(n^3)
正确答案:————
9.线性表采用链式存储结构时,其地址()。 (满分:5)
A.必须是连续的
B.一定是不连续的
C.连续或不连续都可以
D.部分地址必须是连续的
正确答案:————
10.栈是一种具有()特性的线性表。 (满分:5)
A.后进先出
B.先进先出
C.后进后出
D.不分顺序
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
正确答案:————
三、判断题：
11.若顺序表中第一个元素的存储地址是100,每个元素长度为2,则第5个元素的地址是110。 (满分:5)
正确答案:————
12.取线性表第k个元素的时间代价同k的大小无关。 (满分:5)
正确答案:————
13.栈结构是一种限定只能在一端进行插入,在另一端进行删除的线性表。 (满分:5)
正确答案:————
14.线性表的每个元素都必须有一个前驱和一个后继。 (满分:5)
正确答案:————
15.串的长度是指串中所含字符的个数 (满分:5)
正确答案:————
16.顺序存储的线性表不可以进行随机存取操作。 (满分:5)
正确答案:————
17.在队列的任意位置均可以实现插入元素操作。 (满分:5)
正确答案:————
18.线性表的链式存储结构使用任意位置的一组存储单元来存储线性表中数据元素。 (满分:5)
正确答案:————
19.分配给单链表的物理内存单元地址必须保证是连续的。 (满分:5)
正确答案:————
20.顺序表中逻辑上相邻的元素,其存储结构中的物理位置不一定紧邻。 (满分:5)
正确答案:————
大工17秋《数据结构》在线作业2
一、单选题：
1.某二叉树的后序遍历序列为dabec,中序遍历序列为debac,则先序遍历的序列为()。 (满分:5)
A.cbeda
B.decab
C.deabc
D.cedba
正确答案:——D——
2.()能够判断出一个有向图中是否存在环(回路)。 (满分:5)
A.求关键路径
B.拓扑排序
C.求最短路径
D.以上均不可
正确答案:——B——
3.3个结点的二叉树有()种可能的不同形态。 (满分:5)
A.3
B.4
C.5
D.6
正确答案:——C——
4.有k个结点的完全二叉树的深度是()。 (满分:5)
A.log2k
B.log2k +1
C.log2(2k)
D.log2k -1
正确答案:————
5.深度为k的完全二叉树中,叶子结点只能出现在第()层上。 (满分:5)
A.k-1
B.1
C.k
D.k-1或k
正确答案:————
6.某二叉树的先序遍历序列为abdgcefh,中序遍历的序列为dgbaechf,则后序遍历的序列为()。 (满分:5)
A.gdbehfca
B.bdgaechf
C.gdbecfha
D.gcefhabd
正确答案:————
7.哈夫曼树的带权路径长度WPL为()。 (满分:5)
A.除根结点之外的所有结点权值之和
B.所有结点权值之和
C.根结点的值
D.各叶子结点的带权路径长度之和
正确答案:————
8.任一二叉树的叶结点分别在先序、中序、后序三种遍历序列中的相对次序()。 (满分:5)
A.发生改变
B.不发生改变
C.不能确定
D.以上都不对
正确答案:————
9.一棵完全二叉树上有1001个结点,其中叶子结点的个数为()。 (满分:5)
A.251
B.254
C.501
D.505
正确答案:————
10.有8个结点的无向图,至少需要有()条边才能确保是这一个连通图。 (满分:5)
A.5
B.6
C.7
D.8
T.对
F.错
正确答案:————
三、判断题：
11.如果二叉树的树根为第1层,则第6层上的结点数最多为32。 (满分:5)
A.对
B.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
正确答案:————
12.中缀表达式A+(B+C/D)*E的后缀形式是ABCD/+E*+。 (满分:5)
正确答案:————
13.入栈和出栈操作的时间复杂度均为O(1)。 (满分:5)
正确答案:————
14.有m个结点的二叉排序树有多种,树高最小的一棵是最佳的。 (满分:5)
正确答案:————
15.在单链表中取某个元素时,只要知道该元素的指针即可,因此可以说单链表是随机存取的存储结构。 (满分:5)
正确答案:————
16.用顺序表表示的循环队列可以用标志位来表示队空或队满的条件。 (满分:5)
正确答案:————
17.一棵二叉树可以通过前序和后序遍历序列来恢复该二叉树。 (满分:5)
正确答案:————
18.二叉树的左右子树次序不允许任意改变。 (满分:5)
正确答案:————
19.二叉树中必有度为2的结点。 (满分:5)
正确答案:————
20.哈夫曼树是带权路径长度最短的树,权值较大的结点离根结点较近。 (满分:5)
正确答案:————
大工17秋《数据结构》在线作业3
一、单选题：
1.设一组初始记录序列为(5,2,6,3,9),以5为基准进行一趟快速排序的结果为()。 (满分:5)
A.2，3，5，9，6
B.3，2，5，6，9
C.3，2，5，9，6
D.2，3，6，5，9
正确答案:——B——
2.有序表(12,17,24,35,47,50,62)中,利用二分法查找到24需要经过()次比较。 (满分:5)
A.1
B.2
C.3
D.4
正确答案:——C——
3.在800个无序的元素用最快的速度挑选出其中前8个最大的元素,最好选用()排序法。 (满分:5)
A.冒泡排序
B.快速排序
C.基数排序
D.堆排序
正确答案:——D——
4.在具有n个结点的线性表中,使用顺序查找法找到一个结点的时间复杂度为()。 (满分:5)
A.O(log2n^2)
B.O(nlog2n)
C.O(n)
D.O(log2n)
正确答案:————
5.n个顶点和e条边的有向图进行拓扑排序,总计算时间为()。 (满分:5)
A.O (nlog2e)
B.O (n+e)
C.O (en )
D.O ( elog2n)
正确答案:————
6.以下各种排序方法中,辅助空间为O(n)的是()。 (满分:5)
A.堆排序
B.希尔排序
C.归并排序
D.快速排序
正确答案:————
7.n个顶点e条边的无向图对应的邻接表中的表头结点和表结点的个数分别为()。 (满分:5)
A.n和2e
B.2n和e
C.e和n
D.n和e
正确答案:————
8.最短路径的生成过程可以采用()算法。 (满分:5)
A.普里姆
B.迪杰斯特拉
C.克鲁斯卡尔
D.哈夫曼
正确答案:————
9.以下四类排序方法中()排序法是不稳定性排序法。 (满分:5)
A.插入
B.冒泡
C.快速
D.二路归并
正确答案:————
10.线性表中采用折半查找法查找元素,该线性表应该有()特点。 (满分:5)
A.元素按值有序并采用链式存储结构
B.元素按值有序并采用顺序存储结构
C.采用顺序存储结构
D.元素按值有序
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
T.对
F.错
正确答案:————
三、判断题：
11.有向图的邻接表中存在m个表头结点和n个表结点,则该图中有n条有向边。 (满分:5)
正确答案:————
12.强连通图各顶点间不一定保证全部可达。 (满分:5)
正确答案:————
13.m阶B树的每个结点的子树个数必然不大于m。 (满分:5)
正确答案:————
14.在记录按关键字有序时,快速排序的时间复杂度为O(n)。 (满分:5)
正确答案:————
15.基数排序是一种稳定的排序方法。 (满分:5)
正确答案:————
16.哈希存储方式中的负载因子值越大,存取元素时发生冲突的可能性就越小。 (满分:5)
正确答案:————
17.对k个数据进行第一趟冒泡排序需要比较k-1对元素。 (满分:5)
正确答案:————
18.哈希存储结构是由关键码的值决定数据存储地址。 (满分:5)
正确答案:————
19.从一个图的某个结点进行一次深度或广度优先遍历一定能够访问到该图的每个顶点。 (满分:5)
正确答案:————
20.对于一个基本有序的元素序列,采用插入排序效率最高。 (满分:5)
正确答案:————
页:
[1]