2022年4月自考02331数据结构试题（历年真题）

2022年4月自考数据结构真题试卷出来了，免费下载哦，欢迎有需要的同学下载学习哦，此外还包含2022年4月高等教育自学考试全国统一命题考试真题试卷免费下载。

绝密★启用前

2022年4月高等教育自学考试全国统一命题考试数据结构

(课程代码02331)

注意事项：

• 本试卷分为两部分，第一部分为选择题，第二部分为非选择题。

2. 应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。
3. 涂写部分、画图部分必须使用2B铅笔，书写部分必须使用黑色字迹签字笔。

点击免费下载：2022年4月高等教育自学考试全国统一命题考试

第一部分选择题

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

1.下列数据结构中，与存储结构相关的是

1. 线性表 栈 C.链队列 D.二叉树

• 将20个数据元素的线性表存储在数组中，若第9个元素的存储地址是1000,第11 个元素的存储地址是1040,则最后一个元素的存储地址是

1. 1200 B. 1210 C. 1215 D. 1220
2. 设栈的初始状态为空，元素1,3, 5, 2, 4依次入栈，不能得到的出栈序列是
3. 5, 1,3, 2,4 B. 4, 2, 5, 3, 1
4. 2,4, 5,3, 1 D. 1,3, 5, 2, 4
5. 设指针变量p指向非空单链表中的结点，next是结点的指针域，现要删除p所指结 点的所有后继结点，则下列语句中正确的是
6. while (p != NULL) ( q = p; p = p->next; free(q); }
7. while (p != NULL) { q = p->next = p->next->next; free(q);}
8. while (p->next != NULL) (q = p->next; p = p->next; free(q); )
9. while (p->next != NULL) (q = p->next; p->next = p->next->next; free(q);}
10. 已知广义表 LS = (((a, b), (c, d)), (e, f, (g, h, i))), LS 的深度是
11. 2 B. 3 C. 4 D. 5
12. 已知一棵高度为4的完全二叉树T的第4层上共有3个叶子结点，则T中叶子结点 的个数是
13. 4 B. 5 C. 6 D. 7
14. 已知二叉树T的前序遍历序列为a,b,c,d,e,则前序遍历序列与T相同的不同二叉 树个数(不包含T)是
15. 11 B. 12 C. 13 D. 14
16. 釆用邻接矩阵存储含〃个顶点和e条边的有向图G,邻接矩阵中0的个数是
17. n><n-e B. n^-n-le C. n(w-l)/2-e D. m(m-1)/2-2c
18. 无向图中所有顶点的度数之和是10,则顶点的最大度数是
19. 5 B. 6 C. 7 D. 10
20. 设有向图G含有〃个顶点、e条边，使用邻接矩阵存储。对G求拓扑序列算法的时 间复杂度是
21. O(n) B. O(e) C. O(n²) D. O(*xe)
22. 对数据序列(15,12,13,12, 8,4, 5)采用冒泡排序进行升序排序，两趟排序后得到的排 序结果是

14. 在一棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子结点，则
15. n 一定大于m B. n 一定小于m
16. n 一定等于m D. n与m的大小关系不确定
17. 设散列表长m=14,散列函数H(key) = key%13。釆用线性探测法处理冲突。表中
    己按散列地址保存了 3个关键字16, 30, 18,此时存储关键字29的探查次数是
18. 1 B. 2 C. 3 D. 4

第二部分非选择题

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

16. 链栈、顺序队列的存储结构不同，数据的运算也不同，它们的 结构相同。
17. 若指针p和q分别指向单链表L中的两个相邻结点，且q指向的是终端结点。则在 p所指结点之后插入指针r所指结点的语句是r->next=q; ;。
18. 实现递归函数调用和返回的数据结构是 o
19. 广义表((a, b), (c, d), ((e, f), (g, h)))的表尾是 。
20. 已知完全二叉树的按层遍历序列存储在一维数组A[0..n-l]中，则A[i](lWiWn-l)的 父结点是 =
21. 如果有向无环图G中至少有两个顶点的入度为。，则G中至少有 个不同的 拓扑序列一
22. 将森林T转换为一棵二叉树T1,则T中叶子结点在T1中满足的条件为 。
23. 对含n个元素的数据序列采用二路归并排序算法进行排序，算法的时间复杂度是

