数据结构真题2012年10月

1、数据结构真题2021年10月总分：100.00 ,做题时间：90分钟一、单项选择题总题数：15,分数：30.001 .一个算法的时间消耗的数量级称为该算法的 分数：2.00A.效率B.难度C.可实现性D.时间复杂度 V解析：考点算法的时间复杂度的概念解析一个算法的时间消耗的数量级称为该算法的时间复杂度.2 .顺序表便于分数：2.00A.插入结点B.删除结点C.按值查找结点D.按序号查找结点V解析：考点顺序表的特征解析顺序表便于按序号查找结点.3.设带头结点的单循环链表的头指针为head,指针变量P指向尾结点的条件是 分数：2.00A.p- > next- > next=headB.

2、p- > next=head VC.p- > next- >next=NULLD.p- > next=NULL解析：考点指针变量p指向尾结点的判定条件解析单循环链表的指针变量 p指向尾结点的判定条件是p-> next=head.4 .设以数组A0.m-1存放循环队列,front指向队头元素,rear指向队尾元素的下一个位置,那么当前队 列中的元素个数为分数：2.00A.rear-front+m%m VB.rear-front+1C.front-rear+m%mD.rear-front%m解析：考点队列中元素个数的计算解析队列中元素的个数为rear-front+m%

3、m5 .以下关于顺序栈的表达中,正确的选项是 分数：2.00A.入栈操作需要判断栈满,出栈操作需要判断栈空VB.入栈操作不需要判断栈满,出栈操作需要判断栈空C.入栈操作需要判断栈满,出栈操作不需要判断栈空D.入栈操作不需要判断栈满,出栈操作不需要判断栈空解析：考点顺序栈的性质的判断解析入栈操作需要判断栈满,出栈操作需要判断栈空.6 .A是一个10X10的对称矩阵,假设采用行优先的下三角压缩存储,第一个元素a 0,0的存储地址为1,每个元素占一个存储单元,那么a 7,5的地址为分数：2.00A.25B.26C.33D.34 V解析：考点对称矩阵的元素的地址的计算解析假设对称矩阵采用下三角压缩存储

4、,根据其地址的计算公式,可得到所求元素的地址.7 .树的后序遍历等价于该树对应二叉树的 分数：2.00A.层次遍历8 .前序遍历C.中序遍历 VD.后序遍历解析：考点树的遍历与二叉树遍历的关系解析树的后序遍历等价于该树对应的二叉树的中序遍历.8 .使用二叉线索树的目的是便于 分数：2.00A.二叉树中结点的插入与删除B.在二叉树中查找双亲C.确定二叉树的高度D.查找一个结点的前驱和后继V解析：考点二叉线索树的使用目的解析二叉线索树的使用目的是便于查找一个结点的前趋和后继.9 .设无向图的顶点个数为 n,那么该图边的数目最多为 分数：2.00A.n-1B.nn-1/2 VC.nn+1/2D.n2

5、解析：考点无向图的边数的问题解析无向图的边数最多为 nn-1/2 o10 .可进行拓扑排序的图只能是 分数：2.00A.有向图B.无向图C.有向无环图VD.无向连通图解析：考点拓扑排序的图的要求解析可进行拓扑排序的图只能是有向无环图.11 .以下排序方法中稳定的是 分数：2.00A.直接插入排序VB.直接选择排序C.堆排序D.快速排序解析：考点排序方法稳定性的判断解析直接插入排序是稳定的,直接选择排序、堆排序以及快速排序是不稳定的.12 .以下序列不为堆的是分数：2.00A.75, 45, 65, 30, 15, 25B.75, 65, 45, 30, 25, 15C.75 , 65, 30,

6、 15, 25, 45 VD.75 , 45, 65, 25, 30, 15解析：考点堆的判断解析根据堆的概念,可判断出 75, 65, 30, 15, 25, 45不为堆.13 .对线性表进行二分查找时,要求线性表必须是 分数：2.00A.顺序存储B.链式存储C.顺序存储且按关键字有序排列VD.链式存储且按关键字有序排列解析：考点二分查找对线性表的要求解析对线性表进行二分查找时,要求线性表必须是顺序存储且按关键字有序排列.14 .分别用以下序列生成二叉排序树,其中三个序列生成的二叉排序树是相同的,不同的序列是 分数：2.00A.4 , 1, 2, 3, 5 VB.4 , 2, 3, 1, 5

7、C.4 , 5, 2, 1, 3D.4 , 2, 1, 5, 3解析：考点二叉排序树的生成解析根据二叉排序树的生成方法,不同的序列是A选项.15 .以下关于m阶B树的表达中,错误的选项是 分数：2.00A.每个结点至多有m个关键字 VB.每个结点至多有 m棵子树C.插入关键字时,通过结点分裂使树高增加D.删除关键字时通过结点合并使树高降低解析：考点B树的特征的判断解析m阶B树中,假设树非空,那么根结点至少有一个关键字,最多有 m-1个关键字.二、填空题总题数：10,分数：20.0016 .数据元素之间的逻辑关系称为数据的1结构.分数：2.00解析：逻辑考点数据的逻辑结构的概念解析数据元素之间的

