数据结构与算法在线作业答案.docx
《数据结构与算法在线作业答案.docx》由会员分享，可在线阅读，更多相关《数据结构与算法在线作业答案.docx（19页珍藏版）》请在冰点文库上搜索。
单选题
1.邻接表是图的一种____。
A顺序存储结构
B链式存储结构
C索引存储结构
D散列存储结构
单选题
2.具有5个顶点的有向完全图有____条弧。
A10
B16
C20
D25
单选题
3.链表不具有的特点是_____。
A可随机访问任一元素
B插入和删除不需要移动元素
C不必事先估计存储空间
D所需空间和线性表长度成正比
单选题
4.作进栈操作时，应先判断栈是否为_____。
A空
B满
C上溢
D下溢
单选题
5.下面关于图的存储的叙述中，哪一个是正确的？
A用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
B用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
单选题
6.当字符序列x5y作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是____。
A3个
B4个
C5个
D6个
单选题
7.树最适合用来表示_____。
A有序数据元素
B无序数据元素
C元素之间具有分支层次关系的数据
D元素之间无联系的数据
单选题
8.线性表按链式方式存储时，每个结点的存储包括_____两部分。
A数据值与符号
B数据与指针
C数据与表名
D数据项与符号
单选题
9.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。
那么以下结论中_____是正确的。
A树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D以上都不对
单选题
10.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____（注意C和D中h为指数）。
A2h-1
B2（h-1）
C2*h-1
D2*h
单选题
11.关于二叉树的三种遍历，下列说法正确的是____。
A任意两种遍历序列都不可以唯一决定该二叉树
B任意两种遍历序列都可以唯一决定该二叉树
C先序遍历序列和后序遍历序列可以唯一决定该二叉树
D先序遍历序列和中序遍历序列可以唯一决定该二叉树
单选题
12.计算机算法是指______。
A计算方法
B排序方法
C调度方法
D解决问题的有限运算序列
单选题
13.若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择_____最合适。
A单链表
B带尾指针的单循环链表
C双链表
D双循环链表
单选题
14.下列关于图的生成树的唯一性，正确的是_____。
A生成树是唯一的
B生成树是不唯一的
C生成树是唯一性不确定
D图的生成树有两棵
单选题
15.一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。
A38,40,46,56,79,84
B40,38,46,79,56,84
C40,38,46,56,79,84
D40,38,46,84,56,79
单选题
16.设散列表长为14，散列函数是H（key）=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是____________。
A8
B3
C5
D9
单选题
17.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是____。
Adbafec
Bfecdba
Cefcdba
Ddbfeca
单选题
18.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过____。
An/2
Bn
C（n+1）/2
Dn+1
单选题
19.设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为______。
AO（log2n）
BO（n）
CO（nlog2n）
DO（n^2）
单选题
20.判断一个循环队列是空队列的条件是_____。
AQ.rear==Q.front
BQ.front==0
CQ.rear==0
D（Q.rear+1）%maxsize==Q.front
单选题
21.有m个叶子结点的Huffman树所具有的结点总数为____。
Am+1
B2m-1
C2m
D2m+1
单选题
22.在一个无向图中，所有顶点的度数之和等于所有边数的____倍。
A1/2
B1
C2
D4
单选题
23.线性表采用链式存储时，其地址_____。
A必须是连续的
B必须是不连续的
C连续与否均可
D部分地址必须是连续的
单选题
24.在数据结构中，与所使用的计算机无关的是数据的____结构。
A存储
B物理
C逻辑
D物理与存储
单选题
25.向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动_____个元素。
A115
B114
C58
D57
单选题
26.任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序____。
A不发生变化
B发生变化
C不能确定
D以上都不对
单选题
27.将10个元素散列到100000个单元的散列表中，则__________产生冲突。
A一定会
B一定不会
C仍可能会
单选题
28.一组记录的排序码为（20,29,11,74,35,3,8,56），则利用堆排序方法建立的初始（小顶）堆为____。
A20,29,11,74,35,3,8,56
B3,29,8,56,35,20,11,74
C3,8,11,20,29,35,56,74
D20,29,3,8,11,35,74,56
单选题
29.对线性表进行二分查找时，要求线性表必须____。
A以顺序方式存储
B以顺序方式存储且元素有序
C以链式方式存储
D以链式方式存储且元素有序
单选题
30.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是____。
A根结点无右子树的二叉树
B根结点无左子树的二叉树
C根节点可能有左子树和右子树的二叉树
D各结点只有一个儿子的二叉树
单选题
31.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是____。
Aa是b祖先
Ba是b子孙
Ca在b左方
Da在b右方
单选题
32.采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。
栈顶结点的插入与删除通常在链表的_____进行。
A任意位置
B链表头尾两端
C链表头一端
D链表尾一端
单选题
33.用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时,元素序列的变化情况如下
（1）20,15,21,25,47,27,68,35,84
（2）15,20,21,25,35,27,47,68,84（3）15,20,21,25,27,35,47,68,84则所采用的排序方法是____。
A选择排序
B希尔排序
C归并排序
D快速排序
单选题
34.关于无向连通图的最小生成树的个数_____。
A一定有多棵
B一定只有一棵
C有一棵或多棵
D可能不存在
单选题
35.已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为____。
A16，28，34，54，73，62，60，26，43，95
B28，16，34，54，62，73，60，26，43，95
C28，16，34，54，62，60，73，26，43，95
D16，28，34，54，62，60，73，26，43，95
单选题
36.在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动_______个元素。
A1
Bn-i
Cn-i-1
Dn-i+1
单选题
37.若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为______。
An-i+l
Bn-i
Ci
D哪个元素无所谓
单选题
38.在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是______。
AO（n）
BO（log2n）
CO
（1）
DO（n^2）
单选题
39.数据结构课程主要研究以下三方面的内容，它们是______。
A数据、数据元素、数据类型
B数据元素、数据类型、算法实现
C数据元素、数据的逻辑结构、数据的存储结构
D数据的逻辑结构、数据的存储结构、数据的运算
单选题
40.在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。
A正确
B不正确
单选题
41.一个栈的入栈序列是a,b,c,d,则下列序列中不可能的输出序列是_______。
Aacbd
Bdcba
Cacdb
Ddbac
单选题
42.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是____。
Aacbed
Bdecab
Cdeabc
Dcedba
单选题
43.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的出栈序列是_____。
Aedcba
Bdceab
Cdecba
Dabcde
单选题
44.栈结构通常采用的两种存储结构是_____。
A线性存储结构和链表存储结构
B散列方式和索引方式
C链表存储结构和数组
D线性存储结构和非线性存储结构
单选题
45.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好____排序法。
A起泡排序
B快速排序
C堆排序
D基数排序
单选题
46.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____。
A该中间位置
B该中间位置－1
C该中间位置＋1
D该中间位置／2
单选题
47.在长度为n的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是_____。
AO（n）
BO（log2n）
CO
（1）
DO（n^2）
单选题
48.队列的操作原则是_____。
A先进先出
B先进后出
C只能进行插入
D只能进行删除
单选题
49.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_____。
A6
B5
C4
D3
单选题
50.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____（注意C和D中h是指数）。
A2h-1
B2（h-1）
C2*h-1
D2*h
单选题
51.下列排序算法的时间复杂度最小的是____。
A冒泡排序
B希尔排序
C简单选择排序
D归并排序
单选题
52.如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是_____。
AG肯定不是完全图
BG一定不是连通图
CG中一定有回路
DG有2个连通分量
单选题
53.带头结点的单链表Head为空表的判定条件是______。
AHead->next==Head
BHead->next==NULL
CHead!
=NULL
DHead==NULL
单选题
54.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较。
A2
B3
C4
D5
单选题
55.顺序表的特点是______。
A逻辑上相邻的结点其物理位置不相邻
B逻辑上相邻的结点其物理位置亦相邻
C顺序表不是随机存储结构
D在顺序表中插入和删除操作比在链表上方便
单选题
56.设n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为____。
AO（n）
BO（n+e）
CO（n*n）
DO（n*e）
单选题
57.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中所有结点总数是_____。
Ae/2
B2e
Ce
Dn+e
单选题
58.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是_____的二叉树。
A空或只有一个结点
B高度等于其结点数
C.任一结点无左孩子
D任一结点无右孩子
单选题
59.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A插入排序
B快速排序
C归并排序
D选择排序
单选题
60.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。
则插入一个元素时平均要移动表中的_____个元素。
An/2
B（n+1）/2
C（n-1）/2
Dn
判断题
61.通过关键字比较的方法进行排序，其时间复杂性至少是O（nlog2n）。
正确错误
判断题
62.5个顶点的无向图，若不连通，则最多可能有6条边。
正确错误
判断题
63.由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。
正确错误
判断题
64.任何一个森林都可以唯一地与一棵二叉树对应。
正确错误
判断题
65.无向图各顶点度之和就等于边的数量。
正确错误
判断题
66.图的深度优先遍历和广度优先遍历都包含了图的全部顶点。
正确错误
判断题
67.有向图各顶点入度之和就等于边的数量。
正确错误
判断题
68.在某个实例的排序结果看出，值相同的两个关键字排序前后领先关系不变，由此可知该排序方法是稳定的。
正确错误
判断题
69.序列｛12,23,15,24,22,18,16,30,27｝是一个堆。
正确错误
判断题
70.判断顺序储存下队列q是空的条件是q.front==q.rear。
正确错误
判断题
71.满二叉树一定是完全二叉树，反之不然。
正确错误
判断题
72.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
正确错误
判断题
73.树可以看成是连通的图。
正确错误
判断题
74.用邻接矩阵表示图所用的存储空间大小与图的边数成正比。
正确错误
判断题
75.判断顺序储存下堆栈s是空的条件是s.top==0。
正确错误
判断题
76.若散列表的装载因子α<1，则可避免冲突的产生。
正确错误
判断题
77.n（n>0）个结点的树有n-1条边。
正确错误
判断题
78.哈夫曼编码使一串文字的编码长度最短。
正确错误
判断题
79.逻辑结构相同时物理结构也应该相同。
正确错误
判断题
80.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。
正确错误
判断题
81.二叉排序树一般用于查找某个元素。
正确错误
判断题
82.在n个元素的顺序表中删除第i个元素，需要移动n-i个元素。
正确错误
判断题
83.哈希表是用于查找的技术之一。
正确错误
判断题
84.任何二叉树的叶子数都要比度为2的结点数多。
正确错误
判断题
85.如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树。
正确错误
保存提交关闭
窗体底端
升级会员 