2023年笔试题数据结构部分

数据结构

1.采用折半搜索算法长度为n的有序表时，元素的平均搜索长度为()

A)0(n2)

B)O(nlog2n)

C)O(log2n)

D)O(n)

2.下面程序的时间复杂度为()

for(inti=0;i<m;i++)

(

for(intj=O;j<n;j++)

(

a[i]U]=i*j；

)

)

A)0(m2);

B)O(n2);

C)O(m*n);

D)O(m+n);

3.下列叙述中，对的的是()

A)线性表中的个元素在存储空间中的位置必须是连续的

B)线性表中的表头元素一定存储在其他元素的前面

C)线性表中的个元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素

的前面

D)线性表中的个元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的

4.已知二叉树后序遍历序列是edcfba,中序遍历序列deacbf,它的前序遍历序列是();

5.假如进栈序列为el,e2,e3,e4,则也许的出栈序列是();

6,对长度为n的字符串进行字符定位运算的时间复杂度为();

A)O(l)

B)0(根号n)

C)O(nlog2n)

D)O(n)

7.n个顶点的连通图中边得条数至少为()

8.合并两个已经排好序的长度为n的Array<int>,最坏情况下需要比较多少次()

A)2n

B)2n-1

C)2n+1

D)n2

9.深度为5的满二叉树中，叶子结点的个数为()

A)32

B)31

C）16

D）15

10.冒泡排序算法和快速排序算法的时间复杂度分别是什么？

11.请简述数组和链表数据结构的特点及应用的场合？

12.下列哪些数据结构最适合医疗仪器设备中的大型数据量的插入，查找（）

A）数组

B）哈希表

C）红黑树/二叉平衡树

D）链表

13.下列哪些排序算法的平均时间复杂度是。（nlog2n）（）,哪些是稳定的排序（）

A）冒泡排序

B）希尔排序

C）快速排序

D）插入排序

E）堆排序

14.下列口那些说法是对的的：（）

A）二分查找法在一个长度为1000的有序整数数组查找一个整数，比较的次数不超过100次

B）在二叉树中查找元素的时间复杂度为。（Iog2n）；

C）对单向链表，可以使用冒泡排序;

D）对双向链表，可以使用快速排序;

15.已知某二叉树的后序遍历是DFBEGCA,中序遍历的顺序是DBFACEG,其前序遍历顺序是

16.下列代码将两个有序链表结合为一个，链表中的元素的排列顺序为从小到大。请补充其

中的空缺。

structnode

(

structnode*pnext;

intval;

)；

structnode*splice(structnode*plhs,structnode*prsh)

(

if()

returnprhs?prhs:plhs;

structnode*phead,*plast;

if()

(

phead=plast=prhs;

plhs=plhs->pnext;

)

else

(

phead=plast=plhs;

prhs=prhs->pnext;

)

while()

{

if(plhs->val<prhs->val)

(

plast->pnext=plhs;

plast=plhs;

plhs=plhs->pnext;

}

else

(

plast->pnext=prhs;

plast=prhs;

prhs=prhs->pnext;

)

)

plast->pnest=;

return;

)

17.比较哈希表和平衡二叉树的特点，他们分别用在哪些场合.

18.一个栈的入栈序列是A,B,C,D,E则栈的不也许的输出序列是()

A)EDCBA

B)DECBA

ODCEAB

D)ABCDE

19.在排序的方法中，关键码比较次数与记录地初始排列无关的是()

A)Shell

B)归并排序

Q直接排序

D)选择排序

20以下反向遍历array数组的方法有什么错误？

vectorarray;

array.push_back(l);

array.push_back(2);

array.push_back(3);

for(vector::size_typei=array.size()-l;i>=O;-i)

(

cout«array[i]«endl;

)

21.某火车站要通过一条栈道(先进后出)来调换进入车站的列车顺序，若进站的列车顺序

为A,B,C,则下列哪个出栈顺序不也许？

A)ABC

B)ACB

C)CAB

D)CBA

22.栈是一种是自能在某一端插入和删除的特殊线性表。他按照后进先出的原则存储数据，

