2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构2010-2022历年真题选编带答案难题含解析

2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构2010-2022历年真题选编带答案难题含解析（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共75题)1.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较______次。A.1B.2C.3D.42.从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、*、/四种运算，例如：234-34+2*$。3.在采用链地址法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的______相同。A.关键字值B.元素值C.散列地址D.含义4.有一组数据(15，9，7，8，20，-1，7，4)，用堆排序的筛选方法建立的初始堆为______。A.-1，4，8，9，20，7，15，7B.-1，7，15，7，4，8，20，9C.-1，4，7，8，20，15，7，9D.A、B、C均不对5.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在______。A.内存空间的首地址B.内存空间的尾地址C.内存空间的两端D.内存空间的中间6.若循环队列以数组Q[0，…，m-1]作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MODm进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是______。A.rear-lengthB.(rear-length+m)MODmC.(rear-length+l+m)MODmD.m-length7.设A和B是两个顺序表，其元素按从小到大的顺序排列。编写一个将A和B中相同元素组成一个新的从大到小的有序顺序表C的算法，并分析算法的时间复杂度。8.设计快速排序的递归和非递归算法。9.构建一个哈夫曼树，如果给定权值的个数为n，那么哈夫曼树的结点总数为______．A.不确定B.2nC.2n+1D.2n-110.下列______是一个堆。A.19，75，34，26，97，56B.97，26，34，75，19，56C.19，56，26，97，34，75D.19，34，26，97，56，7511.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足

。A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树12.改写顺序栈的结构和进栈函数Push(x)，要求当栈满时执行一个stackFull()操作进行溢出处理。其功能是：动态创建一个比原来的栈数组大一倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前maxSize个位置。

原顺序栈的程序代码如下：

typedefstruct

{

intdata[maxSize];

//存放栈中元素，maxSize是已定义的常量

inttop;

//栈顶指针

}SqStack;

//顺序栈类型定义

原进栈函数程序代码如下：

intPush(SqStack&st,intx}

{

if(st.top==maxSize-1)

//栈满不能进栈

return0;

++(st.top);

//先移动指针，再进栈

st.data[st.top]=x;

return1;

}13.试问中序序列及后序序列是否能唯一地建立二叉树?若不能，则说明理由；若能，则对中序序列[)BEAFGC和后序序列DEBGFCA构造二叉树。14.下列4组含C1～C7的结点序列中，______是下图所示的有向图的拓扑序列。

A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C3，C615.若在一棵完全二叉树中对所有结点按层次自上向下，同一层次自左向右进行编号，根结点的编号为0，现有两个不同的结点，它们的编号是p和q，那么判断它们在同一层的条件应是______。

A．

B．

C．

D．p/2==q/216.已知10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为______。A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，9517.对AOE网络中有关关键路径的叙述中，正确的是______。A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间18.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是

。A.9B.11C.15D.不确定19.若想在单链表中删除某结点p(p既不是第一个，也不是最后一个结点)的直接后继，则应执行______操作。A.p→next=p→next→nextB.p=p→next;p→next=p→next→nextC.p→next=p→nextD.p=p→next→next20.无向图的邻接矩阵是一个______。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵21.设G是一个非连通无向图，有15条边，则该图至少有______个顶点。A.5B.6C.7D.822.在n个结点的线索二叉树中，线索的数目是______。A.n-1B.n+1C.2nD.2n-123.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是______。A.单链表B.带有头指针的单循环链表C.双链表D.带有尾指针的单循环链表24.下列二叉树中，不平衡的二叉树是

。

25.一组记录的序列F={46，79，56，38，40，84}，则利用快速排序算法，以第一个记录为基准，得到的一次划分结果为______。A.{38，40，46，56，79，84}B.{40，38，46，79，56，84}C.{40，38，46，56，79，84}D.{40，38，46，84，56，79}26.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为

。A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84)D.(40，38，46，84，56，79)27.用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入______时，会出现不平衡的现象。A.22B.35C.48D.6228.已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2h一1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。29.若一个栈的输入序列为1，2，3，…，n，输出序列的第一个元素是i，则第j个输出元素是

。A.i-j-1B.i-jC.j-i+1D.不确定的30.试分别用顺序表和单链表作为存储结构，实现将线性表(a0，a1，a2，……，an-1)就地逆置的操作，所谓“就地”，是指辅助空间应为O(1)。31.用单链表存储多项式的结构定义如下：

TypedefstructTerm{

//多项式的项

floatcoef;

//系数

intexp;

//指数

structTerm*link;//链指针

}*Polynomial;

试编写一个算法，输入一组多项式的系数和指数，按指数降幂的方式建立多项式链表，要求该链表具有表头结点。如果输入的指数与链表中已有的某一个项的指数相等，则新的项不加入，并报告作废信息。整个输入序列以输入系数为0标志结束。算法的首部为PolynomialcreatePoly()；32.设一棵二叉树的前序序列为abdecf，后序序列为debfca，则该二叉树中序遍历的顺序是______。A.adbecfB.dfecabC.dbeacfD.abcdef33.设T是哈夫曼二叉树，具有5个叶结点，树T的高度最高可以是______。A.3B.4C.5D.634.设一棵二叉树的先序、中序遍历序列分别为ABDFCEGH、BFDAGEHC

