2023年自考类计算机类(工学类)数据结构历年高频考题带答案难题附详解

2023年自考类计算机类(工学类)数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.以下将ah，…am，和am+1…an，两个有序序列(它们相应的关键字值满足Kh≤Km，Km+1≤…Kn，)合并成一个有序序列Rh，…，Rn，(使其关键字值满足Kh，'≤…≤Kn，')。请分析算法，并在______上填充适当的语句。

voidmerge(lista,listR,inth,intm,intn)

{i=h;k=h;j=m+1;

while((i＜m)&&(j＜=n))

{if(a[i].key<=a[i].key){R[k]=______;______;}

else{R[k]=______;______;}

k++;

}

while(i＜=______){R[k]=a[i];i++;k++;)

while(j＜=______){R[k]=a[j];j++;k++;}

}

此算法的执行时间为______。2.对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是

A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不确定3.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是______。4.写出向某个有序文件中插入一个记录的程序。5.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为______。6.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序，则得到的结果为______。7.广义表的深度是指______。8.假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。

(1)队列为空(即没有任何元素进入)；

(2)A，B，C入队；

(3)A出队；

(4)B，C出队，此时队列为空。9.假设以带头结点的单链表表示有序表，单链表的类型定义如下：

typedefstructnode{

DataTypedata;

structnode*next

}LinkNode,*LinkList;

编写算法，从有序表A中删除所有和有序表B中元素相同的结点。10.在下面的程序中，语句S的执行次数为

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

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

{S;

}

11.一棵树中非叶子结点的个数为n，与树对应的二叉树中右子树为空的结点的个数为m，则m=______。12.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用

A.求关键路径的方法B.求最短路径的Dijkstra方法C.广度优先遍历方法D.深度优先遍历方法13.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是______的。14.以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在______上填充合适的语句。

intbinsearch(sqtableR,keytypeK)

