数据结构复习题讲解

1、数据结构第一二章一填空1. 衡量算法效率的两个重要指标称为算法的时间复杂度_和空间复杂度。2. 一个算法应具有 有穷性，确定性，可行性，输入和输出这五个特性。3. 线性表的长度是指 表中元素的个数 。4. 在线性表的顺序存储中，元素之间的逻辑关系是通过元素存储的相对位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过相关元素的存储位置 决定的。5在双向链表中，每个结点包含两个指针域，一个指向其直接前趋结点，另一个指向其直接后继结点。二、判断题1. 线性表的逻辑顺序与存储顺序总是一致的。(FALSE)2 顺序存储的线性表可以按序号随机存取。(TRUE)3. 在线性表的顺序存储结构中，逻辑上

2、相邻的两个元素在物理位置上并不一定紧邻。(FALSE4在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(TRUE5. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(TRUE6线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(TRUE三、单选题(请从下列A, B, C, D选项中选择一项)1.线性表是(A)。(A) 一个有限序列，可以为空；(B) 个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 个无序序列，不能为空。2对顺序存储的线性表，设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动

3、表中的(A )个元素。(A) n/2(B)(n+1) /2(C) (n- 1)/2(D) n3线性表采用链式存储时，其地址 (D )。(A)必须是连续的；(B)部分地址必须是连续的；(C) 一定是不连续的；(D)连续与否均可以。4. 用链表表示线性表的优点是(C)。(A) 便于随机存取(B) 花费的存储空间较顺序存储少(C) 便于插入和删除(D) 数据元素的物理顺序与逻辑顺序相同5. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用(D)存储方式最节省运算时间。(A) 单链表(B) 双链表(C) 单循环链表(D) 带头结点的双循环链表6. 循环链表的主要优点是(D

4、 )。(A) 不再需要头指针了(B) 已知某个结点的位置后，能够容易找到他的直接前趋(C) 在进行插入、删除运算时，能更好的保证链表不断开(D) 从表中的任意结点出发都能扫描到整个链表7. 单链表中，增加一个头结点的目的是为了（A）使单链表至少有一个结点（B）（C）方便运算的实现（D）8. 若某线性表中最常用的操作是取第 储方式最节省运算时间（A）单链表 （B）四、简答题 1何时选用顺序表、 答：在实际应用中，C ）。标识表结点中首结点的位置 说明单链表是线性表的链式存储i个元素和找第i个元素的前趋元素，则采用（）存B ）。顺序表 （C）双链表 （D） 单循环链表何时选用链表作为线性表的存储结

5、构为宜？应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1. 基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约 存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态 链表作为存储结构为好。2. 基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。?具体的移动次数取决于哪两个因n/2个结点。删除一个

6、结点需平均n以及需插入或删除的位置i。i2在顺序表中插入和删除一个结点需平均移动多少个结点素？答：在等概率情况下，顺序表中插入一个结点需平均移动 移动（n-1）/2个结点。具体的移动次数取决于顺序表的长度 越接近n则所需移动的结点数越少。3为什么在单循环链表中设置尾指针比设置头指针更好？答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和 终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是 rear-next-next 和rear,查找时间都是 0（1）。若用头指针来表示该链表，则查找终端结点的时间为O（n）。typed

7、ef struct ElemType *elem; / intlen gth; /int listsize/五、分别设计算法，实现线性表的顺序存储结构和链式存储结构的原地置逆。 顺序存储结构的原地置逆存储空间基址线性表的实际长度；/当前分配的存储容量，（以 sizeof （ ElemType）为单位sqList;void reverse(SqList &A) /顺序表的就地逆置int i; int j;for(i=1,j=A.le ngth;ij;i+,j-)A. elemiA.elemj;/reverse链式存储结构的原地置逆。算法：结点值指针域，存储下一个结点的地址T ypedef str

8、uct LNode ElemType data;/struct LNode *n ext;/LNode,*Li nkList;void ReverseList( Lin kList &L )/将L所指的带头结点的单链表逆置if( L- next & L- next-next)当链表不是空表或单结点时p=L-n ext;q=p-n ext; p - n ext=NULL;/将开始结点变成终端结点while (q) /每次循环将后一个结点变成开始结点p=q; q=q_n ext ; p_next = L- n ext ;L-next = p;作业2.1,2.2答案见习题册后面答案2.6答案：解答：

9、a.(4)(1)b.(7)(11)(8)(4) C1)c.(5)(12)d.(11)(9)(1)(6)或(11)2.7答案：解答：a.(11)(3)(4)b.(10)(12)(8)(10)(3)(4)c.(10)(12)(7)(3)(4)d.(12)(11)(3)(14)e.(9)(11)(3)(14)(9)(4)( 1)e(1)P-n ext=P-n ext- n ext; (2)P_prior=P_prior-prior; P- next=S;(4) P-prior=S;(5) S- next=P;(6) S-prior=P;已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语

10、句序列在P结点后插入S结点的语句序列是- 在P结点前插入S结点的语句序列是- 删除P结点的直接后继结点的语句序列是 删除P结点的直接前驱结点的语句序列是 删除P结点的语句序列是(10) P-prior-next=P;(11) P- next-prior =P;(12) P- next-prior=S;(13) P-prior- next=S;(14) P-n ext-prior=P-prior(15) Q=P- next;(16) Q= P-prior;(17) free(P);(18)free(Q);(7) S- next= P- next;(8) S-prior= P-prior;2.31

11、答案：T ypedef struct LNodestruct LNode *n ext;(9) P-prior- n ext=p-n ext;解答：a.(12)(7) ( 3) ( 6)3 必须在b.(13)(8)(4) (5)同上c.(15)(1)(11) (18)不可变d.(16)(2)(10) (18)不可变e.(9)(14)(17)12和7的后面，其余的顺序可变ElemType data; /结点值/指针域，存储下一个结点的地址LNode,*Li nkList;Status Delete_Pre(li nklist s ElemType& e)/删除单循环链表中结点s的直接前驱 p=s

12、;while（p-n ext- n ext!=s） p=p-n ext;/ 找到s的前驱的前驱pq=p-n ext; p_n ext =s;e=q -data;free（q）;return OK;/Delete_Pre第三章一、单项选择题1. 栈中元素的进出原则是（B ）A.先进先出E.后进先出 C.栈空则进D.栈满则出2. 若已知一个栈的入栈序列是 1, 2, 3,，n,其输出序列为p1, p2, p3,，pn,若p1= n, 则pi为（C）A. IB. n=iC. n-i+1D.不确定解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序

13、必定是 1, 2, 3,，n,则出栈的序列是 n,，3, 2, 1。（若不要求顺序出栈，则输出序列不确定）3. 判定一个栈ST （最多元素为 m0）为空的条件是 （B ）A. ST-top0 B. ST-top= =0C. ST-topmOD. ST-top= =m04.在作进栈运算时，应先判别栈是否（B ）,在作退栈运算时应先判别栈是否（A ）。 当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为（B ）。为了增加内存空间的利用率和减少溢出的可能性 将两栈的（D ）,由两个栈共享一片连续的内存空间时，应,这样，当（C ）时，才产生上溢。:A.空B.满C.上溢 D.下溢A.n-1B

14、. nC. n+1D. n/2A.长度B.深度C.栈顶D.分别设在这片内存空间的两端栈底:A.两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点C. 两个栈的栈顶在栈空间的某一位置相遇D. 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底5某堆栈的输入序列为a, b,c ,d,下面的四个序列中，不可能是它的输出序列的是（D ）。A. a ， c， b， d B. b, c，d， a C. c, d ， b, a D. d, c，a，b6.若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈（i =1,2）栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条

15、件是（B ）。A. |top2-top1|=0B. top1+1=top2C. top1+top2=mD.top1=top27. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（D ）数据结构最佳。A.线性表的顺序存储结构B. 队列 C.线性表的链式存储结构D. 栈8. 用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（A ）。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头，队尾指针都可能要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（C ）的数据结构。A.队列B.多维数组C .栈D.线性表1

16、0. 若用一个大小为 6的数组来实现循环队列，且当前（rear和front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ B ）A. 1 和 5 B. 2和 4 C. 4和 2 D. 5 和 1二填空题1. 线性表、栈和队列都是 线性结构，可以在线性表的 任意位置插入和删除元素；对于栈只能在 栈顶插入和删除元素；对于队列只能在 队尾插入元素,在_队头 删除元素。2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。3. 一个栈的输入序列是：1, 2, 3则不可能的栈输出序列是3 1 2。4. 循环队

17、列的引入，目的是为了克服队列的假溢出。5. 用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M= （M+1）%N6. 队列的特点是_先进先岀。7表达式求值是_ 应用的一个典型例子。3.1铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为123,4,5,6的六辆列车，顺序开入栈式结构的站台,则可能的出栈序列有多少种 ？(2) 若进站的六辆列车顺序如上所述,那么是否能够得到 435612, 325641,154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得 到(即写出”进栈”或

18、”出栈”的序列)。【解答】(1) 可能的不同出栈序列有 1/(61) C1 132 种。(2) 不能得到435612和154623这样的出栈序列。因为若在 4, 3, 5, 6 之后再将1,2 出栈，则1, 2必须一直在栈中，此时 1先进栈，2后进栈，2应压在1上面，不可能1先于 2出栈。154623也是这种情况。出栈序列 325641和135426可以得到。1354263-15将编号为0和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第0号栈的栈顶指针top0等于-1时该栈为空，当第1号栈的栈顶指针top1等于m时该 栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元

19、素时，使top0增1得到新的栈顶位置，当向第 1号栈插入一个新元素时，使top1减1得到新的栈顶位置。当top0+1= top1时或top0 = top1-1 时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删 除算法。0m-1【解答】T| tbot0ttop0ttop1tbot1双栈的类定义如下：#in clude template classDblStack /双栈的类定义private:int top2, bot25/双栈的栈顶指针和栈底指针Type *elements5/栈数组int m;/栈最大可容纳兀

20、素个数public:DblStack ( intsz =10 )5/初始化双栈，总体积m的默认值为10DblStack () deleteeleme nts;/析构函数void DblPush (con st Type & x, int i );/把x插入到栈i的栈顶int DblPop ( int i );/退掉位于栈i栈顶的兀素Type * DblGetTop (int i );/返回栈i栈顶兀素的值int IsEmpty ( int i ) const returntopi = boti; / 判栈 i 空否，空则返回1,否则返回0int IsFull ( )con st returnt

21、op0+1=top1; / 判栈满否，满则返回1,否则返回0void MakeEmpty ( int i );/清空栈i的内容template class Type DblStack : DblStack ( int sz ) : m(sz), top0 (-1), bot0(-1), top1(sz), bot1(sz)/建立一个最大尺寸为sz的空栈，若分配不成功则错误处理。elements = new Typem ;/创建栈的数组空间assert ( elements != NULL );/断言：动态存储分配成功与否template void DblStack : DblPush ( co

22、nst Type& x, int i )/如果IsFull () ，则报错；否则把x插入到栈i的栈顶assert ( !lsFull ( ) );/断言：栈满则出错处理，停止执行if ( i = 0 ) elements +top0 = x;/ 栈 0 情形：栈顶指针先加 1,然后按此地址进栈else elements-top1 = x ;/栈1情形：栈顶指针先减1,然后按此地址进栈template int DblStack : DblPop ( int i )/如果IsEmpty ( i )，则不执行退栈，返回0 ;否则退掉位于栈i栈顶的元素，返回1if ( IsEmpty ( i ) )r

23、eturn 0 ;/判栈空否，若栈空则函数返回 0if ( i = 0 ) top0-;/栈0情形：栈顶指针减 1else top1+ ;/栈1情形：栈顶指针加1return 1;DblGetTop ( int i )/判栈i空否，若栈空则/返回栈顶元素的值template Type * DblStack : /若栈不空则函数返回该栈栈顶元素的地址。if ( IsEmpty ( int i ) ) return NULL;函数返回空指针return& elements topi;MakeEmpty ( int i )template voidif ( i = 0 ) top0 = bot0 =

24、 -1else top1 = bot1 = m或进栈：S1.top+ S2.top-出栈：Sl.top- S2.top+栈满：S1.top=-S2.top 或 +S1.top=S2.top3.1【解答】 可能的不同出栈序列有 5种：123, 132, 213, 231, 321。 不能得到435612和154623这样的出栈序列。因为若在 4, 3, 5, 6之后再将1, 2出栈, 则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。 154623也是这种情况。出栈序列 325641和135426可以得到。3.15 画出两个栈共享存储空间S 1.m示意图，并说

25、明两个栈进栈、出栈操作时栈顶指针变化情况及栈满的条件。进栈：S1.top+S2.top-出栈：S1.top- S2.top+栈满：S1.top=-S2.top 或 +S1.top=S2.toppS! a 碎叭 1 ! 111 I祁 1 *-.! If-. 11汁“ 1 作” 1 S1.bases1.tops2.tops2. base3.28假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素（注意不设头 指针），试编写相应的队列初始化、入队列和出队列的算法。typedef struct QNode QElemType data;struct QNode *n ext;QNode,*Q

26、ueuePtr;void Ini tQueue(Queue &Q) /初始化循环链表表示的队列QQ=(QueuePtr)malloc(sizeof(QNode);Q- next=Q;/lnitQueueStatus EnQueue(QueuePtr &tail,QEIemType e) q = (QueuePtr)malloc(sizeof(QNode);/分配空间，构造入队列兀素结点q-data = e; /兀素赋值q-n ext = tail -n ext; /入队列tail -n ext = q;tail = tail -n ext; /队尾指针后移return OK;Status De

27、Queue(QueuePtr & tail,QElemType &e ) if(tail = tail -n ext) return ERROR; /队列已空q = tail -n ext- n ext;/q指向带头结点链表的第一个元素e = q-data; / 返回出队列元素tail -n ext- next = q -n ext; /元素出队歹Ufree(q);/释放空间return OK;3.30假设将循环队列定义为：以rear和length分别指示环形队列中的队尾元素的位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的入队列和出队列元素的算法(在出队列的算法

28、中要返回队头元素)。队空条件:Q.length=O队满条件： Q.le ngth=MAXSIZEStatus En CyQueue(CyQueue & Q,i nt x) /带length域的循环队列入队算法if(Q.le ngth=MAXSIZE) return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.baseQ.rear=x;Q.le ngth+;return OK;/En CyQueue Status DeCyQueue(CyQueue & Q,i nt &x) /带length域的循环队列出队算法if(Q.length=0) return ERROR;

29、head=(Q.rear+ MAXSIZE -Q.le ngth+1)%MAXSIZE; /详见书后注释x=Q.basehead;Q.le ngth-;/DeCyQueue第四五章一、填充题1、 一个串中任意个连续 的字符组成的子序列称为该串的子串。2、 串的静态存储结构中的两种不同的存储方式分别是非紧缩 格式和 紧缩 格式。3、 两个串的相等，是指两个两串的长度 相等,对应位置的字符相同。4、已知二维数组 A有m行n列，采用行优先方式存储，每储单元，并且第一个元素的存储地址是 L0C(A1,1)，则数据元素 Ai,j的地址是L0C(A1,1)+(n(i-1)+(j-1)k。5、 有一个10阶

30、的对称矩阵，采用以行优先的压缩存储方式，已知元素A1,1的地址为1，则元素 A8,5的地址是 33，元素 A5,8的地址是_J3。6、 广义表(a,(a,b),d,e,(i,j),k)的长度是 5 ，深度是 3。二、单选题1、给出字符串 A= abcd，它的子串个数是CA 、10BC 、11D、14.2、 给出两个串 A= ABCDE，B= ABCdE，它们的关系是不是 。A、B串大于A串B、B串等于A串C、B串小于A串D、B串是A串的子串3、 设有两个串 A和B,求B在A中首次出现的位置的操作称作C。A 、连接B、求串长C、模式匹配D、求子串4、设串S仁ABCDEFG，串S2= PQRST，

31、函数con(x,y)返回x和y串的连接串，函数subs(s,i,j) 返回串s的从序号i的字符开始的j个字符组成的子串，而函数len(s) 则返 回串s的长度。那么，表达式 con(subs(S1,2,len(S2),subs(S1,len(S2),2)的结果串是D。、BCDEFG、BCDEFEFA、 BCDEFC、 BCPQRST5、数组通常具有的两种基本操作是A、建立与删除C、查找与修改C。B、索引与修改D、查找与索引6、在数组A中，每个数据元素 Ai,j的长度为3个字节，数组A的行下标i从1到8,而列下标j从1到10，从首地址SA开始连续存放在存储器中，若该数组按行优先存放时，数据元素A

32、8,5的起始地址为_D。、SA+144A 、 SA+141C 、SA+225D、SA+2227. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，an为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为(B )。A. 13B. 33C. 18 D. 40E.128. 将一个A100100的三对角矩阵，按行优先存入一维数组B1 - 298中，A中元素A665(即该元素下标i=66 , j=65 ),在B数组中的位置 K为(A )。A. 198B. 195C. 1979. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组

33、E1.(n(n+1)/2中，则在B中确定(ij )的位置k的关系为(A )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i10. 对稀疏矩阵进行压缩存储目的是( C )。A. 便于进行矩阵运算 B 便于输入和输出C .节省存储空间D .降低运算的时间复杂度11. 已知广义表LS= (a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是(C )。A. head(tail(LS)B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(

34、head(LS)12. 广义表(a,(b,c),d,e )的表头为(A )。A. a B. a,(b,c) C. (a,(b,c)D. (a)4.24void HStri ng_Co ncat(HStri ng &t ,HStri ng s1,HStri ng s2)/将堆结构表示的串s1和s2连接为新串tif(t.ch) free(t.ch);if(!(t.ch=(char*)malloc(s1.le ngth+s2.le ngth)*sizeof(char);exit (OVERFLOW);for(i=1;i=s1.length;i+) t.chi-1=s1.chi-1;for(j=1;j

35、=s2.length;j+,i+) t.chi-1=s2.chj-1;t.len gth=s1 .len gth+s2 .len gth;/HStri ng_Co neat5.23typedef structint j;int e; DSElem; typedef structDSElem dataMAXSIZE;in t cpotMAXROW;/这个向量存储每一行在二元组中的起始位置int mu, nu,tu; DSMatrix; /二元组矩阵类型Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)/求二元组矩阵的元素Aij 的值efor

36、(s=A.cpoti;sA.cpoti+1&A.datas.j!=j;s+);注意查找范围if(s 1）层最多有2 i-1个结点；一棵有n （ n0 ）个结点 的满二叉树共有（n +1） /2_个叶子和（n-1 ） /2_个非终端结点。6. 现有按中序遍历二叉树的结果为abc ,问有5种不同形态的二叉树可以得 到这一遍历结果。7. 哈夫曼树 是带权路径最小的二叉树。8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。9. 以给定的数据集合4 , 5, 6, 7, 10, 12, 18为结点权值构造的 Huffman树的加权路径长度是 165。10

37、. 树被定义为连通而不具有回路的（无向）图。11. 若一棵根树的每个结点最多只有两个 孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。12. 高度为k，且有 2 k-1个结点的二叉树称为 满二叉树。13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为Huffman树。14. 在一棵根树中，树根是入度 为零的结点，而出度 为零的结点是树叶 结点。15. Huffman树中，结点的带权路径长度是指由节点 到 树根之间的路径长度与结点权值的乘积。16. 满二叉树是指高度为 k，且有 2 k-1个结点的二叉树。二叉树的每一层i上，最多有 2i-1个结点。二、单选题1. 具有10个叶

38、结点的二叉树中有(B) 个度为2的结点。(A)8(B)9(C)10(D)112. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_( 3)次序的遍历实现编号。(1)先序(2)中序(3)后序(4)从根开始按层遍历3. 由2、3、4、7作为结点权值构造的树的加权路径长度B。A、33B、30C、36D、404. 高度为6的满二叉树，总共有的结点数是B。A、15B、63C、20D、255. 下面描述根树转换成二叉树的特性中，正确的是C。A、根树转换成的二叉树是唯一的，二叉树的根结点有左、右孩子。B、根树转换成

39、的二叉树是不唯一的，二叉树的根结点只有左孩子。C、根树转换成的二叉树是唯一的，二叉树的根结点只有左孩子。D、根树转换成的二叉树是不唯一的，二叉树的根结点有左、右孩子。6.如图所示的4棵二叉树中，不是完全二叉树的是C。A、oB、 oooooo o o oo oC、oD、 oooooo ooo7.某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则其后序遍历的结点序歹y是d 。A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca8.已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJ,按后序遍历所得到的结点序列为DCEGBFHKJ

40、,按先序遍历所得到的结点序列为ABCDGEIHFJK 。m为一棵二叉树上的两个结点，在中序遍历时,n在m前的条件是C、n在m右方、n是m祖先、n在m左方、n是m子孙10.二叉树第i层结点的结点个数最多是（设根的层数为1）)2i-1C）2i)2i-111.树的后根遍历序列等同于该树对应的二叉树的:）先序序列）中序序列）后序序列12.树最适合用来表示 CQA.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据13.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法A.正确B.错误14.假定在一棵二叉树中，双分支结点数为15,单分支结点数为 30

41、个，则叶子结点数为 B 个。A . 15B . 16D. 4715.按照二叉树的定义，具有3个结点的不同形状的二叉树有C种。A. 3B. 4C. 5D. 616.深度为5的二叉树至多有C个结点。A. 16B. 32C. 31D. 1017.对一个满二叉树，m个树叶，n个结点，深度为h，则 _D qA. n=h+mB. h+m=2nC. m=h-1D. n=2 h-118.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A.不发生改变B.发生改变C.不能确定D.以上都不对19.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为 uwtvs ,那么该二叉树的后序A. uwvtsB.

42、 vwutsC. wuvtsD. wutsv20.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_OA.正确B.错误21.在一非空二叉树的中序遍历序列中，根结点的右边A oA.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点22.已知某D o1叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是A. acbedB.decabC.deabcD. cedba23. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_C_存储结构。A.二叉链表 B.广义表存储结构C.三叉链表

43、D.顺序存储结构24. 在线索化二叉树中，t所指结点没有左子树的充要条件是_B_ oA. t left=NULLB. t ltag=1C. t ltag=1 且 t left=NULL D.以上都不对25. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B_Lchild ) & ( ! T -Rchild )Count+ ; /计数器加1CountLeaf( T -Lchild, count);CountLeaf( T -Rchild, count);6.43交换所有结点的左右子树void Bitree_Revolute(Bitree T)if(T)T-lchildT

44、-rchild; /交换左右子树if(T-lchild) Bitree_Revolute(T-lchild);if(T-rchild) Bitree_Revolute(T-rchild);/左右子树再分别交换各自的左右子树/Bitree_Revolute第七章一、选择题1对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为(B )A) 0( n) B ) 0(n+e) C ) O( n*n) D ) O( n*n*n)2 设无向图的顶点个数为n,则该图最多有( B )条边。2A) n-1 B ) n(n-1)/2 C ) n(n+1)/2D ) n3. 连通分量

45、指的是( B )A) 无向图中的极小连通子图B) 无向图中的极大连通子图C) 有向图中的极小连通子图D) 有向图中的极大连通子图4. n个结点的完全有向图含有边的数目( D )A) n*n B ) n (n+1)C) n/2D) n* (n-1 )5. 关键路径是(A )A) AOE网中从源点到汇点的最长路径B) AOE网中从源点到汇点的最短路径C) AOV网中从源点到汇点的最长路径D) AOV网中从源点到汇点的最短路径6. 有向图中一个顶点的度是该顶点的(C )A)入度B ) 出度 C )入度与出度之和D )(入度+出度)/27. 有e条边的无向图，若用邻接表存储，表中有(B )边结点。A

