资源描述：
《最新数据结构习题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、习题4-11.有六个元素A、B、C、D、E、F依次进栈，允许任何时候出栈，能否得到下列每个序列。（1）CDBEFA（2）ABEDFC（3）DCEABF（4）BAEFCD2.有4个元素a,b,c,d依次进栈，任何时侯都可以出栈，请写出所有可能出栈序列和所有不存在的序列。3.用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有五个元素：23，45，67，80，34，其中，23尾队首元素，front的值为3，请画出对应的存储状态，当连续做4次出队运算后，再让15，36，
2、48元素依次进队，请再次画出对应的存储状态。4.假定用于顺序存储一个队列的数组的长度为N，队首和队尾指针分别为front和rear，写出求此长度（即所含元素个数）的公式。习题4-2算法分析，写出该算法的功能。1intAE(inta[],intn){if(n==0)return0;elsereturna[n-1]+AE(a,n-1);}2.intAF(intk,ints)//第一次使用AF(0,0)调用此算法{if(s>=100)returnk-1;else{k++;s+=k*k;returnAF(k,s);}}
3、3.voidFun1(Stack&s1,intn){srand(time(0);inti=0,j;while(iy&&x>10){i++;Push(s1,x);}}4.voidFun2(Queue&q1,Queue&q2,intn){inti,x;cout<<”从键盘输入”<>
4、x;if(x%2)Enqueue(q1,x);elseEnqueue(q2,x);}}习题4-3算法设计1.写出采用递归方法求1~n之间所有整数的平方和的算法。2.采用递归方法把任一十进制正整数转换为S进制（2≤S≤9）数输出。3.采用辗转相除法和递归的方法求出两个正整数的最大公约数。4.采用递归方法求两个正整数的最小公倍数。5.裴波那契(Fibonacci)数列的定义为：它的第1项和第2项为0和1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fib(n)表示，则计算公式为：Fib(n)=试编写计算Fib
5、(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。习题5-1运算题1.已知一棵度为m的树中有n个度为1的结点，n个度为2的结点，…，n个度为m的结点，问树中有多少个叶子结点？2.画出由三个结点a、b、c组成的所有不同结构的二叉树，则共有多少种不同的结构？每一种结构又对应多少种不同的值的排列次序？3.设一棵二叉树广义表表示为a(b(c),d(e,f)),分别写出对它进行先序、中序、后序、按层遍历的结果。4.设一棵二叉树的广义表表示为a(b(,e),c(f(h,i),d))分别写出对它进行先序、中序
6、、后序、按层遍历的结果。5.已知一棵二叉树的先根和中根序列，求该二叉树的后根序列。先根序列：A,B,C,D,E,F,G,H,I,J中根序列：C,B,A,E,F,D,I,H,J,G后根序列：6.已知一棵二叉树中根和后根序列，求出该二叉树的高度和双支、单支和叶子节点数。中根序列：c,b,d,e,a,g,i,h,j,f后根序列：c,e,d,b,i,j,h,g,f,a习题5-21.下面函数的功能是返回二叉树BT中值为X的节点所在层号，请在划有横线的地方填写合适的内容。intNodelevel(BTreeNode*BT,
7、ElemTypex){if(BT==NULL)return0;elseif(BT->data==X)return1;else{intc1=Nodelevel(BT->left,X);if(c1>=1)_________________;intc2=___________________;if________________________;//若树中不存在X节点则返回0return0;}}2.指出下面函数的功能。BTreeNode*BTreeSwapX(BTreeNode*BT){if(BT==NULL)ret
8、urnNULL:else{BTreeNode*pt=newBTreeNode;pt->data=BT->data;pt->right=BTreeSwapX(BT->left);pt->left=BTreeSwapX(BT->right);returnpt;}}3.已知二叉树中的节点类型StreeNode定义如下。structStreeNode(datatypedata;STreeNod
