数据结构综合题参考答案.doc

数据结构综合题部分参考答案（仅供参考）一、填空1、一个算法的效率可分为_时间_效率和_空间_效率。， 2、栈的特点是_先进后出_,队列的特点是_先进先出_。 、3、在线性表的顺序存储结构中，若每个元素占L个存储单元，则第i个元素ai的存储位置为LOC(ai)=LOC(a1)+ _（i-1）*L_。4、已知一棵完全二叉树共139个结点，按照层次从左到右进行编号，根结点编号为1，则编号为60的左孩子编号为_120_右孩子编号为_121_双亲编号为_30_。、5、已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_ s-next=p-next; p-next=s;_。6、在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_哈希表查找法_。7、算法时间复杂度的分析通常有两种方法，即_事后统计_和_事前估计_的方法，通常我们对算法求时间复杂度时，采用后一种方法。 8、已知元素序列E,F,G,H,I,J,K,L,M,N经过操作XXYXXYXYXYYXXYXYYYXY以后的出栈序列（注X表示入栈，Y表示出栈）_ FHIJGLMKEN _。9、设数组A1.10,1.8的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A4,5的存储地址为_2056_；若以列序为主序顺序存储,则元素A4,5的存储地址为_2086_。10、一个二叉树中叶子结点3个，度为1的结点4个，则该二叉树共有_9_个结点。11、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_度_,对于有向图来说等于该顶点的_出度_。、12、二分查找的存储结构仅限于_顺序存储结构_,且是_有序的_。 13、设顺序循环队列Q0：m-1的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =_(F+1) % m_。14、设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为_O(n)_，在链式存储结构上实现顺序查找的平均时间复杂度为_ O(n)_。15、设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有_个指针域，_个空指针域。16、设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为_ s-next=p-next; p-next=s;_。17、设无向图G中有n个顶点和e条边，则其对应的邻接表中有_n_个表头结点和_2e_个表结点。1. 18、设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有_ m=2e_关系。19、设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为_CBA_。20、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是_4_，编号为8的左孩子结点的编号是_16_。21、下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。int index(char s , char t )i=j=0;while(istrlen(s) & jleft=p；s-right=p-right；_ p-right _=s； p-right-left=s；（设结点中的两个指针域分别为left和right）。30、设完全有向图中有n个顶点，则该完全有向图中共有_ n(n-1) _条有向条；设完全无向图中有n个顶点，则该完全无向图中共有_n(n-1)/2_条无向边。31、设关键字序列为(Kl，K2，Kn)，则用筛选法建初始堆必须从第_n/2_个元素开始进行筛选。32、设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有_14_个。33、高度为h的完全二叉树中最少有_2h-1_个结点，最多有_2h-1_个结点。34、设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是_ _12，24，35，27，18，26_。35、设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是 _12，18，24，27，35，26_。36、下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, int &i) int j=t; struct record x=rs; i=s; while(ij) while (ix.key) j=j-1; if (ij) ri=rj;i=i+1; while (_ij & ri.keyx.key _) i=i+1; if (ij) rj=ri;j=j-1; _ ri=x _;37 for(i=1，t=1，s=0；i=n；i+) t=t*i；s=s+t；的时间复杂度为 O(n) 。38下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1; rj+1=rj ;rj=temp;exchange=1;if (exchange=0) return；39下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。struct recordint key; int others;int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(lowk ) high=mid-1;else low=mid+1; return(0);40根据二叉树的定义可知二叉树共有 五 种不同的形态。二、判断题1、数据的机内表示称为数据的存储结构。（正确）2、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（）错误3、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 4、二叉树的前序序列和中序序列可以唯一确定一棵二叉树。（ ）5、一棵哈夫曼树中不存在度为1的结点。（）正确6、一个无向图的邻接矩阵中各元素之和与图中边的条数相等。（）错误7、给定一棵树，可以找到唯一的一棵二叉树与之对应。( ) 8、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（ ）9、希尔排序最后一趟与直接插入排序过程相同，因此前者一定比后者花的时间多。 ( ) 10、快速排序总比简单排序快。（ ）11、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。（ ）12、若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,6,5,4,1。（ ）13、二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法。错误14、二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（）错误15、二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（）正确16、Hash表的平均查找长度与处理冲突的方法无关。（ ）17、设某完全无向图中有n个顶点，则该完全无向图中有n(n-1)/2条边。正确18、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（ ）19、希尔排序最后一趟与直接插入排序过程相同，因此前者一定比后者花的时间多。 ( ) 20、快速排序不一定总比简单排序快。（ ）21、数据的最小单位是数据项。.( )22、多重表文件中主索引为非稠密索引，次索引为稠密索引。.( )23、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。.( )24、算法具有输入、输出、可行性、稳定性、有穷性五个特性。.( )25、数据的基本单位是数据项。.( )26、算法的复杂度分为时间复杂度和效率复杂度。.( )27、性质相同的数据元素的集合成为数据对象。.( )28、所有结点按1对1的邻接关系构成的整体就是集合结构。.( )29、散列文件不能顺序存取、只能按关键字随机存取。.( )30、数据的基本单位是数据元素。.( )31不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ）32当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）33由树转化成二叉树，该二叉树的右子树不一定为空。（ ）34线性表中的所有元素都有一个前驱元素和后继元素。（ ）35.带权无向图的最小生成树是唯一的。（ ）36.具有12个结点的完全二叉树有5个度为2的结点。（）37.关键路径是事件结点网络中的从源点到汇点的最短路径。（）38. 由树转化成二叉树，该二叉树的右子树不一定为空。（ ）39.堆排序是不稳定的排序方法。（）40.查找表是由同一类型的数据元素(或记录)构成的集合()41调用一次深度优先遍历可以访问到图中的所有顶点。（ ）42分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ）43冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）44满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）45设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ）46设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）47完全二叉树中的叶子结点只可能在最后两层中出现。（ ）48哈夫曼树中没有度数为1的结点。（ ）49对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ）50先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ）51希尔排序最后一趟与直接插入排序过程相同，因此前者一定比后者花的时间多。（ ）52二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法。（ ）三、选择题1. 数据结构是研究数据的（ ）以及它们之间的相互关系。A、理想结构，物理结构 B、理想结构，抽象结构C、物理结构，逻辑结构 D、抽象结构，逻辑结构2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。A、存储结构B、逻辑结构 C、链式存储结构D、顺序存储结构3. 一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )。 A、110 B、108C、100 D、120 4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ ）A、s-next=p;p-next=s; B、s-next=p-next;p-next=s;C、s-next=p-next;p=s; D、p-next=s;s-next=p;5. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。A、 edcbaB、decbaC、dceab D、abcde 6. 判定一个栈ST(最多元素为m0)为空的条件是（）。A、ST-top!=0 B、ST-top=0 C、ST-top!=m0 D、ST-top=m07. 栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点8. 稀疏矩阵一般的压缩存储方法有两种,即（）。A、 二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表9. 在线索化二叉树中,t所指结点没有左子树的充要条件是（）A、t-left=NULL B、t-ltag=1C、t-ltag=1且t-left=NULLD、以上都不对10. 已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（）。A、acbed B、decabC、deabc D、cedba11. 在一非空二叉树的中序遍历序列中,根结点的右边（）A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点12. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（） A、不发生改变B、发生改变C、不能确定D、以上都不对13. 对一个满二叉树,m个树叶,n个结点,深度为h,则（）A、n=h+m B、h+m=2nC、m=h-1D、n=2h-114. 在一个图中，所有顶点的度数之和等于所有边数的（）倍。A、1/2B、1C、2D、415. 具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。A、5B、6C、7D、816. 对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（）A、n B、(n-1)2C、n-1 D、n217. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A、先序遍历B、中序遍历C、后序遍历D、按层遍历18. 顺序查找法适合于存储结构为（ ）的线性表。A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储19. 采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为A、n B、n/2C、(n+1)/2D、(n-1)/220、下述几种排序方法中,平均查找长度最小的是（）答案A、插入排序B、选择排序C、快速排序D、归并排序21. 算法分析的两个主要方面是（ ）A、正确性和简单性 B、可读性和文档性C、数据复杂性和程序复杂性 D、时间复杂度和空间复杂度22. 线性表采用链式存储结构时，其地址（ ）。A、 必须是连续的 B、部分地址必须是连续的C、 一定是不连续的 D、连续与否均可以23. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。A、64B、63C、63.5D、724. 在一个单链表中，若删除p所指结点的后续结点，则执行（ ）A、p-next=p-next-next; B、p=p-next; p-next=p-next-next;C、p-next=p-next; D、p =p-next-next;25. 一个队列的入列序列是1,2,3,4,则队列的输出序列是（）。A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,126. 判定一个栈ST(最多元素为m0)为栈满的条件是（）。A、ST-top!=0 B、ST-top=0 C、ST-top!=m0-1D、ST-top=m0-127. 线性表是具有n个（ ）的有限序列（n0)A、表元素 B、字符 C、数据元素 D、数据项28. 常对数组进行的两种基本操作是（ ）A、建立与删除B、索引和修改C、查找和修改D、查找与索引29. 设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（）。A、2h B、2h-1C、2h+1D、h+130. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca31. 树最适合用来表示（）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据32. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（）存储结构。A、二叉链表B、广义表存储结构C、三叉链表D、顺序存储结构33. 具有五层结点的二叉平衡树至少有（）个结点。A、10B、12C、15D、1734. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。A、1/2B、1C、2D、435. 在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。A、n B、n+1C、n-1D、n/236. 对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（）。A、n B、n+1C、n-1D、n+e37. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。 A、先序遍历B、中序遍历C、后序遍历D、按层遍历38. 对线性表进行二分查找时,要求线性表必须（ ）。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储,且结点按关键字有序排序D、以链接方式存储,且结点按关键字有序排序39. 有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值为82的结点时,（ ）次比较后查找成功。A、1B、2C、4D、840、下述几种排序方法中,要求内存量最大的是（）。答案A、插入排序B、选择排序C、快速排序D、归并排序41组成数据的基本单位是（ C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量42设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是（ C ）。(A) 线性结构(B) 树型结构 (C) 图型结构(D) 集合43数组的逻辑结构不同于下列（ D ）的逻辑结构。(A) 线性表(B) 栈 (C) 队列(D) 树44二叉树中第i(i1)层上的结点数最多有（C ）个。(A) 2i(B) 2i(C) 2i-1(D) 2i-145设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（A ）。(A) p-next=p-next-next(B) p=p-next(C) p=p-next-next(D) p-next=p46设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。(A) 6(B) 4(C) 3(D) 247将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ C ）。(A) 100(B) 40(C) 55(D) 8048设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为（ B ）。(A) 3(B) 4(C) 5(D) 149根据二叉树的定义可知二叉树共有（ B ）种不同的形态。(A) 4(B) 5(C) 6(D) 750设有以下四种排序方法，则（ B ）的空间复杂度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序51、以下说法正确的是 （ A ）A.连通图的生成树，是该连通图的一个极小连通子图。B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。C.任何一个有向图，其全部顶点可以排成一个拓扑序列。D.有回路的图不能进行拓扑排序。52、以下说法错误的是 ( D ) A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树53、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( B ) A.完全图 B.连通图 C.有回路 D.一棵树54、将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点(B ) A.无左、右孩子 B.有左孩子，无右孩子C.有右孩子，无左孩子 D.有左、右孩子55、深度为6的二叉树最多有(B )个结点 A.64 B.63 C.32 D.3156、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（ A ）。A、128 B、127 C、126 D、25557、具有n个顶点的有向完全图最多可包含( D )条有向边。 An-1 Bn Cn(n-1)/2 Dn(n-1)58、用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为(B ) A. O(n) B. O(n+e) C. O(e) D. O(n*e)59、在有向图中，所有顶点的入度之和是所有顶点出度之和的（B）倍。 A.0.5 B. 1 C. 2 D.4 60、以下说法错误的是（B）A.用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。B.邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。C.存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（或上）三角部分就可以了D.用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。61、在一个无向图中，所有顶点的度数之和等于所有边数的（ B ）倍。A3 B2 C1 D1/262、设有6个结点的无向图，该图至少应有（A）条边能确保是一个连通图。 A. 5 B. 6 C. 7 D. 863下面关于线性表的叙述错误的是（ D ）。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现64设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B ）个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m65设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。(A) R-F(B) F-R(C) (R-F+M)M(D) (F-R+M)M66设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-167设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。(A) 9(B) 10(C) 11(D) 1268设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。(A) n-1(B) n(C) n+1(D) 2n-169设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C ）。(A) 2，3，5，8，6(B) 3，2，5，8，6(C) 3，2，5，6，8(D) 2，3，6，5，870设某无向图有n个顶点，则该无向图的邻接表中有（ B ）个表头结点。(A) 2n(B) n(C) n/2(D) n(n-1)71设无向图G中有n个顶点，则该无向图的最小生成树上有（B ）条边。(A) n(B) n-1(C) 2n(D) 2n-172设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（C ）。(A) 40，42，60，55，80，85(B) 42，45，55，60，85，80(C) 42，40，55，60，80，85(D) 42，40，60，85，55，8073（ B ）二叉排序树可以得到一个从小到大的有序序列。(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历74设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-175程序段s=i=0；do i=i+1； s=s+i；while(inext=0(C) head-next=head(D) head!=077设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（C ）。(A) 20(B) 256(C) 512(D) 102478设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（B ）。(A) 1(B) 2(C) 3(D) 479.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（D ）。(A) top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-next;80设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ C）。(A) n-i(B) n-1-i (C) n+1-i(D) 不能确定81.为查找某一特定单词在文本中出现的位置，可应用的串运算是(D ) A.插入 B.删除 C.串联接 D.子串定位82设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B ）次。(A) 25 (B) 10 (C) 7 (D) 1 83.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(C ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表84设某完全无向图中有n个顶点，则该完全无向图中有（B ）条边。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-185设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。(A) 9(B) 10(C) 11(D) 1286 在数据结构中，从逻辑上可以把数据结构分为 ( D ) A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.内部结构和外部结构 D. 线性结构和非线性结构 87 已知图的邻接表如下所示，根据算法，则从顶点V0出发按广度优先遍历的结点序列是( A )A0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 288 若进栈序列为a,b,c,d,e,则栈的不可能的输出序列是 ( B ) A. edcba B. dceab C. decba D. abcde 89把一棵树转换为二叉树后，这棵二叉树的形态是( A )。A.唯一的 B.有多种C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子90.为查找某一特定单词在文本中出现的位置，可应用的串运算是(D ) A.插入 B.删除 C.串联接 D.子串定位91.ALV树是一种平衡的二叉树，树中任一结点的(B ) A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 92. 二叉树是非线性数据结构，所以( C )。.它不能用顺序存储结构存储; B.它不能用链式存储结构存储; C.顺序存储结构和链式存储结构都能存储; D.顺序存储结构和链式存储结构都不能使用93. 用邻接表表示图进行广度优先遍历时，通常是采用( B )来实现算法的。A栈 B. 队列 C. 树 D. 图94数据的最小单位是（A ）。(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量95函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”96 深度为k的完全二叉树中最少有（D ）个结点。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-197设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m四、应用题1、下图所示的森林：(1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列；(3) 将此森林转换为相应的二叉树；参考答案：(1) 先根序列：ABCDEF;后根序列：BDEFCA；(2) 先序序列： ABCDEFGHIJK; 中序序列：BDEFCAIJKHG(3)森林转换为相应的二叉树；2、已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。参考答案：3、请画出下图的邻接矩阵和邻接表。参考答案：(1)邻接矩阵：(2)邻接表：4、图G的邻接表如下，求出其拓扑序列。13225436749859108611712899101011111212参考答案：拓扑序列如下： l 2 4 5 8 9 10 3 7 6 ll 125、已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用普里姆算法、克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边，并计算最小生成树各边上的权值之和。参考答案：普里姆算法: (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20克鲁斯卡尔算法:(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20最小生成树各边上的权值之和: 3+5+8+4+10+20=506、设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。(22，40，45，48，80，78)，(40，45，48，80，22，78)7、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。参考答案： 2, ASL = (1*1+2*2+3*4+4*2)/9=25/98、画出向小顶堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。参考答案：44444222552852834528439、已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6（2）求出在查找每一个元素概率相等情况下的平均查找长度。参考答案：（1）H(36)=36 mod 7=1; H(22)=(1+1) mod 7=2; .冲突H(15)=15 mod 7=1;.冲突 H2(22)=(2+1) mod 7=3; H(15)=(1+1) mod 7=2;H(40)=40 mod 7=5;H(63)=63 mod 7=0;H(22)=22 mod 7=1; .冲突 0 1 2 3 4 5 66336152240（2）ASL= 10设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。11设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。12设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。13设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列,并画给相应的生成树14、设一棵树T中边的集合为(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。15、给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。16、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。(1) 简单选择排序 275 275* 512 061 i = 1 061275* 512 275 i = 2 061 275* 512 275 i = 3 061 275* 275 512 (2) 快速排序 512275 275* 275*275 512 (3) 堆排序 275 275* 061 170 已经是最大堆，交换275与170 170 275* 061 275 对前3个调整 275* 170 061 275 前3个最大堆，交换275*与061 061 170 275* 275 对前2个调整 170 061 275* 275 前2个最大堆，交换170与061 061 170 275* 275 17、给出下图邻接矩阵和邻接表两种存储结构；写出图的拓扑序列。V2V1V3V6V5V41 18设给定权集W=5,7,2,3,6,8,10,请构造画出关于W的一棵赫夫曼树，并求出其加权路径长度WPL。19已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。20设有一组初始记录关键字为(45，80，47，40，22，68)，要求构造一棵二叉排序树并给出构造过程；画出删除45后的二叉排序树。21、 (1) 求树三棵树的先根序列和后根序列； (2) 求森林先序序列和中序序列；（3）把森林转换为对应的二叉树。HKECBDAGIJ22、把下面的二叉树转换为相应的森林。五、算法题1、编写算法实现将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。思路：从链上依次取下结点，按照逆序建表的方法重新建表。void Reverse ( LinkList &L ) p = L-next; / 原链表 L-next = NULL; / 新表(空表) while ( p