《全国2007年自学考试数据结构试题.doc》由会员分享，可在线阅读，更多相关《全国2007年自学考试数据结构试题.doc（8页珍藏版）》请在金锄头文库上搜索。
1、自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.全国2007年1月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1抽象数据类型的三个组成部分分别为（）A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储结构C数据项、数据元素和数据类型D数据元素、数据结构和数据类型2若算法中语句的最大频度为
2、T(n)=2006n+6nlogn+29log2n,则其时间复杂度为（）AO(logn)BO(n)CO(nlogn)DO(log2n)3若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）A无头结点的双向链表B带尾指针的循环链表C无头结点的单链表D带头指针的循环链表4上溢现象通常出现在（）A顺序栈的入栈操作过程中B顺序栈的出栈操作过程中C链栈的入栈操作过程中D链栈的出栈操作过程中5已知串s=aabacbabcaccab，串t1=abc,串t2=cba,函数index(s,t)的返回值为串t在串s中首次出现的位置，则能求得串abcacba的操作序列为（）Asubstr
3、 (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,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)执行h
4、ead(tail(head(tail(L)操作的结果是（）AdBeC(e)D(e,f )7已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）A7B8C9D108若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）A10B11C12D不确定的9对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（）A求一个顶点的邻接点B求一个顶点的度C深度优先遍历D广度优先遍历10若用邻接矩阵表示带权有向图，则顶点i的入度等于矩阵中（）A第i行非元素之和B第i列非元素之和C第i行非元素个数D第i列非元素个数11对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一
5、个元素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一个记录B一组记录C一个类型D一个文件15稀疏索引是指在文件的索引表中（）A为每个字段设一个索引项B为每个记录设一个索引项C为每组字段设一个索引项
6、D为每组记录设一个索引项二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16链式存储结构的特点是借助_来表示数据元素之间的逻辑关系。17假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是_；_。18无表头结点的链队列Q为空的条件是_。19不含任何字符的串称为_。20假设按行优先顺序将一个20阶的三对角矩阵A压缩存储在一维数组Q中，其中Q0存放矩阵的第1个元素a1,1，那么矩阵元素a3,4在Q中的存储位置k=_。21前序序列和中序序列不相同的二叉树的特征是_。22在含有n个顶点的连通图中，任意两个不同
7、顶点之间的简单路径的最大长度为_。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。下表所列为按照朴素的串匹配算法进行的前两趟匹配。请继续完成余下各趟匹配，直至结束。27已知带权图G如图所示
8、，画出图G的一棵最小生成树。28对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于O（n2）的排序方法；（2）所需辅助空间最多的排序方法；（3）最好情况和最坏情况下的时间复杂度相同的排序方法。（1）（2）（3）29已知一棵线索化的二叉排序树如图所示。（1）说明该树的线索化是基于何种遍历次序的；（2）在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树。（1）（2）四、算法阅读题（本大题共4小题，每小题5分，共20分）30假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f 30，并回答下列问题：（1）设顺序
9、表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+; L-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 (
10、!QueueEmpty(Q) 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-leftmostchil
11、d) return 1;else c=0; for(p=T-leftmostchild;p;p=p-rightsibling) c+=f32(p); return c; (1)(2)33已知数组R1.p-1中的元素序列为一个大根堆，函数Adjust(R,p)将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=1& Rj.keytemp.key) Ri=Rj;
12、i=j; ; Ri= ; void f33(SeqList R,int n) int k; for(k=2;k=n;k+) Adjust(R,k); (1)(2)五、算法设计题（本大题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);1俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦在百度贴吧的搜
