2025年数据结构导论自考经典试题及答案解析笔记.doc

全国1月高等教育自学考试

数据构造导论试題

課程代码：02142

一、单项选择題(本大題共15小題，每題2分，共30分)

在每題列出的四个备选项中只有一种是符合題目规定的，請将其代码填写在題后的括号内。錯选、多选或未选均无分。

1.結点按逻辑关系依次排列形成一条“锁链”的数据构造是(B)

A.集合 B.线性构造

C.树形构造 D.图状构造（任意两个結点可以邻接的构造）

2.下面算法程序段的時间复杂度為(C)

for(inti=0;im;i++)

for(intj=0;jn;j++)

a［i］［j］=i*j;

A.O(m2) B.O(n2)

C.O(mn) D.O(m+n)

3.线性构造是(A)

A.具有n（n≥0）个表元素的有穷序列 B.具有n（n≥0）个字符的有穷序列

C.具有n（n≥0）个結点的有穷序列 D.具有n（n≥0）个数据项的有穷序列

4.单链表中删除由某个指针变量指向的結点的直接后继，该算法的時间复杂度是(D)

注：1.插入与删除运算，

注：1.插入与删除运算，次序表与线性表的時间复杂度都為O（n）。

2.查找运算，次序表的時间复杂度為O（1）

单列表的時间复杂度為O（n）

C.O(log2n) D.O(n)

5.有关串的论述，对的的是(D)

A.串是具有一种或多种字符的有穷序列

B.空串是只具有空格字符的串

C.空串是具有零个字符或具有空格字符的串注：空串不等于空格串

D.串是具有零个或多种字符的有穷序列

6.栈的输入序列依次為1，2，3，4，则不也許的出栈序列是(D)

A.1243 B.1432

C.2134 D.4312(不符合后进先出原则)

7.队列是(A)

A.先进先出的线性表 B.先进后出的线性表（栈）

C.后进先出的线性表 D.随意进出的线性表

8.10阶上三角矩阵压缩存储時需存储的元素个数為(B)

A.11 B.56

C.100 D.101

9.深度為k（k≥1）的二叉树，結点数最多有(B)

A.2k个 B.(2k-1)个

C.2k-1个 D.(2k+1)个

10.具有12个結点的二叉树的二叉链表存储构造中，空链域NULL的个数為(B)

A.11 B.13注：孩子有n-1个，空子域有n+1个，指针域有2n个。

C.23 D.25

11.具有n个顶点的无向图的边数最多為(C)

A.n+1 B.n(n+1)

C.n(n-1)/2 D.2n(n+1)

12.三个顶点v1,v2,v3的图的邻接矩阵為，该图中顶点v3的入度為(B)

A.0 B.1

C.2 D.3

13.次序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相似的，且每个元素的关键字值不相似。用次序查找法查找時，平均比较次数约為(B)

A.0 B.30000

C.40000 D.60000

14.外存储器的重要特点是(B)

A.容量小和存取速度低 B.容量大和存取速度低

C.容量大和存取速度高 D.容量小和存取速度高

15.在待排数据基本有序的前提下，效率最高的排序算法是(A)

A.直接插入排序 B.直接选择排序

C.迅速排序 D.归并排序

二、填空題(本大題共13小題，每題2分，共26分)

請在每題的空格中填上对的答案。錯填、不填均无分。

16.数据的不可分割的最小标识单位是__数据项____，它一般不具有完整确定的实际意义，或不被当作一种整体看待。

17.运算分為加工型运算和引用型运算，读取操作是__引用____运算。

18.带有头結点的单向循环链表L（L為头指针）中，指针p所指結点為尾結点的条件是_p-next=L_____。

19.在双链表中，前趋指针和后继指针分别為prior和next。若使指针p往后移动两个結点，则需执行語句_P=P-next-next____。

注：1.向一种栈顶指针hs的栈中插入一种*s指针，须执行的操作為；s-next=hs;hs=s;

2.单列表中指针p要删除其背面的A結点（直接后继）需要执行的操作為：p-next=p-next-next

（下一种下一种原则）

20.元素s1，s2，s3，s4，s5，s6依次进入次序栈S，假如6个