先进入的数据被压入栈底，最后进入的数据在栈顶，

若6元素进入栈S的顺序为A.B.C.D.E.F出栈顺序为B.D.C.F.E.A,则S栈最小容量为？

A)3B)4C)5D)6

24.若完全二叉树的结点个数为2的N次方-1,则叶子结点个数为：

A)N-1

B)2*N

C)2(N-1)次方

D)2N次方

25.排序算法是稳定是指：关键码相同的记录排序前后相应位置不发生改变，下面哪种排序

算法是不稳定的？

A)插入排序

B)冒泡排序

C)快速排序

D)归并排序

26.下列说法中错误的是：

A)插入排序某些情况下复杂度为0(N)。

B)排序二叉树元素查找的复杂度也许为0(N).

C)对于有序列表的排序最快的是快速排序。

D)在有序列表中通过二分查找的复杂度一定是。(nlog2n)。

27.栈和队列的共同特点是()

28.栈通常采用的两种存储结构是（）

29.下列关于栈的叙述对的的是（）

A）栈是非线性结构

B）栈是一种树状结构

C）栈具有先进先出的特性

D）栈有后进先出的特性

30.链表不具有的特点是（）

A）不必事先估计存储空间

B）可随机访问任一元素

C）插入删除不需要移动元素

D）所需空间与线性表长度成正比

31.用链表表达线性表的优点是（）

32.循环链表的重要优点是（）

33.线性表L=（al,a2,a3,...ai,........an）,下列说法对的的是（）

A）每个元素都有一个直接前件和直接后件

B）线性表中至少要有一个元素

C）表中诸元素的排列顺序必须是由小到大或由大到小

D）除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件

34.线性表若采用链式存储结构时，规定内存中可用存储单元的地址（）

A）必须是连续的

B）部分地址必须是连续的

C）一定是不连续的

D）连续不连续都可以

35.树是结点的集合，它的根结点数目是（）

36.在深度为5的满二叉树中，结点的个数为（）

37.具有3个结点的二叉树有（）种形态

38.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（）

39.算法一般都可以用哪几种控制结构组合而成（）

40.下列叙述对的的是（）

A）算法的执行效率与数据的存储结构无关

B）算法的空间复杂度是指算法程序中指令（或语句）的条数

C）算法的有穷性是指算法必须能在执行有限个环节之后终止

D）算法的时间复杂度是指执行算法程序所需要的时间

41.数据结构作为计算机的一门学科，重要研究数据的逻辑结构、对各种数据结构进行的运

算，以及（）

42.下列叙述中，错误的是（）

A）数据的存储结构与数据解决的效率密切相关

B）数据的存储结构与数据解决的效率无关

C）数据的存储结构在计算机中所占的空间不一定是连续的

D）一种数据的逻辑结构可以有多种存储结构

46.根据数据结构中各数据元素之间前后件关系的复杂限度，一般将数据结构分为（）

43.下列数据结构中，按先进后出原则组织数据的是（）

A）线性链表

B）栈

C）循环链表

D）顺序表

44.下列关于栈的叙述中对的的是（）

A）在栈中只能插入数据

B）在栈中只能删除数据

C）栈是先进先出的线性表

D）栈是先进后出的线性表

45.应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其

存放在硬盘中的一个指定（）中，

当打印机空闲时，就会按先来先服务的方式从中取出待打印的作业进行打印。

46.下列关于队列的叙述中对的的是()

A)在队列中只能插入数据B)在队列中只能删除数据

C)队列是先进先出的线性表D)队列是先进后出的线性表

47.有一个C语言用来删除单链表的头元素的函数，请找出其中的问题并加以纠正。

voidRemoveHead(node*head)

(

free(head)

head=head->next

48.设单链表中节点的结构为：

typedefstructnode

(

Elemtypedata;〃数据

structnode*Link;//节点后继指针

JListnode;

(1)已知指针p所指节点不是尾节点，若在*p之后插入节点*s,则应执行下列哪一个操作?

A)s->link=p;p->link=s;B)s->link=p->link;p->link=s;

