数据结构课程作业

1、数据结构课程作业_A交卷时间：2017-08-09 10:08:51一、单选题1.（7分）设有一个二维数组 Amn，假设A00存放位置在644（10） , A22存放位置在676（10），每个 元素占一个空间，问 A33（10）存放在什么位置脚注（10）表示用10进制表示。A. 688B. 678C. 692D. 696纠错得分：7知识点:第五章3.展开解析 答案C 解析第五章第二节综合题目2.（7分）若有18个元素的有序表存放在一维数组A19中，第一个元素放 A1中，现进行二分查找，则查找的比较序列的下标依次为（）A. 1 , 2,B. 9 , 5,2, 3C. 9 , 5,纠错得分:知识点

2、:D. 9 , 4,2, 3第九章展开解析 答案D 解析第九章第一节有序表的查找（7分）设某完全无向图中有 n个顶点，则该完全无向图中有（）条边。A. n(n-1)/2B. n(n-1)C. n2D. n2-1纠错得分：7 知识点：第七章 展开解析 答案A 解析第七章第一节综合题目4.（7分）若在任意一棵二叉树中，有no个叶子结点，有n2个度为2的结点，则：n0=.A. n2+1B. n2-1C. n2+2D. n2-2纠错得分：7知识点:第六章展开解析 答案A 解析第六章第二节二叉树的性质5.（7分）栈的插入和删除操作在（）进行。A. 栈顶B. 栈底C. 任意位置D.指定位置纠错得分：7知识

3、点:第三章展开解析 答案A 解析第三章第一节栈的表示和实现6.（7分）设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。A. 25B. 10C. 7D. 19.纠错得分：7 知识点：第九章 展开解析 答案B 解析第九章第一节有序表的查找7.（7分）设某棵二叉树的高度为10,则该二叉树上叶子结点最多有（）。A. 20B. 256C. 512D. 1024纠错得分：7知识点:第六章展开解析 答案C 解析第六章第六节二叉树的性质8.（7分）线性表的顺序存储结构是一种的存储结构A. 随机存取B. 顺序存取C. 索引存取D. 散列存取纠错得分：7知识点:第二章展开解析 答案A 解析第

4、二章第二节综合题目（7分）对完全二叉树叙述正确的是A. 完全二叉树就是满二叉树B. 完全二叉树和满二叉树编号不对应C. 完全二叉树同一层上左子树未满不会有右子树D.以上都不正确2.纠错得分：6纠错得分：7 知识点：第六章 展开解析 答案C 解析第六章第二节二叉树的性质10.）条边。（7分）设某强连通图中有n个顶点，则该强连通图中至少有（A. n(n-1)B. n+1C. nD. n(n+1)纠错得分：7知识点:第七章展开解析 答案C 解析第七章第一节综合题目 二、判断1.（6分）哈希表不需要进行比较便可以直接取得所查记录纠错得分：6 知识点：第九章 展开解析 答案正确 解析第九章第三节综合题目

5、（6分）直接插入排序是一种最简单的排序方法知识点： 第十章 展开解析 答案 正确 解析 第十章第二节直接插入排序3.（6 分 ）分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（纠错得分： 6知识点： 第九章 展开解析 答案 正确 解析 第九章第一节索引顺序表的查找4.（6 分 ）数据的物理结构是指数据在计算机内的实际的存储形式纠错得分： 6知识点： 第一章 展开解析 答案 正确 解析 第一章第二节物理结构5.（6 分 ）当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（纠错得分： 6知识点： 第九章 收起解析 答案 正确 解析 第九章第二节二叉排序树和平衡二叉树数据

6、结构课程作业 _B交卷时间： 2017-08-09 10:25:50纠错得分：7知识点:第七章展开解析一、单选题1.（7分）若有18个元素的有序表存放在一维数组A19中，第一个元素放 A1中，现进行二分查找，则查找A : 3的比较序列的下标依次为（）A. 1 , 2,B. 9 ,2, 3C. 9 ,纠错得分:知识点:D. 9 ,第九章2, 3展开解析 答案D 解析第九章第一节有序表的查找2.（7分）按照二叉树的定义，有三个结点的二叉树有A. 2B. 3C. 4D. 5纠错得分：7知识点:第六章展开解析 答案D 解析第六章第二节二叉树的定义3.（7分）广义表（a）,a ）的表头是A. aB. b

