【真题】2021年10月自考02331数据结构试卷

绝密★考试结束前

全国2021年10月高等教育自学考试
数据结构试题
课程代码：02331

1 .请考生按规定用笔将所有试题的答案涂、写在答题纸上。
2 .答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

选择题部分

注意事项：
每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。

一、单项选择题：本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1 .下列关于数据项和数据元素的叙述中，正确的是
A.数据项只能是数值类型 B.数据项可以包含数据元素
C.数据元素是数据的基本单位 D.数据元素是由数据项组成的集合

2 .下列关于抽象数据类型的叙述中，正确的是
A.抽象数据类型与具体实现相关
B.抽象数据类型是由C语言本身提供的
C.抽象数据类型是C语言提供的类型的逻辑描述
D.抽象数据类型将数据定义和数据操作封装在一起

3 .设有初始为空的栈S,入栈序列是f, e, d, c, b, a,出栈序列是d, e, a, b, c, f,则需要为S分配的空间大小至少是
A. 2 B. 3 C. 4 D. 5

4 .指针head指向带头结点的单链表L的表头，结点结构为：I data | next |,其中，data为int型，next是指向后继结点的指针。指针p指向L中的首个数据结点，指针q指向P的后继结点。现要交换p、q所指向的两结点中的data值，下列选项中，不能完成该任务的操作是 •
A. head->next = q; p->next = q->next; q->next = p;
B. p->next = q->next; head->next = q; q->next = p;
C • q->next = p; p->next = q->next; head->next = q;
D. int temp = p->data; p->data = q->data; q->data = temp;

5 .采用行优先压缩存储方式保存6行6列对称矩阵A的上三角部分，每个元素占2个单元，若A中第一个元素％的存储地址是10,则元素a34的存储地址是
A. 22 B. 26 C. 34 D. 40

6 .已知广义表L = (((l,i),h),(x,i,a,o)),下列运算中，结果得到h的是
A. head( tail( L)) B. head( tail(head(L)))
C. head( head( tail( L))) D. head( head( tail( tail( L))))

7 .下列关于二叉树的叙述中，错误的是
A.二叉树可以为空
B .二叉树可以保存在数组中
C.二叉树中叶结点的个数多于度为1结点的个数
D.二叉树中叶结点的个数多于度为2结点的个数

8 .若二叉树的前序遍历序列是ABCD,中序遍历序列是ACDB,则其后序遍历序列是
A. ABDC B. ACDB C. CDBA D. DCBA

9 .对下图进行广度优先搜索遍历，正确的遍历序列是

A. bdeac B. badce C. acedb D. abced

10 .关于图G的深度优先生成树T1与广度优先生成树T2,下列叙述中正确的是
A. T1与T2 一定相同 B. T1与T2可能相同
C. T1与T2—定不相同 D. T1与T2中所含边数不相等

11 .对n个记录进行排序，最坏情况下，时间复杂度不是0(/)的排序方法是
A.直接插入排序 B.冒泡排序
C.快速排序 D.堆排序

12 .下列排序方法中，不宜在链表上实现的是
A.直接插入排序 B.快速排序
C.归并排序 D.基数排序

13 .若元素序列11,13,15, 7, 8, 9, 23, 2, 5是采用下列排序算法之一得到的第2趟排序后的结果，则该排序算法是
A.直接插入排序 B.冒泡排序
C.选择排序 D.二路归并排序

14 .在长度为〃 52100） 的有序线性表中进行二分查找，查找成功时，查找长度不多于4的关键字个数是
A. 4 B. 7 C. 15 D. 100

15 .将下列数据分别依次插入到初始为空的二叉排序树中，能得到高度最低二叉排序树的是
A. 9,7,2, 1,4, 10 B. 6,4, 1, 8, 10, 5
C. 5, 1,2, 6,3,4 D. 2,4, 7, 5, 8, 10

非选择题部分

注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

二、填空题：本大题共10小题，每小题2分，共20分。

16 .非空的带头结点的单循环链表中，终端结点的指针域指向的是链表的_____。

17 .已知循环队列存储在一维数组A[0..n-l]中，头指针是fhmt,尾指针是rear,初始时front的值和rear的值均是0,则第1个入队元素存储在数组中存储位置的下标是_____

18 .将中缀表达式9-（ 2+4*7）转换为后缀表达式的结果是_____。

19 .广义表G = （ 27, G） 的深度是_____。

