数据结构期末综合练习2.pdf

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

1、数据结构（本）期末综合练习数据结构（本）期末综合练习一一、单项选择题 针 对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则 采 用（1）存储方式最节省时间。A.单链表 B.双链表 C.单循环链表 D.顺序表2.线性表采用链式存储时，其 地 址（C ）。A.一定是不连续的 B.必须是连续的C.可以连续也可以不连续 D.部分地址必须是连续的 数 据结构中，与所使用的计算机无关的是数据的（D）结构。A.物理 B.存储 C.逻辑与物理 D.逻辑4 .带头结点的单向链表的头指针为he a d,该链表为空的判定条件是（C ）的值为真。A.he a d =N U L L B.he a d-n e

2、 xt=he a dC.he a d-n e xt=N U L L D.he a d =he a d-n e xt5 .以下特征中，（D）不是算法的特性。A.有穷性 B.确定性 C.可行性 D.有0个或多个输出6 .设顺序存储的线性表长度为n,对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（A ）。A.n/2 B.n C.n-1 D.n-i+1 设 有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（A）。A.n-i+1 B.n-i C.n-i-l D.i8.一个栈的进栈序列是5,6,7,8,则栈的不可能的出栈序列是（A

3、）（进出栈操作可以交替进行）A.5,8,6,7B.7,6,8,5C.7,6,5,8 D.8,7,6,5 栈 的插入删除操作在（D）进行。A.栈底 B.任意位置 C.指定位置D.栈顶1 0.栈和队列的相同点是（D ）。A.都是后进先出 B.都是后进后出C.逻辑结构与线性表不同D.逻辑结构与线性表相同，都是操作规则受到限制的线性表 以 下 说法正确的是（C ）。A.栈的特点是先进先出，队列的特点是先进后出B.栈和队列的特点都是先进后出C.栈的特点是先进后出，队列的特点是先进先出D.栈和队列的特点都是先进先出 在C语言中，利用数组a存放字符串“H e llo ，以下语句中正确的是（A D ）。A.c

4、 ha r a 1 0 =H e llo”；B.c ha r a f lO ;a=H e llo”;C.c ha r a 1 0 =H e llo ;D.c ha r a 1 0 =H ,e ,T,T,o ;|元素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是（D）（进栈出栈可以交替进行）。A.8,6,4,2 B.2,4,6,8C.4,2,8,6 D.8,6,2,41 4 .设有一个1 5 阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中。（矩阵A 的第一个元素为a.j,数组b 的下标从1 开始），则数组元素 b 1 3 对应A 的矩阵元素是（A ）。A.

5、a5.3 B.a6.4 C.a7.2 D.a6,81 5 .设有一个1 5 阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到 维数组B中（数组下标从1 开始），则矩阵中元素a?.6 在一维数组B中的下标 是（C ）A.42 B.1 3 C.2 7 D.321 6 一棵完全二叉树共有30 个结点，则该树一共有（D）层（根结点所在层为第一层）。A.6 B.4 C.3 D.5 串 函数 S tr C m p （d”，“D”）的 值 为（BA.0 B.1 C.-1 D.31 8.以下说法正确的是（D）。A.连通图G的生成树中不一定包含G的所有顶点B.连通图G的生成树中一定要包含G的

6、所有边C.连通图G的生成树一定是唯一的D.连通图G一定存在生成树 在 一 棵二叉树中，若编号为i 的结点存在右孩子，则右孩子的顺序编号为（D）。A.2 i B.2 i-l C.2i+2 D.2 i+l2 0.对二叉排序树进行（C）遍历，遍历所得到的序列是有序序列。A.按层次 B.前序 C.中序 D.后序 设 一棵有n个结点采用链式存储的二叉树，则该树共有（D）个指针域为空。A.2 n B.2 n+l C.2 n+2 D.n+12 2 .以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（AA.直接选择 B.冒泡 C.直接插入 D.折半插入2 3.已知如图1 所

7、示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（B）。A.a b c e d f B.a b c e f d C.a e b c f d D.a c f d e b2 4 .对长度为n的线性表进行h找，在等概率情况下，平均查找长度为（B）。A.n B.（n+1）/2 C.2 n D.n-1在有序表 L 3,8,1 3,33,4 2,4 6,6 3,7 6,7 8,8 6,9 7,1 0 0 中,用折半查找值 8 6 时，经（D）次比较后查找成功。A.6B.3C.8D.42 6.如 图 若 从 顶 点 a(A )oA.a c f g e d bB.a e d c

