全国自学考试数据结构试卷.docx
7页
全国 20XX 年 1 月高等训练自学考试数据结构试题课程代码： 02331一、单项挑选题（本大题共 15 小题，每道题 2 分，共 30 分）在每道题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内；错选、多项或未选均无分；1．抽象数据类型的三个组成部分分别为（ A ） A ．数据对象、数据关系和基本操作B．数据元素、规律结构和储备结构 C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型 2．如算法中语句的最大频度为 T〔n〕=2006n+6nlogn+29logA ． O〔logn〕 B ．O〔n〕C． O〔nlogn〕 D ．O〔log 2n〕2n,就其时间复杂度为（ C ）3．如线性表的插入和删除操作频繁地在表头或表尾位置进行，就更相宜采纳的储备结构为（ B ）A ．无头结点的双向链表 B ．带尾指针的循环链表C．无头结点的单链表 D ．带头指针的循环链表 4．上溢现象通常显现在（ A ）A ．次序栈的入栈操作过程中 B ．次序栈的出栈操作过程中 C．链栈的入栈操作过程中 D ．链栈的出栈操作过程中5．已知串 s= ″ aabacbabcacca，b 串″t1= ″ abc串″t,2= ″ cb,a函″数 index〔s,t〕 的返回值为串 t 在串 s中首次显现的位置，就能求得串 ″abcacba的″操作序列为（ C ）A ． substr 〔s1,s,6,index〔s,t1〕〕; substr 〔s2,s,index〔s,t1〕,1〕;strcat〔s1,s2〕;B． substr 〔s1,s,7,index〔s,t1〕〕; substr 〔s2,s,index〔s,t1〕,1〕;strcat〔s2,s1〕;C． substr〔s1,s,6,index〔s,t2〕〕; substr〔s2,s,index〔s,t2〕,3〕;strcat〔s1,s2〕;D． substr〔s1,s,6,index〔s,t2〕〕; substr〔s2,s,index〔s,t2〕,3〕;strcat〔s2,s1〕;6．对广义表 L=〔〔a,b〕,〔〔c,d〕,〔e,f〕〕〕 执行 head〔tail〔head〔tail〔L〕〕〕〕 操作的结果是（ D ）A ． d B． e C． 〔e〕 D ． 〔e,f 〕7．已知一棵完全二叉树有 64 个叶子结点，就该树可能达到的最大深度为（ B ）A ． 7 B． 8 C． 9 D． 108．如一棵二叉树有 11 个叶子结点，就该二叉树中度为 2 的结点个数是（ A ）A ． 10 B ．11C． 12 D ．不确定的9．对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ B ）A ．求一个顶点的邻接点 B ．求一个顶点的度C．深度优先遍历 D ．广度优先遍历 10．如用邻接矩阵表示带权有向图，就顶点 i 的入度等于矩阵中（ D ）A ．第 i 行非 ∞元素之和 B ．第 i 列非 ∞元素之和C．第 i 行非 ∞元素个数 D ．第 i 列非 ∞元素个数11．对关键字序列（ 5， 1，4， 3，7，2， 8，6）进行快速排序时，以第一个元素 5 为基准的一次划分的结果为（ C ）A ．（ 1， 2， 3， 4， 5， 6，7， 8） B．（ 1，4， 3， 2，5， 7， 8， 6） C．（ 2，1， 4， 3，5， 7， 8， 6） D．（ 8， 7， 6， 5， 4， 3，2， 1）12．以下二叉树中，不 ．平稳的二叉树是（ C ）13．以下序列中，不构成堆的是（ ）D．A ．（ 1， 2， 5， 3， 4， 6，7， 8， 9，10） B．（ 10，5， 8， 4， 2， 6，7， 1， 3） C．（ 10，9， 8， 7， 3， 5，4， 6， 2） D．（ 1， 2， 3， 4， 10， 9， 8， 7， 6， 5） 14．主关键字能唯独标识（ A ）A ．一个记录 B ．一组记录C．一个类型 D ．一个文件15．稀疏索引是指在文件的索引表中（ D ） A ． 为 每 个 字 段 设 一 个 索 引 项B．为每个记录设一个索引项 C．为每组字段设一个索引项D．为每组记录设一个索引项二、填空题（本大题共 10 小题，每道题 2 分，共 20 分）请在每道题的空格中填上正确答案；错填、不填均无分；16．链式储备结构的特点是借助 指针 来表示数据元素之间的规律关系；17．假设带头结点的非空单循环链表中仅设尾指针 L ，就在第 1 个结点之前插入指针 s 所指结点的语句依次是 s->next=L->next->next ； L->next->next=s ；18．无表头结点的链队列 Q 为空的条件是 Q.front==NULL 19．不．含任何字符的串称为 _ _空串 ；；〔或 Q->front==NULL〕20．假设按行优先次序将一个 20 阶的三对角矩阵 A 压缩储备在一维数组 Q 中，其中 Q[0]存放矩阵的第 1 个元素 a1,1，那么矩阵元素 a3,4 在 Q 中的储备位置 k= _7 ； 21．前序序列和中序序列不 ．相同的二叉树的特点是 树中至少含有一个具有非空右子树的结点 ；（或树中存在具有右孩子的结点）22．在含有 n 个顶点的连通图中， 任意两个不同顶点之间的简洁路径的最大长度为 n-1 ；23． 用 冒泡 排序方法对关键字序列（ 20， 25，12， 47， 15， 83， 30， 76）进行排序时，前三趟排序的结果为：20， 12， 25， 15， 47， 30， 76，8312， 20， 15， 25， 30， 47， 76，8312， 15， 20， 25， 30， 47， 76，8324．哈希表常用的两类解决冲突的方法是 开放定址法 和 拉 链法 ；25．倒排文件和多重表文件的主要区分在于 次关键字索引 的结构不同；三、解答题（本大题共 4 小题，每道题 5 分，共 20 分）26．已知主串为 ″ ccgcgccgcgcbcb，模″式串为 ″ cgcgcb；″下表所列为根据朴实的串匹配算法进行的前两趟匹配；请连续完成余下各趟匹配，直至终止；c c g c g c c g c g c b c bi=0 c g 匹配失败时 j=1i=1 c g c g c b 匹配失败时 j=5i=2 c 匹配失败时 j=0i=3 c g c g 匹配失败时 j=3i=4 c 匹配失败时 j=0i=5 c g 匹配失败时 j=1 i=6 c g c g c b 匹配胜利27．已知带权图 G 如下列图，画出图 G 的一棵最小生成树；去掉： 〔A,B〕,〔A,D〕,〔C,F〕,〔C,E〕,〔C,H〕,〔D,E〕,〔E,H〕保留： 〔A,C〕,〔B,C〕,〔B,F〕,〔F,H〕,〔C,D〕,〔D,K〕,〔K,E〕,28．对于直接插入排序，希尔排序，冒泡排序，快速排序，直接挑选排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于 O（ n2）的排序方法；（2）所需帮助空间最多的排序方法；（3）最好情形和最坏情形下的时间复杂度相同的排序方法；（ 1）希尔排序、快速排序、堆排序和归并排序（ 2）归并排序（ 3）直接挑选排序、堆排序和归并排序29．已知一棵线索化的二叉排序树如下列图；（1）说明该树的线索化是基于何种遍历次序的；（2）在该树中插入元素值为 53 的结点并修改相应线索，画出修改之后的树；（ 1）中序（ 2） 53四、算法阅读题（本大题共 4 小题，每道题 5 分，共 20 分）30．假设线性表采纳次序储备结构，表中元素值为整型；阅读算法 f 30，并回答以下问题：（1）设次序表 L=〔3,7,3,2,1,1,8,7,3〕, 写出执行算法 f 30 后的 L;（2）简述算法 f 30 的功能；void f 30〔SeqList *L〕{ int i,j,k; k=0;for〔i=0;i
