精品学习资源全国 2006 年 10 月高等训练自学考试数据结构试卷课程代码： 02331一、单项挑选题 <本大题共 15 小题，每道题 2 分，共 30 分）在每道题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内；错选、多项或未选均无分；1．数据结构是 < ） A ．一种数据类型B．数据的储备结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．算法分析的目的是 < ）A ．辨别数据结构的合理性B．评判算法的效率 C．讨论算法中输入与输出的关系D．鉴别算法的可读性3. 性表的以下运算中，不 ．转变数据元素之间结构关系的运算是 < ）A ．插入 B ．删除C．排序 D ．定位4. 如进栈序列为 1， 2， 3，4， 5， 6，且进栈和出栈可以穿插进行，就可能显现的出栈序列为 < ）A ． 3，2， 6， 1， 4， 5 B ．3， 4， 2，1， 6， 5C． 1，2， 5， 3，4， 6D ．5， 6， 4， 2， 3，15．设串sl=″ Data Structures with Java″ ,s2=″it ″，就子串定位函数index〔s1,s2> 的值为< ）A ． 15B ．16C． 17D ．186．二维数组 A[8][9] 按行优先次序储备，如数组元素 A[2][3] 的储备地址为 1087 ， A[4][7] 的储备地址为1153，就数组元素A[6][7]的储备地址为 <）A ． 1207B ．1209C． 1211D ．12137. 在按层次遍历二叉树的算法中，需要借助的帮助数据结构是 < ）A ．队列 B ．栈C．线性表 D ．有序表8. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 < ）A ．不肯定相同 B ．都相同欢迎下载精品学习资源C．都不相同 D ．互为逆序9. 如采纳孩子兄弟链表作为树的储备结构，就树的后序遍历应采纳二叉树的 < ）A ．层次遍历算法 B ．前序遍历算法C．中序遍历算法 D ．后序遍历算法10．如用邻接矩阵表示一个有向图，就其中每一列包含的″ 1″的个数为 < ）A ．图中每个顶点的入度C．图中弧的条数B ．图中每个顶点的出度D ．图中连通重量的数目11．图的邻接矩阵表示法适用于表示A ．无向图<）B ．有向图C．稠密图D ．稀疏图12. 在对 n 个关键字进行直接挑选排序的过程中，每一趟都要从无序区选出最小关键字元素，就在进行第 i趟排序之前，无序区中关键字元素的个数为 < ）A ． i B ．i+1C． n-i D ．n-i+113. 以下排序算法中，其时间复杂度和记录的初始排列无关的是 < ）A ．插入排序 B ．堆排序C．快速排序 D ．冒泡排序14. 如有序表的关键字序列为 60>OR< 性别=“女”） OR<年龄 >55） B． <性别=“男”） OR〔 年龄 > 60>AND< 性别 =“女”） OR<年龄 >55 ）C． <性别=“男”） AND〔 年龄 > 60>OR< 性别 =“女”） AND< 年龄 >55 ） D． <性别 =“男”） AND〔 年龄 > 60>AND< 性别 =“女”） AND< 年龄 >55 ） 二、填空题 <本大题共 10 小题，每道题 2 分，共 20 分）请在每道题的空格中填上正确答案；错填、不填均无分；16. 称算法的时间复杂度为 O〔f〔n>> ，其含义是指算法的执行时间和 的数量级相同；17. 在一个长度为 n 的单链表 L 中，删除链表中 *p 的前驱结点的时间复杂度为 ；18. 假设为循环队列安排的向量空间为 Q[20] ，如队列的长度和队头指针值分别为 13 和 17，就当前尾指针的值为 ；19. 设 s=″ I AM A ATHLETE ″ ,t= ″ GOOD ″，就执行以下串操作序列之后得到的 sub1 为 ；substr 〔sub1,s,5,2>；substr〔sub2,s,6,8>； strcpy〔t1,t> ；欢迎下载精品学习资源strcat〔t1,sub2> ； strcat〔sub1,t1>；20．广义表的深度是指 ；21. 一棵含 999 个结点的完全二叉树的深度为 ；22. 含 n 个顶点的无向连通图中至少含有 条边；23. 对表长为 9000 的索引次序表进行分块查找，假设每一块的长度均为 15，且以次序查找确定块，就在各记录的查找概率均相等的情形下，其查找胜利的平均查找长度为 ；24．如对关键字序列 <43 ， 02， 80， 48， 26， 57， 15， 73， 21， 24， 66）进行一趟增量为 3 的希尔排序，就得到的结果为 ；25. ISAM 文件由主索引、 、 和主文件组成；三、解答题 <本大题共 4 小题，每道题 5 分，共 20 分）26. 某广义表的表头和表尾均为 ），画出该广义表的图形表示；27. 已知二叉树的先序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG ；<1）画出该二叉树；<2）画出与 <1 ）求得的二叉树对应的森林；<1）<2）28. 已知带权图的邻接表如下所示，其中边表结点的结构为：依此邻接表从顶点 C 动身进行深度优先遍历；<1）画出由此得到的深度优先生成树；<2）写出遍历过程中得到的从顶点 C 到其它各顶点的带权路径及其长度；<1）<2）29．从空树起，依次插入关键字 37， 50， 42， 18， 48， 12， 56， 30， 23，构造一棵二叉排序树；<1）画出该二叉排序树；欢迎下载精品学习资源<2）画出从 <1 ）所得树中删除关键字为 37 的结点之后的二叉排序树；<1）<2）四、算法阅读题 <本大题共 4 小题，每道题 5 分，共 20 分） 30．已知用有序链表储备整数集合的元素；阅读算法 f30 ，并回答以下问题：<1）写出执行 f30{//LinkList 是带有头结点的单链表//ha 和 hb 分别为指向储备两个有序整数集合的链表的头指针LinkList pa,pb ；pa=ha->next ；pb=hb->next ；while〔pa && pb && pa->data==pb->data>{ pa=pa->next ；pb=pb->next ；}if〔pa==NULL && pb==NULL> return 1 ；else return 0；}〔1>〔2>〔3>31. 已知稀疏矩阵采纳带行表的三元组表表示，其形式说明如下： #define MaxRow 100 // 稀疏矩阵的最大行数typedef struct {int i,j,v ； // 行号、列号、元素值}TriTupleNode ；typedef struct{TriTupleNode data[MaxSize] ；int RowTab[MaxRow+1] ； // 行表int m,n,t ； //矩阵的行数、列数和非零元个数欢迎下载精品学习资源}RTriTupleTable ；以下算法 f31 的功能是，以行优先的次序输入稀疏矩阵的非零元 <行号、列号、元素值），建立稀疏矩阵 的带行表的三元组表储备结构；请在空缺处填入合适内容，使其成为一个完整的算法； <注：矩阵的行、列下标均从 1 起计） void f31〔RTriTupleTable *R>{ int i,k ；scanf〔″ %d %d %d ″ ,&R->m,&R->n,&R->t> ；R->RowTab[1]=0 ；k=1； //k 指示当前输入的非零元的行号for〔i=0 ； ① ； i++>{ scanf〔 ″ %d %d %d ″ ,② ，③， &R->data[i].v> ；while〔kdata[i].i>{ ④；R->RowTab[k]=i ；}}}①②③④32. 已知二叉树的储备结构为二叉链表，其类型定义如下： typedef struct NodeType {DataType data；struct NodeType *lchild,*rchild ；}BinTNode,*BinTree ；阅读算法 F32，并回答以下问题：〔1> 对于如下列图的二叉树，画出执行算法 f32 的结果；欢迎下载精品学习资源<2 ）简述算法 f32 的功能；BinTree f32〔BinTree bt1>{BinTree bt2 ；if〔bt1==NULL> bt2=NULL ；else {bt2=〔BinTNode *>malloc〔sizeof〔BinTNode>> ；bt2->data=bt1->data ；bt2->rchild=f32〔bt1->lchild> ；bt2->lchild=f32〔bt1->rchild> ；}return bt2 ；}〔1>〔2>33. 假设有向图采纳邻接表表示法，其定义如下： typedef struct {VertexNode adjlist[MaxVertexNum] ；int n,e ； // 图的当前顶点数和弧数} ALGraph ； // 邻接表类型欢迎下载精品学习资源其中顶点表结点 VertexNode 结构为：vertex firstedge欢迎下载精品学习资源欢迎下载精品学习资源边表结点 EdgeNode 结构为：adjvex next欢迎下载精品学习资源以下算法 f33 的功能是，对以邻接表表示的有向图进行拓扑排序；<1 ）阅读算法 f33，并在空缺处填入合适的内容，使其成为一个完整的算法；<2 ）对于如下列图的邻接表，将执行算法 f33 后的 topo[ ] 结果填入给定的数组中；欢迎下载精品学习资源void f33〔ALGraph G , int topo [ ]>{ int i,j,k,count=0 ；。
120日元之冬.txt
