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

1、数据结构真题 2006 年下半年及答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.数据结构是 ( )（分数：2.00）A.一种数据类型B.数据的存储结构C.一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合2.算法分析的目的是 ( )（分数：2.00）A.辨别数据结构的合理性B.评价算法的效率C.研究算法中输入与输出的关系D.鉴别算法的可读性3.在线性表的下列运算中，不改变数据元素之间结构关系的运算是 ( )（分数：2.00）A.插入B.删除C.排序D.定位4.若进栈序列为 1,2,3,4,5,6，且进栈

2、和出栈可以穿插进行，则可能出现的出栈序列为( )（分数：2.00）A.3,2,6,1,4,5B.3,4,2,1,6,5C.1,2,5,3,4,6D.5,6,4,2,3,15.设串 s1=“Data Structures、with Java“，s2=“it“，则子串定位函数 index(s1，s2)的值为 ( )（分数：2.00）A.15B.16C.17D.186.二维数组 A89按行优先顺序存储，若数组元素 A23的存储地址为 1087，A47的存储地址为1153，则数组元素 A67的存储地址为 ( )（分数：2.00）A.1207B.1209C.1211D.12137.在按层次遍历二叉树的算

3、法中，需要借助的辅助数据结构是 ( )（分数：2.00）A.队列B.栈C.线性表D.有序表8.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 ( )（分数：2.00）A.不一定相同B.都相同C.都不相同D.互为逆序9.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 ( )（分数：2.00）A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法10.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( )（分数：2.00）A.图中每个顶点的入度B.图中每个顶点的出度C.图中弧的条数D.图中连通分量的数目11.图的邻接矩阵表示法适用于表示

4、( )（分数：2.00）A.无向图B.有向图C.稠密图D.稀疏图12.在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i 趟排序之前，无序区中关键字元素的个数为 ( )（分数：2.00）A.iB.i+1C.n-iD.n-i+113.下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( )（分数：2.00）A.插入排序B.堆排序C.快速排序D.冒泡排序14.若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为 ( )（分数：2.00）A.f,c,bB.f,d,bC.g,c,b

