数据结构2习题线性表它是一种最简单的可以在任意位置进行和删除

≥0)a0,a1,an-1前趋和一个直接后继。→可表示为（a1,a2 ,……,an）一、选 （n>0表元 二、判三、填15．线性结构包括_线性表、栈 和串。线性表的结构分成_顺序结构和链式存讨论1：顺序和链式的区别和优缺点链式时，相邻数据元素可随意存放，但所占空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式的优点是插入或删除元素时很方便，使用灵活。缺点是密度小，一、选下述哪一条是顺序结构的优点？（AA．密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的表 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）顺序 链表不具有的特点是（ 插入、删除不需要移动元素B．可随机任一元C．不必事先估计空间D．所需空间与线性长度成正下面的叙述不正确的是（BC 时，查找第i个元素的时间同i的值成正 时，查找第i个元素的时间同i的值成正 时，查找第i个元素的时间同i的值无二、判顺 结构的主要缺点是不利于插入或删除操作。(√顺 方式插入和删除时效率太低，因此它不如链式方式好。(×解释：两 结构实现。(×线性表就是顺序的表。(× 密度大，且插入、删除运算效率高。(链表是采用链 (√ii三、填时，应采用顺

结构中每一个结点包含的指针个数将线性链表分成_单链表和_多重链表的特点是利用指 结构是通过物理上相邻 间的关系的;链式结构是通过指针 五、应n动地改变。在此情况下，应选用哪种结构？为什么？O（1O（1线性表的顺序结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难表的链式结构是否一定都能够克服上述三个弱点，试讨论之。.顺序映射时，ai与ai+1的物理位置相邻；链表表示时ai与ai+1的物理位置不要求相邻x2.^bapba

头指 头结^^pXa bXabp-Step1：q->next=p-Step2：p->next=q一、选

插入

s-headp（A B．p－＞next D．p=HP（A B．P－＞NEXT= hpA. B.p－＞next=NULLC.p－＞next. D.p－＞data=-ps（BA．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p-对于一个头指针为head的结点的单链表，判定该表为空表的条件是（Bhead==NULL 二、判1.×三、填在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动

n- 在单链表中设置头结点的作用是主要是使插入和删除等操作统一，在第一个元前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。循环单链表的最大优点是：从任一结点出发都可到链表中每一个元素ps_s->next=p->next;p->next=s设单链表的结点结构为(data,next)，nextpxdata为xpydatayyxpy->next=px->next;px-10.对于单链表链表,在两个结点之间插入一个新结点需修改的指针共 五、应next，pCq=p->next;p->next=q->next;p（p）data，next，pshead,pre=head；while(pre->next!=p)pre=pre->next;s->next=p;pre-五应用题(51 …^头指 头结 首元结头指针是指向链表中第一个结点（结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域学 分数—选择题(27对于栈操作数据的原则是（BA.先进先 B.后进先 C.后进后 D.不分顺在作进栈运算时,应先判别栈是否(B①),在作退栈运算时应先判别栈是否(A② 当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ①,②:A. B. C.上 D.下③:A.n- B. C. 是（BA.不确 B.n- D.n-1,2,3,…,n，i，j（DA.i-j- B.i- C.j- D.1,2,3,…,np1,p2,p3，…，pNpN是n是 D)A. B.n- C.n- D.6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（CA.54361 B.45312 C.34652 D.234151，2，3，4,则（D）A. B. C.D. E.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（ A.2341 B.5413 C.2314 D.1543设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（DA.5123 B.4513 C.4312 D.3215bcd,A. B.b, C.c,d，b, D.d,abcdef D B. C. D.设有三个元素XYZ顺序进（进的过程中允许出栈下列得不到的出栈排列是(C B.YZX C.ZXY D.ZYX输入序列为ABC，可以变为CBA时，经过的栈操作为（ B.C. D.栈在（ ）中应用A.递归调 B.子程序调 C.表达式求 D.A[m]frontrear，则当前队列中的元素个数为（A 中的元素数是(AA.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-循环队列在数组A[0..m]中，则入队时的操作为（DA. B.rear=(rear+1)mod(m-C.rear=(rear+1)modmD.若用一个大小为6的数组来实现循环队列，且当前rearfront的值分别为03，当从队列中删除一个元素，再加入两个元素后，rearfront？(B)A.1和5B.2和 C.4和2D.5和栈和队列的共同点是（C都是先进先 B.都是先进后C.只允许在端点处插入和删除元素D.栈的特点是（B①）,队列的特点是（A②）,栈和队列都是（C③。若进栈1,2,3,4（C④）不可能是一个出栈序列（不一定全部进栈后再出栈1,2,3,4则（⑤F）是一个出队列序列。①,②:A.先进先出B.后进先出C.进优于出D.③:A.顺序的线性结构B.链式的线性结C.限制存取点的线性结构D.④,⑤:A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1F.G.栈和队都是（C顺序的线性结构B.链式的非线性结C.限制存取点的线性结构D.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是(C)。 B. C. D.A．{d B.C. D.二判断题（√（√若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. （ （×（√循环队列通常用指针来实现队列的头尾相接。（ 循环队列也存在空间溢出问题 栈和队列都是线性表，只是在插入和删除时受到了一些限制 栈和队列的方式，既可以是顺序方式，又可以是链式方式 三填空题(15栈是操作受限（或限定仅在表尾进行插入和删除操作） 的线性表，其运算遵循后 栈一个栈的输入序列是：1，2，3312，经过之后，输出序列 23序，相应的S和X的操作串为 S×SS×S××_。顺序栈用 数据，栈顶指针是top,则值为x的元素入栈的操作是data[top++]=x循环队列的引入，目的是为了克服_假溢出时大量移动数据元素0开始的NM1围内循环，可采用的表达式是：M=_(M+1)%N队列队列的特点是_先进先出_先进_。A[0..m-1]frontrear，则当前队列的元素个数是_（rear-front+m）%m。设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数 （R-P+N）%N_。四应用题（45）叫栈底。最后插入的元素最先删除，故栈也称后进先出（F）表。一端叫队头。最先插入队的元素最先离开（删除，故队列也常称先进先出（FF）表。用常规意义下顺序结构的一维数组表示队列，由于队列的性质（队入和队头删除个数小于队列的长（容量循环队列是解“假溢出的法通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个单元”或“作标记”的方法解决“满”和“队空”的判定问题。123456,试问能否通过栈结构得到以下两个序列:43561235426;输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩122不可能栈底元素1在栈顶元素2之前出得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出最后6栈并退栈，得最终结果135426。D、B、A、C、E？能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为：若出栈序列以D开头，说明在D之前的入栈元素是A、BC，三个元素中C是栈顶元素，BA可能早于C栈，故不可能得到D、B、A、C、E栈序列。a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出借助栈结构，n个入栈元素可得到1/(n+1)((2n！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，设一数列的输入顺序为123456，若采用堆栈结构并以A和D分别表示入栈和出栈操作，325641154623能得到。在依次进栈后，32栈，得部分输出32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。不能得到输出顺序为154623序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623简述顺序队列的假溢出的避免方法及队列满和空的条件设顺序队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质“删除”在队头而“插入”在队尾所以当队尾指针rear等于m-1front不等-1，则队列中仍有空闲单元所以队列并不是真满这时若再有入队操作造成其解决办法有二，一是将队列元素向前“平移（占用0rear-front-1；二是将队1在循环队列中，空队特征是front=rear；队满时也会有front=rear；条件将出现二义判队满：count>0&&rear==front判队空②加设标志位，出队时置０,入队时置１,则可识别当前front=rear属于何种情况判队满：tag==1&&rear==front判队空：tag==0&&③少用一个单判队满判队空typedef{DataTypeint /*队尾指针intfront; intcount; } 初始状Q.rear=0; Q.front=0; Q.count=0; Q->count==Q->count>0&&Q->rear==Q-第六 树和二叉知识点1树的基本概4.T41，2，344，2，1，1T （1≤i≤m（1）(4)A.有0个或1个B.有0个或多个C.有且只有一 D.有1个或1个以A.互不相 C.允许叶结点相交D.允许树枝结点相A. B.维 C.次 D.7．321，32，431224．如果结点A有3个兄弟，而且B是A的双亲，则B的度是 32．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为 21。知识点2二叉树的基本概念和性5.（.D0;②二叉树的度为2； 10（.B）2 12．1001（E）A． B 有关二叉树下列说法正确的是（B I（C B．2I-1- C．2I- D．2I-1025h（C 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(B)结点 n（D n（深度）是（A 深度为h的满m叉树的第k层有（A）个结点。(1=<k=<h) k（C K（C C．2k- K（C）2k B.2k-1 C.2k- D. 46．在下列情况中，可称为二叉树的是（B） B. D.每个结点只有一棵右子 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（B正确B．nA[l..n]中时，i（D） B.A[2i+1](2i+1=< 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序在一维数组A[1..n]中，则二i（i1）A（D）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i- 28.（2（a）1+1（k≥1） ）二叉树由_(1)，(2)_，_(3)三个基本单元组成。(1)根结点(2)左子树(3 p->lchild==null&&p->rchlid==null6．2569深度为k的完全二叉树至少有 个结点，至多有 个结点。.(1)2k-1(2)2k-H的完全二叉树至少有_(1)个结点；至多有_(2)个结点；HN2(3)。(1)2H- (2)2H-1(3)H=log2n(1)_1(2)_（）结点和(3)_个叶子，该满二叉树的深度为_(4)。(1)0(2)(n-1)/2(3)(n+1)/2(4)log2n+1假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是.n在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=_N2+1 设只含根结点的二叉树的高度为0则高度为k的二叉树的最大结点数 (1)2K+1-1(2) 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 20011123．203069有最大高度。(1)完全二叉树(2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左或只有右。 30．8层完全二叉树至少有 个结点拥有100个结点的完全二叉树的最大层数为 七层满，加第八层１个)(2)731．含4个度为2的结点和5个叶子结点的二叉树，可有 个度为1的结点。0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个数才至多为1。48．n(n+1)/2_2，树无此限制；二是二叉树有左右子树之分，即使nn2n-1(nlog2nn2n-1，而完全二叉树11，nn+(n-1)+1=2n2n-1（有12n(2n-1)个结点的完全二叉树的深度是log2(2n)+1(log2(2n-1)+1，即log2n+1,nlog2n+1（最下层结点数>=2知识点3二叉树的遍左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(C)次序的遍历实现编号。A．先 B.中 C.后 D.从根开始按层次遍 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：B 37．：EFHIGJKHFIEJKGA、 B、 C、 D、39.某二Tn个结点，设按某种顺序对T每个结点进行编号1，2，…，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V1。这时是按(B)编号的。A.B.C.后序遍历序列40．下面的说法中正确的是（B）. 对于前序遍历和后序遍历结果相同的二叉树为（B2 D．根结点无右孩子的二叉树E．F．所有结点只有右子树的二叉树A．BC．D．是任意一棵二叉树43．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（B） A,B,C,D,E,F,GB,D,C,A,F,G,E,则该二叉树结点的前序序列为_(1)。(1)EACBDGF abdecfhgdbeahfcg，则该二叉树的根为_(1)，左子树中有_(2)，右子树中有_(3)。(1)a(2)dbe(3)hfcg 。 知识点4 设给定权值总数有n个，其树的结点总数为(D)A．不确 有n个叶子的树的结点总数为（D不确 一 52．树 _(2)6:a,b,c,d,e,f2,3,4,7,8,9，曼树，则 路径长度WPL为_(1)，字符c的编码是_(2) 个结点 54.(1)655.(1)802)001（不唯一）56.2n0-应（12）80.30，0.07，0.10，WPL补充知21．若一棵树中有度数为1至m的各种结点数为n1,n2,…,nm(nm表示度数为m的结点个数)请推导出该n0的公式。21.设树的结点数为n，b， b= 由(1)、(2)和（3）得叶子结点数n0=1+图知识点1图的基本概A．n- C． 5．n（D 在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。 11．下列哪一种图的邻接矩阵是对称矩阵？（B）有向

0A1

111.（√nnee（×VV1（× 单元数目与图的边数有关（×

。有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元和的一半（√式来它（×）（√）1045若用n表示图中顶点数目，则有_n(n- 设无向图G有n个顶点和e条边，每个顶点Vi的度为di（1<=i<=n，则 n 2(n-1)。

在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度；对于有向图来说等于该顶点的出度 I_I知识点2图的遍下列说法不正确的是（C （D 5（Daebdf acfde aedfc aefdc aefdbA．5 B．4 C．3 abecdf第17abecdf71C①)，C② G=（V，Eaabecd，则采用的是_深度优先遍历方法。24.为了实现图的广度优先搜索，除了一个标志数组标志已的图的结点外，还需_队列存放被（1）12345 12345 8915题 （1）V1V2V4V3V5V6 查ASL为(C)。(n- B. C. D.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A)A（N+1）/2 B.N/2 C.N D.[（1+N）*N]/2( D( ，也可以链表方式C.表必须有序，而且只能从小到大列 对线性表进行二分查找时，要求线性表必须（BA.以顺序方式B.以顺序方式,且数据元素有序C.以方式D.以方式,且数适用于折半查找的表的方式及元素排列要求为(DA．方 C．顺序方 ，元素有)必然 B.必然 C.相 D.不能确查找速度(C)必定 C.在大部分情况下要 D.取决于表递增还是递 A. B. C. D.当采用分快查找时，数据的组织方式为(B)C（1）(C（2）)(1):ABC.D.(2):ABC.D.（C1（D2找的平均比较次数为（G3；折半查找的平均比较次数为（4H（1（2：A.必须以顺序方式；B.必须以链式方式；C.既可以以顺序方式，也可以链式方式；D.必须以顺序方式，且数据已按递增或递减顺序排好；