8、 b g fC.a c f e b d gD.a e c b d g f出发按深度优先搜索法进行遍历，则可能得到的顶点序列为 有 一个长度为1 0 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（AA.2 9/1 0 B.31/1 0 C.2 6/1 0 D.2 9/92 8.一棵哈夫曼树有1 2 个叶子结点（终端结点），该树总共有（C）个结点。A.2 2 B.2 1 C.2 3 D.2 4 组记录的关键字序列为（37,7 0,4 7,2 9,31,8 5）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（A ）。A.31,2 9,37,4 7,7 0

9、,8 5 B.2 9,31,37,4 7,7 0,8 5C.31,2 9,37,7 0,4 7,8 5 D.31,2 9,37,8 5,4 7,7 03 0.队列的删除操作在（B）进行。A.队头 B.队尾 C.队头或队尾 D.在任意指定位置得分评卷人1 .把数据存储到计算机中，并具体体现数据之间的逻辑结构称为 结构。2 .设有一个不带头结点的单向循环链表，结点的指针域为n e x t,指针p 指向尾结点，现要使p 指向第一个结点，可用语句。3.结构中的数据元素存在一对一的关系称为顺序结构。4 .要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为n

10、 e x t,头指针为h e a d,尾指针为p,则可执行h e a d=h e a d-n e x t;p-n e x t=h e a d。在 双向链表中，每个结点有两个指针域，-个指向结点的直接前驱，另一个指向结点的直接后驱。6 .设有一个非空的链栈，栈顶指针为h s,要进行出栈操作，用 x保存出栈结点的值，栈结点的指针域为n e x l,数据域为d a t a,则可执行 x=h s-d a t a ；和h s=h s-n e x t ；7 .设有一个头指针为h e a d 的单向链表，p 指向表中某一个结点，且有p-n e x t=N U L L,通过操作p-next=head,就可使该

11、单向链表构造成单向循环链表。8.循 环 队 列 的 最 大 存 储 空 间 为 MaxSize,队 头 指 针 为 f,队 尾 指 针 为 r,当（q-r+l）%MaxSize=q-f 时表明队列己满。从 一个栈顶指针为h 的链栈中删除一个结点时，用 X 保存被删结点的值，可执行x=h-data;和 h=h-nexto（结点的指针域为 next）1 0.程序段 int count=0;char*s=ABCD”；while（*s!=,0,）s+;count+;执行后count=4 两 个串相等的充分必要条件是串长度相等且对应位置的字符相等12.一棵二叉树总结点数为1 1,叶结点数为5,该树有 4

12、 个双分支结点2个单分支结点。对 二叉树的遍历可分为一 M_、中序、后序、层次四种不同的遍历次序。1 4.设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9,该完全二叉树一共有 18 个结点。一 棵 有 n 个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有2n-l_ 个结点。16.双向循环链表中，p 指向表中某结点，则通过p 可以访问到p 所指结点的直接后继结点和直接前驱结点，这种说法是 正确 的（回答正确或不正确）。17.一棵有14个结点的完全二叉树，则它的最高层上有_ 7 个结点。18.栈和队列的操作特点分别是先进后出（后进先出）和 先进先出（后

13、进后出）。19.如图2 所示的二叉树，其先序遍历序列为 abdgcef hi。20 .折半查找只适用于顺序存储结构 存储的有序表。哈 希 函数是记录关键字值与该记录上假地址 之间所构造的对应关系。22.深度为k 的二叉树最多有（2-）-1 结点。23.二叉树排序中任一棵子树都是二叉排序树，这种说法是正确 的。（回答正确或不正确）串的两种最基本的存储方式是顺序存储.和链式存储得 分评卷人三、综合题1.设一组记录的关键字序列为（4 9,8 3,5 9,4 1,4 3,4 7）,采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6个元素的初始堆（2）以二叉树描述逐次取走堆顶

