2020智慧树知道网课《数据结构》课后章节测试满分答案

1、第一章测试1【单选题】（2分）图书馆的数目检索系统采用关系的数据结构。A.树形B.图状C.集合D.线性参考答案【单选题】（2分）是相互之间存在一种或多种特定关系的数据元素的集合。A.数据项B.数据结构C.数据元素D.数据参考答案3【单选题】（2分）（）是一个值的集合和定义在这个值集上的一组操作的总称。A.数据项B.数据类型C.数据元素D.数据结构参考答案4【单选题】（2分）算法的确定性是指（）A.算法中没有逻辑B.在任何情况下，算法不会出现死循环C.算法中的每一条指令必须有确切的含义D.当输入数据非法时，算法也能作出反应或进行处理第二章测试1【单选题】（2分）线性表中的数据元素有一个前驱多个后

2、继A.错B.对参考答案【单选题】（2分）用顺序结构存储，删除最后一个结点时，（）A.其它B.会移动其它结点位置C.可能会移动其它结点位置D.一定不会移动其它结点位置参考答案3【单选题】（2分）链表中逻辑上相邻的元素的物理地址相邻。A.一定不B.必定C.其它D.不一定参考答案4【单选题】（2分）1假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算 法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元 素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。/将合并逆置后的结果放在C表中，并删除B表StatusListMergeOp

3、pose_L（LinkList&A,LinkList&B,LinkList&C）LinkLis tpa,pb,qa,qb;pa=A;pb=B;qa=pa;/呆存pa的前驱指针qb=pb;/保存pb的前驱指针pa=pa-next;pb=pb-next;A-next=NULL;C=A;while(pa&pb)if(pa-datapb-data)qa=pa;pa=pa-next;qa-next=A-next;/将当前最小结点插入A表表头 Anext二qa;elseqb=pb;pb二pb-next;()/将当前最小结点插入B表表头Anext=qb;while(pa)qa=pa;pa二panext;qa

4、next二Anext; Anext二qa;while(pb)qb=pb;pb二pb-next;qbnext二Anext; Anext=qb;pb=B;free(pb);returnOK;A.qanext二AnextB.qanext二A;C.qb-next二A-nextD.qb-next=A;5【单选题】(2分)假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表 中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。StatusListDelete_CL(LinkList&S)LinkLis tp,q;f(S=S-next)returnERROR;q=S;

5、p=S-next;while()q=p；p=p-next;q-next=p-next;free(p);returnOK;A.p=SB.p-next=SC.p!=SD.p-next!=S参考答案第三章测试1【单选题】（2分）若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合 法的是（）；A.SXSXXSSXB.SSSXXSXXC.SXSSXXXXD.SXXSXSSX参考答案2【单选题】（2分）设计一个迷宫求解的算法，采用数据结构最佳。A.栈B.队列C.线性表的链式存储结构D.线性表的顺序存储结构参考答案3【单选题】(2分)循环队列存储在数组AO.m-l则出队时的操作为(

6、)A.front=(front+l)mod(m-l)B.front=(front+1)modmC.front=(frontmodm)+1D.front=front+1参考答案4【单选题】(2分)1.试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列 2模式的字符序列。其中序列和序列2中都不含字符&，且序列2是序列的逆序列。例 如，a+b&b+a是属该模式的字符序列，而1+3&3-1则不是。BOOLSymmetry(chara)inti=0;Stacks;InitStack(s);ElemTypex;while(ai!= &ai)i+；if(!ai)returnFALSE