(1)画出这棵二叉树。

(2)画出这棵二叉树的后序线索树。

(3)将这棵二叉树转换成对应的树(或森林)。35.对于由n个顶点组成的有向完全图来说，图中共包含______条边，对于由n个顶点组成的无向完全图来说，图中共包含______条边。A.n，n(n-1)B.n，n(n-1)/2C.2n，n(n-1)D.n(n-1)，n(n-1)/236.一个n×n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?37.对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减1，并对其未访问的、入度为0的邻接到的顶点进行递归。

(1)给出完成上述功能的图的邻接表定义。

(2)定义在算法中使用的全局辅助数组。

(3)写出在遍历图的同时进行拓扑排序的算法。38.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为______。A.(n-1)/2B.n/2C.(n+1)/2D.n39.已知二叉树排序树中某结点指针p，其双亲结点指针为fp，p为fp的左孩子。试编写算法，删除p所指结点。40.已知一棵二叉树的中序序列和后序序列如下：

中序：GLDHBEIACJFK

后序：LGHDIEBJKFCA

(1)给出这棵二叉树；

(2)转换为对应的森林；

(3)画出该森林的带右链的先根次序表示法：

(4)画出该森林带度数的后根次序表示法；

(5)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。(用语言叙述，不用写算法)41.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈的次序不包括______。A.CDEBAB.CDBEAC.CDBAED.CDAEB42.已知一算术表达式的中缀形式为A+B+C-D/E，后缀形式为ABC*+DE/-，其前缀形式为______。A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE43.不带表头结点的单链表first为空的判定条件是

，带表头结点的单链表first为空的判定条件是first→next==NULL;。A.first==NULL;B.first→next==NULL;C.first→next==first;D.first!=NULL;44.散列表的平均查找长度______。A.与处理冲突的方法有关而与表的长度无关B.与处理冲突的方法无关而与表的长度有关C.与处理冲突的方法有关且与表的长度有关D.与处理冲突的方法无关且与表的长度无关45.如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用______存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表46.为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈s1、s2都采用顺序栈方式，并且共享一个存储区[0～maxsize-1]。

设计共享存储空间的两个栈s1、s2的入栈和出栈算法。要求：

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释；47.已知输入序列为abed，经过输出受限的双端队列后，能得到的输出序列是______。A.daebB.eadbC.dbeaD.以上答案都不对48.包含有4个结点的元素值互不相同的二叉排序树有______种。A.4B.6C.10D.1449.有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。(可不定义结构体)50.以下是一个5×5阶螺旋方阵。设计一个算法输出该形式的n×n(n＜10)阶方阵(顺时针方向旋进)。

1

2

3

4

5

16

17

18

19

6

15

24

25

20

7

14

23

22

21

8

13

12

11

10

951.归并排序中，归并的趟数是______。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)52.判断一个有向图是否存在回路除了可利用拓扑排序方法外，还可用利______。A.求关键路径的方法B.求最短路径的Dijkstra方法C.广度优先遍历算法D.深度优先遍历算法53.在一个非空二叉树的中序序列中，根结点的右边______。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点54.已知一组递增有序的关键字值存放在k[1，…，n]中，k[1]≤k[2]≤…≤k[n]，在相等搜索概率的情况下，若要生成一棵二叉排序树，以哪个关键字值为根结点，按什么方式生成二叉排序树平衡性最好且方法又简单?阐明算法思路，写出相应的算法。如果数组k中元素为{7，12，13，15，21，33，38，41，49，55，58}，并画出这棵二叉排序树。55.已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?

(1)关键字自小到大有序(key1＜key2＜…＜keyn)；

(2)关键字自大到小逆序(key1＞key2＞…＞keyn)；

(3)奇数关键字顺序有序，偶数关键字顺序有序(key1＜key3)＜…，key2＜key4＜…)；

(4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1＜key2＜…＜keym，keym+1＞keym+2＞…＞keyn，m为中间位置)。56.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是______。A.10B.11C.16D.不确定57.试设计判断两棵二叉树是否相似的算法。所谓二叉树t1和t2相似是指t1和t2都是空的二叉树；或者t1和t2的根结点是相似的，t1的左子树和t2的左子树是相似的且t1的右子树与t2的右子树是相似的。58.分析以下程序段的时间复杂度。

...

i=1;

while(i＜=n)

i=i*2;

...59.下面的叙述中正确的是______。

Ⅰ．线性表在链式存储时，查找第i个元素的时间同i的值成正比

Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关

Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比A.仅ⅠB.仅ⅡC.仅ⅢD.Ⅰ、Ⅱ、Ⅲ60.编写算法实现以被分类序列中所有元素的平均值为界值的快速分类方法。61.在一个长度为n的顺序表中向第i个元素(0＜i＜n+1)之前插入一个新元素时，需向后移动(

)个元素。A.n-iB.n-i+1C.n-i-1D.i62.一个二部图的邻接矩阵A是一个______类型的矩阵。A.n×n矩阵B.分块对称矩阵C.上三角矩阵D.下三角矩阵63.在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为______。A.O(n)B.O(log2/n)C.O(nlog2n)D.O(n2)64.一棵高度为h的AVL树，若其每个非叶结点的平衡因子都是0，则该树共有______个结点。A.2h-1-1B.2h-1C.2h-1+1D.2h-165.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。66.下列4个序列中，哪一个是堆

。A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15，25，20，10D.75，45，65，10，25，30，20，1567.有n个结点的二叉树，已知叶结点个数为n0。

(1)写出求度为1的结点的个数的n1的计算公式。

(2)若此树是深度为k的完全二叉树，写出n为最小的公式。

(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。68.依次读入数据元素序列{a，b，C，d，e，f，g)进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列?

A．{d，e，c，f，b，g，a}

B．{f，e，g，d，a，C，b}

C．{e，f，d，g，b，C，a}D．{c，d，e，b，f，a，g}69.假设图采用邻接表存储，编写一个函数，利用深度优先搜索算法，求出无向图中通过给定点v的所有简单回路。70.由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为

。A.24B.48C.72D.5371.假设稀疏矩阵只存放其非0元素的行号、列号和数值，以一维数组顺次存放，行号-1作结束标志。例如，如下所示的稀疏矩阵M，存放在一维数组D中，D的元素如下：D[0]=0，D[1]=0，D[2]=1，D[3]=0，D[4]=4，D[5]=10，D[6]=2，D[7]=8，D[8]=5，D[9]=-1。

现有两个如上方法存储的稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，编写求矩阵加法C=A+B的算法，C亦放在数组C中。72.在下列关于外排序过程输入/输出缓冲区作用的叙述中不正确的是______。A.暂存输入/输出的记录B.内部归并的工作区C.产生初始归并段的工作区D.传送用户界面的消息73.给定整型数组B[0，…，M][0，…，N]。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。设计一个程序段，找出一对满足B[i][j]=x的i，j值，找到后输出i和j的值，要求比较次数不超过M+N。74.有n个叶结点的非满的完全二叉树的高度为______。A.2n+1B.2n-1C.log22n+1D.log22n-175.用邻接矩阵A表示图，判定任意两个顶点vi和vj之间是否有长度为m的路径相连，则只要检查______的第i行第j列的元素是否为零即可。A.mAB.AC.AmD.Am-1第1卷参考答案一.历年考点试题黑钻版1.参考答案：C第6趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入60，要与95、70和50进行比较，共比较3次，本题答案为C。2.参考答案：逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND，对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。

floatexpr(){

//从键盘输入逆波兰表达式，以'$'表示输入结束，本算法求逆波兰表达式的值

floatOPND[30];

//OPND是操作数栈

init(OPND);

//两栈初始化

floatnum=0.0;

//数字初始化

scanf("%c",&x);

//x是字符型变量

while(x!='$'){

switch(x){

case'0':

case'1':

case'2':

case'3':

case'4':

case'5':

case'6':

case'7':

case'8':

case'9':

while((x＞='0'&&x＜='9')||x=='.')//拼数

if(x!='.'){num=num*10+(ord(x)-ord('0'));scanf("%c",&x);}//处理整数

else{

//处理小数部分

scale=10.0;scanf("%c",&x);

while(x＞='0'&&x＜='9'){

num=num+(ord(x)-ord('0'))/scale;

scale=scale*10;scanf("%c",&x);

}

}//else

push(OPND,num);num=0.0;

//数压入栈，下个数初始化

case'':break;

//遇空格，继续读下一个字符

case'+':push(OPND,pop(OPND)+pop(OPND));break;

case'-':x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;

case'*':push(OPND,pop(OPND)*pop(OPND));break;

case'/':x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;

default;

//其他符号不作处理

}//结束switch

scanf("%c",&x);

//读入表达式中下一个字符

}//结束while(x!='$')

printf("后缀表达式的值为%f");pop(OPND);

}假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于'0'且小于等于'9'的字符，认为是数。这种字符的序号减去字符'0'的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点时，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10(或10的幂数)变成十分位、百分位、千分位数等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量nun恢复为0，准备下一个数。这时对新读入的字符进入'+'、'-'、'*'、'/'及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。3.参考答案：C[解析]同义词子表所链接的各个表项的关键字互为同义词，意味着虽然这些关键字的值不同，但用同一个散列函数计算出的散列地址相同。4.参考答案：C此题考查的知识点是堆排序。应选C。5.参考答案：C两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。6.参考答案：C[解析]按照循环队列的定义，因为元素移动按照rear=(rear+1)MODm进行，则当数字Q[m-1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是(rear-length+1+m)MODm。7.参考答案：本算法是从A和B的最后两个元素开始比较，若相等，将其值放入C的第一个元素中，如此直到A和B中的所有元素比较完毕。实现本题功能的程序代码如下：

intintersect(intA[],intna,intB[],intnb,intC[])

{

inti=na,j=nb,k=0;

while(i＞=0&&j＞=0)

if(A[i-1]＞B[j-1])

--i;

elseif(A[i-1]＜B[j-1])

--j;

else//A[i-1]=B[j-1]

{

C[k++]=A[i-1];

--i;

--j;

}

returnk-1;

}

本算法intersect(A，na，B，nb，C)的时间复杂度为O(na+nb)，其中na和nb分别为A和B的长度。8.参考答案：本题非递归算法容易实现，在《数据结构高分笔记》一书中已经讲过，核心算法即为序列的划分，然后递归处理划分好的子序列。非递归算法需要自己申请栈空间以代替系统栈。

划分函数代码如下：

voidsplit(intA[],intlow,inthigh,int&i)

{

intj;

intx;

i=low;j=high;x=A[i];

//初始化

while(i＜j)

{

while(A[j]＞=x&&i＜j)

//从右向左遍历

--j;

if(i＜j)

{

A[i]=A[j];++i;

//相当于交换A[i]与A[j]

}

while(A[i]＜=x&&i＜j)

//从左向右遍历

++i;

if(i＜j)

{

A[j]=A[i];--j;

//相当于交换A[i]与A[j]

}

}

A[i]=x;

//x定位在位置i处

}

递归算法代码如下：

voidquicksort(intA[],ints,intt)

{

inti;

if(s＜t)

{

split(A,s,t,i);

quicksort(A,s,i-1);

quicksort(A,i+1,t);

}

}

非递归算法代码如下：

voidquicksort2(intA[],intn)

{

inti,l,h;

intstack[maxSize][2],top=-1;

//maxSize是已定义的常量

i=0;h=n-1;

++top;

//入栈

stack[top][0]=1;stack[top][1]=h;

while(top＞=0)

{

l=stack[top][0];h=stack[top][1];

//出栈

--top;

split(A,l,h,i);

if(l＜h)

{

++top;

//入栈

stack[top][0]=1;stack[top][1]=i-1;

++top;

//入栈

stack[top][0]=i+1;stack[top][1]=h;

}

}

}9.参考答案：D哈夫曼树中只有度为0和度为2的结点，即N=n0+n2，而根据二叉树的性质：n0=n2+1，可知n0=n，那么n2=n-1，N=n+n-1=2n-1。10.参考答案：D完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示：

得出答案为D。11.参考答案：C前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。12.参考答案：原顺序栈的结构体中是用静态数组来存放数据，现在题目需要动态创建数组，因此需要把静态数组改掉，代码如下：

typedefstruct

{

int*data;

//指向动态数组的指针

inttop;

//栈顶指针

intmaxSize;

//因data数组是动态变化的，所以将maxSize改为变量

}SqStack;

修改后的Push()函数代码如下：

intPush(SqStack&st,intx)

{

if(st.top==st.maxSize-1)//栈满执行stackFull()

{

if(stackFull(st)==0)

//栈满，且stackFull()函数失败，返回0

return0;

//否则只执行stackFull()

}

++(st.top);

//先移动指针，再进栈

st.data[st.top]=x;

return1;

}

stackFull()函数代码如下：

intStackFull(SqStack&st)

{

int*temp=(int*)malloc(2*st.maxSize*sizeof(int));

//申请一个动态数组空间长度为2倍的maxSize，由temp指向其首地址

if(temp==NULL)

return0;

//空间申请失败，返回0

for(inti=0;i＜=st.top;++i)

temp[i]=st.data[i];

//复制原栈中元素到新空间的前一半地址

free(st.data);

//释放原栈元素空间

st.data=temp;

//用data指针指向新空问首地址

return1;

//成功，返回1

}13.参考答案：[证明]

当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。

设当n=m-1时结论成立，现证明当n=m时结论成立。

设中序序列为S1，S2，…，Sm，后序序列是P1，P2，…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1，Si+2，…，Sm是右子树的中序序列。

若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1，则{S2，S3，…，Sm}和{P1，P2，…．Pm-1}可以唯一确定右子树，从而也确定了二叉树。

若i=m，则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。

最后，当1＜i＜m时，s，把中序序列分成{S1，S2，…，Si-1}和{Si+1，Si+2，…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1，P2，…，Pi-1)和{Pi，Pi+1，…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{Si+1，Si+2，…，Sm}和{Pi，Pi+1，…，Pm-1}可唯一确定二叉树的右子树。

由中序序列DBEAFGC和后序序列DEBGFCA构造的二叉树如下图：

14.参考答案：D考查拓扑排序的算法。

以1开头的拓扑排序过程，如下图所示：

以5开头的拓扑排序过程，答案中的过程如下图所示：

15.参考答案：A[解析]由结点层号计算公式可得编号为i(假设结点编号从0开始)的结点所在层号为+1。当两个结点位于同一层时，有，即。注意，如果结点编号从1开始，则。16.参考答案：B冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选B。17.参考答案：A本题考查关键路径的定义。

关键路径：从起点到终点的最长路径长度(路径上各活动持续时间之和)。

关键活动：关键路径上的活动称为关键活动。18.参考答案：B对任何一棵二叉树，如果终端结点数为n。，度为2的结点数为n2，则一定有n0=n2+1。所以n0=10+1=11，而与n1无关。19.参考答案：A[解析]因为p既不是第一个，也不是最后一个结点，所以p的直接后继存在。若想删除结点p的直接后继，只需要让p的后继的后继成为p的后继，即p→next=p→next→next。20.参考答案：A[解析]无向图的邻接矩阵是一个对称矩阵。对于同一条边(vi，vj)，它是双向的，所以在矩阵的第i行、第j列以及第j行、第i列都为1。21.参考答案：C[解析]本题根据连通图的性质以及顶点与边数的关系即可求解：设无向图有n个顶点，它的边数e≤n(n-1)/2。若e=15，有15≤n(n-1)/2，解得n>≥6。在连通图情形下至少需有6个顶点，在非连通图情形下则至少需有7个顶点。22.参考答案：B[解析]线索二叉树中共有2n个指针，子女指针有n-1个，其余的n+1个指针为线索。23.参考答案：D在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。24.参考答案：C平衡二叉树的特点为：左、右子树深度之差的绝对值不大于1。25.参考答案：C[解析]根据快速排序算法，以46为基准，其过程是将40放在第一个元素的位首，79放在40的位置，故选C。26.参考答案：C快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将待排序的记录分成独立的两部分，其中一部分记录的关键字比另一部分的关键字小。然后对这两部分再继续排序，一直达到整个序列有序。

设待排序序列为{L.r[1]，L.r[2]，…，L.r[n])，首先任意选取一个记录(通常选择第一个记录L.r[1])作为支点(pivot)，然后按照下述原则排列其余记录：将所有关键字比L.r[1]．key小的记录都安排在它的位置之前，将所有关键字比L.r[1].key大的记录都安排在它的位置之后。可以发现，在安置的过程中，L.r[1]的确切位置将被最终确定。设该支点(pivot)最后确定的位置为i，则将序列分割为左右两部分。这个过程称为一趟快速排序。

设待排序序列用数组e[low..high]保存。设置两个指针low和high，分别指向数组的开始位置和终止位置。设支点记录为e[low]，并将之暂存于t。

首先，从high的位置向前搜索，找到第一个小于t的记录，将这个记录和e[low]的值交换；然后，从low所指向的位置向后搜索，找到第一个值大于t的记录，将这个记录和e[high]的值交换。重复以上步骤，直到low=high。完成一趟排序，low(或者high)指向的位置就是第一个元素的确切位置(从两边向中间“夹挤”)。

第一趟完成后，确定了第一个元素的确切位置，同时生成了两个子序列，然后再对这两个序列使用同样的办法，最终实现整个序列的有序。

举例：利用快速排序法对以下序列进行排序：

(49，38，65，97，76，13，27，49)

过程如下：

初始状态：

high向左移动(high——)，直到找到小于t(49)的关键字27，将27的值赋给e[low]，如下：

接着low开始向右移动(low++)，直到找到大于t(49)的关键字65，将65的值赋给e[high]，如下：

high继续左移(high——)，直到找到一个小于t的数13，将之赋给e[low]，如下：

low继续右移(low++)，直到找到大于t(49)的关键字97，将之赋给e[high]，如下：

high继续左移(high——)，没有找到比t(49)还小的数，但是由于出现了high==low的情况，结束左移。如下：

此时low(或者high)指向的位置就是第一个元素的确定位置：e[low]=t；

经过以上一趟快速排序，可将原序列分为两个序列，同时确定关键字49的确切位置，如下：

{27，38，13}

49

{76，97，65，[49]}

下面再分别对两个子类进行快速排序，得最终结果：

{13)27{38}

49

{49，

65}

76

{97}

49

{65}

则最终得到有序序列：(13，27，38，49，49，6576，97)

说明：在一趟排序中，支点最后才确定位置，故只需最后一步赋值即可，中间不必交换。即，虽然快速排序是交换排序的一种，但是可以不用交换操作即可实现。该算法由于有不相邻元素交换，故是不稳定排序，其时间复杂度为O(nlogn2)，是内排序中最好的方法之一。27.参考答案：C由题中所给的结点序列构造二叉排序树的过程如下图：

当插入48后，首次出现不平衡子树，虚线框内即为最小不平衡子树。28.参考答案：[解析]二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的，不按完全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。本题中的虚结点用‘#’表示。

typedefstruct

BiTreebt；

∥二叉树结点指针

intnum；

∥num是结点在一维数组中的编号

}tnode

tnode

Q[maxsize]；

∥循环队列，容量足够大

voidcreat(BiTreeT，ElemTypeBT[])

∥深度h的二叉树存储于一维数组BT[1:2h-1]中，本算法生成该二叉树的二叉链表存储结构

{

tnodetq；

∥tq是队列元素

intlen=2h-1；

∥数组长度

T=(BiTree)malloc(sizeof(BiNode))；

∥申请结点

T->data=BT[1]；

∥根结点数据

tq.bt=T；

tq.num=1；

Q[1]=tq；

∥根入队列

front=0：

rear=1；

∥循环队列头、尾指针

while(front!=rear)∥当队列不空时循环

{

front=(front+1)%maxsize；

tq=Q[front]；

p=tq.bt；

i=tq.num；∥出队，取出结点及编号

if(BT[2*i]==‘#’‖2*i＞len)

p—＞lchild=null；

∥左子树为空，‘#’表示虚结点

else∥建立左孩子结点并入队列

{

p—＞lchild=(BiTree)malloc(sizeof(BiNode))；

∥申请结点空间

p—＞lchild——＞data=BT[2*i]；

∥左孩子数据

tq.bt=p—＞lchild；tq.num=2*i；rear=(rear+1)%maxsize；

∥计算

队尾位置

Q[rear]=tq；∥左孩子结点及其编号入队

}

if(BT[2*i+1]==‘#’‖2*i+l>len)

p—＞rchild=null；

∥右子树为空

else∥建立右孩子结点并入队列

{

p—＞rchild—(BiTree)malloc(sizeof(BiNode)；

∥申请结点空间

p—＞rchild—＞data=BT[2*i+1]；

tq.bt=p—＞rchild；

tq.num=2*i+1；

rear=(rear+1)%maxsize；

Q[rear]=tq；

∥计算队尾位置，右孩子及其编号入队

}

}

}29.参考答案：D不知道i，j的大小关系，所以无法确定。30.参考答案：

方法一：用顺序表作存储结构

structSqList/{

ElemType*elem；∥存储空间基址

intlength；∥当前长度

}；

voidInvertSqList(SqList＆L)

{

inti；ElemTypetemp；

for(i—0；i＜L．length/2；i++)

{

temp=L．elem；

L．elem=L．elem[L．1ength—i—1]；

L.elem[L.length—i—1]—temp；

}}

方法二：用顺序表作存储结构

voidInvertSqList(SqList&L)6R{

inti，j；ElemTypetemp；

i=0；j=L．length—1；

while(i＜j)

{

temp=L．elem；

L．elem=L.elem[j]

L.elem[j]=temp

i++；j——；

}}

方法三：用带头结点的单链表作存储结构

structLNode{

ElemTypedata；

LNode*next：

}；

typedefLNode*LinkList；

VoidInvertLinkList(LinkList&L)

{

p—L；L—NULL；

while(p){

s—p；p—p—＞next；

S—＞next—L：

}}31.参考答案：本题程序使用了一些C++的常用语句，如：“＜＜”输出符，“＞＞”输入符，“cout”输出到屏幕，“cin”从键盘输入，“endl”换行格式符，“new”动态存储分配。

PolynomialcreatePoly(){

structpnode*head,*p,*pre,*s;

floatc;inte,i=0;

cout＜＜”建立一个多项式的单链表”＜＜endl;

//提示

head=newTerm;

//创建表头结点和表头指针

head-＞exp=-1;head-＞link=NULL;

//表头结点的exp标志为-1

while(1){

//创建结点

cout＜＜”输入第”＜＜++i＜＜”个项:”;

//提示:输入第i个项

cin＞＞c＞＞e;

//输入:c系数,e指数

cout＜＜endl;

if(c==0)break;

//输入系数为0,退出

S=newTerm;s-＞coef:c;s-＞exp=e;

//创建结点

p=head;pre=NULL;

//寻找按升幂插入的位置

while(p!=NULL&&P-＞exp＞e){pre=p;p=p-＞link;}

if(p!=NULL&&p-＞exp==e)

//指数与链中某项指数相等

cout＜＜”输入项的指数重复,此次输入作废!”＜＜endl;

else{s-＞link=p;pre-＞link=s;}

//按升幂插入

}

returnhead;

}32.参考答案：C[解析]由二叉树的前序遍历序列和后序遍历序列不能唯一地确定这棵二叉树。但是利用二叉树前序遍历序列的第一个结点和后序遍历序列的最后一个结点为二叉树的根结点的特性，可以确定一棵二叉树，它的中序遍历序列为dbeacf。33.参考答案：C[解析]哈夫曼二叉树是只有度为2和度为0的结点的二叉树，有n个叶结点，就有n-1个非叶结点，其最大高度是n，即从第1层起到次底层止，每层有一个非叶结点，最底层有两个叶结点。例如，下图所示的哈夫曼树，n=5，叶结点的权值为{12，22，32，42，52}，该哈夫曼树的高度是5，所以具有5个叶结点的哈夫曼树的高度最高可以是5。

34.参考答案：

35.参考答案：D由完全图的定义可知本题答案为D。36.参考答案：n(n+1)/2(压缩存储)或n2(不采用压缩存储)。此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为1，2，3，…，n之和。37.参考答案：(1)邻接表定义：

typedefstructArcNode{

intadjvex;

struetArcNode*next;

}ArcNode;

typedefstructVNode{

vertypedata;

ArcNode*firstarc;

}VNode,AdjList[MAX];

(2)全局数组定义：

intvisited[]=0;finished[]=0;flag=1;

//flag测试拓扑排序是否成功

ArcNode*final=null;

//final是指向顶点链表的指针，初始化为0

(3)算法

voiddfs(AdjListg,vertypev){

//以顶点v开始深度优先遍历有向图g，顶点信息就是顶点编号

ArcNode*t;

//指向边结点的临时变量

printf("%d",v);

visited[v]=1;

p=g[v].firstarc;

while(p!=null){

j=p-＞adjvex;

if(visited[j]==1&&finished[j]==0)flag=0;

//dfs结束前出现回边

elseif(visited[j]==0){dfs(g,j);finished[j]=1;}

p=p-＞next;

}//while

t=(ArcNode*)malloc(sizeof(ArcNode));

//申请边结点

t-＞adjvex=v;t-＞next=final;final=t;

//将该顶点插入链表

}//dfs结束_

intdfs_Topsort(ndjlistg){

//对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回1，否则返回0

i=1;

while(flag&&i＜=n)

if(visited.[i]==0){dfs(g,i);finished[i]=1;}//if

return(flag);

}此题考查的知识点是图的遍历。对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。38.参考答案：C[解析]此结论需要考生当作定理一样的牢记。39.参考答案：本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。

voidDelete(BSTreebst,p,fp){

//在二叉排序树bst上，删除fp所指结点的左子女(由p所指向)

if(!p-＞lchild){fp-＞lchild=p-＞rchild;flee(p);}

//p无左子女

elseif(!p-＞rchild){fp-＞lchild=p-＞lchild;free(p);}

//p无右子女

else

//p有左子女和右子女

{q=p-＞rchild;s=q;

//用p右子树中的最小值代替p结点的值

while(q-＞lchild){s=q;q=q-＞lchild;}

//查p右子树中序序列最左结点

if(s==p-＞rchild)

//p右子树的根结点无左子女

{p-＞data=s-＞data;p-＞rchild=s-＞rchild;frees);}

else{p-＞data=q-＞data;s-＞lchild=q-＞rchild;free(q);}

}

}40.参考答案：

41.参考答案：D以元素C，D最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。42.参考答案：D根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C)-D/E，前缀表达式：-+A*BC/DE。43.参考答案：A[解析]对于不带头结点的单链表，first指向开始结点(第一个结点)，链表为空则first为空。对于带有头结点的单链表，first指向表头结点，链表为空则表头结点后面没有结点，即指针first→next为空。44.参考答案：A[解析]散列表的平均查找长度与处理冲突的方法有关，与装填因子a有关，与表的长度无关。45.参考答案：D最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。46.参考答案：(1)栈s1、s2共享向量空间，将两栈栈底设在向量两端。初始时，s1栈项指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。

(2)算法设计如下：

#definemaxsize

//两栈共享顺序存储空间所能达到的最多元素数

#defineelemtpint

//假设元素类型为整型

typedefstnlct{

elemtpstack[maxsize];

//栈空间

inttop[2];

//top为两个栈项指针

}stk;

stks;

//s是如上定义的结构类型变量，为全局变量

①入栈操作：

intpush(inti,intx){

//入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右

//边的栈s2，x是入栈元素。入栈成功返回1，否则返回0

if(i＜0||i＞1){

printf("栈号输入不对");exit(0);}

if(s.top[1]-s.top[0]==1){printf("栈已满\n");return(0);}

switch(i){

case0:s.stack[++s.top[0]]=x;return1;break;

case1:s.stack[--s.top[1]]=x;return1;

}

}

②退栈操作：

elemtppop(inti){

if(i＜0||i＞1){printf("栈号输入错误\n");exit(0);}

switch(i){

case0:if(s.top[0]==-1){printf("栈空\n");return-1;}

elsereturns.stack[s.top[0]--];

case1:if(s.top[1]==maxsize){printf("栈空\n");return-1;}

elsereturns.stack[s.top[1]++];

}

}47.参考答案：B输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。

分析选项A，输入序列为abed，输出序列为dacb，由输出受限性质可知以da开头的结果只有dabc，选项A为错误答案。

分析选项B，输入序列为abed，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba。再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。

分析选项C，输入序列为abed，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac，选项C为错误答案。48.参考答案：D[解析]含有n个结点的二叉排序树，其中序遍历序列都是一样的，前序遍历序列不同则对应了不同形状的二叉排序树，不同形态的个数可以用catalan函数计算：

catalan函数为(n为结点数)。

当n=4时，有。49.参考答案：BiTreeCreat(ElemTypeA[],inti){

//n个结点的完全二叉树存于一维数组A中，本算法

//据此建立以二叉链表表示的完全二叉树

BiTreetree;

if(i＜=n){

tree=(BiTree)malloc(sizeof(BiNode));tree-＞data=A[i];

if(2*i＞n)tree-＞lchild=null;

elsetree-＞lchild=Creat(A,2*i);

if(2*i+1＞n)tree-＞rchild=null;

elsetree-＞rchild=Creat(A,2*i+1);

}

return(tree);

}//Creat初始调用时i=1。50.参考答案：本题代码实现如下：

voidfun(inta[MaxLen][MaxLen],intn)//MaxLen是已经定义的常量

{

inti,j,k=0,m;

if(n%2==0)//m=□n/2□

m=n/2;

else

m=n/2+1;

for(i=0;i＜m;++i)

{

for(j=i;j＜n-i;++j)

{

++k;

a[i][j]=k;

}

for(j=i+1;j＜n-i;++j)

{

++k;

a[j][n-i-1]=k;

}

for(j=n-i-2;j＞=i;--j)

{

++k;

a[n-i-1][j]=k;

}

for(j=n-i-2;j＞=i+1;--j)

{

++k;

a[j][i]=k;

}

}

}51.参考答案：B此题考查的知识点是归并排序。第l遍归并的子序列长度为20，第2遍为21，…，第i遍为2i-1，所以由2i-1≥n知，对n个记录的数据集合，总共需要归并log2n次。应选B。52.参考答案：D[解析]判断一个有向图是否存在回路，可用的方法如下：

1)利用拓扑排序算法可以判定图中是否存在回路，即在拓扑排序算法结束后如果还有顶点没有输出，则说明剩下这些结点都还有前驱，它们构成一个有向回路。

2)设有向图具有n个顶点，若图的边数e≥n，则该图一定有一个闭合的环。

3)设图是具有n个顶点的有向图，若该图的每个顶点的出度至少为1，入度也至少为1，则图中一定有回路存在。

