1、2006 年下半年全国自考（数据结构）真题试卷及答案与解析一、单项选择题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
2、,6,5（C） 1,2,5,3,4,6（D）5,6,4,2,3,15 设串 s1=“Data Structures、with Java“，s2=“it“ ，则子串定位函数 index(s1，s2) 的值为 ( )（A）15（B） 16（C） 17（D）186 二维数组 A89按行优先顺序存储，若数组元素 A23的存储地址为1087，A47的存储地址为 1153，则数组元素 A67的存储地址为 ( )（A）1207（B） 1209（C） 1211（D）12137 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是 ( )（A）队列（B）栈（C）线性表（D）有序表8 在任意一棵二叉树的前序序列和
3、后序序列中，各叶子之间的相对次序关系 ( )（A）不一定相同（B）都相同（C）都不相同（D）互为逆序9 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 ( )（A）层次遍历算法（B）前序遍历算法（C）中序遍历算法（D）后序遍历算法10 若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( )（A）图中每个顶点的入度（B）图中每个顶点的出度（C）图中弧的条数（D）图中连通分量的数目11 图的邻接矩阵表示法适用于表示 ( )（A）无向图（B）有向图（C）稠密图（D）稀疏图12 在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第
4、 i 趟排序之前，无序区中关键字元素的个数为 ( )（A）i（B） i+1（C） n-i（D）n-i+113 下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( )（A）插入排序（B）堆排序（C）快速排序（D）冒泡排序14 若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t) ，则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为 ( )（A）f,c,b（B） f,d,b（C） g,c,b（D）g,d,b15 若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录，则查询条件为 ( )（A）(性别=“男“)OR( 年龄60)OR( 性别=“女“
5、)OR( 年龄55)（B） (性别=“男“)OR( 年龄 60)AND(性别=“女“)OR(年龄55)（C） (性别=“男“)AND(年龄60)OR(性别=“女“)AND(年龄55)（D）(性别=“男“)AND(年龄 60)AND(性别=“女“)AND(年龄55)二、填空题16 称算法的时间复杂度为 O(f(n)，其含义是指算法的执行时间和_的数量级相同。17 在一个长度为 n 的单链表 L 中，删除链表中*p 的前驱结点的时间复杂度为_。18 假设为循环队列分配的向量空间为 Q20，若队列的长度和队头指针值分别为13 和 17，则当前尾指针的值为_。19 设 s=“I AM A ATHLET
6、E“，t=“GOOD“，则执行下列串操作序列之后得到的 suhl为_。 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,
7、73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为_。25 ISAM 文件由主索引、_、_和主文件组成。三、解答题26 某广义表的表头和表尾均为(a,(b,c)，画出该广义表的图形表示。27 已知二叉树的先序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG。 (1)画出该二叉树； (2)画出与(1)求得的二叉树对应的森林。28 已知带权图的邻接表如下所示，其中边表结点的结构为： 依此邻接表从顶点C 出发进行深度优先遍历。 (1)画出由此得到的深度优先生成树； (2)写出遍历过程中得到的从顶点 C 到其他各顶点的带权路径及其长度。29 从空树起，依次插入关键字 3
8、7,50,42,18,48,12,56,30,23，构造一棵二叉排序树。 (1)画出该二叉排序树； (2)画出从(1)所得树中删除关键字为 37 的结点之后的二叉排序树。四、算法阅读题30 已知用有序链表存储整数集合的元素。阅读算法。f30，并回答下列问题： (1)写出执行 f30(a,b)的返回值，其中 a 和 b 分别为指向存储集合 2,4,5,7,9,12和2,4,5,7,9的链表的头指针； (2)简述算法 f30 的功能； (3)写出算法 f30 的时间复杂度。 int f30(LinkList ha,LinkList hb) /LinkList 是带有头结点的单链表 /ha 和 hb
9、 分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=hanext; pb=hb next; while(pa pb=pbnext; if(pa=NULL else return 0; 31 已知稀疏矩阵采用带行表的三元组表表示，其形式说明如下： #define MaxRow 100 /稀疏矩阵的最大行数 typedef struct int i,j,v; /行号、列号、元素值 TriTupleNode; typedef struct TriTupleNode dataMaxSize; int RowTabMaxRow+1; /行表 int m,n,t; /矩阵
10、的行数、列数和非零元个数 RTriTupleTable; 下列算法 f31 的功能是，以行优先的顺序输入稀疏矩阵的非零元(行号、列号、元素值)，建立稀疏矩阵的带行表的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法。(注：矩阵的行、列下标均从 1 起计) void f31(RTriTupleTable*R) int i,k; scanf(“%d%d%d“, RRowTab1=0; k=1; /k 指示当前输入的非零元的行号 for(i=0; ;i+) scanf(“%d%d%d“, , , while(kR-datai.i) ; RRowTabk=i; 32 已知二叉树的存储结
11、构为二叉链表，其类型定义如下： 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); bt2data=bt1data; bt2rchi
12、ld=f32(bt1lchild); bt2lchild=f32(bt1rchild); return bt2; 32 假设有向图采用邻接表表示法，其定义如下： typedef struct VertexNode adjlistMaxVertexNum; int n,e; /图的当前顶点数和弧数 ALGraph /邻接表类型 下列算法 f33 的功能是，对以邻接表表示的有向图进行拓扑排序。 (1)阅读算法 f33，并在空缺处填入合适的内容，使其成为一个完整的算法； (2)对于如图所示的邻接表，将执行算法f33 后的 topo结果填入给定的数组中。 void f33(ALGraph G,int
13、topo ) int i,j,k,count=0; int indegreeMaxVertexNum; EdgeNode*p;/p 为指向边表结点的指针 Queue Q;/Q 为队列 FindIndegree(G,indegree);/求各顶点的入 度，并置于入度向量indegree InitQueue( for(i=0;iG.n;i+) if(!indegreei)EnQueue( while(!QueueEmpty( topoj=+count for(p=G.adjlistj.firstedge;p;p=pnext) k=padjvex; if(!(-indegreek) ; if(cou
14、ntG.n)printf(“n 图 G 中存在有环路“); 33 34 五、算法设计题35 假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node DataType data; struct node*next LinkNode,*LinkList; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。2006 年下半年全国自考（数据结构）真题试卷答案与解析一、单项选择题1 【正确答案】 D2 【正确答案】 B3 【正确答案】 D4 【正确答案】 B5 【正确答案】 C6 【正确答案】 A7 【正确答案】 A8 【正确答案】 B9 【正确
15、答案】 C10 【正确答案】 A11 【正确答案】 C12 【正确答案】 D13 【正确答案】 B14 【正确答案】 A15 【正确答案】 C二、填空题16 【正确答案】 f(n)17 【正确答案】 O(n)18 【正确答案】 1019 【正确答案】 A GOOD ATHLETE20 【正确答案】 广义表展开后所含括号的最大层数21 【正确答案】 1022 【正确答案】 n-123 【正确答案】 308.524 【正确答案】 15,02,21,24,26,57,43,66,80,48,7325 【正确答案】 柱面索引 磁道索引三、解答题26 【正确答案】 27 【正确答案】 1. 2.28 【
16、正确答案】 1. 2.29 【正确答案】 1. 2.四、算法阅读题30 【正确答案】 1.02.判断两个整数集合是否相等，相等则返回 1，否则返回 03.O(Min(m,n)，m 和 n 分别为两个整数集合中的元素个数31 【正确答案】 1. iR-t2. p=ha; q=hb next; while(pnext else if(pnext data=qdata) r=pnext; pnext=r next; free(r); /从 A 表删除相同的元素结点 q=q next; 参考答案二： void f34(LinkList ha,LinkList hb) /hb 和 hb 分别为存放 A 和 B 有序链表的头指针 LinkList p,q,r; r=ha;p=hanext; q=hb next; while(pp=p-next; else if(pdata=qdata) rnext=p next; free(p); p=rnext; /从 A 表删除相同的元素结点 q=qnext
