数据结构复习题及答案

1、精选优质文档-倾情为你奉上中南大学现代远程教育课程考试（考试）复习题及参考答案数 据 结 构(使用教材：余腊生编著，人民邮电出版社出版，数据结构基于C+模板类的实现一、判断题 1 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 2 链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 3 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 4 通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 5 一个广义表的表尾总是一个广义表。 6 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，

2、然后再按条件把它逐层向下调整，直到调整到合适位置为止。 7 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。 8 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 9 直接选择排序是一种稳定的排序方法。 10 30、闭散列法通常比开散列法时间效率更高。 11 有n个结点的不同的二叉树有n!棵。 12 直接选择排序是一种不稳定的排序方法。 13 在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。 14 当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。 15 一棵3阶B_树是平

3、衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。 16 在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。 在设计再散列函数时，要求计算出的值与表的大小m互质。 17 在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。 18 折半搜索只适用于有序表，包括有序的顺序表和有序的链表。 19 如果两个串含有相同的字符，则这两个串相等。 20 数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。 21 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。

4、22 在顺序表中取出第i个元素所花费的时间与i成正比。 23 在栈满情况下不能作进栈运算，否则产生“上溢”。 24 二路归并排序的核心操作是将两个有序序列归并为一个有序序列。 25 对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点. 26 二叉排序树或者是一棵空二叉树，或者不是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子的值。 27 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 28 一个有向图的邻接表和逆邻接表中表结点的个数一定相等。 二、

5、选择题1 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为 A. O(n) B. O(n2)C. O(1) D. O(n2)2 带头结点的单链表first为空的判定条件是： A. first=NULL B. first一>1inkNULL C. first一>link=firstD. first!NUlL3 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为 A. n-2 B. n-l C. n D. n+14 在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参

6、数的（），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址5 在一棵树中， 没有前驱结点。 A. 分支结点 D. 叶结点C. 树根结点 D. 空结点6 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加 。A. 2 B. 1C. 0 D. -17 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为 的值除以9。 A. 20 B. 18C. 25 D. 228 在有向图中每个顶点的度等于该顶点的 。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差9 在基于排序码比较的排序算法中， 算法的最坏情况下的时间复

7、杂度不高于O(n1og2n)。 A. 起泡排序 B. 希尔排序C. 归并排序 D. 快速排序10 当的值较小时，散列存储通常比其他存储方式具有 的查找速度。A. 较慢 B. 较快 C. 相同 D. 不清楚11 设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳 个表项。 (设搜索成功的平均搜索长度为ASL1+l(1一)2，其中为装填因子)A. 400 B. 526 C. 624 D. 676 12 堆是一个键值序列k1,k2,.kn,对I=1,2,.|_n/2_|,满足 A. kik2ik2i+1 B. ki&l

8、t;k2i+1<k2iC. kik2i且kik2i+1(2i+1n)D. kik2i 或kik2i+1(2i+1n) 13 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上 A. 操作的有限集合 B. 映象的有限集合C. 类型的有限集合 D. 关系的有限集合14 在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为 A. n-i+1 B. iC. i+1 D. n-i15. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是 A. head=NULL B. head->next=NULLC. head!=NULL D. hea

9、d->next=head16. 引起循环队列队头位置发生变化的操作是 A. 出队 B. 入队C. 取队头元素 D. 取队尾元素17. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 A. 2，4，3，1，5，6 B. 3，2，4，1，6，5C. 4，3，2，1，5，6 D. 2，3，5，1，6，418. 字符串通常采用的两种存储方式是 A. 散列存储和索引存储 B. 索引存储和链式存储C. 顺序存储和链式存储 D. 散列存储和顺序存储19. 设主串长为n，模式串长为m(mn)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 A. m B. n

10、-mC. n-m+1 D. n20. 二维数组A1218采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A97的地址为 A. 429 B. 432C. 435 D. 43821. 对广义表L=(a,b),(c,d),(e,f)执行操作tail(tail(L)的结果是 A. (e,f) B. (e,f)C. (f) D. ( )22. 下列图示的顺序存储结构表示的二叉树是 23.n个顶点的强连通图中至少含有 A. n-1条有向边 B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边24. 对关键字序列(56，23，78，92，88，67，1

11、9，34)进行增量为3的一趟希尔排序的结果为 A. (19，23，56，34，78，67，88，92) B. 23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92) D. (19，23，67，56，34，78，92，88)25. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为 A. 4 B. 5C. 8 D. 926. 由同一关键字集合构造的各棵二叉排序树 A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同D. 其形态均相同，平均查找

12、长度也都相同27. ISAM文件和VSAM文件的区别之一是 A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，后者只能进行随机存取C. 前者建立静态索引结构，后者建立动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘28 .下列描述中正确的是 A 线性表的逻辑顺序与存储顺序总是一致的B 每种数据结构都具备三个基本运算：插入、删除和查找C 数据结构实质上包括逻辑结构和存储结构两方面的内容D 选择合适的数据结构是解决应用问题的关键步骤29.下面程序段的时间复杂度是 I=s=0While(s<n)I+;s+=I;AO(1) B.O(n) C.O(log2n)

13、 D.O(n2)30.对于顺序表来说，访问任一节点的时间复杂度是 AO(1) B.O(n) C.O(log2n) D.O(n2)31.在具有n个节点的双链表中做插入、删除运算，平均时间复杂度为 AO(1) B.O(n) C.O(log2n) D.O(n2)32.经过下列运算后，QueueFront(Q)的值是 InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x);A.a B.b C.1 D.233.一个栈的入栈序列是a,b,c，则栈的不可能输出序列是 A. acb B.abc C.bca D.cab34.循环队列是空队列的条件是 AQ->

