数据结构练习题23463

1、数据结构练习题一、简答题1什么是拓扑排序？2什么是堆积？3图的邻接矩阵与邻接表两种存储表示法在空间代价上的差别为何？4算法与程序的区别是什么?5什么是堆(heap)？6什么是栈(stack)？7什么样的图遍历后由所有顶点和遍历时所经过的边所构成的子图一定是生成树？8举例说明希尔(Shell)排序是否是稳定的排序方法？9什么是遍历运算？10什么是AVL树？11链表中的表头指针、表头结点和开始结点有什么不同？各自所起的作用是什么？12举例说明直接选择排序是否是稳定的排序方法？13什么是完全二叉树(complete binary tree) ？14什么是稀疏矩阵(sparse matrix) ？15

2、试述链接存储结构的优缺点。16什么是AVL树，它与最佳二叉排序树最主要的差别是什么 ？17什么是假溢出 ？18什么是排序算法的“稳定性”？19设高度为h的二叉树中只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少 ？20顺序查找、折半查找和分块查找各自的平均查找长度ASL是多少 ？二、单选题1顺序表中逻辑上相邻的结点其物理位置也 ( )。A一定相邻 B不必相邻 C按某种规律排列 D无要求2下面关于串的叙述中，哪一个是不正确的? ( )A串是字符的有限序列 C模式匹配是串的一种重要运算B空串是由空格构成的串 D串既可以采用顺序存储，也可以采用链式存储3. 某二叉树结

3、点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列为 ( )。A ABCED B DECAB C DEABC D BDACE4. 设二维数组Amn 按列优先顺序存储且每个元素占c个单元，则元素Aij 的地址为 ( )。ALOC(A00) + (j*m+i)*c BLOC(A00) + (i*n+j)*cCLOC(A00) + (j-1)*m+i-1*c DLOC(A00) + (i-1)*n+j-1*c5. 在下述几种排序方法中，不稳定的排序方法是 ( )。A直接插入排序 B冒泡排序C直接选择排序 D归并排序6. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其

4、值域的每个值 ( )。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图的深度优先遍历是

5、一个递归过程11. 数组A6,7 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5,5 的地址是 ( )。A1165 B1170 C1175 D118012. 在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ( )。A直接插入排序 B快速排序C直接选择排序 D归并排序13在栈中存取数据的原则是 ( )。A先进先出 B后进先出 C后进后出 D随意进出14设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。A求子串 B求串长 C联接 D模式匹配15. 堆的形状是一棵 ( )。A二叉排序树 B满二叉树 C完全二叉树 DAVL树

6、16. 求图的最小生成树问题，考虑的是下面的哪一种图 ( )。A无向图 B有向图 C带权的无向图 D带权的有向图17. 广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ( )。A( g ) B( d ) Cc Dd18. 设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为( )。A( 1 ) B(log2n) C(n) D(nlog2n)19经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'

7、;a'); push(ST,'b'); pop(ST,x);Aa Bb C1 D220空串与空格串是相同的，这种说法 ( ) 。A正确 B可能正确 C不正确 D可能不正确21. 在线索二叉树中，p所指结点没有右子树的充要条件是 ( )。Ap->rchild = = NULL Bp->rtag = = 1Cp->rtag = = 1且p->rchild = = NULL Dp->rtag = = 022. 有n个顶点的无向连通图的边数最少为 ( )。An/2 Bn-1 Cn Dn+123. 设广义表L = ( ( a , b , c ) )，

8、则L的长度和深度分别为 ( )。A1和1 B1和3 C1和2 D2和324. 折半查找要求结点 ( )。A无序、顺序存储 B无序、链接存储C有序、顺序存储 D有序、链接存储25一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是 ( )。Aacbd Babcd Cdbca Dadcb26串是一种特殊的线性表，其特殊性体现在 ( )。A可以顺序存储 B数据元素是一个字符C可以链接存储 D数据元素可以是多个字符27. 在k叉树中，无父母的结点称为 ( )。A根 B叶 C祖先 D子孙28. 采用邻接表存储的图的广度优先遍历类似于二叉树的 ( )。A前序遍历 B中序遍历 C后序遍历 D层次遍历2

9、9. 下列四个序列中，哪一个是堆 ( ) 。A75 , 65 , 30 , 15 , 25 , 45 , 20 , 10 B75 , 65 , 45 , 10 , 30 , 25 , 20 , 15C75 , 45 , 65 , 30 , 15 , 25 , 20 , 10 D75 , 45 , 65 , 10 , 25 , 30 , 20 , 1530. 如果要求线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ( )。A顺序查找 B折半查找 C分块查找 D基于属性的查找三、判断题1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）2链表中的表头结点仅起到标识的作用

10、。（ ）3哈夫曼树是带权 ( 外部 ) 路径长度最短的树，路径上权值较大的结点离根较近。（ ）4. 在有向图中，度为0的顶点称为终端顶点(或叶子)。（ ）5. 归并排序在任何情况下都比所有简单的排序方法速度快。（ ）6. 折半查找法的查找速度一定比顺序查找法快。（ ）7. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。（ ）8循环链表不是线性表。（ ）9完全二叉树的存储结构通常采用顺序存储结构。（ ）10. 无向图的邻接矩阵可用一维数组存储。（ ）11. 归并排序的辅助存储空间代价为O( 1 )。（ ）12. 分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中

