全国2011年10月自考数据结构导论考试试题,答案,笔记

201110数据结构导论试题课程代码:02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。SQe6依次通过栈S，元素退栈后即进入队列Q6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少为( B )A.2 B.3C.4 D.6设计一个判别表达式左右括号是否配对出现的算法，采用的最佳数据结构( D )A.线性表的顺序存储结构C.线性表的链式存储结构下列程序段的时间复杂度(A i=0；s=0；while（s<n）{i++；s=s+i；}nA.O（ ）nC.O(n)

B.队列D.栈B.O(logn)D.栈2D.O(n2)An×nAA(1≤i,j≤n,i≤j)以列优先顺序存放在一维数组ij元素B［1］至B［n(n+1)/2］中，则元素A(i≤j)在B中的位置为(B )B.j(j-l)/2+iijB.j(j-l)/2+iA.i(i-l)/2+jC.j(j-l)/2+i-1 D.i(i-l)/2+j-1在有向图G的拓扑序列中，若顶点V在顶点V之前，则下列情形不可能出现的( D )D.G中有一条从VD.G中有一条从Vj到Vi的路径i A.G中有弧<V，Vi C.GV，V>

B.GVi到Vj的路径i jviviVJ那么说明只能i到j，不能有回路，切记。A.［da，ax，eb，de，bb］ff［ha，gc］下列序列中，由第一快速排序可得到的序列（排序的关键字类型是字符串）(A )A.［da，ax，eb，de，bb］ff［ha，gc］B.［cd，eb，ax，da］ff［ha，gc，bb］C.［gc，ax，eb，cd，bb］ff［da，ha］ D.［ax，bb，cd，da］ff［eb，gc，ha］C.堆排序不稳定的排序方法是(C A.直接插入排序C.堆排序

B.冒泡排序 注：冒选插归 稳定D.二路归并排序 希堆快 不稳定m=14h（k）=k%114二次探测法49的记录的存储位置是(D )153815386184A.3C.8

B.5注：解题思路：1.先用散列函数求余数，所求余数看是否与表格中的位置是否冲突，若冲突，使用（余数注：解题思路：1.先用散列函数求余数，所求余数看是否与表格中的位置是否冲突，若冲突，使用（余数+i2）mod表长,i=1,2,3….直到算出的结果表格里没有即可。解题过程：49%11=5,冲突----（5+12）mod13=6，冲突----（5-12）mod13=4（5+22）mod13=9（OK）9.若元素1，2，3依次进栈，则退栈不可能出现的次序(C )A.3，2，1C.3，1，2(不符合线性结构)10.直接插入排序的时间复杂度是(AB.2，1，3D.1，3，2)A.O（n2）B.O（nlogn）2C.O（n）稀疏矩阵是指(C A.元素少的矩阵C.有少量非零元素的矩阵

D.O（logn）2B.有少量零元素的矩阵D.行数、列数很少的矩阵 解题说明：深度为k（k≥1）的二叉树，结点数最多( B )A.2k B.2k-1

C.2k-1

(层) D.2k-1-1

来，以此类推。最后一层是层13.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树带权路径长为( C)

数（最后一层A.23

B.37 23图解C.44D.46C.44

权数相加）9149有n个顶点的有向完全图的弧数( C ) 1A.n2C.n（n-1）注：无向图有n（n-1）/2

B.2n 7 7D.2n（n+1） 2图的深度优先搜索类似于二叉树的(A ) 2 5D.9A.先根遍历（中左右）D.9C.后根遍历

B.中根遍历 39*1+2*2+3*(2+5)=44D.层次遍历9*1+2*2+3*(2+5)=44二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分16.下列程序段的时间复杂度O(n2) 。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;数据结构中结点按逻辑关系依次排列形成一条“锁链的结构是线性结。在表长为n的顺序表上做删除运算，平均要移动的结点个数n(n-1)/2 注：删除第i，需要向前移动n-i个，先后需要移动n-i+1个。在带有头结点的单循环链表head中，指针p所指结点为尾结的条件_p->next=head 。队列又称为 先进先的线性表注：栈又称为后进先出线性表顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作_sq->top=0 。对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n，则n=__n-1_ （性质3）2 2 0个结点。1：二叉树第i（i≥1）2i-1个结点。性质2：深度为k（k≥1）的二叉树至多有2k-1结点。一棵具有n个结点的二叉树采用二叉链表存，则二叉链表中指孩子结点的指有 n-1 个。若连通图G的顶点个数为n，则图G的生成树的边数_n-1 。一个具有n个顶点的无向图的边数最多_n(n-1)/2 注：有向完全图为n（n-1）中根遍历二叉排序树所得到的结点访问序列是键值递增 序列。冒泡排序的平均时间复杂度O(n2) 。注：冒选--希堆归--O（nlogn）希归不稳228.将序列{60，20，23，68，94，70，73}建成堆，则只需把20与 60 互相交换。解题思路：解题思路：先将给出的序列以完全二叉树依次写出。大根，那么找最大的作为根。逐渐减大。调整位置即可。三、应用题(本大题共5小题，每小题6分，共30分)如题29图所示，在栈的输入端元素的输入顺序为，进栈过程中可以退栈，写出在栈的输出端以AB题29图

答：ABCDACBDADCBABDCBACDBADCDBCABCDA注:根据后进先出原则，进行排列组合即可。有n个数，就有2n-1种排列方法。答：先根遍历为：中根遍历为：DBGEACHF后根遍历为：答：先根遍历为：中根遍历为：DBGEACHF后根遍历为：DGEBHFCA中根遍历：左中又后根遍历：左右中题30图ACEDACEDGJHKBFI解题技巧剖析：1.2.3.31先找关键分界点，本题为AC,所以有n+1个树，本题为2+1=3.由于所有的从分界点开始，所有的右子树（包括其下部的分支）是从分界点割裂下来的（尤其是连续右子树，所以要把右子树连（如红箭头所示）45（箭头所示）4.当独立结点有≥2个孩子的时候，左子树不动，右子树连上即可。（如黄箭头所示。对于有向无环图：叙述求拓扑排序算法的基本步骤；324答：1.拓扑排序法的基本步骤为：输出该顶点。的入度。重复2成或图中再也没有入度为零的顶点为止。2.4种不同的拓扑排序为：13245678123456781234785631245678判别以下序列是否为堆。如果不是，则把它调整为堆。（110，8，4，735，3，4，5，6，2；（2127033652，5，4，9，8，33。

32

题32图为堆；（2）不为堆；1212703324336524564865705648928633928633概念：堆是一键值序列{k1,k2,k3….kn}，对所有n/2满足：kk12kki≤2ii≤2i+12433结点比下部结点小。若不是，调整即可。可。65335648928670四、算法设计题(本大题共2小题，每小题7分，共14分)34.n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A［1］至A［n］中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。答：voidBiTreeCreat(ElemTypeA[],inti){BiTreetree;If(i<=n){tree=(BiTree)malloc(sizeof(BiNode));Tree->data=A[i];}If(2*i>n){tree->lchild=NULL;elsetree->lchild=Creat(A,2*i)}If（2*i+1>n）{tree->rchild=NULL;elsetree->rchild=Creat(A,2*i+1)}return(t