数据结构题9324习1
精品文档
习题4-1
1.有六个元素A、B、C、D、E、F依次进栈，允许任何时候出栈，能否得到下列每个序列。
（1）CDBEFA （2）ABEDFC （3）DCEABF （4）BAEFCD
2. 有4个元素a,b,c,d依次进栈，任何时侯都可以出栈，请写出所有可能出栈序列和所有不存在的序列。
3.用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有五个元素：23，45，67，80，34，其中，23尾队首元素，front的值为3，请画出对应的存储状态，当连续做4次出队运算后，再让15，36，48元素依次进队，请再次画出对应的存储状态。
4. 假定用于顺序存储一个队列的数组的长度为N，队首和队尾指针分别为front和rear，写出求此长度（即所含元素个数）的公式。 习题4-2 算法分析，写出该算法的功能。 1 int AE(int a[],int n) {
if(n==0) return 0;
else return a[n-1]+AE(a,n-1); }
2.int AF(int k,int s)//第一次使用AF(0,0)调用此算法 { if(s>=100) return k-1; else { k++;s+=k*k;return AF(k,s); } }
3. void Fun1(Stack& s1,int n) {
srand(time(0); int i=0,j; while(i int x=rand()0; int y=int(sqrt(x)); for(j=2;j<=y;j++) if(x%j==0)break; if(j>y&&x>10){i++;Push(s1,x);} } 4. void Fun2(Queue& q1,Queue& q2,int n) { int i,x;cout<<”从键盘输入”< 收集于网络，如有侵权请联系管理员删除 精品文档 for(int i=1;i<=n;i++){cin>>x;if(x%2) Enqueue(q1,x);else Enqueue(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)=??n?1............................................(n?1或2) Fib(n?1)?Fib(n?2)...........(n??2)?试编写计算Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。 习题5-1 运算题 1.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问树中有多少个叶子结点？ 2.画出由三个结点a、b、c组成的所有不同结构的二叉树，则共有多少种不同的结构？每一种结构又对应多少种不同的值的排列次序？ 3. 设一棵二叉树广义表表示为a(b(c),d(e,f)),分别写出对它进行先序、中序、后序、按层遍历的结果。 4. 设一棵二叉树的广义表表示为a(b(,e),c(f(h,i),d))分别写出对它进行先序、中序、后序、按层遍历的结果。 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-2 1. 下面函数的功能是返回二叉树BT中值为X的节点所在层号，请在划有横线的地方填写合适的内容。 int Nodelevel(BTreeNode *BT,ElemType x) { if(BT==NULL) return 0; else if(BT->data==X)return 1; else { int c1=Nodelevel(BT->left,X); if(c1>=1)_________________; int c2=___________________; if________________________; } } //若树中不存在X节点则返回0 return 0; 2.指出下面函数的功能。 BTreeNode* BTreeSwapX(BTreeNode* BT) { if(BT==NULL) return NULL: else{ BTreeNode* pt = new BTreeNode; pt->data=BT->data; pt->right=BTreeSwapX(BT->left); pt-> left =BTreeSwapX(BT-> right); return pt; } } 3. 已知二叉树中的节点类型StreeNode定义如下。 struct StreeNode(datatype data;STreeNode *lchild,*rchild,*parent;); 收集于网络，如有侵权请联系管理员删除 精品文档 其中，data为节点值域，lchild和rchild分别为指向左、右孩子节点的指针域，parent为指向父亲节点的指针域。根据下面函数的定义指出函数的功能。算法中的参数ST指向一颗二叉树，X保存一个节点的值。 STreeNode* PN(STreeNode *ST,datatype& X) { if(ST==NULL) return NULL; else { StreeNode* mt; if(ST->dat==x) return ST->parent; else if(mt=PN(ST->lchild,X)) return mt; else if(mt=PN(ST->rchild,X)) return mt; return NULL; } } 4.指出下面函数的功能。 void BTC(BTreeNode*BT) { if(BT!=NULL) { if(BT->left!=NULL && BT->right!=NULL) if(BT->left->data>BT->right->data) { BTreeNode*t=BT->left; BT->left=BT->right; BT-right=t; } BTC(BT->left); BTC(BT->right); } } 5. 设BT指向一棵二叉树，该二叉树的广义表表示为a(b(a,d(f)),c(e(,a(k)),b)),则依次使用 BTC(BT,’a’,C)、BTC(BT,’b’,C)、BTC(BT,’c’,C)、BTC(BT,’g’,C)、调用下面算法时，假定每次调用时C的初值均为0，引用变量带回值依次为______、______、______、______。 void BTC(BTreeNode*BT,char x,int& k) { if(BT!=NULL){ if(BT->data==x) k++; BTC(BT->left,x,k); BTC(BT->right,x,k); } } 6.下面函数功能 收集于网络，如有侵权请联系管理员删除
数据结构习题19324上课讲义