14、元素后，经调整得到的5个元素、4个元素的堆2.设有一个不带头结点的单向链表，头指针为h e a d,结点类型为N O D E,每个结点包含一个数据域d a t a 和一个指针域n e x t,该链表有两个结点，p 指向第二个结点（尾结点），按以下要求写出相应语句（不要求完整程序，（1）、（2）、（3）、（4）是一个连续的过程）。（1）新开辟一个结点，使指针s 指向该结点，结点的数据成员d a t a 赋值为1（2）把该结点插入链表的尾部，释放指针s 的指向（3）删除链表的第一个结点（4）已知p i 指向另一个新结点，把它插入到p所指结点和尾结点之间3.设有序表为（1 3,1 9,2 5,3 6

15、,4 8,51,63,8 4,9 1,1 1 6,1 3 5,2 0 0）,元素的下标依次为1,2,1 2。（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5,需要进行多少次元素间的比较才能确定不能查到4.（1）设有序列 1 0,1 2,1 5,1 9,2 2,2 5,1 0 0,1 3 0,1 50,2 0 0 画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）（2）为了成功查找到1 0 0 需要进行多少次元素间的比较？为了查找9,经过多少次元素间的比较可知道查找失败？5.（1）对给定

16、数列 7 6,4,8,2 0,9,6,1 8,5,依次取数列中的数据，构造一棵二叉排序树。（2 ）对个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素2 0 共要进行多少次元素的比较？6.（1）设有查找表 5,1 4,2,6,1 8,7,4,1 6,3 ,依次取表中数据，构造 棵二叉排序树。（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。四、程序填空题1.以下冒泡法程序对存放在a l ,a2L，a n 中的序列进行排序，完成程序中的空格部分，其 中n是元素个数，要求按升序排列。vo i d b s o r t (N O D E

17、 a ,i n t n)N O D E t e m p;i n t i,j,f l a g;f o r p l;(1)j a i+l .k e y)f l a g=l;t e m p=a i ;a i =a i+l _ _ _ _ _ _ _ _ _ _;a i+l =t e m p _ _ _ _ _ _ _ _ _ _ _ _ _;)i f(f l a g=0)b r e a k;)程 序 中f l a g的功能是一(5)当某趟冒泡中没有出现交换则已排好序，结束循环2 .以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为l e f t和r i g h

18、t,数据域d a t a为字符型，BT指向根结点)。vo i d P r e o r d e r (s t r u c t B T r e e N o d e *B T)i f(B T!=N U L L)(1)p r i n l f(“c”,BT-data);(2)Preorder(BT left);(3)Preorder(Blk right);3 .设 线 性 表 为(6,1 0,1 6,4),以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#define NULL0void main()NODE a,b,c,d,*head,*p;a.data=6;b.data=10;

19、c.data=16;d.data=4;/*d 是尾结点*/h e a d=(1)&a;a.n e x t=&b;b.n e x t=&c;c.n e x t=&d;(2)d-n e x t=N U L L;/*以上结束建表过程9p=h e a d;/*p为工作指针，准备输出链表*/d o p r i D t f(d n”,p，d a t a )：(4)p=p-n e x t;w h i l e f (5)p!=N U L L);4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和 rig h t,数据域data为字符型，BT指向根结点)。voi

20、d Inorder(struct BTreeNode*BT)if(BT!=NULL)(1)I n o r d e r(BT-l e f t);(2)p r i n t f(%c,B T-d a t a);(3)I n o r d e r(B T-r i g h t);数据结构（本）期末综合练习一参考答案一、单项选择题1.D 2,C 3.D 4.C 5.D 6.A 7.A1 3.D 1 4.A 1 5.C 1 6.D 1 7.B 1 8.D8.A 9.D1 9.D 20.C1 0.D 1 1.C 1 2.A21.D 22.A 23.B24、B 25.D 26.A 27.A 28.C 29.A 3

21、0.A二、填空题1.物 理（存储）3.线性5.结点的直接后继结点的直接前驱7.p-n e x t=h e ad;9.h=h-n e x t;1 1.串长度相等且对应位置的字符相等1 3.先序、中序、后序、层次1 5.2n-l1 7.71 9.abd gc e f h i2 1.存储地址2 3.正确2.p=p-n e x t;4.p-n e x t=h e ad；6.h s-d at a;h s-n e x t;8.(r+1)%M ax Si z e=f1 0.41 2.4；21 4.1 81 6.正确1 8.先进后出（后进先出）2 0.顺序存储结构22.2k-l2 4.顺序存储链式存储三、综合