5、D.g,d,b15.若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录，则查询条件为 ( )（分数：2.00）A.(性别=“男“)OR(年龄60)OR(性别=“女“)OR(年龄55)B.(性别=“男“)OR(年龄60)AND(性别=“女“)OR(年龄55)C.(性别=“男“)AND(年龄60)OR(性别=“女“)AND(年龄55)D.(性别=“男“)AND(年龄60)AND(性别=“女“)AND(年龄55)二、B填空题/B(总题数：10，分数：20.00)16.称算法的时间复杂度为 O(f(n)，其含义是指算法的执行时间和 1 的数量级相同。（分数：2.00）填空项

6、 1:_17.在一个长度为 n 的单链表 L 中，删除链表中*p 的前驱结点的时间复杂度为 1。（分数：2.00）填空项 1:_18.假设为循环队列分配的向量空间为 Q20，若队列的长度和队头指针值分别为 13 和 17，则当前尾指针的值为 1。（分数：2.00）填空项 1:_19.设 s=“I AM A ATHLETE“，t=“GOOD“，则执行下列串操作序列之后得到的 suhl 为_。 substr(sub1,s,5,2);substr(sub2,s,6,8);strcpy(t1,t); strcat,(t1,sub2);strcat(sub1,t1);（分数：2.00）填空项 1:_20

7、.广义表的深度是指 1。（分数：2.00）填空项 1:_21.一棵含 999 个结点的完全二叉树的深度为 1。（分数：2.00）填空项 1:_22.含 n 个顶点的无向连通图中至少含有 1 条边。（分数：2.00）填空项 1:_23.对表长为 9000 的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 1。（分数：2.00）填空项 1:_24.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00）填空项 1:_

8、25.ISAM 文件由主索引、_、_和主文件组成。（分数：2.00）填空项 1:_三、B解答题/B(总题数：2，分数：35.00)26.某广义表的表头和表尾均为(a,(b,c)，画出该广义表的图形表示。（分数：5.00）_已知二叉树的先序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG。 (1)画出该二叉树； (2)画出与(1)求得的二叉树对应的森林。（分数：30.00）(1). （分数：5.00）_(2).（分数：5.00）_(3). （分数：5.00）_(4).（分数：5.00）_(5). （分数：5.00）_(6).（分数：5.00）_四、B算法阅读题/B(总题数：4，分数：

9、55.00)已知用有序链表存储整数集合的元素。阅读算法。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 分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=hanext; pb=hbnext; while(pa pb=pbnext; if(pa=NU

10、LL else return 0; （分数：15.00）(1).（分数：5.00）(2).（分数：5.00）_(3).（分数：5.00）_已知稀疏矩阵采用带行表的三元组表表示，其形式说明如下： #define MaxRow 100 /稀疏矩阵的最大行数 typedef struct int i,j,v; /行号、列号、元素值 TriTupleNode; typedef struct TriTupleNode dataMaxSize; int RowTabMaxRow+1; /行表 int m,n,t; /矩阵的行数、列数和非零元个数 RTriTupleTable; 下列算法 f31 的功能是，

11、以行优先的顺序输入稀疏矩阵的非零元(行号、列号、元素值)，建立稀疏矩阵的带行表的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法。(注：矩阵的行、列下标均从 1 起计) void f31(RTriTupleTable*R) int i,k; scanf(“%d%d%d“, RRowTab1=0; k=1; /k 指示当前输入的非零元的行号 for(i=0;U /U;i+) scanf(“%d%d%d“,U /U,U /U, while(kR-datai.i) U /U; RRowTabk=i; （分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_已知二叉

12、树的存储结构为二叉链表，其类型定义如下： typedef struct NodeType DataType data; struct NodeType*lchild，*rchild; BinTNode,*BinTree; 阅读算法 f32，并回答下列问题： (1)对于如图所示的二叉树，画出执行算法 f32 的结果； （分数：10.00）(1). （分数：5.00）_(2).（分数：5.00）_假设有向图采用邻接表表示法，其定义如下： typedef struct VertexNode adjlistMaxVertexNum; int n,e; /图的当前顶点数和弧数 ALGraph /邻接表类

13、型 其中顶点表结点 VertexNode 结构为： 边表结点 EdgeNode 结构为： 下列算法 f33 的功能是，对以邻接表表示的有向图进行拓扑排序。 (1)阅读算法 f33，并在空缺处填入合适的内容，使其成为一个完整的算法； (2)对于如图所示的邻接表，将执行算法 f33 后的 topo结果填入给定的数组中。 void f33(ALGraph G,int topo ) int i,j,k,count=0; int indegreeMaxVertexNum; EdgeNode*p;/p 为指向边表结点的指针 Queue Q;/Q 为队列 FindIndegree(G,indegree);/

14、求各顶点的入 度，并置于入度向量 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)U /U; if(countG.n)printf(“/n 图 G 中存在有环路“); （分数：10.00）填空项 1:_填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)27.假设以带头结点的单链表表示有序表，单链表的类型定义如下： t

15、ypedef struct node DataType data; struct node*next LinkNode,*LinkList; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_数据结构真题 2006 年下半年答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.数据结构是 ( )（分数：2.00）A.一种数据类型B.数据的存储结构C.一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合 解析：2.算法分析的目的是 ( )（分数：2.00）A.辨别数据结构的合理

16、性B.评价算法的效率 C.研究算法中输入与输出的关系D.鉴别算法的可读性解析：3.在线性表的下列运算中，不改变数据元素之间结构关系的运算是 ( )（分数：2.00）A.插入B.删除C.排序D.定位 解析：4.若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )（分数：2.00）A.3,2,6,1,4,5B.3,4,2,1,6,5 C.1,2,5,3,4,6D.5,6,4,2,3,1解析：5.设串 s1=“Data Structures、with Java“，s2=“it“，则子串定位函数 index(s1，s2)的值为 ( )（分数：2.00）A.15B

17、.16C.17 D.18解析：6.二维数组 A89按行优先顺序存储，若数组元素 A23的存储地址为 1087，A47的存储地址为1153，则数组元素 A67的存储地址为 ( )（分数：2.00）A.1207 B.1209C.1211D.1213解析：7.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是 ( )（分数：2.00）A.队列 B.栈C.线性表D.有序表解析：8.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 ( )（分数：2.00）A.不一定相同B.都相同 C.都不相同D.互为逆序解析：9.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 ( )

18、（分数：2.00）A.层次遍历算法B.前序遍历算法C.中序遍历算法 D.后序遍历算法解析：10.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( )（分数：2.00）A.图中每个顶点的入度 B.图中每个顶点的出度C.图中弧的条数D.图中连通分量的数目解析：11.图的邻接矩阵表示法适用于表示 ( )（分数：2.00）A.无向图B.有向图C.稠密图 D.稀疏图解析：12.在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i 趟排序之前，无序区中关键字元素的个数为 ( )（分数：2.00）A.iB.i+1C.n-iD.n-i+1 解析：13.

19、下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( )（分数：2.00）A.插入排序B.堆排序 C.快速排序D.冒泡排序解析：14.若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为 ( )（分数：2.00）A.f,c,b B.f,d,bC.g,c,bD.g,d,b解析：15.若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录，则查询条件为 ( )（分数：2.00）A.(性别=“男“)OR(年龄60)OR(性别=“女“)OR(年龄55)B.(性别=“男“)OR(年龄60)AND(性别=

20、“女“)OR(年龄55)C.(性别=“男“)AND(年龄60)OR(性别=“女“)AND(年龄55) D.(性别=“男“)AND(年龄60)AND(性别=“女“)AND(年龄55)解析：二、B填空题/B(总题数：10，分数：20.00)16.称算法的时间复杂度为 O(f(n)，其含义是指算法的执行时间和 1 的数量级相同。（分数：2.00）填空项 1:_ （正确答案：f(n)）解析：17.在一个长度为 n 的单链表 L 中，删除链表中*p 的前驱结点的时间复杂度为 1。（分数：2.00）填空项 1:_ （正确答案：O(n)）解析：18.假设为循环队列分配的向量空间为 Q20，若队列的长度和队头

21、指针值分别为 13 和 17，则当前尾指针的值为 1。（分数：2.00）填空项 1:_ （正确答案：10）解析：19.设 s=“I AM A ATHLETE“，t=“GOOD“，则执行下列串操作序列之后得到的 suhl 为_。 substr(sub1,s,5,2);substr(sub2,s,6,8);strcpy(t1,t); strcat,(t1,sub2);strcat(sub1,t1);（分数：2.00）填空项 1:_ （正确答案：“A GOOD ATHLETE“）解析：20.广义表的深度是指 1。（分数：2.00）填空项 1:_ （正确答案：广义表展开后所含括号的最大层数）解析：21

22、.一棵含 999 个结点的完全二叉树的深度为 1。（分数：2.00）填空项 1:_ （正确答案：10）解析：22.含 n 个顶点的无向连通图中至少含有 1 条边。（分数：2.00）填空项 1:_ （正确答案：n-1）解析：23.对表长为 9000 的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 1。（分数：2.00）填空项 1:_ （正确答案：308.5）解析：24.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数

23、：2.00）填空项 1:_ （正确答案：15,02,21,24,26,57,43,66,80,48,73）解析：25.ISAM 文件由主索引、_、_和主文件组成。（分数：2.00）填空项 1:_ （正确答案：柱面索引 磁道索引）解析：三、B解答题/B(总题数：2，分数：35.00)26.某广义表的表头和表尾均为(a,(b,c)，画出该广义表的图形表示。（分数：5.00）_正确答案：()解析：已知二叉树的先序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG。 (1)画出该二叉树； (2)画出与(1)求得的二叉树对应的森林。（分数：30.00）(1). （分数：5.00）_正确答案：(

24、)解析：(2).（分数：5.00）_正确答案：()解析：(3). （分数：5.00）_正确答案：()解析：(4).（分数：5.00）_正确答案：()解析：(5). （分数：5.00）_正确答案：()解析：(6).（分数：5.00）_正确答案：()解析：四、B算法阅读题/B(总题数：4，分数：55.00)已知用有序链表存储整数集合的元素。阅读算法。f30，并回答下列问题： (1)写出执行 f30(a,b)的返回值，其中 a 和 b 分别为指向存储集合2,4,5,7,9,12和2,4,5,7,9的链表的头指针； (2)简述算法 f30 的功能； (3)写出算法 f30 的时间复杂度。 int f3

25、0(LinkList ha,LinkList hb) /LinkList 是带有头结点的单链表 /ha 和 hb 分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=hanext; pb=hbnext; while(pa pb=pbnext; if(pa=NULL else return 0; （分数：15.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解析：判断两个整数集合是否相等，相等则返回 1，否则返回 0(3).（分数：5.00）_正确答案：()解析：O(Min(m,n)，m 和 n 分别为两个整数集合中的元素个数已知稀

26、疏矩阵采用带行表的三元组表表示，其形式说明如下： #define MaxRow 100 /稀疏矩阵的最大行数 typedef struct int i,j,v; /行号、列号、元素值 TriTupleNode; typedef struct TriTupleNode dataMaxSize; int RowTabMaxRow+1; /行表 int m,n,t; /矩阵的行数、列数和非零元个数 RTriTupleTable; 下列算法 f31 的功能是，以行优先的顺序输入稀疏矩阵的非零元(行号、列号、元素值)，建立稀疏矩阵的带行表的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法

27、。(注：矩阵的行、列下标均从 1 起计) void f31(RTriTupleTable*R) int i,k; scanf(“%d%d%d“, RRowTab1=0; k=1; /k 指示当前输入的非零元的行号 for(i=0;U /U;i+) scanf(“%d%d%d“,U /U,U /U, while(kR-datai.i) U /U; RRowTabk=i; （分数：20.00）填空项 1:_ （正确答案：iR-t）解析：填空项 1:_ （正确答案： struct NodeType*lchild，*rchild; BinTNode,*BinTree; 阅读算法 f32，并回答下列问题

28、： (1)对于如图所示的二叉树，画出执行算法 f32 的结果； （分数：10.00）(1). （分数：5.00）_正确答案：()解析：(2).（分数：5.00）_正确答案：()解析：函数 f32 返回一个指向复制所得二叉树根结点的指针，新建的二又树上每个结点的左、右孩子均为原二叉树上相应结点的右、左孩子假设有向图采用邻接表表示法，其定义如下： typedef struct VertexNode adjlistMaxVertexNum; int n,e; /图的当前顶点数和弧数 ALGraph /邻接表类型 其中顶点表结点 VertexNode 结构为： 边表结点 EdgeNode 结构为： 下

29、列算法 f33 的功能是，对以邻接表表示的有向图进行拓扑排序。 (1)阅读算法 f33，并在空缺处填入合适的内容，使其成为一个完整的算法； (2)对于如图所示的邻接表，将执行算法 f33 后的 topo结果填入给定的数组中。 void f33(ALGraph G,int topo ) int i,j,k,count=0; int indegreeMaxVertexNum; EdgeNode*p;/p 为指向边表结点的指针 Queue Q;/Q 为队列 FindIndegree(G,indegree);/求各顶点的入 度，并置于入度向量 indegree InitQueue( for(i=0;i

30、G.n;i+) if(!indegreei)EnQueue( while(!QueueEmpty( topoj=+count for(p=G.adjlistj.firstedge;p;p=pnext) k=padjvex; if(!(-indegreek)U /U; if(countG.n)printf(“/n 图 G 中存在有环路“); （分数：10.00）填空项 1:_ （正确答案： DeQueue( struct node*next LinkNode,*LinkList; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_正确答案：()解析：参考答案

31、一： void f34(LinkList ha,LinkList hb) /hb 和 hb 分剐为存放 A 和 B 有序链表的头指针 LinkList p,q,r; p=ha; q=hbnext; while(pnext else if(pnextdata=qdata) r=pnext; pnext=rnext; free(r); /从 A 表删除相同的元素结点 q=qnext; 参考答案二： void f34(LinkList ha,LinkList hb) /hb 和 hb 分别为存放 A 和 B 有序链表的头指针 LinkList p,q,r; r=ha;p=hanext; q=hbnext; while(pp=p-next; else if(pdata=qdata) rnext=pnext; free(p); p=rnext; /从 A 表删除相同的元素结点 q=qnext