7、C. (a)D. (a)答案C 解析 第五章第四节综合题目4.（7分）设某棵二叉树的中序遍历序列为ABC D前序遍历序列为CAB D则后序遍历该二叉树得到序列为（）。A. BADCB. BCDAC. CDABD. CBDA纠错得分：7知识点:第六章展开解析 答案A 解析第六章第三节遍历二叉树5.（7分）数据结构是一门研究的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科A. 数值B. 非数值C. 字符D. 数字纠错得分：0知识点:第一章展开解析 答案B 解析第一章第一节综合题目6.（7分）图的广度优先遍历算法类似于二叉树的A. 先序遍历B. 中序遍历C. 后序遍历D. 层次遍历答

8、案D 解析第七章第三节广度优先搜索7.（7分）设一棵完全二叉树中有 65个结点，则该完全二叉树的深度为（）。A. 8B. 7C. 6D. 5纠错得分：7知识点:第六章展开解析 答案B 解析第六章第六节二叉树的性质8.（7分）设用链表作为栈的存储结构则退栈操作（）。A. 必须判别栈是否为满B. 必须判别栈是否为空C. 判别栈元素的类型D.对栈不作任何判别纠错得分：7知识点:第三章展开解析 答案B 解析第三章第一节综合题目9.（7分）设一组初始记录关键字序列为（13，18，24, 35, 47, 50，62，83, 90, 115, 134）,则利用二分法查）。找关键字90需要比较的关键字个数为（

9、A. 1B. 2C. 3D. 4展开解析 答案B 解析第九章第一节有序表的查找10.）。（7分）设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（A. 0(n)B. 0(n2)C. O(nlog2n)D. O(1og2n)纠错得分：7知识点:第九章展开解析 答案D 解析第九章第二节二叉排序树和平衡二叉树 二、判断1.（6分）设一棵树T可以转化成二叉树 BT,则二叉树BT中一定没有右子树。（）纠错得分：6 知识点：第六章 展开解析 答案正确 解析第六章第四节森林与二叉树的转换2.（6分）如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（纠错得分：6 知识点：

10、第九章 展开解析 答案正确 解析第九章第三节什么是哈希表3.（6 分 ）栈是后进先出的线性表纠错得分： 6知识点： 第三章 展开解析 答案 正确 解析 第三章第一节综合题目4.（6 分 ）二维数组和多维数组均不是特殊的线性结构。（纠错得分： 6知识点： 第五章 展开解析 答案 错误 解析 第五章综合题目5.（6 分 ）栈和队列都是操作受限的线性表纠错得分： 6知识点： 第三章 收起解析 答案 正确 解析 第三章综合题目数据结构课程作业 _C交卷时间： 2017-08-09 10:36:47一、单选题（7 分 ）对完全二叉树叙述正确的是1.A. 完全二叉树就是满二叉树B. 完全二叉树和满二叉树编

11、号不对应C. 完全二叉树同一层上左子树未满不会有右子树D. 以上都不正确纠错得分：7知识点:第六章展开解析 答案C 解析第六章第二节二叉树的性质2.（7分）线性表是纠错得分：7知识点:A.有限序列,B.有限序列,C.无限序列,D.无限序列,第二章可以为空不能为空可以为空不能为空展开解析 答案A 解析第二章第一节综合题目3.（7分）下面关于线性表的叙述错误的是（）。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现纠错得分：7知识点:第一早展开解析 答

12、案D 解析第二章综合题目4.（7分）设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。A. n-1B. nC. n+1D. 2n-17.纠错得分：7知识点:第七章展开解析 答案B 解析第七章第二节邻接表5.（7分）二路归并排序的时间复杂度为（）。A. 0(n)B. 0(n2)C. O(nlog2n)D. O(1og2n)纠错得分：7知识点:第十章展开解析 答案C 解析第十章第五节综合题目6.（7分）两个字符串相等的充要条件是（）。A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等C.同时具备（A）和（B）两个条件D.以上答案都不对纠错得分：0知识点:第四章展开解析 答

13、案C 解析第四章第一节字符串相等（7分）栈的插入和删除操作在（）进行。纠错得分：7知识点:A.栈顶B.栈底C.任意位置D.指定位置第三章10.展开解析 答案A 解析第三章第一节栈的表示和实现8.（7分）设某有向图的邻接表中有 n个表头结点和m个表结点，则该图中有（）条有向边。A. nB. n-1C. mD. m-1纠错得分：7知识点:第七章展开解析 答案C 解析第七章第二节邻接表9.）。（7分）设一组初始记录关键字序列为（50，40，95，20，15, 70, 60，45），则以增量d=4的一趟希尔排序 结束后前4条记录关键字为（A. 40，50，20，95B. 15，40，60，20C. 1

14、5，20，40，45D. 45，40，15，20纠错得分：7知识点:第十章展开解析 答案B 解析第十章第二节希尔排序（7分）设有以下四种排序方法，则（）的空间复杂度最大。A.冒泡排序B. 快速排序C. 堆排序D. 希尔排序纠错得分：73.知识点:第十章展开解析 答案B 解析第十章综合题目 二、判断1.（6分）森林的先序遍历与其对应的二叉树的中序遍历对应纠错得分：0 知识点：第六章 展开解析 答案错误 解析第六章第四节数和森林的遍历2.（6分）带权无向图的最小生成树是唯一的。（纠错得分：0 知识点：第七章 展开解析 答案错误 解析第七章第四节最小生成树（6分）算法和程序没有区别纠错得分：6 知识

15、点：第一章 展开解析 答案错误 解析 第一章第四节综合题目4.O(log2n)。()（6分）设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为纠错得分：6 知识点：第十章 展开解析 答案正确 解析第十章第四节堆排序5.（6分）设一棵树T可以转化成二叉树 BT,则二叉树BT中一定没有右子树。（）纠错得分：6 知识点：第六章收起解析答案正确解析第六章第四节森林与二叉树的转换1.数据结构课程作业交卷时间：2017-09-08 19:21:11单选题（7分）设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。?A.?head=O ?B.?head->next=O ?C.

16、?head->next=head?D.?head!=O纠错得分：?7知识点：？第二章展开解析2.(7 分)for (j=1; jv=n; +j) s=s+1;?A.?O(n) ?B.?0(1) ?C.?0(nA2) ?D.?0(n3)纠错得分：?0知识点：？第一章展开解析3.（7分）一个队列的入队序列是1、2、3、4,则队列的首次输出元素是?A.?1 ?B.?2 ?C.?3 ?D.?4纠错得分：?0知识点：？第三章展开解析4.（7分）将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）?A.?O(1) ?B.?O(n) ?C.?O(m) ?D.?O(m+n)纠错得分：?7

17、知识点：？第二章展开解析#.5.）。I（7分）设某棵二叉树的高度为10,则该二叉树上叶子结点最多有（?A.?20 ?B.?256 ?C.?512 ?D.?1024纠错得分：?7知识点：？第六章展开解析6.（7分）链式队列Q为空的判定条件?A.?= ?B.?=Q ?C.?Q = ?D.?没有正确答案纠错得分：?0知识点：？第三章展开解析7.（7分）数据的最小单位是（）。?A.?数据项 ?B.?数据类型 ?C.?数据元素 ?D.?数据变量纠错得分：?7知识点：？第一章展开解析（7分）设一棵二叉树的深度为 k，则该二叉树中最多有（）个结点。I?A.?2k-1 ?B.?2k ?C.?2k-1 ?D.?

18、2k-1纠错得分：?7知识点：？第六章展开解析9.（7分）由权值分别为11, 8 , 6, 2, 5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（?A.?24 ?B.?71 ?C.?48 ?D.?53纠错得分：?7知识点：？第六章展开解析10.（7分）设一组初始记录关键字序列为（50， 40, 95, 20, 15, 70, 60， 45），则以增量d=4的一趟希尔排序|结束后前4条记录关键字为（）。1.?A.?40, 50, 20, 95?B.?15 ,40,60,20?C.?15,20,40,45?D.?45,40,15,20纠错得分:?7知识点：？第十章展开解析二、判断（6分）线性结构

