文档介绍：该【数据结构试题及答案9 】是由【小屁孩】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【数据结构试题及答案9 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..数据结构复****思考试题○9一、单项选择题,在括号内填写所选择的标号(每小题1分,共12分),则应把形参变量说明为()参数。()。。。。。?n的对称矩阵A,将其上三角部分按行存放在一个一维数组B中,A[0][0]存放于B[0]中,那么第i行的对角元素A[i][i]存放于B中()处。A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/,单链表B长度为n,若将B联接在A的末尾,其时间复杂度应为()。(1)(m)(n)(m+n),则判断队空的条件为()。==!=!===(intn){//n大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为()次。++-(假定树根结点的层号为0)的完全二叉树中,所含结点个数不小于()。-+-(b,c(e,f(g)),d),当用左子女-右兄弟链表表示时,右指针域非空的结点个数为()。、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为9-1:..()。(1)(logn)(n)(nlogn)()条有向边。-(n-1)/(n-1)()次序遍历。(不考虑年份,只考虑月、日)来排序,那么使用下列排序算法中()算法最快。、填空题,在横线处填写合适内容(每小题1分,共12分)、________、索引和散列等四种。。这种数组在声明它时需要使用数组指针。。,又被称为___________表。,或自己定义自己,则称这个对象是_________的对象。(b(c,d(e,f),g(h)),i(j,k(x,y))),结点f的层数为_________。假定树根结点的层数为0。-右兄弟表示法转换成对应的二叉树,则该二叉树中树根结点肯定没有________子女。,若元素的值小于根结点的值,则应把它插入到根结点的________上。=(V,E),V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>},从顶点1出发,对图G进行广度优先搜索的序列有________种。,若出现逆序排列就交换它们的位置,这种排序方法叫做__________排序。9-2:..。=10000的线性表进行二级索引存储,每级索引表中的索引项是下一级20个表项的索引,则一级索引表的长度为________。三、判断题,在每小题前面打对号表示正确或打叉号表示失败(每小题1分,共10分),是用户根据应用需要建立的。,都可以按下标随机(或直接)访问。,队头指针指向队头元素的后一个位置。。,假定每个结点只有左子女,没有右子女,对它分别进行中序遍历和后序遍历,则具有相同的结果。,若各元素的搜索概率不等,则各元素应按照搜索概率的降序排列存放,则可得到最小的平均搜索长度。,若各结点的搜索概率不等,使得搜索概率越小的结点离树根越近,则得到的是最优二叉搜索树。,加速任一关键活动都能使整个工程提前完成。。。四、运算题(前2小题,每小题6分,后3小题,每小题8分,共36分)[10][20],按行存放于一个连续的存储空间中,A[0][0]的存储地址是200,每个数组元素占1个存储字,则A[6][2]的存储字地址是多少。A[6][2]的存储字地址:,求该二叉树的高度(假定空树的高度为-1)和度为2、度为1及度为0的结点个数。中序序列:c,b,d,e,a,g,i,h,j,f后序序列:c,e,d,b,i,j,h,g,f,a高度:度为2的结点数:度为1的结点数:度为0的结点数:9-3:..(36,75,83,54,12,67,60,40),将按次序把每个结点插入到初始为空的一棵AVL树中,请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”,“不调整”的结点数各是多少?左单旋转结点个数:右单旋转结点个数:先左后右双旋转结点个数:先右后左双旋转结点个数:不调整结点个数::V={0,1,2,3,4,5,6};E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12};试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径,在下面填写对应的路径长度。顶点:01234560路径长度:{36,25,25*,62,40,53},请写出在进行快速排序的过程中每次划分后数据表的变化。(0)[362525*624053](1)(2)(3)五、算法分析题(每小题6分,共18分)。voidmatrimult(inta[M][N],intb[N][L],intc[M][L]){//M、N、L均为全局整型量inti,j,k;for(i=0;i<M;i++)for(j=0;j<L;j++)c[i][j]=0;for(i=0;i<M;i++)for(j=0;j<L;j++)for(k=0;k<N;k++)c[i][j]+=a[i][k]*b[k][j];}9-4:..功能为:时间复杂度为:(Hanoi)的递归算法如下:voidHANOI(intn,intpeg1,intpeg2,intpeg3){if(n==1)cout<<peg1<<“→”<<peg3<<endl;else{HANOI(n-1,peg1,peg3,peg2);cout<<peg1<<“→”<<peg3<<endl;HANOI(n-1,peg2,peg1,peg3);}}当使用HANOI(3,1,2,3)进行调用时,给出else子句中的cout语句的输出结果。:structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};其中data为结点值域,left和right分别为指向左、右子女结点的指针域。参数t指向一棵二叉搜索树,该树的广义表表示为:25(10(5,16(12)),40(32(,38)))。根据下面算法按标号把答案填写到算法后面相应标号的位置。执行LN(pt,40)调用后返回的值为__(1)_____。执行LN(pt,38)调用后返回的值为__(2)_____。执行LN(pt,5)调用后返回的值为___(3)_____。intLN(BinTreeNode*t,ElemTypeX){if(t==NULL)return0;elseif(t->data==X)return1;elseif(t->data>X)return1+LN(t->left,X);elsereturn1+LN(t->right,X);}(1)(2)(3)六、算法设计题(每小题6分,共12分)9-5:..,在一个顺序表A中查找出具有最大值和最小值的整数。函数的原型如下所示,原型的参数表中给出顺序表对象为A,通过算法执行,从参数表中的引用参数Max中得到表中的最大整数,Min中得到表中的最小整数。注意,函数中可使用顺序表的如下两个公有函数:intLength();求表的长度;intgetData(intk);提取第k个元素的值。#include“”template<classT>voidFindMaxMin(SeqList<int>&A,int&Max,int&Min);:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域,left和right分别为指向左、右子女结点的指针域,根据下面函数声明编写出判断两棵二叉树是否相等的算法,若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。intBTreeEqual(BinTreeNode*T1,BinTreeNode*T2);9-6:..数据结构试题参考解答及评分标准一、单项选择题,在括号内填写所选择的标号(每小题1分,共12分)、填空题,在横线处填写合适内容(每小题1分,共12分)(logn)、判断题,在每小题前面打对号或打叉号(每小题1分,共10分)、运算题(前2小题,每小题6分,后3小题,每小题8分,共36分)[6][2]的存储字地址:322//6分答案说明:按行存储时,计算A[i][j]地址的公式为LOC(i,j)=LOC(0,0)+(i*n+j)*d其中首地址LOC(0,0)=200,每个数组元素的存储占用数d=1,二维数组的列数n=20,根据题意,元素A[6][2]的存储地址为LOC(6,2)=200+(6*20+2)*1=:4//2分度为2的结点数:3//2分度为1的结点数:3//1分度为0的结点数:4//:1//2分右单旋转结点个数:0//2分先左后右双旋转结点个数:1//2分先右后左双旋转结点个数:0//1分不调整结点个数:6//,最多扣全部8分。顶点:01234560161014252131路径长度:9-7:..5.(0)[362525*624053](1)[25*25]36[624053]//3分(2)25*2536[5340]62//3分(3)25*2536405362//2分五、算法分析题(每小题6分,共18分):矩阵相乘,即a[M][N]×b[N][L]→c[M][L]。//3分时间复杂性为:O(M×N×L)。//→2//2分1→3//2分2→3//2分3.(1)2//2分(2)4//2分(3)3//2分六、算法设计题(每小题6,共12分)#include“”template<classT>voidFindMaxMin(SeqList<int>&A,int&Max,int&Min){Max=Min=(0);for(inti=1;i<();i++){if((i)>Max)Max=(i);elseif((i)<Min)Min=(i);}},如注释。intBTreeEqual(BinTreeNode*T1,BinTreeNode*T2){//若两棵树均为空则返回1表示相等if(T1==NULL&&T2==NULL)return1;//1分//若一棵为空一棵不为空则返回0表示不等elseif(T1==NULL||T2==NULL)return0;//2分//若根结点值相等并且左、右子树对应相等则两棵树相等elseif(T1->data==T2->data&&BTreeEqual(T1->left,T2->left)&&BTreeEqual(T1->right,T2->right))return1;//5分9-8:..//若根结点值不等或左、右子树对应不等则两棵树不等elsereturn0;//6分}另一个参考答案:intBTreeEqual(BinTreeNode*T1,BinTreeNode*T2){//若两棵树均为空或实际上是同一棵树时返回1表示相等if(T1==T2)return1;//1分//若一棵为空一棵不为空则返回0表示不等if(T1==NULL||T2==NULL)return0;//2分//若根结点值不等返回0表示不等if(T1->data!=T2->data)return0;//3分//若根结点值相等则两棵树是否相等取决于它们的左、右子树是否对应相等returnBTreeEqual(T1->left,T2->left)&&BTreeEqual(T1->right,T2->right);//6分}9-9