4)利用深度优先遍历算法可以判定一个有向图中是否存在有向回路。如果从有向图上的某个顶点v出发进行深度优先遍历，若在算法结束之前出现一条从顶点u到顶点v的回边，因u在生成树上是v的子孙，则有向图必定存在包含顶点v和顶点u的环。53.参考答案：A[解析]由二叉树的中序遍历规则可以知道，在中序遍历序列中，根结点右边只含有右子树上的结点。54.参考答案：(1)以居中的关键字值为根结点，按折半查找判定树的生成方法构造二叉排序树，既有好的平衡性又简单。算法代码如下：

voidCreate_BestBST(BTNode*&t,intlow,inthigh,intk[])

{

//low和high初始值分别为关键字值序列的下界和上界，t是创建

//子树的根。由于新根要回填给实参，所以它是引用型指针参数

if(low＞high)

t=NULL;

else

{

intmid=(low+high)/2;

t=(BTNode*)malloc(sizeof(BTNode));

t→data=k[mid];

Create_BestBST(t→lchild,low,mid-1,k);

Create_BestBST(t→rchild,mid+1,high,k);

}

}

这是一个递归算法，通过引用型参数t把新创建起来的子树根结点自动链接到父结点的某个子指针。

(2)根据上述算法得如下图所示的二叉排序树。

