2022年数据结构期末综合练习汇编 .pdf

《2022年数据结构期末综合练习汇编 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期末综合练习汇编 .pdf（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 数据结构期末综合练习2012 年 12 月期末练习一一、单项选择题1. 一种逻辑结构在存储时（） 。 A 只要存储数据元素间的关系 B只能采用一种存储结构 C 可采用不同的存储结构 D只要存储数据元素的值2同一种逻辑结构（） 。A只能有唯一的存储结构B可以有不同的存储结构C只能表示某一种数据元素之间的关系D以上三种说法均不正确3 . 对链表 , 以下叙述中正确的是（） 。A不能随机访问任一结点 B结点占用的存储空间是连续的C插入删除元素的操作一定要要移动结点 D 可以通过下标对链表进行直接访问4链表所具备的特点是（） 。A可以随机访问任一结点 B占用连续的存储空间C插入删除元素的操作不需要

2、移动元素结点 D 可以通过下标对链表进行直接访问5线性表在存储后, 如果相关操作是: 要求已知第i 个结点的位置访问该结点的前驱结点，则采用（）存储方式是不可行的。A单链表 B双链表 C 单循环链表 D 顺序表6数据的物理结构（） 。 A与数据的逻辑结构无关 B仅仅包括数据元素的表示C只包括数据元素间关系的表示 D 包括数据元素的表示和关系的表示7栈和队列的共同特点是（） 。 A都是先进后出 B元素都可以随机进出C只容许在端点处插入和删除元素 D都是先进先出8线性结构中数据元素的位置之间存在（）的关系。 A 一对一 B一对多9元素2，4，6，8 按顺序依次进栈，按该栈的的可能输出序列依次入队列

3、，该队列的可能输出序列是（） （进栈出栈可以交替进行）。 A8，6，2，4 B8，4，2，6 C6，2，4， 8 D8，6，4，2 10以下表中可以随机访问的是（） 。 A 单向链表 B双向链表C单向循环链表D顺序表11在一个不带头结点的链队中，假设f 和 r 分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x 中的运算为（） 。 A x=rdata ；r=rnext; Br=rnext; x=rdata C x=fdata ；f=fnext; Df=fnext; x=fdata 12算法的时间复杂度与（）有关。 A所使用的计算机 B与计算机的操作系统C与算法本身 D与数据

4、结构13设有一个20 阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 35 页 - - - - - - - - - 2 到一维数组B 中（数组下标从1 开始） ，则数组中第38 号元素对应于矩阵中的元素是（） 。Aa10,8 Ba7,6 Ca9,2 Da8,5 14设有一个长度为n 的顺序表，要删除第i 个元素需移动元素的个数为（） 。 A n-i+1 Bn-i Cn-i-1 D i 15在 C语言中，分别

5、存储“S”和 s，各需要占用（）字节。 A一个和两个 B两个 C一个 D两个和一个16在一个单链表中，p、q 分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用的语句是（） 。 Ap=q-next Bp-next=q Cp-next=qnext D q-next=NULL 17一棵有 n 个结点，采用链式存储的二叉树中，共有（）个指针域被有效使用（即指针域为非空） 。 A n+1 Bn Cn-1 Dn-2 18从一个栈顶指针为top 的链栈中删除一个结点时，用变量x 保存被删结点的值，则执行（） 。 A x=top-data; top=top-nex

6、t; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data; 19在一棵二叉树中，若编号为i 的结点存在双亲结点，则双亲结点的顺序编号为（） 。 A i/2.0 Bi/2向下取整 C2i+1 Di+2 20在一个链队中，假设f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（） 。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next; 21设一棵哈夫曼树共有2n+1 个结点，则该树有（）个非叶结点。 A n Bn+1 Cn-1 D2n 22一个栈的进栈序列是a，b，c， d，e，则栈的

7、不可能输出序列是（） （进栈出栈可以交替进行）。A dceab Bedcba Cdecba Dabcde 23一棵完全二叉树共有4 层，且第 4 层上有 2 个结点，该树共有（）个非叶子结点( 根为第一层 ) 。 A 5 B4 C3 D9 24有一个长度为10 的有序表， 按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（） 。A26/10 B29/10 C 29/9 D31/10 25如图 1 所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 A abedfc Bacfebd Caebcdf D aebcfd b d f e c a