14、rear=Q->front B.(Q->rear+1)%maxsize=Q->frontC.Q->rear=0 D.Q->front=035.设s3="I AM",s4="A TERCHER".则strcmp(s3,s4)= A.0 B.小于0 C.大于0 D.不确定36.一维数组的元素起始地址loc6=1000，元素长度为4，则loc8为 A1000 B.1004 C.1008 D.837.广义表（a,b）,c,d）的表尾是 Aa B.b C.(a,b) D.(c,d)38对于二叉树来说，第I层上至多有_个节点 A2i B

15、. 2i -1 C.2i-1 D.2i-1-139.某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF，则后序遍历序列为 ABDGCEFHA B.GDBECFHA C.BDGAECHF D.GDBEHFCA40.M叉树中，度为0的节点数称为 A根 B.叶 C.祖先 D.子孙41.已知一个图如下所示，若从顶点a出发按宽度搜索法进行遍历，则可能得到的一种顶点序列为 42.堆的形状是一棵 A二叉排序树 B.满二叉树 C.完全二义树 D.平衡二叉树43.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 A希尔排序 B.归并排序 C.插入

16、排序 D.选择排序44采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 An B.n/2 C.(n+1)/2 D.(n-1)/245.散列查找是由键值_确定散列表中的位置，进行存储或查找 A散列函数值 B.本身 C.平方 D.相反数46.顺序文件的缺点是 A不利于修改 B.读取速度慢 C.只能写不能读 D.写文件慢47 .索引文件的检索方式是直接存取或按_存取 A随机存取 B.关键字 C.间接 D.散列三、 填空题1. 若频繁地对线性表进行插入与删除操作，该线性表应采用_存储结构。2. 在双链表中，每个结点有两个指针域，一个指向_ _，另一个指向_ _。3. 空格串是_ _，其

