1、数据结构-6 及答案解析(总分：99.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.具有 12个记录的序列，采用冒泡排序最少的比较次数是( )（分数：2.00）A.1B.144C.11D.662.任何一个带权的无向连通图的最小生成树( )（分数：2.00）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3.在一棵具有 5层的满二叉树中，结点总数为( )个。（分数：2.00）A.33B.32C.31D.304.在循环双链表的 p所指结点之后插入 s所指结点的操作是( )（分数：2.00）A.Pnext=s；B.pnext=s； sprior=p；
2、pnextprior=s； pnextprior=s； sprior=p； snext=pnext； snext=pnextC.sprior=p；D.sprior=p； snext=pnext； snext=pnext； pnext=s； pnextprior=s； pnextprior=s； pnext=s；5.在下面的程序中，语句 S的执行次数为( ) for(i=1;i=n-1;i+) for(j=n;j=i;j-) S; （分数：2.00）A.B.C.D.6.若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，共要进行(
3、 )次比较。（分数：2.00）A.33B.45C.70D.917.用数组 A0N-1存放循环队列的元素值，若其头尾指针分别为 front和 rear，则循环队列中当前元素的个数为( )（分数：2.00）A.(rear-front+mod mB.(rear-front+1)mod mC.(rear-front-1+mod mD.(rear-fronmod m8.若已知一个栈的输入序列为 1,2,3,n，其输出序列为 P1，P 2，P n。若 P1=n，则 P1为( )（分数：2.00）A.iB.n=iC.n-i+lD.不确定9.设矩阵 A(aij,1i,ji0)的元素满足： aij0(ij,1i
4、,j10) aij=O(ij,1i,j10) 现将 A的所有非 0元素以行序为主序存放在首地址为 2000的存储区域中，每个元素占 4个单元，则元素9,5的首地址为( )（分数：2.00）A.2160B.2164C.2336D.234010.如果要求一个线性表适应动态变化的要求，又必须能尽快地进行查找，则可以选择采用( )查找方法。（分数：2.00）A.分块B.二分C.顺序D.散列11.在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )（分数：2.00）A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同12.设栈 S和队列 Q的
5、初始状态为空，元素 e1、e 2、e 3、e 4、e 5和 e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6个元素出列的顺序是 e2、e 3、e 4、e 5、e 6、e 1，则栈 S的容量至少应该是( )（分数：2.00）A.6B.4C.3D.213.循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别是 front和 rear，则当前队列中的元素个数是( )（分数：2.00）A.(rear-front+MODmB.rear-fomt+1C.rear-fribt-1D.rear-front14.索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关键字顺序存储，故需要建
6、立一张指示逻辑记录和物理记录之间一一对应关系的( )（分数：2.00）A.索引表B.链接表C.符号表D.交叉访问题15.在线索化二叉树中，结点 T没有左子树的充要条件是( )（分数：2.00）A.Lchild=NILB.Ltag=1C.Ltag=1 且 TLchils=NILD.均不对二、B填空题/B(总题数：10，分数：20.00)16.从树的根结点到树中的其余结点之间的路径 1 惟一的。（分数：2.00）填空项 1:_17.一个字符串相等的充要条件是_和_。（分数：2.00）填空项 1:_18.在线性结构中， 1 决定了它的遍历路线只有一条。（分数：2.00）填空项 1:_19.带有一个头
7、结点的单链表 head为空的条件是 1。（分数：2.00）填空项 1:_20.散列文件关键在于选择好的_和_方法。（分数：2.00）填空项 1:_21.ISAM文件采用_索引结构，而 VSAM文件采用_索引结构。（分数：2.00）填空项 1:_22.已知广义表 A=(a,b,c)，(d,e,f)，则运算 head(head(tail(tail(A)= 1。（分数：2.00）填空项 1:_23.具有 N个顶点的无向完全图的边为_，具有 N个顶点无向完全图的弧为_。（分数：2.00）填空项 1:_24.设树 T的度为 4，其中度为 1、2、3 和 4的结点个数分别是 4、2、1 和 1，则 T中叶
8、子结点的个数是： 1。（分数：2.00）填空项 1:_25.任意一棵具有 n个结点的二叉树，若它有 m个叶子，则该二叉树上度数为 1的结点为 1 个。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：19.00)26.已知一棵二叉树的前序遍历序列是 ABDGCEFH，其中序遍历序列为 DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?（分数：5.00）_27.已知有一关键字序列为97,86,53,108,72,34,215,146,11,68，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列
9、)，请给出每一趟的排序结果。（分数：5.00）_28.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点 vi表示)。 （分数：5.00）_判别下列二序列是否为堆，如不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。（分数：4.00）(1).(1,5,7,25,21,8,8,42)（分数：2.00）_(2).(3,9,5,8,4,17,21,6)（分数：2.00）_四、B算法阅读题/B(总题数：4，分数：20.00)29.请将下面的程序改成递归的过程。 voide ditui(int n) int i; i=n; while(i1) prinft(i-); （分数：5.00
10、）_30.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok; )/A（分数：5.00）_31.求下面算法中变量 count的值：(假设 n为 2的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_32.写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main(
11、) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)； push(s,e); push(s,x); pop(s,x); push(s,h); while(!stackEmpty(s) pop(s,y); printf(y); prinft(x) （分数：5.00）_五、B算法设计题/B(总题数：1，分数：10.00)33.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。（分数：10.00）_数据结构-6 答案解析(总分：99.00，做题时间：90 分钟)一、B单项选择题
12、/B(总题数：15，分数：30.00)1.具有 12个记录的序列，采用冒泡排序最少的比较次数是( )（分数：2.00）A.1B.144C.11 D.66解析：2.任何一个带权的无向连通图的最小生成树( )（分数：2.00）A.只有一棵B.有一棵或多棵 C.一定有多棵D.可能不存在解析：3.在一棵具有 5层的满二叉树中，结点总数为( )个。（分数：2.00）A.33B.32C.31 D.30解析：4.在循环双链表的 p所指结点之后插入 s所指结点的操作是( )（分数：2.00）A.Pnext=s；B.pnext=s； sprior=p； pnextprior=s； pnextprior=s； s
13、prior=p； snext=pnext； snext=pnextC.sprior=p；D.sprior=p； snext=pnext； snext=pnext； pnext=s； pnextprior=s； pnextprior=s； pnext=s； 解析：5.在下面的程序中，语句 S的执行次数为( ) for(i=1;i=n-1;i+) for(j=n;j=i;j-) S; （分数：2.00）A.B. C.D.解析：6.若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，共要进行( )次比较。（分数：2.00）A.33B.
14、45C.70 D.91解析：7.用数组 A0N-1存放循环队列的元素值，若其头尾指针分别为 front和 rear，则循环队列中当前元素的个数为( )（分数：2.00）A.(rear-front+mod m B.(rear-front+1)mod mC.(rear-front-1+mod mD.(rear-fronmod m解析：8.若已知一个栈的输入序列为 1,2,3,n，其输出序列为 P1，P 2，P n。若 P1=n，则 P1为( )（分数：2.00）A.iB.n=iC.n-i+l D.不确定解析：9.设矩阵 A(aij,1i,ji0)的元素满足： aij0(ij,1i,j10) aij
15、=O(ij,1i,j10) 现将 A的所有非 0元素以行序为主序存放在首地址为 2000的存储区域中，每个元素占 4个单元，则元素9,5的首地址为( )（分数：2.00）A.2160 B.2164C.2336D.2340解析：10.如果要求一个线性表适应动态变化的要求，又必须能尽快地进行查找，则可以选择采用( )查找方法。（分数：2.00）A.分块 B.二分C.顺序D.散列解析：11.在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )（分数：2.00）A.都不相同B.完全相同 C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同解析：12.设栈 S和队列
16、 Q的初始状态为空，元素 e1、e 2、e 3、e 4、e 5和 e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6个元素出列的顺序是 e2、e 3、e 4、e 5、e 6、e 1，则栈 S的容量至少应该是( )（分数：2.00）A.6B.4C.3 D.2解析：13.循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别是 front和 rear，则当前队列中的元素个数是( )（分数：2.00）A.(rear-front+MODm B.rear-fomt+1C.rear-fribt-1D.rear-front解析：14.索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关
17、键字顺序存储，故需要建立一张指示逻辑记录和物理记录之间一一对应关系的( )（分数：2.00）A.索引表 B.链接表C.符号表D.交叉访问题解析：15.在线索化二叉树中，结点 T没有左子树的充要条件是( )（分数：2.00）A.Lchild=NILB.Ltag=1 C.Ltag=1 且 TLchils=NILD.均不对解析：二、B填空题/B(总题数：10，分数：20.00)16.从树的根结点到树中的其余结点之间的路径 1 惟一的。（分数：2.00）填空项 1:_ （正确答案：是）解析：17.一个字符串相等的充要条件是_和_。（分数：2.00）填空项 1:_ （正确答案：两个字符串的长度相等 对应
18、位置的字符相等）解析：18.在线性结构中， 1 决定了它的遍历路线只有一条。（分数：2.00）填空项 1:_ （正确答案：线性结构中后继的惟一性）解析：19.带有一个头结点的单链表 head为空的条件是 1。（分数：2.00）填空项 1:_ （正确答案：Jaeadnext=NULL）解析：20.散列文件关键在于选择好的_和_方法。（分数：2.00）填空项 1:_ （正确答案：散列函数 冲突处理）解析：21.ISAM文件采用_索引结构，而 VSAM文件采用_索引结构。（分数：2.00）填空项 1:_ （正确答案：静态 动态）解析：22.已知广义表 A=(a,b,c)，(d,e,f)，则运算 he
19、ad(head(tail(tail(A)= 1。（分数：2.00）填空项 1:_ （正确答案：e）解析：23.具有 N个顶点的无向完全图的边为_，具有 N个顶点无向完全图的弧为_。（分数：2.00）填空项 1:_ （正确答案：n(n-1)/2 n(n-1)）解析：24.设树 T的度为 4，其中度为 1、2、3 和 4的结点个数分别是 4、2、1 和 1，则 T中叶子结点的个数是： 1。（分数：2.00）填空项 1:_ （正确答案：8 个）解析：25.任意一棵具有 n个结点的二叉树，若它有 m个叶子，则该二叉树上度数为 1的结点为 1 个。（分数：2.00）填空项 1:_ （正确答案：n-2m+
20、1）解析：三、B解答题/B(总题数：4，分数：19.00)26.已知一棵二叉树的前序遍历序列是 ABDGCEFH，其中序遍历序列为 DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?（分数：5.00）_正确答案：()解析：根据二叉树的遍历规则，前序遍历总是先访问根结点，然后依次遍历其左右子树，而中序遍历规则是先遍历左子树，再访问根结点，然后访问右子树，则由以上规则，我们极易得出此二叉树的根结点是A，中序遍历序列中，根结点左右两边的结果分别属于其左、右子树，所以得出左子树包含 3个节点：B，D，G，右子树包含四个结点 C
21、，E，F，H。在左子树中，先序遍历序 B位于最前，而中序遍历序列中，B位于最后，则可以得出结点 B无右子树，只有左子树，又在 B的子树中，无论先序遍历还是中序遍历，D都位于 G的前面，则 G只能是 D的右孩子，且 D无左孩子，按照以上分析规则，我们同样可以分析出此二叉树的右子树的结构。从而我们得到了此二叉树的最终结构为： 此二叉树的后序遍历序列为：GDBEHFCA 从求出的二叉树的形状我们可以看出此二叉树不是完全二叉树，完全二叉树的性质是：一棵完全二叉树只有最下面的两层的结点数可以小于 2，并且最下面一层的结点都集中在该层最左边的若干位置上。 27.已知有一关键字序列为97,86,53,108
22、,72,34,215,146,11,68，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_正确答案：()解析：直接选择排序的过程为：从第 i趟开始时，当前的有序区和无序区分别为 R1i和 R1n(1-1n-1)，则在该趟排序是从当前无序区中选出关键字最小的记录 RK，将它与无序区中的第 1个记录Ri交换，使 R1i和 Ri+1n分别变成新的有序区和新的无序区，每次排序都使有序区增加一个记录，无序区减少一个记录，按照以上规则，我们得到各趟结果如下： 初始：97,86,53,108,72,34,215,232,11,68 第 1趟：1186
23、,53,108,72,34,215,232,97,68 第 2趟：11,3453,108,72,86,215,232,97,68 第 3趟：11,34,531108,72,86,215,232,97,68 第 4趟：11,34,53,6872,86,215,232,97,108 第 5趟：11,34,53,68,7286,215,232,97,108 第 6趟：11,34,53,68,72,86215,232,97,108 第 7趟：11,34,53,68,72,86,97232,215,108 第 8趟：11,34,53,68,72,86,97,108215,232 第 9趟：11,34,5
24、3,68,72,86,97,108,215,23228.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点 vi表示)。 （分数：5.00）_正确答案：()解析：A，B，C 对应的图分别为： 判别下列二序列是否为堆，如不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。（分数：4.00）(1).(1,5,7,25,21,8,8,42)（分数：2.00）_正确答案：()解析：为堆；(2).(3,9,5,8,4,17,21,6)（分数：2.00）_正确答案：()解析：不是堆，调整为堆的过程如下图所示： 四、B算法阅读题/B(总题数：4，分数：20.00)29.请将下面的程序改成递
25、归的过程。 voide ditui(int n) int i; i=n; while(i1) prinft(i-); （分数：5.00）_正确答案：()解析：此递推过程可以改写成如下递归过程： voide dkui(int j) if(i1) prind(j); digui(j-1); 30.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok; )/A（分数：5.00）_正确答案：()解析：本程序实现的功能就是：
26、如果 L的长度不小于 2，则将首元结点删去并插入到表尾。31.求下面算法中变量 count的值：(假设 n为 2的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_正确答案：()解析：count=log 2n32.写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main( ) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)； p
27、ush(s,e); push(s,x); pop(s,x); push(s,h); while(!stackEmpty(s) pop(s,y); printf(y); prinft(x) （分数：5.00）_正确答案：()解析：此题的输出结果是 hello。五、B算法设计题/B(总题数：1，分数：10.00)33.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。（分数：10.00）_正确答案：()解析：可通过设置一个标志位进行区分的方式来进行交替扫描，算法描述如下： Alterbubblesort(r) /*交替扫描法起泡排序*/ Reetype R; int i,j，temp，flag; /*设置扫描标志 flag*/ flag=True; i=0; while(flag) /*开始扫描*/ flag=False; for(j=n=i,ji,j-) if(Rj,keyRj-1,key) flag=True; temp=Rj; Rj=Rj-1; Rj-1=temp; for(j=l;jn-1;j+) if(Rj.keyRj+1.key) flag=True; temp=Rj; Rj=Ri+1; Rj-1=temp; i+; /*往右扫描*/ /*AIterbubblesort*/