{low=l;hig=R.n;/*置查找区间初值。low，hig分别标记查找区间的下、上界*/

while(low＜=hig)

{mid=(low+hig)/2;

switch

{caseK==R.item[i].key:return(mid);

/*找到，返回位置mid*/

caseK＜R.item[i].key:______.break;/*缩小区间*/

caseK＞R.item[i].key:______;break/*缩小区间*/

}

}

return(0);

/*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/

}15.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为

A.4B.5C.6D.716.对于如下一个有序的关键字序列{5,9,12,18,23,31,37,46,59,66,71,78,85)，现在要求用二分法进行查找值为18的关键字，则经过几次比较之后能查找成功?17.数据元素之间的逻辑关系称为数据的______结构。18.产生冲突现象的两个关键字称为该散列函数的______。19.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是______的。20.就文件而言，按用户的观点所确定的基本存储单元称为______。按外设的观点所确定的基本存储单元称为______。21.在循环双链表的p所指结点之后插入s所指结点的操作是

A.P—＞next=s；B.p—＞next=s；

s—＞prior=p；

p—＞next—＞prior=s；

p—＞next—＞prior=s；

s—＞prior=p；

s—＞next=p—＞next；

s—＞next=p—＞nextC.s—＞prior=p；D.s—＞prior=p；

s—＞next=p—＞next；

s—＞next=p—＞next；

p—＞next=s；

p—＞next—＞prior=s；

p—＞next—＞prior=s；

p—＞next=s；22.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是______。23.非空的单循环链表L的尾结点P↑，满足

A.P↑.next=NULL;B.P=NULL;C.P↑.next=L;D.P=L24.已知图G的邻接表如下图所示。

从顶点v1出发进行深度优先搜索，得到的深度优先搜索序列是______。25.在按照顺序存储方式存储的数组中，元素aij的存储地址应该是数组的______加上排在aij前面的元素所占用的单元数。26.对序列(8，13，26，55，29，44)从小到大进行基数排序，第一趟排序的结果是______A.(13，44，55，26，8，29)B.(13，26，55，44，8，29)C.(8，13，26，29，44，55)D.(29，26，8，44，55，13)27.对于如图所示的二叉树，请画出其顺序存储结构图。

28.假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0；写出依次执行下列操作后头、尾指针的当前值。

a，b，c，d，e，f入队，a，b，c，d出队；(1)Q.front=______；Q.rear=______。

g，h，i，j，k，1入队，e，f，g，h出队；(2)Q.front=______；Q.rear=______。

M，n，o，P入队，i，j，k，l，m出队；(3)Q.front=______；Q.rear=______。29.设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是______A.p-＞next-＞next==headB.p-＞next==headC.p-＞next-＞next==NULLD.p-＞next==NULL30.如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于右子树上所有结点的值，要得到各结点值的递增序列，应按下列哪种次序排列结点

A.先根B.中根C.后根D.层次31.散列函数的作用是：______。32.INITIATE()的功能是建立一个空表。请在______处填上正确的语句。

lklistinitiate_lklist()

/*建立一空表*/

{______;

______;

return(t);

}33.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是______。34.在下面的排序方法中，不需要通过比较关键字就能进行排序的是

A.箱排序B.快速排序C.插入排序D.希尔排序35.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较

个结点。A.nB.n/2C.(n-1)/2D.(n+1)/236.以下运算实现在循环队上的入队列，请在______处用适当的语句予以填充。

intEnCycQueue(CycquetaeTp*sq,DataTypex)

{if((sq—＞rear+1)%maxsize==______)

{error("队满");return(0);)

else{______;

______;

return(1);

}

}37.______与数据元素本身的内容和形式无关。38.与数据元素本身的形式、内容、相对位置、个数无关的是数据的

A.存储结构B.存储实现C.逻辑结构D.运算实现39.对于数组，通常具有的基本操作有______种，它们分别是______。40.假设一个循环队列的容量为50，对其进行人队和出队操作，则经过一段时间之后，有：

(1)front=35，rear=12；

(2)front=12，rear=35。

其中front和rear分别是队头和队尾指针。

求：循环队列中元素的个数?41.算法分析的目的是

A.辨别数据结构的合理性B.评价算法的效率C.研究算法中输入与输出的关系D.鉴别算法的可读性42.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。(1)在P结点之前插入S结点的语句序列是______；(2)在表首插入S结点的语句序列是______。

a

P—＞nex=S

b

P—＞next=P—＞next—＞next

cP—＞next=S—＞next

dS—＞next=P—＞next

e

S—＞next=L

f

Q=P

gwhile(P—＞next!=Q＞P=P—＞next

hwhile(P—＞next!=NULL)P=P—＞next

i

P=L

j

L=S43.散列表的目的是

A.插入B.删除C.快速查找D.排序44.在具有n个单元的循环队列中，队满时共有______个元素。45.栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表______和______运算的限定不一样。46.在单链表中，除了首元结点外，任一结点的存储位置是由______指示。47.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点vi表示)。

48.下面四种内排序方法中，要求内存容量最大的是

A.插入排序B.选择排序C.快速排序D.归并排序49.假设在图G中任意的顶点设为vi，此顶点对应的度为D(vi)，此图的顶点数为n。则边数e和度数之间的关系为______。50.如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的

A.前序B.中序C.后序D.层次序第1卷参考答案一.历年考点试题黑钻版1.参考答案：a[i]

i++

a[j]

j++

mn

P(n-h+1)2.参考答案：B3.参考答案：一个数据元素可能有多个直接前趋和多个直接后继4.参考答案：所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第3个参数，且设为d。若原文件中没有数据，则d写入文件；若有数据，则找到第1个比d大的数据i，先写入d，再将i和其后各数据写回文件中，可通过调用fseek函数采实现插入。相应程序为：

#include＜stdio.h＞

#include＜stdlib.h＞

#include＜io.h＞

#include＜fcntl.h＞

#defineLENsizeof(int)

voidmain(intargi,char**argc)

{intfp,i,d;

if(argi＜3)

{printf("filenameint\11")

exit(0);

}

d=atoi(argc[2]);

fp=open(argc[1],O_GREAT|O_RDWRIO_BINARY,s_IREAD|S_IWRITE);

while(1)

{if(read(fp,&I,LEN)!=LEN)

{write(fp，&d,LEN):

/*文件结束，d添加到文件尾端*/

break;)

if(i＞=d)

/*文件中读出数据i，若i＞=d，则先存d*/

{do

{fseek(fp,-1L*lan,SEEK_CUR);

/*文件指针后退1个记录*/

write(fp,&d,LEN);

/*d写到文件中*/

d=i;

/*原i作d，以便处理其他数据*/

}while(read(fp,&i,LEN)==LEN);

write(fp，&d,LEN);/*继续读数据，并判别文件是否结束*/

break;

}

}

close(fp);

}

/*main*/5.参考答案：O(n)6.参考答案：15,02,21,24,26,57,43,66,80,48,737.参考答案：广义表展开后所含括号的最大层数8.参考答案：

根据队列的操作规则：进队时，将新元素插入到rear所指的位置，然后将rear加1，front不变，出队时，删除front所指的元素，然后将front加1，rear不变，则有：A，B，C进队列后，rear指针指向3，front不变，A出队列时，删除A，将front加1，所以front指向1，rear不变，B，C都出队时，fron加2，rear不变，此时，rear和front相等。9.参考答案：参考答案一：

voidf34(LinkListha,LinkListhb)

{

//hb和hb分剐为存放A和B有序链表的头指针

LinkListp,q,r;

p=ha;

q=hb—＞next;

while(p—＞next&&q){

if(p—＞next—＞data＜q-＞data)

p=p—＞next;

else{

if(p—＞next—＞data==q—＞data){

r=p—＞next;

p—＞next=r—＞next;

free(r);

}

//从A表删除相同的元素结点

q=q—＞next;

}

}

}

参考答案二：

voidf34(LinkListha,LinkListhb)

{

//hb和hb分别为存放A和B有序链表的头指针

LinkListp,q,r;

r=ha;p=ha—＞next;

q=hb—＞next;

while(p&&q){

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

r=p;p=p-＞next;

}else{

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

r—＞next=p—＞next;

free(p);

p=r—＞next;

}

//从A表删除相同的元素结点

q=q—＞next

}

}

}10.参考答案：B11.参考答案：n+112.参考答案：D13.参考答案：稳定14.参考答案：hig=mid-1low—low+115.参考答案：C16.参考答案：根据二分查找的过程，我们可以得到如下的比较结果：

第一次比较：[5,9,12,18,23,31,37,46,59,66,71,78,85,]

↑

第二次比较：[5,9,12,18,23,31],37,46,59,66,71,78,85

↑

第三次比较：5,9,12[18,23,31],37,46,59,66,71,78,85

↑

第四次比较：5,9,12[18]23,31,37,46,59,66,71,78,85

↑

则从上面的比较过程我们可以看出：经过四次比较之后，就可以查找到值为18的关键字。17.参考答案：逻辑[考点]数据的逻辑结构的概念

[解析]数据元素之间的逻辑关系称为数据的逻辑结构。18.参考答案：同义词19.参考答案：稳定20.参考答案：逻辑记录

物理记录21.参考答案：D22.参考答案：选择排序23.参考答案：C24.参考答案：v1、v4、v3、v5、v2[考点]图的遍历

[解析]深度优先搜索(DFS)类似于树的先根遍历。深度优先遍历图的方法是从图中某顶点v出发：(1)访问顶点v；(2)依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；(3)若此时图中尚有顶点