7、;i+；while(ai)Pop(s,x);if(x!=ai)DestroyStack(s);returnFALSE;i+;returnTRUE;A.Pop(s,ai+)B.Pop(s,ai)C.Push(s,ai+)D.Push(s,ai)参考答案5【单选题】(2分)Stat usSymme tryStri ng(char*p)Queueq;if (!Init Queue(q)re tur nO;S tacks;I nitSt ack(s);Ele mTypeel,e2;while(*p)Push(s,*p);EnQueue(q,*p);p+;while(!S tackEmp ty (s)(

8、)DeQue ue(q,e2);if(el!=e2)returnFALSE;returnOK;A.Push(s,*p);ppppppppC.Pop(s,el);D.EnQueue(q,*p)参考答案第四章测试【单选题】(2分)设 s=IAMASTUDENT, t=GOOD J则 Concat(Substring(s,6,2),Concat(t,SubString(s,7, 8) = ()A.AGOODSTUDENTB.AGOODWORKERC.STGOODSTUDENTD.AGOODWORKER参考答案【单选题】（2分）空串与空格串是相同的，这种说法A.不正确B.正确参考答案【单选题】（2分）

9、设串 sl二DataStructureswithjava,s2= “则子串定位函数 index（sl,s2的值为（A.15B.16C.18D.17参考答案4【单选题】（2分）串的长度是指（）A.串中所含字符的个数B.串中所含不同字母的个数C.串中所含非空格字符的个数D.串中所含不同字符的个数参考答案5【判断题】（2分）串是一种数据对象和操作都特殊的线性表。A.错B.对参考答案第五章测试1【单选题】（2分）数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10,从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是。A.B.80C.240100D.参考答案【单选题】

10、（2分）假设有二维数组A6X8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A14第一个字节的位置（）；A.1072B.1030C.1024D.1018参考答案3【单选题】（2分）若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了 对该矩阵的转置运算，这种观点（）。A.B.正确参考答案【单选题】（2分）广义表（），a,（b,c）,（）,d）,（O（的长度为（）；A.B.5C.D.参考答案5【单选题】（2分）下面说法不正确的是（）。A.广义表的表头总是一个广义表B.广义表可以是一个多层次的结构C.广义表难以用

11、顺序存储结构D.广义表的表尾总是一个广义表参考答案6【单选题】(2分)1试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。 /由广义表L复制广义表TintCopyGList(GList&T,GList&L)f(!L)T=NULL;elseT=newGLNode;if (!T)exit(OVERFLOW);T-tag=L-tag;if(L-tag=AT0M)T-atom=L-atom;elseCopyGLis t(T-t p,L-t p);returnOK;A.CopyGList(L-hp,T-hp)B.CopyGList(T-hp,L-hp);C.CopyGList(L-tp

12、,T-tp);D.CopyGList(T,L)第六章测试【单选题】（2分）已知一棵树边的集合为I,M，I,N，E,I，B,E，B,D，A,B，G,J，G,K，C,G，C,F,H,L,C,H,A,C,问这棵树中结点G的双亲结点为（）【单选题】（2分）参考答案3【单选题】（2分）假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是（）；A.结点A是结点D的左子树上的结点B.结点A是结点D的双亲结点C.结点A是结点D的右子树上的结点D.结点A与结点D具有共同的双亲的右子树上的结点参考答案4【单选题】（2分）已知一棵树边的集合为I,M,I,N,E,I,B,E,B,D,A,B,G,J,

13、G,K,C,G,F,H,L,C,H,A,C,将此树转化为二叉树后，E的左孩子为（）；BD.参考答案5【单选题】（2分）一棵哈夫曼树有17个结点，则其叶子结点的个数是A.9B.8C.7D.10参考答案6【单选题】(2分)写递归算法，将二叉树中所有结点的左、右子树相互交换StatusExchangeBiTree(BiTree&T)BiTreep;if(T)p=T-lchild;T-lchild二T-rchild;T-rchild=p;ExchangeBiTree(T-lchild);returnOK;A.A.ExchangeBiTree(p);B.ExchangeBiTree(T-rchild);

14、C.ExchangeBiTree(T-lchild-rchild)D.ExchangeBiTree(T);参考答案7【单选题】(2分)试写一个算法，为一棵二叉树建立后序线索二叉树。Stat usPos tOrderThreading(BiThrTree&T,BiThrTree&pre);/首先建立后序线索树Stat usFindNex tl nBiThrTree(BiThrTree&q,TElemType*p);/再进行查找/后序线索二叉树的算法StatusPostOrderThreading(BiThrTree&Thrt ,BiThrTree&T)BiThrTreepre;Thrt二newB

15、iThrNode;/为线索二叉树建立头结点if(!Thrt)exit(OVERFLOW);Thrt-LTag二Link;Thrt-RTag二Thread;Thr t-rchild二Thr t右子树回指if(!T)Thr t-lchild二Th若二叉树空，左子树回指elseThrt-lchild二T;pre=Thrt;Pos tThreading(T,pre);后序遍历进行后序线索化pre-rchild二Thrt最后一个结点线索化preRTag二Thread;Thrt-rchild二pre;returnOK;StatusPostThreading(BiThrTree&T,BiThrTree&pr

16、e)if(T)if(T-LTag=Link)PostThreading(T-lchild,pre); if(T-RTag=Link)PostThreading(T-rchild,pre); 辻(！T-lchild)TLTag二Thread;if(pre&!pre-rchild) preRTag二Thread; prerchild二T;pre二T;returnOK;A.T-lcHld=pre;B.T-rchild=preC.pre-rchild=TD.pre-lch订d=T参考答案【单选题】(2分)1编写递归算法，将二叉树中所有结点的左、右子树相互交换StatusExchangeBiTree(B

17、iTree&T)BiTreep;if(T)p=T-lchild;T-lchild=T-rchild;T-rchild=p;ExchangeBiTree(T-lchild);returnOK;A.ExchangeBiTree(T-lchild-rchild);B.ExchangeBiTree(T);C.ExchangeBiTree(p);D.ExchangeBiTree(T-rchild);参考答案第七章测试【单选题】（2分）下图中结点B的出度为（）BA.0B.1C2D.3B2A.B.(n-l) (n-1)nx(n+l)参君答案【单选题】（2分）对于一个具有n个顶点的无向图,若采用邻接矩阵表示，

18、则该矩阵的大小为（）；nxnD.(n-l) n参考答案【单选题】（2分）采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。A.中序遍历B.先序遍历C.层次遍历D.后序遍历参考答案【单选题】（2分）b屮A.B.CD.B5A.B.C下面的无向带权图的最小生成树包含的边有（）aegegfebbccdaeeddccbegdfaggffddccbbeaeebbccddfeg宽度优先遍历算法深度优先遍历算法参君答寮【单选题】（2分）判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）；求关键路径的方法D.求最短路径的Dijkstm方法参考答案6【单选题】(2分)编写算法实现建立图的邻

19、接表StatusCreateAG(ALGraph&G)int n,e,k,i,j;cou t请输入顶点数：;cinn;cou t请输入边数：；cine;G.vernum二n;G.arcnum=e;/建立顶点数组 for(k=0;kG.vernum;k+) cou t请输入顶点信息：;cinG.ver ti cesk.da ta;G.ver ti cesk.firs tare二NULL;/建立邻接表VertexTypevl,v2;ArcNode*p,*q;for(k=0;kG.arcnum;k+)cout请输入弧的始点和终点信息，中间用空格分开:; cinvlv2;i=Loca teVex(G,

20、vl);if(iO|iG.vernum-l)returnERROR;j=Loca teVex(G,v2);if(jO|jG.vernum-l)returnERROR; if(i=j)returnERROR;p二newArcNode;f (!p)returnERROR;p-adjvex二j;pnextare二NULL;q=G.ver ti cesi.firs tare;if(!q)G.ver ti cesi.firs tare二p;elsewhile(q-nextare)/指针定位于邻接表的尾结点qnextare二p;returnOK;A.q=qnextareB.qnextare=pnextar

21、eC.qnextare=NULL;D.p=pnextare;参考答案7【单选题】(2分)编写算法实现从邻接表中取出某个顶点V的存储位置。intLoeateVex(ALGraph&G,VertexTypev)inti=0;while(&iG.vernum)i+;if(G.ver ti eesi.da ta=v)re turni;elsereturn1;A.G.verticesi+.data!=vB.G.vertices+i data!=vC.G.v ertices i. data!=vD.G.v ertices i. data=v参考答案第八章测试【单选题】（2分）1.对线性表进行二分查找时，要

22、求线性表必须（）。A.以链接方式存储，且结点按关键字有序排序B.以链接方式存储C.以顺序方式存储D.以顺序方式存储，且结点按关键字有序排序参考答案【单选题】（2分）2下列描述中不符合二叉排序树特点的是()A.左子树中所有结点的关键字小于根结点的关键字B.根结点的关键字大于左、右子树中所有结点的关键字C.关键字插入的顺序影响二叉排序树的形态D.右字树中所有结点的关键字大于根节点的关键字C 参考答案【单选题】(2分)3设哈希表长m=14,哈希函数H(key)二key%ll。表中已有4个结点:addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列处理

23、冲突，关键字为49的结点的地址是()A.B.C.9D.5参考答案【单选题】(2分)试将折半查找的算法改写成递归算法。lntbisearch(sqlistL,intlow,inthigh,elemtypex)lf(lowhigh)return(0);elseif(L.datamid=x)return(mid);elseif(L.datamidx)bisearch(L,low,mid1,x);elsebisearch(L,mid+1,high,x);/bisearchA.mid=(low+high)/2B.mid(low+high)/2C.mid!=(low+high);D.mid(low+hig

24、h)/2;参考答案5【单选题】(2分)设计算法判定给定二叉树是否为二叉排序树。 voidBSTree(BiTree t,int&f lag,i nt&las 声明/StatusIsBSTree(BiTreet)intflag=1;intlast=0;BSTree(t,flag,last);returnflag;voidBSTree(BiTreet,int&flag,int&last) 取地址不需要返回值if(tlchild&flag)BSTree(tlchild,flag,last);遍历左子树if(t-da ta.keylas t&fl lag)=tdata.key;elseflag=O;/

25、last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈keyif(t-rchild&flag)A.BSTree(t-rchild,last,flag);B.BSTree(t-rchild,flag,last);C.BSTree(t-lchild,flag,last);D.BSTree(t-lchild,last,flag);参考答案6【单选题】(2分)m阶B_树中的m是指？A.非终端结点中关键字的个数B.m阶B_树的深度(或高度)C.每个结点至少有m棵子树D.每个结点至多有m棵子树参考答案第九章测试1【单选题】（2分）1.设一组初始记录关键字序列为（50, 40, 95, 20,15, 70, 60, 45），则以增量d=4的一 趟希尔排序结束后前4条记录关键字为（）。45, 40, 15 , 2015, 40, 60, 2015, 20, 40, 4540, 50, 20, 95参考答案2【单选题】（2分）2 .快速排序方法在情况下最不利于发挥其长处。（）A.要排序的数据量太大。B.要排序的数据个数为奇数C.要排序的数据中含有多个相同值D.要排序的数据已基本有序参考答案3【单选题】（2分）一组记录的排序码为（46,79,56,38,40,84）,则利用堆排序的方法建