数据结构((本)期末综合练习(月).pdf

《数据结构((本)期末综合练习(月).pdf》由会员分享，可在线阅读，更多相关《数据结构((本)期末综合练习(月).pdf（36页珍藏版）》请在三一文库上搜索。

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

2、储空间 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

3、 按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能 输出序列是（）（进栈出栈可以交替进行）。 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算法的时间复杂度与（）

4、有关。 A 所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构 13设有一个20 阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存 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 分别指向表中两个相邻的结

5、点，且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 。

6、 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一棵完全二叉树共有

7、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 3 / 36 图 1 26排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比 较（要求比较次数尽量少），然后将其放入已排序序列的正

8、确位置的方法是（）。 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 开始），则

9、矩阵中元素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

10、的 顺 序 表 , 第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 所指结点的_指向

11、 q 。 8要求在n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次 b d f e c a 4 / 36 数和算法的时间复杂度分别为_和 _ 。 9设有一个带头结点的，头指针为head的单向链表， p 指向表中某一个结点，且有 p-next= =NULL, 现要删除头结点，并使该单向链表构造成单向循环链表，通过 操作 head=head-next。 _。 10在一个单向链表中p 所指结点之后插入一个s所指向的结点时，应执行_ _ 和 p-next=s。的操作。 11从一个栈顶指针为top 的链栈中删除一个结点时，用d 保存被删结点的值，可执行 _。(结点的指针域为nex

12、t,数据域为data) 12在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、 。 13 循环链队列中，设front 和 rear分别为队头和队尾指针，(最多元素为MaxSize, 采用少用一 个元素的模式),判断循环链队列为满的条件为_ 。 14一棵二叉树中顺序编号为i 的结点，若它存在左、右孩子，则左、右孩子编号分别为 _、_。 15对稀疏矩阵进行压缩存储,可采用三元组表，一个6行 7 列的稀疏矩阵A 相应的三元组 表共有 8 个元素 ,则矩阵 A 共有 _个零元素。 16向一个栈顶指针为h 的链栈中插入一个s所指结点时，可执行s-next=h。和 _。 17.一棵有 20个

13、结点的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在 查找 表中 ，

14、通 过 记 录的 某关 键字 能唯 一地 确定 一个 记录 ，该 关键 字称 为 _。 24在对一组记录(55,39,97,22,16,73,65,47,88) 进行直接插入排序时，当把第7 个记录65 插入到有序表时，为寻找插入位置需比较_次。 3 76 5 4 2 1 8 9 5 / 36 三、综合题 1（ 1）对给定权值3，1 ，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层) (2) 求树的带权路径长度。 （3）链接存储上述哈夫曼树，结点中共有多少个个指针域为空,说明理由 . 2 (1)以 2，3，4，7，8， 9 作为叶结点的权，构造一棵哈夫曼树( 要求每个结点的左子树根结

15、点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。 (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）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交 换元素的过程，要求以

16、升序排列） （ 2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 A1 A2 A4 A7 A5 A9 A8 A3 A6 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)说出进行折半查找成

17、功查找到元素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 。idata。 while （q-next!=NULL ）q=q-next 。 _(1)_ q=p。 p=

18、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）。 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

19、 A 23 B24 B25 C 26C27B 28 A29C 30 D 二、填空题 1物理（存储） 2后进先出、先进先出 3乘法 O(n 3) 4图状（网状） 58 6树形图状 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 三

20、、综合应用题 1. (1) 645 23 14 9 8 44 13 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 1

21、0 / 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 12 13 6 56 79 38 40 84 46 84 79 38 40 46 56 56 79 38 40 46 79 38 40 84 84 56 46 11 / 36 图 7 (2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二

22、叉排：若它的左子树 非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子 树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。 左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。 (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 110 120 60 12 / 36 2 （1）p （2）q=p （3）(NODE*)malloc(sizeof(NODE) （4）p （5）q=p 3. (1

23、) 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

24、 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，则栈

25、的不可能输出序列是（）（进栈出栈可 以交替进行）。 A12345 B43512 C45321 D 54321 8设一棵哈夫曼树共有n 个非叶结点，则该树有（）个叶结点。 A n Bn+1 C n-1 D2n 9一个队列的入队序列是2，4，6，8，按该队列的输出序列使各元素依次入栈，该栈的可 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-n

26、ext。 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设有一

27、个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 V1V

28、2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7 C V1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 图 1 V6V7 V1 V2V3 V8 V4V5 14 / 36 17一棵有23 个结点，采用链式存储的二叉树中，共有（）个指针域为空。 A 24B25C23D45 18已知如图2 所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得 到的一种顶点序列为（）。 Aabcedf Babcefd Caebcfd Dacfdeb 图 2 19在一棵二叉树中，若编号为i 的结点是其双亲结点的左孩子，则双亲结点的顺序编号为 （）。 A i/2B 2i-1

29、 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 D5 23已知如图3 所示的一个图，若从顶点a 出发，按深度优先搜索法进行遍历，则可能得到 的一种顶点序列为（）。 A abecdf Bacfebd Caebcfd Daedbfc 图 3 2

30、4有一个长度为9 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 b d f e c a b d f e c a 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折半插

31、入 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，

32、 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

33、个元素），则最少要移动元素的个数为（）。 F G A B C H DE 16 / 36 4一棵二叉树中顺序编号为i 的结点，若它存在左、右孩子，则左、右孩子编号分别为 _ _、_ _。 5在双向链表中，要删除p 所指的结点，可以先用语句（p-prior）-next=p-next ；然 再用语句 _。 6串的两种最基本的存储方式是_ _和 _ _。 7在一个单向链表中p 所指结点之后插入一个s 所指向的结点时，应执行s-next=p- next。 和 _的操作 . 8一棵有2n-1 个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 _个叶 结点。 9 一 个 栈 和 一 个 队 列 的

34、输 入 序 列 都 为abcdefg， 它 们 可 能 有 相 同 的 输 出 序 列 吗 ？ _。 （若没有则回答没有，若有则写出序列,进栈出栈可以交替进行）。 10对于一棵具有n 个结点的二叉树，其相应的链式存储结构中共有_个指针域为 空。 11.从一个栈顶指针为top 的链栈中取栈顶元素，用d 保存栈顶元素的值，可执行 _。(结点的数据域为data) 12_遍历二叉排序树可得到一个有序序列。 13. 循环链队列中，设front 和 rear分别为队头和队尾指针，(最多元素为MaxSize,), 判断循环 链队列为空的条件是_为真 。 14如图 5 所示的二叉树，其后序遍历序列为。 图 5

35、 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 17 / 36 图 6 17设有一棵深度为5 的完全二叉树，该树共有20个结点 ,第五层上有个叶结点。 （根所在结点为第1 层） 18图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_

36、的。 (回答正 确或不正确 ) 19中序遍历 _树可得到一个有序序列。 20二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩 子的值。这种说法是_的。 (回答正确或不正确) 21如图 7 所示的二叉树，其后序遍历序列为_。 图 7 22对记录序列排序是指按记录的某个关键字排序，记录序列按_排序结果是唯一 的。 23 .给 定 一 组 权重 值 ，构 造 哈 夫 曼树 ， 哈 夫曼树 的 高 度 一定 是 唯 一的，这 种 说 法是 _的。 (回答正确或不正确) 24按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法 是稳定的，否则是不稳定的

37、。 三、综合题 1. (1) 说明什么是顶点活动网(AOV 网)和拓扑序列 （2）设有向图G 如下，写出3 种拓扑序列， （3）在图 G 中增加一条边，使图G 仅有一条拓扑序列 3 76 5 4 2 1 8 9 18 / 36 图 8 2设查找表为 (16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n 个元 素进行冒泡排序要进行多少趟冒泡？第j 趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元 素作为树结点 ) 3如下是一棵二叉排序树，A1,A2, A9 代表 1，2

38、，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 19 / 36 5 (1) 设有查找表 17，26，14，16，15， 30，18，19，28 ，依次取表中数据构造一棵二叉 排序树

39、. (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 *l

40、eft 。 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)_) 。 20 / 36 3 . 设有一个头指针为head 的不带头结点单向链表，p、q 是指向链表中结点类型的指针 变量， p指向链表中结点a,

41、（设链表中没有结点的数据域与结点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 23

42、D24B 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 21 / 36 22主关键字 23不正确 24关键字相等的记录 三、 综合应用题 1 (1)原

43、序列 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 22 / 36

44、(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 18 11 7 6 3 3 1 2 2 4 6 16 7 3 18 5 14 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 2 18

45、7 11 3 1 2 3 3 4 6 5 5 3 4 18 11 7 6 3 3 1 2 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