46、) e B ) 2e C ) e-1 D ) 2(e-1)&实现图的广度优先搜索算法需使用的辅助数据结构为（B ）A ）栈B）队列C）二叉树D）树9 实现图的非递归深度优先搜索算法需使用的辅助数据结构为（A ）A ）栈B）队列C）二叉树D）树10. 存储无向图的邻接矩阵- -定是一个（C ）A ）上三角矩阵B ）稀疏矩阵C ）对称矩阵 D ）对角矩阵11在一个有向图中所有顶点的入度之和等于出度之和的（B ）倍A ) 1/2B) 1C) 2D) 412.在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为（B )A)O( n)B )O(n+e)C23)O(n )D) O(n )13.

47、下列关于 AOE网的叙述中，不正确的是（B )A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成14. 具有10个顶点的无向图至少有多少条边才能保证连通（A ）A） 9B） 10 C ） 11 D ） 1215. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（D ）2 2A） eB） 2e C ） n -eD） n -2e16. 对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表头向量的大、n+1、n+e小为 AA、nC、n-1 二、填空题1. 无向图中所有顶点的度数之和等于所有边数的 倍。2具有n个顶点的无向完全图中包含有 n（n-1）/2条边，具有 n个顶点的有向完全图中包含有n（n-1） 条边。3. 个具有n个顶点的无向图中，要连通所有顶点则至少需要n-1 条边。5. 对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为 ，对用邻接表表示的图进行任一种遍历时，其时间复杂度为O（n+e）q6对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别