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

1 / 36 数据结构期末综合练习2018 年 12 月期末练习一一、单项选择题1. 一种逻辑结构在存储时（）。A 只要存储数据元素间的关系 B 只能采用一种存储结构 C 可采用不同的存储结构 D 只要存储数据元素的值2同一种逻辑结构（）。 A只能有唯一的存储结构 B可以有不同的存储结构C只能表示某一种数据元素之间的关系 D以上三种说法均不正确3 . 对链表 ,以下叙述中正确的是（）。A不能随机访问任一结点 B结点占用的存储空间是连续的C插入删除元素的操作一定要要移动结点 D 可以通过下标对链表进行直接访问4链表所具备的特点是（）。A可以随机访问任一结点 B占用连续的存储空间C插入删除元素的操作不需要移动元素结点 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 按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能输出序列是（）（进栈出栈可以交替进行）。A 8，6，2， 4 B 8，4，2，6 C6，2，4，8 D 8，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 。 D f=fnext 。x=fdata 12算法的时间复杂度与（）有关。A 所使用的计算机 B与计算机的操作系统C与算法本身 D与数据结构13设有一个20 阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 36 页2 / 36 储到一维数组B 中（数组下标从1 开始），则数组中第38 号元素对应于矩阵中的元素是（）。Aa10,8 Ba7,6 Ca9,2 Da8,5 14设有一个长度为n 的顺序表，要删除第i 个元素需移动元素的个数为（）。 A n-i+1 Bn-i Cn-i-1 Di 15在 C语言中，分别存储“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 D n-2 18从一个栈顶指针为top 的链栈中删除一个结点时，用变量x 保存被删结点的值，则执行（）。 A x=top-data。 top=top-next。 Bx=top-data。Ctop=top-next。 x=top-data。 Dtop=top-next。 x=data 。19在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为（）。 A i/2.0Bi/2向下取整C 2i+1 Di+2 20在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。 A r=f-next。 Br=r-next。 C f=f-next。 D f=r-next。21设一棵哈夫曼树共有2n+1 个结点，则该树有（）个非叶结点。 A n Bn+1 C n-1 D2n 22一个栈的进栈序列是a， b，c，d，e，则栈的不可能输出序列是（）（进栈出栈可以交替进行）。Adceab Bedcba C decba D abcde 23一棵完全二叉树共有4 层，且第4 层上有 2 个结点，该树共有（）个非叶子结点( 根为第一层 ) 。 A 5B4C3D9 24有一个长度为10 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A26/10 B 29/10 C29/9 D31/10 25如图 1 所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 A abedfc Bacfebd Caebcdf D aebcfd 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 36 页3 / 36 图 1 26排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。 A冒泡 B直接插入 C折半插入 D选择排序27一组记录的关键字序列为（56，30,89 ，66，48，50，94,87,100 ），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。 A 30，50,48 ，56，66，89， 94,100,87B 50 ，30,48 ，56，66，89，94,87,100 C48，30,50 ，56，66，89， 94,87,100D 50，30,48 ，66，56，89，94,87,100 28设有一个10 阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B 中（数组下标从1 开始），则矩阵中元素A8,5在一维数组B 中的下标是（）。A33 B 32 C85 D 41 29线性表以（）方式存储，能进行折半查找。 A 关键字有序的链接B顺序 C关键字有序的顺序D数组C多对多 D每一个元素都有一个直接前驱和一个直接后继30在一个无向图中，所有顶点的度数之和等于边数的（）倍。A 3 B2.5 C 1.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号位置，其结果是新表中第25 号元素的值为 _ 。6根据数据元素间关系的不同特性，通常可分为集合、线性、四类基本结构。7在双向链表中，要在p 所指的结后插入q 所指的结点 (设 q 所指的结点已赋值)，其中所用的一条语句（p-next） -prior=q ；的功能是使P 所指结点的_指向q 。8要求在n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次b d f e c a 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 36 页4 / 36 数和算法的时间复杂度分别为_和 _ 。9设有一个带头结点的，头指针为head的单向链表， p 指向表中某一个结点，且有p-next= =NULL, 现要删除头结点，并使该单向链表构造成单向循环链表，通过操作 head=head-next。 _。10在一个单向链表中p 所指结点之后插入一个s所指向的结点时，应执行_ _ 和p-next=s。的操作。11从一个栈顶指针为top 的链栈中删除一个结点时，用d 保存被删结点的值，可执行_。(结点的指针域为next,数据域为data) 12在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、。13 循环链队列中，设front 和 rear分别为队头和队尾指针，(最多元素为MaxSize, 采用少用一个元素的模式),判断循环链队列为满的条件为_ 。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 分别为队头和队尾指针，则插入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) 进行直接插入排序时，当把第7 个记录65插入到有序表时，为寻找插入位置需比较_次。376542189 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 36 页5 / 36 三、综合题1（ 1）对给定权值3，1 ，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层) (2) 求树的带权路径长度。（3）链接存储上述哈夫曼树，结点中共有多少个个指针域为空,说明理由 . 2 (1)以 2，3，4，7，8， 9 作为叶结点的权，构造一棵哈夫曼树( 要求每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。(2) 一棵哈夫曼树有n 个叶结点，它一共有多少个结点？简述理由？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）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。A1 A2 A4A7 A5 A9 A8 A3 A6 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 36 页6 / 36 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) (1)说出进行折半查找成功查找到元素120 需要进行多少次元素间的比较？(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？（ 3）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) 四、程序填空题1以下函数为直接选择排序算法，对a1,a2, an中的记录进行直接选择排序，完成程序中的空格typedef struct int key 。NODE 。void selsort(NODE a,int 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)_。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 36 页7 / 36 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 。 /*建立头结点 */ 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）。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 36 页8 / 36 期末复习一答案一、单项选择题1 C 2 B3 A4 C5 A 6 D7 C8 A9 D10 D 11 C 12 C 13 C14 B15 D16 C17 C 18 A19 B 20 C21 A22 A 23 B24 B25 C 26C27B 28 A29C 30 D 二、填空题1物理（存储）2后进先出、先进先出3乘法 O(n3) 4图状（网状）586树形图状7 直接前驱的左指针8n-1,O(n) 、9 p-next= head。10s-next=p-next。11d=top-data。top=top-next 。12左指针右指针13front= =(rear+1)%MaxSize 14 2i 2i+1 1534 16h=s。1713 18r-next=s 。191 2012 21215347896 22行下标、列下标、非零元素值23主关键字24 3 三、综合应用题1. (1) 6452314984413 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 36 页9 / 36 图 4 （2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58 (3) 共 11 个结点 ,22 个指针域 ,除根结点外 ,每个结点对应一个指针域.,共 10 个指针域非空 ,故有 22-10=12 个空指针域 , 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) 8 9 5 9 7 2 4 3 33 18 15 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 36 页10 / 36 图 6 4(1)初始序列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 4 2 1 5 6 3 8 9 3.5 9 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 页，共 36 页11 / 36 图 7 (2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。 (3) 3 次6 (1)3 次 (2)4 次 (3) 图 8四、程序填空题1（ 1） n-1 （2）n （3）k=j （4）ai=ak （5）ak=temp 96 75 98 130 105 85 50 110120 60 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 36 页12 / 36 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) 期末练习二一、单项选择题1 . 结构中的元素之间存在一对多的关系是（）。A 集合 B线性结构 C 树形结构 D 图状结构2在 C语言中，顺序存储长度为3 的字符串，需要占用（）个字节。A4 B3 C6 D 12 3 . 对不带头结点的单向链表, 判断是否为空的条件是（）（设头指针为head）。Ahead=NULL Bhead-next= =NULL Chead-next= =head Dhead =NULL 4串函数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 B43512 C45321 D 54321 8设一棵哈夫曼树共有n 个非叶结点，则该树有（）个叶结点。A n Bn+1 C n-1 D2n 9一个队列的入队序列是2，4，6，8，按该队列的输出序列使各元素依次入栈，该栈的可精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 36 页13 / 36 能输出序列是（）。 A8，6，4，2 B 6，2，4，8 C8，4，2， 6D8， 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在一个链队中，假设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 D 23 13设有一个25 阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中（数组下标从1 开始），则矩阵中元素a7,6在一维数组B 中的下标是（）。A34 B14 C26 D 27 14在一个无向图中，所有顶点的度数之和等于边数的（）倍。 A 3 B 2.5 C 1.5 D2 15. 以下程序段的结果是 c 的值为（）。char a5=“1236789”, int *p=a, int c=0。 while(*p+)c+。 A8, B7 C10 D12 16已知如图1 所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A V1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7C V1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 图 1 V6V7V1V2V3V8V4V5精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 36 页14 / 36 17一棵有23 个结点，采用链式存储的二叉树中，共有（）个指针域为空。 A 24B25C23D45 18已知如图2 所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 Aabcedf Babcefd Caebcfd Dacfdeb 图 2 19在一棵二叉树中，若编号为i 的结点是其双亲结点的左孩子，则双亲结点的顺序编号为（）。 A i/2B 2i-1 C2i+1 Di/2-1 20对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列。按层次 B 后序 C中序 D 前序21设一棵哈夫曼树共有2n+1 个叶结点，则该树有（）个叶结点。 A n-1 Bn Cn+1 D2n 22在有序表 2 ，4，7，14，34， 43，47，64， 75，80，90，97，120 中，用折半查找法查找值 80 时，经（）次比较后查找成功。A 4 B2C 3 D523已知如图3 所示的一个图，若从顶点a 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 A abecdf Bacfebd Caebcfd Daedbfc 图 3 24有一个长度为9 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的b d f e c a b d f e c a 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 36 页15 / 36 平均比较次数为（）。A25/10 B25/9 C 20/9 D17/9 25已知如图4 所示的一个图，若从顶点B出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（）。A.BADEHCFGB.ADEHCGFC.BADECHFG D.BADEHCFG图 4 26排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。A 冒泡 B直接插入 C折半插入 D 选择排序27一组记录的关键字序列为（46，38，56，40，79， 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 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， 46，73，77，78，89，99，106 中，用折半查找值 43 时，经（）次比较后查找成功。A6 B 3 C8 D 4 30排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（）排序。 A 归并 B 插入 C 快速 D 选择二、填空题1. 本书中介绍的树形结构和_ 属非线性结构。 2在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_、右指针。3设有一个长度为18 的顺序表，要在第4 个元素之前插入2 个元素（也就是插入元素作为新表的第5 个和第 4 个元素），则最少要移动元素的个数为（）。F GA B C HDE 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 36 页16 / 36 4一棵二叉树中顺序编号为i 的结点，若它存在左、右孩子，则左、右孩子编号分别为_ _、_ _。5在双向链表中，要删除p 所指的结点，可以先用语句（p-prior）-next=p-next ；然再用语句 _。 6串的两种最基本的存储方式是_ _和 _ _。7在一个单向链表中p 所指结点之后插入一个s 所指向的结点时，应执行s-next=p-next。和 _的操作 . 8一棵有2n-1 个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 _个叶结点。9 一 个 栈 和 一 个 队 列 的 输 入 序 列 都 为abcdefg， 它 们 可 能 有 相 同 的 输 出 序 列 吗 ？_。（若没有则回答没有，若有则写出序列,进栈出栈可以交替进行）。10对于一棵具有n 个结点的二叉树，其相应的链式存储结构中共有_个指针域为空。11.从一个栈顶指针为top 的链栈中取栈顶元素，用d 保存栈顶元素的值，可执行_。(结点的数据域为data) 12_遍历二叉排序树可得到一个有序序列。13. 循环链队列中，设front 和 rear分别为队头和队尾指针，(最多元素为MaxSize,), 判断循环链队列为空的条件是_为真 。14如图 5 所示的二叉树，其后序遍历序列为。图 5 15. 对稀疏矩阵进行压缩存储,可采用三元组表，设a是稀疏矩阵A 相应的三元组表类型（结构体类型）变量，a 中的一个成员项是三元组类型的结构体数组data，按书中定义，若a.data0.i=2 。a.data0.j=3 。a.data0.v=16 。 它提供的 A 数组的相关信息有_ 16如图 6 所示的二叉树，其先序遍历序列为_ _。e f g i b a c h d g a b d e c 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 36 页17 / 36 图 6 17设有一棵深度为5 的完全二叉树，该树共有20个结点 ,第五层上有个叶结点。（根所在结点为第1 层）18图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_的。 (回答正确或不正确 ) 19中序遍历 _树可得到一个有序序列。20二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是_的。 (回答正确或不正确) 21如图 7 所示的二叉树，其后序遍历序列为_。图 7 22对记录序列排序是指按记录的某个关键字排序，记录序列按_排序结果是唯一的。23 .给 定 一 组 权重 值 ，构 造 哈 夫 曼树 ， 哈 夫曼树 的 高 度 一定 是 唯 一的，这 种 说 法是_的。 (回答正确或不正确) 24按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题 1. (1) 说明什么是顶点活动网(AOV 网)和拓扑序列（2）设有向图G 如下，写出3 种拓扑序列，（3）在图 G 中增加一条边，使图G 仅有一条拓扑序列376542189 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 36 页18 / 36 图 8 2设查找表为 (16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n 个元素进行冒泡排序要进行多少趟冒泡？第j 趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点 ) 3如下是一棵二叉排序树，A1,A2, A9 代表 1，2，3,9 中各个不同数字，（ 1）给出对该树中序遍历的结果（ 2） A3,A5,A7 的值各为多少？（ 3）请在该树中再插入一个结点9 .5作为叶结点，并使它仍然是一棵二叉排序树图 9 4 (1) 设有查找表 5,14,2,6,18,7,4,16,3, 依次取表中数据，构造一棵二叉排序树。（ 2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。A1 A2 A4 A7 A5 A9 A8 A3 A6 a b c d 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 36 页19 / 36 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以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p 指向查到的树结点，不成功p 指向为NULL ）完成程序中的空格typedef struct Bnode int key 。struct Bnode *left 。struct Bnode *right 。 Bnode。Bnode *BSearch(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)_) 。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 36 页20 / 36 3 . 设有一个头指针为head 的不带头结点单向链表，p、q 是指向链表中结点类型的指针变量， p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句 (1).使该单向链表成为单向循环链表 (2)插入结点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)_ 答案一、单项选择题1 C2 A 3 A 4 D 5 D 6 A 7 B 8 B9 A 10 A 11 B 12 C13 D14 D 15 B 16 A 17 A 18 B 19 A 20 C 21 C 22 A 23D24B 25 C 26C 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。8n9abcdefg 10n+1 11d=top-data。12中序13front= =rear 14gdbeihfca 15A 的第一个非零元素的下标为2，3 ，元素为16 16 abdefcg 175 18正确19二叉排序20不正确21519876432 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 36 页21 / 36 22主关键字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) 图 10 2(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) 图 11 7 15 20 64 16 53 7 15 20 64 16 53 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 36 页22 / 36 (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) 图 13 (2)中序遍历中序 2，3，4， 5，6，7，14，16，18 5（1）2 4 6 16 7 3 18 5 14 5 3 4 1811 7 6 3 3 1 2 2 4 6 16 7 3 18 5 14 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 36 页23 / 36 wpl1=45 （2）图 15 wpl2=45 6（ 1）答wpl1=45 四、程序填空题1（ 1） NULL （2）k （3）p=p-left （4）p=p-right （5）p 2187 11 3 1 2 3 3 4 6 5 5 3 4 1811 7 6 3 3 1 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 36 页24 / 36 （1）&a （2）d next=NULL （3）p-data （4）p=p-next （5）p!=NULL 3. (1)q-next!=NULL (2) p=p-next 。(3)q-next=s 。4（1）Postorder(BT-left) （2）Postorder(BT-right) （3） printf(“ %c ”,BT-data) 期末练习三一、单项选择题1. 数据结构在计算机内存中的表示是指 ( ) 。A 数据元素之间的关系 B数据的存储结构 C 数据元素的类型 D数据的逻辑结构2. 在数据结构和算法中，与所使用的计算机有关的是（）。 A 数据元数间的抽象关系 B数据的存储结构 C 算法的时间复杂度D数据的逻辑结构3 . 结构中的元素之间存在多对多的关系是（）。A 集合 B线性结构 C 树形结构 D 图状结构4 . 对顺序表 , 以下叙述中正确的是 ( )。A 用一组地址连续的存储单元依次存放线性表的数据元素B 各个数据元素的首地址是连续的 C 数据元素不能随机访问D 插入操作不需要移动元素5. 设有一个长度为20 的顺序表，要