大工2017春《数据结构》在线作业满分答案
大工17春《数据结构》在线作业1一、单选题：
1.具有n个结点的有序单链表中删除一个结点并仍然有序的时间复杂度是( )。 (满分:5)
A. O(1)
B. O(n)
C. O(n^2)
D. O(nlog2n)
2.以下数据结构中哪个不是线性结构？( ) (满分:5)
A. 队列
B. 线性表
C. 栈
D. 二叉树
3.栈的插入和删除操作在( )进行。 (满分:5)
A. 栈底
B. 栈顶
C. 任意位置
D. 指定位置
4.采用链式存储结构的线性表要求内存中可用存储单元的地址( )。 (满分:5)
A. 必须是连续的
B. 一定是不连续的
C. 连续或不连续都可以
D. 部分地址必须是连续的
5.以下关于串的叙述中错误的是( )。 (满分:5)
A. 串是字符的有限序列
B. 串既可以采用顺序存储，也可以采用链式存储
C. 空串是由空格构成的串
D. 模式匹配是串的一种重要运算
6.在一个链队列中，若f, r分别为队首和队尾指针，则插入p所指向的结点操作为( )。 (满分:5)
A. p->next=f;f=p;
B. p->next=r;r=p;
C. r->next=p;r=p;
D. f->next=r;f=p;
7.栈操作数据的原则是( )。 (满分:5)
A. 后进先出
B. 先进先出
C. 后进后出
D. 不分顺序
8.线性表在哪种情况下最适合采用链表表示？( ) (满分:5)
A. 经常需要随机地存取元素
B. 经常需要进行插入和删除操作
C. 表中元素的个数不变
D. 表中元素需要占据一片连续的存储空间
9.设赋值语句的时间是单位时间，则以下算法的时间复杂度为( )：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)
10.进栈顺序为{a,b,c,d}的序列，其出栈顺序不可能为( )。 (满分:5)
A. dcba
B. cdab
C. adcb
D. abcd
三、判断题：
1.线性表的每个元素都有一个前驱和一个后继。 (满分:5)
A. 错误
B. 正确
2.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上一定相邻。 (满分:5)
A. 错误
B. 正确
3.顺序表中逻辑上相邻的元素，其物理位置不一定紧邻。 (满分:5)
A. 错误
B. 正确
4.取线性表第m个元素的时间代价同m的大小有关。 (满分:5)
A. 错误
B. 正确
5.栈结构限定只能在一端进行插入，在另一端进行删除的线性表。 (满分:5)
A. 错误
B. 正确
6.顺序存储的线性表可以进行随机存取。 (满分:5)
A. 错误
B. 正确
7.KMP算法特点是在模式匹配时指示主串的指针不会变小。 (满分:5)
A. 错误
B. 正确
8.若顺序表中第一个元素的存储地址是100，每个元素长度为2，则第5个元素的地址是108。 (满分:5)
A. 错误
B. 正确
9.线性表的链式存储结构使用一组任意的存储单元来存储线性表中数据元素。 (满分:5)
A. 错误
B. 正确
10.在队列的任意位置均可以插入元素。 (满分:5)
A. 错误
B. 正确
大工17春《数据结构》在线作业2
一、单选题：
1.( )可以判断出一个有向图中是否有环（回路）。 (满分:5)
A. 求关键路径
B. 拓扑排序
C. 求最短路径
D. 以上均不可
2.Huffman树的带权路径长度WPL为( )。 (满分:5)
A. 除根结点之外的所有结点权值之和
B. 所有结点权值之和
C. 根结点的值
D. 各叶子结点的带权路径长度之和
3.一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为( )。 (满分:5)
A. cbeda
B. decab
C. deabc
D. cedba
4.有3个结点的二叉树可能有( )种不同的形态。 (满分:5)
A. 3
B. 4
C. 5
D. 6
5.有8个结点的无向图，至少应有( )条边才能确保是一个连通图。 (满分:5)
A. 5
B. 6
C. 7
D. 8
6.任何一棵二叉树的叶结点分别在先序、中序、后序遍历序列中的相对次序( )。 (满分:5)
A. 发生改变
B. 不发生改变
C. 不能确定
D. 以上都不对
7.深度为k的完全二叉树，叶子结点一定出现在第( )层上。 (满分:5)
A. k-1
B. 1
C. k
D. k-1或k
8.一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为( )。 (满分:5)
A. gdbehfca
B. bdgaechf
C. gdbecfha
D. gcefhabd
9.一棵完全二叉树上有1001个结点，其中叶子结点的个数为( )。 (满分:5)
A. 250
B. 254
C. 501
D. 505
10.有N个结点的完全二叉树的深度是( )。 (满分:5)
A. log2N
B. log2N +1
C. log2(2N)
D. log2N -1
三、判断题：
1.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根结点较近。 (满分:5)
A. 错误
B. 正确
2.若已知一棵二叉树的前序和后序遍历序列，可以恢复该二叉树。 (满分:5)
A. 错误
B. 正确
3.如果树根为第1层，在一棵二叉树上第6层的结点数最多为32。 (满分:5)
A. 错误
B. 正确
4.度为2的有序树一定是二叉树。 (满分:5)
A. 错误
B. 正确
5.中缀表达式A+(B-C/D)*E的后缀形式是ABCD/+E*-。 (满分:5)
A. 错误
B. 正确
6.在用顺序表表示的循环队列中，可用标志位来表示队空或队满的条件。 (满分:5)
A. 错误
B. 正确
7.具有m个结点的二叉排序树有多种，其中树高最小的一棵是最佳的。 (满分:5)
A. 错误
B. 正确
8.出栈操作的时间复杂度为O(1)。 (满分:5)
A. 错误
B. 正确
9.在单链表中，要取得某个元素，只要知道该元素的指针即可，可以说单链表是随机存取的存储结构。 (满分:5)
A. 错误
B. 正确
10.二叉树的左右子树次序可以任意改变。 (满分:5)
A. 错误
B. 正确
大工17春《数据结构》在线作业3
一、单选题：
1.最短路径的生成算法可用( )算法。 (满分:5)
A. 普里姆
B. 迪杰斯特拉
C. 克鲁斯卡尔
D. 哈夫曼
2.设一组初始记录序列为(5，2，6，3，8)，以5为基准进行一趟快速排序的结果为( )。 (满分:5)
A. 2，3，5，8，6
B. 3，2，5，6，8
C. 3，2，5，8，6
D. 2，3，6，5，8
3.线性表中采用折半查找法查找元素，该线性表应该有( )特点。 (满分:5)
A. 元素按值有序，且采用链式存储结构
B. 元素按值有序，且采用顺序存储结构
C. 采用顺序存储结构
D. 元素按值有序
4.在1000个无序的元素用最快的速度挑选出其中前10个最大的元素，最好选用( )排序法。 (满分:5)
A. 冒泡排序
B. 快速排序
C. 基数排序
D. 堆排序
5.有n个顶点和e条边的有向图进行拓扑排序时，总的计算时间为( )。 (满分:5)
A. O(nlog2e)
B. O(n+e)
C. O(en )
D. O( elog2n)
6.对一组数据（46,79,56,38,40,84）采用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。 (满分:5)
A. 38,40,46,56,79,84
B. 40,38,46,84,56,79
C. 40,38,46,56,79,84
D. 40,38,46,79,56,84
7.一个有序表中的元素为(12，17，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过( )次比较。 (满分:5)
A. 1
B. 2
C. 3
D. 4
8.有n个顶点e条边的无向图G中，其对应的邻接表中的表头结点和表结点的个数分别为( )。 (满分:5)
A. n和2e
B. 2n和e
C. e和n
D. n和e
9.用顺序查找法在具有n个结点的线性表中查找一个结点的时间复杂度为( )。 (满分:5)
A. O(log2n^2)
B. O(nlog2n)
C. O(n)
D. O(log2n)
10.下面四种排序法中( )排序法是不稳定性排序法。 (满分:5)
A. 插入
B. 冒泡
C. 堆排序
D. 二路归并
三、判断题：
1.快速排序是一种稳定的排序方法。 (满分:5)
A. 错误
B. 正确
2.一个基本有序的元素序列，效率最高的排序方法是插入排序。 (满分:5)
A. 错误
B. 正确
3.强连通图的各顶点间不一定全部可达。 (满分:5)
A. 错误
B. 正确
4.选择排序方法是两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。 (满分:5)
A. 错误
B. 正确
5.从一个图的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。 (满分:5)
A. 错误
B. 正确
6.在哈希存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越小。 (满分:5)
A. 错误
B. 正确
7.对m个数据进行冒泡排序，第一趟共需要比较m-1对元素。 (满分:5)
A. 错误
B. 正确
8.某有向图的邻接表中有m个表头结点和n个表结点，则该图中有n条有向边。 (满分:5)
A. 错误
B. 正确
9.哈希法存储是由关键码的值决定数据的存储地址。 (满分:5)
A. 错误
B. 正确
10.m阶B树每一个结点的子树个数必然不大于m。 (满分:5)
A. 错误
B. 正确
附件就是满分答案，需要可以下载。
页:
[1]