22、题先 进 先 出（后进后出）图 32.(1)s=(NODE*)malloc(sizeof(NODE);s-data=1;(2)p-next=s;s-next=NULL；free(s)(3)head=head-next；(4)prnext=p-next；p-next=pi；3.(1)19,48,84,116,20 0(2)图 53 次(2)4 次；3 次图 6(2)先将给定值与根结点比较，若相等则查找成功,否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找,查找20 共进行3 次比较。6.(1)图6(2)中序遍历中序 2,3,4,5,6,7,14,16,18四、程序填空题L.(1)j

23、=n-l(2)idata)(2)Preorder(BT-left)(3)Preorder(BT-right)(1)&a(2)d-next二N U LL(3)p-data(4)p=p-next(5)p!=NULL(1)Inorder(BT-left)(2)printf(a%c,f,BT-data)(3)Inorder(BT-right)数据结构（本）期末综合练习二一、单项选择题I.数据元素是数据的基本单位，它（C）。A.只能有一个数据项组成 B.至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D.至少有一个数据项为指针类型2.一种逻辑结构（A）存储结构。A.可以有不同的 B.只能

24、有唯一的C.的数据元素在计算机中的表示称为 D.的数据元素之间的关系称为3.线性表的顺序结构中，（C）。A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高4.以下说法中不正确的是（B）。A.双向循环链表中每个结点需要包含两个指针域B.已知单向链表中任一结点的指针就能访问到链表中每个结点C.顺序存储的线性链表是可以随机访问的D.单向循环链表中尾结点的指针域中存放的是头指针5.以下表中可以随机访问的是（D ）。A.单向链表 B.双向链表C.单向循环链表 D.顺序表6.双向循环链表结点的数据类型为：stru

25、ct node int data;struct node*next;/*指向直接后继*/struct node*prior;）：设 p 指向表中某一结点，要显示p 所指结点的直接前驱结点的数据元素，可用操作（B）。A.printf（%d”,p-next-data）;B.printf（%d,p-prior-data）;C.printf（%d”,p-prior-next）;D.printf（%d”,p-data）;7.设顺序存储的线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（A）。A.（n+1 ）/2 B.n C.2n D.n-i8.一个栈的进栈序列是e

26、fg h,则栈的不可能的出栈序列是（D）（进出栈操作可以交替进行）。A.hgfe B.gfeh C.fgeh D.ehfg9.设 top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x 接收栈顶元素，则出栈操作为（A）。A.x=top-data;top=top-next;B.top=top-next;x=top-data;C.x=top-next;top=top-data;D.top-next Mop;x=top-data;10.设 top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成,设用x 接收栈顶元素，则取栈顶元素的操作为（C

27、）oA.top-data=x;C.x=top-data;1 1.以下说法正确的是（CA.队列是后进先出B.top=top-next;D.x=top-data;top=top-next;)oB.栈的特点是后进后出C.栈的删除和插入操作都只能在栈顶进行D.队列的删除和插入操作都只能在队头进行 以 下说法不正确的是（CA.栈的特点是后进先出 B.队列的特点是先进先出C.栈的删除操作在栈底进行，插入操作在栈顶进行D.队列的插入操作在队尾进行，删除操作在队头进行13.串函数 StrCmp（abA,aba）的 值 为（D）。A.1 B.0 C.“abAaba D.-114.char*p;p=StrCat（

28、ABD,ABC）;Printf（“%s”,p）;的显示结果为（B）A.-1 B.ABDABC C.AB D.115.设有-个12阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中（矩 阵 A 的第一个元素为a,数组b 的下标从1 开始），则矩阵A中第4 行的元素在数组b 中的下标i 一 定 有（A）。A、7WW10 B、UWiW15 C、9WiW14 D、6WiW916.深 度 为 5 的满二叉树至多有（B）个 结 点（根结点为第一层）A.40 B.31 C.34 D.3517.已知一个图的边数为m,则该图的所有顶点的度数之和为（A）。A.2m B.m C.2m+l

29、 D.m/218.已知一个图的所有顶点的度数之和为m,则该图的边数为（D）,A.2m B.m C.2m+l D.m/219.以下说法不正确的是（D）。A.连通图G 一定存在生成树B.连通图G 的生成树中一定包含G 的所有顶点C.连通图G 的生成树中不一定包含G 的所有边D.连通图G 的生成树可以是不连通的20 .以下说法不正确的是（AA.连通图G 的生成树一定是唯一的B.连通图G 一定存在生成树C.连通图G 的生成树中一定要包含G 的所有顶点D.连通图G 的生成树一定是连通而且不包含回路21.散列查找的原理是（A）。A.在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B.按待查记录

