数据结构练习(答案).doc

《数据结构练习(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、)O(n)稳定红黑树O(nlog2n)O(nlog2n)O(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))：其中分配为O（n）；收集为O（rd）（r为基、d为“分配－收集”的趟数）习题一．填空题1．进栈序列是1、2、3、4，进栈过程中可以出栈，则可能的出栈序列有个，不可能的出栈序列是。2．具有N个元素的顺序存储的循环队列中，假定front和rear分别指向队头元素的前一位置和队尾元素的位置

3、，则判断队空的和队满的条件分别是f=r和f=rmodm+1。求此队列中元素个数的计算公式为：((r+m)-f-1)modm+1。入队运算：r:=rmodm+1。出队运算：f:=fmodm+1。3．单链表是非顺序线性的链式存储结构，链栈和链队分别是和的链式存储结构。4．线性表的顺序存储中，元素之间的逻辑关系是通过元素存储地址次序决定的，在线性表的链接存储中，元素之间的逻辑关系是通过元素存储指针地址访问决定的。5．深度为5的二叉树至多有结点数为31。6．数据结构即数据的逻辑结构包括顺性存储结构、链式存储结构、非线性结构三种类型，树型结构和图型

4、结构称为非线性结构。？？？四种基本存储方法：（1）顺序存储方法（2）链接存储方法（3）索引存储方法（4）散列存储方法二．选择题..1．有一个10阶对称矩阵，采用压缩存储方式，以行序为主序存储，A[0][0]的地址为1，则A[7][4]的地址为（C）A13B．18C．33D．402．线性表采用链表存储时其存储地址D。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以3．下列叙述中错误的是C。A．串是一种特殊的线性表，其特殊性体现在数据元素是一个字符B．栈和队列是两种特殊的线性表，栈的特点是后进先出，队列的特点是先

5、进先出。C．线性表的线性存储结构优于链式存储结构D．二维数组是其数据元素为线性表的线性表4．一棵二叉树的顺序存储结构如题图4-1所示，若中序遍历该二叉树，则遍历次序为A.A.DBEGACFHB.ABDEGCFHC.DGEBHFCAD.ABCDEFGH1234567891011121314ABCDEFGH题图4-15．设一棵二叉树的顺序存储结构如题图4-2所示，则该二叉树是C.A．完全二叉树B．满二叉树C．深度为4的二叉树D．深度为3的二叉树12345678910111234567题图4-26．设T是Huffman树，它具有6个树叶，且各树

6、叶的权分别为1，2，3，4，5，6。那么该树的非叶子结点的权之和为A。A．51B．21C．30D．497．设有一无向图的邻接矩阵如下所示，则该图所有顶点的度之和为C。abcdea01110b10101c11000d10000e01000..A．8B．9C．10D．118．已知二叉树的后序遍历序列是fedbgca，中序遍历序列是dfebagc，则该二叉树的先序遍历序列是D。A．defbagcB．abcdgefC．dbaefcgD．abdefcg9．由三个结点构成的二叉树，共有C种不同的形态。A．3B．4C．5D．610．在一个具有n个顶点的

7、无向图中，要连通全部顶点至少需要D条边A．nB．n+1C．n/2D．n-111．对线性表进行折半（二分）查找时，要求线性表必须B。A．以顺序方式存储B．以顺序方式存储且数据元素有序C．以链表方式存储D．以链表方式存储且数据元素有序12．顺序查找一个具有n个元素的线性表，其时间复杂度为A，二分查找一个具有n个元素的线性表，其时间复杂度为B。A．O(n)B．O(log2n)C．O(n2)D．O(nlog2n)13.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列中的正确位置上，此方法称为直接插入排序；从未排序序列中挑

8、选元素，并将其放入已排序序列中的一端，此方法称为直接选择排序；依次将每两个相临的有序表合并成一个有序表的排序方法称为归并排序；当两个元素比较出现反序时就相互交换位置的排序方法称为交换排序；A．