数据结构导论真题分类整理详细综述

1、第一章 概述 真题16. 下列程序段的时间复杂度为 。for（i=1 ；i=n ；i+） for（j=1 ；j=n ； j+）for（k=1 ； k=n ； k+） s=i+j+k ；17. 在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为 16. 下列程序段的时间复杂度为 。i=0 ；s=0；while （in ） i+ ；s=s+i ；17.数据的逻辑结构被分为集合结构、 、树形结构和图状结构 4 种。1. 数据的不可分割的最小标识单位是（）A. 数据项B.数据记录C.数据元素D.数据变量2. for（i=0 ；im ；i+）for （ j=0 ；jt ； j+）c

2、i j=0；for （ i=0 ；im ；i+）for （ j=0 ；jt ； j+ ）for （k=0；kn；k+）cij=ci j+ai k*bk j； 上列程序的时间复杂度为（ ）A. O（m+n t）B.O（m+n+t）C.O（mnt）D.O（mt+n）16. 在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、 和散列存储方式等四种。17. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为 。1. 从逻辑上可以把数据结构分为（）A. 动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构2. 关于算法的描述，不正确的

3、是（）A.算法最终必须由计算机程序实现B. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界C. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态D. 算法的优劣与算法描述语言无关16. 在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为 。17. 存储结点之间通常有四种基本存储方式，即顺序存储方式、 索引存储方式、 和散列存储方式。1. 在数据结构中，数据的基本单位是 （ ） A.数据项B.数据元素C.数据对象D.数据文件2. k=1; for （ i=0 ； in ； i+ ） for（j=0 ；jn ；j+） Aij=k+；上述程序段的时间复杂度为 （

4、 ）A.O （ n2） B.O（n） C.O（2n） D.O （ 1）16. 数据的逻辑结构通常包括集合、线性结构、 和图状结构。1. 在数据结构中，从逻辑上可以把数据结构分成（ ）A.线性结构和非线性结构 B.紧凑结构和非紧凑结构 C.动态结构和静态结构 D. 内部结构和外部结构2. for（i=0；im； i+） for （ j=0； jn；j+ ）Aij=i*j ；上面算法的时间复杂度为 （ ） A.O（m2） B.O（n2）C.O（mn）D.O（m+n ）则称该类运算为16.如果操作不改变原逻辑结构的 “值 ”，而只是从中提取某些信息作为运算结果， 型运算。3从逻辑关系来看，数据元素的

5、直接前驱为0 个或 1个的数据结构只能是（ ）A 线性结构B.树形结构C.线性结构和树型结构D. 线性结构和图状结构16在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为 17每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为 1.数据的基本单位是（） A. 数据项2.下列程序的时间复杂度为（）i=0 ； s=0； while （ sn） i+ ； s=s+i； A.O（ n ）B.O（ 2n ） C.O（n）16. 在数据结构中，数据的逻辑结构分为集合、17. 通

6、常从正确性、易读性、 和高效率等B. 数据类型C.数据元素 D. 数据变量D. O （ n2）、树形结构和图状结构等四类。4 个方面评价算法（包括程序）的质量。1.数据结构中所定义的数据元素，是用于表示数据的（A.最小单位 B.最大单位 C.基本单位D. 不可分割的单位2.数据的四种基本存储结构是指（）A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B顺序存储结构、索引存储结构、链式存储结构、散列存储结构C顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构16.数据表示和 是程序设计者所要考虑的两项基本任务。17.一个算

7、法通常可从正确性、易读性、健壮性和 等四个方面评价、分析。1.若要描述数据处理的变化过程，其正确的次序应为（ ）A.处理要求、基本运算和运算、算法B. 处理要求、算法、基本运算和运算C. 基本运算和运算、处理要求、算法D. 算法、处理要求、基本运算和运算2.从运算类型角度考虑，属于引用型的运算是( )16.算法通常可分为程序、伪语言算法和17.时间复杂性描述量级中，若某算法达到1.数据的四种基本逻辑结构是指 ( ) A.数组、链表、树、图形结构 C.线性结构、链表、树、图形结构A.插入、删除B.删除、修改C.查找、读取D. 查找、删除三种类型。量级，则该算法通常是不可计算的。B. 线性表、链表