C)s->link=p->link;p=s;D)p->link=s;s->link=p;

(2)非空的循环单链表first的尾节点(由p所指向)满足：

A)p->link==NULL;B)p==NULL;

C)p->link==first;D)p==first;

49.如何证明一个表是循环链表？

52.假如一棵二叉树节点的前序序列是A、B、C,后序序列是C、B、A,则该二叉树节点的

中序序列是什么？

A)必为ABCB)必为ACBC)必为BCAD)不能拟定

53.什么是平衡二叉树？

54.下面的程序是一快速排序问题，请填空。

#include<iostream>

#include<stdio.h>

voidimproveqsort(int*list,intrnjntn)

(

int/*

for(i=0;i<10;i++)

printf(”％3d“,list[i]);*/

if(m<n)

(

i=m;j=n+l;k=list[m];

while(i<j)

for(i=i+l,i<n.i++)

if(list[i]>=k)

break;

for(j=j-lj>mzj-)

if(list[j]<=k)

break;

if(i<j)

{t=list[i];list[i]=list[j];list[j]=t;}

}

t=list[m];list[m]=list[j];list[j]=t;

improveqsort();

improveqsort();

)

}

main()

(

intlist[10];

intn=9,m=O,i;

printf("input10number:");

for(i=0;i<10;i++)

printf("\n")；

improveqsort(list,m,n);

for(i=0;i<10;i++)

printf("%5d",list[i]);

printf("\n");

55.以下哪种排序属于稳定排序？

A)归并排序B)快速排序C)希尔排序D)堆排序

56.用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较多少次?

A)5B)2C)4D)1

57.下面那种排序法对1234567最快？

A)quicksortB)bubblesortC)mergesort

58.解释一下什么是哈夫曼编码问题？

59.假设执行语句Q的时间是。(1),则执行下列程序段的时间为()

for(inti=l;i<=n;i++)

for(intj=i;j<=n;j++)

Q；

A.O(n)B.O(n2)C.O(n*i)D.0(n+l)

61.一棵有124个叶结点的完全二叉树，最多有()个结点

A.247B.248C.249D.250

63.下列排序算法中，在待排序数据有序的情况下，花费时间最多的是()

A.快速排序

B.希尔排序

C.冒泡排序

D.堆排序

64.有1000个无序的整数，希望使用最快的方式找出前50个最大的，最佳的选择是()

A.冒泡排序

B.基数排序

C.堆排序

D.快速排序

65.下列哪个不是用来解决哈希表冲突的开放地址法()

A.线性探测法

B.线性补偿探测法

C.拉链探测法

D.随机探测法

66.假设把整数关键码K散列到有N个槽的散列表，以下哪些散列函数是好的散列函数_

A.h(k)=k/N;

B.h伙)=1;

C.h(k)=kmodN;

D.h(k)=(k+Random(N))modN,random(N)返回一个0到N-1的整数

68.下面算法的时间复杂度是,

intf(unsignedintn)

if(n==O||n==l)

return1;

elsereturnn*f(n-l);

)

A.O(l)

B.O(n)

C.O(nA2)

D.O(n!)

69.对于一个具有n个顶点的无向图，若采用邻接表表达，则存放表头节点的数组大小为

A.n

B.n+1

C.n-1

D.n+边数

70.考虑一个特殊的hash函数h,能将任一字符串hash成一个整数k,其概率为P(k)=2八(-k)。

k=1,2…。对一个位未知大小的字符串集合S中的

每一个元素取hash值所组成的集合为h(S)。若h(S)中最大的元素maxh(S)=10,那么S的大

小的盼望是

A.5

B.10

C.512

D.1024

71.对于顺序存储的线性数组，访问结点和增长，删除结点的时间复杂度为一.

A.O(n),O(n)

B.O(n),O(l)

C.O(l),O(n)

D.O(1),O(1)

75.递归式的先序遍历一个n节点，深度为d的二叉树，需要栈空间的大小为一.

A.O(n)

B.O(d)

