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

2023年自考类计算机类(工学类)数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.深度为k的二叉树，所含叶子的个数最多为

A.2KB.KC.2K-1D.2K-12.已知有一组长度为9的关键字序列为{22,63,72,54,97,17,37,80,92}，现在假设散列表的地址空间为T[0..10]，请用除余法构造散列函数，如果存在冲突问题，请用线性探查法解决冲突，并给出相应的散列表。3.排序的重要目的是为了以后对已排序的数据元素进行

A.打印输出B.分类C.查找D.合并4.对于一个非空的线性表，以下关于其逻辑结构特征的描述，错误的是______A.开始元素没有前趋B.终端元素没有后继C.内部元素有且仅有一个直接前趋和一个直接后继D.所有数据元素都既有前趋和后继5.______查找法的平均查找长度与元素个数n无关。6.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的

A.先序遍历B.中序遍历C.后序遍历D.按层遍历7.已知有如下一个关键字序列{96,47,104,32,73,136,15,38,90,180}，按照上述插入顺序构造一棵二叉排序树，则请给出二叉排序树的构造过程，说明其深度，并在等概率的条件下求出平均查找长度。8.无向图的邻接矩阵是______，并且主对角线上的元素的值为______。9.设s="IAMAATHLETE"，t="GOOD"，则执行下列串操作序列之后得到的suhl为______。

substr(sub1,s,5,2);substr(sub2,s,6,8);strcpy(t1,t);

strcat,(t1,sub2);strcat(sub1,t1);10.对表长为9000的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为______。11.假设一个循环队列的容量为50，对其进行人队和出队操作，则经过一段时间之后，有：

(1)front=35，rear=12；

(2)front=12，rear=35。

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

求：循环队列中元素的个数?12.已知散列函数为H(K)=Kmod12，键值序列为25,37,52,43,84,99,120,15,26,11,70,82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。13.已知森林F={T1，T2,T3,T4,T5)，各棵树Ti(i=1,2,3,4,5)中所含结点的个数分别为7,3,5,1,2，则与F对应二叉树的右子树中的结点个数为

A.2B.3C.8D.1114.在下面的排序方法中，不需要通过比较关键字就能进行排序的是

A.箱排序B.快速排序C.插入排序D.希尔排序15.设一个链栈的栈顶指针为ls，栈中结点两个字段分别为info和next，其中next是指示后继结点的指针，栈空的条件是______。如果栈不空，则退栈操作为p：=ls；______；dispose(p)。16.假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。

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

(2)A，B，C入队；

(3)A出队；

(4)B，C出队，此时队列为空。17.删除双向循环链表中*p的前驱结点(存在)应执行的语句是______。18.长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是

A.37/12B.62/13C.39/12D.49/1319.由权值为1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为______。20.假设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=______。21.如果需要对线性表频繁进行______或______操作，则不宜采用顺序存储结构。22.对长度为n的关键字序列进行堆排序的空间复杂度为

A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)23.以下有关数据结构的叙述，正确的是

A.线性表的线性存储结构优于链式存储结构B.二叉树的第i层上有2i-1个结点，深度为K的二叉树上有2k-1个结点C.二维数组是其数据元素为线性表的线性表D.栈的操作方式是先进先出24.______查找法的平均查找长度与元素个数n无关。25.以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在______上填充合适的语句。

pointerresearch_openhash(keytypeK,openhashHP)

{i=H(K);

/*计算K的散列地址*/

p=HP[i];

/*i的同义词子表表头指针传给P*/

while(______)p=p—＞next;

/*未达到表尾且未找到时，继续扫描*/

______;

}26.就文件而言，按用户的观点所确定的基本存储单元称为______。按外设的观点所确定的基本存储单元称为______。27.数组的长度是______，线性表的长度是______。28.在下面的程序中，语句S的执行次数为

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

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

{S;

}

29.树的前序遍历序列等同于该树对应二叉树的______遍历序列。30.假设一个顺序栈存放在S.data[max]中，max-1是其栈底，则判断栈满的条件是______，判断栈空的条件是______。31.对磁带上的顺序文件进行更新某个记录时，必须______整个文件。而在顺序文件的最后添加新的记录时，则不必______整个文件。32.若非连通无向图G含有21条边，则G的顶点个数至少为

A.7B.8C.21D.2233.在栈和队列中，存取数据的原则分别是______A.先进先出；先进先出B.先进后出；先进先出C.先进后出；先进后出D.进出的先后无所谓34.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是

