1、2009 年下半年全国自考（数据结构）真题试卷及答案与解析一、单项选择题1 按值可否分解，数据类型通常可分为两类，它们是 ( )（A）静态类型和动态类型（B）原子类型和表类型（C）原子类型和结构类型（D）数组类型和指针类型2 对于三个函数 f(n)=2008n3+8n2+96000，g(n)=8n 3+8n+2008 和 h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )（A）f(n)是 O(g(n)（B） g(n)是 O(f(n)（C） h(n)是 O(nlogn)（D）h(n)是 O(n2)3 指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*
2、r 在表中次序的程序段是 ( )（A）pnext=r; q next=rnext; rnext=q;（B） pnext=r; rnext=q; qnext=rnext;（C） rnext=q; qnext=r next; pnext=r;（D）rnext=q; p next=r; qnext=r next;4 若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是 ( )（A）3（B） 5（C） 6（D）75 假设以数组 An存放循环队列的元素，其头指针 front 指向队头元素的前一个位置、尾指针 rear 指向队尾元素所在的存储位置，则在少用一个元素
3、空间的前提下，队列满的判定条件为 ( )（A）rear=front（B） (front+1)%n=rear（C） rear+1=front（D）(rear+1)%n=front6 串的操作函数 str 定义为： int str(char*s) char*p=s; while(*p!=0)p+; return p=s; 则 str(“abcde“)的返回值是 ( )（A）3（B） 4（C） 5（D）67 二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34的存储地址为 1000，则元素 A43的存储地址为 ( )（A）1020（B） 1024（C） 1036（D
4、）12408 对广义表 L=(a，()执行操作 tail(L)的结果是 ( )（A）()（B） ()（C） a（D）(a)9 已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( )（A）FEDCBA（B） ABCDEF（C） FDECBA（D）FBDCEA10 已知森林 F=T1，T 2,T3,T4,T5)，各棵树 Ti(i=1,2,3,4,5)中所含结点的个数分别为7,3,5,1,2，则与 F 对应二叉树的右子树中的结点个数为 ( )（A）2（B） 3（C） 8（D）1111 若非连通无向图 G 含有 21 条边，则 G 的顶点个数至少为 ( )（A）7（B） 8（
5、C） 21（D）2212 如图所示的有向图的拓扑序列是 ( )（A）c,d,b,a,e（B） c,a,d,b,e（C） c,d,e,a,b（D）c,a,b,d,e13 对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( )（A）(5,1,4,3,6,2,8,7)（B） (5,1,4,3,2,6,7,8)（C） (5,1,4,3,2,6,8,7)（D）(8,7,6,5,4,3,2,1)14 分块查找方法将表分为多块，并要求 ( )（A）块内有序（B）块间有序（C）各块等长（D）链式存储15 便于进行布尔查询的文件组织方式是 ( )（A）顺序
6、文件（B）索引文件（C）散列文件（D）多关键字文件二、填空题16 数据的链式存储结构的特点是借助_表示数据元素之间的逻辑关系。17 如果需要对线性表频繁进行_或_操作，则不宜采用顺序存储结构。18 如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈 1 为空的条件是 top1=0，栈 2 为空的条件是 top2=n-1，则“栈满”的判定条件是_。19 静态存储分配的顺序串在进行插入、置换和_等操作时可能发生越界。20 广义表 L=(a，(b，()的深度为_。21 任意一棵完全二叉树中，度为 1 的结点数最多为_。22 求最小生成树的克鲁斯卡尔(Kruskal) 算法耗用的时间与图中
7、_的数目正相关。23 在 5 阶 B-树中，每个结点至多含 4 个关键字，除根结点之外，其他结点至少含_个关键字。24 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是_的。25 常用的索引顺序文件是_文件和_文件。三、解答题26 如图所示，在 nn 矩阵 A 中，所有下标值满足关系式 i+jn+1 的元素 ai,j 的值均为 0，现将 A 中其它元素按行优先顺序依次存储到长度为 n(n+1)/2 的一维数组sa 中，其中元素 a1, 存储在 sa0。 (1)设 n=10，元素 a4,9 存储在 sap，写出下标 p的值； (2)设元素 ai,j 存储在 sak中，写出由 i
8、,j 和 n 计算 k 的一般公式。 27 由字符集s,t,a,e,i)及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为 111000010100，请根据该哈夫曼树进行译码，写出原来的电文。 28 已知无向图 G 的邻接表如图所示， (1)画出该无向图； (2)画出该图的广度优先生成森林。 29 对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。 初始堆： 第 1 趟： 第 2 趟：四、算法阅读题30 阅读下列算法，并回答问题： (1)无向图 G 如图所示，写出算法 f30( void
9、DFS(Graph*g,int i); /*从顶点 vi 出发进行深度优先搜索，访问顶点 vj 时置 visitedj为 1*/ int f30(Graph*g) int i,k; for(i=0;igN;I+) visitedi=0; if(visitedi=0) k+; DFS(g,i); return k; 31 假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /* 成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (2
10、)简述算法 f31 的功能。 void f31(LinkList A,LinkList B) LinkList p,q; p=Anext; q=Bnext; while(p else if(p id qid) q=qnext; else if(pscore 60) if(qscore60) pscore=qscore; else pscore=60; p=pnext; q=q next; 32 阅读下列算法，并回答问题： (1)设串 s=“OneWorldOneDream“，t=“One“，pos 是一维整型数组，写出算法f32(s,t,pos)执行之后得到的返回值和 pos 中的值； (2)
11、简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/ int index(char*st，char*t); /*若串 t 在串 st 中出现，则返回在串 st 中首次出现的下标值，否则返回-1*/ int f32(char*s,char*t,int pos) int i,j,k,ls,It; Is=strlen(s); lt=strlen(t); if(ls=0| It=0)return-1; k=0; i=0; do j=index(s+i,t); if(j=0) posk+=i+j; i+=j+it; while(i+it=is=0); retur
12、n k; 33 二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： (1)对如图所示的二叉排序树 T，写出 f33(T,8)返回的指针所指结点的关键字； (2)在哪些情况下算法 f33 返回空指针? (3)简述算法 f33 的功能。 BSTNode*f33(BSTree T,Key
13、Type x) BSTNode*P; if(T=NULL)return NULL; p=f33(Tlehild,x); if(p!=NULL)return p; if(Tkeyx)return T; return f33(Trchild,x); 五、算法设计题34 假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct int dataListSize; int length; SeqList,*Table; 编写算法，将顺序表 L 中所有值为奇数的元素调整到表的前端。2009 年下半年全国自考（数据结构）真题试卷答案与解析一、单项
14、选择题1 【正确答案】 C【试题解析】 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。2 【正确答案】 C【试题解析】 当 n 充分大时，由题意可得： f(n)与 n3 是同阶的，g(n) 与 n3 是同阶的，h(n)与 n2 是同阶的。所以 f(n)=O(g(n)，g(n)=O(f(n)，h(n)=O(n 2)。3 【正确答案】 A4 【正确答案】 B5 【正确答案】 D【试题解析】 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加 1 后是否等于头指针，若相等则认为队满。6 【正确答案】 C【试题解析】
15、 由此操作函数可知，循环执行前，P 和 S 均指向字符串的首字符，循环执行结束后，S 仍指向首字符，而 P 指向字符串之后的结束符(0)，故 PS返回的是整个字符串的长度。7 【正确答案】 A【试题解析】 由题意可知，自 A34的存储地址 1000 起共存放了 5 个元素(即A34、A35、A40 、A41和 A42)后，才开始存放 A43，所以 A43的存储地址为 1000+54=1020。8 【正确答案】 B【试题解析】 广义表的两个特殊的基本运算：取表头 Head(LS)和取表尾 tail(LS)。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是
16、子表，而其表尾必定是子表。值得注意的是广义表()和()不同。前者是长度为 O 的空表，对其不能做求表头和表尾的运算；而后者是长度为 1 的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。9 【正确答案】 A【试题解析】 对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点序列分别称为前序序列、中序序列和后序序列。10 【正确答案】 D11 【正确答案】 B12 【正确答案】 B13 【正确答案】 C14 【正确答案】 B15 【正确答案】 D二、填空题16 【正确答案】 指针17 【正确答案】 插入 删除18 【正确答案】
17、top1top2(或 top2=top1-1 或 top1-top2+1)19 【正确答案】 联接20 【正确答案】 321 【正确答案】 122 【正确答案】 边23 【正确答案】 224 【正确答案】 稳定25 【正确答案】 ISAM VSAM三、解答题26 【正确答案】 1.D=82.27 【正确答案】 eatst28 【正确答案】 1. 2.29 【正确答案】 初始堆：(96,55,63,48,22,31,50,37,11) 第 1 趟：(63,55,50,48,22,3l,11,37,96) 第 2 趟：(55,48,50,37,22,31,11,63,96)四、算法阅读题30 【正
18、确答案】 1. 32.返回无向图 g 中连通分量的个数。31 【正确答案】 1.2.对于表 A 中成绩低于 60 的学生，如果在表 B 中也有成绩记录，则将表 A 中的成绩修改为其在表 B 中的成绩；但若其在表 B 中的成绩高于 60 分，则只改为 60 分。32 【正确答案】 1. 2；pos0=0，pos1=82. 返回串 t 在 S 中出现的次数，并将每次出现的位置依次存放在数组 pos 中。33 【正确答案】 1. 102. T 是空树或 T 中所有结点的关键字均不大于给定值 X 时，返回空指针。3. 如果二叉排序树 T 中存在含有关键字大于给定值 X 的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。五、算法设计题34 【正确答案】 参考答案一： void f34(Table L) int i,j,t; i=0; j=Llength-1; while(ij) while(ij while(i j if(ij) t=Ldatai; Ldatai=L dataj; Ldataj=t; i+; j-; 参考答案二： void f34(SeqList*L) int i,j=0.t; for(i=0;i Llength;i+) if(Ldatai%2)/*奇数*/ if(i!=j) t=Ldatai; Ldatai=L dataj; Ldataj=t; j+;