30、的关键字有序的顺序方式存储C.按关键字值的比较进行查找D.基于二分查找的方法22.有序表为1,2,4,6,10,18,20,32,用课本中折半查找算法查找值1 8,经（B）次比较后成功查到。A.3 B.2 C.4 D.523.排序过程中，每一趟从无序子表中将个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是（A）。A.直接插入排序 B.快速排序C.冒泡排序 D.选择排序24.在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束排序过程的排序算法是（A）。A.冒泡 B.选择 C.直接插入 D.折半插入25

31、.采用顺序查找法对长度为n 的线性表进行查找（不采用表尾设监视哨的方法），最坏的情况下要进行（B）次元素间的比较。A.n+2 B.n C.n-1 D.n/226.用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（A）次元素间的比较A.4 B.3 C.5 D.62 7.如图若从顶点a HI发按索法进行遍历,A.acebdfghB.aebcghdfC.aedfbcghD.abecdfgh则可能得到的顶点序列为（D）o图 128.如图若从顶点a 出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（B）。A.acfgedbB-aedbgfcC.acfebdgD.aecbdgf29.

32、一棵哈夫曼树总共有23个结点，该树共有（D）个叶结点（终端结点）A.10B.13C.11D.1230.一棵哈夫曼树总共有25个结点，该树共有（A.12 B.13 C.14A）个非叶结点（非终端结点）。D.15二、填 空 题（每小题2 分，共 24分）1.通常数据的逻辑结构包括集 合、线 性、树 形、图 状.四种类型。2.结构中的元素之间存在多对多的关系称为图状.结构。3.设有一个单向链表，结点的指针域为n ex t,头指针为head,p 指向尾结点，为了使该单向链表改为单向循环链表，可用语句 p-n e x l=h e a d。4.设有一个单向循环链表,结点的指针域为n ex t,头指针为he

33、ad,指针p 指向表中某结点，若逻辑表达式p-next=head 的结果为真,则p 所指结点为尾结点。5.设有一个单向循环链表，头指针为h ead,链表中结点的指针域为next,p 指向尾结点的 直 接 前 驱 结 点，若 要 删 除 尾 结 点，得 到 一 个 新 的 单 向 循 环 链 表，可执行操作一p-next=head。设 有一个链栈，栈顶指针为h s,现有一个s 所指向的结点要入栈，则可执行操作s-n e x t=h s;hs=s。7.在一个链队中，f 和 r 分别为队头和队尾指针，队结点的指针域为n e x t,则插入一个s 所指结点的操作为 r-ne xt=s：r=s；8.在一

34、个链队中，f 和 r 分别为队头和队尾指针，队结点的指针域为next,s 指向一个要入队的结点，则入队操作为 r-next=s:r=s；9.循环队列的队头指针为f,队尾指针为r,当 匚=f 时表明队列为空。10 .循环队列的最大存储空间为MaxSize=6,采用少用一个元素空间以有效地判断栈空或栈满，若 队 头 指 针 front=4,当 队尾 指针 reaa 3 时队满,队列中共有5 个元素。11.A 在存储时占 _ _ _ _ 个字节。“A”在存储时占 2 个字节。12.程序段 char*s=aBcD”;n=0;while（*s!=0）if（*s=a&*s=z）n+;s+;执行后n=213

35、.一棵二叉树没有单分支结点，有 6 个叶结点，则该树总共有 11_ 个结点。14.一棵二叉树中顺序编号为5 的 结 点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在左孩子，则左孩子的编号为-10。15.按照二叉树的递归定义，对二叉树遍历的常用算法有 先序、_ 中序 、.后序 三种。根 据搜索方法的不同，图 的 遍 历 有 深度优先 广 度 优 先 两种方法。17.把,数据存储到计算机中.并具体体现数据之间的逻辑结构称为物 理（存储）18.结构中的数据元素存在多对多的关系称为 图 状（网状）.结构。如 图 2 所示的二叉树，其后序遍历序列为 gdbei hf ca。图

