62 74 56 30 15 48 图4
3
（1）图5 6 39
10 1 4 7
11 2 5 8
图5
(2) 3次 (3) 4次 (4) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 （序号） 4.
(1)图6 (2)4次41,15,26,38
(3) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41) （4）1( 3）,2(9), 3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)
6 3 9 1 4 7 11 2
四、程序填空题
1. (1) p=p->next;
(2)p->data或prep->data (3) p->next;
2.
(1)low<=high (2)mid (3)a[mid].num 3. (1) n (2) (s+j)/2; (3) j=m-1; (4) s=m+1; (5) a[k+1] 4． (1) p=bt; (2) k (3)p=p->left (4)p=p->right 5 8 10 图6 12 期末综合练习二 一、单项选择题 1.数据的存储结构包括数据元素的表示和（ ）。 A . 数据处理的方法 B. 数据元素间的关系的表示 C . 相关算法 D. 数据元素的类型 2 .下面关于线性表的叙述中,错误的是( )。 A . 线性表采用顺序存储,必须占用一片连续的存储空间 B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动 C. 线性表采用链式存储，不必占用连续的存储空间 D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 3．设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A．15 B．22 C．14 D．23 4 .设有一个长度为28的顺序表，要在第12个元素之前插入一个元素（也就是插入元素作为新表的第12个元素），则移动元素个数为（ ）。 A．12 B．17 C. 13 D．11 5．元素2,6,10,14按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列 的不可能输出序列是是（ ）。（进栈出栈可以交替进行）。 A．14,10,6,2 B．2,6,10,14 C．14,10,2,6 D．6,2,14,10 6．元素2，4，6,8按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。 A．8,6,4,2 B．2,4,6,8 C．4,2,8,6 D．8,6,2,4 7．对一个栈顶指针为top的链栈进行进栈操作，设P为指向待进栈的结点的指针，把e 的值赋值给该结点的数据域，然后使该结点进栈，则执行（ ）。 A．p->data=e; p=top->next; top=top?next; B．p->data=e;p->next=top;top=p; C．p->data=e;top=p; D．p->data=e;p->next=top->next; top =p; 8．对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值 ，则执行 （ ）。 A. e= top->next; top->data=e; B．e=top->data; top=top->next; C．top=top->next; e=top->data; D．top=top->next; e=data; 9 .对不带头结点的单向链表,判断是否为空的条件是（ ）（设头指针为head）。 A．head==NULL B．head->next= =NULL C．head->next= =head D．head =NULL 10．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行（ ）。 A．rear?next= s; s?next=rear?next B．rear?next=s?next; C．rear=s?next D．s?next=rear?next ; rear?next=s; 11．设有一个25阶的对称矩阵A（矩阵的第一个元素为a1,1），采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,5在一维数组B中的下标是（ ）。 A．34 B．14 C．26 D．27 12．设有一个28阶的对称矩阵A（矩阵的第一个元素为a1,1），采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第40号元素对应于矩阵中的元素是（ ）。 A．a10,8 B．a9,4 C．a9,5 D．a8,5 13.数组a经初始化 char a[ ]=“English”; a[7]中存放的是（ ）。 A. 字符串的结束符 B. 字符h C. 〝h〞 D. h 14.数组a经初始化 char a[ ]=“English”; a[1]中存放的是（ ）。 A. 字符n B. 字符E C. 〝n〞 D. 〝E〞 15 .设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。 A. aBc B. BCd C. ABC D .Abc 16. 程序段char a[ ]=“English”; char *p=a; int n=0; while( *p!=‘\\0’){ n++; P++;}结果中,P指向（ ）。 A. 字符h B.a C. 字符串的结束符 D.7 17．设一棵哈夫曼树共有11个非叶结点，则该树有（ ）个叶结点。 A．22 B。10 C．11 D．12 18．在一棵二叉树中，编号为17的结点的双亲结点的的顺序编号为（ ）。 A．34 B．7 C．9 D．8 19．一棵具有38个结点的完全二叉树，最后一层有（ ）个结点。 A．7 B．5 C．6 D．8 20．设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空。则该树共有（ ）个非叶子结点 A．21 B．22 C． 9 D．10 21．已知如图1所示的一个图，若从顶点V1出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 A．V0V1V2V3V6V7V4V5V8 B．V0V1V2V3V4V5V8V6V7 C．V0V1V2V3V4V5V6V7V8 D．V0V1V2V3V4V8V5V6V7 V1 V0 V2 V3 V4 V5 V6 V7 V8 图1 22．已知如图1所示的一个图，若从顶点V0出发，按深度优先法进行遍历，则可能得到的一种顶点序列为（ ）。 A. V0V1V2V4V8V5V3V6V7 B．V0V1V2V4V5V8V3V6V7 C．V0V1V2V4V8V3V5V6V7 D．V0V1V3V6V7V2V4V5V8 23．在有序表{10,14，34，43，47，64，75，80，90}中，用折半查找法查找值80时，经（ ）次比较后查找成功。 A．4 B．2 C．3 D．5 24．对( )进行中序遍历，可以使遍历所得到的序列是有序序列。 A．完全二叉树 B．二叉排序树 C．满二叉树排 D．哈夫曼树 25．排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行 比较，然后将其放入已排序序列的正确位置的方法是（ ）。 A．冒泡排序 B．直接插入排序 C．归并排序 D．选择排序 26．有一个长度为7的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平 均比较次数为（ ）。 A．17/7 B．18/7 C．21/7 D．20/7 27．一组记录的关键字序列为（22，55，32，14,16，60），利用快速排序，以第一个关键字 为分割元素，经过一次划分后结果为（ ）。