17、长度等于_ _。4. 一个图的 表示法是唯一的，而 表示法是不唯一的。5. 对于长度为n的关键字有序的线性表，若进行顺序查找，则时间复杂度为_ _；若采用二分法查找，则时间复杂度为_ _；6. 设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是 。7. 对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，8. 在进行 运算时，可能发生栈的下溢。9. 在双向链表中，每个结点有两个指针域，一个指向_ _，另一个指向_ _。10. 由一棵二叉树的前序序列和 可唯一确定这棵二叉树。 11. 折半查找的存储结构仅限于_ _，且是_ _。12. 对于一个

18、具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 和 。13. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是_ _。 for (i=1; i<=n; i+) for (j=1; j<=i ; j+) cout<<i+j ; 14. 稀疏矩阵的压缩存储结构，一种是 表示法，而另一种是 表示法。15. 数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为 。16. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。17. 在树形结构中，树根结点没有 结点，其

19、余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以 。18. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。19. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。20. 算法的五个重要特性是_ _ , _ _ , _ _ , _ _ , _ _。21. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：q=head;while (q->next!=p) q=q->next;s= new Node; s->data=e;q->next= ; /填空s->

20、;next= ; /填空22. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p->next;p->next= _ _; /填空delete ; /填空23. 两个串相等的充分必要条件是_。24. 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元并且A00的存储地址是200，则A612的地址是_。25. 二维数组A10.205.10采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A189的地址是_。26. 求下列广义表操作的结果：(1) GetTailGetHead(a,b),(c,d);(2) GetTailGet

21、HeadGetTail(a,b),(c,d)27. n个顶点的连通图至少_条边。28. 在无权图G的邻接矩阵A中，若(vi,vj)或vi,vj属于图G的边集合，则对应元素Aij等于_，否则等于_。29. 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是_。30. 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是_。31. 如果含n个顶点的图形成一个环，则它有 棵生成树。32. 一个非连通无向图，共有28条边，则该图至少有 个顶点。33. 遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ，DFS遍历图的时间复杂度为 ，两者不同之处在于 ，反映在数据结构上的差别是 。3

22、4. 顺序查找法的平均查找长度为_；折半查找法的平均查找长度为_；哈希表查找法采用链接法处理冲突时的平均查找长度为_。35. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_。36. 折半查找的存储结构仅限于_，且是_。37. 假设在有序线性表A1.20上进行折半查找，则比较一次查找成功的结点数为_，则比较二次查找成功的结点数为_，则比较三次查找成功的结点数为_，则比较四次查找成功的结点数为_，则比较五次查找成功的结点数为_，平均查找长度为_。38. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为_；若采用折半法查找，则时间复杂度为_；39. 已知有序表为（12，18，24，

23、35，47，50，62，83，90，115，134），当用折半查找90时，需进行 次查找可确定成功；查找47时，需进行 次查找成功；查找100时，需进行 次查找才能确定不成功。40. 二叉排序树的查找长度不仅与 有关，也与二叉排序树的 有关。41. 一个无序序列可以通过构造一棵 树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。42. 在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用而使用的栈所能达到的最大深度为_，共需递归调用的次数为_，其中第二次递归调用是对_一组记录进行快速排序。43. 在堆排序，快速排序和归并排序中

24、，若只从存储空间考虑，则应首先选取_方法，其次选取_方法，最后选取_方法；若只从排序结果的稳定性考虑，则应选取_方法；若只从平均情况下排序最快考虑，则应选取_方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_方法。四、 计算与算法应用题1.给定表（119，14，22，1，66，21，83，27，56，13，10）请按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均长度。（9分）2.已知一个有向图的顶点集V和边集G分别为：V=a,b,c,d,e,f,g,hE=<a,b>,<a,c>,<b,f>,<c,d>,<c,

25、e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。（9分）3. 设散列表的长度为13，散列函数为H（h）= k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（8分） 0 1 2 3 4 5 6 7 8 9 10 11 12 4.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。(1)假设关键字集合为1,2,3,4,5,6,7，

