数据结构模拟试题1-8_模拟试题答案.doc

模拟试题1一、 选择题(20分)1. 组成数据的基本单位是什么（ ）。(A) (A) 数据项 （B）数据类型 （C）数据元素 （D）数据变量2. 线性表的链接实现有利于（ ）运算。（A）插入 （B）读表元 （C）查找 （D）定位3. 串的逻辑结构与（）的逻辑结构不同。（A）线性表 （B）栈 （C）队列 （D）树4. 二叉树第i(i=1)层最多有（ ）个结点。（A）2i （B）2i （C）2i-1 （D）2i -1 5. 设单链表中指针p指向结点A之后的结点（若存在），则修改指针的操作为（ ）。（A）p- next=p- next- next （B）p=p- next（C）p=p- next- next （D）p- next=p6. 设一数列的输入顺序为1，2，3，4，5，6，通过栈操作不可能派成的输出序列为（）。（A）3，2，5，6，4，1 （B）1，5，4，6，2，3（C）2，4，3，5，1，6 （D）4，5，3，6，2，17. 设字符串S1=ABCDEFG，S2=PQRST，则运算S=Concat(Sub(S1,2,Length(S2),Sub(S1, Length(S2),2)后结果为（ ）。（A）BCQR （B）BCDEF （C）BCDEFG （D）BCDEFEF8. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第1个元素，其存储地址为1个地址空间，则a85的地址为（）。（A）13 （B）33 （C）18 （D）409. 如果结点A有3个兄弟，且B为A的双亲，则B的度为（ ）。（A）3 （B）4 （C）5 （D）110.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是（ ） （A）堆排序 （B）冒泡排序 （C）简单选择排序 （D）快速排序二、 填空题（每空2分，共22分）1.对于一个以顺序实现的循环队列Q0m-1，队首、队尾指针分别为f和r，其判空的条件是 ，判满的条件是 。2.循环链表的主要优点是 。3.给定一个整数集合3，5，6，9，12，画出其对应的一棵Huffman树 。4.在双向循环链表中，在指针p所指的结点之后插入指针f所指的结点，其操作为 。5.下面为简单模式匹配算法，请在算法的下划线处填上正确的子句。 int index(s,t) string *s,*t; i=j=0; while(ilen)&(jlen) if(s-chi=t-chj) i=i+1; j=j+1; else i= ; j= ; if(j=t-len) return(i-t-len); else return(-1); 6.一个nn的对称矩阵，如果以行或列为主序存入内存，则其容量为 。7.设 F是森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有 。8.先序序列和中序序列相同的二叉树为 。9.已知一棵二叉树的中序遍历结果为DBHEAFICG，后序遍历结果为DHEBIFGCA，画出该二叉树 。三、 应用题（16分）1. 设二叉树的顺序存储结构如下：（4分） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20EAFDHCGIB （1） 根据其存储结构，画出二叉树。 （2） 写出按先序、中序、后序遍历该二叉树所得的结点序列。 （3） 画出二叉树的后序线索化树。2. 一棵完全二叉树共有21个结点，现顺序存放在一个矢量中，矢量的下标正好为结点的序号，试问序号为12的双亲结点存在吗？为什么？（4分）3. 线性表有顺序表和链表两种存储结构，简述各自的优缺点。（4分）4. 何谓队列的“假溢”现象？如何解决？（4分）四、 算法设计（38分）1. 试写出求二叉树结点数目的算法。（13分）2. 设a=(a1,a2,am)和b=(b1,b2,bn)是两个循环链表，写出将这两个表合并为循环链表c的算法。（15分） (a1,b1,a2,b2,，am,bm,bm+1,bn) (mn) 3 写函数用于删除元素递增排列的带首结点单链表L中值大于mink且小于maxk的所有元素，并给出其时间复杂度。链表类型定义如下。（10分）typedef struct node int Data ;struct node * next *LinkList;模拟试题2一、选择题（20分）1.数据结构是研究数据的（ ）以及他们之间的相互关系。（A）理想结构，物理结构 （B）理想结构，抽象结构（C）物理结构，逻辑结构 （D）抽象结构，逻辑结构 2.线性表采用链式存储时，其地址（ ）。（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续与否均可以3. 设循环队Q1n-1的首尾指针为f和r，当插入元素时尾指针r加1，首指针F总是指在队列中的第一个元素的前一个位置，则队列中元素计数为（）。（A）r-f （B）n-(r-f)（C）(r-f+n)% （D）(f-r+n)%n4. 完成堆排序的全过程需要（ ）个记录大小的辅助空间。（A）1 （B）n（C）nlog2n （D）nlog2n5. 若给定的关键码集合为20，15，14，18，21，36，40，10，一趟快速排序结束时，键植的排列为（）（A）10，15，14，18，20，36，40，21（B）10，15，14，18，20，40，36，21（C）10，15，14，20，18，40，36，21（D）15，10，14，18，20，36，40，216. 有一棵二叉树如下图，该树是（ ）（A）二叉平衡树 （B）二叉排序树（C）堆的形状 （D）以上都不是50205510309585707. 某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。（A）空或只有一个结点 （B）高度等于其结点数（C）任一结点无左孩子 （D）任一结点无右孩子8.具有n个顶点的完全有向图的边数为（ ）。（A）n(n-1)/2 （B）n(n-1) （C）n2 （D）n2 19.设有100个元素，用折半查找时，最大比较次数为（ ），最小比较次数为（ ）。（A）25 （B）7 （C）10 （D）110.在内部排序中，排序时不稳定的有（ ）（A）插入排序 （B）冒泡排序（C）快速排序（D）归并排序二、填空题（22分）1.具有64个结点的完全二叉树的深度为 。2.有向图G用邻接矩阵A1n,1n存储，其第i列的所有元素等于顶点i的 。3.设有一空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，5，经过Push,Push,Pop,Push,Pop,Push,Push操作后，输出序列为 。4.线索化二叉树中某结点D，没有左孩子的主要条件是 。5.模式中“ababbabbab”的前缀函数为 。6.设图G的顶点数为n，边数为e，第i个顶点的度数为D(vi)则e= （即边数与各顶点的度数之间的关系）。7.按 遍历二叉数，可以得到按值递增的关键码序列，在下图中所示的二叉树中，检索关键码85的过程，需与85进行比较的关键码序列为 。50205510309585708.下列算法实现二叉树排序树上的查找，请在空格处填上适当的语句，完成上述功能。 bitreptr *bstsearch(bitreptr *t,keytype k) if(t=NULL) return NULL; else while(t!= NULL;) if(t-key=k) ; if(t-keyk) ; else ; 三、应用题（28分）1. 设哈希表的地址空间为016，开始时哈希表为空，用线性探测开放地址法处理冲突，对于数据元素Jan,Feb,Mar,Jun,Aug,Sep,Oct,Nov,Dec,试构造其对应的哈希表，H(key)=i/2，其中i为关键码中第一个字母在字母表中的序号。2. ABCDEFGH给出右图所示树的先序遍历的结果。3. 对于下图，试给出（1）每个顶点的入度和出度；（2）邻接矩阵；（3）逆邻接表；142356（4）强连通分量。 4. 简述堆排序的基本思想，对键值集合72，73，71，23，94，16，05，68对应的二叉树进行堆，并写出具体步骤。四、算法设计（30分）1. 编写算法，求一个整型数组中不同值的个数。例如数组5，3，5，7，3，6，不同的值有3个。提示：可先将数组排序。 2. 已知单链表结点数据结构如下，编写算法，删除单链表的表首结点与表尾结点。 typedef struct LinkNodeint data;struct LinkNode *next;Node;3.设计一个算法，建立无向图（n个顶点，e条边）的邻接表。模拟试题3一、 选择题（20分）1. 组成数据的基本单位是（ ）。 （A） 数据项 （B）数据类型 （C）数据元素 （D）数据变量2. 线性表的链接实现有利于（ ）运算。（A）插入 （B）读表元 （C）查找 （D）定位3. 中序遍历一棵二叉排序树所得到的结点访问序列是键值的（）序列。（A）递增或递减 （B）递减 （C）递增 （D）无序4. SubStr(DATA STRUCTURE,5,9)=( )。（A）STRUCTURE （B）DATA （C）ASTRUCTUR （D） DATA STRUCTURE5. 下列哪一种形态不为树（ ）。ABABCD A (a) (b) (c) (d)6. 下列哪种排序需要的附加存储开销最大（ ）。（A）快速排序 （B）堆排序 （C）归并排序 （D）插入排序7. 对任何一棵树T，设n0,n1,n2,nm分别是度为0，1，2，,m的结点，则n0=（）。（A）n1+n2+nm （B）1+n2+2n3+3n4+（m-1）nm（C）n2+2n3+3n4+（m-1）nm （D）2n1+3n2+(m+1)nm 8. 对下图v4的度为（）。（A）1 （B）2 （C）3 （D）4V11V4V2V39. 在内部排序中，排序时不稳定的有（ ）。（A）快速排序 （B）冒泡排序（C）归并排序 （D）直接插入排序10. 设有1000个元素，用折半查找时，最大比较次数为（ ），最小比较次数为（ ）。（A）25 （B）10 （C）7 （D）1二、 填空题（26分）1.在一个长度为n的顺序表中插入一个元素，平均需移动 个元素，时间复杂度是 。2.双向循环链表的主要优点是 。3.上三角矩阵压缩存储的下标对应关系k= 。4.设有一个空栈，现输入序列为1，2，3，4，5，经过Push,Push,Pop,Push,Pop,Push,Pop,Push后，输出序列为 。5.后序序列和中序序列相同的二叉树为 。6.具有128个结点的完全二叉树的深度为 。7.有向图G用邻接矩阵A1m, 1m,存储，其第i行的所有元素值之和等于顶点vi的 。8. 衡量一个算法的优劣主要看它的 效率和 效率。9.在下面冒泡排序算法中填入适当内容，使该算法在发现有序时能及时停止。bubble(Rectype Rn)int i,j,exchang;Rectype temp;i=1;doexchang=False;for(j=n;j= ;j-) if(Rjnext!=p; pf=pf-next); =p-next;free(p);return head;2. 已知数组r有n个元素，并已经由小到大排序。下面的函数search的功能是采用折半查找法查找值为e的元素，并返回其下标，如果找不到，返回-1。完成下面程序。（10分） int search(elem r,int n, int e)int i1,i2,k;i1=0; i2=n-1;while(i1= i2)k=( i1+ i2)/2;if(rk=e) ;if(erk)i2= ;else ;return-1;3. 以下算法是将线性表L中所有负数元素删除，返回被删除的元素个数。完成以下算法。（10分） typedef structint elem100;int length;SQ;int deln(SQ *L)/*算法思路是，对每个元素做以下循环，如果第i个元素大于等于0，且前面有c个小于0的元素，则将它前移c个位置*/int i,c; /*c将记录小于0的元素个数*/for(i=0,c=0;ilength;i+) if( 0)x-ei- =x-ei; x-length= ;return c;模拟试题4一、 选择题（20分）1. n个顶点的无向图的邻接表中结点总数最多有（）个。（A）2n （B）n （C）n/2 （D）n(n-1)2. 设连通图G的顶点数为n，则G的生成树的边数为（）。（A）n （B）n-1 （C）2n （D）2n-13. 下列哪种排序需要的附加存储开销最小（ ）。 （A）快速排序 （B）堆排序 （C）归并排序 （D）计数排序4. 若按（ ）列出二叉排序树中所存储的元素，则恰好是集合中所有元素从小到大的排序。（A）先序 （B）中序 （C）后序 （D）按层次5. 在下列4棵树中，哪一棵是完全二叉树（）。 10040501525203035 10040501525203035 （a） (b)1004050152520303510040501530202535 (c) (d)6. 下面程序段的时间复杂度为（ ）。s=s0;for(i=1;i=n-i;j-) s=s+1; （A）O(n) （B）O(nlog2n) （C）O(n2) （D）O(n3/2)7. 采用链结构存储线性表时，其地址（ ）。（A）必须是连续的 （B）连续不连续都可以（C）部分地址必须是连续的 （D）必须是不连续的8. 具有2000个结点的二叉树，其高度至少为（）。（A）9 （B）10 （C）11 （D）129. 按字母顺序，下图中的二叉排序树是（ ）。ABCDEABCDE （a） （b）ABCDEABCDE（c） （c） （d） 10.设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（）。（A）p-next=p-next-next （B）p=p-next（C）p=p-next-next （D）p-next=p二、判断题（20分）1. 对称矩阵的存储只需要存储一半的数据元素。（ ）2. 二叉排序树的左、右子树都是二叉排序树。（ ）3. 折半查找说法的前提之一是线性表有序。（ ）4. 对相同关键码集合，以不同次序插入初始为空的的树中，一定得到不同的二叉排序树。（）5. 即使某排序算法是不稳定的，但该方法仍有实际应用价值。（）6. 连通分量是无向图中的极小连通子图。（ ）7. 线性表的顺序存储结构只能顺序访问（ ）8. 已知指针p指向链表L中的某结点，执行语句p=p-next不会删除该链表中的结点。（）9. 如果一个串中的所有字符均在另一个串中出现，则说明前者是后者的子串。（）10. 作为解决一类特定问题的算法，不能没有输入运算项。（ ）三、填空题（每空2分，共22分）1. 在双向循环表中，在p所指的结点之后插入指针f所指的结点，其操作为 =p;f-next=p-next; =f;p-next=f. 2.若字符串t=ababcab，取子串函数substr(t,2,3)= 。 3.一个具有n个顶点的有向完全图的弧数为 。 4. 对于一个以顺序实现的循环队列Q0m-1，队首、队尾指针分别为f和r，队列判空的条件是 。5.设键值序列为K1，K2，Kn，用筛选法建堆必须从第 个元素开始筛选。6.哈希表的两种解决冲突的方法： 和 。7.设一棵二叉树共有50个叶子结点（终端结点），则它共有 个度为2的结点。8.高度为h(=0)的二叉树，至少有 个结点，最多有 个结点。四、应用题（20分）1. 依次输入集合20，13，22，5，16，3，48，24中的键值，得到一棵二叉排序树，试画出该二叉排序树并求出在等概率下成功查找的平均查找长度。（5分） 2. 设下图所示的二叉树是由森林转换而成的，试将它还原为森林。（5分） ABCEDFGHIJK3. 树与二叉树之间有何区别？（5分） 4. 已知图如下所示。（5分） （1） 要求用Kruskal算法求出最小生成树；（2） 指出生成树的第一条边。123456 5 5 7 10 6 19 3 18五、 算法设计（18分）1. 编写一个程序，输出二叉排序树BT中最小的键值。（8分）2. 我们用链表来存储多项式Pn(x)=C1xe1+C2xe2+Cmxem，其中n=emem-1e1=0,Ci！=0(i=1,2,m,m1),试编写求Pn(x)微商的算法。（注，d(xk)/dx=kxk-1）(10分)模拟试题5一、选择题（30分）1. 下列程序的时间复杂度为（ ）。 for(i=0;im;i+)for(j=0;jt;j+) cij=0;for(i=0;im;i+) for(j=0;jt;j+) for(k=0;kn;k+) cij=cij+aik*bkj;（A）O（mnt） （B）O(m+n+t)（C）O(m+nt) （D）O(mt+n)2. 从一个长度为n的顺序表中删除第i个元素（1=inext=s;s-prior=p;p-next-prior=s;s-next=p-next;（B）s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;（C）p-next=s; p-next-prior=s; s-prior=p;s-next=p-next;（D）s-prior=p; s-next=p-next; p-next-prior=s; p-next=s;6. 串的长度是（ ）。 （A）串中不同字符的个数 （B）串中不同字母的个数（C）串中所含字符的个数n（n0） （D）串中所含字符的个数n（n=0）7. 若有一个栈的输入序列是1，2，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。 （A）n-i （B）n-i-1 （C）n-i+1 （D）不确定8. 设有一个栈，元素的进栈次序为A，B，C，D，E，下列（ ）是不可能的出栈序列。 （A）A，B，C，D，E （B）B，C，D，E，A（C）E，A，B，C，D （D）E，D，C，B，A9. 在一棵度为3的树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数有2个，那么度为0的结点数有（ ）个。 （A）4 （B）5 （C）6 （D）710. 在一个具有n个结点的无向完全图中，包含有（ ）条边。 （A）n(n-1)/2 （B）n(n-1) （C）n(n+1)/2 （D）nn11. 采用顺序查找法查找度为n的线性表，则查找每个元素的平均比较次数为（ ） （A）n （B）n/2 （C）(n+1)/2 （D）(n-1)/212. 已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，需（ ）次比较可查找成功。 （A）1 （B）2 （C）3 （D）413. 在顺序存储的线性表R029上进行顺序查找的平均查找长度为（），进行二分查找的平均查找长度为（），进行分块查找（设分为5块）的平均查找长度为（）。 （A）15 （B）15.5 （C）16 （D）20 （A）4 （B）62/15 （C）64/15 （D）25/6 （A）6 （B）11 （C）5 （D）6.514. 在所有排序方法中，关键码的比较次数与记录的初始排列无关的是（ ）。 （A）Shell排序 （B）冒泡排序（C）直接插入排序 （D）直接选择排序15. 已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（ ）。 （A）4 （B）5 （C）6 （D）7二、填空题（22分，前4题每空2分，第5题每空1分）1.若要在一个单链表的*p结点之前插入一个*s结点时，可执行下列操作：s-next= ；p-next=s;t=p-data;p-data= ;s-data= 。2.计算机软件系统中有两种处理字符串长度的方法，一种是采用 ，另一种是 。3.假定对线性表R059进行分块查找，共分10块，每块长度等于6。若假定查找索引表和块均用顺序查找法，则查找每一个元素的平均查找时间为 。4.一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时第一趟需进行相邻记录的次数为 ，在整个排序过程中共需进行 趟才可以完成。5.在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取 方法，其次选 方法，最后选取 方法；若从排序结构的稳定性考虑，则应选择 方法；若只从平均情况下排序的速度来考虑，则选择 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应该取 方法。三、判断题（10分）1. 数据元素是数据的最小单元。（ ） 2. 在单链表中任何两个元素的存储位置之间都有固定的联系，因此可以从首结点进行查找任何一个元素。（ ） 3. 设哟两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为q在p中的位置的算法称为匹配。（ ） 4. 若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必须是该子树的先许8遍历的最后一个结点。（ ） 5. 对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度为O(n2).( ) 6. 用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。（ ） 7. 哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。（ ） 8. 因为算法和程序没有区别，所以再数据结构中二者是通用的。（ ） 9. 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。（ ） 10. 进栈操作push(x,s)作用于链接栈时，无需判满。（ ） 四、应用题（20分）1. 已知一个长度为12的表Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec. 试按表中元素的次序依次插入一棵初始为空的二叉排序树，字符之间以字典顺序比较大小，并画出对应的二叉排序树，且求出在等概率情况下查找成功的平均查找长度。 若对表中元素先排序构成有序表，试求在等概率情况下对此有序表进行折半查找成功的平均查找长度。2. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。3. 假设用于通讯的电文仅有8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10，试为这8个字母设计哈夫曼编码。4. 判断以下序列是否为堆，如果不是，则把它调整为堆。（1）（100，86，48，73，35，39，42，57，66，21）；（2）（12，70，33，65，24，56，48，92，86，33）；（3）（103，97，56，38，66，23，42，12，30，52，06，20）。五、算法设计（18分）1. 已知线性表的元素按递增顺序排列，并以带首结点的单链表作为存储结构。试编写一个删除表中所有值大于min切小于max的元素的算法。2. 试设计一个算法，求出指定结点在给定的二叉树中的层次。3. 在含有n个元素的堆中增加一个元素，且调整为堆。4. 试设计将数组A0N-1中所有奇数移到所有偶数之前的算法，要求不另外增加存储空间，且时间复杂度为O(n)。模拟试题6一、选择题（每小题1分，共8分）1. 如果某数据结构的数据元素集合为S=A，B，C，D，E，F，G，数据元素之间的关系为R=,则该数据结构是一种（ ）。 （A）线性结构 （B）数结构 （C）图结构 （D）链表结构2. 设有二维数组A5060，其元素长度为1字节，按列优先顺序存储，首元素A00的地址为200，则元素A1020的存储地址为（ ）。 （A）820 （B）720 （C）1210 （D）14103. 一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需要进行相邻记录交换的次数为（ ）。 （A）5 （B）6 （C）7 （D）84. 具有20个结点的二叉树，其深度最大为（ ）。 （A）4 （B）5 （C）6 （D）205. 在具有N个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件为（ ）。 （A）front=rear （B）（rear+1）%MAXSIZE=front（C）front- rear=1 （D）rear% MAXSIZE=front6. 一个55的对称矩阵采用压缩存储，需要存储（ ）个元素。 （A）5 （B）10 （C）15 （D）207. 一个无向连通图有5个顶点8条边，则其生成树将要去掉（ ）条边。 （A）3 （B）4 （C）5 （D）68. 设一棵二叉树共有50个叶子结点（终端结点），则共有（ ）个度为2的结点。 （A）25 （B）49 （C）50 （D）51二、填空题（每题2分，共16分）1.一个算法，如果不论问题规模大小，运行所需时间都一样，则该算法的时间复杂度是 。 2.已知某算法的执行时间为（n+n2）/2+log2(2n+1),n为问题规模，则该算法的时间复杂度是 。3.在求生成树的两种算法中， 算法适合与稀疏图。4.一棵Huffman树是由5个叶子结点形成的，该Huffman树总共有 个结点。5.设循环队列Q1N的首尾指针为F，R，当插入元素时尾指针R加1，首指针总是指向队列中第一个元素的前一个位置，则队列中元素的个数为 。6.一个具有5个结点的有向图最少有 条弧。7.二叉排序树采用 序遍历可以得到结点的有序序列。8.设有1000个元素，用折半法查找时，最大比较次数是 。三、判断题（每题1分，共8分。正确的打，错误的打）1. 如果某数据结构的每一个元素都最多只有一个直接后继结点，则必为线性表。（ ）2. 如果某有向图的所有顶点可以构成一个拓扑排序，则说明有向图存在回路。（ ）3. 如果把一个大顶堆看成一棵二叉树，根元素层次为1，则层次越大的元素值越小。（ ）4. Huffman树没有度为1的结点。（ ）5. 在冒泡排序中，关键码的比较次数与记录的初始排列无关。（ ）6. 设一棵二叉树共有50个叶子结点（终端结点），则共有49个度为1的结点。（ ）7. 一个有序的单链表采用折半查找法比顺序查找效率高的多。（ ）8. 一个图可以没有边，但不能没有顶点。（ ）四、简答题（共38分）1. 排序（1） 写出先性表（26，45，12，20，30，6，15，29，16，2，18）采用基数排序后，第一趟结束时的结果。（4分）（2） 线性表采用简单选择排序算法对线性表（26，15，12，16，5，30）进行排序，进行交换的第一对元素是哪两个元素?在什么情况下，第一趟不需要进行元素的交换？（6分）2.（1）给出下图所示的二叉树后序遍历的结果。（5分）（2）如果下图表示的是采用孩子-兄弟法转换后的一棵树，试画出原来的树。（5分）AABCDEFG3.已知下图是一个有向图。（1） 画出该有向图的邻接矩阵。（5分）（2） 基于你给出的邻接矩阵，求出从顶点B出发的深度优先遍历。（5分）BCDEAF4.已知有序表（4，11，13，19，26，28，33，39，42），采用折半查找。(1)各元素的平均查找长度是多少？（4分）（2）查找值为10的元素，查找时与哪些元素进行了比较？（4分）五、程序填空题（共15分） 1. 已知STACK表示栈的数据结构，push为将一个值为e的元素进栈，若成功返回1，否则返回0。完成以下程序。（4分） typedef struct int data100; int top; /*栈顶元素的下标*/ STACK； int push(STACK *s,int e) if()return 0; s-top+; =e; return 1; 2.以下程序是在二叉排序树T中找出值最大的元素，返回其地址，如果空树返回NULL。完成程序。（6分）Typedef struct LinkNode int data; Struck LinkNode *lchild, *rchild; Node; Node *sm (Node *t) Node *p; if( )return NULL;for(p=t; ;p=p-rchild);return; 3.写出下列程序的输出结果。（5分）int strc(char s,char t) int i; for(i=0;si!=0&ti!=0;i+) if(si!=ti)break; return(si-ti);main()printf(“%dn”,strc(“student”, “study”);六、编程题（共15分）