C.O(logn)

D.(nlogn)

76.关于排序算法的以下说法，错误的是一

A.快速排序的平均时间复杂度为O(nlogn),最坏的时间复杂度为0(n2)

B.堆排序的平均时间复杂度为O(nlogn),最坏的时间复杂度为O(nlogn)

C.冒泡排序的平均时间复杂度为0(n2),最坏的时间复杂度为0(n2)

D.归并排序的平均时间复杂度为。(nlogn),最坏的时间复杂度为0(n2)

77.某二叉树的前序遍历序列为-+a*b-cd/ef,后序遍历序列为abcd-*+ef/-,问其中序遍历序

列是一.

78.某缓存系统采用LRU淘汰算法，假定缓存容量为4,并且初始为空，那么在顺序访问以

下数据项的时候1,5,1,352,4,1,2出现缓存直接命中的次数是1最后缓存中即将准

备淘汰的数据项是.

79.有两个较长的单向链表a和b,为了找出结点node满足nodeina并且nodeinb。请设计

空间使用尽量小的算法。

80.当存储数据量超过单节点数据管理能力的时候，可以采用的办法有数据库sharding的

解决方案，也就是按照一定规律把数据

分散存储在多个数据管理结点N中(节点编号为0,1,2…N-1).假设存储的数据是a,请完毕

为数据a计算存储节点的程序。

#defineN5

inthashfintelement){

returnelement*;

}

