《数据结构(第二版)习题》由会员分享，可在线阅读，更多相关《数据结构(第二版)习题（18页珍藏版）》请在金锄头文库上搜索。
1、第一章绪论一、问答题1.什么是数据构造?2.论述四类基本数据构造的名称与含义。3.论述算法的定义与特性。论述算法的时间复杂度。5.论述数据类型的概念。6. 论述线性构造与非线性构造的差别。7论述面向对象程序设计语言的特点。.在面向对象程序设计中,类的作用是什么？ 论述参数传递的重要方式及特点。10.论述抽象数据类型的概念。二、判断题(在各题后填写“”或“”)1线性构造只能用顺序构造来寄存,非线性构造只能用非顺序构造来寄存。()2算法就是程序。(）3. 在高档语言(如C或PASCAL）中,指针类型是原子类型。()三、计算下列程序段中1的语句频度fo(=1;in;+)or(j1；jnexP-nt-
2、ext；（3)P-xt=Snext;(4）-net=P-et;（5)-ntL;(）S-nxt=ULL;(7)QP;（8)wl(-next!=Q)P-nx;（）while(P-next!=ULL）P=P-next；(10)PQ;()L;（1)L=S;(13)L=P；24已知线性表L递增有序。试写一算法,将X插入到L的合适位置上，以保持线性表的有序性。tusInet_qLi（qitv，int)/把x插入递增有序表va中f(.egth+1va.listsie)returnERR;va.enh+;or(=va.lngth;va.eleix&i0;i-)va.lemi+1=veli；va.elmi1x;
3、retunK;/InrtSqList2.5写一算法,从顺序表中删除自第i个元素开始的k个元素。2.6已知线性表中的元素（整数）以值递增有序排列,并以单链表作存储构造。试写一高效算法，删除表中所有不小于mink且不不小于maxk的元素(若表中存在这样的元素）,分析你的算法的时间复杂度（注意：mik和ax是给定的两个参变量,它们的值为任意的整数)2.试分别以不同的存储构造实现线性表的就地逆置算法,即在原表的存储空间将线性表（a,2.,an)逆置为(a，n-1,.,a1)。（1） 以顺序表作存储构造。（2） 以单链表作存储构造。28假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储构造,
4、请编写算法，将A表和B表归并成一种按元素值递减有序的排列的线性表C,并规定运用原表（即A表和B表的)结点空间寄存表.9假设有一种循环链表的长度不小于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。2.0已知有单链表表达的线性表中具有三类字符的数据元素(如字母字符、数字字符和其他字符），试编写算法来构造三个以循环链表表达的线性表,使每个表中只含同一类的字符,且运用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。.11设线性表A=(a,a2，,am），(b1,b2,，n)，试写一种按下列规则合并A、为线性表C的算法,使得:C
5、=(a1,b1,m,bm,m+1,，）当m时;或者C=（a1,b1，,an，n,an+1,a)当mn时。线性表A、B、C均以单链表作为存储构造，且C表运用表和表中的结点空间构成。注意：单链表的长度值和均未显式存储。.12将一种用循环链表表达的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项，并规定运用原链表中的结点空间来构成这两个链表。2.13建立一种带头结点的线性链表，用以寄存输入的二进制数，链表中每个结点的dat域寄存一种二进制位。并在此链表上实现对二进制数加1的运算。.14设多项式P(x)采用课本中所述链接措施存储。写一算法,对给定的x值,求P（x)的值。第三章栈和队列
6、.按图3.1（b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度,回答:如进站的车厢序列为123，则也许得到的出站车厢序列是什么?如进站的车厢序列为13456，能否得到435612和1546的出站序列,并阐明因素。(即写出以“S”表达进栈、以“”表达出栈的栈操作序列)。2.设队列中有A、B、C、E这5个元素,其中队首元素为A。如果对这个队列反复执行下列4步操作:(1)输出队首元素;（2)把队首元素值插入到队尾；（3）删除队首元素;(4）再次删除队首元素。直到队列成为空队列为止,则与否也许得到输出序列：(A）A、C、C、C（B）A、E()A、E、C、C、C(）A、C、E、C3. 给出栈的两种存储
7、构造形式名称，在这两种栈的存储构造中如何鉴别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算(）优先关系的惯例,画出对下列算术体现式求值时操作数栈和运算符栈的变化过程：AB*C/DE5.试写一种算法,判断依次读入的一种以为结束符的字母序列，与否为形如序列1&序列模式的字符序列。其中序列1和序列2中都不含字符，且序列2是序列的逆序列。例如,a+b&b+是属该模式的字符序列，而+3&3则不是。6. 假设体现式由单字母变量和双目四则运算算符构成。试写一种算法,将一种一般书写形 式(中缀）且书写对的的体现式转换为逆波兰式（后缀）。7.假设以带头结点的循环链表表达队列，并且只设一种指针指向队尾元素结点
8、（注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。8.规定循环队列不损失一种空间所有都能得到运用,设立一种标志域tag,以tag为0或1来辨别头尾指针相似时的队列状态的空与满,请编写与此构造相应的入队与出队算法。9. 简述如下算法的功能(其中栈和队列的元素类型均为in）:（1)odro_1(tackS）inti,n，A255;n=0;wile(!EmpyStack()n+;p(&,&n）;or(=1；=n;+)Push（&,Ai);（2） voidproc_(StkS,nte）StacT；td;InitStak(&）;ile(!EmptyStack(S）)Pop(&S,&d）;
9、(d!e）ush（&,);whie（!EmptyStack（T)Pp（&T,&d);Ph(S，d)； （3） vodpro_3(Qeue*Q)StackS；in；IiStack(&S)；hl（!EmyQue(*Q)eeteQeue(Q,&d)；Pus(&S，d);whi(!Emtytk(S)Pop(&S,）;EnerQeu（Q,d)第四章串.设s=MASTUDENT,OD,qWOKER。给出下列操作的成果:SLengt();SubSring(ub1，s,1,7);SbStrin(u2,7,)；SrIndex(s,A,4);tRepae(s,TDNT,q)；rCa(StrCat(sub1,),r
10、at(ub2,);2. 编写算法,实现串的基本操作SReplce(S,V)。3假设以块链构造表达串，块的大小为1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsig（S,chars);StCopy(,T);SrCmare（,T)；StrLegth（)；StrCat(S,T)；SubString（Sub，S,pos,len)。4.论述如下每对术语的区别:空串和空格串;串变量和串常量;主串和子串;串变量的名字和串变量的值。.已知:S”(yz）*”,T=”(+)*”。试运用联接、求子串和置换等操作,将S转换为.6S和T是用结点大小为1的单链表存储的两个串,设计一种算法将串中初次与T匹配的子串逆置。7.S是用结点大小为4的单链表存储的串，分别编写算法在第k个字符后插入串T，及
