【学历类职业资格】数据结构真题2012年10月及答案解析.doc

1、数据结构真题 2012 年 10 月及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.一个算法的时间耗费的数量级称为该算法的_（分数：2.00）A.效率B.难度C.可实现性D.时间复杂度2.顺序表便于_（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点3.设带头结点的单循环链表的头指针为 head，指针变量 P 指向尾结点的条件是_（分数：2.00）A.p-next-next=headB.p-next=headC.p-next-next=NULLD.p-next=NULL4.设以数组 A0m-1存放循环队列，fr

2、ont 指向队头元素，rear 指向队尾元素的下一个位置，则当前队列中的元素个数为_（分数：2.00）A.(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m5.下列关于顺序栈的叙述中，正确的是_（分数：2.00）A.入栈操作需要判断栈满，出栈操作需要判断栈空B.入栈操作不需要判断栈满，出栈操作需要判断栈空C.入栈操作需要判断栈满，出栈操作不需要判断栈空D.入栈操作不需要判断栈满，出栈操作不需要判断栈空6.A 是一个 1010 的对称矩阵，若采用行优先的下三角压缩存储，第一个元素 a 0，0 的存储地址为 1，每个元素

3、占一个存储单元，则 a 7，5 的地址为_（分数：2.00）A.25B.26C.33D.347.树的后序遍历等价于该树对应二叉树的_（分数：2.00）A.层次遍历B.前序遍历C.中序遍历D.后序遍历8.使用二叉线索树的目的是便于_（分数：2.00）A.二叉树中结点的插入与删除B.在二叉树中查找双亲C.确定二叉树的高度D.查找一个结点的前驱和后继9.设无向图的顶点个数为 n，则该图边的数目最多为_（分数：2.00）A.n-1B.n(n-1)/2C.n(n+1)/2Dn210.可进行拓扑排序的图只能是_（分数：2.00）A.有向图B.无向图C.有向无环图D.无向连通图11.下列排序方法中稳定的是_

4、（分数：2.00）A.直接插入排序B.直接选择排序C.堆排序D.快速排序12.下列序列不为堆的是_（分数：2.00）A.75，45，65，30，15，25B.75，65，45，30，25，15C.75，65，30，15，25，45D.75，45，65，25，30，1513.对线性表进行二分查找时，要求线性表必须是_（分数：2.00）A.顺序存储B.链式存储C.顺序存储且按关键字有序排列D.链式存储且按关键字有序排列14.分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是_（分数：2.00）A.(4，1，2，3，5)B.(4，2，3，1，5)C.(4，5，2，1，3

5、)D.(4，2，1，5，3)15.下列关于 m 阶 B 树的叙述中，错误的是_（分数：2.00）A.每个结点至多有 m 个关键字B.每个结点至多有 m 棵子树C.插入关键字时，通过结点分裂使树高增加D.删除关键字时通过结点合并使树高降低二、填空题(总题数：10，分数：20.00)16.数据元素之间的逻辑关系称为数据的 1 结构。 （分数：2.00）17.在线性表中，表的长度定义为 1。 （分数：2.00）18.用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1、2、3、4，为了得到 1、3、4、2 的出栈顺序，相应的 S 和 X 的操作序列为 1。 （分数：2.00）19.在二叉树

6、中，带权路径长度最短的树称为 1。 （分数：2.00）20.已知广义表 G，head(G)与 tail(G)的深度分别为 4 和 6，则 G 的深度是 1。 （分数：2.00）21.一组字符(a，b，c，d)在文中出现的次数分别为(7，6，3，5)，字符“d“的哈夫曼编码的长度为 1。 （分数：2.00）22.在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 1 条边。 （分数：2.00）23.直接选择排序算法的时间复杂度是 1。 （分数：2.00）24.对于长度为 81 的表，若采用分块查找，每块的最佳长度为 1。 （分数：2.00）25.用二叉链表保存有 n 个结点的二叉树，则结点

7、中有 1 个空指针域。 （分数：2.00）三、解答题(总题数：4，分数：20.00)26.假设 Q 是一个具有 11 个元素存储空间的循环队列(队尾指针指向队尾元素的下一个位置，队头指针指向队头元素)，初始状态 Q.front=Q.rear=0；写出依次执行下列操作后头、尾指针的当前值。 a，b，c，d，e，f 入队，a，b，c，d 出队；(1)Q.front=_；Q.rear=_。 g，h，i，j，k，1 入队，e，f，g，h 出队；(2)Q.front=_；Q.rear=_。 M，n，o，P 入队，i，j，k，l，m 出队；(3)Q.front=_；Q.rear=_。 （分数：5.00）_

8、27.已知一个无向图如下图所示，以为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。 （分数：5.00）_用归并排序法对序列(98，36，-9，0，47，23，1，8)进行排序，问：（分数：5.00）(1).一共需要几趟归并可完成排序。（分数：2.50）_(2).写出第一趟归并后数据的排列次序。（分数：2.50）_一组记录关键字(55，76，44，32，64，82，20，16，43)，用散列函数 H(key)=key%11 将记录散列到散列表 HT_中去，用线性探测法解决冲突。（分数：5.00）(1).画出存入所有记录后的散列表。（分数：2.50）_(2).求在等概率情

9、况下，查找成功的平均查找长度。（分数：2.50）_四、程序阅读题(总题数：4，分数：20.00)顺序表类型定义如下： #define ListSize 100 typedef struct int dataListSize; int length; SeqList; 阅读下列算法，并回答问题： void f30(SeqList *L) int i, j; i=0; while(iL-length) if(L-datai%2!=0) for(j=i+1; jL-length; j+ L-dataj-1=L-dataj; L-length-; else i+ （分数：5.00）(1).若 L-da

10、ta 中的数据为(22，4，63，0，15，29，34，42，3)，则执行上述算法后 L-data 中的数据以及 L-length 的值各是什么?（分数：2.50）_(2).该算法的功能是什么?（分数：2.50）_有向图的邻接矩阵类型定义如下： #define MVN 100 /最大顶点数 typedef int EType; /边上权值类型 typedef struct EType edgesMVNMVN; /邻接矩阵，即边表 int n; /图的顶点数 MGraph; /图类型 例如，一个有向图的邻接矩阵如下所示： （分数：5.00）(1).step1 到 step2 之间的二重循环语句的

11、功能是什么?（分数：2.50）_(2).step2 之后的二重循环语句的功能是什么?（分数：2.50）_阅读下列算法，并回答问题： void f32(int r, int n) Int i, j; for(i=2; in; i+) r0=ri; j=i-1; while(r0rj) rj+1=rj; j=j-1; rj+1=r0; （分数：5.00）(1).这是哪一种插入排序算法?该算法是否稳定?（分数：2.50）_(2).设置 r0的作用是什么?（分数：2.50）_顺序表类型定义如下： typedef int SeqList100; 阅读下列算法，并回答问题： void f33(SeqLis

12、t r, int n) int a, b, i; if(r0r1) a=r0; b=r1; elsea=r1; b=r0; for(i=2; in; i+) if(ria) a=ri; else if(rib) b=ri; printf(“a=%d, b=%d。/n“, a, b); （分数：5.00）(1).给出该算法的功能；（分数：2.50）_(2).给出该算法的时间复杂度。（分数：2.50）_五、算法设计题(总题数：1，分数：10.00)28.二叉树的存储结构类型定义如下： typedef struct node int data; struct node *lchild, *rchil

13、d; BinNode; typedef BinNode *BinTree; 编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。 函数的原型为：void f34(BinTree T, int *count, int *sum) *count 和*sum 的初值为 0。 （分数：10.00）_数据结构真题 2012 年 10 月答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.一个算法的时间耗费的数量级称为该算法的_（分数：2.00）A.效率B.难度C.可实现性D.时间复杂度 解析：考点 算法的时间复杂度的概念 解析 一个

14、算法的时间耗费的数量级称为该算法的时间复杂度。2.顺序表便于_（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点 解析：考点 顺序表的特征 解析 顺序表便于按序号查找结点。3.设带头结点的单循环链表的头指针为 head，指针变量 P 指向尾结点的条件是_（分数：2.00）A.p-next-next=headB.p-next=head C.p-next-next=NULLD.p-next=NULL解析：考点 指针变量 p 指向尾结点的判定条件 解析 单循环链表的指针变量 p 指向尾结点的判定条件是 p-next=head。4.设以数组 A0m-1存放循环队列，front

15、 指向队头元素，rear 指向队尾元素的下一个位置，则当前队列中的元素个数为_（分数：2.00）A.(rear-front+m)%m B.rear-front+1C.(front-rear+m)%mD.(rear-front)%m解析：考点 队列中元素个数的计算 解析 队列中元素的个数为(rear-front+m)%m5.下列关于顺序栈的叙述中，正确的是_（分数：2.00）A.入栈操作需要判断栈满，出栈操作需要判断栈空 B.入栈操作不需要判断栈满，出栈操作需要判断栈空C.入栈操作需要判断栈满，出栈操作不需要判断栈空D.入栈操作不需要判断栈满，出栈操作不需要判断栈空解析：考点 顺序栈的性质的判断

16、 解析 入栈操作需要判断栈满，出栈操作需要判断栈空。6.A 是一个 1010 的对称矩阵，若采用行优先的下三角压缩存储，第一个元素 a 0，0 的存储地址为 1，每个元素占一个存储单元，则 a 7，5 的地址为_（分数：2.00）A.25B.26C.33D.34 解析：考点 对称矩阵的元素的地址的计算 解析 若对称矩阵采用下三角压缩存储，根据其地址的计算公式，可得到所求元素的地址。7.树的后序遍历等价于该树对应二叉树的_（分数：2.00）A.层次遍历B.前序遍历C.中序遍历 D.后序遍历解析：考点 树的遍历与二叉树遍历的关系 解析 树的后序遍历等价于该树对应的二叉树的中序遍历。8.使用二叉线索

17、树的目的是便于_（分数：2.00）A.二叉树中结点的插入与删除B.在二叉树中查找双亲C.确定二叉树的高度D.查找一个结点的前驱和后继 解析：考点 二叉线索树的使用目的 解析 二叉线索树的使用目的是便于查找一个结点的前趋和后继。9.设无向图的顶点个数为 n，则该图边的数目最多为_（分数：2.00）A.n-1B.n(n-1)/2 C.n(n+1)/2Dn2解析：考点 无向图的边数的问题 解析 无向图的边数最多为 n(n-1)/2。10.可进行拓扑排序的图只能是_（分数：2.00）A.有向图B.无向图C.有向无环图 D.无向连通图解析：考点 拓扑排序的图的要求 解析 可进行拓扑排序的图只能是有向无环

18、图。11.下列排序方法中稳定的是_（分数：2.00）A.直接插入排序 B.直接选择排序C.堆排序D.快速排序解析：考点 排序方法稳定性的判断 解析 直接插入排序是稳定的，直接选择排序、堆排序以及快速排序是不稳定的。12.下列序列不为堆的是_（分数：2.00）A.75，45，65，30，15，25B.75，65，45，30，25，15C.75，65，30，15，25，45 D.75，45，65，25，30，15解析：考点 堆的判断 解析 根据堆的概念，可判断出 75，65，30，15，25，45 不为堆。13.对线性表进行二分查找时，要求线性表必须是_（分数：2.00）A.顺序存储B.链式存储C

19、.顺序存储且按关键字有序排列 D.链式存储且按关键字有序排列解析：考点 二分查找对线性表的要求 解析 对线性表进行二分查找时，要求线性表必须是顺序存储且按关键字有序排列。14.分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是_（分数：2.00）A.(4，1，2，3，5) B.(4，2，3，1，5)C.(4，5，2，1，3)D.(4，2，1，5，3)解析：考点 二叉排序树的生成 解析 根据二叉排序树的生成方法，不同的序列是 A 选项。15.下列关于 m 阶 B 树的叙述中，错误的是_（分数：2.00）A.每个结点至多有 m 个关键字 B.每个结点至多有 m 棵子树

20、C.插入关键字时，通过结点分裂使树高增加D.删除关键字时通过结点合并使树高降低解析：考点 B 树的特征的判断 解析 m 阶 B 树中，若树非空，则根结点至少有一个关键字，最多有 m-1 个关键字。二、填空题(总题数：10，分数：20.00)16.数据元素之间的逻辑关系称为数据的 1 结构。 （分数：2.00）解析：逻辑 考点 数据的逻辑结构的概念 解析 数据元素之间的逻辑关系称为数据的逻辑结构。17.在线性表中，表的长度定义为 1。 （分数：2.00）解析：数据元素的个数 考点 线性表中表的长度的计算 解析 在线性表中，表的长度定义为数据元素的个数。18.用 S 表示入栈操作，X 表示出栈操作

21、，若元素入栈的顺序为 1、2、3、4，为了得到 1、3、4、2 的出栈顺序，相应的 S 和 X 的操作序列为 1。 （分数：2.00）解析：SXSSXSXX 考点 栈的操作 解析 若元素入栈的顺序为 1、2、3、4，为了得到 1、3、4、2 的出栈顺序，相应的 S 和 X 的操作序列为 SXSSXSXX。19.在二叉树中，带权路径长度最短的树称为 1。 （分数：2.00）解析：哈夫曼树 考点 哈夫曼树的概念 解析 在二叉树中，带权路径长度最短的树称为哈夫曼树。20.已知广义表 G，head(G)与 tail(G)的深度分别为 4 和 6，则 G 的深度是 1。 （分数：2.00）解析：6 考点

22、 广义表的深度 解析 若表尾深度大于表头深度，那么线性表的深度为表尾的深度。21.一组字符(a，b，c，d)在文中出现的次数分别为(7，6，3，5)，字符“d“的哈夫曼编码的长度为 1。 （分数：2.00）解析：2 考点 哈夫曼编码 解析 先构造出相应的哈夫曼树，然后进行编码。22.在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 1 条边。 （分数：2.00）解析：n-1 考点 连通无向图的边数的问题 解析 在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 n-1 条边。23.直接选择排序算法的时间复杂度是 1。 （分数：2.00）解析：O(n 2 ) 考点 直接选择排序算法

23、的时间复杂度 解析 直接选择排序算法的时间复杂度是 O(n 2 )。24.对于长度为 81 的表，若采用分块查找，每块的最佳长度为 1。 （分数：2.00）解析：9 考点 分块查找 解析 对于长度为 81 的表，若采用分块查找，每块的最佳长度为 9。25.用二叉链表保存有 n 个结点的二叉树，则结点中有 1 个空指针域。 （分数：2.00）解析：n+1 考点 二叉链表中空指针域的个数 解析 用二叉链表保存有 n 个结点的二叉树，则结点中有 n+1 个空指针域。三、解答题(总题数：4，分数：20.00)26.假设 Q 是一个具有 11 个元素存储空间的循环队列(队尾指针指向队尾元素的下一个位置，

24、队头指针指向队头元素)，初始状态 Q.front=Q.rear=0；写出依次执行下列操作后头、尾指针的当前值。 a，b，c，d，e，f 入队，a，b，c，d 出队；(1)Q.front=_；Q.rear=_。 g，h，i，j，k，1 入队，e，f，g，h 出队；(2)Q.front=_；Q.rear=_。 M，n，o，P 入队，i，j，k，l，m 出队；(3)Q.front=_；Q.rear=_。 （分数：5.00）_正确答案：()解析：Q.front=4；Q.rear=6。 Q.front=8；Q.rear=1。 Q.front=2；Q.rear=5。考点 循环队列的操作27.已知一个无向图

25、如下图所示，以为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。 （分数：5.00）_正确答案：()解析：最小生成树的生成过程如下： 用归并排序法对序列(98，36，-9，0，47，23，1，8)进行排序，问：（分数：5.00）(1).一共需要几趟归并可完成排序。（分数：2.50）_正确答案：()解析：需要 3 趟(2).写出第一趟归并后数据的排列次序。（分数：2.50）_正确答案：()解析：(36，98，9，0，23，47，1，8)考点 归并排序法的应用一组记录关键字(55，76，44，32，64，82，20，16，43)，用散列函数 H(key)=key%11 将记

26、录散列到散列表 HT_中去，用线性探测法解决冲突。（分数：5.00）(1).画出存入所有记录后的散列表。（分数：2.50）_正确答案：()解析：存入所有记录的散列表为： (2).求在等概率情况下，查找成功的平均查找长度。（分数：2.50）_正确答案：()解析：ASL 成功=(1+2+6+1+2+1+1+4)/9=20/9考点 散列表的求解以及平均查找长度的计算四、程序阅读题(总题数：4，分数：20.00)顺序表类型定义如下： #define ListSize 100 typedef struct int dataListSize; int length; SeqList; 阅读下列算法，并回答

27、问题： void f30(SeqList *L) int i, j; i=0; while(iL-length) if(L-datai%2!=0) for(j=i+1; jL-length; j+ L-dataj-1=L-dataj; L-length-; else i+ （分数：5.00）(1).若 L-data 中的数据为(22，4，63，0，15，29，34，42，3)，则执行上述算法后 L-data 中的数据以及 L-length 的值各是什么?（分数：2.50）_正确答案：()解析：data=22，4，0，34，42 length=5。(2).该算法的功能是什么?（分数：2.50）_

28、正确答案：()解析：删除顺序表中的奇数数据元素。 考点 删除顺序表中的奇数数据元素的算法 解析 通过阅读程序，可知其为删除顺序表中的奇数数据元素的操作，可得出 data=22，4，0，34，42，length=5。有向图的邻接矩阵类型定义如下： #define MVN 100 /最大顶点数 typedef int EType; /边上权值类型 typedef struct EType edgesMVNMVN; /邻接矩阵，即边表 int n; /图的顶点数 MGraph; /图类型 例如，一个有向图的邻接矩阵如下所示： （分数：5.00）(1).step1 到 step2 之间的二重循环语句的

29、功能是什么?（分数：2.50）_正确答案：()解析：统计输出图中边的数目。(2).step2 之后的二重循环语句的功能是什么?（分数：2.50）_正确答案：()解析：统计输出图中每个结点的入度数。 考点 图的操作 解析 step1 到 step2 之间的二重循环语句的功能是统计输出图中边的数目；step2 之后的二重循环语句的功能是统计输出图中每个结点的入度数。阅读下列算法，并回答问题： void f32(int r, int n) Int i, j; for(i=2; in; i+) r0=ri; j=i-1; while(r0rj) rj+1=rj; j=j-1; rj+1=r0; （分数

30、：5.00）(1).这是哪一种插入排序算法?该算法是否稳定?（分数：2.50）_正确答案：()解析：直接插入排序，该算法是稳定的。(2).设置 r0的作用是什么?（分数：2.50）_正确答案：()解析：r0的作用是监视哨兵。 考点 排序算法的判定 解析 根据算法，可知其为直接插入排序的算法，该算法是稳定的。程序中 r0的作用是监视哨兵。顺序表类型定义如下： typedef int SeqList100; 阅读下列算法，并回答问题： void f33(SeqList r, int n) int a, b, i; if(r0r1) a=r0; b=r1; elsea=r1; b=r0; for(i

31、=2; in; i+) if(ria) a=ri; else if(rib) b=ri; printf(“a=%d, b=%d。/n“, a, b); （分数：5.00）(1).给出该算法的功能；（分数：2.50）_正确答案：()解析：算法的功能是求最大最小值。(2).给出该算法的时间复杂度。（分数：2.50）_正确答案：()解析：时间复杂度为 O(n)。 考点 求最大最小值的问题 解析 根据算法，可知其为求最大最小值的问题，并且其时间的复杂度可计算出为 O(n)。五、算法设计题(总题数：1，分数：10.00)28.二叉树的存储结构类型定义如下： typedef struct node int

32、 data; struct node *lchild, *rchild; BinNode; typedef BinNode *BinTree; 编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。 函数的原型为：void f34(BinTree T, int *count, int *sum) *count 和*sum 的初值为 0。 （分数：10.00）_正确答案：()解析：void f34(BinTree T, int *count, int *sum) if(T) if(T-lchild *sum+=T-data; f34(T-lchild, count, sum); f34(T-rchild, count, sum); 考点 求只有一个孩子结点的结点总数，并计算这些结点的数据值的和的算法