intshardinglndex(inta){

intp=hash(a);

returnp;

82.具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左右孩

子，其余一个指针域为空

A.50

B.99

C.100

D.1O1

83.请实现一个快速排序算法，仅考虑被排序对象为整数的情况。

84.一颗二叉树高度为h,所有节点的度或为0,或为2,则这颗二叉树最少有()结点

A.2h

B.2h-1

C.2h+1

D.h+1

85.在百度或淘宝搜索时，每键入字符都会出现搜索建议，实现这类技术后台采用的数据结

构是.

86.设哈弗曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该哈弗曼树中总共

有()个空指针域：

A.2m-1

B.2m

C.2m+1

D.4m

87.后缀式ab+cd+/可用下面哪个表达式来表达：

A.a+b/c+d

B.a+b/(c+d)

C.a+b+c/d

D.(a+b)/(c+d)

88.给定一个数组11315762139194,每次操作可以互换不含反复数字的多对数，求至少

需要多少次操作才干使数组递增有序，

比如互换(11,3)(15,7)(6,2)只算一次操作，而互换(11,3).(3,2)算两次操作

A.6

B.5

C.2

D.3

89.写一个函数，去除一个字符串中的所有反复字符，规定在原字符串上进行操作，不可以

使用库函数，空间复杂度。(1)。

例如：输入字符串为”aabbbca“，则去重后的字符串为“abc“

90.如何判断一个二叉树是不是对称二叉树。(对称必须是左右子树对称，且相应节点的值也

相同)

91.某个车站呈狭长型，宽度只能容下一台车，并且只有一个出入口，已知某时刻该车站状

态为空，从这一时刻开始的出入记录为：

“进，出，进，进，进，出，出，进，进，进，出，出”假设该车辆入栈的顺序为1,2,3……,

则车辆的出栈顺序为()

A.1,2,3,4,5

B.1,2,4,5,7

C.1,4,3,7,6

D.1,4,3,7,2

92.将数组｛8,23,4,16,77,-5,53,100｝中的元素按从小到大的顺序排列，每次可以互换任意两个

元素，最少需要互换()次

A.4

B.5

C.6

D.7

94.完全二叉树和满二叉树的联系和区别？

95似下序列中不符合堆定义的是()

A.(102,87,100,79,82,62,84,42,22,12,68)

B.(102,100,87,84,82,79,68,62,42,22,12)

C.(12,22,42,62,68,79,82,84,87,100,102)

D.(102,87,42,79,82,62,68,100,84,12,22)

96.使用cache命中率最高的替换算法是()

A.先进先出算法FIFO

B.随机算法RAND

C.先进后出算法FIL。

D.替换最近最少使用的块算法LRU

97.快速排序最坏情况下的时间复杂度是：()

A.0(nlog(n))

B.0(n2)

C.O(log(n))

D.0(n)

98.一个文本文献，大约有10000行，每行一个词，规定记录出其中最频繁出现的前十个词

(Ie表达单词的平均长度)，给出时间复杂度分析。()

A.max(O(n*le),O(n*lgl0))

B.min(O(n*le),O(n*lgl0))

C.O(n*le)

D.O(n*lglO)

99.关于数据结构和算法，以下说法对的的是()

A.数据的逻辑结构与所使用的计算机无关

B.数据的存储结构与数据解决的效率密切相关

C.数据的存储结构在计算机中所占的空间不一定是连续的

D.一种数据的逻辑结构只相应一种存储结构

E,算法的执行效率与数据的存储结构无关

F.算法的时间复杂度是指执行算法程序所需要的时间

G.在单链表中，只要指出表中任何一个节点的位置，就可以从他出发依次访问到链表中其

他所有节点

H.在一个单链表中，已知q所指结点是p所指节点的前驱结点，若在p和q之间插入结点

s,贝!I执行，s->next=p;q->next=s;

I.在一个单链表中，若删除p所指节点的后续结点，则执行p=p->next;p->next=p->next->next

J.使用链表，可随机访问链表中的任何一个元素

100.调用printf函数可以分解为九个过程，请写出他们的排列顺序.

A.call指令

B.EBP出栈

C.函数参数压栈

D.收回局部变量空间

E.EBP压栈

F.在栈上保存局部变量

G.函数参数出栈

H.ret指令

I.打印输出字符串

102.在以下几种数据结构中，在执行数量相称的查找，删除和插入操作时，综合性能最佳的

数据结构是：

A.双向链表

B.分块链表

C.穿线二叉树

D.堆

103.广告系统为了做地理位置定向，将IPV4分割为627672个区间，并标记了地理位置信

息，区间之间无重叠，用二分查找将IP地址映射到地理位置信息，

请问在最坏的情况下，需要查找多少步？

A.17

B.18

C.19

D.20

104.以入栈顺序作为输入，出栈作为输出，并以I代表入栈，。代表出栈，现将1,2,3,4顺序

入栈，则栈操作序列IIIIOOOO后，输出4321；与输出1234相相应

的栈操作序列为I0I0I0Q则若想得到输出为2314,则栈操作序列应为—.无法由栈操作序

列而得到的输出有。

105.设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序列建成

的初始堆为.

106.线性有序表(al,a2,a3j”.a256)是从小到大排列的，对一个给定的值k,用二分法检索

表中与K相等的元素，在查找不成功的情况下，最多需要检索次。

编程

1单链表

1：编程实现一个单链表的建立。

2：编程实现一个单链表的侧长。

3：编程实现一个单链表的打印。

4:编程实现一个单链表删除节点。

5：编程实现单链表的插入。

6：编程实现单链表的逆置。

2双链表

1：编程实现双链表的建立。

2：编程实现双链表的侧长。

3：编程实现双链表的打印。

4：编程实现双链表删除节点。

5：编程实现双链表的插入。

1：编程实现队列的入队。

2：编程实现队列的出队。

3：编程实现队列的侧长。

4：编程实现队列的打印。

1.一个学生的信息：姓名，学号，性别，年龄等信息，用一个链表，把这些学生信息连在

一起，给出一个age,在这些链表中删除学生年龄等于age的学生信息。

2.请用C或C++写出一个冒泡排序程序，规定输入10个整数，输出排序结果。

3.请用C或C++写出一个shell排序程序，规定输入10个整数，输出排序结果。

4.链表

structstudent

(

intm_Num;〃学号

doublem_dScore;〃分数

structstudent*m_pNext;〃下一个

1).构造一个有20名学生的单向链表。按顺序每名学生的分数值为，1,2,3,5,8,13…

2).求出他们的平均分。

5.请实现一个快速排序的算法。仅考虑排序的对象为整数的情况。

