数据结构练习题一、简答题1．什么是拓扑排序？2．什么是堆积？3．图的邻接矩阵与邻接表两种存储表示法在空间代价上的差别为何？4．算法与程序的区别是什么?5．什么是堆(heap)？6．什么是栈(stack)？7．什么样的图遍历后由所有顶点和遍历时所经过的边所构成的子图一定是生成树？8．举例说明希尔(Shell)排序是否是稳定的排序方法？9．什么是遍历运算？10．什么是A VL树？11．链表中的表头指针、表头结点和开始结点有什么不同？各自所起的作用是什么？12．举例说明直接选择排序是否是稳定的排序方法？13．什么是完全二叉树(complete binary tree) ？14．什么是稀疏矩阵(sparse matrix) ？15．试述链接存储结构的优缺点。
16．什么是A VL树，它与最佳二叉排序树最主要的差别是什么？17．什么是假溢出？18．什么是排序算法的“稳定性”？19．设高度为h的二叉树中只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？20．顺序查找、折半查找和分块查找各自的平均查找长度ASL是多少？二、单选题1．顺序表中逻辑上相邻的结点其物理位置也( )。
A．一定相邻B．不必相邻C．按某种规律排列D．无要求2．下面关于串的叙述中，哪一个是不正确的? ( )A．串是字符的有限序列C．模式匹配是串的一种重要运算B．空串是由空格构成的串D．串既可以采用顺序存储，也可以采用链式存储3.某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列为( )。
A．ABCED B．DECAB C．DEABC D．BDACE4. 设二维数组A[m][n] 按列优先顺序存储且每个元素占c个单元，则元素A[i][j] 的地址为()。
A．LOC(A[0][0])+(j*m+i)*c B．LOC(A[0][0])+(i*n+j)*cC．LOC(A[0][0])+[(j-1)*m+i-1]*c D．LOC(A[0][0])+[(i-1)*n+j-1]*c5.在下述几种排序方法中，不稳定的排序方法是()。
A．直接插入排序B．冒泡排序C．直接选择排序D．归并排序6.散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值()。
A．同等概率B．最大概率C．最小概率D．平均概率7．在有n个结点的顺序表中进行插入、删除运算，平均时间复杂度为( )。
A．Ο(1)B．Ο(n)C．Ο(log2n)D．Ο(n2 )8．设s1="abc"，则strlen(s1) = ( )。
A．0 B． 1 C．2 D．39. 完全二叉树是下列情况的哪一种( )。
A．一定是满二叉树B．可能是满二叉树C．一定不是满二叉树D．不是二叉树10. 下列说法不正确的是( )。
A．图的遍历是从给定的源点出发每个顶点仅被访问一次B．遍历的基本方法有两种：深度优先遍历和广度优先遍历C．图的深度遍历不适用于有向图D．图的深度优先遍历是一个递归过程11. 数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是( )。
A．1165 B．1170 C．1175 D．118012. 在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是( )。
A．直接插入排序B．快速排序C．直接选择排序D．归并排序13．在栈中存取数据的原则是( )。
A．先进先出B．后进先出C．后进后出D．随意进出14．设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为( )。
A．求子串B．求串长C．联接D．模式匹配15. 堆的形状是一棵( )。
A．二叉排序树B．满二叉树C．完全二叉树D．A VL树16. 求图的最小生成树问题，考虑的是下面的哪一种图( )。
A．无向图B．有向图C．带权的无向图D．带权的有向图17. 广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为()。
A．( g ) B．( d ) C．c D．d18. 设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为( )。
A．Ο( 1) B．Ο(log2n) C．Ο(n) D．Ο(nlog2n)19．经过下列栈的操作后，GetTop(ST)的值是( )。
InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);A．a B．b C．1 D．220．空串与空格串是相同的，这种说法( ) 。
A．正确B．可能正确C．不正确D．可能不正确21. 在线索二叉树中，p所指结点没有右子树的充要条件是( )。
A．p->rchild == NULL B．p->rtag == 1C．p->rtag == 1且p->rchild == NULL D．p->rtag == 022. 有n个顶点的无向连通图的边数最少为( )。
A．n/2 B．n-1C．n D．n+123. 设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为( )。
A．1和1B．1和3 C．1和2 D．2和324. 折半查找要求结点( )。
A．无序、顺序存储B．无序、链接存储C．有序、顺序存储D．有序、链接存储25．一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是( )。
A．acbd B．abcd C．dbca D．adcb26．串是一种特殊的线性表，其特殊性体现在( )。
A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符27. 在k叉树中，无父母的结点称为( )。
A．根B．叶C．祖先D．子孙28. 采用邻接表存储的图的广度优先遍历类似于二叉树的( )。
A．前序遍历B．中序遍历C．后序遍历D．层次遍历29. 下列四个序列中，哪一个是堆( ) 。
A．75 , 65 , 30 , 15 , 25 , 45 , 20 , 10 B．75 , 65 , 45 , 10 , 30 , 25 , 20 , 15C．75 , 45 , 65 , 30 , 15 , 25 , 20 , 10 D．75 , 45 , 65 , 10 , 25 , 30 , 20 , 1530. 如果要求线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )。
A．顺序查找B．折半查找C．分块查找D．基于属性的查找三、判断题1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。
（）2．链表中的表头结点仅起到标识的作用。
（）3．哈夫曼树是带权(外部)路径长度最短的树，路径上权值较大的结点离根较近。
（）4.在有向图中，度为0的顶点称为终端顶点(或叶子)。
（）5.归并排序在任何情况下都比所有简单的排序方法速度快。
（）6. 折半查找法的查找速度一定比顺序查找法快。
（）7. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。
（）8．循环链表不是线性表。
（）9．完全二叉树的存储结构通常采用顺序存储结构。
（）10. 无向图的邻接矩阵可用一维数组存储。
（）11. 归并排序的辅助存储空间代价为O( 1 )。
（）12. 分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
（）13. 为了方便的插入和删除数据，可以使用双向链表来存放数据。
（）14．给定一棵树，可以找到唯一的一棵二叉树与之对应。
（）15．邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
（）16. 当广义表中的每个元素都是原子时，广义表便成了线性表。
（）17. 堆是满二叉树。
（）18. 对一棵二又排序树按前序方法遍历得到的结点序列是从小到大的序列。
（）19. 链接存储结构属动态存储方式。
（）20. 采用二叉链表作为存储结构，树的先根遍历和相应的二叉树的前序遍历的结果是一样的。
（）21. 带权的连通无向图的最小(代价)生成树必是唯一的。
（）22. 广义表的取表尾运算，其结果通常是一个表，但有时也可能是一个单元素值。
（）23. 在待排数据基本有序的情况下，快速排序效果最好。
（）24. 在A VL树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
（）25. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。
（）26．在指定结点之后插入新结点时，双链表比单链表更方便。
（）27．二叉树的遍历只是为了在应用中找到一种线性次序。
（）28. 拓扑排序算法仅适用于有向无环图。
（）29. 数组是同类型值的集合。
（）30. 哈希法的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
（）四、填空题1. head指向的不带表头结点的单链表为空的条件是。
2．具有256个结点的完全二叉树(设根结点的层数为0)的深度为。
3．二维数组A[10][20]采用了行优先的顺序进行存储，每个元素占一个存储单元，并且A[0][0]的存储地址是300，则A[6][12]的地址是。
4.排序是将一组任意排列的记录按的值从小到大或从大到小重新排列成有序的序列。
5. 散列表的查找效率主要取决于散列表造表时选取的和。
6．数据的运算是定义在数据的结构之上的。
7. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是；在给定值为x的结点后插入一个新结点的时间复杂度是。
8. 树中结点的最大度数称为树的。
9. 为了实现图的广度优先搜索，除了对已访问的图的结点进行标记外，还需以存放被访问的结点以实现遍历。
10. 在堆排序和快速排序中，若初始记录接近正序或反序，则应选用。
11．在具有n个结点的双链表中进行插入、删除运算，其时间复杂度为。
12. 已知二叉树有50个叶结点，则该二叉树的总结点数至少是。
13. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要条有向边(弧)。
14. 选择合适的是解决应用问题的关键步骤。
15. 对于两棵具有而形状不同的二叉排序树，遍历它们得到的结点序列是一样的。
16．在有n个结点的顺序表中进行插入、删除运算，其平均时间复杂度为。
17. 二叉树的前序序列和中序序列相同的条件是。
18. 对于n个顶点、e条边的图，若采用邻接表进行存储，则空间复杂度为。
19. 对n个记录的表R [ l .. n ]进行直接选择排序，所需进行的排序码之间的比较次数为。
20. 有900个结点的线性表若采用分块查找(检索)的方法，最好每块应含有个结点；若按每块含有25个结点来分块并对索引表也采用顺序查找，则平均查找长度为。