应本数据结构试卷

1、2013年一、单项选择题1.以下数据结构是非线性结构的是( D)。A. 队列 B. 栈 C. 线性表 D. 二叉树2设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B）。A 5，3，4，6，1，2B 3，2，5，6，4，1C 3，1，2，5，4，6D 1，5，4，6，2，33.引起循环队列队头位置发生变化的操作是(A)。A.出队B.入队 C.取队头元素D.取队尾元素4采用散列技术实现表的存储和查找 ，需解决的主要问题是（ D ）。A如何申请到足够大的空间 B如何正确认识元素之间的逻辑关系 C如何找到一个好的查找方法 D如何构造一个散列地址均匀分布的散列函数5广义表A

2、=(a,(b),(), c,( d,e)的长度为( B ) A.4 B.5 C.6 D.7 6.树结构最适合用来表示( C )。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据7设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到的序列为（ A ）。ABADCBBCDACCDABDCBDA8设某棵二叉树中有1000个结点，则该二叉树的最小高度为（ B ）。A9B10C11D129.已知森林F=T1，T2，T3，T4，T5，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，1，4，则与F对应的二叉树

3、的右子树中结点个数为(D )。A.2 B.3 C.11 D.1310.除根结点外，树上每个结点( A )A.可有任意多个孩子、一个双亲B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D.只有一个孩子、一个双亲11.设某散列表的长度为10，散列函数H(k)=k%P，则P通常情况下最好选择（B ）。A9B 7C 1D 312数据的基本单位是（ C ）。A.数据项B.数据类型C.数据元素D.数据变量13下面程序的时间复杂度为( )。for（i=1，s=0； i=n； i+） t=1;for(j=1；jnext=s；front=s；Bs-next=rear；rear=s；Crear-n

4、ext=s；rear=s；Ds-next=front；front=s；17如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（C）。A.栈 B.队列 C.树 D.图18下面关于线性表的叙述错误的是（ D ）。A线性表采用顺序存储必须占用一片连续的存储空间B线性表采用链式存储不必占用一片连续的存储空间C线性表采用链式存储便于插入和删除操作的实现D线性表采用顺序存储便于插入和删除操作的实现19.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作序列是（D ）。A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX2

5、0多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（C）。A数组的元素处在行和列两个关系中B数组的元素必须从左到右顺序排列C数组的元素之间存在次序关系D数组是多维结构，内存是一维结构21. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为7的元素个数为（ B ）。A1 B2 C3 D422设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（B ）。A小于等于m的最大奇数B小于等于m的最大素数C大于等于m的最大奇数D大于等于m的最大素数23若有序表的关键字序列为（b,c,d,e,f,g

6、,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（B）。Af,c,b Bf,d,b Cg,c,b Dg,d,b24判断一个顺序栈st（最多元素为StackSize）为栈满的条件表达式是（D）。Ast.top!= StackSize Bst.top!=0 Cst.top=-1 Dst.top=StackSize-125以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n0），空链域的个数为（B）。A2n-1 Bn+1 Cn-1 D2n+126下列程序段的时间复杂度为（ C ）。i=0,s=0; while(in) s=s+i;i+;AO(n1/2)BO(n1

7、/3)CO(n)DO(n2)27算法指的是（ D ）。A计算机程序 B运算方法C排序方法 D解决问题的方法或步骤28在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A插入B删除 C排序D查找29在一个长度为n的顺序表中，向第i个元素(1in)之前插入一个元素时，需要依次后移元素个数为（B）。An-i Bn-i+1 Cn-i-1 Di30设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。AR-FBF-RC(R-F+M)MD(F-R+M)M31从广义表LS（(p,q)

8、,r,s）中分解出原子q的运算是（A）。Atail(head(LS)Bhead(tail(head(LS)Chead(tail(LS)Dtail(tail(head(LS)32已知广义表的表头为A，表尾为(B,C)，则此广义表为（C ）。A.(A,(B,C) B.（A）,B,C）C.(A,B,C) D.(A,B,C)33. 二叉树的第k层的结点数最多为（ D ）。A2k-1 B.2k+1 C.2k-1 D. 2k-134. 设一棵完全二叉树中有60个结点，则该完全二叉树的深度为（C ）。A8B7C6D535.某二叉树的前序和后序序列正好相同，则该二叉树的特点是（A ）。A空或者只有一个结点 B

9、高度等于其结点数C任一结点无左孩子 D任一结点无右孩子36设输入序列是1、2、3、n，经过栈的操作后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ A ）。An-iBn-1-iCn+1-iD不能确定37设一棵二叉树的深度为k，则该二叉树中最多有的结点个数为（D）。A2k-1B2kC2k-1D2k-138. 下列有关二叉树的说法中正确的是（ B ）。A二叉树的度一定为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为239设某三叉树中有40个结点，则该三叉树的最小高度为（ B ）。A3B4C5D640设F是由T1、T2和T3三棵树组成的森林

10、，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的右子树的结点数为（ C ）。 AN1-1BN2-1CN2+N3DN1+N341采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ B ）。 A n B (n+1)/2 Cn/2 D (n-1)/242下列程序段的时间复杂度为（A ）。s=i=0；do i=i+1； s=s+i；while(i=n)；A. O(n)B. O(nlog2n)C. O(n2)D. O(n3/2)43在数据结构中，数据的逻辑结构可以分成（B）。A内部结构和外部结构 B线性结构和非线性结构C紧凑结构和非紧凑结构D动态结构和

11、静态结构44根据数据元素的关键字直接计算出该元素存储地址的存储方法是（D）。A顺序存储方法B链式存储方法 C索引存储方法D散列存储方法45若一个算法的时间复杂度用T(n)表示，其中n的含义是（ B ）。A问题规模 B语句条数C循环层数 D函数数量46设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行入队操作后其头指针rear值为（ D ）。Afront=front+1 Brear=rear+1Cfront=(front+1)%m Drear =( rear +1)%m47队列和栈的主要区别是（D ）。A.逻辑结构不同 B.存储结构不同C.所包含的运算个

12、数不同 D.限定插入和删除的位置不同48设有一个二维数组Amn，假设A00存放位置为644，A22存放位置为676，每个元素占一个存储空间，则A33存放位置为（ C）。 A688 B678 C692 D69649.对广义表L=(a,b),(c,d),(e,f)执行操作tail(tail(L)的结果是(B)。A.(e,f) B.(e,f) C.(f)D.()50设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为m的结点数为Nm，则N0=（ B）。ANl+N2+NmBl+N2+2N3+3N4+(m-1)NmCN2+2N3+3N4+(m-1)NmD2Nl+3N2+(m+1)Nm51

13、. 深度为k的完全二叉树中最少结点个数为（ B ）。A2k-1-1B2k-1C2k-1+1D2k-152设按照从上到下、从左到右的顺序，从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。A2i+1B2iCi/2D2i-153除第一层外，满二叉树中每一层结点个数是上一层结点个数的（C）。A1/2倍B1倍 C2倍D3倍54.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序从前往后扫描的第一趟冒泡排序结束后的结果是（ D ）。AF，H，C，D，P，A，M，Q，R，S，Y，XBP，A，C，S，Q，D，F，X，R，H，M，YCA，D，C，

14、R，F，Q，M，S，Y，P，H，XDH，C，Q，P，A，M，S，R，D，F，X，Y55.设一个顺序有序表A114中有14个元素，则采用二分法查找元素A4的过程中比较元素的顺序为( C )。AA1，A2，A3，A4BA1，A14，A7，A4CA7，A3，A5，A4DA7，A5 ，A3，A456线性表若采用链式存储结构时，要求内存中可用存储单元地址(A )。A不一定是连续的 B部分地址必须是连续的C必须是连续的D一定是不连续的57.一棵含18个结点的二叉树的高度至少为( C ) 。 A.3 B.4 C.5 D.6 58若有18个元素的有序表存放在一维数组A118中，第一个元素存放在A1中，现进行二

15、分查找，则查找A3的比较序列依次为( )。A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，359能进行二分查找的线性表,必须以（A）。A顺序方式存储,且元素按关键字有序B链式方式存储,且元素按关键字有序C顺序方式存储,且元素按关键字分块有序D链式方式存储,且元素按关键字分块有序60对于哈希函数H(key)=key%13，被称为同义词的关键字是( D )。A35和41 B.23和39C.15和44 D.25和5161.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。A. O(n)B. O(nlog2n)C. O(1)D. O(n2)62算法分析

16、的目的是（B）。A辨别数据结构的合理性 B评价算法的效率C研究算法中输入与输出的关系 D鉴别算法的可读性63具有线性结构的数据结构是（ C ）。A树 B多维数组 C栈和队列 D广义表64.广义表L= (a，()的表尾是( B)。A.() B.()C.a D.(a)65设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ D ）。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子66 在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（D）。Ai Bi+1 Cn-iDn-i+16

17、7若栈采用顺序存储结构，则下列说法中正确的是（ ）。A需要判断栈满且需要判断栈空B不需要判断栈满但需要判断栈空C需要判断栈满但不需要判断栈空D不需要判断栈满也不需要判断栈空68在任意一棵二叉树的前序序列和后序序列中，各叶子结点之间的相对次序关系（B）。A不一定相同 B都相同 C都不相同 D互为逆序69利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ C）。AO(n)BO(nlog2n)CO(n2)DO(log2n)70.假定一个顺序队列的队头和队尾指针分别为f和r，则判断队空的条件为 （ D ）。Af+1=r Br+1=f Cf=0 Df=r71一个非空广义表的表尾（ B ）。A不可

18、能是子表 B只能是子表C只能是原子 D可以是子表或原子72.二维数组A45采用行优先的存储方法，若每个元素占2个存储单元，且第1个元素的地址为100，则元素A23的地址为(A)。A.126B.125 C.127D.12873.设一组初始关键字的长度为9，则插入排序可以得到有序序列的最多排序趟数为（C）。A6B7C8D974查找运算主要是对关键字的（C ）。A移位B交换C比较D定位75用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( A )A.线性探测法B.除留余数法C.平方取中法D.折叠法二、填空题1所谓“就地排序”，是指排序

19、算法辅助空间的复杂度为 稳定 的排序方法。2在数据结构中，数据的存储结构有顺序存储方法、_链式存储方法_、索引存储方法和散列存储方法等四种。3.当栈空时再做退栈运算产生的溢出称为_下溢_。4.一个值的集合和定义在这个值集上的一组操作的总称是 _数据类型_。5.队列的操作是按_先进先出_原则进行的。6.去除广义表LS=(a1,a2,，an)中第1个元素，由其余元素构成的广义表称为LS的_表尾_。7已知广义表C=(a，(b，c)，d)，则tail(head(tail(C)= _(c)_。8实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_ _有序_的。9数据元素及其关系在计算机存储器

20、内的表示，称为数据的 存储结构 。10被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表是 队列 。11若待散列的序列为(18, 24，35，12，27，18，26)，散列函数为H(key)=key%9，与18发生冲突的元素有_2_个。12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为13的元素需要经过_3_次比较。13含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为_n+1_。 14对一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为_99_。15

21、对n个记录的排序文件进行冒泡排序时，最多的比较次数是_n-1_n(n-1)/2_。16.数据物理结构的主要实现方法包括两种情况：链式存储方法和_ 顺序存储方法_。17下述程序段的的时间复杂度为_O(n)_。k=1; for(i=0;in;i+) Aij=k+; 18高度为5的完全二叉树的结点数至少有 16 。19设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为 8 。20一种抽象数据类型封装的两部分是数据和 操作 。21.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法中通常选用的辅助数据结构是_顺序栈结构_。22.对一棵完全二叉树按

22、从1开始顺序编号，则编号为25的结点的双亲结点编号为_12_。23设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中共有_129_个结点。24.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为,，则该树的度是_3_。25.设一组初始关键字序列为(76，65，13，38，97，27，10)，则第1趟从前往后扫描的冒泡排序结果为_10，76，65，13，38，97，27_ _65,13,38,76,27,10,97_。26.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是_稳定_。27.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其

23、余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为_直接选择排序_。28.按照二叉树的定义，具有3个结点的二叉树有_5_种。29.解决散列表冲突的开放地址法分为线性探测法、双重散列法和_二次探查法_。30.设有一批数据元素，为了最快地存取某元素，宜用_顺序_存储结构进行存储。31数据类型按其值能否分解,通常可分为原子类型和_结构类型_两种。32.数据结构的三个方面包括_逻辑结构_、存储结构和运算。33.栈结构允许进行删除操作的一端称为_栈顶_。34假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且第一个元素a000的存储地址为100，

24、则元素a987的存储地址是 _1801_2257_。 35用广义表的取表头head和取表尾tail的运算，从广义表LS=(b,c,(f),(d)中分解出原子c的操作为_head(tail(LS)_。36.广义表L=(a，(b，( )的长度为_2_。37.任意一棵完全二叉树中，度为1的结点数最多为_1_。38.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第2趟递增的直接选择排序后的结果为_10,13,97,76,65,27,38_。39.设有序查找表中有100个元素，如果用二分法查找数据元素X，则最少需要比较_7_次就可以断定数据元素X是否在查找表中。40循环队列用数组

25、Am存放元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是_(rear-front+m) % m_。41若进栈序列为a,b,c则通过入出栈操作可能得到的a,b,c的不同排列个数为_5_。42已知一棵完全二叉树中共有768个结点，则该树中叶子结点的个数是 384 。43有一个长度为30的有序表采用二分查找方法进行查找，则查找长度为3的元素个数为 4 。44.设深度为k的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_2k-1_。45.具有n个结点的二叉树，拥有指向孩子结点的分支数目是_n-1_。46设顺序表中有n个数据元素，则在第i个位置上插入一个

26、数据元素需要移动表中_n-i n-i+1_个数据元素。47在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队头元素是_C_。48假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 bceda 。49n个结点的满二叉树的高度为 log(n+1) 。50.对一组初始关键字序列（40，50， 20，15，70，95，60，45，10）进行自前向后扫描的冒泡排序，则第一趟需要移动的记录的次数为_8_5_。51.在一般情况下用直接插入排序、直接选择排序和冒泡排序的过程中，所需记录交换次数最少的是_n-1

27、_。52.如果一个算法总的运行次数是常数，则该算法的时间复杂度为_O(1)_。53.若频繁地对线性表进行插入与删除操作，该线性表应采用_链式_存储结构。54.设顺序栈存放在S.datamaxsize中，栈底位置是maxsize-1，变量top指示栈顶元素的位置，则栈空条件是_s.top=maxsize-1 s.top=maxsize_。55.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为_ O(n2)_。56.对n个记录采用直接选择排序方法，第一趟排序所执行的记录交换次数最少为_n-1_0_。57.对一个表长为n的线性表采用顺序查找，在等概率情况下，查找成功的平均查找长度是_（n+1）/

28、2_。58.图中树T的度为_3_。59.在各种查找算法中，平均查找长度和结点的个数n无关的查找方法是_哈希表_。60.已知二叉树有7个叶子结点，且仅有一个孩子的结点数为5，则总结点数为_18_。61. 数据的链式存储结构的特点是借助 指针 表示数据元素之间的逻辑关系。62数据结构算法中，通常用空间复杂度和 时间复杂度 两种方法衡量其效率。63. 设输入序列为1、2、3，则经过入栈和出栈操作后可以得到 5 种不同的输出序列。64.栈下溢是指在栈空时进行 退栈 操作。65. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCD，则该二叉树的中序遍历序列为 DBAC 。66二分查找排序的时间复杂度

29、是 O(log2n) 。67.数据的逻辑结构在计算机存储器内的表示，称为数据的_物理结构_。68在有序表（12，24，36，48，60，72，84）中利用顺序查找关键字72时，所需进行的关键字比较次数为 6 。 69.产生冲突现象的两个关键字称为该散列函数的 同义词 。70.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有 512 个。71.设某棵二叉树中只有度数为0和度数为2的结点，且度数为0的结点数为n，则这棵二叉树中共有 2n-1 个结点。72.若一个算法中的语句频度之和为T(n)=3720n+4log2n，则算法的时间复杂度为 O(n) 。73.线性表L=（a1,a2,an）采用顺

30、序存储，假定在不同的n+1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是 0 n/2 。74.已知完全二叉树的第5层有4个结点，则其叶子结点数目是 10 。75.描述客观事物的数、字符以及能输入计算机中并被计算机处理的符号的集合被称为 数据 。三、应用综合题1、已知有6个元素A,B,C,D,E,F依次进栈，若得到的出栈序列为ADCFEB，请写出栈操作的过程。用PUSH(i)表示i进栈，POP( )表示出栈。 PUSH(i)POP(i) PUSH(i) PUSH(i) PUSH(i)POP(i)POP(i) PUSH(i) PUSH(i) POP(i) POP(i) POP(i

31、)2、已知循环队列Q的顺序存储类型定义如下：#define QueueSize 100typedef char DataType;typedef struct DataType dataQueueSize; int front,rear;CirQueue;CirQueue *Q;请分别写出判断队空和队满的条件。 队空的条件：Q-front=Q-rear; 队满的条件: (Q-rear + 1)% QueueSize = Q-front;3、设二维数组A56的每个元素占3个字节，已知Loc(a00)=100，请回答：按行优先存储时，计算a25的存储地址； a25的存储地址=100+(2*6+5)

32、*3=151按列优先存储时，写出数组A的第12个元素下标，并说明原因。 数组A的第12个元素下标=2,1 因为该数组按列存储的。每列为5个元素。4、已知三维数组Amnp按行优先顺序存储在内存中，假设每个元素占d个存储单元，第一个元素的存储地址为Loc(a000)，请写出：数组A共占的字节数=m*n*p*d数组A的任一个元素aijk的存储地址计算公式。 公式= Loc(a000)+(i*n*p+j*p+k)*d;5、请计算以下广义表的表头和表尾。(a),(b),c),(d),(e) 表头和表尾：(a)和(b),c),(d),(e) 表尾应为(b),c),(d),(e)(a,b),(c,(d,e)

33、 表头和表尾：(a,b)和(c,(d,e) 表尾应为：(c,(d,e)6、请计算以下广义表的长度和深度。(a,b,c,(d) 长度和深度:4和4 深度为2(a),(b,c,d) 长度和深度:2和2 看长度与深度的定义7、设用函数head( )、tail( )分别表示取广义表的表头和表尾操作，请写出：取出广义表A=(x,y,z),(a,b,c,d)中(y,z)的函数； 函数= tail(head(A)取出广义表A=(x,(a,b)c,d)中原子x的函数。 函数=head(A);8、设二叉树后序遍历为ABC，请画出所有可能的二叉树。 9、请画出具有3个结点的二叉树的所有不同形态。 10、树T如下图

34、所示，请回答： 树T的度；3此处有问题吧，4树T的度为3。结点I的层次和双亲结点；2层和双亲是H。从结点K到结点N是否有路径。如果有，请计算该路径长度。有，路径长度是：3 路径长度指的是线段长度吗11、有一棵完全二叉树按层次顺序存放在一维数组中，如下所示： 请回答问题：指出结点K的双亲结点；H 双亲为i/2下取整指出结点D的左孩子结点； B 左孩子为2i，右孩子为2i+1（3）计算该二叉树的度:4 12个结点log212下取整+1=412、设二叉树bt的存储结构如下：不会下标12345678910left00237580101datajhfdbacegiright0009400000其中bt为

35、树根结点指针，left、right分别为结点的左、右孩子指针域，data为结点的数据域。左、右孩子指针域均为0的是叶子结点。请完成下列各题：画出二叉树bt； 写出按前序遍历二叉树bt得到的结点序列。前序遍历二叉树bt序列：a b c e d f h g i j13、设一棵树T中边的集合为(A，B)，(A，C)，(B，D)，(C，E)，(C，F)，(C，G)，其中边（X，Y）表示X是Y的双亲。要求将该树转化成对应的二叉树。 14、将下图所示的二叉树转换成森林。 森林是： 15、将下图所示的森林转换成二叉树。二叉树是： 16、将下图所示的树转换成二叉树。 二叉树是： 此图中C改为L17、对下图所示

36、二叉树分别按前序、中序和后序遍历，给出相应的结点序列。 前序遍历是：ABDEGHCF 中序遍历是：DBGEHAFC后序遍历是：DGHEBFCA已知一棵二叉树的中序遍历结点排列为DGEHBFCA，后序遍历结点排列为DGHEBFCA，画出此二叉树，并写出该二叉树的前序遍历序列。 二叉树是： 二叉树的前序遍历序列是：ACFBEGDH:已知一棵二叉树的前序序列为ABDFCEGH，中序序列为BFDAGEHC，画出此二叉树，并写出该二叉树的后序遍历序列。 二叉树是： 二叉树的后序遍历序列是：FDBGHECA20、二叉树bt的结点采用顺序存储结构，如图所示：下标01234567891011121314151

37、6171819btEAFDGCJHIB请完成下列各题：画出二叉树bt； 写出按后序遍历二叉树bt得到的结点序列。 后序遍历二叉树bt得到的结点序列是：B C J D A H I G F E21、对下图所示的树T，画出其孩子兄弟链表存储结构。22、对关键字序列（49,38,27,13,97,76,50,65）进行直接插入排序和直接选择排序，使关键字递增有序，请写出每个排序方法的前三趟结果。1.直接插入排序： 一趟排序的结果：38， 49 , 27, 13, 97, 76, 50, 65 二趟排序的结果： 27，38，49，13，97，76，50，56 三趟排序的结果： 13，27，38，49，9

38、7，76，50，652. 直接选择排序： 一趟排序的结果：13, 38, 27, 49 , 97, 76, 50, 65 二趟排序的结果：13, 27, 38, 49 , 97, 76, 50, 65三趟排序的结果：13, 27, 38, 49 , 97, 76, 50, 6523、若对序列(87，72，69，23，94，16，5，58)采从后往前扫描的冒泡排序法进行递增排序，请写出前三趟排序的结果。 一趟排序的结果： 5，87，72，69，23，94，16，58二趟排序的结果： 5，16，87，72，69，23，94，58,三趟排序的结果： 5，16，23，87，72，69，94，58,第三

39、趟应改为： 5，16，23，87，72，69，58，94，24、已知待散列的线性表为（22，41，53，33，46，30），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K%7，若发生冲突采用线性探测法处理，请完成下列各题：（1）画出该散列表，并在散列表中标出查找每个关键字所需的比较次数；（2）计算在查找每一个元素概率相等情况下，查找成功时的平均查找长度ASL。 ASL=(1*5 +4*1)/6=1.525、已知散列函数为H(k)=k mod 11, 关键字序列为35，67，42，21，29，86，95，47，50，36，91，处理冲突的方法为拉链法，请完成下列各题：（1）画出

40、该散列表； （2）计算在等概率情况下，查找成功时的平均查找长度ASL。 ASL=(7*1+3*2+1*3)/11=1.45四、程序综合题1、 阅读下列算法，并回答问题：(1)假设数组L= 7,9,5,4,2，写出调用函数f (L,5)后L的内容； 2,4,5,7,9(2)写出上述函数调用过程中进行元素交换操作的总次数。void f (int R,int n) int i,t; for (i=0;in-1;i+) while (Ri!=i) t=RRi; RRi= Ri; Ri=t; 总次数是： 4 次2、已知线性表的存储结构为顺序存储结构，阅读下列算法，并回答问题：（1）设线性表L=（21，-

41、7，-8，19，0，-11，34，30，-10），写出执行f（&L）后L的内容；（2）简述算法的功能。void f（SeqList *L） int i,j;for （i=j=0;ilength; i+）if（L-datai=0）if（i!=j）L-dataj=L-datai;j+；L-length=j; 算法的功能：将线性表L中的非负整数取出并按顺序形成新线性表3、 阅读下列算法，并回答问题：(1)设线性表L=（3，7，11，14，20，51），写出执行f(&L,28)之后L的内容； 内容； 3，7，11，14，20，28，51(2)简述算法的功能。void f(SeqList*L, Data

42、Type x) int i =0, j; while (ilength & xL-datai) i+; if(ilength & x=L-datai) for(j=i+1;jlength;j+) L-dataj-1=L-dataj; L-length-; else for(j=L-length;ji;j-) L-dataj=L-dataj-1; L-datai=x; L-length+; 功能：如果给定x的值与线性表L中的值相等，则删除，否则按元素大小的顺序插入线性表L的对应位置。4、已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：(1)简述算法f的功能；将线性表L中大于零的数取出并按

43、顺序形成新线性表L。 (2)设线性表L=（-4，6，0，-27，11，-51，-30），写出执行f（&L）之后的L状态。void f(SeqList *L) int i,j; for( i=j=0;ilength;i +) if(L-datai) 0) if(i!=j) L-dataj=L-datai; j+; L-length=j;L的内容是：6,115、阅读下列算法，并回答问题：（1）设线性表L=（1，2，3，4，5，6），写出执行f（&L）之后的L的内容。 135246（2）写出上述函数调用过程中进行元素交换操作的总次数。void f(SeqList *L) int i,j=0,t;fo

44、r(i=0;ilength;i+) if(L- datai%2) if(i!=j) t=L- datai; L- datai=L- dataj;L- dataj=t;j+;总次数：26、阅读下列算法，并回答问题：(1)简述算法的功能； 是通过一个中间栈T，达到删除栈S中所有与变量相同的元素。 (2)假定栈S=1,3,7,9,11，写出执行算法f(S,3)后栈S中的元素内容。void f(SeqStack *S,int c)/ 设DataType 为int 型SeqStack T;int d;InitStack(&T);while(!StackEmpty(S)d=Pop(S);if(d!=c)

45、Push(T,d);while(!StackEmpty(T)d=Pop(T);Push(S,d);S中的元素内容：1,7,9,117、阅读下列算法，并回答问题：(1)简述算法的功能； 借助栈实现判断给定的字符串是否是回文，是返回1，否则返回0 (2)如果有字符串str=”abcdcba”，写出执行算法f(str)后的返回值。int f (char str)SeqStack S;int j,k,i=0;InitStack(&S);while(stri!=0) i+;for(j=0;ji/2;j+)Push(&S,strj);k=(i+1)/2;for(j=k;ji;j+)if(strj!=Pop

46、(&S) return 0;return 1; 返回值为18、阅读下列算法，并回答问题：（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f（&Q,&Q1,&Q2）之后队列Q、Q1和Q2的状态；Q为空 Q1=-5，-4，-6 Q2=1，0，2，9（2）简述算法的功能。（注：InitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入队、出队和判队空的操作）void f (Queue*Q, Queue*Q1, Queue*Q2) int e;InitQueue (Q1);InitQueue (Q2);whi

47、le (!QueueEmpty(Q) e=DeQueue(Q);if (edata);if(T-rchild)Push(&S,T-rchild);if(T-lchild) T=T-lchild;elseT=Pop(&S);输出结果：ABDCEGF10、已知具有n个结点的完全二叉树采用顺序存储结构存储在向量BT1.n中，结点的数据元素为字符类型，请阅读下列算法，并回答问题：(1)假设向量BT中的内容如下，请写出执行f(BT,6)后的输出结果；输出结果：ABDECFBTABCDEF下标123456 (2) 简述算法的功能。void f(char BT,int n) int i=1; while(i

48、0) if(i0) i+; 算法的功能: 前序遍历11、已知二叉树的存储结构为二叉链表，其类型定义如下：typedef struct NodeTypeDataType data;struct NodeType *left,*right; BTreeNode;阅读下列算法，并回答问题：简述算法的功能； 算法的功能；中序遍历 (2)对于如图所示的二叉树BT，写出执行算法f(BT,a,8)后数组a的内容。void f (BTreeNode * BT, DataType a ,int n) static int i=0; if(BT!=NULL)f(BT-left,a,n);ai+=BT-data;f

49、(BT-right,a,n);数组A内容：DBGEHACF12、已知二叉树的存储结构为二叉链表，阅读下列算法，并回答问题：（1）对下图所示的二叉树T，画出执行算法f(T)后所建立的结构；建立的单链表如下：D- F-H-G（2）简述算法的功能。typedef struct node DateType data；Struct node * next；ListNode；typedef ListNode * LinkList ；LinkList Leafhead=NULL；void f (BinTree T)LinkList s；if(T)f(T-lchild)； if (!T-lchild)&(!T

50、-rchild) s=(ListNode*)malloc(sizeof(ListNode)； s-data=T-data； s-next=Leafhead； Leafhead=s； f(T-rchild)；功能：中序遍历，按叶子结点数据自右至左链接成一个链表。13、假设以二叉链表作为二叉树的存储结构，其类型定义如下：typedef struct node char data; struct node *lchild, *rchild; /左右孩子指针 BinTNode,*BinTree；阅读下列算法，并回答问题：简述算法的功能；功能；如果该结点有右孩子且无左孩子，把右孩子作为左孩子。(2) 已

51、知如图所示的二叉树以T为指向根结点的指针，画出执行f 38(T)后的二叉树。void f38(BinTree T) if (T) f 38 (T - lchild) ; f 38(T - rchild) ; if ( ( !T - rchild) & T-lchild) T - lchild=T-rchild; T - rchild=NULL;二叉树是：14、已知二叉树的存储结构为二叉链表，其类型定义如下：typedef struct NodeTypeDataType data;struct NodeType *left,*right; BTreeNode，*BTree;阅读下列算法，并回答问

52、题：简述算法的功能； 功能； 前序遍历二叉树。(2)对于如图所示的二叉树BT，画出执行算法f后指针pt所指的二叉树形态。BTree f(BTree BT) BTree pt;if(BT=NULL) return NULL;ECFABD else pt=( BTreeNode*)malloc( sizeof(BTreeNode);pt-data=BT-data;pt-right=f(BT-left);pt-left=f(BT-right);return pt; pt所指的二叉树形态： 15、阅读下列算法，并回答问题：说明算法f采用的排序方法：排序方法：直接插入排序法。简述算法f中R0的作用。R0

53、的作用：当中间变量用。Typedef struct KeyType key; InfoType otherinfo;RecType;typedef RecType SqListMAXSIZE;void f(SqList R,int n)/n小于MAXSIZE -1，为顺序表的长度int i,j;for(i=2;i=n;i+) if(Ri.keyRi-1.key) R0=Ri;for(j=i-1;R0.keyRj.key;j-)Rj+1=Rj;Rj+1=R0;16、下列算法的功能是将x插入到递增有序的数组A中，并保持插入后的数组元素依然有序。请在空缺处填入合适的内容，使其成为一个完整的算法。vo

54、id f(DataType A,int num,DataType x) /向量A目前有num个元素 int i=0,j; while (Ai=x & i=i;j-) _ Aj+1=Aj_;/ 向后移动元素 Ai=x; ; / 插入元素 Ai=x;17、下列算法的功能是实现顺序表就地逆置的操作。请在空缺处填入合适的内容，使其成为一个完整的算法。#define ListSize 200typedef struct Datatype dataListSize; int length;Seqlist;void Seq_Reverse(Seqlist *L) int i; Datatype temp;f

55、or(i=0; ilength ; i+) temp= L-datai;L-datai= L-dataL-length-1-i; ; L-dataL-length-1-i =temp;18、下列算法利用二分查找方法在有序表R中插入元素x，并保持表R的有序性，其中length为表R的长度。请在空缺处填入合适的内容，使其成为一个完整的算法。void BinInsert(SeqList R,int length,DataType x) int low=1,high=length,mid,i;while(low=high) mid=(low+high)/2;if (x.key=mid ;i-)Ri+1

56、=Ri; Rmid=x ;length+;19、下列算法的功能是将一个非负的十进制数N转换成二进制数。请在空缺处填入合适内容，使其成为一个完整的算法。void f(int N)SeqStack S;InitStack(&S);while( N )Push(&S, N%2); N=N/2; ; while(!StackEmpty(&S) i= Pop(&S) ; printf(%d,i);20、下列算法f2 的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使其成为一个完整的算法。typedef struct nodeDataType data;struct node *next;QueueNode;typedef struct QueueNode *front;/队头指针QueueNode *rear;/队尾指针LinkQueue;void f2(LinkQueue *Q)QueueNode *p,*s;p= Q-front;while(p!=NULL) s=p; p=p-next; free(s); Q-front =NULL;Q-rear= NULL ;21、下列算法的功能是建立二叉树。请在空缺处填入合