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