A.队列B.栈C.线性表D.有序表35.以下为单链表的定位运算，分析算法，请在______处填上正确的语句。

intlocate_iklist(1klisthead,datatypex)

/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/

{p=head;j=O;

while(______){p=p—＞next;j++;}

if(p—＞data==x)return(j);

else{return(0);

}36.内部排序的方法有许多种，

方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。A.归并排序B.插入排序C.快速排序D.选择排序37.______与数据元素本身的内容和形式无关。38.从树的根结点到树中的其余结点之间的路径______惟一的。39.在分块查找法中，首先查找______，然后再查找相应的______。40.设有两个串p和q，求q在p中首次出现的位置的运算称为

A.连接B.模式匹配C.求子串D.求串长41.下列说法中正确的是

A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中的每个结点的度为2C.任何一棵二叉树中的度肯定等于2D.任何一棵二叉树中的度可以小于242.在一个具有N个顶点的无向完全图中，包含的边的总数是

A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/243.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的S和X的操作序列为______。44.

方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。A.归并排序B.插入排序C.快速排序D.选择排序45.对于数组，通常具有的基本操作有______种，它们分别是______。46.求下面算法中变量count的值：(假设n为2的乘幂，并且n＞2)

intTime

{intn

count=0;x=2;

while(x＜n/2)

{x*=2;count++;

}

return(count)

}47.设线性表L=(a1，a2，…，an)(n＞2)，表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为s和b，若检索不成功，则s和b的数量关系是______。48.对于栈顶指针为top的顺序栈S，判断栈空的条件是______A.S.top=0B.S.top＜0C.S.top=StackSize-1D.S.top=StackSize49.对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是

A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不确定50.已知完全二叉树T的第5层只有7个结点，则该树共有______个叶子结点。第1卷参考答案一.历年考点试题黑钻版1.参考答案：C2.参考答案：因为散列函数为：h(key)=key%11，则根据此函数得到上述关键字序列的散列地址为：(0,8,6,10,9,6,1,3,4)，前5个关键字在插入时，其相应的地址是开放地址，可以直接插入到T[0]，T[8]，T[6]，T[10]，T[9]中，在插入到6个关键字时，其散列地址6已被关键字72占用，所以探查h1=(6+1)%11=7。此地址开放，所以将关键字17插入到T[7]中，然后再依次将关键字34，80，92插入到相应的散列地址中即可。则相应的散列袁为：

3.参考答案：C4.参考答案：D[考点]非空线性表的逻辑结构特征

[解析]非空线性表的逻辑结构特征是开始元素没有前趋，终端元素没有后继，内部元素有且仅有一个直接前趋和一个直接后继。5.参考答案：散列表6.参考答案：A7.参考答案：根据二叉排序树的生成过程，我们可以得到如下二叉排序树的构造结果：

此二叉排序树的深度(即高度)为4，在二叉树上，要找到第i层上的结点恰好需要比较i次，而在此二叉排序树上，第1,2,3,4层上分别有1,2,3,4个结点，则在等概率的条件下，查找成功的平均查找长度为：

8.参考答案：对称零9.参考答案："AGOODATHLETE"10.参考答案：308.511.参考答案：如果一个循环队列的总容量为N，则当rear-front时，循环队列中的元素的个数为rear-front，当ear＜front时，循环队列中的元素的个数为N+(rear-front)。所以此题中：(1)循环队列中元素的个数为35-12=23；(2)循环队列中元素的个数为50+(12-35)=27。12.参考答案：

查找成功的平均查找长度为：(4*2+8)，12=4/313.参考答案：D14.参考答案：A15.参考答案：ls=null这是指链栈没有设置头结点的情况，一般情况下也不必设置ls：=ls↑.next；这一操作让头指针指示下一个结点16.参考答案：

根据队列的操作规则：进队时，将新元素插入到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相等。17.参考答案：p—＞prior=p—＞prior—＞prior;

p—＞prior—＞next=p;

(或p—＞prior—＞prior—＞next=p;

p—＞prior=p—＞prior—＞prior;18.参考答案：B19.参考答案：5520.参考答案：Q.front=4；Q.rear=6。

Q.front=8；Q.rear=1。

Q.front=2；Q.rear=5。[考点]循环队列的操作21.参考答案：插入

删除22.参考答案：B[解析]由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为0(1)，但它是不稳定的。23.参考答案：C24.参考答案：散列表25.参考答案：(P!=NULL)&&(p—＞ke