2023年1月自考数据结构试题

《2023年1月自考数据结构试题》由会员分享，可在线阅读，更多相关《2023年1月自考数据结构试题（8页珍藏版）》请在装配图网上搜索。

1、2023年1月自考数据构造试题 - 【法佬自考论坛】海量自考资！全国2023年1月高等教育自学考试 数据构造试题 课程代码：02331 一、单项选择题(本大题在每题列出的四代码填写在题后的1.每个结点有且仅有一个共15小题，每题2分，共30分) 个备选项中只有一个是符合题目要求的，请将其括号内。错选、多项选择或未选均无分。 直接前趋和多个(或无)直接后继(第一个结点除外)的数据构造称为 A.树状构造 B.网状构造 C.线性构造 D.层次构造 2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，那么最节省运算时间的存储构造是 A.单链表 B.双链表 C.仅有头指针的单循环链表

2、 D.仅有尾指针的单循环链表 3.一个栈的入栈序列是1，2，3，n，其输出序列为pl，p2，p3.，pn，假设p1是n，那么pi是 A.i B.n-i C.n-i+l D.不确定 4.下面关于串的表达中，正确的选项是 A.串是一种特殊的线性表 B.串中元素只能是字母 C.空串就是空白串 D.串的长度必须大于零 5.无向完全图G有n个结点，那么它的边的总数为 A.n2 B.n(n-1) C.n(n-1)/2 D.(n-1) 6.假设一棵二叉树有10个度为2的结点，5个度为1的结点，那么度为0的结点数是 A.9 B.11 C.15 D.不确定 7.如下图，在下面的4个序列中，不符合深度优先遍历的序

3、列是 A.acfdeb B.aebdfc C.aedfbc D.aefdbc 8.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是 A.快速排序 B.归并排序 C.冒泡排序 D.直接选择排序 9.二叉排序树G，要输出其结点的有序序列，那么采用的遍历方法是 本资料由【法佬自考论坛】搜集整理 第1 页 :/.zikao60 【法佬自考论坛】海量自考资！A.按层遍历 B.前序遍历 C.中序遍历 D.后序遍历 10.用ISAM和VSAM组织的文件都属于 A.散列文件 B.索引顺序文件 C.索引非顺序文件 D.多关键字文件 11.对序列(15，9，7，8，20，-1，4)进展排序，第一

4、趟排序后的序列变为(4，9，-1，8，20，7，15)，那么采用的排序方法是 A.选择 B.快速 C.希尔 D.冒泡 12.当采用分块查找时，数据的组织方式为 A.数据分成假设干块，每块内数据有序 B.数据分成假设干块，每块中数据个数必须一样 C.数据分成假设干块，每块内数据有序，块间是否有序均可 D.数据分成假设干块，每块内数据不必有序，但块间必须有序 13.下述编码中不是前缀码的是 A.(00，01，10，11) B.(0，1，00，11) C.(0，10，110，111) D.(1，01，000，001) 14.假设一个栈以向量V1.n存储，初始栈顶指针top为n+l，那么x进栈的正确操

5、作是 A.top=top-1；Vtop=x B.Vtop=x；top=top+1 C.top=top+1；Vtop=x D.Vtop=x；top=top-1 15.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是 A.p - data = - 1 B.p - next = NULL C.p - next - next=head D.p - next = head 二、填空题(本大题共10小题，每题2分，假设有两个空格，每个空格1分，共20分)请在每个空格中填上正确答案。错填、不填均无分。 16.在数据的逻辑构造和存储构造中，与计算机无关的是_。 17.线性表L=(a1

6、,a2,，an)用数组表示，假定删除表中任一元素的概率一样，那么删除一个元素平均需要挪动元素的个数是_。 18.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有front=11，rear=29；front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是_和_。 19.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_。 20.三对角矩阵A1010的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，那么元素 A67 的地址为_。 21.假设以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，那

7、么其带权途径长度是_。 22.有向图G如下图，它的两个拓扑排序序列分别为_和_。 本资料由【法佬自考论坛】搜集整理 第2 页 :/.zikao60 【法佬自考论坛】海量自考资！23.一组记录的关键字为(46，79，56，38，40，84)，那么利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_。 24.广义表A=(x，(a，b)，c，)，函数head(head(tail(A)的运算结果是_。 25.索引顺序文件既可以顺序存取，也可以_。 三、解答题(本大题共4小题，每题5分，共20分) 26.对关键字序列(26，18，60，14，7，45，13，32)进展降序的堆排序，写出构建的初始

8、堆(小根堆)及前两趟重建堆之后序列状态。 初始堆： 第一趟： 第二趟： 27.设散列函数为H (key)=key 11，散列地址空间为010，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。 28.一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。 29.如下图的带权无向图，请画出用普里姆算法从顶点1开场的最小生成树的构造过程。 四、算法阅读题(本大题共4小题，每题5分，共20分) 30.阅读以下算法，并

9、答复以下问题： (1)简述该算法的功能； (2)写出分别输入字符串：和，调用算法函数的返回值。 int symmetry(void) int i=0,j,k；. char str80； SeqStack s； InitStack(&s)； gets (str)； while (stri!= 0) i+； for (j=0;jRmid.key) (1) ； else (2) ； for (i=*n；i=low；i-) Ri+1=Ri； (3) ； +(*n)； (1) (2) (3) 32.阅读以下算法，并答复以下问题： (1)简述该算法中标号s1所指示的循环语句的功能； (2)简述该算法中标号

10、s2所指示的循环语句的功能。 LinkList Insertmnode(LinkList head，char x，int m) LinkNode*p，*q，*s; int i; char ch； p=head-next； s1：while (p&p-data!=x) p=p-next； 本资料由【法佬自考论坛】搜集整理 第4 页 :/.zikao60 【法佬自考论坛】海量自考资！if (p=NULL)printf(； else q=p-next； s2： for(i=1；idata=ch； p-next=s； p=s； p-next=q； return head； (1) (2) 33.阅读以

11、下算法，并答复以下问题： (1)该算法采用的是何种排序方法? (2)算法中的Rn+1的作用是什么? typedef struct KeyType key； InfoType otherinfo； RecType； typedef RecType SeqListMaxLen； void sort(SeqList R，int n) /n=1;k-) if (Rk.keyRk+l.key) Rn+1=Rk； for (i=k+1；Ri.keyRn+1.key;i+) Ri-1=Ri; Ri-l=Rn+1； (1) (2) 五、算法设计题(此题10分) 34.假设以单链表表示线性表，单链表的类型定义如下： typedef struct node 本资料由【法佬自考论坛】搜集整理 第5 页 :/.zikao60 【法佬自考论坛】海量自考资！DataType data； Struct node *next； LinkNode，* LinkList； 编写算法，在一个头指针为head且带头结点的单链表中，删除所有结点数据域值为x的结点。函数原型为：LinkList delnode (LinkList head，DataType x) 本资料由【法佬自考论坛】搜集整理 第6 页 :/.zikao60 第 8 页 共 8 页