全国2007年自学考试数据结构试题.doc

1、自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）1全国 2007 年 1 月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

2、错选、多选或未选均无分。1抽象数据类型的三个组成部分分别为（ ）A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储结构C数据项、数据元素和数据类型D数据元素、数据结构和数据类型2若算法中语句的最大频度为 T(n)=2006n+6nlogn+29log2n,则其时间复杂度为（ ）AO(logn) BO(n)CO(nlogn) DO(log 2n)3若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）A无头结点的双向链表 B带尾指针的循环链表C无头结点的单链表 D带头指针的循环链表4上溢现象通常出现在（ ）A顺序栈的入栈操作过程中 B顺序栈的出栈操作过程中C链栈

3、的入栈操作过程中 D链栈的出栈操作过程中5已知串 s= aabacbabcaccab，串 t1=abc,串 t2=cba,函数 index(s,t)的返回值为串 t 在串 s 中首次出现的位置，则能求得串abcacba的操作序列为（ ）Asubstr (s1,s,6,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s1,s2);Bsubstr (s1,s,7,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s2,s1);Csubstr(s1,s,6,index(s,t2); substr(s2,s,

4、index(s,t2),3);strcat(s1,s2);Dsubstr(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)操作的结果是（ ）Ad BeC(e) D(e,f )自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦

5、在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）27已知一棵完全二叉树有 64 个叶子结点，则该树可能达到的最大深度为（ ）A7 B8C9 D108若一棵二叉树有 11 个叶子结点，则该二叉树中度为 2 的结点个数是（ ）A10 B11C12 D不确定的9对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ ）A求一个顶点的邻接点 B求一个顶点的度C深度优先遍历 D广度优先遍历10若用邻接矩阵表示带权有向图，则顶点 i 的入度等于矩阵中（ ）A第 i 行非元素之和 B第 i 列非 元素之和C第 i 行非元素个数

6、D第 i 列非元素个数11对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素 5 为基准的一次划分的结果为（ ）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下列二叉树中，不平衡的二叉树是（ ）13下列序列中，不构成堆的是（ ）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一个记录

7、 B一组记录自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）3C一个类型 D一个文件15稀疏索引是指在文件的索引表中（ ）A为每个字段设一个索引项 B为每个记录设一个索引项C为每组字段设一个索引项 D为每组记录设一个索引项二、填空题（本大题共 10 小题，每小题 2 分，共

8、 20 分）请在每小题的空格中填上正确答案。错填、不填均无分。16链式存储结构的特点是借助_来表示数据元素之间的逻辑关系。17假设带头结点的非空单循环链表中仅设尾指针 L，则在第 1 个结点之前插入指针 s 所指结点的语句依次是_；_。18无表头结点的链队列 Q 为空的条件是_。19不含任何字符的串称为_。20假设按行优先顺序将一个 20 阶的三对角矩阵 A 压缩存储在一维数组 Q 中，其中 Q0存放矩阵的第 1 个元素 a1,1，那么矩阵元素 a3,4 在 Q 中的存储位置 k=_。21前序序列和中序序列不相同的二叉树的特征是_。22在含有 n 个顶点的连通图中，任意两个不同顶点之间的简单路

9、径的最大长度为_。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。下表所列为按照朴素的串匹配算法进行的前两趟匹配。请继续完成余下各趟匹配，直至结束。自考乐园-心境随缘，诚与天

10、下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）427已知带权图 G 如图所示，画出图 G 的一棵最小生成树。28对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于 O（n 2）的排序方法；自考乐园-心境随缘，诚与天下自考人共

11、勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）5（2）所需辅助空间最多的排序方法；（3）最好情况和最坏情况下的时间复杂度相同的排序方法。（1）（2）（3）29已知一棵线索化的二叉排序树如图所示。（1）说明该树的线索化是基于何种遍历次序的；（2）在该树中插入元素值为 53 的结点并修改相应线索，画出修改之后的

12、树。（1）（2）四、算法阅读题（本大题共 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;ilength;i+) for(j=0;jdatai!=L-dataj;j+);if(j=k) if(k!=i)L-datak=L-datai;k+;自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快

13、乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）6L-length=k;(1)(2)31阅读算法 f 31,并回答下列问题：（1）设队列 Q=（1，3，5，2，4，6） 。写出执行算法 f 31 后的队列 Q;（2）简述算法 f 31 的功能。void f 31(Queue *Q)DataType e;if (!QueueEmpty(Q)

14、e=DeQueue(Q);f 31(Q);EnQueue(Q,e);(1)(2)32已知树的存储结构为孩子兄弟链表，其类型定义如下：typedef struct CSTNode char data;struct CSTNode leftmostchild,*rightsibling; CSTNode, *CSTree;阅读函数 f 32,并回答下列问题：（1）对于如图所示树，写出函数调用 f 32(T)的返回值；（2）简述树 T 非空时函数 f 32 返回值的含义。int f32(CSTree T)int c;CSTree p;if (!T-leftmostchild) return 1;el

15、se c=0;自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）7for(p=T-leftmostchild;p;p=p-rightsibling)c+=f32(p);return c;(1)(2)33已知数组 R1.p-1中的元素序列为一个大根堆，函数 Adjust(R,p

16、)将 R1.p重新调整为一个大根堆。（1）在函数 Adjust 的空缺处填入适当内容，使其成为一个完整的函数；（2）简述函数 f33(R,n)的功能。void Adjust(SeqList R,int p) int i,j;RecType temp=Rp;i=p;j=i/2;while(j=1i=j; ;Ri= ;void f33(SeqList R,int n) int k;for(k=2;k=n;k+)Adjust(R,k);(1)(2)自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全

17、，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id，可以直接进入俱乐部） ；俱乐部 url 地址：http:/ url 进入俱乐部。 ）8五、算法设计题（本大题 10 分）34已知有向图的邻接表表示的形式描述如下：#define MaxNum 50 /图的最大顶点数typedef struct ArcNode int adjvex; /邻接点域struct ArcNode *nextArc; /链域 ArcNode; /弧结点类型typedef struct char vertex; /顶点域ArcNode *firstArc; /弧表头指针VertexNode; /顶点表结点类型typedef struct VertexNode adjListMaxNum; /邻接表int n,e; /图中当前的顶点数和边数ALGraph; /邻接表类型按以下函数原型编写算法，求有向图 G 中第 i 顶点的度，并写出算法的时间复杂度。int f34(ALGraph *G,int i);