8、 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 35 页 - - - - - - - - - 3 图 1 26排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（） 。A冒泡B直接插入C折半插入D选择排序27一组记录的关键字序列为（56，30,89 ，66，48，50，94,87,100 ） ，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（） 。 A 30，50,

9、48 ，56，66，89，94,100,87 B 50 ，30,48 ，56，66，89，94,87,100 C48，30,50 ，56， 66，89，94,87,100 D50，30,48 ，66，56，89，94,87,100 28设有一个10 阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组 B中（数组下标从1 开始） ，则矩阵中元素A8,5在一维数组B中的下标是（） 。A33 B32 C85 D41 29线性表以（）方式存储，能进行折半查找。 A 关键字有序的链接 B顺序 C关键字有序的顺序 D 数组C多对多 D每一个元素都有一个直接前驱和一个直接后继30在一

10、个无向图中，所有顶点的度数之和等于边数的（）倍。 A3 B2.5 C1.5 D2 二、填空题1. 数据的逻辑结构在计算机中的表示称为_结构。2栈和队列的操作特点分别是_ _和 _ _。3. 求两个 n 阶矩阵的乘积，算法的基本操作为_，时间复杂度为_。4结构中的数据元素存在多对多的关系称为_ _结构。5设有一个长度为25的顺序表 , 第 8号元素到第 25号元素依次存放的值为8,9,10,11, 25, 某人想要在第8个元素前插入1 个元素 7（也就是插入元素作为新表的第8 个元素），他的做法是从第8号元素开始 , 直到第 25 号元素依次向后移动1 个位置 , 然后把 7 存放在 8号位置，

11、其结果是新表中第25 号元素的值为 _ 。6根据数据元素间关系的不同特性，通常可分为集合、线性、四类基本结构。7在双向链表中，要在p 所指的结后插入q 所指的结点 (设 q所指的结点已赋值)，其中所用的一条语句（p-next）-prior=q ；的功能是使P 所指结点的 _指向 q 。8要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_和 _ 。9设有一个带头结点的，头指针为head的单向链表，p 指向表中某一个结点，且有p-next= =NULL, 现要删除头结点，并使该单向链表构造成单向循环链表，通过操作 head=head-nex

12、t; _。10在一个单向链表中p 所指结点之后插入一个s 所指向的结点时，应执行 _ _ _和 p-next=s; 的操作。11从一个栈顶指针为top 的链栈中删除一个结点时，用d 保存被删结点的值，可执行_。(结点的指针域为next,数据域为data) 12在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、。13 循环链队列中， 设 front 和 rear 分别为队头和队尾指针，(最多元素为MaxSize,采用少用一个元素的模式 ),判断循环链队列为满的条件为_ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

13、 名师精心整理 - - - - - - - 第 3 页，共 35 页 - - - - - - - - - 4 14一棵二叉树中顺序编号为i 的结点，若它存在左、右孩子，则左、右孩子编号分别为_、_。15对稀疏矩阵进行压缩存储,可采用三元组表，一个6 行 7 列的稀疏矩阵A 相应的三元组表共有 8 个元素 ,则矩阵 A 共有 _个零元素。16向一个栈顶指针为h 的链栈中插入一个s所指结点时，可执行s-next=h;和_。17.一棵有 20 个结点的 4 度的树，其中3 度结 1 个， 2 度结 1 个， 1 度结 2 个，则该树共有_个叶结点。18在一个链队中，设f 和 r 分别为队头和队尾指针

14、，则插入s 所指结点的操作为_和 r=s; (结点的指针域为next) 19一棵有 18 个结点的二叉树，其2 度结点数的个数为8，则该树共有_个 1 度结点20设有一棵深度为4 的完全二叉树， 第四层上有5 个结点， 该树共有 _个结点。 （根所在结点为第1 层）21如图 2所示的二叉树，其先序遍历序列为_。图 2 22 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_、_ _和 _ _三项信息。23 在查找表中， 通过记录的某关键字能唯一地确定一个记录，该关键字称为 _。24在对一组记录(55,39,97,22,16,73,65,47,88) 进行直接插入排序时，当把第

