--PAGE--word.zl-以下与数据的存储构造无关的术语是〔c〕C、哈希
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
一个向量第一个元素的存储地址是100，每个元素的长度为2，那么第5个元素的地址是〔B〕B、108假设带头结点的单向循环链表的头指针为head,那么该链表为空的判定条件是〔C〕C、head–>next==head假设进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进展，那么不可能出现的出栈序列是〔D〕D、2，3，5，1，6，4以下关键字序列中，构成小根堆的是〔A〕A、{12，21，49，33，81，56，69，41}以下数据构造中，不属于二叉树的是〔A〕A、B树用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，假设结点A[i]有右孩子，那么其右孩子是〔C〕。C、A[2i+1]设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，那么T中叶子数为〔D〕D、8有数据{53，30，37，12，45，24，96}，从空二叉树开场逐个插入数据来形成二叉排序树，假设希望高度最小，那么应选择下面哪个序列输入〔B〕B、37，24，12，30，53，45，96对下面有向图给出了四种可能的拓扑序列，其中错误的选项是〔C〕C、5，1，6，3，4，2m阶B-树中所有非终端〔除根之外〕结点中的关键字个数必须大于或等于(B)B、[m/2]-1散列文件也称为(C)B、索引文件数据构造是〔D〕D、相互之间存在一种或多种特定关系的数据元素的集合从逻辑关系来看，数据元素的直接前驱为0个或1个的数据构造只能是〔C〕C、线性构造和树型构造设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，那么同样表示p指针所指向结点的表达式是〔D〕D、p→llink→rlink假设栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，那么栈满的条件是〔B〕B、top[1]+1=top[2]假设一棵二叉树有11个叶子结点，那么该二叉树中度为2的结点个数是〔A〕A、10树的先根序列等同于与该树对应的二叉树的〔A〕A、先序序列下面关于哈希(Hash，杂凑)查找的说确的是(C)C、不存在特别好与坏的哈希函数，要视情况而定以下序列中，〔D〕是执行第一趟快速排序后所得的序列。D、[68，11，69，23，18][93，73]以下关键字序列中，构成小根堆的是(D)D、(15，28，46，37，84，58，62，41)ISAM文件和VASM文件属于(C)C、索引顺序文件下面程序段的时间复杂度为〔C〕for(i=0;i
next=s->next；s->next=p；为便于判别有向图中是否存在回路，可借助于〔D〕D、拓扑排序算法假设以S和X分别表示进栈和退栈操作，那么对初始状态为空的栈可以进展的栈操作系列是〔D〕D、SSSXXSXX设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,那么栈的容量至少应该是(B)B、3假设以数组A[m]存放循环队列的元素。队列的长度为length，指针rear指向队尾元素的下一个存储位置，那么队头元素所在的存储位置为〔B〕。B、(rear-length+m)%m在一个链队列中，front和rear分别为头指针和尾指针，那么插入一个结点s的操作为〔D〕。D、rear->next=s;rear=s;对于哈希函数H(key)=key%13,被称为同义词的关键字是〔D〕D、25和51采用二叉链表存储的n个结点的二叉树，共有空指针〔A〕个。A、n+1连通网的最小生成树是其所有生成树中〔D〕D、边的权值之和最小的生成树对记录序列(314，298，508，123，486，145)依次按个位和十位进展两趟基数排序之后所得结果为〔B〕B、508，314，123，145，486，298任何一个无向连通图的最小生成树(C)。C、一棵或多棵无向图的邻接矩阵是一个(C)C、对称矩阵设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树，那么以下说法中不正确的选项是(B)。B、G’为G连通分量以v1为起始结点对以下图进展深度优先遍历，正确的遍历序列是〔D〕D、v1，v2，v5，v6，v7，v3，v4下面几个符号串编码集合中，不是前缀编码的是〔B〕B、{0,1,00,11}希尔排序的增量序列必须是〔B〕。B、递减的采用起泡排序法对n个关键字进展升序排序，假设要使排序过程中比拟关键字的次数最多，那么初始时的序列应满足条件〔D〕D、关键字从大到小排列在以下部排序中(A)是不稳定的。A、希尔排序分别以以下序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)。A、〔100，80，90，60，120，110，130〕在查找过程中，冲突指的是〔C〕。C、不同键值对应一样的存储地址对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比拟元素依次为〔D〕。D、A[7]，A[3]，A[5]，A[4]以v1为起始结点对以下图进展广度度优先遍历，正确的遍历序列是〔A〕v1，v2，v3，v4，v5，v6，v7二、填空题(本大题共10小题，每题2分，假设有两个空格，每个空格1分，共20分)数据的物理构造包括数据元素的存储和数据之间关系的存储。假设一个算法中的语句频度之和为T(n)=1921n+4nlogn,那么算法的时间复杂度为nlogn。下面程序段的时间复杂度是。i=1；while(i<=n)i=i*3；循环队列用数组A[0..m-1]存放其元素值，其头尾指针分别是front和rear，那么当前队列的元素个数是〔rear-front+m〕%m主要是使插入和删除等操作统一〔n-1〕/2。在单链表中设置头结点的作用是深度优先。线性表L=〔a1,a2,…,an〕用数组表示，假定删除表中任一元素的概率一样，那么删除一个元素平均需要移动元素的个数是一样值关键字。一无向图G=〔V，E〕，其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开场遍历图，得到的序列为abecd，那么采用的是前移遍历方法。如果排序过程不改变时间复杂度之间的相对次序，那么称该排序方法是稳定的。从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需出度一个位置。当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的10。假设以邻接矩阵表示有向图，那么邻接矩阵上第i行中非零元素的个数即为顶点vi的sxssxxssxssxxx。一棵含999个结点的完全二叉树的深度为12。假设S和X分别表示进栈和出栈操作，由输入序列“ABC〞得到输出序列“BCA〞的操作序列为SSXSXX，那么由“a*b+c/d〞得到“ab*cd/+〞的操作序列为4。.如下图的有向无环图可以排出L->next->next==L边种不同的拓扑序列。从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为384。带头结点的双循环链表L中只有一个元素结点的条件是队列。求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中边稠密、边稀疏的数目正相关。一棵完全二叉树中共有768结点，那么该树中共有5个叶子结点。实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要8、64存放被访问的结点以实现遍历。Prim〔普里姆〕算法适用于求2h-1的网的最小生成树；kruskal〔克鲁斯卡尔〕算法适用于求2h-1的网的最小生成树。对长度为20的有序表进展二分查找的判定树的高度为n-1。设一棵完全二叉树有128个结点，那么该完全二叉树的深度为n，有_个叶子结点。高度为h的完全二叉树中最少有栈个结点，最多有个结点。设连通图G中有n个顶点e条边，那么对应的最小生成树上有3条边。构造n个结点的强连通图，至少有O(n2)条弧。表达式求值是〔42,13,94,55,05,46,17〕应用的一个典型例子。设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，假设6个元素出队的序列是e2,e4,e3,e6,e5,e1，那么栈的容量至少应该是。快速排序算法在最差的情况下其时间复杂度是。对序列{55，46，13，05，94，17，42}进展基数排序，第一趟排序后的结果是。三、应用题〔本大题共5小题，每题6分，共30分〕二叉树的先序遍历序列ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
：二叉树形态如图请给出邻接表、邻接矩阵及逆邻接表。V1V3V2V4参考答案如下：〔1〕邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertexfirstedge next 〔2〕逆邻接表：〔3〕由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如下图。某段电文的哈夫曼编码为0，请根据该哈夫曼树进展译码，写出原来的电文。答案：原来的电文为：eatst请画出以下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历。12345678答案：12345678先序遍历为：12345687中序遍历为：34867521设散列表为HT[13],散列函数为H(key)=key%13。用闭散列法解决冲突,对以下关键码序列12,23,45,57,20,03,78,31,15,36造表。采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。答案：使用散列函数H(key)=keymod13，有H(12)=12,H(23)=10,H(45)=6,H(57)=5,H(20)=7,H(03)=3,H(78)=0,H(31)=5,H(15)=2,H(36)=10.利用线性探查法造表：012345678910111278150357452031233612(1)(1)(1)(1)(1)(1)(4)(1)(2)(1)搜索成功的平均搜索长度为ASLsucc=(1+1+1+1+1+1+4+1+2+1)=带权图G如下图，画出图G的一棵最小生成树。答：假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，请为这8个字母设计哈夫曼编码。哈夫曼编码为：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000注意：答案不唯一试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69画出与如下图森林对应的二叉树。答：一个散列表如以下图所示：35203348590123456789101112其散列函数为h(key)=key%13,处理冲突的方法为双重散列法，探查序列为：hi=(h(key)+*h1(key))%m=0,1,…，m-1其中：h1(key)=key%11+1答复以下问题：〔1〕对表中关键字35，20，33和48进展查找时，所需进展的比拟次数各为多少？〔2〕该散列表在等概率查找时查找成功的平均查找长度为多少？答：〔１〕对关键字35、20、33和48进展查找的比拟次数为３、２、１、１；〔２〕平均查找长度请画出与以下二叉树对应的森林。答：对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}，〔1〕试构造一棵二叉排序树；〔2〕求等概率情况下的平均查找长度ASL。答：74312596108〔2〕ASL=(1*1+2*2+3*4+4*3)/10=2.9给出以下图对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度答案:邻接矩阵为：ABCDEF其中顶点A的入度为2，出度为1；其中顶点B的入度为2，出度为2；其中顶点C的入度为1，出度为3；图5.32如下所示，求从顶点a到其余各顶点的最短路径。〔给出求解过程〕543223356abdfce答：终点最短路径求解过程b6(a,b)5(a,c,b)c3(a,c)d6(a,c,d)6(a,c,d)e7(a,c,e)7(a,c,e)7(a,c,e)f9(a,c,d,f)9(a,c,d,f)vjcbdefS{a,c}{a,c,b}{a,c,d}{a,c,e}{a,c,d,f}阅读以下算法，并答复以下问题：〔1〕假设串由合法的英文字母和空格组成，并以’\0’作完毕符。设串s=〞⊔⊔I⊔am⊔a⊔⊔⊔student〞(⊔表示空格符)，写出f30〔s〕的返回值；〔2〕简述算法f30的功能。intf30(char*s)答案：(1)4(2)算法功能：统计单词的个数。阅读以下函数,并答复以下问题：〔1〕假设队列q中的元素为(a,b,c,d,e),其中“a〞为队头元素。写出执行函数调用Conv(&q)后的队列q；〔2〕简述算法Conv的功能。答案：e，d，c，b，a将队列里的值反转阅读以下函数,并答复以下问题：整形数组L［1..8］中的元素依次为〔19，18，15，17，16，13，12，10〕，阅读以下函数，并写出执行函数调用sort(L,8)时，对L进展的头两趟〔pass分别为0和1〕处理结果。答案：〔1〕第一趟〔pass=0〕1915181617121310〔2〕第二趟〔pass=1〕1915161812171013keynext带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点构造为：。请在空缺处填入适当容，使其成为一个完整算法。voidf33(LinkListL,LinkListH［］,intm)答案：NULL〔2〕p->next=H[j]p=q以下函数的功能是，对以带头结点的单链表作为存储构造的两个递增有序表〔表中不存在值一样的数据元素〕进展如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入适宜容，使其成为一个完整的算法。答案：〔1〕pre->next=pb〔2〕pre->next=pa〔3〕pre->next=pb阅读算法f30，并答复以下问题：以下算法为有向图拓扑排序,请在空缺处填入适宜的容，使其成为一个完整的算法。答案：(1〕top==-1〔2〕top=graph[j].count〔3〕graph[k].count==0阅读算法f31，并答复以下问题：以下算法功能为在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a中各元素的值都不一样。请在空缺处填入适宜的容，使其成为一个完整的算法。答案：〔1〕(i==k)return;〔2〕i+1〔3〕i-1阅读算法f33，并答复以下问题：以下算法功能为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进展比拟,第二趟对所有偶数的i,将a[i]和a[i+1]进展比拟,每次比拟时假设a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。请在空缺处填入适宜的容，使其成为一个完整的算法。答案：(1)a[i]=t(2)(i=2;i<=n;i+=2)(3)flag四、算法设计题〔本大题共2小题，每题10分，共20分〕单链表的结点类型为Lnode，包含next和data成员。编写算法，实现带头结点单链表的逆置算法。参考答案：voidinvent(Lnode*head){Lnode*p,*q;if(!head->next)returnERROR;p=head->next;q=p->next;p->next=NULL;while(q){p=q;q=q->next;p->next=head->next;head->next=p;}}编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。其中，栈类型为SeqStack，可以直接使用InitStack(SeqStack**)、Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函数。参考答案：voidInverse(ElemTypearr[],intn){SeqStack*s;inti;InitStack(&s);for(i=0;ileft);num2=twochild1(b->right);if(b->left!=NULL&&b->right!=NULL)return(num1+num2+1);elsereturn(num1+num2);}}假设以带双亲指针的二叉链表作为二叉树的存储构造，其结点构造的类型说明如下所示：typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;//左右孩子指针structnode*parent;//指向双亲的指针}BinTNode;typedefBinTNode*BinTree;假设px为指向非空二叉树中某个结点的指针，可借助该构造求得px所指结点在二叉树的中序序列中的后继。(1)就后继的不同情况，简要表达实现求后继操作的方法；参考答案：〔1〕分两种情况讨论=1\*GB3①当*px的右子树不为空时，那么从*px的右孩子开场，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，那么该结点为*px在中序序列中的后继；=2\*GB3②当*px的右孩子为空时，那么沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，那么该祖先结点为*px在中序序列中的后继。(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。〔2〕BinTreef34(BinTreepx){BinTreeq=px->rchild;if(q!=NULL){//沿左孩子往下查找px=q;while(px->lchild!=NULL)px=px->lchild;}else{//沿双亲指针链向上查找while(px!=NULL&&px->rchild==q){q=px;px=px->parent;}}returnpx;//返回所找到的中序序列后继结点的指针//或者无后继结点时返回空指针}已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，假设有那么印出该路径上的顶点。参考答案：voidAllSPdfs(AdjListg,vertypeu,vertypev){//求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v)inttop=0,s[];s[++top]=u;visited[u]=1;while(top>0||p){p=g[s[top]].firstarc;//第一个邻接点。while(p!=null&&visited[p->adjvex]==1)p=p->next;//下一个访问邻接点表。if(p==null)top--;//退栈。else{i=p->adjvex;//取邻接点〔编号〕。if(i==v)//找到从u到v的一条简单路径，输出。{for(k=1;k<=top;k++)printf("%3d",s[k]);printf("%3d\n",v);}//ifelse{visited[i]=1;s[++top]=i;}//else深度优先遍历。}//else}//while}//AllSPdfs有n个顶点的有向图邻接表，编写一个函数求出该图中指定顶点的出度。边类型edgenode，包含next和adjvex〔序号〕成员。类型adjlist表示顶点数组类型，每个数组元素包含link和vex成员。参考答案：intoutdegree(adjlistadj,intv){intdegree=0;edgenode*p;p=adj[v].link;while(p!=NULL){degree++;p=p->next;}returndegree;}编写算法实现对给定的二叉树是否为二叉排序树的判别。设二叉树以二叉链表存储表示。〔要求写出二叉链表的类型定义〕参考答案：//二叉树的二叉链表表示typedefstructBINTREENODE{ElemTypedata;structBINTREENODE*lchild,rchild;}BinNode,*BinTree//答对给2分intBsBtr(BinTreet,BinTreepre,intflag){//判别给定的二叉树是否为二叉排序树pre=NULL;flag=TRUE;if(t&&flag){BSBtr(t->lchild,pre,flag);if(pre==NULL){flag=TRUE；pre=t;}elseif(pre->keykey)//比拟t与中序直接前驱pre的大小{flag=TRUE;pre=t;}//pre与t有序elseflag=FALSE;//pre与t无序}//ifBSBtr(t->rchild,pre,flag);}//BSBtr
浙公网安备 33021202002483