36、2 一 棵 有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有2 n-l 个结点。2 1.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这 种 说 法 是 错误.的。(回答正确或不正确)串 的两种最基本的存储方式分别是一顺序存储 和 _链式存储。根 据搜索方法的不同，图的遍历有 深 度 优 先、广度优先 两种方法 按 某关键字对记录序列排序，若关键字关键字相等 的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题1.(1)已知某二叉树的后序遍历序列是d e b c a,中序遍历序列是d b e a c,试画

37、出该二叉树(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为棵二叉排序树，试给出a、b、c、d、e的大小关系(3)给出该树的前序遍历序列2.(1)已知某二叉树的先序遍历序列是a e c d b,中序遍历序列是e a d c b,试画出该二叉树(2)给出上述二叉树的后序遍历序列(3)若上述二叉树的各个结点的字符分别是1,2,3,4,5,并恰好使该树成为一棵二叉排序树，试问a、b、c、d、e的值各为多少？3.(1)设有一个整数序列 4 0,2 8,6,7 2,1 0 0,3,5 4 依次取出序列中的数，构 造-棵二叉排序树(2)对上述二叉排序树，在等概率条件下

38、，求成功查找的平均查找长度4.(1)给定数列 8,1 7,5,9,2 1,1 0,7,1 9,6 ,依次取序列中的数构造一棵二叉排序树(2)对上述二叉树给出中序遍历得到的序列5.(1)利用筛选过程把序列 4 2,8 2,6 7,1 0 2,1 6,3 2,57,52 建成堆(小根堆),画出相应的完全二叉树(不要求中间过程)(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列6.(1)以给定权重值1,2,1 2,1 3,2 0,2 5为叶结点，建立一棵哈夫曼树（2）若哈夫曼树有n 个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一四、程序填空题1.以下函数在a0

39、 到中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1,完成程序中的空格typedef struct int key;NODE;i n t B i n a r y S e a r c h(N O D E a ,i n t n,i n t k)(i n t l o w,m i d,h i g h;l o w=0;h i g h=n-l;wh i l e(_ _ _(1)_ lo w =h ig h)m i d=(l o w+h i g h)/2;i f (a m i d .k e y=k)r e t ur n _(2)_ mi d;e l s e i f(_ _

40、_(3)_ am id.k ey k e y!=(2)_ k)i f(k k e y)一(3)_ p=p-left ;e l s e _(4)_ p=p-rig h t;i f(p=N U L L)b r e a k;)R e t ur n (_ _ _(5)_ p_ _ _ _ _);)3.以下函数为链队列的入队操作，x 为要入队的结点的数据域的值，from、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node*next;)；struct node*front,*rear;vo i d I n Q ue ue(E l e m T yp

41、 e x)(s t r uc t n o d e *p;p=(s t r uc t n o d e*)_ _ _(1)_malloc(sizeof(struct node)_;p-d a t a=x;p-n e xt=N U L L;_(2)re a r-n e x t=p;r e a r=_ _(3)_ p;)4.以下函数为链队列的出队操作(链队列带有头结点)，出队结点的数据域的值由x 返回，front、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node*next;)；struct node*front,*rear;E l e m

42、T yp e O ut Q ue ue O(E l e m T yp e x;i f (_(1)_ front=rear_)p r i n t f (队列下溢错误！n );e xi t (1);s t r uc t n o d e *p=f r o n t-n e xt;x=p-d a t a;f r o n t-n e xt=_ _ _(2)_ p-next.i f(p-n e xt=N U L L)r e a r=f r o n t;f r e e (p);一(3)_ return(x)数据结构（本）期末综合练习二参考答案一、单项选择题1.C 2.A 3.C 4.B 5.D 6.B 7.A

43、 8.I)9.A 10.C 11.C 12.C13.D 14.B 15.A 16.B 17.A 18.D 19.D 20.A 21.A 22.B 23.A24.A 25.B 26.A 27.D 28.B 29.I)30.A二、填空题1.集合；线性；树形；图状2.图状3 p-next=head;4.p-next=head;5.p-next=head；6.hs=s；7.r-next=s8.r-next=s；r=s；9.r=f10.3；511.1；212.213.1114.101 5.先序；中序；后序1 6.深度优先；广度优先1 7.物理(存储)1 8.图状(网状)19.gdbeihfca20.2n