8、逻辑关系称为数据的逻辑结构.17 .在线性表中,表的长度定义为1.分数：2.00解析：数据元素的个数考点线性表中表的长度的计算解析在线性表中,表的长度定义为数据元素的个数.18 .用S表示入栈操作,X表示出栈操作,假设元素入栈的顺序为1、2、3、4,为了得到1、3、4、2的出栈顺序,相应的S和X的操作序列为1.分数：2.00解析：SXSSXSXX居点栈的操作解析假设元素入栈的顺序为1、2、3、4,为了得到1、3、4、2的出栈顺序,相应的 S和X的操作序列为 SXSSXSXX19 .在二叉树中,带权路径长度最短的树称为1.分数：2.00解析：哈夫曼树考点哈夫曼树的概念解析在二叉树中,带权路径长度

9、最短的树称为哈夫曼树.20 .广义表 G headG与tailG的深度分别为4和6,那么G的深度是1.分数：2.00解析：6 考点广义表的深度解析假设表尾深度大于表头深度,那么线性表的深度为表尾的深度.21 .一组字符a , b, c, d在文中出现的次数分别为7 , 6, 3, 5,字符"d的哈夫曼编码的长度为1.分数：2.00解析：2 考点哈夫曼编码解析先构造出相应的哈夫曼树,然后进行编码.22 .在一个具有n个顶点的无向图中,要连通全部顶点至少需要1条边.分数：2.00解析：n-1 考点连通无向图的边数的问题解析在一个具有n个顶点的无向图中,要连通全部顶点至少需要n-1条边.2

10、3 .直接选择排序算法的时间复杂度是1.分数：2.00解析：On 2 考点直接选择排序算法的时间复杂度解析直接选择排序算法的时间复杂度是On 2 o24 .对于长度为81的表,假设采用分块查找,每块的最正确长度为1.分数：2.00解析：9 考点分块查找解析对于长度为81的表,假设采用分块查找,每块的最正确长度为9.25 .用二叉链表保存有n个结点的二叉树,那么结点中有1个空指针域.分数：2.00解析：n+1 考点二叉链表中空指针域的个数解析用二叉链表保存有n个结点的二叉树,那么结点中有n+1个空指针域.三、解做题总题数：4,分数：20.0026.假设Q是一个具有11个元素存储空间的循环队列队尾

11、指针指向队尾元素的下一个位置,队头指针指向队头元素,初始状态Q.front=Q.rear=0 ；写出依次执行以下操作后头、尾指针的当前值.a,b,c, d, e, f 入队,a,b,c, d 出队；1Q.front= ； Q.rear= .g,h,i , j , k, 1 入队,e,f,g, h 出队；2Q.front= ； Q.rear= .M n, o, P入队,i , j , k, l , m出队；3Q.front= ； Q.rear= .分数：5.00 正确答案：解析：Q.front=4 ； Q.rear=6 . Q.front=8 ； Q.rear=1 . Q.front=2 ； Q

12、.rear=5 .考点循环队列的操作27.一个无向图如以下列图所示,以为起点,用普里姆Prim算法求其最小生成树,画出最小生成树的构造过程.分数：5.00 正确答案：解析：最小生成树的生成过程如下：考点Prim 算法求最小生成树的过程用归并排序法对序列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

13、, 64, 82, 20, 16, 43,用散列函数 Hkey=key%11将记录散列到散列表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 100typedef structint dataListSize;int len

14、gth;SeqList;阅读以下算法,并答复以下问题：void f30(SeqList *L)int i, j;i=0;while(i < L- > length)if(L- >datai%2!=0)for(j=i+1; j < L- >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->leng

15、th的值各是什么(分数：2.50)正确答案：解析:data=22 , 4, 0, 34, 42 length=5（2） .该算法的功能是什么分数：2.50正确答案：解析：删除顺序表中的奇数数据元素.考点删除顺序表中的奇数数据元素的算法解析通过阅读程序,可知其为删除顺序表中的奇数数据元素的操作,可得出 data=22 , 4, 0, 34,42 , length=5 .有向图的邻接矩阵类型定义如下：#define MVN 100 /最大顶点数typedef int EType; /边上权值类型typedef structEType edgesMVNMVN;/ 邻接矩阵,即边表int n; /图的

16、顶点数MGraph; / 图类型例如,一个有向图的邻接矩阵如下所示：阅读以下算法,并答复以下问题：Void f31(MGraph G) Int i, j, k=0;Step1;for(i=0; i< G.n; i+)for(j=0; j< G.n; j+)if(G.edgesij=1)k+;printf("%d/n", k);step2:for(j=0; j< G.n; j+) k=0;for(i=0; i< G.n; j+)if(G.edgesij=1)k+;printf("%d/n", k);(分数：5.00)（1） .ste

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

18、r0;(分数：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(r0<r1)a=r0; b=r1;>elsea=r1; b=r0; for(i=2; i < n; i+) if(ri < a) a=ri; else if(ri >b) b=ri; printf("a=%d, b=%d . /n, a, b); (分数：5.00)(1) .给出该算法的功能；(分数：2.50)正