6.计算a的n次方是许多加密算法的基本操作，蛮力计算方法的时间复杂度是O(n),请设

计一个时间复杂度小于O(n)的算法，(假设计算结果可以使用long型存储)

7.给定一个数组a[n],我们希望构造数组b[n],其中b[i]=a[0]*a[l]...a[n-l]/a[i].在构造过程

不允许使用除法。

1.规定0(1)空间复杂度和0(n)时间复杂度。

2.除遍历计数器与a[n]b[n]外，不可使用新的变量(涉及栈临时变量，堆空间和全局静态变

量等)；

8.给定一个如下输入格式的字符串，(1,(2,3),(4,(5,6),7))括号内的元素可以是数字,

也可以是另一个括号。请实现一个算法消除嵌套的括号，

比如把上面的表达式变成：(123,4,5,6,7),假如表达式有误请报错。

9.相似度计算用于衡量对象之间的相似限度，在数据挖掘，自然语言解决中是一个基础性计

算。在广告检索服务中往往也会判断网民检索Query和广告Adword的

主题相似度。假设Query或者Adword的主题属性定义为一个长度为10000的浮点数组

Pr[10000](称之为主题概率数组)，其中Pr[i]表达Query或者Adword属于主

题ID为i的概率，而Query和Adword的相似度简化定义为两者主题概率数组的内积：即

sim(Query,Adword)=sum(QueryPr[i]*AdwordPr[i])(0<=i<=10000)«在

实际应用场景中，由于大多数主题概率都为0,所以主题概率数组往往比较稀疏，在实现时

会以一个紧凑型数组topic_info_t0的方式保存，其中100<=数组大小

<=1000,并按照topicjd递增排列，0<=topic_id<10000,0<topic_pr<l»

structtopic_info_t

(

inttopicjd;

floattopic_pr;

)；

现在给出Query的topicjnfo_t数组和N(N>=5000)个Adwords的topic_info_t数组，现规

定出与的相似度最大值。即

QueryAdwordsmax(sim(Query;Adword[i]))

(0<=i<N).

floatmax_sim(constvector<topic_info_t>&query_topic_info,

constvector<topic_info_t>adwords_topic_info[],

intadwords_number);

编写代码求时间复杂度最低的算法，并给出时间复杂度分析。

10.给一个单词a,假如通过互换单词中字母的顺序可以得到此外的单词b,那么b是a的

兄弟单词，比如单词army和mary互为兄弟单词。

现在要给出一种解决方案，对于用户输入的单词，根据给定的字典找出输入单词有哪些兄弟

单词。请具体说明数据结构和查询流程，规定期间和空间效率尽也许

的高？

11.系统中维护了若干数据项，我们对数据项的分类可以分为三级，一方面我们按照一级

分类方法将数据项分为A,B,C……若干类别，每一个级分类方法产生的类

别又可以按照二级分类方法分为a,b,c…若干子类别，同样，二级分类方法产生的类别又可

按照三级分类方法分为i,ii,iii…若干子类别，每个三级分类方法产生

的子类别中的数据项从1开始的编号。我们需要对每个数据项输出日记，日记的形式是

key-valueo写入日记的时候，用户提供三级类别名称，数据项编号和日

志的key,共五个key值，例如write（A,a,i,l,keyl）,获取日记的时候，用户提供三级类别名

称，数据项编号，共四个key值，返回相应的所有key-value,

例如get_log（A,a,i,l）,请描述一种数据结构来存储这些日记，并计算出写入日记和读出日记

的时间复杂度？

12.链表

structstudent

{

intm_Num;〃学号

doublem_dScore;〃分数

structstudent*m_pNext;〃下一个

}；

1）构造一个有20名学生的单向链表。按顺序每名学生的分数值为1,1,2,3,5,8,13…

2）求出他们的平均分

13眉泡排序（写出具体算法）：答题需注意程序的有效性，可行性，健壮性并体现严格，规

范的过程。

14.单链表反序（写出具体算法）：答题需注意程序的有效性，可行性，健壮性并体现严格，

