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

窗体顶端单选题 1.【第1章第2节】数据结构课程主要研究以下三方面的内容，它们是_。 A 数据、数据元素、数据类型 B 数据元素、数据类型、算法实现 C 数据元素、数据的逻辑结构、数据的存储结构 D 数据的逻辑结构、数据的存储结构、数据的运算 正确答案:D单选题 2.【第1章第2节】在数据结构中，与所使用的计算机无关的是数据的_结构。 A 存储 B 物理 C 逻辑 D 物理与存储 正确答案:C判断题 3.【第1章第2节】逻辑结构相同时物理结构也应该相同。 正确 错误 正确答案: 错 单选题 4.【第1章第3节】设某二维数组A1.n，1.n，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为_。 A O（log2n） B O(n) C O(nlog2n) D O(n2) 正确答案:D单选题 5.【第1章第3节】计算机算法是指_。 A 计算方法 B 排序方法 C 调度方法 D 解决问题的有限运算序列 正确答案:D判断题 6.【第1章第3节】所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 正确 错误 正确答案: 对 单选题 7.【第3章第2节】在长度为n 的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是_ 。 A O(n) B O(log2n) C O(1) D O(n2) 正确答案:C单选题 8.【第3章第2节】线性表按链式方式存储时，每个结点的存储包括_两部分。 A 数据值与符号 B 数据与指针 C 数据与表名 D 数据项与符号 正确答案:B单选题 9.【第3章第2节】链表不具有的特点是_。 A 可随机访问任一元素 B 插入和删除不需要移动元素 C 不必事先估计存储空间 D 所需空间和线性表长度成正比 正确答案:A单选题 10.【第3章第2节】对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的_个元素。 A n/2 B (n+1)/2 C (n-1)/2 D n 正确答案:A单选题 11.【第3章第2节】在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是_。 A O(n) B O(log2n) C O(1) D O(n2) 正确答案:A单选题 12.【第3章第2节】线性表采用链式存储时，其地址_。 A 必须是连续的 B 必须是不连续的 C 连续与否均可 D 部分地址必须是连续的 正确答案:C单选题 13.【第3章第2节】若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择_最合适。 A 单链表 B 带尾指针的单循环链表 C 双链表 D 双循环链表 正确答案:B单选题 14.【第3章第2节】带头结点的单链表Head为空表的判定条件是_。 A Head-next=Head B Head-next=NULL C Head!=NULL D Head=NULL 正确答案:B单选题 15.【第3章第2节】顺序表的特点是_。 A 逻辑上相邻的结点其物理位置不相邻 B 逻辑上相邻的结点其物理位置亦相邻 C 顺序表不是随机存储结构 D 在顺序表中插入和删除操作比在链表上方便 正确答案:B单选题 16.【第3章第2节】在一个长度为n的顺序表中，在第i个元素（1=i0)个结点的树有n-1条边。 正确 错误 正确答案: 对 单选题 37.【第4章第3节】任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序_。 A 不发生变化 B 发生变化 C 不能确定 D 以上都不对 正确答案:A单选题 38.【第4章第3节】设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_。 A 6 B 5 C 4 D 3 正确答案:C单选题 39.【第4章第3节】某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是_的二叉树。 A 空或只有一个结点 B 高度等于其结点数 C .任一结点无左孩子 D 任一结点无右孩子 正确答案:A单选题 40.【第4章第3节】关于二叉树的三种遍历，下列说法正确的是_。 A 任意两种遍历序列都不可以唯一决定该二叉树 B 任意两种遍历序列都可以唯一决定该二叉树 C 先序遍历序列和后序遍历序列可以唯一决定该二叉树 D 先序遍历序列和中序遍历序列可以唯一决定该二叉树 正确答案:D单选题 41.【第4章第3节】已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是_。 A acbed B decab C deabc D cedba 正确答案:D单选题 42.【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_(注意C和D中h是指数)。 A 2h-1 B 2(h-1) C 2*h-1 D 2*h 正确答案:A单选题 43.【第4章第3节】设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是_。 A a是b祖先 B a是b子孙 C a在b左方 D a在b右方 正确答案:C单选题 44.【第4章第3节】树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中_是正确的。 A 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D 以上都不对 正确答案:A单选题 45.【第4章第3节】在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。 A 正确 B 不正确 正确答案:A单选题 46.【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_(注意C和D中h为指数)。 A 2h-1 B 2(h-1) C 2*h-1 D 2*h 正确答案:A单选题 47.【第4章第3节】如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是_。 A dbafec B fecdba C efcdba D dbfeca 正确答案:D判断题 48.【第4章第3节】满二叉树一定是完全二叉树，反之不然。 正确 错误 正确答案: 对 判断题 49.【第4章第3节】任何二叉树的叶子数都要比度为2的结点数多。 正确 错误 正确答案: 对 判断题 50.【第4章第3节】由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。 正确 错误 正确答案: 对 单选题 51.【第4章第4节】若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过_。 A n/2 B n C (n+1)/2 D n+1 正确答案:B判断题 52.【第4章第4节】二叉排序树一般用于查找某个元素。 正确 错误 正确答案: 对 判断题 53.【第4章第4节】如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树。 正确 错误 正确答案: 错 单选题 54.【第4章第6节】有m个叶子结点的Huffman树所具有的结点总数为_。 A m+1 B 2m-1 C 2m D 2m+1 正确答案:B判断题 55.【第4章第6节】序列12, 23, 15, 24, 22, 18, 16, 30, 27是一个堆。 正确 错误 正确答案: 错 判断题 56.【第4章第6节】哈夫曼编码使一串文字的编码长度最短。 正确 错误 正确答案: 对 判断题 57.【第5章第1节】哈希表是用于查找的技术之一。 正确 错误 正确答案: 对 单选题 58.【第5章第2节】将10个元素散列到100000个单元的散列表中，则_产生冲突。 A 一定会 B 一定不会 C 仍可能会 正确答案:C判断题 59.【第5章第2节】若散列表的装载因子1，则可避免冲突的产生。 正确 错误 正确答案: 错 单选题 60.【第5章第3节】设散列表长为14，散列函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是_。 A 8 B 3 C 5 D 9 正确答案:D单选题 61.【第6章第2节】在一个无向图中，所有顶点的度数之和等于所有边数的_倍。 A 1/2 B 1 C 2 D 4 正确答案:C单选题 62.【第6章第2节】具有5个顶点的有向完全图有_条弧。 A 10 B 16 C 20 D 25 正确答案:C判断题 63.【第6章第2节】树可以看成是连通的图。 正确 错误 正确答案: 对 判断题 64.【第6章第2节】5个顶点的无向图，若不连通，则最多可能有6条边。 正确 错误 正确答案: 对 判断题 65.【第6章第2节】有向图各顶点入度之和就等于边的数量。 正确 错误 正确答案: 对 判断题 66.【第6章第2节】无向图各顶点度之和就等于边的数量。 正确 错误 正确答案: 错 单选题 67.【第6章第3节】对于一个具有n个顶点和e 条边的无向图，若采用邻接表表示，邻接表中所有结点总数是_。 A e/2 B 2e C e D n+e 正确答案:B单选题 68.【第6章第3节】设n个顶点e条边的图 G 用邻接表存储，则求每个顶点入度的时间复杂度为_。 A O(n) B O(n+e) C O(n*n) D O(n*e) 正确答案:B单选题 69.【第6章第3节】下面关于图的存储的叙述中，哪一个是正确的？ A 用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B 用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 正确答案:A单选题 70.【第6章第3节】邻接表是图的一种_。 A 顺序存储结构 B 链式存储结构 C 索引存储结构 D 散列存储结构 正确答案:B判断题 71.【第6章第3节】用邻接矩阵表示图所用的存储空间大小与图的边数成正比。 正确 错误 正确答案: 错 单选题 72.【第6章第4节】 如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是_。 A G肯定不是完全图 B G一定不是连通图 C G中一定有回路 D G有2个连通分量 正确答案:C判断题 73.【第6章第4节】连通图的广度优先搜索中一般要采用队列 来暂存刚访问过的顶点。 正确 错误 正确答案: 对 判断题 74.【第6章第4节】图的深度优先遍历和广度优先遍历都包含了图的全部顶点。 正确 错误 正确答案: 对 单选题 75.【第6章第5节】关于无向连通图的最小生成树的个数_。 A 一定有多棵 B 一定只有一棵 C 有一棵或多棵 D 可能不存在 正确答案:B单选题 76.【第6章第5节】下列关于图的生成树的唯一性，正确的是_。 A 生成树是唯一的 B 生成树是不唯一的 C 生成树是唯一性不确定 D 图的生成树有两棵 正确答案:C单选题 77.【第7章第2节】一组记录的排序码为（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 正确答案:B单选题 78.【第7章第3节】用某种排序方法对线性表(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 快速排序 正确答案:D判断题 79.【第7章第3节】在某个实例的排序结果看出，值相同的两个关键字排序前后领先关系不变，由此可知该排序方法是稳定的。 正确 错误 正确答案: 错 单选题 80.【第7章第4节】一组记录的关键字为（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 正确答案:C单选题 81.【第7章第4节】已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为_。 A 16，28，34，54，73，62，60，26，43，95 B 28，16，34，54，62，73，60，26，43，95 C 28，16，34，54，62，60，73，26，43，95 D 16，28，34，54，62，60，73，26，43，95 正确答案:B单选题 82.【第7章第8节】在待排序的元素序列基本有序的前提下，效