26、试举出能达到上述结果的初始关键字序列；(2)对所举序列进行快速排序，写出排序过程。（分）5. 如图所示二叉树，回答下列问题。（9分）6.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。7.已知一组记录的排序码为（ 46 ， 79 ， 56 ， 38 ， 40 ， 80,   95 ， 24 ），写出对其进行快速排序的每一次划分结果。 8.  一个线性表为 B= （ 12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31

27、 ， 15 ， 36 ），设散列表为 HT0.12 ，散列函数为 H （ key ） = key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 9.  已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJ ，中序遍历的结果是 EBCDAFHIGJ ，试写出这棵二叉树的后序遍历结果。10. 假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用H(K)=K9作为散列函数，若分别采用线性探查法和链接法处理冲突，则对应的平均查找长度分别为和 。11假定一组记录的排序码为(46，79，56，38，40，80，25，34，

28、57，21)，则对其进行快速排序的第一次划分后又对左、右两个子区间分别进行一次划分，得到的结果为： 。12. 下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。其中A、B、C的选择有：(1) V1,V2,V3,V4,V5,V6,V7,V8(2) V1,V2,V4,V6,V5,V3,V7,V8(3) V1,V2,V4,V6,V3,V5,V7,V8(4) V1,V2,V4,V6,V7,V3,V5,V8(5

29、) V1,V2,V3,V8,V4,V5,V6,V7(6) V1,V2,V3,V8,V4,V5,V7,V6(7) V1,V2,V3,V8,V5,V7,V4,V6D、E的选择有：       V1,V2,V4,V5,V3,V8       V1,V6,V5,V3,V8       V1,V6,V7,V8       V1,V2,V5,V7,V8 

30、60;         13.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。14. 已知如图所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。 另外，还要求大家熟练掌握Huffman树的构建方法，树与二叉树之间的转换，以及各种排序方法的排序过程。五、阅读下列算法，分析它的作用/ 类定义typedef int ElemType ;struct NodeType ElemType data; NodeType

31、*next;class LinkList private:NodeType *Head ; public:LinkList();LinkList();int sum();void creat();/.; ;1. 阅读下列算法，说明该算法的作用。int LinkList:sum( ) int x;NodeType *p;p=Head->next; while(p!=NULL) x+; p=p->next;return x; / pop 2读下述算法，说明本算法完成什么功能。 void Btree :inordern( bnode *p, int &n ) if ( p!=NU

32、LL) inordern( p->lch, n); if ( p->lch=NULL && p->rch=NULL) n+; inordern( p->rch, n); / inordern装订线3. 下列函数是二叉排序树的什么算法？如果K值为5，针对下图所示二叉树，运行下列算法，输出是什么？比较几次得到结果？Void Bstree:Search( KeyType K) int flag = 0; BstNode *q=root, *p = NULL; while(q!=NULL)&&(flag=0) if(q->key=K) fl

33、ag = 1; else if ( K<q->key) p = q; q = q->lch; else p = q; q = q->rch; if(flag = 0) cout<<"n 查找失败，无此结点！n" else cout<<"n 查找成功，找到："<<q->key<<endl;785249294.假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 1，请写出输出结果。# include < iostream.h># include <

34、; stdlib.h >consst int stackmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize; int top;# include “stack.h”Void main ( ) stack a; initstack(a); int x; cin >>x; while (x! = -1) push (a, x ); cin >>x;while (!stackempty (a) cout <<pop (a) <<” ;cout <

35、;<end1;该算法的输出结果为：_. 5. 阅读以下二叉树操作算法，指出该算法的功能。Template <calss type > void BinTree <Type> ：unknown (BinTreeNode<Type>*t) BinTreeNode< Type> *p =t, *temp; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 该

36、算法的功能是：_6. void AA (LNode * HL,const ElemType & item) LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL; while ( p->next!=HL ) p=p->next;newptr->next=HL;p->next=newptr;对于结点类型为LNode的单链表，以上算法的功能为：7. void BB(List &L)int i=0;while (i<L.size)int j=i+1;while (j<L.size)

