2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解

2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.具有6个顶点的无向图至少应有______条边才能确保是一个连通图。A.5B.6C.7D.82.假设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列的最大容量为maxSize，除此之外，该队列再没有其他数据成员，则该队列的队满条件是______。A.Q.front==Q.rearB.Q.front+Q.rear＞=maxSizeC.Q.front==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%maxSize;3.下列二叉树中，不平衡的二叉树是

。

4.一个n阶矩阵A[0…n-1，0…n-1]采用一维数组s[0…n*n-1]按行序为主序，存放其上三角各元素，编写一个算法求出S[k]在A[i][j]中的位置和A[i][j]在S[k]中的位置。5.设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若不采用败者树，使用传统的顺序选小(简单选择排序算法)的方法，总的比较次数是______。A.20B.258C.396D.5006.编写一个算法，将用二叉链表表示的完全二叉树转换为二叉树的顺序表示，假设数据类型为int型。7.构建一个哈夫曼树，如果给定权值的个数为n，那么哈夫曼树的结点总数为______．A.不确定B.2nC.2n+1D.2n-18.在下列各种次序的线索二叉树中，______对查找指定结点在该次序下的后序效率较差。A.前序线索二叉树B.中序线索二叉树C.后序线索二叉树D.层次序线索二叉树9.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行______操作。A.s→next=p→next;p→next=s;B.p→next=s→next;s→next=p;C.q→next=s;s→next=p;D.p→next=s;s→next=q;10.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法?______A.分块B.顺序C.二分法D.哈希11.设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列0，下列语句中可用来计算队列元素个数的是______。A.(Q.rear-Q.front+maxSize)%maxSizeB.(Q.rear-Q.front)%mexSizeC.Q.rear-Q.front-1D.Q.rear-Q.front12.假设二叉树采用链接存储结构进行存储，t指向根结点，s所指结点为任意一个给定的结点，编写一个求出从根结点到p所指结点之间路径的函数。13.在10阶B树中根结点所包含的关键字个数最多为______，最少为1。A.7B.8C.9D.1014.利用串的基本运算，编写一个算法，删除串s1中所有的s2子串。15.线性表(a1，a2，…，an)以链式存储方式存储时，访问第i位置元素的时间复杂度为______。A.O(i)B.O(1)C.O(n)D.O(i-1)16.下列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，1517.若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式中最节省时间的是______。A.单链表B.双链表C.单循环链表D.顺序表18.在线性表中的每一个表元素都是数据对象，它们是不可再分的______。A.数据项B.数据记录C.数据元素D.数据字段19.已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2h一1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。20.设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号(‘(’和‘)’)是否配对的C语言描述算法：EXYX(E)；(注：算法中可调用栈操作的基本算法。)21.没有一个不带表头结点的单链表，表头指针为head。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针head指向原链表的最后一个结点。22.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[1..n]中时，数组中第i个结点的左孩子为

。A.A[2i](2i＜-n)B.A[2i+1](2i+1＜-n)C.A[i/2]D.无法确定23.以下关于图的叙述中，正确的是______。A.强连通有向图的任何顶点到其他所有顶点都有弧B.图与树的区别在于图的边数大于或等于顶点数C.无向图的连通分量指无向图中的极大连通子图D.假设有图G={V,{E}}，顶点集V'∈V，E'∈E，则V'和{E'}构成G的子图24.线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：

(1)用最少的时间在表中查找数值为x的元素。

(2)若找到将其与后继元素位置相交换。

(3)若找不到将其插入表中并使表中元素仍递增有序。25.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：

(1)25，84，21，47，15，27，68，35，20

(2)20，15，21，25，47，27，68，35，84

(3)15，20，21，25，35，27，47，68，84

(4)15，20，21，25，27，35，47，68，84

其所采用的排序方法是______。A.直接选择排序B.希尔排序C.归并排序D.快速排序26.下列有关图的说法中正确的是______。A.在图结构中，顶点不可以没有任何前驱和后继B.具有n个顶点的无向图最多有n(n-1)条边，最少有n-1条边C.在无向图中，边的条数是结点度数之和D.在有向图中，各顶点的入度之和等于各顶点的出度之和27.由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为

。A.24B.48C.72D.5328.最不适合用做链式队列的链表是______。A.带有队头指针的双向非循环链表B.带有队头指针的双向循环链表C.只带队尾指针的双向循环链表D.只带队尾指针的循环单链表29.由权值为8，4，5，7的4个叶结点构造一棵哈夫曼树，该树的带权路径长度为______。A.24B.36C.48D.7230.使用散列函数：

H(k)=3kmod11

采用链地址法处理冲突时，设计一个算法删除一个指定的结点。31.已知两个链表A和B分别表示两个集合，其元素递增排列。用C语言编写一函数，求A和B的交集，并存放于A链表中。32.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是______。A.先序遍历二叉树B.判断两个指定位置的结点是否在同一层上C.层次遍历二叉树D.根据结点的值查找其存储位置33.非空的循环单链表head的链尾结点(由p所指向)满足______。A.P→next==NULL;B.P==NULL;C.P→next==head;D.P==head;34.对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为______。A.5.5B.5C.39/8D.19/435.设计一个算法创建一个带权(路径)的无向图，要求被创建的图由用户输入，输出从V0到其他各个顶点的最短路程长度和路径。36.当采用邻接表方式存储带权连通图时，求最小生成树的Prim算法的时间复杂度为______。A.O(n)B.O(elog2e)C.O(n2)D.O(n3)37.假设以带头结点的单链表表示有序表，单链表的类型定义如下：

typedefstructnode{

DataTypedata：

structnode

*next

}LinkNode，

*LinkList；

编写算法，从有序表A中删除所有和有序表B中元素相同的结点。38.若对27个元素只进行3趟多路归并排序，则选取的归并路数为______。A.2B.3C.4D.539.对于一个使用邻接表存储的带权有向图G，试利用深度优先搜索方法，对该图中所有顶点进行拓扑排序。若邻接表的数据类型为graph，则算法对应函数的说明为

intdfs_toposort(graph*g)

若函数返回1，则表示拓扑排序成功，图中不存在环；若函数返回0，则图中存在环，拓扑排序不成功。在这个算法中嵌套调用一个递归的深度优先搜索算法为

dfs1(graph*g,intv)

在遍历图的同时进行拓扑排序，给出整个算法的实现。40.在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为______，如果加速这样的关键路径就能使整个工程提前完成。A.汇B.源C.桥D.潭41.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作______型调整以使其平衡。A.LLB.LRC.RLD.RR42.关于图(Graph)的一些问题：

(1)有n个顶点的有向强连通图最多有多少条边?最少有多少条边?

(2)表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?43.线性表的每一个表元素是否必须类型相同?为什么?44.设A是n×n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1…n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为______。A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-145.下列二叉排序树中，满足平衡二叉树定义的是______。

A．

B．

C．

D．46.设一棵二叉树的中序序列为badce，后序遍历为bdeca，则该二叉树前序遍历的顺序是______。A.adbecB.decabC.debacD.abcde47.设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点个数是______。A.n-1B.nC.n+1D.n+248.用链表表示线性表的优点是______。A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同49.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点的入边表中的边结点数为______。A.k1B.k2C.k1-k2D.k1+k250.对任何一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则一定有n0=n2+1。第1卷参考答案一.历年考点试题黑钻版1.参考答案：A[解析]有n个顶点的连通图，至少需要n-1条边才能保持图的连通。多一条边将形成回路，少一条边将变成非连通图。当n=6时，n-1=5。2.参考答案：C[解析]当队尾指针rear追上队头指针front时队列满。一般以牺牲一个存储单元来区分队列空和队列满。3.参考答案：C平衡二叉树的特点为：左、右子树深度之差的绝对值不大于1。4.参考答案：这是一道简单题，只要注意区分行主序和列主序即可：

已知S[k]，求A[i][j]的算法如下：

voidfindij(intk,intn,int&i,int&j)

{

i=(k+1)/n;

j=k%n;

已知A[i][j]求S[k]的算法如下：

voidfindk(inti,intj,int&k,intn)

{

k=i*n+j;

}5.参考答案：C[解析]5路归并就意味着在5个参加比较的记录中选择一个排序码最小的记录，用传统的方法需做4次比较，总共5×20=100个记录，需做99次选择最小记录的操作，需要的比较次数为99×4=396。6.参考答案：因为链表形式是递归的数据结构，所以使用递归算法最简单。将以t为根的二叉链表表示的二叉树转换为二叉树的顺序表示也可以采用递归算法，其思路是：假设子树的根t存放于T[i]，则可将它的左子女存放于T[2*i]，右子女存放于T[2*i+1]。

在主程序调用时，t应赋予root，i应赋予1(根结点在T[1]中)。

voidLinkList_to_Array(BTNode*t,intA[],intn,inti)

{

if(t==NULL)return;

if(i＞n)

{

cout＜＜"arraymemorylimit"＜＜endl;

return;

}

A[i]=t→data;

LinkList_to_Array(t→lchild,A,n,2*i);

LinkList_to_Array(t→rchild,A,n,2*i+1);

}7.参考答案：D哈夫曼树中只有度为0和度为2的结点，即N=n0+n2，而根据二叉树的性质：n0=n2+1，可知n0=n，那么n2=n-1，N=n+n-1=2n-1。8.参考答案：C[解析]对二叉树进行后序线索化后，寻找指定结点的后序下的后序结点比较麻烦。因为它首先要找到这个结点的父结点，再到其父结点的右子树中找后序下的第一个结点。9.参考答案：C10.参考答案：A[解析]由于题目只说明是线性表，因此排除二分法。哈希算法虽然有最快的查找效率，但建立哈希表无法适应动态变化的要求。在数据量大的查找中，顺序查找显然缺乏效率，因此应选择使用分块查找方法。11.参考答案：A[解析]为了做到让队列指针周而复始地在循环队列中遍历，可用取模(%)运算使得指针从存储数据末端直接移到存储数组的始端。12.参考答案：本题采用非递归后序遍历树t，当后序遍历访问到s所指结点时，stack中所有结点均为p所指结点的祖先，由这些祖先便构成了一条从根结点到p所指结点之间的路径。

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

intpath(BTNode*t,BTNode*s)

{

BTNode*stack[MaxSize];

BTNode*p;

inti,flag,top=-1;

//栈指针置初值

do

{

while(t)

//将t的所有左结点入栈

{

++top;

stack[top]=t;

t=t→left;

}

p=NULL;

//p指向当前结点的前一个已访问的结点

flag=1;

//设置t的访问标记为已访问过

while(top!=1&&flag)

{

t=stack[top];

//取出当前的栈顶元素

if(t→right==p)

//右子树不存在或已被访问，访问之

{

if(t==s)

//要访问的结点为要找的结点

{

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

cout＜＜stack[i]→data＜＜"";

return1;

}

else

{

--top;

p=t;

//p指向已被访问的结点

}

}

else

{

t=t→right;

//t指向右子树

flag=0;

//设置未被访问的标记

}

}

}while(top!=-1);

return0;

}13.参考答案：C[解析]根据B树的定义，10阶B树的根结点最多可以有9个关键字(m=10-1)，最少有1个关键字。14.参考答案：本题利用index()函数和删除子串的函数循环来实现。其程序如下：

voiddelall(Str*s1,Str*s2)

{

intn;

n=index(s1,s2);

while(n＞=0)

{

del(s1,n,length(s2));

n=index(s1,s2);

}

disp(s1);

}

其中del函数实现如下：

intdel(Str*s,intpos,intn)

//从串s中删除从位置pos开始的n个字符构成的子串

{

inti;

if(pos+n＞s-＞length)

return0;

for(i=pos+n-1;i＜s-＞length;++i)

s-＞ch[i-n]=s-＞ch[i];

s-＞length=s-＞length-n;

s-＞ch[s-＞length]='\0';

return1;

}15.参考答案：C此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第i个位置的元素时需要从头开始向后查找，平均查找次数为(n+1)/2，所以时间复杂度为O(n)，选C。16.参考答案：C堆排序是另一种基于选择的排序方法。n个元素的序列{k1，k2，k3，...kn}，当且仅当满足以下关系时，称之为堆：

ki＜=k2i

或者：

ki＞=k2i。

ki＜=k2i+1

ki＞=k2i+1

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

若将同以上序列对应的一维数组看成是一棵完全二叉树，则堆的含义表明：该完全二叉树的所有非终端结点均不大于(或不小于)其左、右孩子结点的值。由此，若{k1，k2，…kn)是堆，则堆顶元素(或完全二叉树的根结点)必定是该序列n个元素中的最小值(或者最大值)。

若将堆看成是一棵以k1为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这n个结点中的最小者(或最大者)。下图给出了两个堆的示例。

从堆的定义可以看出，若将堆用一棵完全二叉树表示．则根结点是当前堆中所有结点的最小者(或最大者)。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小(或次大)的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。

假设当前要进行筛选的结点编号为k，堆中最后一个结点的编号为m，且a[k+1]至a[m]之间的结点都已经满足堆的条件，则调整过程可以描述为：

(1)设置两个指针i和j，i指向当前(要筛选)的结点：|=k；j指向当前结点的左孩子结点：j=2*i；

(2)比较当前结点的左右孩子的关键字值，并用j指向关键字值较大的孩子结点。

if(j＜m&&a[j]．key＜a[j+1])．key)j++；

(3)用当前结点的关键字与j所指向的结点关键字值进行比较，根据比较结果采取相应的操作，即结束筛选或交换结点内容并继续进行筛选。实现这个操作的语句为：

if(a[i]．key＞a[j]．key)

break；

∥结束筛选操作

else{

temp=a[i]；a[i]=a[j]；a[j]=temp；

∥交换结点内容

i=j；

j=2*i；

∥准备继续筛选

}

可以将交换改进为：

if(a[i]．key＞a[j]．key)

break：

else

{a[i]=a[j]；i=j；j=2*i；}

堆排序的筛选算法：

voidsift(DataTypea，intk，intm)

{i=k；；j=2*i；temp=a[i]；

while(j＜=m)

if(j＜m&&a[j]．keyr＜a[j+1]．key)

j++；

if(a[i]．key＞a[j]．key)

break：

else

{a[i]=a[j]；

i=j；

j=2*i；

}

}

a[i]=temp；

}

堆排序完整的算法为：

voidheapsort(DataTypea，intn)

{h=n/2；

∥最后一个非终端结点的编号

for(i=h；i＞=1；i——)

∥初建堆，从最后一个非终端结点至根结点

sift(a，i，n)；

for(i=n；i＞1；i——)

∥重复执行移走堆顶结点及重建堆的操作

{

temp=a[l]；a[l]=a[i]．a[i]=temp；

sift(a，1，i-1)；

}

}

在堆排序中，除建初堆以外，其余调整堆的过程最多需要比较树深度次，因此，与简单选择排序相比时间效率提高了很多；另外。不管原始记录如何排列，堆排序的比较次数变化不大，所以说，堆排序对原始记录的排列状态并不敏感。

在堆排序算法中只需要一个暂存被筛选记录内容的单元和两个简单变量h和i，所以堆排序是一种速度快且省空间的排序方法。堆排序是一种不稳定排序，其时间复杂度为O(nlog2n)。17.参考答案：D本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，其特点如下：

(1)顺序表可以实现随机存取，其时间复杂度为O(1)。但在顺序表中，进行插入和删除操作需要移动大量的元素，其时间复杂度为O(n)；

(2)链表中只能实现顺序查找，其时间复杂度为O(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为O(1)。

本题中，线性表中常用的操作是取第i个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第i个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也不方便；双链表虽然能快速查找第i个元素的前驱，但不能实现随机存取。18.参考答案：C[解析]线性表是n(n≥0)个数据元素的有限序列。数据记录、数据字段是数据库文件组织中的术语。数据项相当于数据元素中的属性。

本题考查的依然是线性表的基本定义。19.参考答案：[解析]二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的，不按完全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。本题中的虚结点用‘#’表示。

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；

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

}

}

}20.参考答案：判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈．右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配

intEXYX(charE[]，intn)

//E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配

{charsE30]；

∥s是一维数组，容量足够大，用作存放括号的栈

inttop=0；

∥top用作栈顶指针

SEtop]=‘#’；

∥‘#’先入栈，用于和表达式结束符号‘#’匹配

inti=0；

∥字符数组E的工作指针

while(E[l]!=‘#’)

∥逐字符处理字符表达式的数组

switch(E[i])

{caSe‘(’：s[++top]=‘(’；i++；break；

case‘)’：if(s[top]==‘(’{top——；i++；break；)

else{printf(“括号不配对”)；exit(0)；}

case‘#’：if(sEtop]==‘#’){printf(“括号配对＼n”)；return(1)；}

else{printf(“括号不配对\n”)；return(0)；)∥括号不配对

default：i++；

∥读入其他字符，不作处理

}

}

本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况下是检查花括号(‘{’，‘}’)、方括号(‘[’，‘]’)和圆括号(‘(’，‘)’)的配对问题。编写算法中如遇左括号(‘{’，‘[’，或‘(’)就压入栈中，如遇右括号(‘)’，‘]’，或‘)’)，则与栈顶元素比较，如是与其配对的括号(左花括号、左方括号或左圆括号)，则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。

另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。21.参考答案：

voidInverse(LinkList&head){

//head设为引用型,因要返回head改变后的值

if(head==NULL)return;

//空表无需逆转

LinkedNode*p=head-＞link,*pr=NULL;

while(p!=NULL){

head-＞link=pr;

//逆转head指针

pr=head;head=p;p=p-＞link;

//指针前移

}

head-＞link=pr;

}22.参考答案：D如果2i+1＜=n，则左孩子为A[2i+1]，否则就没有左孩子。所以无法确定。23.参考答案：C强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若E'中的边对应的顶点不是V'中的元素时，则V'和{E'}无法构成图，D错误。24.参考答案：(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。

voidSearchExchangelnsert(ElemTypea[];ElemTypex)

//a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的

//元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序

{

low=0;

high=n-1;

//low和high指向线性表下界和上界的下标

while(low＜=high)

{

mid=(low+high)/2;

//找中间位置

if(a[mid]==x)break;

//找到x，退出while循环

elseif(a[mid]＜x)low=mid+1;

//到中点mid的右半去查

elsehigh=mid-1;

//到中点mid的左半去查

}

if(a[mid]==x&&mid!=n)

//若最后一个元素与x相等，则不存在与其后继交换的操作

{

t=a[mid];

a[mid]=a[mid+1];

a[mid+1]=t;

}

//数值x与其后继元素位置交换

if(low＞high)

//查找失败，插入数据元素x

{

for(i=n-1;i＞high;i--)

a[i+1]=a[i];

//后移元素

a[i+1]=x;

//插入x

}

//结束插入

}

//结束本算法

(2)算法讨论

首先是线性表的描述。算法中使用一维数组a表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体，对元素的引用应使用a.elem[i]。另外，元素类型就假定是ElemType，未指明具体类型。其次，C中一维数组下标从0开始，若说有n个元素的一维数组，其最后一个元素的下标应是n-1。最后，本算法可以写成三个函数，即查找函数、交换后继函数与插入函数，写成三个函数显得逻辑清晰、易读。25.参考答案：A可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。26.参考答案：D[解析]如果有向图中只有一个顶点，则此顶点没有前驱，也没有后继；对于无向图，图中顶点没有次序关系，所以也谈不上前驱和后继，因此选项A错误。

具有n个顶点的无向图最少可以有0条边，只有在连通图的情形下最少是n-1条边，因此选项B错误。

在无向图中，所有顶点的度数之和是边的条数的2倍，选项C错误。27.参考答案：D

生成的哈夫曼树如上图所示，路径长度为：3*(2+3)+2*(8+5+6)=53。28.参考答案：A[解析]即使是双向链表，如果是非循环链表，只有队头指针也是不够的。29.参考答案：C[解析]由权值为8，4，5，7的4个叶结点构造出的一棵哈夫曼树如下图所示。它的带权路径长度WPL的计算有两种方法：一是先求每一个叶结点的带权路径长度，加起来得到WPL=4×2+5×2+7×2+8×2=48；另一种方法是把所有非叶结点的权值加起得到WPL=24+9+15=48。

30.参考答案：实现本题功能的函数代码如下：

intdelnode(ints)

{

hashnode*p,*q;

inti;

i=(3*s)%M;

p=ht[i].next;q=p;

while(p!=NULL&&p-＞key!=s)

{

cout＜＜p-＞key＜＜endl;

q=p;

p=p-＞next;

}

if(p!=NULL&&p==q)

//p为第一个结点

{

ht[i].next=p-＞next;

free(p);

return1;

}

elseif(p!=NULL)

//p为其他结点

{

q-＞next=p-＞next;

free(p);

return1;

}

else

{

return0;

}

}31.参考答案：LinkedListla;

la=(LinkedList)malloc(sizeof(LNode));

la-＞next=ha;

//申请头结点,以便操作

pa=ha;

//pa是ha链表的工作指针

pb=hb;

//pb是hb链表的工作指针

pre=la;

//pre指向当前待合并结点的前驱

while(pa&&pb)

if(pa-＞data＜pb-＞data)//处理ha中的数据

{

pre-＞next=pa:

pre=pa;

pa=pa-＞next:

}

elseif(pa-＞data＞pb-＞data)

//处理hb中的数据

{

R=(LinkedList)malloc(sizeof(LNode));

//申请空间

R-＞data=pb-＞data;

pre-＞next=r;

pre=r;

//将新结点链入结果链表

pb=pb-＞next;

//hb链表中工作指针后移

}

else

//处理pa-＞data=pb-＞data;

pre-＞next=pa;

Pre=pa;

pa=pa-＞next;

//两结点数据相等时,只将ha的数据链入

pb=pb-＞next;

//不要hb的相等数据

}

if(pa!=null)pre-＞next=pa;

//将两链表中剩余部分链入结果链表

elsepre-＞next=pb;

free(la);

//释放头结点,ha、hb指针未被破坏

}

//算法Union结束[解析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。如果遇上相等的元素，只需记录一个，并同时向后移动链表工作指针。32.参考答案：B[解析]选项A、C、D运算的时间复杂度都是O(n)，而选项B的运算的时间复杂度为O(1)，因为对于指定位置p和q的两个结点，判断是否在同一层上，只需判断两者|log2p|=|log2q|是否成立。33.参考答案：C[解析]非空单循环链表的尾结点为p，则其后继结点为链表的头结点head，即p→next==head。34.参考答案：C[解析]在查找概率不等的情况下，前5个元素的查找概率均为1/8，后5个元素的查找概率均为3/40，则：

35.参考答案：本题属于基础题，考查图的创建和迪杰斯特拉算法。

intcost[maxSize][maxSize];

//cost为带权邻接矩阵

intdist[maxSize],n;

//dist为从V0到各顶点的最短路程

struct

{

intnum;

intpnode[maxSize];

}path[maxSize];

//path为从V0到各顶点的最短路径

voidcreatgraph()

//创建带权无向图

{

intitj,s,e,len,contin=1;

cout＜＜"顶点个数:";

cin＞＞n;

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

{

for(j=0;j＜n;++j)

cost[i][j]=cost[j][i]=up;

//up是已定义的最大值，表示无穷大

cost[i][i]=0;

}

cout＜＜"输入各边，以0，0，0表示结束：\n";

i=1:

while(contin==1)

{

cout＜＜"\t第"＜＜i＜＜"条边-＞顶点，顶点，边长:";

cin＞＞s＞＞e＞＞len;

if(s==0&&e==0&&len==0)

contin=0;

else

{

cost[s][e]=len;

++i;

}

}

}

voidshortdjs()

//求最短路径

{

ints[maxSize];

intmindisfdis,i,j,v0=0,u;

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

{

dist[i]=cost[v0][i];

path[i].pnode[0]=v0;

path[i].num=0;

s[i]=0;

}

s[v0]=1;

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

{

mindis=up;

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

if(s[j]==0&&dist[j]＜mindis)

{

u=j;

mindis=dist[j];

}

s[u]=1;

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

if(s[j]==0)

{

dis=dist[u]+cost[u][j];

if(dist[j]＞dis)

{

dist[j]=dis;

++(path[j].num);

path[j].pnode[path[j].num]=u;

}

}

++(path[i].num);/*将终点i添加到路径中*/

path[i].pnode[path[i].num]=i;

}

}

voiddispath()

//输出最短路径

{

inti,j;

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

{

if(dist[i]＜up)

cout＜＜dist[i];

else

cout＜＜"∝";

//显示无穷大

for(j=0;j＜path[i].num;++j)

cout＜＜"V"＜＜path[i].pnode[j]＜＜",";

}

}36.参考答案：B[解析]求最小生成树的Prim算法中，如果采用小根堆来组织那些一个端点在S中、另一个端点在V-S中的边，最坏情况下所有边都进一次堆，在堆内把权值最小的边调整到堆顶需要的时间是O(log2e)，则总的时间应是O(elog2e)。37.参考答案：

voiddeleted_list(LinkListA，LinkListB){

LinkListp，q，r；

r=A：

p=A—＞next；

q=B—＞next；

while(p!—NULL&&q!=NULL)

{

if(p—＞data＞q—＞data)

q=q—＞next

elseif(p—＞data＜q—＞data)

{

r=P：

p—p—＞next；

}

else

{

r—＞next=p—＞next；

free(p)；

p=r—＞next：

}

}}38.参考答案：B[解析]设需要的路数为m，则对于11个元素做m路归并排序所需趟数。当n=27，s=3时，则，m=271/3=3。39.参考答案：intvisited[Vnum];

intfinished[Vnum];//表示对顶点i的DFS搜索是否结束

voiddfs1(graph*g,intv,int&flag)

//在深度优先遍历时输出顶点号。若图中不存在环，则输出全部顶点

//号，即为有向图的顶点拓扑排序，否则将flag置为0

{

arcnode*p;

cout＜＜v＜＜"";finished[v]=0;

visited[v]=1;

p=g→adjlist[v].firstarc;

while(p!=NULL)

{

if(visited[p→adjvex]==1&&finished[p→adjvex]==0)

flag=0;

elseif(visited[p→adjvex]==0)

{

dfs1(g,p→adjvex,flag);

finished[p→adjvex]=1;

}

p=p→nextarc;

}

}

intdfs_topo