程序员习题.docx
《程序员习题.docx》由会员分享，可在线阅读，更多相关《程序员习题.docx（25页珍藏版）》请在冰点文库上搜索。
程序员习题
程序员习题
1）经过以下栈运算后，x的值是_____________。
InitStack（s）;Push（s,a）;Push（s,b）;Pop（s,x）;GetTop（s,x）;
A.aB.b
C.1D.0
2）经过以下栈运算后，StackEmpty（s）的值是___________。
InitStack（s）;Push（s,a）;Push（s,b）;Pop（s,x）;Pop（s,y）;
A.aB.b
C.1D.0
3）设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是___________.
A）.A.B.C.DB）D.C.B.A
C）.A.C.D.BD）.D.A.B.C
4）一个栈的进栈序列是a.b.c.d.e,则栈的不可能的输出序列是___________’
A.edcbB.decbaC.dceabD.abcde
5）已知一个栈的进栈序列是1,2,3,……,n,其输出序列的第一个元素是i，则第j个出栈元素是_______________’
A.jB.n-IC.z-i+1D.不确定
6）已知一个栈的进栈序列是1,2,3,…..,n,其输出序列是p1,p2,……,pn,若p1=n,则p1的值是_____________.
A.IBn-ICn-i+1D不确定
7）设n个元素的进栈序列为p1,p2,p3,……,pn,其输出序列为1,2,3,……,n,若pn=1,则pi（1<=i<=n-1）的值___________.
A.n-i+1B.IC.ID.有多种可能
8）栈是一种具有_________________特性的线性表。
9）顺序栈和链栈的区别仅在于_____________的不同？
10）如果栈的最大长度难以估计，那么最好使用__________________栈。
11）一个栈的输入序列是12345，则栈的输出序列12345可不可能出现。
12）判定一个顺序栈st为（元素个数最多为Maxsize）空的条件为_____________.
A.st.top==-1;B.st.top!
=-1;
C.st.top!
=Maxsize;D.st.top==Maxsize;
13）判定一个顺序栈st为（元素个数最多为Maxsize）满的条件为______________.
A.st.top!
=-1;B.st.top==-1;
C.t.top!
=Maxsize-1;D.st.top==axsize-1;
14）递归模型f（n=f（n-1）+n（n>1）的递归出口是___________.
A..f
（1）=0B.f
（1）=1C.f（0）=1D.f（n）=n15）经过以下队列运算后，队头的元素是____________.
InitQuue（qu）;enQueue（qu,’a’）;enQueue（qu,’b’）;enQueue（qu,’c’）;deQueue（qu）;
A.aB.bC.1D.0
16）元素A,B,C,D顺序连续进入队列qu后，队头元素是____________,队尾元素是_______.
A.AB.BC.CD.D
17）一个队列的入列序列为1234，则队列可能的输出序列是______________.
A.4321B.1234C.1432D.3241
18）队列是一种具有___________特性的线性表。
19）顺序队和连队的区别仅在于______________的不同。
20）如果队列的最大长度难以估计，则最好使用_____________.
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.front
22）最适合用作列队的列表是__________.
A.带队首指针和队尾指针的循环单连表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的循环单链表
D.只带队尾指针的循环单链表
23）最不合适用做链队的链表是
A.只带队首指针的非循环双链表。
B．只带队首指针的循环双链表。
C.只带队尾指针的循环双链表。
D.只带队尾指针的循环单链表。
24）.假设一个练队的队尾和队首指针分别为rearfront则判断队空的条件是
Afront==rear
Bfront!
==NULL
Crear!
==NULL
Dfront==NULL
25）用单链表表示的链队的队头在链表的_______位置
A.链头
B．链尾
C．链中
D．以上都可以
26）用单链表表示的链队的队尾在链表的_______位置
A.链头C．链中
B．链尾D．以上都可以
27）对于链队在进行删除操作时
A仅修改头指针
B仅修改尾指针
C头尾指针都要修改
D头尾指针可能都要修改
填空题
1．若用带表头结点的单链表表示则队列为空的标志是_______.
2．若用不带表头结点的单链表表示则创建一空队列的所要执行的操作是_______.
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．有如下算法：
Voidprint（intw）
{
Inti;
If（w!
=0）
{
Print（w-1）;
For（i=1;i<=w;i++）
Printf（“%d”,w）;
Printf（“\n”）;
}}
调用语句print（4）的结果_______。
2．有如下递归过程：
Voidreverse（intm）
{printf（“%d”,n%10）;
If（n/10!
=0）reverse（n/10）;
}
调用语句reverse（582）的结果是________。
3.递归函数sum（inta[],intn）的返回值是数组a[]的前n个元素之和。
Intsum（inta[],intn）
{if（n>0）return_______;
Else________;
}
4.递归函数intdec（inta[],intn）判断数组a[]的前n个元素是否递增，递增返回0；
intdec（inta[],intn）
{if（n<=1）________;
If（a[0]Else________;
}
5.递归函数invert（inta[],intk）将指定数组中的前k个元素逆置
Voidinvert（inta[],intk）
{intt;
If（_______）{invert（____________）;
T=a[0];
A[0]=a[k-1];a[k-1]=t;
}
}
6.intdec（intn）的功能是计算n!
.如调用dec（6）后函数的反回值是120
intdec（intn）{if（n<2）_________;
elsereturn（________）;
}
7.递归函数intfib（intn）的功能是计算fibonacci数列的第n项
intfib（intn）{if（n==0）________;
elseif（_________）return1;
else_________;
}
判断：
1）栈低元素是不能删除的元素。
2）顺序栈中元素值的大小是有序的。
3）在n个元素进栈后，他们的出栈顺序和进栈顺序正好相反。
4）栈顶元素和栈底元素有可能是同一元素。
5）若用s[1]~s[m]表示顺序栈的存储空间，则对栈的进栈，出栈操作最多只能进行m次。
6）栈是一种对进栈，出栈操作总次数做了限制的线性表。
7）对顺序栈进行进栈，出栈操作，不涉及元素的前后移动问题。
8）栈是一种对进栈，出栈操作的次序做了限制的线性表。
9）空栈没有栈顶指针。
10）栈和队列都是限制存取端的线性表。
11）队列是一种对进队列，出队列操作的次序做了限制的线性表。
12）n个元素进队列的顺序和出队列的顺序总是一致的。
13）顺序队中有多少元素，可以根据队首指针的值和队尾指针的值来计算。
14）若用“队首指针的值和队尾指针的值相等”作为环形顺序队为空的标志，则在设置一个空队时，只需给队首指针和队尾指针赋同一个值，不管什么值都可以。
15）无论是顺序队还是链队，进队，出队操作的时间复杂度都是O
（1）.
解答题：
1）设有一个数列的输入顺序为123456，若采用栈结构，并以A和D分别表示进栈和出栈操作，试问通过进栈和出栈操作的合法序列。
（1）能否得到输出序列为325641的序列？
（2）能否得到输出序列为154623的序列？
2）说说线性表，栈和队列的异同。
3）设栈s和队列q的初始状态都为空，元素a,b,c,d,e和f依次通过栈s，一个元素出栈后既进入队列q，若6个元素出队的序列是bdcfea,则栈s的容量至少应该存多少个元素？
程序题：
1>写出下列程序字段的输出结果（栈的元素类型SElemType为char）
Voidmain（）
{StackS;
Charx,y;
InitStack（S）;
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）
Statusalgo2（StackS,inte）
{StackT;intd;
InitStack（T）;
While（!
StackEmpty（S））
{pop（S,d）;
If（d!
=e）push（T,d）;
}
While（!
StackEmpty（S））
{pop（T,d）;
Push（S,d）;
}
}
3>写出以下程序段的输出结果（队列中元素类型QElemType为char）
Voidmain（）
{QueueQ;InitQueue（Q）;
Charx=’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（longn,intB）的功能是：
将一个无符号十进制数n转换成B（2<=B<=16）进制整数并输出。
该函数先将转换过程中得到的各位数字入栈，转换结束后把B进制从栈中输出。
有关操作的各函数功能见相应函数中的注释。
C代码中的符号常量及栈的类型定义如下：
#defineMAXSIZE32
Typedefstruct{
Int*elem;/*栈的存储区*/
Intmax;/*栈的容量，即栈中最多能存放的元素个数*/
Inttop;/*栈的指针*/
}Stack;
C代码
IntInitSack（Stack*s,intn）
{S->elem=（int*）malloc（n*sizeof（int））;
If（S->elem==NULL）return-1;
S->max=n;
_____________=0;
Return0;
}`
Intpush（Stack*S,intitem）/*将整数item压入栈中*/
{if（S->top==S->max）{printf（*Stackisfull!
\n）;
Return-1;
}
_____________=irem;
Return0;
}
IntStackEmpty（StackS）
{
Return（!
S.top）?
1:
0;/*判断栈是否为空*/
}
Intpop（Stack*S）栈顶元素出栈*/
{
If（S->top）{printf（“popanemptystack!
\n”）;
Return-1;
}
Return__________;
}
VoidMultibaseOutput（longn,intB）
{
Intm;StackS;
If（InitStack（&S,MAXSIZE））{printf（“Failure!
\n”）;
Return;
}
Do{if（push（&S,________））{printf（“Failure!
\n”）;
Return;}
N=________;
}while（n!
=0）;
While（!
StackEmpty（S））/*输出B进制数*/
{m=pop（&S）;
If（m<10）printf（“%d”,m）;/*小于10，输出数字*/
Elseprintf（“%c”,m+55）;/*大于或等于10，输出相应的字符*/
}
Printf（“\n”）;}
8.编写一个实现串的置换操作Replace（char*S,T,V）的算法
intReplace（StringType&s,StringTypeT,StringTypeV）//将串中S中所有子串T替换V并返回置换次数
{
}//Replace
9.编写算法,从串s中删除所有和串t相同的子串.
intDelete_SubString（StringType*s,StringTypet）/从串s中删除所有与t相同的子串,并返回删除次数
{
}//Delete_SubString
11.编写算法,实现串的基本操作StrAssign（char*T,chars）
voidStrAssign（StringType&T,charchars&#）//用字符数组chars给串T附值
{
}//StrAssign
12.编写算法,实现串的基本操作StrCompare（S,T）.
charStrCompare（StringTypes,StringTypet）//串的比较,s>t时返回正数,s=t时返回0,s{
}//StrCompare
13.编写算法,实现串的基本操作Replace（char*S,T,V）.
boolrepl（SString&News,SStringS,SStringT,SStringV）
{
}//repl
14.编写算法,求串s所含不同字符的总数和每种字符的个数。
15.假设以结点大小1（且附设头结点）的连表结构表示串,试编写实现下列六种串的基本操作:
StrAssign,StrCopy,StrCompare,StrLenght,ConCat和SubString的函数.
6．2典型例题解析
6．1一棵完全二叉树第6层有7个结点，则共有（）个结点，其度为1的结点有（）个，度为0的结点有（）个，编号最大的非叶子结点是（），编号最小的叶子结点是（）。
6．2试回答下面的问题：
已知一棵满二叉树的结点个数为20~40的数，试问此二叉树的叶子结点有多少个？
有n个结点的二叉树，已知叶子结点的个数为n0，
写出求度为1的结点的个数n1计算公式；
若此数是高度为h的完全二叉数，写出n为最小的公式；
若二叉数中仅有度为0和度为2的结点，写出该二叉数结点个数n的公式。
（3）已知一棵度位m的树中有n1个度为1的结点，n2个度为2的结点，……,Nm个度为m的结点,问该树有多少个叶子结点?
6．3.已知有一棵二叉树的中序遍历序列为DBEHAFCIG，后序遍历是DHEBFIGCA，试画出该二叉树，并给出该二叉树的的前序序列。
6．5设二叉树用二叉链表表示，设计算法：
（1）求二叉树的高度；
（2）求二叉树的度为2的结点数；
6．6试编写算法判断二叉树T是否是完全二叉树；
（1）若给定的二叉树采用顺序表作为存储结构；
（2）若给定的二叉树采用二叉链表作为存储结构。
6．7．对以二叉链表存储的非空而叉树，从右向左依次释放所有的叶子结点，释放的同时，把结点存放到一个数组中。
要求：
（1）用文字写出实现上述过程的基本思想。
（2）写出算法，
6．8．试以二叉树链表的存储结构，编写按层次顺序遍历二叉树的算法。
6．9假设二叉树以二叉链表为存储结构，编写求任一指定结点所在的层次。
6．11设计算法，统计一棵二叉树中所有结点的数目及非叶子结点的数目。
6．14已知以二叉链表表示的二叉树中有值为x，y，z的三个结点，试编写算法判断x是否为y和z的共同祖先。
6．16假设二叉树的存储结构为二叉链表，试编写C语言的函数，其功能是交换二叉树中各结点的左子树和右子树。
6．18已知一棵二叉树用二叉链表存储，root指向根结点，p指向树中任何一结点。
试编写算法输出从root~p路径上的结点。
6．20编写一个算法，利用叶子结点中的空指针域，将所有叶子结点链接为一个带有头结点的单链表，算法返回头结点的地址。
6．21假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
6.3习题及参考答案
1.已知一棵树边的集合为{,,,,,,,,,,,},
请画出这棵树,并回答下列问题:
（1）哪个是根结点?
（2）哪些是叶子结点?
（3）哪些是结点G的双亲?
（4）哪些是结点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的儿子结点（若存在）的编号是多少？
（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左方
n在m右方
n是m祖先
n是m子孙
11．找出所有满足下列条件的二叉树：
（1）他们在先序遍历和中序遍历时，得到的结点访问序列相同；
（2）他们在后序遍历和中序遍历时，得到的结点访问序列相同；
（3）他们在先序遍历和后序遍历时，得到的结点访问序列相同；
12．请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。
19.画出和下列已知序列对应的树T：
树的先根次序访问序列为GFKDAIEBCHJ；
树的后根次序访问序列为DIAEKFCJHBG。
21.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK.
请画出该树.
22.假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA.
请画出该树.
29.编写递归算法,在二叉树中求位于先序序列中第K个位置的结点的值.
30.编写递归算法,计算二叉树中叶子结点的数目.
30.编写递归算法,将二叉树中所有结点的左,右子树相互交换.
32.编写递归算法:
求二叉树中以元素值为X的结点为根的子树的深度;
33.编写递归算法:
对于二叉树中每一个元素值为X的结点,删去以它为根的子树,并释放相应的空间.
34.编写复制一棵二叉树的非递归算法.
35.编写按层次顺序（同一层从左至右）遍历二叉树的算法.
36.在二叉树中,*root为根结点,*p和*q为二叉树中两个结点,试编写求距离它最近的共同祖先的算法.
41.试编写算法,求给定二叉树上从根到叶子结点的一条其路径长度等于树的深度减一的路径（即列出从根结点到该叶子结点的结点序列）,若这样的路径存在多条,则输出路径终点
（叶子结点）在"最左"的一条.
42.已知一棵完全二叉树存于顺序表sa中,sa.elem[sa.last]中存放各结点的数据元素.
试编写算法由此顺序存储结构建立该二叉树的二叉链表.
43.为二叉链表的结点增加DescNum域.试编写一算法,求二叉树的每个结点的子孙数目并且存入其DescNum域，请给出算法的时间复杂度。
44.试写一算法,在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继（假设二叉树的根结点未知）.并讨论实现此算法对存储结构有何要求?
45.试写一算法,在后序后继线素二叉树中，查找给定结点*p在后序序列中的后继（二叉树的根结点指针并没给出）。
并讨论实现算法对存储结构有什么要求？
四：
算法设计题
1．社设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将元素S插入到线性表的适当位置，以保持线性表的有序性，并且给出算法的时间复杂度。
2．针对下面的问题，设计算法，要求算法的时间复杂度均为O（n）。
（1）已知数组A[n]的元素类型为整型,设计算法调整A,使其左边的所有元素小于零,右边的元素大于零。
（2）设计算法，将一个带头结点的单链表A分解为两个具有相同结构的单链表B和C，其中B链表的结点为A链表中值小于零的结点，而C链表的结点为A链表中值大于等于零的结点（假设单链表
升级会员 