1、程序员习题程序员习题1）经过以下栈运算后，x的值是_。InitStack(s); Push(s,a); Push(s,b); Pop(s,x); GetTop(s,x);A. a B. bC. 1 D. 02) 经过以下栈运算后，StackEmpty(s)的值是_。 InitStack(s); Push(s,a); Push(s,b); Pop(s,x); Pop(s,y); A. a B. b C. 1 D. 03) 设一个栈的输入序列为A,B,C,D, 则借助一个栈所得到的输出序列不可能是_. A). A.B.C.D B) D.C.B.A C). A.C.D.B D). D.A.B.C4)
2、 一个栈的进栈序列是a.b.c.d.e, 则栈的不可能的输出序列是_ A.edcb B.decba C.dceab D. abcde5) 已知一个栈的进栈序列是 1,2,3,n,其输出序列的第一个元素是i，则第j个出栈元素是_ A.j B.n-I C.z-i+1 D.不确定6） 已知一个栈的进栈序列是1,2,3,.,n, 其输出序列是p1,p2,pn, 若p1=n, 则p1的值是_. A.I Bn-I Cn-i+1 D 不确定7） 设n个元素的进栈序列为p1,p2,p3,pn, 其输出序列为1,2,3,n, 若pn=1,则pi(1=i1)的递归出口是_.A.f(1)=0 B.f(1)=1 C.
3、f(0)=1 D.f(n)=n 15) 经过以下队列运算后，队头的元素是_. InitQuue(qu); enQueue(qu,a); enQueue(qu,b); enQueue(qu,c); deQueue(qu);A.a B.b C.1 D.016) 元素A,B,C,D顺序连续进入队列qu后，队头元素是_,队尾元素是_.A.A B.B C.C D.D17) 一个队列的入列序列为1234，则队列可能的输出序列是_.A.4321 B.1234 C.1432 D. 3241 18) 队列是一种具有_特性的线性表。19）顺序队和连队的区别仅在于_的不同。20）如果队列的最大长度难以估计，则最好使
4、用_.21）环形队列qu的队满条件是_. A. (qu. rear+1)%maxSize = (qu.front+1)%MaxSize B. (qu. rear+1)%MaxSize=qu.front+1; C. (qu.rear+1)%MaxSize=qu.front+1; D. qu.rear=qu.front22) 最适合用作列队的列表是_.A. 带队首指针和队尾指针的循环单连表B. 带队首指针和队尾指针的非循环单链表C. 只带队首指针的循环单链表D. 只带队尾指针的循环单链表23）最不合适用做链队的链表是A.只带队首指针的非循环双链表。B只带队首指针的循环双链表。C. 只带队尾指针的循
5、环双链表。D. 只带队尾指针的循环单链表。24）.假设一个练队的队尾和队首指针分别为rear front则判断队空的条件是A front=rearB front!=NULLC rear!=NULLD front=NULL25)用单链表表示的链队的队头在链表的_位置A. 链头 B链尾C链中D以上都可以26）用单链表表示的链队的队尾在链表的_位置A. 链头 C链中B链尾D以上都可以27）对于链队在进行删除操作时A 仅修改头指针B仅修改尾指针C 头尾指针都要修改D头尾指针可能都要修改填空题1若用带表头结点的单链表表示则队列为空的标志是_.2若用不带表头结点的单链表表示则创建一空队列的所要执行的操作是
6、_.3若用带头结点的单链表表示则创建一空队列的所要执行的操作是_.4已知链队的头尾指针分别是f和r则将值x如队的操作是 P=(QNode *)malloc (sizeof(QNode);p-data=x; _;_;_;5表达式23+（12*3-2）/4+34*5/7）+108/9的后缀表达式是_6;程序：1有如下算法：Void print (int w) Int i; If (w!=0) Print(w-1); For (i=1;i0) return_; Else _;4. 递归函数int dec(int a, int n)判断数组a的前n个元素是否递增， 递增返回0； int dec(int
7、 a, int n)if(n=1)_; If(a0a1)return 0; Else _;5. 递归函数invert (int a, int k)将指定数组中的前k 个元素逆置 Void invert (int a, int k)int t;If(_)invert(_); T=a0; A0=ak-1;ak-1=t; 6. int dec(int n)的功能是计算n!.如调用dec(6)后函数的反回值是120 int dec(int n)if (n写出下列程序字段的输出结果（栈的元素类型SElemType为char）Void main()Stack S;Char x,y;InitStack(S)
8、;X=c;y=k;Push(S,x); push(S,a); push(S,y);Pop(S,x); push(S,t); push(S,x);Pop(S,x); push(S,s);While(!StackEmty(S)pop(S,y);printf(y);Printf(x);2简述以下算法的功能（栈的元素类型SElemType为int）Status algo2(Stack S,int e)Stack T;int d;InitStack(T);While(!StackEmpty(S)pop(S,d);If(d!=e)push(T,d);While(!StackEmpty(S)pop(T,d)
9、;Push(S,d);3写出以下程序段的输出结果（队列中元素类型QElemType为char）Void main()Queue Q; InitQueue(Q);Char x=e,y=c;EnQueue(Q,h); EnQueue(Q,r); EnQueue(Q,y);DeQueue(Q,x); EnQueue(Q,x);DeQueue(Q,x); EnQueue(Q,a);While(!QueueEmpty(Q)DeQueue(Q,y); Printf(y);Printf(x);4函数MultibaseOutput(long n,int B)的功能是：将一个无符号十进制数n转换成B（2=Bel
10、em=(int * )malloc(n*sizeof(int);If(S-elem=NULL) return -1;S-max=n;_=0;Return 0; Int push(Stack *S,int item )/*将整数item压入栈中*/if(S-top=S-max)printf(*Stack is full!n); Return -1;_=irem; Return 0;Int StackEmpty(Stack S) Return(!S.top)?1:0;/*判断栈是否为空*/Int pop(Stack *S)栈顶元素出栈*/ If(S-top)printf(“pop an empty
11、 stack!n”); Return -1;Return _;Void MultibaseOutput(long n,int B) Int m;Stack S;If(InitStack(&S,MAXSIZE)printf(“Failure!n”); Return; Doif(push(&S,_)printf(“Failure!n”);Return;N=_;while(n!=0);While(!StackEmpty(S)/*输出B进制数*/m=pop(&S);If(mt时返回正数,s=t时返回0,st时返回负数 /StrCompare13.编写算法,实现串的基本操作Replace(char *S
12、,T,V). bool repl(SString &News, SString S, SString T,SString V) /repl14.编写算法,求串s所含不同字符的总数和每种字符的个数。15.假设以结点大小1(且附设头结点)的连表结构表示串,试编写实现下列六种串的基本操作: StrAssign,StrCopy,StrCompare,StrLenght,ConCat和SubString的函数.62 典型例题解析61一棵完全二叉树第6层有7个结点，则共有（）个结点，其度为1的结点有（）个，度为0的结点有（）个，编号最大的非叶子结点是（），编号最小的叶子结点是（）。62 试回答下面的问题：
13、已知一棵满二叉树的结点个数为2040的数，试问此二叉树的叶子结点有多少个？有n个结点的二叉树，已知叶子结点的个数为n0， 写出求度为1的结点的个数n1计算公式；若此数是高度为h的完全二叉数，写出n为最小的公式；若二叉数中仅有度为0和度为2的结点，写出该二叉数结点个数n的公式。 （3） 已知一棵度位m的树中有n1 个度为1的结点，n2个度为2的结点，,Nm个度为m的结点,问该树有多少个叶子结点?63.已知有一棵二叉树的中序遍历序列为DBEHAFCIG，后序遍历是DHEBFIGCA，试画出该二叉树，并给出该二叉树的的前序序列。65设二叉树用二叉链表表示，设计算法： （1）求二叉树的高度； （2）求
14、二叉树的度为2的结点数；66试编写算法判断二叉树T是否是完全二叉树； （1）若给定的二叉树采用顺序表作为存储结构； （2）若给定的二叉树采用二叉链表作为存储结构。67 对以二叉链表存储的非空而叉树，从右向左依次释放所有的叶子结点，释放的同时，把结点存放到一个数组中。要求： （1）用文字写出实现上述过程的基本思想。 （2）写出算法，68试以二叉树链表的存储结构，编写按层次顺序遍历二叉树的算法。69假设二叉树以二叉链表为存储结构，编写求任一指定结点所在的层次。611设计算法，统计一棵二叉树中所有结点的数目及非叶子结点的数目。614已知以二叉链表表示的二叉树中有值为x，y，z的三个结点，试编写算法判
15、断x是否为y和z的共同祖先。616假设二叉树的存储结构为二叉链表，试编写C语言的函数，其功能是交换二叉树中各结点的左子树和右子树。618已知一棵二叉树用二叉链表存储，root指向根结点，p指向树中任何一结点。试编写算法输出从rootp路径上的结点。620编写一个算法，利用叶子结点中的空指针域，将所有叶子结点链接为一个带有头结点的单链表，算法返回头结点的地址。621假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。6.3 习题及参考答案1.已知一棵树边的集合为, 请画出这棵树,并回答下列问题: (1)哪个是根结点? (2)哪些是叶子结点? (3)哪些是结点G的双亲? (4)哪些是
16、结点G的祖先? (5)哪些是结点G的孩子? (6)哪些是结点E的子孙? (7)哪些是结点E的兄弟?哪些是结点F的兄弟? (8)结点B和N的层次号分别是什么? (9)树的深度是多少? (10)以结点C为根的子树的深度是多少?2.一棵度为2的树与一棵二叉树有何区别?3.试分别画出具有3个结点的树和3个结点的二叉树的所有不同的形态.4.一棵深度为H的满K叉树有如下性质:第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树,如果按层次顺序从1开始全部结点编号,问: (1)各层的结点数目是多少? (2)编号为p的结点的父结点(若存在)的编号是多少? (3)编号为p的第i的儿子结点（若存在）的编
17、号是多少？(4)编号为p的结点有右兄弟的条件是什么?其右兄弟的编号是多少?5.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点,.nk个度为k的结点,问该树中有多少个叶子结点?6.已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点,试求该树含有叶子结点的数目.7.一棵含有n个结点k叉树,可能达到的最大深度和最小深度各为多少?9对题3所得各种形态的二叉树，分别写出前序，中序和后序遍历的序列。10假设n和m为二叉树中两结点，有“1”，“0”或“（分别表示肯定，恰恰相反或者不一定）填写下表。 答 问已知前序遍历时n在m前？中序遍历n在m前？后序遍历时n在m前？n 在m
18、左方n 在m 右方n 是m 祖先n 是m 子孙11找出所有满足下列条件的二叉树：（1）他们在先序遍历和中序遍历时，得到的结点访问序列相同；（2）他们在后序遍历和中序遍历时 ，得到的结点访问序列相同；（3）他们在先序遍历和后序遍历时，得到的结点访问序列相同；12请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。 19.画出和下列已知序列对应的树T： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。21.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK. 请画出该树.22.假设一棵二叉树的中序序列
19、为DCBGEAHFIJK和后序序列为DCEGBFHKJIA. 请画出该树.29.编写递归算法,在二叉树中求位于先序序列中第K个位置的结点的值.30.编写递归算法,计算二叉树中叶子结点的数目.30.编写递归算法,将二叉树中所有结点的左,右子树相互交换.32.编写递归算法:求二叉树中以元素值为X的结点为根的子树的深度;33.编写递归算法:对于二叉树中每一个元素值为X的结点,删去以它为根的子树,并释放相应的空间.34.编写复制一棵二叉树的非递归算法.35.编写按层次顺序(同一层从左至右)遍历二叉树的算法.36.在二叉树中,*root为根结点,*p和*q为二叉树中两个结点,试编写求距离它最近的共同祖先
20、的算法.41.试编写算法,求给定二叉树上从根到叶子结点的一条其路径长度等于树的深度减一的路径(即列出从根结点到该叶子结点的结点序列),若这样的路径存在多条,则输出路径终点 (叶子结点) 在最左的一条.42.已知一棵完全二叉树存于顺序表sa中,sa.elemsa.last中存放各结点的数据元素. 试编写算法由此顺序存储结构建立该二叉树的二叉链表.43.为二叉链表的结点增加DescNum域.试编写一算法,求二叉树的每个结点的子孙数目并且存入其DescNum域，请给出算法的时间复杂度。44.试写一算法,在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继(假设二叉树的根结点未知).并讨论实现此
21、算法对存储结构有何要求?45.试写一算法,在后序后继线素二叉树中，查找给定结点*p在后序序列中的后继（二叉树的根结点指针并没给出）。并讨论实现算法对存储结构有什么要求？四：算法设计题 1社设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将元素S插入到线性表的适当位置，以保持线性表的有序性，并且给出算法的时间复杂度。2针对下面的问题，设计算法，要求算法的时间复杂度均为O（n）。 （1）已知数组An的元素类型为整型,设计算法调整A,使其左边的所有元素小于零,右边的元素大于零。 （2）设计算法，将一个带头结点的单链表A分解为两个具有相同结构的单链表B和C，其中B 链表的结点为A链表中值小于零的结点，而C链表的结点为A 链表中值大于等于零的结点（假设单链表