规范的过程。

15.请写一个函数，功能是把一段字符串倒序：答题需注意程序的有效性，可行性，健壮性

并体现严格，规范的过程。

16.设计一个算法，把一个具有N个元素的数组循环右移K位，规定期间复杂度为O(N),

空间复杂度为O(l)o

17.一个单向链表，不知道头结点，一个指针指向其中一个节点，问如何删除这个指针指向

的结点.

18.编程得到以下算式的结果(规定计算的效率最高)

算式:1-2+3-4+5-6......N

19.请写出一个程序，把一段字符串里面的某个字符(也许出现几次)过滤掉，比如“abcdefg”

过滤掉e变成"abcdfg”。

规定算法复杂度。(n),空间复杂度。⑴(10)。

20.编写一个按单词反转字符串的函数，如给定输入hereis.com后变成.comishere

21.列出你知道的排序算法,并使用其中的任意一种排序算法实现int*sort(intarray[],int

length),array是一个待排整形数组，length是数组长度，

将排序结果以整型指针的形式输出。

22.编写一个函数，计算两个正整数的最小公倍数，规定用辗转相除法。

23.已知两个链表Listl和List2,均为增序，请把他们合并成一个链表，规定仍为增序，请

用递归实现。

24.编程求10000以内的素数，规定对算法进行适当优化。

25.（八皇后问题）在一个8*8的国际象棋棋盘上摆放八个皇后，使其不能互相袭击，即任

意两个皇后都不能处在同一行，同一列或同一斜线上。

请编程求出所有可行的摆法，规定用回溯法写出程序。

26.给定一个单链表和一个整数K,规定每隔K个元素翻转链表：

structnode

（

intkey;

structnode*next;

｝；

typedefnode*List;

实现该函数：int*kReverse（List*Head,intk）

比如：原始链表为：l->2->3->4->5->6

k=2翻转为:2->1->4->3->6->5

k=3翻转为:3->2->1->6->5->4

k=4翻转为:4->3->2->1->5->6

27.对于一个m*n的int矩阵，其每行自左向右是升序排列的，其每列自上向下是升序排列

的，现需要在其中查找整数elem,找届时返回elem所在位置。

请1）先写出思绪；2）自行定义函数接口然后编程实现，编程语言不限。

28.下面程序段的时间复杂度为（）

for(inti=O;i<m;i++)

for(intj=0;j<n;j++)

(

a[i]U]=i*j;

)

)

A.O(mA2)

B.O(nA2)

C.O(m*n)

D.O(m+n)

29.一个单向链表，不知道头结点，现在有一个指针指向其中一个节点，问如何从链表中删

除这个指针指向的节点？例如：单向链表L(1->2->3->4->5),

现有指针P指向节点3,现在要删除节点3,把链表L变成(1->2->4->5)

30.已知一颗二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,画出这颗二叉

树.

31.给定一个没有反复数据的整数数组，找出其中所有两个数相加之和等于2023的整数对，

并且打印出来。(请写出你的思绪，然后用代码实现出来)

32.已知两个集合A[5,2,7,4,3,9,9]B[5,3,1,9,2,6,2],写一段代码顺序打

印出这两个集合中反复的元素。尝试使你的代码时间复杂度最优,

请在代码之前写出你的思绪。

33.己知字母顺序是［d,g,c,f,b,e,a］请对输入的一组字符串input［3］={"dca”,“dfa”,

“cgd”},按照字母顺序进行排序并打印，本例的输出为：

1：dca

2：dfa

3：cgd

如何检测上述代码是达成质量标准的？

34.createafunctionforstringpadstart(Stringstring,intminlength,charpadChar);

returnastring,oflengthatleastminlength,consistingofstringprependedwithasmanycopies

ofpadCharasarenecessarytoreach

thatlength.

forexample:

padStart("7〃3'0')returns"007”

padStart(z/2023,：3/0,)returns//2023,/

35.有一个数组，里面由若干整数组成，除了一个整数外，其他都出现两次，如何快速找到

这个整数。例如：［1,