44、-l2 1.错误2 2.顺序存储链式存储2 3.深度优先广度优先2 4.关键字相等的记录三、综合应用题1.(1)_(2)dbeac(3)2.(1)(2)(3)edbcae=l,a=2,d=3,c=4,b=53.(1)(2)ASL=(1x1+2x24-3x3+4)/7=18/7(2)5,6,7,8,9,10,17,18,19,216.初始树堆(2)10 2,52,42,82,16,67,32,57(2)2n-l 不一定唯一四、程序填空题(每空2 分，共 16分)1.(1)(2)(3)(4)(5)low=highmidamid.keyleft(4)p=p-right(5)p3.(1)malloc(

45、sizeof(struct node)(2)rear-next=p(3)p4.(1)front=rear(2)p-next(3)retum(x)数据结构(本)期末综合练习三一、单项选择题1.(B)是性质相同的数据元素的集合，是数据的子集。A、数据元素 B.数据对象 C.数据结构 D.数据项2.从 n 个数中选取最大元素(CA.基本操作是数据元素间的交换 B.算法的时间复杂度是0(/)C.算法的时间复杂度是0(n)D.需要进行(n+1)次数据元素间的比较3.设链表中的结点是NODE类型的结构体变量，且有NODE*p：为了申请一个新结点，并由p 指向该结点，可用以下语句(A)。A.p=(NODE*

46、)malloc(sizeof(NODE);B.p=(*NODE)malloc(sizeof(NODE);C.p=(NODE)malloc(sizeof(p);D.p=(NODE*)malloc(sizeof(p);4.设head为非空的单向循环链表头指针,p 指向链表的尾结点，则满足逻辑表达式(D)的值为真。A.p-next=NULL B.p=NULLC.p-next=head D.p-next=head5.设顺序存储的线性长度为n,要在第i 个元素之前插入一个新元素，按课本的算法当上(D)时，移动元素次数为2A.n/2 B.n C.1D.n-16.设顺序存储的线性表长度为n,要删除第i 个元

47、素，按课本的算法，当 i=(C)时,移动元素的次数为3A.3 B.n/2 C.n-3 D.37.一个栈的进栈序列是1,2,3,4,则栈的不可能的出栈序列是(B)(进出栈操作可以交替进行)A.3,2,4,1 B.1,4,2,3C.4,3,2,1D.3,2,1,48.一个栈的进栈序列是a,b,c,d,则栈的不可能的出栈序列是(A)oA.adbcB.beadC.cbadD.deba9.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和 rear分别为链队列的头指针和尾指针。设 p 指向要入队的新结点(该结点已被赋值)，则入队操作为(A)oA.rear-ne

48、xt=p;rear=p;B.rear-next=p;p=rear;C.p=rear-next;rear=p;D.rear=p;rear-next=p;1 0.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成,front和 rear分别为链队列的头指针和尾指针，要执行出队操作，用 x 保存出队元素的值，p 为指向结点类型的指针，可执行如卜 操作：p=front-next;x=p-data;然后指行(B)。A.front=p-next;B.front-next=p-next;C.front=p;D.front-next=p;1 1.以下说法不正确的是（C）。A.顺序

49、栈中，栈满时再进行进栈操作称为“上溢”B.顺序栈中，栈空时再作出栈栈操作称为“下溢”C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空1 3 .设有一个2 0 阶的对称矩阵A,采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A的第 个元素为a”，数组b的下标从1 开始），则矩阵元素a&5 在一维数组b中的下标是（D ）。A.3 0 B.2 8 C.4 0 D.3 31 4 .设有一个1 0 阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素

50、为au,数组b的下标从1 开始），则矩阵元素 a s.3 对应一维数组b的数组元素是（C ）。A.b 1 8 B.b 8 C.b 1 3 D.b 1 0 1 5 .深度为5的完全二叉树第5 层上有4个结点，该树一共有（D ）个结点。A.2 8 B.3 0 C.3 1 D.1 91 6 .深度为5的完全二叉树共有2 0 个结点，则第5 层 上 有（C ）个结点（根所在结点为第一层）。A.3 B.8 C.5 D.61 7 .已知一个图的所有顶点的度数之和为m,则 m一定不可能是（D ）。A.4 B.8 C.1 2 D.91 8 .已知一个图的所有顶点的度数之和为m,且 m是以下4中情况之一，则 m