20 .具有几521） 个结点的二叉树，采用二叉链表存储，空指针域的个数是_____。

21 .两个无向连通图均含有10个顶点，它们之间的边数差最大是_____。

22 .有向图G存在拓扑序列的条件是_____。

23 .若用C语言的数组A保存含/（”210） 个元素的大根堆，则第3大元素在A中的下标最大是 _____。

24 .分块查找又称为_____。

25 .非空的3阶B树中，每个非根结点中含有的关键字个数最少是_____。

三、解答题：本大题共4小题，每小题5分，共20分。

26 .链栈为什么不必设置头结点？

27 .已知字符集{ a, b, c, d, e }中各字符出现的频次分别为2, 3, 6, 8, 10,对字符集进行哈夫曼编码，字符a的编码是000,字符e的编码是11,则其余3个字符的编码分别是什么？

28 .设有向图G如题28图所示，给出图G的邻接矩阵。

题28图

29 .设有关键字16, 15, 32, 11, 6, 30,将它们依次保存在哈希表(长度为7的一维数组)中，哈希函数为H/) = 上mod7,采用线性探查法解决冲突。已知关键字16已放置在数组下标为2的位置。请画出哈希表。

四、算法阅读题：本大题共4小题，每小题5分，共20分。

30 .程序f30()创建了一个带头结点的含% (%23)个数据结点的单链表L, L前两个数据结点中的data值均为1,从第3个结点开始，结点的data值是其前两个结点data值之和。请在空白处填上适当内容将算法补充完整。

typedef struct node
{       int    data;
        struct node *next;
} myList;
myList *head=NULL;
void f30(int n)
{       int i;
        myList *p, *preOne;
        if(n<3) return;
        head = (myList *)malloc( sizeof(myList) ); // 建立头结点
        p = (myList *)malloc( sizeof(myList) ); // 建立第一个数据结点
        p->data=l ;p->next=NULL;
        head->next=p;preOne=p;
        p = (myList *)malloc( sizeof(myList) ); II 建立第二个数据结点
        p->data= 1 ;p->next=NULL;preOne->next=p;
        for (i=3; i<=n; i++ )
        {     p = (myList *)malloc( sizeoRmyList));
              p->data =    (1)   ;
              p->next=   ⑵   ；
              (3)    =p;
              preOne = preOne->next;
        }
return;
}

31 .已知图的邻接矩阵表示的存储结构定义如下，算法f31()统计图中各顶点的度，并返回最大度数。请在空白处填上适当内容将算法补充完整。

#define MaxVertexNum 100 //
typedef struct gra //
{ int vexs[ MaxVertexNum ]; //
int arcs[ MaxVertexNum ][ MaxVertexNum ]; //
最大顶点数
图
顶点数组
邻接矩阵
} MGraph;
int f31 (MGraph g, int vex) 〃g为图的邻接矩阵,vex为图g中的顶点数
{ int i, j, countmax=0, count;
for (i=0; i<vex; i++)
{ CD；
fbr(j=O;j<vex;j++)
iff (2) )
count -H-；
if ( count > countmax )
countmax = count;
}
return (3) :

32 .己知二叉排序树结点的数据类型定义及二叉排序树的某个算法f32()如下。

typedef struct node
{ int data;
struct node *left, *right;
} BstTree;
void f32(BstTree * root, int kl, int k2)
{ if ( root=NULL ) return;
if ( kl>k2 ) return;
f32( root->left, kl, k2 );
if (root->data >= kl && root->data <=k2 )
printf(”％d, ", root->data );
f32( root->right, kl, k2);
return;
}

请回答下列问题。
(1) f32()的功能是什么？
(2)对于题32图所示的二叉排序树T,调用f32(T, 100, 612)后的输出是什么？

题32图

33 .阅读程序，并回答下列问题。

int f33(int A[], int i, int j, int k)
{ int mid;
if(i<j)
{ mid = (i+j)/2;
if (A[mid]<k) return f33(A, mid+1, j, k);
else return f33(A, i, mid, k);
}
if (A[i]==k ) return i;
else return -1;
}

(1)若有 int a[6] = {3, 5, 7, 9, 11,15};,则执行 printf(“f33=%d\n”, f33(a, 0, 5, 7));后输出的内容是什么？
(2) f33()的功能是什么？

五、算法设计题：本题10分。

34.设n个整数存放在数组A中，请编写函数f34（ int A口，intn） ,将所有奇数调整到所有偶数之前。