《数据结构练习答案》由会员分享，可在线阅读，更多相关《数据结构练习答案（37页珍藏版）》请在金锄头文库上搜索。
1、数据构造练习1填写下面表格，对以下几种排序方法进展比拟：排序方法平均时间复杂度最坏情况空间复杂度是否稳定选择排序直接选择排序O(n2)O(n2)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(1)不稳定插入排序直接接插入排序O(n2)O(n2)O(1)稳定拆半接插入排序O(nlog2n)O(n2)O(1)稳定Shell排序O(nlog2n)O(nlog2n)O(1)不稳定冒泡排序交换排序O(n2)O(n2)O(1)稳定快速排序O(nlog2n)O(n2)O(1)不稳定归并排序2-路归并排序O(nlog2n)O(nlog2n)O(n)稳定红黑树O(nlog2n)O(nlog2n)O(
2、1)不稳定线性排序计数排序O(N+K)O(N+K)O(N+K)稳定桶排序O(N)O(N)O(N)稳定基数排序O(d(n+rd)O(d(n+rd)O(rd)稳定解释：时间复杂度O(d(n+rd)：其中分配为On；收集为Ordr为基、d为“分配收集的趟数习题一 填空题1 进栈序列是1、2、3、4，进栈过程中可以出栈，那么可能的出栈序列有 个，不可能的出栈序列是 。2 具有N个元素的顺序存储的循环队列中，假定front与rear分别指向队头元素的前一位置与队尾元素的位置，那么判断队空的与队满的条件分别是 f=r 与 f=r mod m +1 。求此队列中元素个数的计算公式为： (r+m)-f-1)
3、mod m +1 。入队运算： r:=r mod m+1 。 出队运算： f:=f mod m + 1 。3 单链表是 非顺序线性 的链式存储构造，链栈与链队分别是 与 的链式存储构造。4 线性表的顺序存储中，元素之间的逻辑关系是通过 元素存储地址次序 决定的，在线性表的链接存储中，元素之间的逻辑关系是通过 元素存储指针地址访问 决定的。5 深度为5的二叉树至多有结点数为 31 。6 数据构造即数据的逻辑构造包括 顺性存储构造 、 链式存储构造 、 非线性构造 三种类型，树型构造与图型构造称为 非线性构造 。四种根本存储方法：1顺序存储方法2链接存储方法3索引存储方法4散列存储方法二 选择题1
4、 有一个10阶对称矩阵，采用压缩存储方式，以行序为主序存储，A00的地址为1，那么A74的地址为 C A 13 B 18 C 33 D 402 线性表采用链表存储时其存储地址 D 。A必须是连续的 B局部地址必须是连续的C一定是不连续的 D连续不连续都可以3 以下表达中错误的选项是 C 。A 串是一种特殊的线性表，其特殊性表达在数据元素是一个字符B 栈与队列是两种特殊的线性表，栈的特点是后进先出，队列的特点是先进先出。C 线性表的线性存储构造优于链式存储构造D 二维数组是其数据元素为线性表的线性表4 一棵二叉树的顺序存储构造如题图4-1所示，假设中序遍历该二叉树，那么遍历次序为 A .A. D
5、BEGACFH B. ABDEGCFH C. DGEBHFCA D. ABCDEFGH 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEF GH题图4-1 5 设一棵二叉树的顺序存储构造如题图4-2所示，那么该二叉树是 C . A完全二叉树 B满二叉树 C深度为4 的二叉树 D深度为3的二叉树 1 2 3 4 5 6 7 8 9 10 111234567题图4-26 设T是Huffman树，它具有6个树叶，且各树叶的权分别为1，2，3，4，5，6。那么该树的非叶子结点的权之与为 A 。A51 B21 C30 D49 7设有一无向图的邻接矩阵如下所示，那么该图所有顶点的
6、度之与为 C 。 a b c d ea 0 1 1 1 0 b 1 0 1 0 1 c 1 1 0 0 0 d 1 0 0 0 0 e 0 1 0 0 0 A8 B9 C10 D11 8二叉树的后序遍历序列是fedbgca，中序遍历序列是dfebagc，那么该二叉树的先序遍历序列是 D 。Adefbagc Babcdgef Cdbaefcg Dabdefcg9由三个结点构成的二叉树，共有 C 种不同的形态。A3 B 4 C 5 D 610在一个具有n个顶点的无向图中，要连通全部顶点至少需要 D 条边 A n Bn+1 Cn/2 Dn-111对线性表进展折半二分查找时，要求线性表必须 B 。 A
7、以顺序方式存储 B以顺序方式存储且数据元素有序C以链表方式存储 D以链表方式存储且数据元素有序12顺序查找一个具有n个元素的线性表，其时间复杂度为 A ，二分查找一个具有n个元素的线性表，其时间复杂度为 B 。 A O(n) B O(log2n) C O(n2) DO(nlog2n)13.从未排序序列中依次取出元素与已排序序列中的元素进展比拟，将其放入已排序序列中的正确位置上，此方法称为 直接插入排序 ；从未排序序列中挑选元素，并将其放入已排序序列中的一端，此方法称为 直接选择排序 ；依次将每两个相临的有序表合并成一个有序表的排序方法称为 归并排序 ；当两个元素比拟出现反序时就相互交换位置的排
8、序方法称为 交换排序 ；A归并排序 B 选择排序 C交换排序 D插入排序ABCDEFGH图4-3三 简述下面的几个概念：单链表，栈、队列，排序二叉树。四 简述空串与空格串的区别。五 一棵度为2的树与二叉树有何区别？六 试分别画出具有3个结点的树与具有3个结点的二叉树的所有不同形态。七 一二叉树如题图4-3所示，1 用二叉链表与顺序存储方式分别存储此二叉树。画出相应的存储构造图。2 写出此二叉树的中序、先序、后序遍历序列。123456题图4-4八 一无向图如题图4-4所示，请给出该图的1 每个顶点的度。2 邻接矩阵3 邻接表4 按上述的邻接表写出广度与深度遍历序列。九 一组数据元素为46，75，
9、18，54，15，27，42，39，88，671 利用直接插入排序方法，写出每次插入后的结果。2 利用快速排序方法，写出每趟排序后的结果。3 利用2-路归并排序方法，写出每趟归并后的结果。4 利用冒泡排序方法，写出每趟排序后的结果。十 假定一个表为32，75，63，48，94，25，36，18，70，散列空间为0.10，1 假设采用除留余数法构造表，哈希函数为HK=K MOD 11，用线性探测法解决冲突，试画出哈希表，并求在等概率情况下的平均查找长度。2 假设采用除留余数法构造表，哈希函数为HK=K MOD 11，用链地址法解决冲突，试画出哈希表，并求在等概率情况下的平均查找长度。十一 有8个
10、带权结点，权值为3，7，8，2，6，10，14，9，试以它们为叶子结点构造一棵哈夫曼树要求每个结点左子树的权值小于等于右子树的权值，并计算出带权路径长度。十二 一对称阵An*n，假设只存储此对称阵的上半三角元，写出以行为主序存储与以列为主序存储时计算每一元素Aij存储地址的公式。十三 算法设计1 写出在循环单链表L中查找查找第i个元素的算法：SEARCHL，i。2 设有如下题图4-3的单链表，链表头指针为H，写一个将链表进展逆转的算法，逆转以后的链表为题图4-4所示。a1a2an NULLH题图4-3单链表示意图anan-1a1 NULLH题图4-4单链表示意图3 假定用一个带头结点的循环单链
11、表表示循环队列循环链队，该队列只设一个队尾指针，不设头指针，试编写下面的算法：A 向循环链队中插入一个元素x的算法入队。B 从循环链队中删除一个结点出队。4 数组AN存放循环队列中的元素，同时设两个变量分别存储队尾元素的位置与队列中实际元素个数。A 写出此队列的队满条件。B 写出此队列的出、入队算法。5 设LA与LB为两个顺序存储的线性表，且元素按非递减排列，写出算法将其合并为LC，且LC中的元素也按非递减排列。6 一个由n个整数组成的线性表，请定义该线性表的一种存储构造，并用C语言编写算法，实现将n个元素中所有大于等于20的整数放在所有小于等于20的整数之后，要求算法的时间复杂度为On,空间
12、复杂度为O1。7 编写算法，计算二叉树中叶子结点的数目。8 编写一个按层次顺序同一层自左向右遍历二叉树的算法。三种基于“分配“收集的线性排序算法-计数排序、桶排序与基数排序 文中代码见原文链接：非基于比拟的排序在计算机科学中，排序是一门根底的算法技术，许多算法都要以此作为根底，不同的排序算法有着不同的时间开销与空间开销。排序算法有非常多种，如我们最常用的快速排序与堆排序等算法，这些算法需要对序列中的数据进展比拟，因为被称为基于比拟的排序。基于比拟的排序算法是不能突破O(NlogN)的。简单证明如下：N个数有N!个可能的排列情况，也就是说基于比拟的排序算法的判定树有N!个叶子结点，比拟次数至少为log(N!)=O(NlogN)(斯特林公式)。而非基于比拟的排序，如计数排序，桶排序，与在此根底上的基数排序，那么可以突破O(NlogN)时间下限。但要注意的是，非基于比拟的排序算法的使用都是有条件限制的，例如元素的大小限制，相反，基于比拟的排序那么没有这种限制(在一定范围内)。但并非因为有条件限制就会使非