11、的元素个数有关。（ ）13. 为了方便的插入和删除数据，可以使用双向链表来存放数据。（ ）14给定一棵树，可以找到唯一的一棵二叉树与之对应。（ ）15邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ ）16. 当广义表中的每个元素都是原子时，广义表便成了线性表。（ ）17. 堆是满二叉树。（ ）18. 对一棵二又排序树按前序方法遍历得到的结点序列是从小到大的序列。（ ）19. 链接存储结构属动态存储方式。（ ）20. 采用二叉链表作为存储结构，树的先根遍历和相应的二叉树的前序遍历的结果是一样的。（ ）21. 带权的连通无向图的最小(代价)

12、生成树必是唯一的。（ ）22. 广义表的取表尾运算，其结果通常是一个表，但有时也可能是一个单元素值。（ ）23. 在待排数据基本有序的情况下，快速排序效果最好。（ ）24. 在AVL树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）25. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。（ ）26在指定结点之后插入新结点时，双链表比单链表更方便。（ ）27二叉树的遍历只是为了在应用中找到一种线性次序。（ ）28. 拓扑排序算法仅适用于有向无环图。（ ）29. 数组是同类型值的集合。（ ）30. 哈希法的平均查找长度不随表中结点数目的增加而增加，

13、而是随负载因子的增大而增大。（ ）四、填空题1. head指向的不带表头结点的单链表为空的条件是 。2具有256个结点的完全二叉树 ( 设根结点的层数为0 ) 的深度为 。3二维数组A1020采用了行优先的顺序进行存储，每个元素占一个存储单元，并且A00的存储地址是300，则A612的地址是 。4. 排序是将一组任意排列的记录按 的值从小到大或从大到小重新排列成有序的序列。5. 散列表的查找效率主要取决于散列表造表时选取的 和 。6数据的运算是定义在数据的 结构之上的。7. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是 ；在给定值为x的结点后插入一个新结点的时间

14、复杂度是 。8. 树中结点的最大度数称为树的 。9. 为了实现图的广度优先搜索，除了对已访问的图的结点进行标记外，还需 以存放被访问的结点以实现遍历。10. 在堆排序和快速排序中，若初始记录接近正序或反序，则应选用 。 11在具有n个结点的双链表中进行插入、删除运算，其时间复杂度为 。12. 已知二叉树有50个叶结点，则该二叉树的总结点数至少是 。13. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 条有向边( 弧 )。14. 选择合适的 是解决应用问题的关键步骤。15. 对于两棵具有 而形状不同的二叉排序树， 遍历它们得到的结点序列是一样的。16在有n个结点的顺序表中进行

15、插入、删除运算，其平均时间复杂度为 。17. 二叉树的前序序列和中序序列相同的条件是 。18. 对于n个顶点、e条边的图，若采用邻接表进行存储，则空间复杂度为 。19. 对n个记录的表R l . n 进行直接选择排序，所需进行的排序码之间的比较次数为 。20. 有900个结点的线性表若采用分块查找(检索)的方法，最好每块应含有 个结点；若按每块含有25个结点来分块并对索引表也采用顺序查找，则平均查找长度为 。21一个栈的输入序列是：1, 2, 3，则不可能的栈输出序列是 。22. 设S = Iamastudent，其长度是 。23. 哈夫曼树是带权(外部)路径长度 的二叉树。24. 用迪杰斯特

16、拉(Dijkstra)算法求某一顶点到其他各顶点的最短路径是按最短路径长度 的次序来产生最短路径的。25. 在数据表有序时，快速排序算法的时间复杂度是 。26. 若对线性表进行折半查找，则对表的要求是 。五、图示题1设待排序文件的初始排序码序列为 85, 42, 70, 19, 10, 38, 17, 56, 33, 49, 57 ，写出采用希尔(Shell)排序算法排序时(取d1=5 )，每趟结束时的状态。2对于右下图所示的带权无向图，请画出它的一棵最小生成树。3对于右下图所示的二叉树，请完成： 画出此二叉树对应的树(林)； 画出其前序线索二叉树。 4对于右下图所示的二叉树，请完成： 画出此

17、二叉树对应的树(林)； 画出其前序线索二叉树。解： 此二叉树对应的树林 前序线索二叉树 结点的前序序列为： GFAIHBCED 5根据给定的一组关键字 36,48,25,65,34,62,16,71,56,40 ，请完成： 按关键字从前向后的次序建立此二叉排序树； 计算在等概率的情况下查找成功的平均查找长度ASL。解： 二叉排序树 查找成功的平均查找长度ASL = (1+2+2+3+3+3+3+4+4+5)/10 = 30/10 = 3 6根据给定的一组关键字 36,48,25,65,34,62,16,71,56,40 ，请完成： 按关键字从前向后的次序建立此二叉排序树； 计算在等概率的情况下

18、查找成功的平均查找长度ASL。7已知一棵二叉树结点的中序序列和后序序列分别为DKHBCFAIGJE和KHDBFIJGEAC，请画出此二叉树及它所对应的树(林)。8若在有序表（05，11，20，26，32，38，43，47，56，61，69，72，86）中进行折半查找，试分别画出查找关键字为11和70的过程。9设有待排序文件为 35,22,18,44,57,06,请给出直接选择排序的过程，即给出每趟结束后的状态。10设有关键字集合为 35,08,21,15,24,03,48,33 ，散列表的长度为12，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。11根据右下图所示的森林，求解如下问题： 写出后根次序(后序)遍历此森林的结点序列； 将此森林转换成对应的二叉树。 12对于长度为12的表（44，05，81，24，19，32，28，35，49，56，53，41），请画出它的最佳二叉排序树，并求其在等概率情况下查找成功的平均查找长度ASL。六、算法题1.设计一个算法，使得在尽可能少的时间内重排数组，将所有负值的数据都放在所有非负值的数据之前。请分析算法的时间复杂度(要求写出存储结构的描述)。2.设有n个结点的二叉树用二叉链表(即lchild-rchild表