福建师大数据结构期中练习

1、09计本数据结构期中练习题 一、选择题:1.下面程序段的时间复杂度为( D ) s=0； for(i=1；in；i+) for(j=1；jnext=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；3.在计算机内实现递归算法时所需的辅助数据结构是( A )A.栈B.队列C.树D.图4.假设以数组Am存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( B )A.(rear-length+m+1)m

2、B.(rear-length+m)mC.(rear-length+m-1)mD.(rear-length)m 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( D )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，46. 下列图示的顺序存储结构表示的二叉树是( A )7在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C ) A4 B5 C6 D78在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B）A不一定相同B都相同C都不

3、相同D互为逆序9若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（C）A层次遍历算法B前序遍历算法C中序遍历算法D后序遍历算法10.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( A )的二叉树。 A.空或只有一个结点B.高度等于其结点数 C.任一结点无左孩子D.任一结点无右孩子2、 填空题:1.在一个长度为100的顺序表中删除第10个元素时，需移动_90_个元素。2.队列的队尾位置通常是随着_入队_操作而变化的。3.已知一棵哈夫曼树含有60个叶子结点，则该树中共有_59_个非叶子结点。4. 已知完全二叉树T的第5层只有7个结点，则该树共有_11_个叶子结点。5假设为

4、循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为_10_。6一棵含999个结点的完全二叉树的深度为_10_。三、解答题：1、现有中序遍历二叉树的结果为BAC，画出可以得到这一结果的所有二叉树。2、设某二叉树的后序遍历序列为：DCBFJIHGEA，中序遍历序列为：BCDAFEHJIG。（1）试画出该二叉树；（2）画出该二叉树前序线索化图。（3）试画出该二叉树对应的森林。3、 将给定的一组权值：2、4、8、6、7、5、7，构造成一棵哈夫曼树。四、阅读算法（每小题5分，共25分）1. void AE(Stack& S) InitStack(S); Push

5、(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a5=1,5,8,12,15; for(i=0;ileft,c1,c2); c1+; if (BT-left=NULL&BT-right=NULL) c2+; ABC(BT-right,c1,c2); /if 该函数执行的功能是什么？统计树的节点总数和叶子数目3. 在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）InitList(La)

6、; Int a=100,26,57,34,79; For (i=0;i5;i+) ListInsert(La,1,ai);（2）ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);（3）ClearList(La); For (i=0;i5;i+) ListInsert(La,i+1,ai);79 34 57 26 100 34 57 26 100 79 100 26 57 34 794. 有如下递归过程：void print(int w) int I; if(w!=0) print(w-1); for(I=1;Inext;L-next=NU

7、LL;while(p)q=p-next;p-next=L-next;L-next=p;p=q;return OK;/zy222编写算法判定两棵二叉树是否相似，所谓两课树相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。 其中树节点定义如下 typedef struct BiTNode DataType data; Struct BiTNode *LChild, * RChild; BiTNode, *BiTree;int JudgeSimilar(BiTree &T1,BiTree &T2)/ 判断两树二叉树是否相似if( (!T1 & !T2) )return 1;else if( (T1 & !T2) | (!T1 & T2) )return 0;else if(!T1-lchild & !T1-rchild & !T2-lchild & !T2-rchild)return 1;else if( JudgeSimilar(T1-lchild,T2-lchild) & JudgeSimilar(T1-rchild,T2-rchild) )return 1;elsereturn 0;得分评卷人七、计算（每小题4分，共12分）1、对比f(n)和g(n)，当n接近无穷时，哪个函数增长更快。 A