数据结构与算法在线作业答案

1.邻接表是图的一种____。

A 顺序存储结构 B 链式存储结构 C 索引存储结构 D 散列存储结构 单选题

2.具有5个顶点的有向完全图有____条弧。

A 10 B 16 C 20 D 25 单选题

3.链表不具有的特点是_____。

A 可随机访问任一元素 B 插入和删除不需要移动元素 C 不必事先估计存储空间 D 所需空间和线性表长度成正比 单选题

4.作进栈操作时，应先判断栈是否为_____。

A 空 B 满 C 上溢 D 下溢

选题

单选题

5.下面关于图的存储的叙述中，哪一个是正确的？

A 用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B 用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 单选题

6.当字符序列 x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是____。

A 3个 B 4个 C 5个 D 6个 单选题

7.树最适合用来表示_____。

A 有序数据元素 B 无序数据元素

C 元素之间具有分支层次关系的数据 D 元素之间无联系的数据 单选题

8.线性表按链式方式存储时，每个结点的存储包括_____两部分。

A 数据值与符号 B 数据与指针 C 数据与表名 D 数据项与符号

单选题

9.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中_____是正确的。

A 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D 以上都不对 单选题

10.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____(注意C和D中h为指数)。

A 2h-1 B 2(h-1) C 2*h-1 D 2*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）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。

A 38,40,46,56,79,84 B 40,38,46,79,56,84 C 40,38,46,56,79,84 D 40,38,46,84,56,79 单选题

16.设散列表长为14，散列函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是____________。

A 8 B 3 C 5 D 9 单选题

17.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是____。

A dbafec B fecdba C efcdba D dbfeca 单选题

18.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过____。

A n/2 B n C (n+1)/2 D n+1 单选题

19.设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为______。

A O（log2n） B O(n) C O(nlog2n) D O(n^2) 单选题

20.判断一个循环队列是空队列的条件是_____。

A Q.rear==Q.front B Q.front==0 C Q.rear==0

D (Q.rear+1)%maxsize==Q.front 单选题

21.有m个叶子结点的Huffman树所具有的结点总数为____。

A m+1 B 2m-1 C 2m D 2m+1 单选题

22.在一个无向图中，所有顶点的度数之和等于所有边数的____倍。

A 1/2 B 1 C 2 D 4 单选题

23.线性表采用链式存储时，其地址_____。

A 必须是连续的 B 必须是不连续的 C 连续与否均可

D 部分地址必须是连续的 单选题

24.在数据结构中，与所使用的计算机无关的是数据的____结构。

A 存储 B 物理 C 逻辑 D 物理与存储 单选题

25.向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动_____个元素。

A 115 B 114 C 58 D 57 单选题

26.任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序____。

A 不发生变化 B 发生变化 C 不能确定 D 以上都不对 单选题

27.将10个元素散列到100000个单元的散列表中，则__________产生冲突。

A 一定会 B 一定不会 C 仍可能会 单选题

28.一组记录的排序码为（20,29,11,74,35,3,8,56），则利用堆排序方法建立的初始(小顶)堆为____。

A 20,29,11,74,35,3,8,56

B 3,29,8,56,35,20,11,74 C 3,8,11,20,29,35,56,74 D 20,29,3,8,11,35,74,56 单选题

29.对线性表进行二分查找时，要求线性表必须____。

A 以顺序方式存储

B 以顺序方式存储且元素有序 C 以链式方式存储

D 以链式方式存储且元素有序 单选题

30.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是____。

A 根结点无右子树的二叉树 B 根结点无左子树的二叉树

C 根节点可能有左子树和右子树的二叉树 D 各结点只有一个儿子的二叉树 单选题

31.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是____。

A a是b祖先 B a是b子孙 C a在b左方 D a在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个数据元素为（，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为____。

A 16，28，34，，73，62，60，26，43，95 B 28，16，34，，62，73，60，26，43，95 C 28，16，34，，62，60，73，26，43，95

D 16，28，34，，62，60，73，26，43，95 单选题

36.在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动_______个元素。

A 1 B n-i C n-i-1 D n-i+1 单选题

37.若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为______。

A n-i+l B n-i C i

D 哪个元素无所谓 单选题

38.在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是______。

A O(n) B O(log2n) C O(1) D O(n^2) 单选题

39.数据结构课程主要研究以下三方面的内容，它们是______。

A 数据、数据元素、数据类型 B 数据元素、数据类型、算法实现

C 数据元素、数据的逻辑结构、数据的存储结构

D 数据的逻辑结构、数据的存储结构、数据的运算 单选题

40.在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。

A 正确 B 不正确 单选题

41.一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是_______。

A acbd B dcba C acdb D dbac 单选题

42.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是____。

A acbed B decab C deabc D cedba 单选题

43.一个栈的进栈序列是a,b,c,d,e, 则栈的不可能的出栈序列是_____。

A edcba B dceab C decba D abcde 单选题

44.栈结构通常采用的两种存储结构是_____。

A 线性存储结构和链表存储结构 B 散列方式和索引方式 C 链表存储结构和数组

D 线性存储结构和非线性存储结构 单选题

45.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好____排序法。

A 起泡排序 B 快速排序 C 堆排序 D 基数排序 单选题

46.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____。

A 该中间位置 B 该中间位置－1 C 该中间位置＋1 D 该中间位置／2 单选题

47.在长度为n 的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是_____ 。

A O(n) B O(log2n) C O(1) D O(n^2)

单选题

48.队列的操作原则是_____。

A 先进先出 B 先进后出 C 只能进行插入 D 只能进行删除 单选题

49.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_____。

A 6 B 5 C 4 D 3 单选题

50.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____(注意C和D中h是指数)。

A 2h-1 B 2(h-1) C 2*h-1 D 2*h 单选题

51.下列排序算法的时间复杂度最小的是____。

A 冒泡排序 B 希尔排序 C 简单选择排序

D 归并排序 单选题

52. 如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是_____。

A G肯定不是完全图 B G一定不是连通图 C G中一定有回路 D G有2个连通分量 单选题

53.带头结点的单链表Head为空表的判定条件是______。

A Head->next==Head B Head->next==NULL C Head!=NULL D Head==NULL 单选题

.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较。

A 2 B 3 C 4 D 5 单选题

55.顺序表的特点是______。

A 逻辑上相邻的结点其物理位置不相邻 B 逻辑上相邻的结点其物理位置亦相邻

C 顺序表不是随机存储结构

D 在顺序表中插入和删除操作比在链表上方便 单选题

56.设n个顶点e条边的图 G 用邻接表存储，则求每个顶点入度的时间复杂度为____。

A O(n) B O(n+e) C O(n*n) D O(n*e) 单选题

57.对于一个具有n个顶点和e 条边的无向图，若采用邻接表表示，邻接表中所有结点总数是_____。

A e/2 B 2e C e D n+e 单选题

58.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是_____的二叉树。

A 空或只有一个结点 B 高度等于其结点数 C .任一结点无左孩子 D 任一结点无右孩子 单选题

59.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 ____ 。

A 插入排序 B 快速排序

C 归并排序 D 选择排序 单选题

60.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的_____个元素。

A n/2 B (n+1)/2 C (n-1)/2 D n 判断题

61.通过关键字比较的方法进行排序，其时间复杂性至少是 O(nlog2n)。

正确 判断题

62.5个顶点的无向图，若不连通，则最多可能有6条边。

正确 判断题

63.由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。

正确 判断题

.任何一个森林都可以唯一地与一棵二叉树对应。

正确 判断题

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，则一定是平衡二叉树。

正确

错误 错误 错误 错误

保存 提交 关闭 窗体底端