2025年山西专升本考试真题及答案解析汇编.docx

山西省专升本考试试題

数据构造试題1(222)

一、是非題(下列各題，你认為对的的，請在題干的括号内打“√”，錯的打“×”。每題1分，共15分）

1、数据构造概念包括数据之间的逻辑构造，数据在计算机中的存储方式和数据的运算三个方面...............()

2、线性表中的每个結点最多只有一种前驱和一种后继。......()

3、从本质上看，文献是一种非线性构造。..................()

4、线性的数据构造可以次序存储，也可以链接存储。非线性的数据构造只能链接存储。.......................()

5、栈和队列逻辑上都是线性表。..........................()

6、单链表从任何一种結点出发，都能访问到所有結点........()

7、单链表形式的队列，头指针F指向队列的第一种結点，尾指针R指向队列的最终一种結点。.................................................()

8、对某一确定的可运用空间表，給定一串内存祈求，若采用最佳适配和初次适配这两

种措施之中的一种能满足该串祈求，则也一定能用另一种措施满足该串祈求。()

9、多维数组是向量的推广。..............................()

10、设串S=a1a2...ai...aj...an,则有ord(ai)ord(aj)。....()

11、设串S的長度為n,则S的子串个数為n(n+1)/2。...........()

12、一般树和二叉树的結点数目都可认為0。................()

13、在拓朴排序序列中，任意两个相继結点Vi和Vj都存在从Vi到Vj的途径。()

14、网络的最小代价生成树是唯一的。.....................()

15、磁带是次序存取的外存储设备。.......................()

二、填空題(每空1分，共10分）

1、在树构造里，有且仅有一种結点没有前驱，称為根。非根結点有且仅有一种(),且存在一条从根到该結点的()。

2、评价数据构造的两条基本原则是：()和()。

3、对于次序存储的栈，由于栈的空间是有限的，在进行()运算時，也許发生栈的上溢，在进行()运算時，也許发生栈的下溢。

4、对于单链表形式的队列，其空队列的F指针和R指针都等于()。

5、若S1=‘linked￡st,S2=ring,则S1//S2=()。

6、设根結点的层数為0，定义树的高度為树中层数最大的結点的层数加1。则高度為k的二叉树具有的結点数目，至少為(),最多為()。

三、单项选择題(在本題的每一小題的备选答案中，只有一种答案是对的的，請把你认為对的答案的題号，填入題干的括号内。多选不給分。每題3分，共9分)

1、对于次序存储的队列，存储空间大小為n，头指针為F，尾指针為R。若在逻辑上看一种环，则队列中元素的个数為......................()

⑴.R-F⑵.n+R-F⑶.(R-F+1)modn⑷.(n+R-F）modn

2、n个记录直接插入排序所需的记录最小移动次数是.......()

⑴.2(n-1)⑵.2n⑶.(n+3)(n-2)/2⑷.n2/2

3、既有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传給y。表达该遗传关系最适合的数据构造為..............................

⑴.向量⑵.树⑶.图⑷.二叉树

四、简朴应用題(第1題6分，其他題每題3分，共18分）

1已知稀疏矩阵如下：

⑴請写出该稀疏矩阵次序存储的带辅助行向量的二元组表达。

⑵請写出该稀疏矩阵链接存储的带行指针向量的单链表达。

2在包括n个关键码的线性表里进行次序查找，若查找第i个关键码的概率為pi，pi如下分布：p1=1/2,p2=1/4,......,pn-1=1/2n-1,pn=1/2n。求成功检索的平均比较次数。

3、设根結点的层数為0，定义树的高度為树中层数最大的結点的层数加1，试问高度為k≥1、非叶結点的度数等于1的树有多少棵？

4、給出下列二叉树的前序序列。

5、设二叉树t的对称序序列為BADCE，后序序列為BDECA，請給出二叉树。

五、综合題(每題4分，共16分)

1、假设有如下关键码及其散列函数值：