8、、栈队列、数组广义表D. 集合、线性结构、树、图形结构2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( )A. 最大时间复杂性和最小时间复杂性B.最好时间复杂性和最坏时间复杂性C. 部分时间复杂性和总体时间复杂性D. 平均时间复杂性和最坏时间复杂性16. 根据不同的描述方式，对数据的操作运算通常可分为加工型运算和 两种基本 类型。17. 数据结构中的算法，通常采用最坏时间复杂度和 两种方法衡量其效率。1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为()A. 逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.机外表示、存

9、储结构、逻辑结构2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常()A. 对数阶量级复杂性大于线性阶量级B. 对数阶量级复杂性小于线性阶量级C.对数阶量级复杂性等于线性阶量级D. 两者之间无法比较16. 从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和 。17.用程序设计语言、伪程序设计语言并混合自然语言描述的算法称为 算法。1下列数据组织形式中， ()的各个结点可以任意邻接。A 集合B 树形结构 C线性结构D图状结构2设某二维数组 A 1.n，1.n，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为( AO(log2n) BO(n)CO(nlog2n) D

10、O(n2)16下列程序段的时间复杂性量级是 。for (i=1;in; i+) for (j=1; jnext=p next nextB.p=p nextC.p=p next nextD.p next=p5. 向一个栈顶指针为 hs 的链栈中插入一个 *s 结点时，应执行的操作为（ ） A.hs next=s; B.s next=hs;hs=s;C.snext=hs next;hs next=s; D.s next=hs;hs=hs next;6. 设循环队列的元素存放在一维数组Q0 30中，队列非空时， front 指示队头元素的前一个位置， rear指示队尾元素。如果队列中元素的个数为11

11、，front 的值为 25，则 rear 应指向的元素是（ ）A.Q4 B.Q5 C.Q14 D.Q157. 定义二维数组 A18，010，起始地址为 LOC ，每个元素占 2L 个存储单元，在以行序为主序的 存储方式下，某数据元素的地址为 LOC+50L ，则在以列序为主序的存储方式下，该元素的存储地址 为（ ）A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L18. 在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 和。19. 在有 n 个元素的链队列中，入队和出队操作的时间复杂度分别为 和 。20. 在栈结构中，允许插入的一端称为 ;

12、在队列结构中，允许插入的一端称为 。21. 在循环队列中，存储空间为 0n-1。设队头指针 front 指向队头元素前一个空闲元素，队尾指针指 向队尾元素，那么其队空标志为 rear=front ，队满标志为 。3. 在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的 （） A. 直接前趋B.直接后继C.开始结点D.终端结点4. 将两个各有 n 个元素的有序表合并成一个有序表，其最少的比较次数为（）A.n B.2n-1 C.2n D.n25. 栈和队列共同具有的特点是（）A. 都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出，也

13、能先进后出6. 若用一个有 6 个单元的数组来实现循环队列， rear和 front 的初值分别为 0 和 3。则从队列中删除一 个元素，再添加两个元素后， rear 和 front 的值分别为（） A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 17. 数组 A0.50.5 的每个元素占 5 个字节，将其以列为主序存储在起始地址为 1000 的内存单元中， 则元素 A 5 5的地址是（ ） A.1175 B.1180 C.1205 D.121018. 在一个长度为 n的顺序表中第 i 个元素（ 1i ）n之前插入一个元素时，需向后移动 个元素。24.两个串是相等的，当且仅当两个串

14、的长度相等且 的字符都相同。34.设两个数据元素均为整型数据的线性表A=（a1 ， a2， ， an）和 B=（b1 ， b2， ， bm） 。若 n=m 且ai=bi（i=1，2, ，n）则认为 A=B；若 ai=bi（ i=1 ，2, ，j）且 aj+1BJ+1 ，（ Jnext-next!=h) p=p-next;p-next=h;后(其中， p-next 为 p指向结点的指针域)，则 ( )A.p-next 指针指向链尾结点 B.h 指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点5. 设顺序表有 19个元素，第一个元素的地址为 200，且每个元素占 3个字节，则第 14 个

15、元素的存储 地址为 ( ) A.236 B.239 C.242 D.2456. 一个栈的入栈序列是 a,b,c,d,e，则栈的输出序列不可能是 ( )A.dceab B.decba C.edcba D.abcde7. 元素大小为 1个单元，容量为 n个单元的非空顺序栈中，以地址高端为栈底，以 top 作为栈顶指针， 则出栈处理后， top 的值应修改为 ( ) A.top=top B.top=n-1 C.top=top-1 D.top=top+117. 设双链表中结点的前趋指针和后继指针的域名分别为t1 和 r1，指针 s 指向双链表中的一个结点 (该结点既非头结点，也非尾结点)，则删除 s

16、指针所指向结点的操作为 “-stl-r1=s-r1 ；”和“”。32.如题 32 图所示，在栈的输入端有 6 个元素，顺序为 A，B，C， D ，E ，F。能否在栈的输出端得 到序列 DCFEBA 及 EDBFCA ？若能，给出栈操作的过程，若不能，简述其理由。35.某带头结点的单链表的结点结构说明如下：typedef struct node1 int data;struct node1 *nextnode；试设计一个算法 int copy(node *head1, node *head2) ，将以 head1 为头指针的单链表复制到一个不带 头结点且以 head2 为头指针的单链表中。3.

17、设顺序表有 9个元素，则在第 3 个元素前插入一个元素所需移动元素的个数为 ( )A.5 B.6 C.7 D.94. 设 p 为指向双向循环链表中某个结点的指针， p 所指向的结点的两个链域分别用p llink 和 prlink表示，则同样表示 p 指针所指向结点的表达式是 ( )A.p llinkB.p rlinkC.p llink llink D.p llink rlink5. 一个向量第一个元素的存储地址是100，每个元素的长度为 2，则第 5个元素的存储地址是 ( )A. 110B. 108C. 100 D. 1206. 设有一个栈，按 A、B、C、D 的顺序进栈，则可能为出栈序列的是

18、( )A.DCBA B.CDAB C.DBAC D.DCAB7. 在一个具有 n个单元的顺序栈中，假定以地址低端（即0 单元）作为栈底，以 top为栈顶指针，则当做出栈处理时， top 变化为 （ ）A.top+B.top-C.top 不变 D.top=017. 设有指针 head 指向不带表头结点的单链表，用 next 表示结点的一个链域，指针 p 指向与链表中结 点同类型的一个新结点。现要将指针 p 指向的结点插入表中，使之成为第一个结点，则所需的操作为 “ p next=hea；d ”和“ 。”18. 单链表中逻辑上相邻的两个元素在物理位置上 相邻。19. 在一个长度为 n 的数组中删除

19、第 i 个元素（ 1 i ）n时，需要向前移动的元素的个数是 。31.如题 31 图所示，输入元素为 A ， B， C，在栈的输出端得到一个输出序列ABC ，试写出在栈的输入端三个可能的输入序列。34.下面程序段为删除循环链表中第一个info域值等于 x 的结点，请填上程序中缺少的部分。循环链表的结构如题 34 图所示：struct nodeint info;struct node *link;int Delete (struct node *head, int x) struct node *p, *q; /*p: 当前处理的结点； q：p 的前驱结点 */ if (! head ) ret

20、urn (0);if (head link =head) if (head info=x) free (head); head=NULL ； return (x) return (0);p=head; q=head;while (q link!=head) q(=1) ;while (p link!=head) if (p info=x) (2) ;if (p=head) head=(3) ;free (p);return (x);else q=p ; ( 4) ;return (0); 1关于栈和队列的说法中正确的是()A 栈和队列都是线性结构B.栈是线性结构，队列不是线性结构C.栈不是线性

21、结构，队列是线性结构D. 栈和队列都不是线性结构2关于存储相同数据元素的说法中正确的是()A 顺序存储比链式存储少占空间 B. 顺序存储比链式存储多占空间C. 顺序存储和链式存储都要求占用整块存储空间D. 链式存储比顺序存储难于扩充空间3从逻辑关系来看，数据元素的直接前驱为0 个或 1个的数据结构只能是( )A 线性结构B.树形结构C.线性结构和树型结构D. 线性结构和图状结构4已知一个单链表中，指针 q 指向指针 p的前趋结点，若在指针 q所指结点和指针 p 所指结点之间 插入指针 s 所指结点，则需执行()A q next=s；p next=s；B.q next=s；s next=p； C

22、.qnext=s；qnext=p；D.q next=s；s next=q； 5在长度为 n 的线性表中删除一个指针 p 所指结点的时间复杂度是( )A O(n)B.O(1) C.O(log2n) D.O(n2)6设一个栈的输入序列是 a,b,c,d，则所得到的输出序列 (输入过程中允许出栈) 不可能出现的是 ( ) A a，b， c， dB.a， b，d，cC.d，c，b，aD.c，d，a， b7关于串的叙述中，正确的是()A 空串是只含有零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D. 串是含有一个或多个字符的有穷序列8在具有 m 个单元的循环队列中

23、，队头指针为front ，队尾指针为rear，则队满的条件是(Afront=rearB.(front+1)%m=rearC.rear+1=frontD.(rear+1)%m=front9设有二维数组A n n表示如下：，则 A ii(0i -1n)的值为()Ai*(i-1)/2B.i*(i+1)/2C.(i+2)*(i+1)/2D.i2/218在顺序表上读表元算法的时间复杂度为 。19双链表中前驱指针为 prior ，后继指针为 next，在指针 P 所指结点前插入指针 S 所指的结点，需 执行下列语句： Snext=P;S prior=P prior;P prior=S;20设数组 A0.8

24、0.8的起始元素位置为 a，每个元素占 2 L 个存储单元，按行序为主序存储。 若元素 A i j 的存储位置为 a+66 L，则元素 Aji的存储位置为 。29有一字符串序列为 5*-x-y/x+2 ，利用栈的运算将其输出结果变为 5x-*yx+/-2 ，试写出该操作的入 栈和出栈过程（采用 push（a）表示 a 入栈， pop（a）表示 a 出栈）。 34设单链表的结点结构如下： struct nodedatatype data;struct node*next;试编写一个函数 int count（struct node *head,datatype x） 统计单链表中数据域为 x 的结

25、点个数。3. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算 时间的存储方式是（ ）A.单链表 B.仅有头指针的单循环链表C.双链表D. 仅有尾指针的单循环链表4. 从一个长度为 n 的顺序表中删除第 i 个元素（ 1in）时，需向前移动的元素的个数是（）A.n-i B.n-i+1 C.n-i-1 D.i5. 顺序栈 S中 top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素 e进栈操作的主要语句为（ ）A.s.elemtop =e； s.top=s.top+1；B.s.elem top+1 =e；s.top=s.top+1 ；C.s

26、.top=s.top+1；s.elemtop+1=e；D.s.top=s.top+1 ； s.elem top =e；6. 循环队列 sq 中，用数组 elem 025存放数据元素， sq.front 指示队头元素的前一个位置， sq.rear 指示队尾元素的当前位置， 设当前 sq.front 为 20，sq.rear 为 12，则当前队列中的元素个数为 （ ） A.8 B.16 C.17 D.187. 设有一个 10 阶的对称矩阵 A，采用压缩存储方式以行序为主序存储，a00 为第一个元素，其存储地址为 0，每个元素占有 1 个存储地址空间，则 a45 的地址为（）A.13 B.35 C.

27、17 D.3618. 顺序表的存储密度为 ，而链表的存储密度为 。19. 对于栈只能在 插入和删除元素。20. 在循环队列中， 存储空间为 0 n-1,设队头指针 front 指向队头元素前一个空闲元素， 队尾指针指向 队尾元素，那么队满标志为 front=（rear+1）%n ，队空标志为 。3. 对于长度为 n 的顺序表执行删除操作，则其结点的移动次数（）A.最少为 0，最多为 n B.最少为 1，最多为 n C.最少为 0，最多为 n-1 D. 最少为 1，最多为 n-14. 在一个单链表中，若 p 所指结点是 q 所指结点的前驱结点，则删除结点 q 的正确操作是 （A. p-next=

28、q B. p-next=q-next C. p=q-next D. p-next=q-next-next5. 有关栈的描述，正确的是（）A. 栈是一种先进先出的特殊的线性表B. 只能从栈顶执行插入、删除操作C. 只能从栈顶执行插入、栈底执行删除D. 栈顶和栈底均可执行插入、删除操作6. 二维数组 A 10 20采用按行为主序的存储方式，每个元素占4 个存储单元，若 A 0 0的存储地址为 300，则 A 1010的地址为（）A.700 B.1120 C.1180 D.114018. 对长度为 n 的顺序表执行删除操作， 其删除算法在最坏情况下的时间复杂性为 。19. 串是一种特殊的线性表，串常

29、见的存储结构有顺序存储和 两种方式。20. 我们通常把队列中允许插入的一端称为 。21. 二维数组在机器级的具体实现，通常均采用 存储结构。34. 试编写一个函数，以读取单链表的第i 个元素。3. 若在长度为 n 的顺序表中插入一个结点，则其结点的移动次数( )A.最少为 0，最多为 n B.最少为 1，最多为 n C.最少为 0，最多为 n+1 D. 最少为 1，最多为 n+14. 在一个单链表中，若 p 所指结点是 q 所指结点的前驱结点，则在结点p、q 之间插入结点 s 的正确操作是 ( )A.s-next=q ； p-next=s-nextB.p-next=q ； p-next=sC.

30、s-next=q-next ； p-next=s D.s-next=q-next ；p-next=s-next5. 若有一串数字 5、6、7、8 入栈，则其不可能的输出序列为 ( )A.5、6、7、8B.8、7、6、 5C.8、7、5、6 D.5、6、8、76. FORTRAN 语言对数组元素的存放方式通常采用 ( )A. 按行为主的存储结构B.按列为主的存储结构C.按行或列为主的存储结构D. 按行和列为主的存储结构18. 对顺序表执行删除操作，其删除算法的平均时间复杂性为 。19. 若head表示循环链表的头指针， t表示尾结点， 则头指针 head与尾结点 t之间的关系可表示为 。20.

31、我们通常把队列中允许删除的一端称为 。21. 二维数组 A 5 6采用按列为主序的存储方式，每个元素占3 个存储单元，若 A00的存储地址是 100，则 A4 3的存储地址是 。34.若循环单链表长度大于 1，p 为指向链表中某结点的指针，试编写一算法删除p 结点的前驱结点。3. 下列关于线性表的叙述中，不正确的是( )A.线性表是 n 个结点的有穷序列B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继D.线性表结点间的逻辑关系是 1:1 的联系4. 在一个单链表中，若 p所指结点不是最后结点，则删除 p 所指结点的后继结点的正确操作是 ( )C.p-next=p-next-

32、next D.p-next=pD.没有共同之处A.p=p-next B.p-next=p-next5. 栈和队列 ()A.共同之处在于二者都是先进先出的特殊的线性表B. 共同之处在于二者都是先进后出的特殊的线性表C. 共同之处在于二者都只允许在顶端执行删除操作3 个存储单元，若 A0 0的B.142 C.150 D.1576. 二维数组 A5 6采用按列为主序的存储方式，每个元素占 存储地址是 100，则 A4 3的存储地址是 ( )A.12718. 判断带头结点 head 的单链表为空的条件是 。19. 若顺序表每个元素长度均为 5，其中第一个元素的存储地址为 30，则第 6 个元素的存储地

33、址为 _20. 若 front 和 rear 分别表示循环队列 Q 的头指针和尾指针， m0 表示该队列的最大容量，则判断循环 队列为满的条件是 。21. 对于顺序存储结构的二维数组，通常采用 两种存放方式存储数据元素。34.试编写一算法，以完成在带头结点单链表L 中第 i 个位置前插入元素 X 的操作。3. 下列关于线性表的基本操作中，属于加工型的操作是()10A. 初始化、求表长度、插入操作B.初始化、插入、删除操作C. 求表长度、读元素、定位操作D.定位、插入、删除操作4. 在一个单链表中，若 p 所指结点不是最后结点， s 指向已生成的新结点，则在 p 之后插入 s 所指结 点的正确操

34、作是（ ）A.snext=p next; p next=s; B.p next=snext; s next=p;C.snext=p; p next=s; D.s next=p next; p=s;5. 若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（）A.3 种 B.4 种 C.5 种 D.6 种6. C 语言对数组元素的存放方式通常采用（ ）A. 按行为主的存储结构 B.按列为主的存储结构C.按行或列为主的存储结构D. 具体存储结构无法确定18.对顺序表执行插入操作，其插入算法的平均时间复杂性为 。19. 在具有 n 个单元、且采用顺序存储的循环队列中，队满时共有 个元素。

35、20. 若 front 和 rear 分别表示循环队列 Q 的头指针和尾指针， m0 表示该队列的最大容量，则循环队列 为空的条件是 。21. 二维数组 A1020 采用按行为主序的存储方式， 每个元素占 4 个存储单元， 若 A00 的存储地址 为 300，则 A1010 的地址为 。34.设某单链表中，存在多个结点其数据值均为D ，试编写一算法统计该类结点的个数。2设某二维数组 A 1.n，1.n，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ AO（log2n） BO（n）CO（nlog2n） D O（n2）3在线性表的下列存储结构中，读取元素花费时间最少的是（）A单链表B

36、双链表C循环链表D顺序表4将一个头指针为 p 的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应 为（） q=NULL;while (p!=NULL) ( ) p=q;A r=q; q=p; p=p - next; q - next=r; C r=q; p=p - next; q=p; q - next=r; 5数组通常具有两种基本运算，即（ A创建和删除B 索引和修改B q=p; r=q; p=p - next; q - next=r;D q=p; p=p - next; r=q; q - next=r; )C读和写D排序和查找17在顺序存储的线性表 （ a1,a2 ，an

37、）中的第 i （1 i个元n）素之前插入一个元素， 则需向后移动 个元素。18 在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：； sq - datasq - top=x ；19 链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的1129如图所示，输入元素为 A， B，C，在栈的输出端得到一个输出序列ABC ，求出在栈的输入端所有可能的输入序列。（ 5 分）34 设某头指针为 head 的单链表的结点结构说明如下：（ 6 分）typedef struct node1 int data;struct node1*nextnode;试设计一个算法 void cha

38、nge （node*head）, 将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。35编写一个算法 void DisplayQueue （），产生 50 个 300 600 之间的随机整数 （调用一次 MyRand（） 可产生一个符合条件的随机整数）。每产生一个数据，若是奇数，则入队列，若是偶数，则从队首取 出一个数据。要求：（ 8 分）（1）队列用链表实现；（2）每产生一个数显示一次相应操作后的队列当前状态；（ 3）无需定义函数 int MyRand（） ；（ 4）显示队列可调用函数void DisOne （QueptrT

39、p lq） ，也无需定义；（5）设链队列定义为：typedef struct linked_queue int data;struct linked_queue*next;LqueueTp;typedef struct queueptr LqueueTp *front, *rear;QueptrTp;QueptrTp lq;122.某二叉树的后根遍历序列为第四章 树 真题dabec，中根遍历序列为 debac，则先根遍历序列为（）A. acbedB.becabC.deabcD.cedba3.含有 n 个结点的二叉树用二叉链表表示时，空指针域个数为（ ）A. n-1B.nC.n+1D.n+212

40、.有关树的叙述正确的是 （ ）A. 每一个内部结点至少有一个兄弟B. 每一个叶结点均有父结点C.有的树没有子树D. 每个树至少有一个根结点与一个叶结点。24.对于一棵满二叉树，若有 m 个叶子，则树中结点数为 。30.已知一棵二叉树的先根遍历序列为ABCDEGHF ，中根遍历序列为 CBEDAGFH ，画出该二叉树。34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。5. 由带权为 9，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）A.23B.37C.44 D.4612. 用 n 个值构造一棵二叉排序树，它的最大高度为（ ）A.n/2B. n C

41、. n+1D.log 2n21. 若满二叉树的结点数为 n，则其高度为 。22. 在一棵具有 n 个结点的完全二叉树中，从树根起，自上而下、从左到右地给所有结点编号。若编号为 i 的结点有父结点，那么其父结点的编号为 。23. 深度为 k 的二叉树，结点数最多有 个。24. 某二叉树的后根遍历为 ABKCBP，M则该二叉树的根为 。29. 某通讯电文由 A，B，C，D，E，F 六个字符编码组成，每个字符编码在电文中出现的次数分别是6，5，9，10，20，1，试画出这六个字符编码所用的哈夫曼树。30. 已知一棵二叉树的顺序存储结构如题 30 图所示，其中表示虚结点，试构造该二叉树。ABGCDHE

42、F题 30 图34. 若两棵二叉树 B1和 B2皆为空，或者皆不空且 B1的左、右子树和 B2的左、右子树分 别相似，则称二叉树 B1和 B2 相似。试编写算法，判别给定两棵二叉树是否相似。8. 具有 n 个结点的二叉树，拥有指向孩子结点的分支数目是（）A.n-1B.nC.n+1D.2n9. 对一棵有 100个结点的完全二叉树按层序编号，则编号为49 的结点，它的左孩子的编号为（ ）A.99B.98C.97D.5010. 有 m 个叶子结点的哈夫曼树，其结点总数是（）A.2m-1B.2mC.2m+1D.2(m+1)22.深度为k 的二叉树至多有 _个结点，最少有 _个结点。29.已知一棵二叉树

43、的前序序列是 ABCDEFG ，中序序列是 CBDAEGF 。请构造出该二叉树，并给出 该二叉树的后序序列。30.将题 30 图所示的由三棵树组成的森林转化为一棵二叉树。138.含有 n 个结点的二叉树采用二叉链表存储时，空指针域的个数为()A.n-1B.nC.n+1D.n+29.在一棵深度为 H 的完全二叉树中，所含结点的个数不少于( )A.2H-1-1 B.2H-1C.2H-1D.2H19.对一棵深度为 10 的满二叉树按层编号，则编号为 51 的结点，它的双亲结点编号为 21. 具有 n 个叶子结点的哈夫曼树，其结点总数为 。22. 一棵具有 n 个结点的树，所有非终端结点的度均为k，则

44、该树中叶子结点个数为 。25. 某二叉树的后根遍历序列为 abd，中根遍历序列为 adb，则它的先根遍历序列为 。30.画出题 30 图所示的二叉树的二叉链表存储结构。35.设二叉树的结点类型定义如下：typedef struct nodedatatype data;struct node*lchild,*rchild;Bitree;Bitree*t;试编写一个计算二叉树深度的递归算法 (int Depth(Bitree*t) 。8.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )A. 高度等于其结点数B.任一结点无左孩子C.任一结点无右孩子D.空或只有一个结点9.在

45、完全二叉树中，若一个结点是叶结点，则它没有( )A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点D. 左孩子结点，右孩子结点和兄弟结点12.若构造一棵具有 n 个结点的二叉排序树， 最坏的情况下其深度不超过 ( )A.n/2 B.n C.n+1/2 D.n+119.在一个具有 n 个结点的单链表中查找值为 m的某结点，若查找成功，则需平均比较的结点数为 20. 深度为 15 的满二叉树上，第 11 层有 个结点。21. 对一棵有 100 个结点的完全二叉树按层编号， 则编号为 49的结点，它的左孩子的编号为 30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC 和

46、DBFHGECA ，试画出这棵二叉树。8.除根结点外，树上每个结点 ( )A.可有任意多个孩子、一个双亲B. 可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D. 只有一个孩子、一个双亲9.题 9图中树的度为 ( )14B.3 C.5 D.820.设 F、C是二叉树中的两个结点，若 F是 C的祖先结点， F和 C 的位置关系为：21.若用后根遍历法遍历题 21 图所示的二叉树，其输出序列为则在采用后根遍历方法遍历该二叉树时，F 必定在 C 的29.分别写出题 29 图中二叉树的先根、中根、后根遍历序列。10高度为 h 的完全二叉树中，结点数最多为（）A2h-1 B.2h+1 C.2

47、h-1 D.2h11由 m 棵结点数为 n 的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上 具有的结点个数是（）A mnB.mn-1 C.n（m-1） D.m（n-1）21有 4 个结点且深度为 4 的二叉树的形态共有 种。22某二叉树的先根遍历序列为孩子是IJKLMNO ，中根遍历序列为 JLKINMO ，则该二叉树中根结点的右30某二叉树的先根遍历序列为 并写出它的后序遍历序列。8.含有 10 个结点的二叉树中，度为 0 的结点数为 4，则度为 2 的结点数为（A.3 B.4 C.5 D.69.对一棵有 100个结点的完全二叉树按层编号，则编号为49 的结点，它的父结点的编号为（A.24 B.25 C.98 D.99 21.三个结点可构成 种不同形态的二叉树。22.对于一棵具有 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为中个用于