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

（共8页第-1-页）09计本《数据结构》期中练习题一、选择题:1.下面程序段的时间复杂度为(D)s=0；for(i=1；in；i++)for(j=1；ji；j++)s+=i*j；A.O(1)B.O(logn)C.O(n)D.O(n2)2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为(A)A.q-next=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.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为(B)A.(rear-length+m+1)％mB.(rear-length+m)％mC.(rear-length+m-1)％mD.(rear-length)％m5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是(D)A.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，46.下列图示的顺序存储结构表示的二叉树是(A)（共8页第-2-页）7．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为(C)A．4B．5C．6D．78．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B）A．不一定相同B．都相同C．都不相同D．互为逆序9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（C）A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法10.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是(A)的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子（共8页第-3-页）二、填空题:1.在一个长度为100的顺序表中删除第10个元素时，需移动_______90_________个元素。2.队列的队尾位置通常是随着____入队____操作而变化的。3.已知一棵哈夫曼树含有60个叶子结点，则该树中共有______59____个非叶子结点。4.已知完全二叉树T的第5层只有7个结点，则该树共有____11___个叶子结点。5．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为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.voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={1,5,8,12,15};for(i=0;i5;i++)Push(S,2*a[i]);while(!StackEmpty(S))print(Pop(S));}该算法被调用后得到的输出结果为：（共8页第-4-页）302416102102.voidABC(BTNode*BT,int&c1,int&c2){if(BT!=NULL){ABC(BT-left,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);Inta[]={100,26,57,34,79};For(i=0;i5;i++)ListInsert(La,1,a[i]);（2）ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);（3）ClearList(La);For(i=0;i5;i++)ListInsert(La,i+1,a[i]);7934572610034572610079100265734794.有如下递归过程：voidprint(intw){intI;if(w!=0){print(w-1);for(I=1;I=w;I++)printf(“%3d”,w);printf(“\n”);}}（共8页第-5-页）调用语句print(4)的结果是什么？1223334444Pressanykeytocontinue12233344445.写出下述算法A的功能：其中BiTree定义如下:TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)){DeQueue(Q,e);If(e==NULL)break;Else{Print(e.data);ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);}}}先序遍历二叉树的非递归算法五、编写算法（每小题10分，共20分）1．编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明零时变量、指针）。（共8页第-6-页）该链表带头节点、头节点和数据节点的结构定义如下typedefstructLNode{ElemTypedata;StructLNode*next;}List,LNode;函数定义：voidinvert(List&L)Statuszy22(LinkList&L)//就地逆序链表{//找到第一个首元结点//让下一个结点插到首元结点前，直到链表尾LinkListp,q;p=L-next;L-next=NULL;while(p){q=p-next;p-next=L-next;L-next=p;p=q;}returnOK;}//zy222．编写算法判定两棵二叉树是否相似，所谓两课树相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。其中树节点定义如下typedefstructBiTNode{DataTypedata;StructBiTNode*LChild,*RChild;}BiTNode,*BiTree;intJudgeSimilar(BiTree&T1,BiTree&T2){//判断两树二叉树是否相似if((!T1&&!T2))（共8页第-7-页）return1;elseif((T1&&!T2)||(!T1&&T2))return0;elseif(!T1-lchild&&!T1-rchild&&!T2-lchild&&!T2-rchild)return1;elseif(JudgeSimilar(T1-lchild,T2-lchild)&&JudgeSimilar(T1-rchild,T2-rchild))return1;elsereturn0;}得分评卷人七、计算（每小题4分，共12分）1、对比f(n)和g(n)，当n接近无穷时，哪个函数增长更快。Af(n)=(ln(n!)+5)2g(n)=13n2.5Bf(n)=2(n*n*n)+(2n)2g(n)=n(n*n)+n5（共8页第-8-页）2、具有n个节点的满二叉树的叶子节点的个数是多少？3、试写出递归函数F(n)的递归算法，并画出F(4)时的调用过程。1n=0(){*(/2)n0nFnnFn