2023年全国高等教育自学考试数据结构试题及答案.doc

全国2023年1月高等教育自学考试数据结构试题（课程代码：02331）一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内错选、多选或未选均无分1．若一个算法的时间复杂度用T(n)表达，其中n的含义是（ ） A．问题规模 B．语句条数 C．循环层数 D．函数数量2．具有线性结构的数据结构是（ ） A．树 B．图 C．栈和队列 D．广义表3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ ） A．O(1) B．O(m) C．O(n) D．O(m+n)4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ ） A．2个 B．3个 ． C．4个 D．6个5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ ） A．3 B．37 C．50 D．976．若栈采用链式存储结构，则下列说法中对的的是（ ） A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空7．若串str=”Software”，其子串的数目是（ ） A．8 B．9 C．36 D．378．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ ） A．1012 B．1017 C．1032 D．10399．允许结点共享的广义表称为（ ） A．纯表 B．线性表 C．递归表 D．再入表10．下列数据结构中，不属于二叉树的是（ ） A．B树 B．AVL树 C．二叉排序树 D．哈夫曼树11．对下面有向图给出了四种也许的拓扑序列，其中错误的是（ ） A．1，5，2，6，3，4 B．1，5，6，2，3，4 C．5，1，6，3，4，2 D．5，1，2，6，4，312．以v1为起始结点对下图进行深度优先遍历，对的的遍历序列是（ ） A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6 C．v1，v2，v3，v4，v7，v5，v6 D．v1，v2，v5，v6，v7，v3，v413．下列排序算法中不稳定的是（ ） A．快速排序 B．归并排序 C．冒泡排序 D．直接插入排序14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（ ） A．2 B．3 C．4 D．815．采用ISAM组织文献的方式属于（ ） A．链组织 B．顺序组织 C．散列组织 D．索引组织二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上对的答案。

错填、不填均无分16．数据元素及其关系在计算机存储器内的表达称为_________17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_________18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________ typedef struct{ DataType data[100]； int top； }SeqStack； DataType f18(SeqStack*S) { if(StackEmpty(S)) Error(”Stack is empty”)； return S->data[S->top]； }19．在串匹配中，一般将主串称为目的串，将子串称为_________20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= _________21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权途径长度为_________ 22．已知有向图如下所示，其中顶点A到顶点C的最短途径长度是_________。

23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_________24．高度为3的3阶B-树最少的关键字总数是_________25．VSAM通常作为大型索引顺序文献的标准组织，其动态索引结构采用的是_________三、解答题(本大题共4小题，每小题5分，共20分)26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树已知一棵二叉树如图所示，请给出其RNL遍历的结果序列27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表达如下所示请回答下列问题：(1)请画出相应的图G2)画出图G的邻接表存储结构28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列29．已知一棵二叉排序树如图所示 请回答下列问题： (1)画出插入元素23后的树结构；(2)请画出在原图中删除元素57后的树结构四、算法阅读题(本大题共4小题，每小题5分，共20分)30．已知下列程序，Ls指向带头结点的单链表。

Typedefstruct node { DataType data; struct node * next; } * LinkList; void f30( LinkList Ls ){ LinkList p, q; q = Ls->next; if ( q && q->next ) { Ls->next = q->next; p=q while ( p->next ) p = p->next; p->next = q; q->next = NULL;}}请回答下列问题：(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果2)请简述算法的功能31．已知字符串解决函数f31程序如下 int f31(char*strl，char*str2) { while(*strl==*str2&&(*strl!=’＼0’)){ strl++； str2++； } return(*strl-*str2 ? l∶0)； } 请回答下列问题： (1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是f31(”abcde”，”abcde”)，则函数的返回值是什么? (2)简述该函数的功能。

32．数组A[]中存储有n个整数，请阅读下列程序 void f32(intA[]，int n) { inti，j，k，x； k=n-l； while(k>0){ i=k； k=0； for(j=O；jA[j+1]){ x=A[j]； A[j]=A[j+l]； A[j+1]=x； k=j； }／／end of if }／／end of while return； } 　请回答下列问题： 　(1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么? 　(2)说明该算法的功能33．下面程序实现二分查找算法 Typedef struct{ KeyType key； InfoType otherinfo； }SeqList[N+1]； int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n； while( (1) ){ mid=(1ow+high)／2； if( (2) ) return mid； if(R[mid]．key>K) high=mid-1； else (3) ； } return O； } ／／BinSearch 　请在空白处填写适当内容，使该程序功能完整。

　(1) 　(2) 　(3)五、算法设计题(本题10分)34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{ ElmType data； struct Node *lchild，*rchild； }*BiTree；请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数全国2023年1月高等教育自学考试数据结构试题答案 (课程代码:02331)一、单项选择题（本大题共15小题，每小题2分，共30分）1. A 2. C 3. B 4. C 5. B 6. B 7. D 8. C 9. D 10. A11. C 12. D 13. A 14. B 15. D二、填空题（本大题共10小题，每小题2分，共20分）16.存储结构（或物理结构）17. O(n)18．取栈顶元素(或StackTop或GetTop)19. 模式（或模式串）20．(c)21. 21922. 3523. 42, 13, 94, 55, 05, 46, 1724.725. B+树三、解答题（本大题共4小题，每小题5分，共20分）26.该树的RNL遍历结果序列为：GCFABD【评分参考】错一个字符扣1分，扣完5分为止。

27．(1)如下图（2分）(2)如下图（3分）【评分参考】以上答案不惟一，只要图形等价对的即可给分28.初始堆序列是(12，15，14，18，16，36，18，60，25，85)【评分参考】错一个数扣1分，扣完5分为止评分参考】以上(2)中答案不惟一，给出的两个图都是对的，只要给出其中之一即可四、算法阅读题（本大题共4小题，每小题5分，共20分）30．(1) （3分）【评分参考】错一个结点扣1分，扣完3分为止2)将单链表的首结点（第一个结点）移到链尾（作为最后一个结点）或将链头元。