数据结构本期末综合练习11月

1、数据结构（本）期末综合练习2015年 11月综合练习一一、单项选择题1. 对稀疏矩阵进行压缩存储 个零元素，其相应的三元组表共有 （ C ） 8B 80 C 7对稀疏矩阵进行压缩存储 , 可采用三元组表， 三元组表共有8A2.A3.字符串( A )A. “ 21AB”4. 程序段char a =, 可采用三元组表，一个 10 行 8 列的稀疏矩阵 A 共有 73 个元素。D 1010行8列的稀疏矩阵A,其相应的 个零元素。 D一个）74的子串。C.6个元素，矩阵A共有(CB 72 C 是“ abcd321ABCD” B.“ abcD”abdcacdef ”char *p=a; int n=0;

2、while( *p!=0 ' ) n+; p+;A. 6 B.8 C. 7 D.95. 栈和队列的共同特点是( A A 都是操作受限的线性结构 C 都是先进后出 D）。10aBCD”D.321a”结果中 ,n 的值是（）。元素都可以随机进出 都是先进先出6. 10,6,2,1 按顺序依次进栈，该队列的可能输出序列是（ （ 进栈出栈可以交替进行） 。A 6,10,1,2 B 2,10,6,1 C6,1,10,17. 在一个链队中，假设 f 和 r 分别为队头和队尾指针， 所指结点赋值A. f->next=p; f=p;C8.）。D p 指向一个新结点 , 要为结点 px, 并入队的

3、运算为 p->data=x; p->next=NULL; B r->next=p;r=p; r=p; p->next=r; D p->next=f;f=p;1,6,10,2B ）。( BABCD对一个栈顶指针为 top 的链栈进行出栈操作，）。 e= top->next; top->data=e; e=top->data; top=top->next; top=top->next; e=top->data; top=top->next; e=data;数据结构中，与所使用的计算机无关的是数据的 逻辑与存储 D. 有关。用变

4、量 e 保存栈顶元素的值 ，则执行9.A. 逻辑 B. 存储10. 算法的时间复杂度与A. 算法本身C. 算法的程序设计 11顺序表所具备的特点之C.( A )物理结构。A )B.D.所使用的计算机 数据结构）。A 可以随机访问任一结点 B 不需要占用连续的存储空间C 插入元素的操作不需要移动元素 D 删除元素的操作不需要移动元素 12在一个单向链表中 , 在 p 所指结点之后插入一个 s 所指的结点时，可执行s->next=p->next;和（ D ）。A . p= s;B.p->next=s->next;C. p=s->nextD.p->next=s;1

5、3. 数据元素是数据的基本单位，它（C）。A .只能有一个数据项组成B .至少有二个数据项组成C 可以是一个数据项也可以由若干个数据项组成D 至少有一个数据项为指针类型14. 一种逻辑结构在存储时 （ C ）。A 只要存储数据元素间的关系 B 只能采用一种存储结构C.可采用不同的存储结构D只要存储数据元素的值15. 设有头指针为 head的非空的单向链表,指针p指向其尾结点,要使该单向链表成为 单向循环链表 ,则可利用下述语句（ C ）。A p =head; B p=NULL; C p->next =head; D head=p;16. 单向链表所具备的特点是 （ C ） 。A.可以随机

6、访问任一结点B.占用连续的存储空间C. 插入删除不需要移动元素 D. 可以通过某结点的指针域访问其前驱结点17. 在线性表的顺序结构中，以下说法正确的是（ C ）。A 逻辑上相邻的元素在物理位置上不一定相邻B 数据元素是不能随机访问的C 逻辑上相邻的元素在物理位置上也相邻D 进行数据元素的插入、删除效率较高18. 数据结构在计算机内存中的表示是指 （ B ）A 数据元素之间的关系B 数据的存储结构C 数据元素的类型D数据的逻辑结构19. 对链表 , 以下叙述中正确的是（ A ）。A 不能随机访问任一结点B结点占用的存储空间是连续的C 插入删除元素的操作一定要要移动结点 D 可以通过下标对链表进

7、行直接访问20.下面关于线性表的叙述中, 错误的是 （ B ）。A .线性表采用顺序存储, 必须占用一片连续的存储空间。B.线性表采用顺序存储, 进行插入和删除操作 , 不需要进行数据元素间的移动。C.线性表采用链式存储，不必占用连续的存储空间。D.线性表采用链式存储，进行插入删除操作，不需要移动元素21.设有一个长度为 35的顺序表，要在第 5个元素之前插入 1个元素（也就是插入元素作为新表的第 5个元素），则移动元素个数为（ B）。A. 30B. 31C. 5 D. 622 .设有一个长度为 18的顺序表，要在第 5个元素之前插入 1个元素（也就是插入元素 作为新表的第 5个元素），则移动

8、元素个数为（ B ）。A 15 B 14 C. 5 D 623.设有一个长度为 40的顺序表，要删除第10个元素（下标从1开始）需移动元素的个数为（ C ）。A11B 10 C 30 D3124 设有一个长度为25 的顺序表,要删除第10个元素(下标从 1开始)需移动元素的个数为(C )。A10 B 17 C 15 D1625 设有一个 25 阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中(数组下标从 1 开始),则矩阵中元素 a7,5 在一维数组 B 中的下标是( C )。A 2526 设有一个B 24C 26D 2718阶的对称矩阵 A,采用压缩存储的方

9、式，将其下三角部分以行序为主序存储到一维数组b中(数组下标从i开始)，则矩阵中元素 aio,8在一维数组b中的下标是( D )。A62,B 63 C 5i D 5327线性表在存储后 , 如果相关操作中有要求 :利用已知的指向某结点的指针或序号,访问该结点的前驱结点，则采用( A )的存储方式是不可行的。A 单向链表 B 双向链表 C 单向循环链表 D 顺序表28在一个尾指针为rear的不带头结点的单循环链表中, 插入一个s 所指的结点, 并作为第一个结点,可执行snext=rearnext ; 和( D)。A rear next= snext;B rear =snext;C rear=s;D

10、 rearnext=s;29在一棵二叉树中,若编号为的结点存在左孩子,i 结点的左孩子的顺序编号为(B )。Ai/2.0B2*iC 2*i+1Di+230在一棵二叉树中， 若编号为 i5 的结点是其双亲结点的右孩子， 则双亲结点的顺序编 号为( D )。A30 B 8C3iD 7二、填空题1. 广义表 ( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是 _ 6。2. 结构中的元素之间存在一对多的关系是_树形 结构。3. 数据结构中，数据元素之间的抽象关系称为 逻辑 结构。4. 结构中的元素之间存在多对多的关系是_图状 结构 。5. 栈的操作特点

11、是后进 _先出 。6. 循环队列的最大存储空间为MaxSize ,若队头指针front,队尾指针rear,采用少用一个存储空间以有效地判断栈空或栈满，队空的判定条件为_ rear=front 为真 7. 广义表( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 的表头是(b,a,c) 。8. 广义表 ( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是 6。9. 设有一个长度为18的顺序表， 第8号元素到第18号元素依次存放的值为8,9,18.某人想要删除第 8 号元素, 程序中他的做法是用语句for(i=18;

12、i<=9;i-)ai-1=ai;即从第 18号元素开始 , 直到第 9号元素,每个元素依次向前 (左)移动1个位置.事实上这 样做是错误的 . 其结果新表中第 9号元素的值为 _ 18 。10要求在 n 个数据元素中找值最大的元素, 其基本操作为元素间的比较。 算法的时间复杂度为 O(n)11. 一棵二叉树 ,有1个2度结点, 2个1度结点,则该树共有 _ 5个结点。12. 棵有8个叶结点的二叉树，其1度结点的个数为3，则该树共有 _ 18个结点。13. 设有一棵深度为 5的完全二叉树，该树共有21个结点，第5层上有 6个结点。（根所在结点为第1层）14. 对于一棵具有n个结点的二叉树，

13、其相应的链式存储结构中共有_ n+1个指针域为空。15中序遍历 二叉排序树 树可得到一个有序序列。16. 对一组记录（5，8，9，2，12，7, 56，44，39）进行直接插入排序（由小到大排序），当把第6个记录7插入有序表，为寻找插入位置需比较_ 4次。17. 序列12,10,13,11,16,14,采用冒泡排序算法，经一趟冒泡后，序列的结果是 10，12，11,13，14，16。（按升序排序）18. 设有一棵深度为 6的完全二叉树，第 6层上有3个结点，该树共有 _ 34个结点。 （根所在结点为第1层）19. 对16个元素的序列用冒泡排序法进行排序，共需要进行15趟冒泡。20. 一棵有16

14、个叶结点的哈夫曼树，则该树共有_ 31个结点。21. 一棵有16个叶结点的哈夫曼树，则该树共有15个非叶结点。22. 20个元素进行冒泡法排序，通常第 6趟冒泡要进行辿次元素间的比较。23. 在对一组记录（40，24，82，9，1，78，46，31，69）进行直接插入排序（由小到大排序），当把第7个记录46插入到有序表时，为寻找插入位置需比较 3次。24. 对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵 A共有38个零元素，其相应的三元组表共有 4_个元素。三、综合题1.设有序表为（5, 8, 14, 15, 33, 51,61, 73, 81,82, 93）,元素的序号依次为

15、1,2,3,，11.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示）（2） 说明成功查找到元素33需要经过多少次比较？（3）在等概率条件下，给出成功查找的平均查找长度（1 ）图 451148151561 8283373934 次(3) ( 1+2*2+3*4+4*4)/11=33/11=32.设数据集合 a=1,5,8,3,10,7,13,9(1) 依次取a中各数据，构造一棵二叉排序树。(2) 对该二叉树进行查找，成功查找到7要进行多少次元素间的比较?(3) 给出对该二叉树中序遍历的序列。(1) 图 54 次中序遍历 1, 3,5 ,7,8,9 , 10 , 133.(

16、1) 如图1所示，若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出可能得到的一种顶点序列。(1) acdbfeh(2) 152364 或 152634 或 1562344.设有序表为(30, 48, 58, 70, 78, 79, 90),元素的序号依次为 1,2,3,7.(1) 画出对上述查找表进行折半查找所对应的判定树(树中结点用序号表示)(2) 给出有序表中经3次比较成功查找到的所有元素(3) 说明不成功查找元素59需要经过多少次比较？(1 )图 67048793058789030 5878905.设数据集合a=7,4,9,8,6,5,3,(2) 对该二叉树进行查找，成功查找

17、到依次取a中各数据，构造一棵二叉排序树。5要进行多少次元素间的比较？(3) 给出对上述二叉排序树进行中序遍历的序列(1) 图 7(3) 3,4,5,6,7,8,9 6.(1) 如图3所示，若从顶点a出发，首先经过c按广度优先搜索法进行遍历，给出可能得 到的一种顶点序列。2种顶(2) 同图3 所示,若从顶点h出发，按深度优先搜索法进行遍历，给出可能得到的 占八、序列。acedh(3)一组记录的关键字序列为(75，63，95，80， 53，45，38， 20)，利用堆排序的方法建立小根堆 (堆顶元素是最小元素) , 给出按筛选法建立的的初始堆。(1) acefdh(2) hdeacf hdfcae

18、(3)20, 53，38，63，75，45， 95，80四、程序填空题1以下函数在a0到an-1 中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a,int n, int k)int low,mid,high;low=0;high=n-1;while(_(1) ) mid=(low+high)/2; if(amid.key=k) return_(2) ;else if(_(3) )low=mid+1;else_(4) ;_(5);(1) lo

19、w<=high(2) mid(3) amid.key < k(4) high=mid -1(5) return -12. 以下函数为直接选择排序算法，对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;(2)_; j+)if(aj.key<ak.key);if(i!=k) temp=ai;(4);(5);(1) n-1 j<=nk=j ai=a

20、ktop为栈顶指针(5) ak=temp3. 以下函数为链栈的进栈操作，x是要进栈的结点的数据域,struct node ElemType data;struct node *n ext;struct node *top ;void Push(ElemType x) struct node *p;p=(struct no de*)malloc(1);p_>data=x;_ ;(3);(1) sizeof(struct node)(2) p next=top top=pfront、4. 以下函数为链队列的入队操作，x为要入队的结点的数据域的值,一、单项选择题1. 对稀疏矩阵进行压缩存储 元

21、素，其相应的三元组表共有 A 8BC 7D2 . 单向链表所具备的特点是A.可以随机访问任一结点B.占用连续的存储空间C. 插入删除不需要移动元素D.可以通过某结点的指针域访问其前驱结点3.子串“ acd”在主串A 3“ abdcacdefacB”中的位置是 （ B ） 。5rear 分别是链队列的队头、队尾指针struct node ElemType data; struct node *next;struct node *front ， *rear;void InQueue(ElemType x)struct node *p;p= (struct node*)_(1);p->data

22、=x;p->next=NULL; _(2); ;rear=_(3) ;(1) malloc(sizeof(struct node)(2) rear->next=p;(3) rear=p;综合练习二, 可采用三元组表，一个有 10 行的稀疏矩阵 A 共有 97 个零 3 个元素。该矩阵 A 有 （ D ） 列。9 101C 74 .设有一个长度为 18的顺序表，要在第 6个元素之前插入一个元素（也就是插入元素作为新表的第 6 个元素），则移动元素个数为（ C ）。A 12 B5C. 13 D 65. 序列 12,16,8,4 按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的不

23、可 能输出序列是（ B ）。 （ 进栈、出栈可以交替进行） 。A16,12,8,4B4,8,12,16C8,4,16,12D16,12,4,86栈和队列的共同特点是（A）。A都是线性结构B元素都可以随机进出C.都是先进后出D都是先进先出7. 在一个不带头结点的链队中，假设 f 和 r 分别为队头和队尾指针，对该队列进行出队 操作 , 并把结点的值保存在变量e 中, 其运算为（ C ）。A e=f->data ； r=r->next;B e=f->data ； r->next=r;C e=f->data ； f=f->next;D e=f->data ；

24、 f->next=f;8 元素 1，3，5，7 按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序 列是（ D ）（进栈出栈可以交替进行） 。A 7， 5，1，3B7，3，1，5C5，1，3，7D 7，5，3，19. 数据的逻辑结构在计算机内存中的表示是 （ B ） 。A. 给相关变量分配存储单元B. 数据的存储结构C. 数据的逻辑结构D. 算法的具体体现10 在一个不带头结点的链队中，假设 f 和 r 分别为队头和队尾指针，则对该队列进行 出队操作中并把结点的值保存在变量e 中 , 其运算为 e=f data ；和（ C ）。A r=r next; B r next=r;C f

25、=fnext; Df next=f11. 以下说法正确的是 （ B ） 。A. 线性表的链式存储结构必须占用连续的存储空间B. 一种逻辑结构可以有不同的存储结构C 一种逻辑结构只能有唯一的存储结构D.线性表的顺序存储结构不必占用连续的存储空间12设有一个对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素，则该矩阵是（D ）阶的对称 矩阵。A. 15B13. 在一个单链表中要删除A . p->next=q->next ; C. p->next=q;14. 下列是 C 语言中. 11 C . 10 Dp 所指结

26、点的后继结点，可执行B. p=q->next;D. p->next=q;abcd321ABCD的子串的选项是（AA.21ABCB.abcABCDC. abcDD.321a.9q=p->next;和（ A ）。）。15. 在数据结构和算法中，与所使用的计算机有关的是（ B ）。A .数据元数间的抽象关系 B .数据的存储结构C .算法的时间复杂度D .数据的逻辑结构16. 字符串 a1= ” BEIJING" , a2 = ” BEF' , a3=” BEFANG , a4= “BEFI"最小的是（ B ） .A. a1B. a2C. a3D. a4

27、17. 以下表中可以随机访问的是（ D ）。A .单向链表B.双向链表C 单向循环链表D 顺序表18. 一棵有20个结点采用链式存储的二叉树中，共有（ A ）个指针域为空。A . 21B. 20 C . 19 D . 1819. 头指针为head的不带头结点的单向链表为空的判定条件是逻辑表达式（A ） 为真。A. head= =NULL B. head-next= =NULLC. head-next=NULL D. head-next!= NULL20. 设一棵哈夫曼树共有18个叶结点，则该树有（ C ）个非叶结点。A . 18B19 C17 D . 1621 .设有一个长度为32的顺序表，要

28、在第 5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），需移动元素个数为（B ）。A . 25 B . 28 C. 5 D. 622 .如图1所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（D ）。gabecdfgacfebd Cgaebcfd D . gaedfcbaCed图123 .设有一个长度为 33的顺序表，要删除第 10个元素（下标从1开始）需移动元素的个数为（C ）。A . 11 B . 10 C . 23 D . 1424 .线性表以（B ）方式存储，能进行折半查找。A .关键字有序的B .关键字有序的顺序C .链接 D .顺序2

29、5 .设有一个28阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组 B中（数组下标从1开始），则数组中第26号元素对应于矩阵中的元 素是（A ）。a . a7,5 , b . a7,6c . a6,5d . a?,426 .有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（D ）。A . 22/8B. 20/8C. 23/8 D . 21/827. 在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是p=p-n ext;禾廿（D

30、）。A . p=q_>next; B . p_>next=q ; C . q=p; D . q_>next=p;28. 排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（ A ）。A .折半插入排序B.直接插入排序C .归并排序 D .选择排序29. 在一棵二叉树中，若编号为16的结点是其双亲结点的左孩子，则他的双亲结点的顺序编号为（B ）°A . 7 B . 8 C . 32 D . 3330. 排序方法中，从未排序序列中挑选兀素，并将其依次放入已排序序列（初始为空）的

31、一一端的方法，称为（C ）排序。A .堆 B .冒泡 C .选择 D .快速二、填空题1数据的逻辑结构在计算机中的表示称为物理（存储）结构。2结构中的数据元素存在一对多的关系称为树形结构。3四类基本结构分别为 集合线性树形图状结构。4栈的操作特点是 先进后出 。5.队列的操作特点是先进 先出。6广义表的（a , （a ,b） , d , e ,（ （i ,j ） ,k ）深度是3。7广义表（b,a,c） , c,d ,（ e ,i ,j ,k ）的表尾是 _ （c,d,（e,i,j,k）。8广义表（a ,b） , d , e ,（ （i ,j ） ,k ）的长度是 4 _。9. 设有一个长度为

32、 20的顺序表，第8号元素到第20号元素依次存放的值为8,9,20。某人想要在第8号元素前插入1个元素7 （也就是插入元素作为新表的第8个元素），程序中他的做法是用语句 for（i=8;i<=20;i+）ai+1=ai;a8=7;即从第8号元素开始，直到第20号元素，每个元素依次向后（右）移动1个位置，然后把7存放在第8号位置。事实上这样做是错误的其结果是新表中第 20号元素的值为 8。10. 设顺序队列的类型为typedef struct ElemType dataMaxSise;int fron t,rear;Squeue;Squeue *sq;sq为指向顺序队列的指针变量，要进行元

33、素的出队操作，并把元素赋给边量x,按教科书约定，可用语句 x=sq->datasq->front;禾口_ sq->fronf+; 。11. 设有一棵有38个结点的完全二叉树，该树共有 6层。（根所在结点为第1层）12. 设顺序队列的类型为typedef struct ElemType dataMaxSise;int fron t,rear;Squeue;Squeue *sq;sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定，可用语句sq->datasq->rear=x;禾廿sq->rear+;。13. 一棵有18个结点的二叉树，其2度结点

34、数的个数为8,则该树共有_ 1个1度结点。14. 序列14,12,15,13,18,16,采用冒泡排序算法，经一趟冒泡后,序列的结果是12,14,13,15,16,18。(由小到大排序)15. 对一组记录(1 , 3, 9, 2, 12, 7, 5, 4, 6)进行直接插入排序(由小到大排序)，当把第6个记录7插入有序表，为寻找插入位置需比较 3 次。16. 数据结构中，数据元素之间的抽象关系称为逻辑结构。17. 序列538,4,7,6,采用冒泡排序算法，经一趟冒泡后，序列的结果是3,5,4,7,6,8 。(按升序排序)18. 循环队列中，设front和rear分别为队头和队尾指针，(最多元素

35、为 MaxSize,),判断循环队列为空的条件为 front= =rear为真。19. 广义表(b,a , (c ,b) , f , e ,( (i ,j ) ,k )的长度是 6。20. 排序算法中，从尚未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少)，然后将其放入已排序序列的正确位置的方法是折半插入排序。21. 棵有18个叶结点的哈夫曼树，则该树共有 17_个非叶结点。22. 对稀疏矩阵进行压缩存储，可采用三元组表，矩阵元素 a3,4对应的三元组为 _ (3,4,a3,4)。23. 对稀疏矩阵进行压缩存储，可采用三元组表，一个8行7列的稀疏矩阵A共有5

36、1个零元 素，其相应的三元组表共有 5个元素24. 在双向链表中，要删除p所指的结点，其中所用的一条语句(p->next) ->prior=p->prior;的功能是：使P所指结点的直接后继的左指针指向P所指结点的直接前驱 。三、综合题1.设数据集合 a=6,17,10,13,8,15,12,18,14(1) 依次取a中各数据，构造一棵二叉排序树。(2) 给出对该二叉树中序遍历的序列(3) 对该二叉树进行查找，成功查找到14要进行多少次元素间的比较？图2(2) 中序遍历 6 , 8 ,10,12 , 13 , 14 , 15 , 17 , 18(3) 6 次2. 设数据集合

37、a=62,74,30,15,56,48（1）依次取 a 中各数据，构造一棵二叉排序树。（2）对该二叉树进行查找，不成功查找有多少种可能？画出不成功查找树的示意图。 （ 3）不成功查找的平均查找长度是多少 ?（ 4）为了成功查找到 48 需要进行多少次元素间的比较 ? （5）给出对该二叉树后序遍历的序列。（1）图 3（2）图 4 7 种可能（3）（2*2+3*3+4*2）/7=21/7（4）4 次（5）15,48,56,30,74,623设有序表为（2, 5, 11, 12, 30, 48, 58）,元素的序号依次为1,2,3,7.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号

38、表示） （ 2）说明成功查找到元素11 需要经过多少次比较？（3）在等概率条件下 , 给出成功查找的平均查找长度（1 ）图 5(2) 3 次(3) ( 1+2*2+3*4)/7=17/74设有序表为（ 3， 9， 15， 26， 38， 41， 53， 74， 81， 96， 97， 99），元素的 序号依次为1,2,，12。（1） 说出有哪几个元素需要经过3次元素间的比较才能成功查到。（2） 画出对上述有序表进行折半查找所对应的判定树（树结点用序号表示）。（3）设查找 5号元素（38），需要进行多少次元素间的比较才能确定不能查到 , 依次和 哪些元素进行了比较？（要求写出具体元素） 。（4）

39、给出后序遍历该二叉树的序列。（5）给出中序遍历该二叉树的序列。(1) 3, 26, 53, 97图7(3) 4 次 41,15,26,38 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41)(5) 1( 3) ,2(9),3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)5 .(1) 如图1所示，若从顶点a出发，首先经过顶点 c按广度优先搜索法进行遍历，给出可能 得到的一种顶点序列。(2) 如图1所示，给出从顶点 h出发，首先经

40、过顶点 d和e按深度优先搜索法进行遍历, 给出可能得到的一种顶点序列。(3) 一组记录的关键字序列为(80,57,41,39,46,47)，利用堆排序的方法的方法建立小根堆(堆顶元素是最小元素)，给出按筛选法建立的的初始堆。(1) acefdbh hdeacfb(3)39 46 41 57 80 47四、程序填空题1. 以下冒泡法程序对存放在a1, a2,an中的序列进行冒泡排序完成程序中的空格部分，其中n是元素个数，程序按升序排列。void bsort (NODE a , i nt) NODE temp;int i,j,flag;for( j=1; j<=n -1 ;(1) flag=

41、0;for(i=1; (2);i+)if ( ai.key>ai+1.key) flag=1;(3)a i=ai+1;(4) ;if(flag= =O)break;程序中flag的功能是_J5)1.(1) j+ i<=n-j(3) temp=ai;(4) ai+1=temp;(5) 判断某一趟排序中是否有元素交换2学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。数组元素按学号num由小到大有序排列，以下函数在a0到an-1中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标（数组元素的下标）。失败时返回-1，完成程序中的空格。type

42、def structchar sex;int num;NODE;int Binary_Search(NODE a,int n, int k)int low,mid,high;low=0;high=n-1;while(_(1)mid=(low+high)/2;if(amid. num = =k)return_(2);else if(_)low=mid+1;else_(4);return -1 ;(1) low<=high(2) mid(3) amid .n um<k(4) high=mid-1;3以下函数为链栈的出栈操作，出栈结点的数据由x返回struct node ElemType

43、 data;struct node *n ext;ElemType Pop() int x;if(top=(1)prin tf("栈下溢错误！ n");exit(1);x= ;top=_(3);return x;(1) NULL(2) top->data(3) top-> next4.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p (查找成功p指向查找到的树结点，不成功，则p指向为NULL),完成程序中的空格。struct bnode int key;structbnode *left;structbnod

44、e *right;typedef struct bnode BnodeBnode *BSearch(Bnode *bt, int k) /* bt 用于接收二叉排序树 的根结点的指针，k用以 接收要查找的关键字 */ Bnode *p;if(bt = = NULL)return (bt);_(1)while(p->key!=_(2)_ ) if(k<p->key)_(3);else_(4) ;if(p=NULL) break;return p ;(1) p=bt;(2) k(3) p=p->left(4) p=p->right综合练习一答案一、单项选择题1C 2C 3 A 4D5A 6 A 7 B 8B 9A10A 11A 12D13C14C15C16 C 17 C18 B 19 A20 B 21 B 22 B23C24C25 C26 D 27 A28 D 29 B30 D二、填空题1. 62. 树形3. 逻辑4. 图状5. 先出6. rear=front 为真7. ( b,a,c)8. 69. 1810.0( n)11.512.1813. 614. n