15、7 个记录65插入到有序表时，为寻找插入位置需比较_次。三、综合题1 （1）对给定权值3，1 ，4，4，5，6，构造深度为5 的哈夫曼树。 (设根为第1 层) (2) 求树的带权路径长度。（3）链接存储上述哈夫曼树，结点中共有多少个个指针域为空,说明理由 . 2(1)以 2，3， 4，7，8，9 作为叶结点的权，构造一棵哈夫曼树( 要求每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。(2) 一棵哈夫曼树有n 个叶结点，它一共有多少个结点？简述理由？376542189 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

16、 - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 35 页 - - - - - - - - - 5 3. (1) 如下的一棵树 ,给出先序遍历序列(2) 把 1,2,3,4,5,6,7,8,9 填人 ,使它成为一棵二叉排序树提示：设图中的树是二叉排序树，找出中序遍历序列与1，2，9 的对应关系(3) 请在该树中再插入一个结点3.5 作为叶结点，并使它仍然是一棵二叉排序树。图 3 4一组记录的关键字序列为（46，79，56，38， 40，84）（ 1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（ 2）对

17、上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。5设查找表为 (5,6,7,8,9,10,11,12,13,14) （1）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2) 给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树是否是二叉排序树(设树中没有相同结点)？(3) 为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？6设查找表为 (50,60,75,85,96,98,105,110,120,130) A1 A2 A4A7 A5 A9 A8 A3 A6 名师资料总结 - - -精品资料欢迎下载 - - - - -

