数据结构课程作业

-数据结构课程作业_A交卷时间：2017-08-09 10:08:51一、单选题 1. (7分)设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点： 第五章 展开解析 答案 C 解析 第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点： 第九章 展开解析 答案 D 解析 第九章第一节有序表的查找 3. (7分)设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点： 第七章 展开解析 答案 A 解析 第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点： 第六章 展开解析 答案 A 解析 第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（ ）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 纠错 得分： 7 知识点： 第三章 展开解析 答案 A 解析 第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点： 第九章 展开解析 答案 B 解析 第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点： 第六章 展开解析 答案 C 解析 第六章第六节二叉树的性质 8. (7分)线性表的顺序存储结构是一种?的存储结构 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 纠错 得分： 7 知识点： 第二章 展开解析 答案 A 解析 第二章第二节综合题目 9. (7分)对完全二叉树叙述正确的是 A. 完全二叉树就是满二叉树 B. 完全二叉树和满二叉树编号不对应 C. 完全二叉树同一层上左子树未满不会有右子树 D. 以上都不正确 纠错 得分： 7 知识点： 第六章 展开解析 答案 C 解析 第六章第二节二叉树的性质 10. (7分)设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。 A. n(n-1) B. n+1 C. n D. n(n+1) 纠错 得分： 7 知识点： 第七章 展开解析 答案 C 解析 第七章第一节综合题目 二、判断 1. (6分)哈希表不需要进行比较便可以直接取得所查记录纠错 得分： 6 知识点： 第九章 展开解析 答案 正确 解析 第九章第三节综合题目 2. (6分)直接插入排序是一种最简单的排序方法纠错 得分： 6 知识点： 第十章 展开解析 答案 正确 解析 第十章第二节直接插入排序 3. (6分)分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ）纠错 得分： 6 知识点： 第九章 展开解析 答案 正确 解析 第九章第一节索引顺序表的查找 4. (6分)数据的物理结构是指数据在计算机内的实际的存储形式纠错 得分： 6 知识点： 第一章 展开解析 答案 正确 解析 第一章第二节物理结构 5. (6分)当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）纠错 得分： 6 知识点： 第九章 收起解析 答案 正确 解析 第九章第二节二叉排序树和平衡二叉树 数据结构课程作业_B交卷时间：2017-08-09 10:25:50一、单选题 1. (7分)若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 7 知识点： 第九章 展开解析 答案 D 解析 第九章第一节有序表的查找 2. (7分)按照二叉树的定义，有三个结点的二叉树有_种 A. 2 B. 3 C. 4 D. 5 纠错 得分： 7 知识点： 第六章 展开解析 答案 D 解析 第六章第二节二叉树的定义 3. (7分)广义表（a）,a）的表头是_ A. a B. b C. (a) D. (a) 纠错 得分： 0 知识点： 第五章 展开解析 答案 C 解析 第五章第四节综合题目 4. (7分)设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。 A. BADC B. BCDA C. CDAB D. CBDA 纠错 得分： 7 知识点： 第六章 展开解析 答案 A 解析 第六章第三节遍历二叉树 5. (7分)数据结构是一门研究？的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科 A. 数值 B. 非数值 C. 字符 D. 数字 纠错 得分： 0 知识点： 第一章 展开解析 答案 B 解析 第一章第一节综合题目 6. (7分)图的广度优先遍历算法类似于二叉树的_ A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 纠错 得分： 7 知识点： 第七章 展开解析 答案 D 解析 第七章第三节广度优先搜索 7. (7分)设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。 A. 8 B. 7 C. 6 D. 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需要比较的关键字个数为（ ）。 A. 1 B. 2 C. 3 D. 4 纠错 得分： 7 知识点： 第九章 展开解析 答案 B 解析 第九章第一节有序表的查找 10. (7分)设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（ ）。 A. O(n) B. O(n2) C. O(nlog2n) D. O(1og2n) 纠错 得分： 7 知识点： 第九章 展开解析 答案 D 解析 第九章第二节二叉排序树和平衡二叉树 二、判断 1. (6分)设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ）纠错 得分： 6 知识点： 第六章 展开解析 答案 正确 解析 第六章第四节森林与二叉树的转换 2. (6分)如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（ ）纠错 得分： 6 知识点： 第九章 展开解析 答案 正确 解析 第九章第三节什么是哈希表 3. (6分)栈是后进先出的线性表纠错 得分： 6 知识点： 第三章 展开解析 答案 正确 解析 第三章第一节综合题目 4. (6分)二维数组和多维数组均不是特殊的线性结构。（ ）纠错 得分： 6 知识点： 第五章 展开解析 答案 错误 解析 第五章综合题目 5. (6分)栈和队列都是操作受限的线性表纠错 得分： 6 知识点： 第三章 收起解析 答案 正确 解析 第三章综合题目 数据结构课程作业_C交卷时间：2017-08-09 10:36:47一、单选题 1. (7分)对完全二叉树叙述正确的是 A. 完全二叉树就是满二叉树 B. 完全二叉树和满二叉树编号不对应 C. 完全二叉树同一层上左子树未满不会有右子树 D. 以上都不正确 纠错 得分： 7 知识点： 第六章 展开解析 答案 C 解析 第六章第二节二叉树的性质 2. (7分)线性表是 A. 有限序列，可以为空 B. 有限序列，不能为空 C. 无限序列，可以为空 D. 无限序列，不能为空 纠错 得分： 7 知识点： 第二章 展开解析 答案 A 解析 第二章第一节综合题目 3. (7分)下面关于线性表的叙述错误的是（ ）。 A. 线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现 纠错 得分： 7 知识点： 第二章 展开解析 答案 D 解析 第二章综合题目 4. (7分)设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 A. n-1 B. n C. n+1 D. 2n-1 纠错 得分： 7 知识点： 第七章 展开解析 答案 B 解析 第七章第二节邻接表 5. (7分)二路归并排序的时间复杂度为（ ）。 A. O(n) B. O(n2) C. O(nlog2n) D. O(1og2n) 纠错 得分： 7 知识点： 第十章 展开解析 答案 C 解析 第十章第五节综合题目 6. (7分)两个字符串相等的充要条件是（ ）。 A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等 C. 同时具备(A)和(B)两个条件 D. 以上答案都不对 纠错 得分： 0 知识点： 第四章 展开解析 答案 C 解析 第四章第一节字符串相等 7. (7分)栈的插入和删除操作在（ ）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 纠错 得分： 7 知识点： 第三章 展开解析 答案 A 解析 第三章第一节栈的表示和实现 8. (7分)设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 A. n B. n-1 C. m D. m-1 纠错 得分： 7 知识点： 第七章 展开解析 答案 C 解析 第七章第二节邻接表 9. (7分)设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 A. 40，50，20，95 B. 15，40，60，20 C. 15，20，40，45 D. 45，40，15，20 纠错 得分： 7 知识点： 第十章 展开解析 答案 B 解析 第十章第二节希尔排序 10. (7分)设有以下四种排序方法，则（ ）的空间复杂度最大。 A. 冒泡排序 B. 快速排序 C. 堆排序 D. 希尔排序 纠错 得分： 7 知识点： 第十章 展开解析 答案 B 解析 第十章综合题目 二、判断 1. (6分)森林的先序遍历与其对应的二叉树的中序遍历对应纠错 得分： 0 知识点： 第六章 展开解析 答案 错误 解析 第六章第四节数和森林的遍历 2. (6分)带权无向图的最小生成树是唯一的。（ ）纠错 得分： 0 知识点： 第七章 展开解析 答案 错误 解析 第七章第四节最小生成树 3. (6分)算法和程序没有区别纠错 得分： 6 知识点： 第一章 展开解析 答案 错误 解析 第一章第四节综合题目 4. (6分)设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）纠错 得分： 6 知识点： 第十章 展开解析 答案 正确 解析 第十章第四节堆排序 5. (6分)设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ）纠错 得分： 6 知识点： 第六章 收起解析 答案 正确 解析 第六章第四节森林与二叉树的转换 数据结构课程作业_A交卷时间：2017-09-08 19:21:11一、单选题1.(7分)设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。 A.head=0 B.head-next=0 C.head-next=head D.head!=0纠错得分：7知识点：第二章展开解析2.(7分)for (j=1; j=n; +j) s=s+1; A.O(n) B.O(1) C.O(n2) D.O(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知识点：第二章展开解析5.(7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 A.20 B.256 C.512 D.1024纠错得分：7知识点：第六章展开解析6.(7分)链式队列Q为空的判定条件 A.Q.front=Q.rear B.Q.front=Q C.Q =Q.rear D.没有正确答案纠错得分：0知识点：第三章展开解析7.(7分)数据的最小单位是（ ）。 A.数据项 B.数据类型 C.数据元素 D.数据变量纠错得分：7知识点：第一章展开解析8.(7分)设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 A.2k-1 B.2k C.2k-1 D.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条记录关键字为（ ）。 A.40，50，20，95 B.15，40，60，20 C.15，20，40，45 D.45，40，15，20纠错得分：7知识点：第十章展开解析二、判断1.(6分)线性结构只能用顺序存储纠错得分：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.2n B.n C.n/2 D.n(n-1)纠错得分：7知识点：第七章展开解析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知识点：第二章展开解析4.(7分)设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 A.3 B.4 C.5 D.8纠错得分：7知识点：第十章展开解析5.(7分)由两个栈共享一个向量空间的好处是：（ ） A.减少存取时间，降低下溢发生的机率 B.节省存储空间，降低上溢发生的机率 C.减少存取时间，降低上溢发生的机率 D.节省存储空间，降低下溢发生的机率纠错得分：7知识点：第三章展开解析6.(7分)设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 A.n B.n-1 C.m D.m-1纠错得分：7知识点：第七章展开解析7.(7分)设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。 A.10，15，14，18，20，36，40，21 B.10，15，14，18，20，40，36，21 C.10，15，14，20，18，40，36，2l D.15，10，14，18，20，36，40，21纠错得分：0知识点：第十章展开解析8.(7分)设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。 A.n(n-1) B.n+1 C.n D.n(n+1)纠错得分：7知识点：第七章展开解析9.(7分)设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 A.9 B.10 C.11 D.12纠错得分：7知识点：第六章展开解析10.(7分)在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。 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.(6分)稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ ）纠错得分：6知识点：第五章收起解析答案正确解析第五章第三节稀疏矩阵数据结构课程作业_C交卷时间：2017-09-08 20:11:29一、单选题1.(7分)栈的插入和删除操作在（ ）进行。 A.栈顶 B.栈底 C.任意位置 D.指定位置纠错得分：7知识点：第三章展开解析2.(7分)堆的形状是一棵 A.二叉排序树 B.满二叉树 C.完全二叉树 D.一般的二叉树纠错得分：7知识点：第十章展开解析3.(7分)时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。 A.堆排序 B.冒泡排序