55.参考答案：本题主要考查直接插入法的算法思想及性能分析。

根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。

(1)在关键字自小到大有序的情况下，插入第i个(2≤i≤n)元素的比较次数为1，因此，总的比较次数为1+1+1+…+1=n-1。

(2)在关键字自大到小有序的情况下，插入第i个(2≤i≤n)元素的比较次数为i，因此，总的比较次数为2+3+4+…+n=[n(n+1)/2]-1=(n-1)(n+2)/2。

(3)在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为n-1。

(4)在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字时比较次数最少，此时前半部分的比较次数为m-1，后半部分的比较次数为(n-m-1)(n-m+2)/2，因此，总的比较次数为m-1+(n-m-1)(n-m+2)/2=(n-2)(n+8)/8(假设n为偶数，m=n/2)。56.参考答案：B根据二叉树的性质可知，度为0的结点个数比度为2结点个数多一个，即n0=n2+1。57.参考答案：本题的递归模型如下：

因此，实现本题功能的程序代码如下：

intlike(BTNode*t1,BTNode*t2)

{

intlike1,like2;

if(t1==NULL&&t2==NULL)

return1;

elseif(t1==NULL||t2==NULL)

return0;

else

{

like1=like(t1→left,t2→left);

like2=like(t1→right,t2→right);

return(like1&&like2);

}

}58.参考答案：此处循环体里面是i=i*2，即每循环一次，i值增加一倍，所以执行次数与n之间是以2为底的对数关系，故时间复杂度为O(log2n)。59.参考答案：A在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。60.参考答案：取平均值，将所有关键字与平均值进行比较，若小于平均值则属于左半部；否则就属于右半部。