18、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 35 页 - - - - - - - - - 6 (1) 说出进行折半查找成功查找到元素120 需要进行多少次元素间的比较？(2) 为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？（ 3）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) 四、程序填空题1以下函数为直接选择排序算法，对a1,a2, ,an中的记录进行直接选择排序，完成程序中的空格typedef struct int key; ,NODE; void selsort(NODE a,int

19、 n) int i,j,k; NODE temp; for(i=1;i= _(1)_;i+) k=i; for(j=i+1;j= _(2)_;j+) if(aj.keyak.key) _(3)_; if(i!=k) temp=ai; _(4)_; _(5)_; 2以下是用尾插法建立带头结点且有n 个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3, ,n，完成程序中空格部分。NODE *create(n) NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE); head= （1）; （2）;pnext=NULL; /*建立

20、头结点 */ for(i=1; idata; while （q-next!=NULL ）q=q-next; _(1)_ q=p; p=p-next; while(p-data!=x) q=p; _(2)_ _(3)_ 4以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right，数据域 data为字符型， BT 指向根结点）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1）; （2）; （3）; 期末复习一答案一、单项选择题1C 2 B 3 A 4 C 5 A 6D 7 C 8 A 9

21、D 10 D 11 C 12 C 13C 14 B 15 D 16 C 17 C 18 A 19 B 20 C 21 A 22 A 23 B 24 B 25 C 26 C 27 B 28 A 29 C 30 D 二、填空题1物理（存储）2后进先出、先进先出3乘法O(n3) 4图状（网状）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 35 页 - - - - - - - - - 8 586树形图状7 直接前驱的左指针8n-1,O(n) 、9 p-next= head; 1

22、0s-next=p-next; 11d=top-data;top=top-next; 12左指针右指针13front= =(rear+1)% MaxSize 142i 2i+1 1534 16h=s; 1713 18r-next=s; 191 2012 21215347896 22行下标、列下标、非零元素值23主关键字243 三、综合应用题1. (1) 图 4 （2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58 (3) 共 11 个结点 ,22 个指针域 ,除根结点外 ,每个结点对应一个指针域.,共 10 个指针域非空 ,故有22-10=12 个空指针域 , 64523149

23、84413 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 35 页 - - - - - - - - - 9 2(1) 图 5 2：1110 3: 1111 4：110 7：00 8：01 9：10 （2） 2n-1 个，因为非叶结点数比叶结点数少一个。3 . (1) A1 A2 A4 A7 A8 A5 A9 A3 A6 (2) (3) 图 6 4(1)初始序列7 4 2 1 5 6 3 8 9 3.5 8 9 5 9 7 2 4 3 33 18 15 名师资料总结 -

24、- -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 35 页 - - - - - - - - - 10 46，79， 56，38，40， 84 40，79， 56，38， 40， 84 40，79， 56，38，79， 84 40，38， 56，38，79， 84 40，38， 56，56，79， 84 40，38， 46，56，79， 84 (2) 图 6 5.(1) 图 7 (2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的

25、根结点的值；若它的右子树非空，则右子树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值; 9 7 10 14 11 8 5 1213 6 56 79 38 40 84 46 84 79 38 40 46 5656 79 38 40 46 79 38 40 84 84 56 46 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 35 页 - - - - - - - - - 11 左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。(3) 3 次6

26、(1)3 次(2)4 次(3) 图 8四、程序填空题1 （1）n-1 （2）n （3）k=j （4）ai=ak （5）ak=temp 2（1）p （2）q=p （3）(NODE*)malloc(sizeof(NODE) （4）p （5）q=p 3. (1) q-next=head; (2) p=p-next; (3) q-next=p-next; 4（1）Inorder(BT-left) （2）printf(“%c ”,BT-data) （3） Inorder(BT-right) 96 75 98 130 105 85 50 110120 60 名师资料总结 - - -精品资料欢迎下载 - -

27、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 35 页 - - - - - - - - - 12 期末练习二一、单项选择题1 . 结构中的元素之间存在一对多的关系是（） 。 A 集合 B线性结构 C 树形结构 D图状结构2在 C语言中，顺序存储长度为3 的字符串，需要占用（）个字节。 A4 B3 C6 D12 3 . 对不带头结点的单向链表, 判断是否为空的条件是（） （设头指针为head） 。Ahead=NULL Bhead-next= =NULL Chead-next= =head Dhead =NULL 4串

28、函数StrCat （a,b ）的功能是进行串（） 。 A比较 B复制 C赋值 D连接5. 在一个不带头结点的单循环链表中，p、 q 分别指向表中第一个结点和尾结点，现要删除第一个结点，可用的语句是（） 。 A p=q-next; p=p-next; Bp-next=q ; p=p-next; C p-next=q-next;q=p; Dp=p-next; q-next=p; 6一棵有n 个结点采用链式存储的二叉树中，共有（）个指针域为空。 An+1 Bn Cn-1 Dn-2 7一个栈的进栈序列是1，2，3， 4，5，则栈的不可能输出序列是（） （进栈出栈可以交替进行）。A12345 B4351

29、2 C 45321 D 54321 8设一棵哈夫曼树共有n 个非叶结点，则该树有（）个叶结点。 An Bn+1 Cn-1 D2n 9一个队列的入队序列是2，4，6，8，按该队列的输出序列使各元素依次入栈，该栈的可能输出序列是（） 。 A8，6，4，2 B6， 2，4，8 C8，4，2，6 D8，2，4，6 10从一个栈顶指针为top 的链栈中删除一个结点时，用变量x 保存被删结点的值，则执行（） 。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data; 11在一个链队中，

30、假设f 和 r 分别为队头和队尾指针，已生成一个结点p, 要为结点p 赋值 x, 并入队的运算为（） 。 A . p-data=x; p-next=NULL; f-next=p; f=p; B p-data=x; p-next=NULL ;r-next=p;r=p; C p-data=x; p-next=r;r=s; D p-data=x; p-next=f;f=s; 12一棵完全二叉树共有5 层，且第5 层上有六个结点，该树共有（）个结点。 A30 B20 C21 D23 13设有一个25 阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中 （数组下标从1 开始

31、） ， 则矩阵中元素a7,6在一维数组B中的下标是 （） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 35 页 - - - - - - - - - 13 A34 B14 C26 D27 14在一个无向图中，所有顶点的度数之和等于边数的（）倍。 A 3 B2.5 C 1.5 D2 15. 以下程序段的结果是 c 的值为（） 。char a5= “1236789”, int *p=a, int c=0; while(*p+)c+; A8, B7 C 10 D12 16

32、已知如图 1 所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 图 1 17一棵有 23 个结点，采用链式存储的二叉树中，共有（）个指针域为空。 A 24 B25 C23 D45 18已知如图2 所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。Aabcedf Babcefd Caebcfd Dacfdeb 图 2 19在一棵二叉树中，若编号为i 的结点是其双亲结点的左

33、孩子，则双亲结点的顺序编号为（） 。b d f e c a V6V7V1V2V3V8V4V5名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 35 页 - - - - - - - - - 14 A i/2 B2i-1 C2i+1 Di/2 -1 20对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列。 A按层次 B后序 C中序 D前序21设一棵哈夫曼树共有2n+1 个叶结点，则该树有（）个叶结点。 A n-1 Bn Cn+1 D2n 22在有序表 2，4，7， 1

34、4，34，43，47，64，75，80，90，97，120 中，用折半查找法查找值 80 时，经（）次比较后查找成功。A4 B2 C3 D523已知如图3 所示的一个图，若从顶点a 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 A abecdf Bacfebd Caebcfd D aedbfc 图 3 24有一个长度为9 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（） 。A 25/10 B25/9 C20/9 D17/9 25已知如图4 所示的一个图，若从顶点B出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（） 。 A.BADEHC

35、FG B.ADEHCGF C.BADECHFG D.BADEHCFG 图 4 b d f e c a F GA B C HDE 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 35 页 - - - - - - - - - 15 26排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（） 。 A冒泡 B直接插入 C折半插入 D 选择排序27一组记录的关键字序列为（46，38，56，

36、40，79，84） ，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（） 。 A 40，38，46，79，56，84 B40，38， 46，56，79，84 C40，38， 46，84，56，79 D38，40，46，56，79，84 28一组记录的关键字序列为（46，79，56，38，40，84） ，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（） 。 A 40，38，46，79，56，84 B40，38，46， 56，79，84 C40，38，46，84，56， 79 D 38，40，46，56，79，84 29在有序表 21 ，23，28， 33，43，45

37、， 46，73，77，78，89，99，106 中，用折半查找值 43 时，经（）次比较后查找成功。A6 B3 C8 D 4 30排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（）排序。 A 归并 B插入 C快速 D选择二、填空题1. 本书中介绍的树形结构和_ 属非线性结构。2在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_、右指针。3设有一个长度为18 的顺序表， 要在第 4 个元素之前插入2 个元素（也就是插入元素作为新表的第 5 个和第 4 个元素），则最少要移动元素的个数为（） 。4一棵二叉树中顺序编号为i 的结点， 若它存在左

38、、 右孩子，则左、右孩子编号分别为_ _、_ _。5在双向链表中，要删除p 所指的结点，可以先用语句（p-prior ）-next=p-next ；然再用语句 _。6串的两种最基本的存储方式是_ _和 _ _。7在一个单向链表中p 所指结点之后插入一个s 所指向的结点时，应执行s-next=p-next; 和 _ _的操作 . 8一棵有2n-1 个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 _个叶结点。9一个栈和一个队列的输入序列都为abcdefg，它们可能有相同的输出序列吗？_。（若没有则回答没有，若有则写出序列,进栈出栈可以交替进行）。10对于一棵具有n 个结点的二叉树，其相应

39、的链式存储结构中共有_个指针域为空。11.从一个栈顶指针为top 的链栈中取栈顶元素，用d 保存栈顶元素的值，可执行_。(结点的数据域为data) 12_遍历二叉排序树可得到一个有序序列。13. 循环链队列中，设front 和 rear 分别为队头和队尾指针，(最多元素为MaxSize,), 判断循环链队列为空的条件是_为真。14如图 5所示的二叉树，其后序遍历序列为。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 35 页 - - - - - - - - - 16 图

40、 5 15. 对稀疏矩阵进行压缩存储,可采用三元组表，设a 是稀疏矩阵A 相应的三元组表类型（结构体类型）变量，a 中的一个成员项是三元组类型的结构体数组data，按书中定义，若a.data0.i=2;a.data0.j=3; a.data0.v=16; 它提供的A 数组的相关信息有_ 16如图 6 所示的二叉树，其先序遍历序列为_ _。图 6 17设有一棵深度为5 的完全二叉树，该树共有20 个结点 ,第五层上有个叶结点。（根所在结点为第1 层）18图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_的。 (回答正确或不正确 ) 19中序遍历 _树可得到一个有序序列。20二叉树为二叉

41、排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是_的。 (回答正确或不正确) 21如图 7所示的二叉树，其后序遍历序列为_。e f g i b a c h d g f a b d e c 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 35 页 - - - - - - - - - 17 图 7 22 对记录序列排序是指按记录的某个关键字排序，记录序列按 _排序结果是唯一的。23 .给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的

42、，这种说法是 _的。(回答正确或不正确) 24按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题1. (1) 说明什么是顶点活动网(AOV 网)和拓扑序列（2）设有向图G 如下，写出3 种拓扑序列，（3）在图 G 中增加一条边，使图G 仅有一条拓扑序列图 8 2设查找表为 (16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n 个元素进行冒泡排序要进行多少趟冒泡？第j 趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以

43、数据元素作为树结点 ) 3如下是一棵二叉排序树，A1,A2, A9 代表 1，2，3,9 中各个不同数字，376542189 a b c d 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 35 页 - - - - - - - - - 18 （ 1）给出对该树中序遍历的结果（ 2） A3,A5,A7 的值各为多少？（ 3）请在该树中再插入一个结点9 .5 作为叶结点，并使它仍然是一棵二叉排序树图 9 4(1) 设有查找表 5,14,2,6,18,7,4,16,3, 依次

44、取表中数据，构造一棵二叉排序树。（ 2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。5(1) 设有查找表 17 ，26，14，16， 15，30，18，19，28，依次取表中数据构造一棵二叉排序树 . (2) 对上述二叉树给出后序遍历的结果(3). 对上述二叉树给出中后序遍历的结果(4) 在上述二叉树中查找元素15 共要进行多少次元素的比较? 6 （1）对给定权值2，1，3，3， 4，5，构造哈夫曼树。（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。四、程序填空题1以下函数是二叉排序树的查找算法，若二叉树

45、为空，则返回根结点的指针，否则，返A1 A2 A4 A7 A5 A9 A8 A3 A6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 35 页 - - - - - - - - - 19 回值是指向树结点的结构指针p（查找成功p 指向查到的树结点，不成功p 指向为 NULL ）完成程序中的空格typedef struct Bnode int key; struct Bnode *left; struct Bnode *right; Bnode; Bnode *BSear

46、ch(Bnode *bt, int k) /* bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/ Bnode *p; if(bt= _(1)_) return (bt); p=bt; while(p-key!= _(2)_) if(kkey) _(3)_; else _(4)_; if(p=NULL) break; return(_(5)_); 3 .设有一个头指针为head 的不带头结点单向链表，p、q 是指向链表中结点类型的指针变量， p 指向链表中结点a, （设链表中没有结点的数据域与结点a 的数据域相同）,写出相关语句(1).使该单向链表成为单向循环链表(2)插入结点

47、s,使它成为 a结点的直接前驱q=p; x=p-data; while （_(1)_ ）q=q-next; q-next=head; q=p; p=p-next; while(p-data!=x) q=p; _(2)_ s-next=p; _(3)_ 答案一、单项选择题1C 2 A 3 A 4 D 5 D 6 A 7 B 8 B 9 A 10 A 11 B 12 C 13 D 14D 15 B 16 A 17 A 18 B 19 A 20 C 21 C 22A 23 D 24B 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

48、师精心整理 - - - - - - - 第 19 页，共 35 页 - - - - - - - - - 20 25 C 26 C 27 B 28 B 29 B 30 D 二、填空题1图状结构2值域左指针315 42i 和 2i+1 5 （p-next）-prior=p-prior ；6顺序存储链式存储7 p-next=s; 8n 9 abcdefg 10n+1 11d=top-data; 12中序13front= =rear 14gdbeihfca 15A 的第一个非零元素的下标为2，3 ，元素为16 16abdefcg 175 18正确19二叉排序20不正确21519876432 22主关键

49、字23不正确24关键字相等的记录三、 综合应用题1(1)原序列 16 15 20 53 64 7 15 16 20 53 7 64 n-1 趟15 16 20 7 53 64 n-j 次15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 (2) 7 15 20 64 16 53 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 35 页 - - - - - - - - - 21 图 10 2(1)原序列 16 15 20

50、53 64 7 15 16 20 53 7 64 n-1 趟15 16 20 7 53 64 n-j 次15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 (2) 图 11 (3)平均查找长度 =（1*1+2*2+3*3 ） /6=14/6 3(1) 图 12 (2)中序遍历中序2，3，4，5，6，7，14，16，18 4(1) 2 4 6 16 7 3 18 5 14 7 15 20 64 16 53 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -