2024年2月23日发(作者：)

目前刚整理了 的试题 过几天 的也会上传上去

希翼对你有匡助。。。。。。。

答案与试题是配套的 选择题没有解析 有不懂得可以在文库上 我

2022

1-5 ：BCDBC 6-10：BADBA

41.该方法求得的路径不一定是最

短路径。例如，对于下图所示的带权

图，如果按照题中的原则，从A 到 C

的最短路径为 A→B →C，事实上其最

短路径为 A →D →C。

42. (1)算法的基本设计思想：定义两个指针变量p 和 q，初始时均指向头

结点的下一个结点。 P 指针沿链表挪移；当p 指针挪移到第 k 个结点时， q 指针

开始与 p 指针同步挪移；当 p 指针挪移到链表最后一个结点时， q 指针所指元素

为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。

(2)算法的详细实现步骤：

①count=0,p 和 q 指向链表表头结点的下一个结点；

②若 p 为空，转⑤；

③若 count 等于 k,则 q 指向下一个结点;否则,count=count+1;

④p 指向下一个结点， 转步骤②；

⑤若 count 等于 k,则查找成功,输出该结点的 data 域的值,返回 1;返回；

查找失败,返回 0;

⑥算法结束。(3)算法实现：

typedef struct LNode{

int data;

struct LNode * link;

} * LinkList;

int SearchN(LinkList list,int k){

LinkList p,q;

int count=0; /*计数器赋初值*/

p=q=list->link; /*p 和 q 指向链表表头结点的下一个结点*/

while(p!=NULL){

if(count

else q=q->link;/*q 移到下一个结点*/

p=p->link; /*p 移到下一个结点*/

}

if(count

查找成功*/

return (1);}//else}//SearchN

2022

1-5 ：DCDCB 6- 11 ：ACBBDA

41.

(1)构造的散列表如下

下标

0

1

2

3

4

5

6

7

8

9

关键字

7 14 8 11 30 18 9

(2)查找成功的平均查找长度:ASL 成功=12/7。

查找不成功的平均查找长度:ASL 不成功=18/7。

42.(1)给出算法的基本设计思想： 先将 n 个数据 x0x1…xp…xn- 1 原地逆置，

得到 xn- 1…xpxp- 1…x0,然后再将前 n-p 个和后 p 个元素分别原地逆置， 得到最终

结果:xpxp+1…xn- 1x0x1…xp- 1。

(2)算法实现：

void reverse(int r[],int left,int right){

int k=left,j=right,temp; //k 等于左边界 left,j 等于右边界 right

while(k

temp=r[k];

r[k]=r[j];

r[j]=temp;

k++;//k 右移一个位置

j--;//j 左移一个位置

}

}

void leftShift(int r[],int n,int p){

if(p>0&&p

reverse(r,0,n-1);//将全部数据逆置

reverse(r,0,n-p-1);//将前 n-p 个元素逆置

reverse(r,n-p,n-1);//将后 p 个元素逆置

}

}

(3)说明算法复杂性：上述算法的时间复杂度为 O(n),空间复杂度为 O(1)。

2022

1-5 ：ABBCC 6-10：DACBA

41.高分笔记 图 最后一题

42.(1)算法的基本设计思想： (5 分)

1) 比较笨的方法：将两升序序列归并排序，然后求其中位数，时间复杂度

是 O(n)，空间复杂度 O(n)。

2) 高效的方法：分别求两个升序序列 A 和 B 的中位数，设为 a 和b 。 如

果 a=b，则 a 或者b 即为所求的中位数。

原因：如果将两序列归并排序，则最终序列中，排在子序列 ab 前边的元素

为先前两序列中排在 a 和 b 前边的元素;排在子序列ab 后边的元素为先前两序列

a 和 b 后边的元素。所以子序列ab 一定位于最终序列的中间，有因为 a=b，显然

a 就是中位数。

如果 a≠b(假设 a< p>

原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如…

a…b…的序列浮现，中位数必然浮现在(a，b)范围内。因此可以做如下处理：舍

弃 a 所在序列A 之中比较小的一半， 同时舍弃 b 所在序列 B 之中比较大的一半。

在保留的两个升序序列中求出新的中位数 a 和b，重复上述过程， 直到两个序列

只含一个元素为止，则较小者即为所求中位数。

(2)算法实现(高效方法)：(8 分)

int Search(int A[], int B[], int n){

int s1,e1,mid1,s2,e2,mid2;

s1=0;e1=n-1;s2=1;e2=n-1;

while(s1!=e1||s2!=e2){

mid1=(s1+e1)/2;

mid2=(s2+e2)/2;

if(A[mid1]==B[mid2]) return A[mid1];

if(A[mid1]< p){//分别考虑奇数和偶数，保持两个子数组元素个数相等

if((s1+e1)%2==0){//若元素个数为奇数

s1=mid1;//舍弃 A 中间点以前部份且保留中间点

e2=mid2; //舍弃 B 中间点以后部份且保留中间点

}//if

else{//若元素个数为偶数

s1=mid1+1;//舍弃 A 中间点以前部份且保留中间点

e2=mid2; //舍弃 B 中间点以后部份且保留中间点

}//else

}//if

else{

if((s1+e1)%2==0){//若元素个数为奇数个

e1=mid1;//舍弃 A 中间点以后部份且保留中间点

s2=mid2;//舍弃 B 中间点以前部份且保留中间点

}//if

else {//若元素个数为偶数个

e1=mid1+1;//舍弃 A 中间点以后部份且保留中间点

s2=mid2;//舍弃 B 中间点以前部份且保留中间点

}//else

}//else

}//while

return (A[s1])

}//search

(3)上述所给算法的时间、空间复杂度分别是 O(log2n)和 O(1) 。(2 分)

因为每次总的元素个数变为原来的一半，所以有：

第一次：元素个数为 n/2=n/(21)

第二次：元素个数为 n/4=n/(22)

……

……

第 k 次：元素个数为 n/(2k)

最后元素个数为 2

则有 n/(2k)=2

解得 k= log2n – 1

因此：时间复杂度为 O(log2n)，而空间复杂度从上述程序中可看出为 O(1)。2022

1-5 ：BAABC 6-11 ：CCADAD

41.高分笔记 排序 最后一题

42. (1)算法思想：顺序遍历两个链表到尾结点时，并不能保证两个链

表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一

个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点了。由于两个链表从

第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一

个公共结点。于是得到算法思路：

①遍历两个链表求的它们的长度 L1，L2；

②比较 L1，L2，找出较长的链表，并求 L=|L1-L2|；

③先遍历长链表的 L 各结点；

④同步遍历两个链表，直至找到相同结点或者链表结束。

(2)算法的C 语言代码描述

LinkList Search_ First_ Common(LinkList L1,LinkList

//本算法实现线性时间内找到两个单链表的第一个公共结点

int len1=Length(L1),len2=Length(L2);

LinkList longList,shortlist;//分别指向较长和较短的链表

if(len1>len2){

longList=L1->next;

shortlist=L2->next;

L=len1-len2;//表长之差

}//if

else{

longList=L2->next;

L2){

L=len2-len1;//表长之差

shortlist=L1->next;}//else

While(L-- )

longList=longList->next;

while(longList!=NULL){

if(longList==shortList)//同步寻觅共同结点

return longList;

else{

longList=longList->next;

shortlist=shortlist->next;

} //else

}//while

return NULL;

}//Search_First_Common

(3)算法的时间复杂度为 O(len1+len2，) 空间复杂度为 O(1)。

2022

1-5 ：DCDBA 6- 10：CCDCA

41. (1) 给出算法的基本设计思想： (4 分) 算法的策略是从前向后扫描数组元素，

标记出一个可能成为主元素的元素Num。然后重新计数， 确认Num 是否是主元素。 算法

可分为以下两步： ①选取候选的主元素：挨次扫描所给数组中的每一个整数，将第一个遇

到的整数Num 保存到 c 中记录 Num 的浮现次数为1；若遇到的下一个整 数仍 等于Num

则计数加一，否则计数减一；当计数减到0 时，将遇到的下一个整数保存到c 中，计

数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描彻底部数

组元素。②判断 c 中元素是否是真正的主元素：再次扫描该数组，统计c 中元素浮现的

次数，若大于n/2，则为主元素；否则，序列中不存在主元素。

(2)算法实现：(7 分)

int Majority ( int A[ ], int n ) {

int i, c, count=1; / / c 用来保存候选主元素，count 用来计数

c = A[0]; / / 设置 A[0]为候选主元素

for ( i=1; i

if ( A[i] = = c ) count++; / / 对 A 中的候选主元素计数

else

if ( count > 0) count--;/ / 处理不是候选主元素的情况

else { / / 更换候选主元素，重新计数

c = A[i];

count = 1;

}//else

}//for

if ( count>0 )

for ( i=count=0; i

if ( A[i] = = c )

count++;

if ( count> n/2 ) return c; / / 确认候选主元素

else return -1; / / 不存在主元素

}//Majority

42. (1)采用顺序存储结构，数据元素按其查找概率降序罗列。(2 分) 采 用 顺

序 查 找 方 法 。 (1 分 ) 查 找 成 功 时 的 平 均 查 找 长 度 = 0.35×1+0.35

×2+0.15×3+0.15×4=2.1。(2 分)

(2) 【答案一】采用链式存储结构， 数据元素按其查找概率降序罗列， 构成单链表。

(2 分) 采用顺序查找方法。 (1 分) 查找成功时的平均查找长度=0.35×1+0.35×2+0.15

×3+0.15×4=2.1。(2 分) 【答案二】采用二叉链表存储结构，构造二叉排序树，元素存储

方式见下图。 (2 分)

2022

1-5 ：CBADC 6-11 ：DDDDBC

41 ．解答：考查二叉树的带权路径长度，二叉树的带权路径长度为每一个叶 子结点的深度与权值之积的总和，可以使用先序遍历或者层次遍历解决问题。

1)算法的基本设计思想：

①基于先序递归遍历的算法思想是用一个 static 变量记录 wpl，把每一个结点 的深度作为递归函数的一个参数传递， 算法步骤如下： 若该结点是叶子结点，

那 么变量wpl 加之该结点的深度与权值之积；若该结点非叶子结点， 那末若左子 树不为空，对左子树调用递归算法， 若右子树不为空，对右子树调用递归算法， 深度参数均为本结点的深度参数加一；最后返回计算出的 wpl 即可。

②基于层次遍历的算法思想是使用队列进行层次遍历， 并记录当前的层数，

当遍历到叶子结点时， 累计 wpl；当遍历到非叶子结点时对该结点的把该结点的

子树加入队列；当某结点为该层的最后一个结点时，层数自增 1；队列空时遍历

结束，返回 wpl

2)二叉树结点的数据类型定义如下：

typedef struct BiTNode{

int weight;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

3)算法代码如下：

①基于先序遍历的算法：

intWPL(BiTreeroot){

return wpl_PreOrder(root,0);

}//int

intwpl_PreOrder(BiTreeroot,intdeep){

static int wpl=0;//定义一个 static 变量存储 wpl

if(root->lchild==NULL&&root->lchild==NULL)//若为叶子结点，积累 wpl

wpl+=deep*root->weight;

if(root->lchild!=NULL)//若左子树不空，对左子树递归遍历

wpl_PreOrder(root->lchild,deep+1);

if(root->rchild!=NULL)//若右子树不空，对右子树递归遍历

wpl_PreOrder(root->rchild,deep+1);

return wpl;

}//wpl_PreOrder

②基于层次遍历的算法：

#defineMaxSize100 //设置队列的最大容量

int wpl_LevelOrder(BiTree root){

BiTree q[MaxSize]; //声明队列， end1 为头指针， end2 为尾指针

int end1, end2; //队列最多容纳MaxSize-1 个元素

end1=end2=0; //头指针指向队头元素，尾指针指向队尾的后一个元素

int wpl=0, deep=0; //初始化 wpl 和深度

BiTree lastNode; //lastNode 用来记录当前层的最后一个结点

BiTree newlastNode; //newlastNode 用来记录下一层的最后一个结点

lastNode=root; /lastNode 初始化为根节点

newlastNode=NULL; //newlastNode 初始化为空

q[end2++]=root; //根节点入队

while(end1!=end2){ //层次遍历，若队列不空则循环

BiTree t=q[end1++]; //拿出队列中的头一个元素

if(t->lchild==NULL&&t->lchild==NULL)

wpl+=deep*t->weight; //若为叶子结点，统计wpl

if(t->lchild!=NULL){ //若非叶子结点把左结点入队

q[end2++]=t->lchild;

newlastNode=t->lchild;

} //并设下一层的最后一个结点为该结点的左结点if(t->rchild!=NULL){ //处理叶节点

q[end2++]=t->rchild;

newlastNode=t->rchild;

}//if

if(t==lastNode){//若该结点为本层最后一个结点，更新 lastNode

lastNode=newlastNode;

deep+=1; //层数加 1

}//if

}//while