37、if(L.listj = =L.list)for (int k=j+1;k<L.size;k+)L.listk-1=L.listk;L.size-;else j+;i+;以上算法的功能为：9. void CC(BTreeNode * & BST )ElemType a6 =45，23，78，35，77，25；BST=NULL；for( int i=0,i<6;i+)Insert(BST , ai);调用该算法后，生成的二叉搜索数的中序序列为：9. void DD ( )ElemType A =1,3,5,7,9,2,4,6,8,10,B10;TwoMerge(A, B,0,

38、4,9);for ( int i=0; i<10; i+)cout<<Bi<<” “;cout<<endl; 调用该算法后，输出结果为：/ 类定义const int MAX=20;typedef char ElemType ;class Sqstack private:ElemType elem MAX;int top ; public:Sqstack()top=0;ElemType pop();void push(ElemType x);/.; ;10. 阅读下列算法，说明该算法的作用。ElemTtype Sqstack:pop( ) ElemTyp

39、e x; if ( top=0 ) x=-999; else x = elemtop; top-;return x; / pop 11. / 类定义const int MAX=20;typedef char ElemType ;class Sqstack private:ElemType elem MAX;int top ; public:Sqstack()top=0;ElemType pop();void push(ElemType x);/.; ;阅读下列算法，说明该算法的作用。void Sqstack:push(ElemType x ) if ( top=MAX-1 )cout<&

40、lt;”n 满！”；else top+; elemtop=x; / push 六、算法设计题1. 已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。2. 编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回true，否则返回false。 bool Find（BtreeNode*BST，ElemType&item）3. 编写算法，将一个结点类型为 Lnode 的单链表按逆序链接，即若原单链表中存储元素的次序为 a 1 ， a n-1 ， a n ，则逆序链接后变为 , a

41、n ， a n-1 ， a 1 。 4.根据下面函数原型，编写一个递归算法，统计并返回以BT为树根指针的二叉树中所有叶子结点的个数。 int Count(BTreeNode * BT)；5. 设A=(a1,.,am)和B=(b1,.,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'=空表，而B'空表，或者两者均不为空表，且A'的首元小于B'的首元，则A<B；否则A>B。试写一个比较A，B大小的算法。6.已知单链表a和b的元素按值递增有序排列, 编写算法归并a和b得

42、到新的单链表c，c的元素按值递减有序。7. 编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。8. 编写算法判别T是否为二叉排序树.9. 已知带头结点的单链表是一个递增有序表，试写一算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。7Head97b15502610. 编写一个算法，返回二叉查找树中的关键字最小的元素值。参考答案一、 判断题 （每题1分）1 2× 3 4× 5 6 7× 8× 9× 10×11 ×

43、; 12 13 × 14 15 × 16 17 × 18 ×19. ×20. × 21. 22. × 23. 24. 25. × 26. × 27. × 28. 二、单项选择题（每题2分）1A 2B 3B 4D 5C 6A 7C 8C 9C 10B 11A 12 C 13.   B   14.    D   15.    A   16.    A&

44、#160;  17.    D   18.    C   19.   C   20.    A   21.    B   22.   A   23.   B   24.   D   25.   C     26

45、.   B   27   C   28.D 29.B 30.A 31.A 32.B 33.D 34.A 35. C 36.C37.D 38.C 39.D 40.A 41.B 42.C 43.D 44.C 45.A 46.A 47.B三、填空题1. 链式存储结构 2. 前驱结点 ， 后继结点3. 由一个或多个空格字符组成的串， 其包含的空格个数4. 邻接矩阵 ， 邻接表5. O（n）， O(log2n)6. 1044 7. 入栈（插入） ， 出栈（删除） 8. 前驱结点 ， 后继结点 9. 中序序列 10. 顺序存储结构 ， 有序的 11. n ， n-1a) 最大语句频度: