【学历类职业资格】数据结构真题2009年下半年及答案解析.doc

1、数据结构真题 2009 年下半年及答案解析(总分：124.98，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.按值可否分解，数据类型通常可分为两类，它们是 ( )（分数：2.00）A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型D.数组类型和指针类型2.对于三个函数 f(n)=2008n3+8n2+96000，g(n)=8n 3+8n+2008 和 h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )（分数：2.00）A.f(是 O(g()B.g(是 O(f()C.h(是 O(nlogD.h(是 O(n2)3.指针 p、q 和 r

2、 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 ( )（分数：2.00）A.pnext=r; qnext=rnext; rnext=q;B.pnext=r; rnext=q; qnext=rnext;C.rnext=q; qnext=rnext; pnext=r;D.rnext=q; pnext=r; qnext=rnext;4.若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是 ( )（分数：2.00）A.3B.5C.6D.75.假设以数组 An存放循环队列的元素，其头指针 front 指向队头元素的前一个位置

3、、尾指针 rear 指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( )（分数：2.00）A.rear=frontB.(front+1)%n=rearC.rear+1=frontD.(rear+1)%n=front6.串的操作函数 str 定义为： int str(char*s) char*p=s; while(*p!=/0)p+; return p=s; 则str(“abcde“)的返回值是 ( )（分数：2.00）A.3B.4C.5D.67.二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34的存储地址为 1000，则元素

4、A43的存储地址为 ( )（分数：2.00）A.1020B.1024C.1036D.12408.对广义表 L=(a，()执行操作 tail(L)的结果是 ( )（分数：2.00）A.()B.()C.aD.(9.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( )（分数：2.00）A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA10.已知森林 F=T1，T 2,T3,T4,T5)，各棵树 Ti(i=1,2,3,4,5)中所含结点的个数分别为 7,3,5,1,2，则与 F对应二叉树的右子树中的结点个数为 ( )（分数：2.00）A.2B.3C.8D.11

5、11.若非连通无向图 G 含有 21 条边，则 G 的顶点个数至少为 ( )（分数：2.00）A.7B.8C.21D.2212.如图所示的有向图的拓扑序列是 ( ) （分数：2.00）A.c,d,b,a,eB.c,a,d,b,eC.c,d,e,a,bD.c,a,b,d,e13.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( )（分数：2.00）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.分块查找方法将表分为多块，并要求 (

6、 )（分数：2.00）A.块内有序B.块间有序C.各块等长D.链式存储15.便于进行布尔查询的文件组织方式是 ( )（分数：2.00）A.顺序文件B.索引文件C.散列文件D.多关键字文件二、B填空题/B(总题数：10，分数：20.00)16.数据的链式存储结构的特点是借助 1 表示数据元素之间的逻辑关系。（分数：2.00）填空项 1:_17.如果需要对线性表频繁进行_或_操作，则不宜采用顺序存储结构。（分数：2.00）填空项 1:_18.如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈 1 为空的条件是 top1=0，栈 2为空的条件是 top2=n-1，则“栈满”的判定条件是_

7、。 （分数：2.00）填空项 1:_19.静态存储分配的顺序串在进行插入、置换和 1 等操作时可能发生越界。（分数：2.00）填空项 1:_20.广义表 L=(a，(b，1)的深度为 2。（分数：2.00）填空项 1:_21.任意一棵完全二叉树中，度为 1 的结点数最多为 1。（分数：2.00）填空项 1:_22.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 1 的数目正相关。（分数：2.00）填空项 1:_23.在 5 阶 B-树中，每个结点至多含 4 个关键字，除根结点之外，其他结点至少含 1 个关键字。（分数：2.00）填空项 1:_24.若序列中关键字相同的记录在排序

8、前后的相对次序不变，则称该排序算法是 1 的。（分数：2.00）填空项 1:_25.常用的索引顺序文件是_文件和_文件。（分数：2.00）填空项 1:_三、B解答题/B(总题数：2，分数：20.00)如图所示，在 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,j 和 n 计算 k 的一般公式。 （分数：9.9

9、9）(1).（分数：3.33）_(2).（分数：3.33）_已知无向图 G 的邻接表如图所示， (1)画出该无向图； (2)画出该图的广度优先生成森林。 （分数：9.99）(1). （分数：3.33）_(2).（分数：3.33）_四、B算法阅读题/B(总题数：4，分数：45.00)阅读下列算法，并回答问题： （分数：10.00）(1).（分数：5.00）(2).（分数：5.00）_假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode

10、,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(A,B)后 A 所指的链表； （分数：10.00）(1). （分数：5.00）_(2).（分数：5.00）_阅读下列算法，并回答问题： (1)设串 s=“OneWorldOneDream“，t=“One“，pos 是一维整型数组，写出算法 f32(s,t,pos)执行之后得到的返回值和 pos 中的值； (2)简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/ int index(char*st，char*t); /*若

11、串 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 return k; （分数：10.00）(1).（分数：5.00）_(2).（分数：5.00）_二叉排序树的存储结构定义为以下类型： typedef int KeyType;

12、 typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）(1).（分数：5.00）(2).（分数：5.00）_(3).（分数：5.00）_五、B算法设计题/B(总题数：1，分数：10.00)26.假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct int dataListSiz

13、e; int length; SeqList,*Table; 编写算法，将顺序表 L 中所有值为奇数的元素调整到表的前端。（分数：10.00）_数据结构真题 2009 年下半年答案解析(总分：124.98，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.按值可否分解，数据类型通常可分为两类，它们是 ( )（分数：2.00）A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型 D.数组类型和指针类型解析：解析 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。2.对于三个函数 f(n)=2008n3+

14、8n2+96000，g(n)=8n 3+8n+2008 和 h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )（分数：2.00）A.f(是 O(g()B.g(是 O(f()C.h(是 O(nlog D.h(是 O(n2)解析：解析 当 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.指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 ( )（分数：2.00）A.pnext=r; qnext

15、=rnext; rnext=q; B.pnext=r; rnext=q; qnext=rnext;C.rnext=q; qnext=rnext; pnext=r;D.rnext=q; pnext=r; qnext=rnext;解析：4.若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是 ( )（分数：2.00）A.3B.5 C.6D.7解析：5.假设以数组 An存放循环队列的元素，其头指针 front 指向队头元素的前一个位置、尾指针 rear 指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( )（分数：2.00）A.

16、rear=frontB.(front+1)%n=rearC.rear+1=frontD.(rear+1)%n=front 解析：解析 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加 1 后是否等于头指针，若相等则认为队满。6.串的操作函数 str 定义为： int str(char*s) char*p=s; while(*p!=/0)p+; return p=s; 则str(“abcde“)的返回值是 ( )（分数：2.00）A.3B.4C.5 D.6解析：解析 由此操作函数可知，循环执行前，P 和 S 均指向字符串的首字符，循环执行结束后，S 仍指向首字符，

17、而 P 指向字符串之后的结束符(/0)，故 PS 返回的是整个字符串的长度。7.二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34的存储地址为 1000，则元素 A43的存储地址为 ( )（分数：2.00）A.1020 B.1024C.1036D.1240解析：解析 由题意可知，自 A34的存储地址 1000 起共存放了 5 个元素(即 A34、A35、A40、A41和 A42)后，才开始存放 A43，所以 A43的存储地址为 1000+54=1020。8.对广义表 L=(a，()执行操作 tail(L)的结果是 ( )（分数：2.00）A.()B.() C

18、.aD.(解析：解析 广义表的两个特殊的基本运算：取表头 Head(LS)和取表尾 tail(LS)。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。值得注意的是广义表()和()不同。前者是长度为 O 的空表，对其不能做求表头和表尾的运算；而后者是长度为 1 的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。9.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( )（分数：2.00）A.FEDCBA B.ABCDEFC.FDECBAD.FBDCEA解析：解析

19、对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点序列分别称为前序序列、中序序列和后序序列。10.已知森林 F=T1，T 2,T3,T4,T5)，各棵树 Ti(i=1,2,3,4,5)中所含结点的个数分别为 7,3,5,1,2，则与 F对应二叉树的右子树中的结点个数为 ( )（分数：2.00）A.2B.3C.8D.11 解析：11.若非连通无向图 G 含有 21 条边，则 G 的顶点个数至少为 ( )（分数：2.00）A.7B.8 C.21D.22解析：12.如图所示的有向图的拓扑序列是 ( ) （分数：2.00）A.c,d,b,a,eB.c,a,d,b,e C.

20、c,d,e,a,bD.c,a,b,d,e解析：13.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( )（分数：2.00）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.分块查找方法将表分为多块，并要求 ( )（分数：2.00）A.块内有序B.块间有序 C.各块等长D.链式存储解析：15.便于进行布尔查询的文件组织方式是 ( )（分数：2.00）A.顺序文件B.索引文件C.散列文件D.多关键字文件 解析：二、B填空题/B

21、(总题数：10，分数：20.00)16.数据的链式存储结构的特点是借助 1 表示数据元素之间的逻辑关系。（分数：2.00）填空项 1:_ （正确答案：指针）解析：17.如果需要对线性表频繁进行_或_操作，则不宜采用顺序存储结构。（分数：2.00）填空项 1:_ （正确答案：插入 删除）解析：18.如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈 1 为空的条件是 top1=0，栈 2为空的条件是 top2=n-1，则“栈满”的判定条件是_。 （分数：2.00）填空项 1:_ （正确答案：top1top2(或 top2=top1-1 或 top1-top2+1)）解析：19.静态存

22、储分配的顺序串在进行插入、置换和 1 等操作时可能发生越界。（分数：2.00）填空项 1:_ （正确答案：联接）解析：20.广义表 L=(a，(b，1)的深度为 2。（分数：2.00）填空项 1:_ （正确答案：3）解析：21.任意一棵完全二叉树中，度为 1 的结点数最多为 1。（分数：2.00）填空项 1:_ （正确答案：1）解析：22.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 1 的数目正相关。（分数：2.00）填空项 1:_ （正确答案：边）解析：23.在 5 阶 B-树中，每个结点至多含 4 个关键字，除根结点之外，其他结点至少含 1 个关键字。（分数：2.00）

23、填空项 1:_ （正确答案：2）解析：24.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。（分数：2.00）填空项 1:_ （正确答案：稳定）解析：25.常用的索引顺序文件是_文件和_文件。（分数：2.00）填空项 1:_ （正确答案：ISAM VSAM）解析：三、B解答题/B(总题数：2，分数：20.00)如图所示，在 nn 矩阵 A 中，所有下标值满足关系式 i+jn+1 的元素 ai,j的值均为 0，现将 A 中其它元素按行优先顺序依次存储到长度为 n(n+1)/2 的一维数组 sa 中，其中元素 a1, 存储在 sa0。 (1)设 n=10，元素 a4,9

24、存储在 sap，写出下标 p 的值； (2)设元素 ai,j存储在 sak中，写出由 i,j 和 n 计算 k 的一般公式。 （分数：9.99）(1).（分数：3.33）_正确答案：()解析：(2).（分数：3.33）_正确答案：()解析：_解析：已知无向图 G 的邻接表如图所示， (1)画出该无向图； (2)画出该图的广度优先生成森林。 （分数：9.99）(1). （分数：3.33）_正确答案：()解析：(2).（分数：3.33）_正确答案：()解析：_解析：四、B算法阅读题/B(总题数：4，分数：45.00)阅读下列算法，并回答问题： （分数：10.00）(1).（分数：5.00）解析：(

25、2).（分数：5.00）_正确答案：()解析：返回无向图 g 中连通分量的个数。假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(A,B)后 A 所指的链表； （分数：10.00）(1). （分数：5.00）_正确答案：()解析：(2).（分数：5.00）_正确答案：()解析：对于表 A 中成绩低于

26、60 的学生，如果在表 B 中也有成绩记录，则将表 A 中的成绩修改为其在表 B中的成绩；但若其在表 B 中的成绩高于 60 分，则只改为 60 分。阅读下列算法，并回答问题： (1)设串 s=“OneWorldOneDream“，t=“One“，pos 是一维整型数组，写出算法 f32(s,t,pos)执行之后得到的返回值和 pos 中的值； (2)简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/ int index(char*st，char*t); /*若串 t 在串 st 中出现，则返回在串 st 中首次出现的下标值，否则返回-1*/ int

27、 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 return k; （分数：10.00）(1).（分数：5.00）_正确答案：()解析：(2).（分数：5.00）_正确答案：()解析：返回串 t 在 S 中出现的次数，并将每次出现的位置依次存放在数组 pos 中。二叉排序树的存储结构定义为以下类型： typed

28、ef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解析：T 是空树或 T 中所有结点的关键字均不大于给定值 X 时，返回空指针。(3).（分数：5.00）_正确答案：()解析：如果二叉排序树 T 中存在含有关键字大于给定值 X 的结点

29、，则返回指针指向它们中关键字最小的结点，否则返回空指针。五、B算法设计题/B(总题数：1，分数：10.00)26.假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct int dataListSize; int length; SeqList,*Table; 编写算法，将顺序表 L 中所有值为奇数的元素调整到表的前端。（分数：10.00）_正确答案：()解析：参考答案一： void f34(Table L) int i,j,t; i=0; j=Llength-1; while(ij) while(ij while(ij if(ij) t=Ldatai; Ldatai=Ldataj; Ldataj=t; i+; j-; 参考答案二： void f34(SeqList*L) int i,j=0.t; for(i=0;iLlength;i+) if(Ldatai%2)/*奇数*/ if(i!=j) t=Ldatai; Ldatai=Ldataj; Ldataj=t; j+;