19、只能用顺序存储纠错得分：?6知识点：？第三章展开解析2.（6分）算法和程序没有区别纠错得分：?6知识点：？第一章展开解析3.（6分）可以用队列实现数值转换算法纠错得分：?0知识点：？第三章展开解析4.（6分）哈夫曼树中没有度数为1的结点。（）纠错得分：?6知识点：？第六章展开解析5.（6分）带权无向图的最小生成树是唯一的。（纠错得分：?6知识点：？第七章收起解析错误解析第七章第四节最小生成树数据结构课程作业_B交卷时间：2017-09-08 19:51:39一、单选题1.（7分）设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。A.2nB.C.n/2D.n(n-1)纠错得分：7知识点

20、： 第七章展开解析2.）。（7分）设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（A.O(n+e)B.O(n2)C.O(ne)D.O(n3)纠错得分：7知识点： 第七章展开解析3.（7分）下面关于线性表的叙述错误的是（）。A.B.C.D.得分：7知识点展开解析纠错线性表采用顺序存储必须占用一片连续的存储空间线性表采用链式存储不必占用一片连续的存储空间线性表采用链式存储便于插入和删除操作的实现线性表采用顺序存储便于插入和删除操作的实现第二章6.（7分）设某有向图的邻接表中有n个表头结点和 m个表结点，则该图中有（）条有向边。4.（7分）设一组初始记录关键字序列为（345， 253,

21、 674， 924, 627），则用基数排序需要进行（）趟的分配|和回收才能使得初始关键字序列变成有序序列。A.B.C.D.纠错得分：7知识点：第十章展开解析5.（7分）由两个栈共享一个向量空间的好处是：（）A.减少存取时间，降低下溢发生的机率B.节省存储空间，降低上溢发生的机率C.减少存取时间，降低上溢发生的机率D.节省存储空间，降低下溢发生的机率纠错得分：7知识点： 第三章展开解析A.nB.n-1C.mD.m-1纠错得分：7知识点：第七章展开解析7.卩分）设一组初始关键字记录关键字为（20 , 15, 14,18, 21, 36, 40, 10），则以20为基准记录的一趟快|速排序结束后的

22、结果为（）。A.10,15,14,18,20,36,40,21B.10,15,14,18,20,40,36,21C.10,15,14,20,18,40,36,2lD.15,10,14,18,20,36,40,21纠错得分：0知识点：第十章展开解析8.（7分）设某强连通图中有n个顶点，则该强连通图中至少有（）条边。I9.A.n(n-1)B.n+1C.nD.n(n+1)纠错得分：7知识点：第七章展开解析（7分）设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。IA. 9B. 10C. 11D. 12纠错得分：7知识点： 第六章展开解析10.）。（7分）在二叉排序树中插入一个关键字值的平均

23、时间复杂度为（A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n2)纠错得分：7知识点： 第九章展开解析二、判断1.（6分）层次遍历初始堆可以得到一个有序的序列。（纠错得分：6知识点:第十章展开解析2.（6分）一个有n个顶点的有向图的边数 e最多为e=n（n-1）纠错得分：6知识点:第七章展开解析3.（6分）常用的图的遍历方法有深度优先遍历和广度优先遍历纠错得分：0知识点：第七章展开解析4.（6分）栈是限定在表尾进行插入或删除操作的线性表纠错得分：6知识点：第三章展开解析5.0元素。（）（6分）稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非纠错得分：6知识点： 第五章收起解析答案正确解析第五章第三节稀疏矩阵数据结构课程作业交卷时间：2017-09-08 20:11:29一、单选题1.（7分）栈的插入和删除操作在（）进行。纠错得分:知识点:A.栈顶B.栈底C.任意位置D.指定位置弟二早展开解析2.（7分）堆的形状是一棵IA.二叉排序树B.满二叉树C.完全二叉树D.一般的二叉树纠错得分：7知识点：第十章展开解析3.（7分）时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（）。A.堆排序B.冒泡排序C.希尔排序D.快速排序4.纠错得