数据结构试题集(包含答案-).doc

第一章概论一、选择题1、研究数据结构就就是研究（ )。A、数据得逻辑结构 B、 数据得存储结构 C、 数据得逻辑结构与存储结构 D、 数据得逻辑结构、存储结构及其基本操作2、算法分析得两个主要方面就是( ）.A、 空间复杂度与时间复杂度B、 正确性与简单性C、可读性与文档性 、 数据复杂性与程序复杂性、具有线性结构得数据结构就是（ D)。A、图 B、 树C、 广义表 、 栈4、计算机中得算法指得就是解决某一个问题得有限运算序列，它必须具备输入、输出、（ B )等5个特性.A、 可执行性、可移植性与可扩充性B、 可执行性、有穷性与确定性C、 确定性、有穷性与稳定性 D、 易读性、稳定性与确定性5、下面程序段得时间复杂度就是( C）。for（i=0;im;i+）for(j0;jn;）ai=ij；、 O（2） B、 （n2）、 （mn）、 O（mn）、算法就是( D ）。A、计算机程序 B、解决问题得计算方法C、 排序算法 、 解决问题得有限运算序列7、某算法得语句执行频度为（n+lo2n+n2+8）,其时间复杂度表示（ C ）。A、 O(n） 、 O（log2n) C、 O（n2) 、 O（2)8、下面程序段得时间复杂度为( C )。i=；hile（i=n）i=；A、 (n）B、 O（3n)C、O(g3n） 、 O（3）、数据结构就是一门研究非数值计算得程序设计问题中计算机得数据元素以及它们之间得（ )与运算等得学科。A、结构、 关系C、 运算D、 算法10、下面程序段得时间复杂度就是（A ).is=；whil（)+;s+=；A、O(n) B、 （2）、 O(log2n） D、 O（n3）11、抽象数据类型得三个组成部分分别为( A)。、 数据对象、数据关系与基本操作 B、 数据元素、逻辑结构与存储结构C、 数据项、数据元素与数据类型、 数据元素、数据结构与数据类型1、通常从正确性、易读性、健壮性、高效性等4个方面评价算法得质量，以下解释错误得就是（ ）.A、 正确性算法应能正确地实现预定得功能、 易读性算法应易于阅读与理解,以便调试、修改与扩充、 健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要得运行结果D、 高效性即达到所需要得时间性能13、下列程序段得时间复杂度为（ ）。x=；y0；while(=（y1)（+）)=y+；A、 O(n) B、 C、O（) D、 (n2)二、填空题、程序段“i；wile(inet=head B、pnext=ULL C、 p=NLL D、 p=head6、链表不具有得特点就是( ).A、 可随机访问任一元素 B、 插入删除不需要移动元素C、 不必事先估计存储空间、 所需空间与线性表长度成正比7、在双向循环链表中，在指针所指得结点后插入一个指针q所指向得新结点，修改指针得操作就是（ ）。A、 pet=q；qprior=;pnext-pio=q；q-nx=q;B、 pne=q；p-net-iorq；qriorp；q-nextp-xt；C、 q-prior=p;ext=p-nxt;p-ex-pro=q;pnext=q；D、 qnext=pnet；q-prior=p；p-n=；pextq；8、线性表采用链式存储时,结点得存储地址（ )。A、 必须就是连续得B、 必须就是不连续得C、 连续与否均可 D、 与头结点得存储地址相连续9、在一个长度为n得顺序表中删除第个元素，需要向前移动（ )个元素。A、 n-i B、 n+1C、n-i 、 i+11、线性表就是个（ ）得有限序列。A、表元素B、 字符C、 数据元素D、数据项11、从表中任一结点出发,都能扫描整个表得就是（ )。A、单链表 B、 顺序表、 循环链表 D、 静态链表12、在具有n个结点得单链表上查找值为x得元素时，其时间复杂度为( )。A、 O（n) B、 O（1) C、O(n2） D、O(）13、线性表L=（a1,a2，a)，下列说法正确得就是（ ）.、 每个元素都有一个直接前驱与一个直接后继 B、 线性表中至少要有一个元素C、表中诸元素得排列顺序必须就是由小到大或由大到小、 除第一个与最后一个元素外，其余每个元素都由一个且仅有一个直接前驱与直接后继14、一个顺序表得第一个元素得存储地址就是0，每个元素得长度为,则第个元素得存储地址就是( ）。、 8 、 0C、02 、10615、在线性表得下列存储结构中，读取元素花费得时间最少得就是( ）. A、 单链表 B、 双链表 C、 循环链表 D、 顺序表6、在一个单链表中,若删除所指向结点得后续结点，则执行（ ).、pnext=nexnext；、ppnext；p-nxt=p-next-xt；、p =pex;D、ppnextnex;1、将长度为n得单链表连接在长度为m得单链表之后得算法得时间复杂度为( )。A、（)B、（）C、（m)、 O（mn）、线性表得顺序存储结构就是一种（ )存储结构。、随机存取B、顺序存取C、 索引存取D、散列存取19、顺序表中,插入一个元素所需移动得元素平均数就是( )。 A、（n1）/2 、n C、 + D、 (+1）/210、循环链表得主要优点就是（ ）。A、不再需要头指针 B、已知某结点位置后能容易找到其直接前驱、在进行插入、删除运算时能保证链表不断开 D、在表中任一结点出发都能扫描整个链表11、不带头结点得单链表hea为空得判定条件就是( A ）。A、 had=NULL 、 headne=NULL C、 hedext=hea D、d！=NLL答案B就是带头结点得12、在下列对顺序表进行得操作中,算法时间复杂度为O(1)得就是（ )。、 访问第i个元素得前驱（1）、在第i个元素之后插入一个新元素（）、 删除第i个元素（）D、 对顺序表中元素进行排序答案就是、假设顺序表L，长度为n,求第i个节点Li,直接前驱Li1，因此为O（1）答案需要移动n-1个节点，因此为O（n）答案C也需要移动n-个节点答案D根据排序方法不同最慢O()，最快（log)1、已知指针p与q分别指向某单链表中第一个结点与最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行得语句为( )。A、 nxt=sext；s-nxt=； B、 s-nex=p；q-nexts-ext; C、 p-ex=-xt；set; D、 snxt=q;net=nxt;14、在以下得叙述中,正确得就是（ ).A、线性表得顺序存储结构优于链表存储结构 B、线性表得顺序存储结构适用于频繁插入删除数据元素得情况C、 线性表得链表存储结构适用于频繁插入删除数据元素得情况D、 线性表得链表存储结构优于顺序存储结构15、在表长为n得顺序表中，当在任何位置删除一个元素得概率相同时，删除一个元素所需移动得平均个数为（ )。A、 (n1）/2 B、n/ C、 (n+1）/2D、 6、在一个单链表中,已知q所指结点就是p所指结点得前驱结点,若在与p之间插入一个结点s，则执行（ )。A、 snxt=p-nx; -next=s； B、 -next=s-t;s-ext=； C、qnt=;snxt=p； D、 pext=；sex=q;1、在单链表中,指针p指向元素为得结点，实现删除x得后继得语句就是（ ）。A、 p=p-nxt; B、pnext=pext-nxt; C、pnx=p;、 p=pnexnext；1、在头指针为head且表长大于得单循环链表中，指针p指向表中某个结点，若p-exteead，则( ）.A、 p指向头结点 、 p指向尾结点C、 p得直接后继就是头结点、 得直接后继就是尾结点二、填空题1、设单链表得结点结构为（t，next）。已知指针p指向单链表中得结点，q指向新结点，欲将q插入到p结点之后，则需要执行得语句： ； 。答案:-next=xt p-nt=q2、线性表得逻辑结构就是 ,其所含元素得个数称为线性表得 .答案：线性结构 长度3、写出带头结点得双向循环链表L为空表得条件 。答案：Lpro=Lnet=L4、带头结点得单链表ead为空得条件就是 。答案:ha-nexNULL5、在一个单链表中删除p所指结点得后继结点时，应执行以下操作： = -next；-nex= q-net _;三、判断题、单链表不就是一种随机存储结构。 P2、在具有头结点得单链表中，头指针指向链表得第一个数据结点。O3、用循环单链表表示得链队列中,可以不设队头指针，仅在队尾设置队尾指针。P4、顺序存储方式只能用于存储线性结构。O、在线性表得顺序存储结构中，逻辑上相邻得两个元素但就是在物理位置上不一定就是相邻得.O6、链式存储得线性表可以随机存取.X四、程序分析填空题1、函数etem实现返回单链表得第个元素，请在空格处将算法补充完整.in GetElem(nListL，n i,Elemtyp *）LinList p；int j;p=Ln；j=1；wh(p&jdaa、函数实现单链表得插入算法，请在空格处将算法补充完整.int LstInert（LinkList L，ini，ElemType e) LNde，s;it j; pL；j=;whle（(p！=NU）&（i-） eturn EROR; s(Le）alc（sieo(LNode)）； daae； () ; (） ; rern O;/LstInsert答案:（1）sext=pnext (2）p-x=s3、函数Litelet_sq实现顺序表删除算法，请在空格处将算法补充完整。ntLitDelt_sq(Slt *L,int i) int k; if(i1|iL-length) etrRROR；or(i-1；Lgth 、函数实现单链表得删除算法,请在空格处将算法补充完整。intLitDelte(inkListL，int i，EemType *s) LNde p，q; intj； p=L;=0； he（ (1) ）&(j-1) pext;+； if（p-net=NULLji-1）reuO； q=pext； (2） ; *s=q-dta; ree(q）; retrn OK;/lstDlte*答案:(1）pnext！=L （)p-nex=qnt5、写出算法得功能。nt L（head）ode * head；it n=；odp；p=h；ile(p!=NULL） p-next； n+; rtn（n)；答案：求单链表ha得长度五、综合题、编写算法,实现带头结点单链表得逆置算法。答案:vodnent（nod *hea） Loe *p，q； if（!head-et） rtrRRR； headnext；q=pnext； pext =NU； whie（q） =q; qext； p-nt=head-nxt; headnextp; 2、有两个循环链表,链头指针分别为L1与2，要求写出算法将L2链表链到L1链表之后,且连接后仍保持循环链表形式。答案：void erge(Lnod *L1, Lode*) node *p，* ; le(p-nxt！=L1）p=pne;whil(next!=L2)q=q-nxt;q-next=L1； pnet =L2; 、设一个带头结点得单向链表得头指针为head，设计算法，将链表得记录,按照data域得值递增排序。答案：voidasending（Lnod *head) Lod *p, ，*r, s； p=hed-next;q=pnet； p-nxUL; wile(q）r=；q=qnet;f（rdatdata) r-nextp；head-nx=; r； elsewhi(!p rdaapdat）=p; p=p-xt； ext=p； next=;p=head-net； 、编写算法，将一个头指针为ead不带头结点得单链表改造为一个单向循环链表,并分析算法得时间复杂度。答案：vod inlis_c（Lnode head） Lnoe ； p=head； f(！p） return ERO;hil（next！=NLL)p=pnt;-nexhed； 设单链表得长度（数据结点数)为N，则该算法得时间主要花费在查找链表最后一个结点上（算法中得while循环）,所以该算法得时间复杂度为O（N）。5、已知head为带头结点得单循环链表得头指针，链表中得数据元素依次为（a1,a，a3，a4，),A为指向空得顺序表得指针。阅读以下程序段，并回答问题:（）写出执行下列程序段后得顺序表A中得数据元素;（）简要叙述该程序段得功能。if（ed-next!head）p=had-nex;A-lngt=0；whi（p-nex!=head）pnx；dtlength+=p-data；i(pnex！head)p=-nex；答案： (） （2， a4, ， ) (）将循环单链表中偶数结点位置得元素值写入顺序表、设顺序表va中得数据元数递增有序.试写一算法,将x插入到顺序表得适当位置上，以保持该表得有序性。答案:vo Isert_sq(Sqlistva, lTp x） in , j, n； =length(va）; if（xvi)anx;eli;while（xi） i+；fo(n1；jI；j-）vaj=a;vai=x; n+; 、假设线性表采用顺序存储结构,表中元素值为整型。阅读算法f，设顺序表L=(3，7，3,2，1,8，7，3)，写出执行算法后得线性表L得数据元素,并描述该算法得功能。 voi f2（Seqist *L) int ，k;or(=0；ilength；i+） for（=; Ldai!=Ldataj；j+）； if（j=） i(!=i)Ldatak=Ldaa; k+； L-lnth=；答案： (，,2,1,8) 删除顺序表中重复得元素8、已知线性表中得元素以值递增有序排列，并以单链表作存储结构。试写一算法,删除表中所有大于x且小于y得元素（若表中存在这样得元素）同时释放被删除结点空间。答案：oid eeteis(Lnde head， EmTpe x, emType y） Lnoe , *q; f（！had)reunERO；p=hea； q=；whie（！p)if(p-dtx) & (p-dta)i+；if（p=head)head=pnet; fre(p)；p=head；q=； ese-net=p-next； fre(p)；p=qnxt； eleqp; ppxt; 9、在带头结点得循环链表L中,结点得数据元素为整型，且按值递增有序存放。给定两个整数a与b,且ab，编写算法删除链表L中元素值大于且小于b得所有结点。第三章栈与队列一、选择题1、一个栈得输入序列为：a，b,，d,e，则栈得不可能输出得序列就是( ）。、 a,b，c，d,e B、d,，c，b，a C、 d，c，e,， D、 e,d，c，b,a、判断一个循环队列Q(最多n个元素）为满得条件就是（ ）。、 Qrea=Q-ron B、 rea=frnt+ C、frnt=(rear+）%nD、 -ront=（Q-re1)n3、设计一个判别表达式中括号就是否配对得算法,采用( ）数据结构最佳.A、 顺序表 、 链表 C、 队列 、栈4、带头结点得单链表head为空得判定条件就是( ）。A、head=NUL B、 hea-=ULC、 hedext!=NUL D、head!=NULL5、一个栈得输入序列为:，2,，4,则栈得不可能输出得序列就是（ ）。、 1243 B、 2134 C、 2 、 4312E、 32、若用一个大小为6得数组来实现循环队列,且当rear与fon得值分别为,3。当从队列中删除一个元素,再加入两个元素后，rer与fnt得值分别为( ）。A、1与 B、 与4C、 4与2D、 5与7、队列得插入操作就是在( ).A、 队尾 B、 队头、 队列任意位置D、 队头元素后8、循环队列得队头与队尾指针分别为front与e，则判断循环队列为空得条件就是( ).、 fot=rea B、 front= C、 ea= D、 font=rear+19、一个顺序栈,其栈顶指针为top，则将元素e入栈得操作就是（ ）。A、 -top=;So+； B、Stop+;*-to；C、 S-op=e D、 Stop=e；10、表达式a（b+c）得后缀表达式就是( ）。A、 abd B、a+d-C、 ac+d 、+bcd1、将递归算法转换成对应得非递归算法时，通常需要使用( )来保存中间结果。A、 队列 、栈C、 链表 D、 树2、栈得插入与删除操作在（ ）。 A、 栈底 、 栈顶 C、 任意位置 D、 指定位置、五节车厢以编号1，,3,，顺序进入铁路调度站（栈），可以得到( ）得编组.A、3，4,，2B、 2,4,1，3，5C、,5，4，,1、 1，,2，41、判定一个顺序栈S（栈空间大小为）为空得条件就是( ）。A、 Stop= B、 Sop！=0、Stp=nD、 S-top!=n5、在一个链队列中，frnt与rer分别为头指针与尾指针,则插入一个结点s得操作为( )。、 frontfrontnextB、 snextrear；rear=sC、 er-nxt=s；rear=s；D、 nxt=ont；frot=s;1、一个队列得入队序列就是1，2，3，4，则队列得出队序列就是(）。A、 1，2，B、 4，3,2，C、 1，4，3，D、,4，217、依次在初始为空得队列中插入元素a，b,c，d以后，紧接着做了两次删除操作,此时得队头元素就是( ）。A、 a 、 b 、 、 18、正常情况下，删除非空得顺序存储结构得堆栈得栈顶元素，栈顶指针t得变化就是( ）。、 tp不变 、op= C、tptp+1 D、op=op9、判断一个循环队列Q(空间大小为M)为空得条件就是（ )。A、 Q-fro=Qra B、 QreQ-front1M C、 frnt1=Qear D、 Q-rea+1=Q-front2、设计一个判别表达式中左右括号就是否配对出现得算法,采用( )数据结构最佳。、线性表得顺序存储结构B、 队列C、栈 D、 线性表得链式存储结构2、当用大小为N得数组存储顺序循环队列时，该队列得最大长度为（ ）.、 N B、 N+1C、 -1D、 N222、队列得删除操作就是在（ ）.A、 队首、 队尾C、 队前、队后23、若让元素1，2，3依次进栈，则出栈次序不可能就是（ ).、,2,B、 2,1，3C、 3,1，2 D、 1,，24、循环队列用数组A0，m1存放其元素值,已知其头尾指针分别就是frnt与rr,则当前队列中得元素个数就是（ ）。A、 （rear-frt+m）%m、 rearfrn+、 rear-fronD、 earfron、在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区，主机将要输出得数据依次写入该缓冲区,而打印机则从该缓冲区中取走数据打印。该缓冲区应该就是一个( ）结构。A、 堆栈 B、 队列C、 数组 D、线性表26、栈与队列都就是（ )。A、 链式存储得线性结构 B、 链式存储得非线性结构 、 限制存取点得线性结构 D、 限制存取点得非线性结构27、在一个链队列中,假定frot与er分别为队头指针与队尾指针，删除一个结点得操作就是( )。A、 fo=ront-ext B、 ear rea-etC、reanxt=fontD、 frnt-nxt=rear28、队与栈得主要区别就是（ ）。A、逻辑结构不同 B、存储结构不同、 所包含得运算个数不同 D、 限定插入与删除得位置不同二、填空题1、设栈S与队列Q得初始状态为空，元素e1,e2，e,e4，e5，e依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队得序列就是e2，e4,e3,e6，e，e1,则栈得容量至少应该就是 .答案:32、一个循环队列得存储空间大小为M,其队头与队尾指针分别为front与rer,则循环队列中元素得个数为： 。答案:(rear-font+M）%M3、在具有n个元素得循环队列中，队满时具有 个元素.答案:n、设循环队列得容量为7,现经过一系列得入队与出队操作后，fon为2,rar为1，则队列中元素得个数为 。答案:615、已知循环队列得存储空间大小为2，且当前队列得头指针与尾指针得值分别为8与,且该队列得当前得长度为_。三、判断题1、栈与队列都就是受限得线性结构。P2、在单链表中,要访问某个结点，只要知道该结点得地址即可；因此,单链表就是一种随机存取结构.O3、以链表作为栈得存储结构,出栈操作必须判别栈空得情况。P四、程序分析填空题1、已知栈得基本操作函数：it Inittac(SqSack *S); /构造空栈ittacEmpty(SqtkS)；/判断栈空nt Pus(SqStac S，EemTpee）;/入栈int Pop（SqStak*,EemTyp e)；/出栈函数onvrsion实现十进制数转换为八进制数，请将函数补充完整。void conversio(）IitStack（S)；cnf(“d”，&N）;wie(） （1) ；N=N/8;while( (2） ）Pop(S,&e);rntf（“%”,);cnrsion答案：(1)Puh(S，N%） (2)！Stackmpy（）2、写出算法得功能。int funton（Squeu Q,ElemTypee)i（Q-fro=-rea）returEROR;*e=Q-bsQront;frnt=（-front1）%MAXSIE;returOK;、阅读算法f2,并回答下列问题：（)设队列Q（1,3，5，2，4，6)。写出执行算法f2后得队列；（2)简述算法f2得功能。vo f2(ueue Q) DaTy e； if(！QuuEmpty(Q） eDeQueu(Q）; f2(Q）； Enueu(Q,e）； 答案：(）6，4，5，3,1（2）将队列倒置五、综合题1、假设以带头结点得循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针,请写出相应得入队列算法(用函数实现)。答案:void Queue(Le r， mTyee) node new; New=（Lnde)alc(sizef(ode);If（!new） retur ERR；newdata=e； new-net=rearn； rarne=ne； rear=; 2、已知Q就是一个非空队列,S就是一个空栈。编写算法，仅用队列与栈得AD函数与少量工作变量，将队列Q得所有元素逆置。栈得ADT函数有：void makeEmpty（qStak ）；置空栈vodpus(SqStck s,ElemTpe e）;元素e入栈lType pp（SqStack s）;出栈，返回栈顶元素itisEm（SqStcks）;判断栈空队列得AD函数有:vid enQeue（uue q,ElemTyp e)；元素e入队EleTyeee(Queue q);出队，返回队头元素it sEty(Queue ）；判断队空答案:void ueuInvent(Queu q） Elemy x； maeEpty（Stack ）；whle（!sEmpt（Quee ）)=eueue（Queu q)；ush(SqStcks，EleTpex）；hil(！sEmp（Stk ）)x=o（SqSta s）； enueue（Que，ElemTyp x）; 3、对于一个栈,给出输入项A,B,C，如果输入项序列为A,B，C，D,试给出全部可能得输出序列。答案:出栈得可能序列: BCD BD ACB AB ADCB AC BAC BCA BDACBDA CBAD DBA D第四章 串一、选择题1、设有两个串S1与S2，求串S2在S1中首次出现位置得运算称作( C ).、 连接