return wpl; //返回 wpl

}//wpl_LevelOrder

注意： 上述两个算法一个为递归的先序遍历， 一个为非递归的层次遍历，读

者应当选取自己最擅长的书写方式。 直观看去，先序遍历代码行数少，不用运用其他工

具，书写也更容易，希翼读者能掌握。 在先序遍历的算法中， static 是一个静态变量，

只在首次调用函数时声明 wpl 并赋值为 0，以后的递归调用并不会使得 wpl 为

0，具体用法请参考相关资料中的static 关键字说明，也可以在函数之外预先设

置一个全局变量， 并初始化。 无非考虑到历年真题算法答案通常都直接仅仅由一

个函数构成，所以参考答案使用 static。若对static 不熟悉的同学可以使用以下形

式的递归：

int wpl_PreOrder(BiTree root,intdeep){

int lwpl, rwpl; //用于存储左子树和右子树的产生的wpl

lwpl=rwpl=0;

if(root->lchild==NULL&&root->lchild==NULL)

//若为叶子结点，

计算当前叶子结点的wplreturn deep*root->weight;

if(root->lchild!=NULL) //若左子树不空，对左子树递归遍历

lwpl=wpl_PreOrder(root->lchild,deep+1);

if(root->rchild!=NULL) //若右子树不空，对右子树递归遍历

rwpl=wpl_PreOrder(root->rchild,deep+1);

return lwpl+rwpl;

}//wpl_PreOrder

C/C++语言基础好的同学可以使用更简便的以下形式：

int wpl_PreOrder(BiTree root,int deep){

if(root->lchild==NULL&&root->lchild==NULL) //若为叶子结点，积累 wpl

return deep*root->weight;

return(root->lchild!=NULL?wpl_PreOrder(root->lchild,deep+1):0)+

(root->rchild!=NULL?wpl_PreOrder(root->rchild,deep+1):0);

}//wpl_PreOrder

这个形式只是上面方法的简化而已，本质是一样的，而这个形式代码更短，在

时间有限的 情 况 下 更 具 优 势 ， 能 比 写 层 次 遍 历 的 考 生 节 约 很 多

时 间 ， 所 以 读 者 应 当 在 保 证 代 码 正 确 的 情况下，尽量写一些较短

的算法，为其他题目赢得更多的时间。但是，对于基础不扎实的考生，还

是建议使用写对把握更大的方法，否则可能会得不偿失。例如在上面的代

码中，考生容易忘记三元式(x?y:z)两端的括号，若不加括号，则答案就会是错

误的。

2022

1-5 ：DCCBD 6- 11 ：AACBBA

41.(1) 算法思想： 定义一个大小为N 的数组，初始化为0. 在遍历链表的同时将数

组中索引值为节点的值的绝对值的元素置 1. 如果此元素已经为 1，说明此节点之前已经

有与此节点的值的绝对值相等的节点， 需将此节点删除。

(2) 节点的数据结构定义如下：

typedef struct Node {

Int data;

Struct Node * next;

}Node;

(3) int a[n]; // 全局数组标志节点的绝对值的值是否浮现过

void DeleteABSEqualNode(Node * head) {

memset(a,0,n); // 初始化为0

if (head == NULL) { return NULL; }

Node * p = head;

Node * r = head

while (p != NULL) {

if (a[abs(p->data)] == 1){

//如果此绝对值已经在节点值的绝对值中浮现过则 删除当前节点

r->next = p->next; delete p; p = r->next;

} //if

else { //否则， 将数组中对应的元素置 1，并将指针指向下一个元素

a[abs(p->data)] = 1; r = p; p = p->next;

}//else

} //while

return head; }//DeleteABSEqualNode

只遍历一次链表，所以时间复杂度为O(n)，

因为申请大小为n 的数组，所以

空间复杂度为O(n)，(n 为节点绝对值的最大值)。

42. 1 邻接矩阵为：

(2) 0 行 3 列的元素的含义是顶点0 到顶点3 的最短距离为2.

(3) Bm 中非零元素的含义是： 假设此顶点位于i 行j 列，如果i==j，则表示到自己的距离为0；如果i≠j，则表示顶点 i 到达不了顶点j。

i 顶点