intPartition(RecTyper[]，intl，h)

{

inti=l，j=h，avg=0；

for(；i＜=h；i++)

avg+=R[i].key；

i=l：

avg=avg/(h-1+1)；∥求得平均值

while(i＜j)

while(i＜j&&R[j]．key＞=avg)∥大于平均值

j——；

if(i＜j)

R[i]=R[j]；

while(i＜j&&R[i]．key＜=avg)∥小于平均值

i++：

if(i＜j)

R[j]=R[i]；

}

if(R[i]．key＜===avg)

return

i；

else

returni-1；

}

voidquicksort(RecTypeR[]，intS，T)；

{

if(S＜T)

{

k=partition(R，S，T)；

quicksort(R，S，k)；

quicksort(R，k+1，T)；

}

}61.参考答案：B一般情况下，在顺序表的第i(1＜=i＜=n)个元素之前插入一个元素，需要将第n至i的元素(共n-i+1个元素)向后移动一个位置。所以答案为B。62.参考答案：B此题考查的知识点是二部图的定义与存储。二部图定义为：若能将无向图G=＜V，E＞的顶点集V划分成两个子集V1和V2(V1∩V2)=使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。由于其特点，其存储矩阵必为分块对称的，所以选B。63.参考答案：B有n个结点且为完全二叉树的二叉排序树的高度为log2n。64.参考答案：D[解析]当一棵AVL树中的所有非叶结点的平衡因子都是0的时候，说明它每个非叶子结点的左、右子树都是一样高，则整棵树是一棵满二叉树。高度为h的满二叉树的结点个数等于2h-1。65.参考答案：intPartition(RecTypeR[],intn,inth){

//一趟快速排序算法，枢轴记录到位，并返回其所在位置

inti=n,j=h,R[0]=R[i],x=R[i].key;

while(i＜j){

while(i＜j&&R[j].key＞=x)j--;

if(i＜j)R[i]=R[j];

while(i＜j&&R[i].key＜=x)i++;

if(i＜j)R[j]=R[i];

}//while

R[i]=R[0];

returni;

}此题考查的知识点是快速排序的思想。66.参考答案：C堆排序是另一种基于选择的排序方法。n个元素的序列{k1，k2，k3，...kn}，当且仅当满足以下关系时，称之为堆：

ki＜=k2i

或者：

ki＞=k2i。

ki＜=k2i+1

ki＞=k2i+1

其中i=1，2，…，n/2。

若将同以上序列对应的一维数组看成是