2008年10月份全国自考数据结构真题及答案.pdf
欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.2008年10月份全国自考数据结构真题 一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项 中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均 无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结 构是（）A.栈 B.队列 C.树 D.图 答案：C 2.下面程序段的时间复杂度为（）A.A B.B C.C D.D 答案：C 3.在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（）A.p-next=head B.p-next-next=head C.p-next=NULL D.p=head 答案：A 4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 答案：D 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！5.两个字符串相等的条件是（）A.串的长度相等 B.含有相同的字符集 C.都是非空串 D.串的长度相等且对应的字符相同 答案：D 6.A.A B.B C.C D.D 答案：A 7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A.0 B.1 C.48 D.49 答案：D 8.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（）A.A B.B C.C D.D 答案：A 9.如图所示的有向无环图可以得到的拓扑序列的个数是（）A.3 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！B.4 C.5 D.6 答案：C 10.如图所示的带权无向图的最小生成树的权为（）A.51 B.52 C.54 D.56 答案：11.对长度为n的关键字序列进行堆排序的空间复杂度为（）A.A B.B C.C D.D 答案：B 12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为 A.A B.B 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！C.C D.D 答案：B 13.已知散列表的存储空间为T0.18，散列函数H（key）=key%17,并用二次探测法处理 冲突。散列表中已插入下列关键字：T5=39，T6=57和T7=7，则下一个关键字23插入 的位置是（）A.T2 B.T4 C.T8 D.T10 答案：D 14.适宜进行批量处理的文件类型是（）A.顺序文件 B.索引顺序文件 C.散列文件 D.多关键字文件 答案：A 15.VSAM文件的索引结构为（）A.B+树 B.二叉排序树 C.B-树 D.最优二叉树 答案：A 二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答 案。错填、不填均无分。1.本题答案为：_ 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！答案：4 2.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达 到的最好的时间复杂度是_。答案：O（m+n）3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾 元素的下一个位置，则在队列不满的情况下，队列的长度是_。答案：（rear-front+m）%m 4.字符串sgabacbadfgbacst 中存在有_个与字符串ba相同的子串。答案：3 5.假设以列优先顺序存储二维数组A58，其中元素A00的存储地址为 LOC（a00）,且每个元素占4个存储单元，则数组元素Aij的存储地址为_。答案：6.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为,，该树的度是_。答案：3 7.n个顶点且含有环路的无向连通图中，至少含有_条边。答案：n 8.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的 是_。答案：选择排序 9.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对_结构也 无特殊要求。答案：存储 10.顺序文件中记录存放的物理顺序和_顺序一致。答案：逻辑 三、解答题（本大题共4小题，每小题5分，共20分）1.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。前序序列：后序序列：答案：前序序列：G H I J（2分）后序序列：H J I G（3分）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！2.图的邻接表的类型定义如下所示：#define MaxVertexNum 50 typedef struct node int adjvex;struct node *next;EdgeNode;typedef struct VertexType vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVertexNum;typedef struct AdjList adjlist;int n,e;ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表 示实例如下图所示，请写出重新定义的类型说明。答案：欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！3.某类物品的编号由一个大写英文字母及2位数字（0.9）组成，形如E32。运用基数排序对 下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。E13，A37，F43，B32，B47，E12，F37，B12 第一趟：第二趟：第三趟：答案：第一趟：B32，E12，B12，E13，F43，A37，B47，F37（2分）第二趟：E12，B12，E13，B32，A37，F37，F43，B47（2分）第三趟：A37，B12，B32，B47，E12，E13，F37，F43（1分）（说明：每错4个关键字扣1分，扣完为止。）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！4.（1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在 该序列中二分查找37时所需进行的比较次数。（1）（2）答案：(1)四、算法阅读题（本大题共4小题，每小题5分，共20分）1.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30（&L）后的L状态；（2）简述算法f30的功能。void f30（SeqList *L）int i,j;for（i=j=0;ilength;i+）if（L-datai=0）if（i!=j）L-dataj=L-datai;j+；L-length=j;（1）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！（2）答案：（1）L=（21，19，0，34，30）（2分）（2）删除顺序表中的负值元素。（3分）2.阅读下列算法，并回答问题：（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写 出执行f31（&Q,&Q1,&Q2）之后队列Q、Q1和Q2的状态；（2）简述算法f31的功能。（注：InitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入队、出队和判队空的 操作）void f31（Queue*Q,Queue*Q1,Queue*Q2）int e;InitQueue（Q1）;InitQueue（Q2）;while（!QueueEmpty（Q）e=DeQueue（Q）;if（e=0）EnQueue（Q1,e）;else EnQueue（Q2,e）（1）（2）答案：（1）Q=（）（1分）Q1=（1，0，2，9）（1分）Q2=（-5，-4，-6）（1分）（2）将队列Q的元素依次退队，并将正值及0元素入队到Q1，负值元素入队到Q2。（2分）3.阅读下列算法，并回答问题：（1）假设串由合法的英文字母和空格组成，并以 0 作结束符。设串s=Iamastudent（表 示空格符），写出f32（s）的返回值；（2）简述算法f32的功能。int f32（char*s）int i,n,inword;n=inword=0;for（i=0;si!=0;i+）if（si!=&inword=0）inword=1;n+;else if（si=&inword=1）inword=0;return n;欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！（1）（2）答案：（1）4（2分）（2）对字符串内的单词个数进行累加计数。（3分）4.阅读下列对正整数关键字序列L操作的算法，并回答问题：（1）设L=（28,19,27,49,56,12,10,25,20,50）,写出f33（L,4）的返回值；（2）简述函数f33的功能。int Partition（SeqList*L,int low,int high）;对Llow.high做划分，返回基准记录的位置，并使左部的关键字 都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字 int f33（SeqList L,int k）int low,high,pivotpos;low=1;high=L.length;if（khigh）return-1;do pivotpos=Partition（&L,low,high）;调用快速排序的划分算法 if（pivotposk）high=pivotpos-1;while（pivotpos!=k）;return L.data pivotpos;（1）（2）答案：（1）20（2分）（2）利用快速排序的“划分”机制进行查找，以求取序列中排行第k小的元素。（3分）五、算法设计题（本题10分）1.二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构 int data;数据域 struct BSTNode *lchild,*rchild;左、右孩子指针 BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.答案：