24. 散列表的平均查找长度不是结点个数〃的函数，而是 ____的函数。
25. 假设顺序存储的有序表R含有13个关键字，进行二分查找时，查找成功时平均查 找长度为 O

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

26. 设电文字符集是(e_be₂,e₃,e4, e₅,e₆),各字符出现的频次分别为｛20, 21,1, 15,22,3｝。 现要为该字符集设计哈夫曼编码。请回答下列问题。

(1)给出构造的哈夫曼树。

(2)给出各字符的哈夫曼编码。

27. 已知图G釆用邻接矩阵存储，邻接矩阵如题27图所示。

题27图

(1)根据邻接矩阵画出图G。

(2)写出图G的从顶点A开始的1个拓扑序列。

28. 有数据序列(15,16,04,12,21,23,43,31,16,13),使用希尔排序方法将其排成升序 序列。请回答下列问题。

• 分别写出增量序列的取值依次为4, 1的希尔排序结果。
• 计算增量为4时希尔排序中数据元素之间的总交换次数(两个元素之间的交换 记1次)。

29. 设二叉排序树T如题29图所示。现需在T中删除结点22。请回答下列问题。

• 删除结点22有几种不同的方法？
• 分别画出对应于(1)中不同方法删除结点22后的二叉排序树。

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

30. 顺序表类型定义如下：

tfdefine ListSize 100

typedef struct {

int data[ ListSize ];

int length;

) SeqList;

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

int mean (SeqList *SL)

( int length, meanvalue, k = 0;

length = SL->length;

mean value = 0;

while( k < length)

( meanvalue += SL->data[k];

k++;}

return meanvalue/length;

int f30( SeqList *SL1, SeqList *SL2 )

( int SI = mean(SLl);

int S2 = mean(SL2);

if ( Sl> S2 ) return SI;

else return S2;}

• 若 SLl->data 中的数据为(13, 12, 23, 7, -27, 36, 123, 52, 31), SLl->length=9, SL2->data 中的数据为(-7, 17, -23, 18, 37, 22, 41, 15), SL2->length=8 则调用函 数f30(&SLl, &SL2)后的返回值是什么？
• 函数f30 ()的功能是什么？

31. 二叉树的存储结构类型定义如下：

typedef char Datalype;

typedef struct node

{ DataType data; // data 是数据域

struct node * Ichild, * rchild; // 分别指向左右孩子

)BinTNode;

typedef BinTNode * BinTree;

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

voidDl(BinTreeT)

( if(T!=NULL)

( printf( ⁿ%c “, T->data );

f31(「>rchild);

f31(T->lchild);}

return;}

(1)设二叉树T如题31图所示，给出执行f31(T)的输出结果。

（2）给出该算法的时间复杂度。

32. 待排序记录的数据类型定义如下:

#define MAXSIZE 100

typedef int KeyType;

typedef struct (

KeyType key;

} RecType;

typedef RecType SeqList [ MAXSIZE ];

下列函数f32 ()的功能是用直接插入排序对顺序表按升序进行排序，请在空白处 填上适当内容使算法完整。

void f32( SeqList R, int n)

{ int i,j;

RecType temp;

fbr(i=l;iv=n-l；i++)

{ temp = R[i];

) BinTNode;

typedef BinTNode * BinTree;

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

void 133( BinTree root, int left, int right)

if (root==NULL ) return;

f33( root->rchild, left, right);

if (root->key >= left && root->key<right) printf( ⁿ%d ”, root->key );

f33( root->lchild, left, right);

(1)设二叉树T如题33图所示，bt是指向根结点的指针。给出执行f33(bt, 15, 25)的输出结果。

(2)给出函数f33 ()的功能。

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

34.设顺序表L按升序排列，请编写函数f34(),要求用二分查找确定插入位置，将元 素x插入到L中，使L保持有序。

函数 134 ()的原型为：void C4 ( SeqList *L, DataType x)

点击免费下载：2022年4月高等教育自学考试全国统一命题考试

以上就是2022年4月自考数据结构真题试卷，有需要的同学可以自行下载使用，有什么问题可以随时留言咨询。