数据结构（中国海洋大学版） 知到智慧树网课答案

数据结构（中国海洋大学版）-知到答案、智慧树答案第一章单元测试1、问题：图书馆的数目检索系统采用关系的数据结构。选项：A:集合B:线性C:树形D:图状答案:【线性】2、问题：是相互之间存在一种或多种特定关系的数据元素的集合。选项：A:数据B:数据元素C:数据项D:数据结构答案:【数据结构】3、问题：（）是一个值的集合和定义在这个值集上的一组操作的总称。选项：A:数据类型B:数据元素C:数据项D:数据结构答案:【数据类型】4、问题：算法的确定性是指（）选项：A:当输入数据非法时，算法也能作出反应或进行处理B:在任何情况下，算法不会出现死循环C:算法中的每一条指令必须有确切的含义D:算法中没有逻辑错误答案:【算法中的每一条指令必须有确切的含义】第二章单元测试1、问题：线性表中的数据元素有一个前驱多个后继。选项：A:对B:错答案:【错】2、问题：用顺序结构存储，删除最后一个结点时，（）选项：A:会移动其它结点位置B:一定不会移动其它结点位置C:可能会移动其它结点位置D:其它答案:【一定不会移动其它结点位置】3、问题：链表中逻辑上相邻的元素的物理地址__________相邻。选项：A:必定B:不一定C:一定不D:其它答案:【不一定】4、问题：1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,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->datadata){qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头A->next=qa;}else{qb=pb;pb=pb->next;()//将当前最小结点插入B表表头A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb)qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}{选项：A:qa->next=A->nextB:qb->next=A->nextC:qa->next=A;D:qb->next=A;答案:【qb->next=A->next】5、问题：假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。StatusListDelete_CL(LinkList&S)LinkListp,q;if(S==S->next)returnERROR;q=S;p=S->next;while(){q=p;p=p->next;}q->next=p-next;free(p);returnOK;}{>选项：A:p->next!=SB:p->next==SC:p!=SD:p==S答案:【p->next!=S】第三章单元测试1、问题：若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（）；选项：A:SXSSXXXXB:SXXSXSSXC:SXSXXSSXD:SSSXXSXX答案:【SSSXXSXX】2、问题：设计一个迷宫求解的算法，采用___________数据结构最佳。选项：A:线性表的顺序存储结构B:栈C:队列D:线性表的链式存储结构答案:【栈】3、问题：循环队列存储在数组A[0..m-1],则出队时的操作为（）选项：A:front=front+1B:front=(front+1)mod(m-1)C:front=(front+1)modmD:front=(frontmodm)+1答案:【front=(front+1)modm】4、问题：1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。BOOLSymmetry(chara[]){inti=0;Stacks;InitStack(s);ElemTypex;while(a[i]!='&'&&a[i]){{_________i++;}if(!a[i])returnFALSE;i++;while(a[i]){Pop(s,x);if(x!=a[i])DestroyStack(s);returnFALSE;}i++;}returnTRUE;}选项：A:Pop(s,a[i++])B:Push(s,a[i++])C:Push(s,a[i])D:Pop(s,a[i])答案:【Push(s,a[i])】5{{、问题：StatusSymmetryString(char*p)Queueq;if(!InitQueue(q))return0;Stacks;InitStack(s);ElemTypee1,e2;while(*p)Push(s,*p);EnQueue(q,*p);p++;}while(!StackEmpty(s)){()DeQueue(q,e2);if(e1!=e2)returnFALSE;}returnOK;}选项：A:Pop(s,e1);B:Push(s,*p);C:EnQueue(q,*p)D:P--P--P--P--P--P--P--P--答案:【Pop(s,e1);】第四章单元测试1、问题：设s=’IAMASTUDENT’,t=’GOOD’,则Concat(Substring(s,6,2),Concat(t,SubString(s,7,8)))=()选项：A:AGOODWORKERB:STGOODSTUDENTC:AGOODSTUDENTD:AGOODWORKER答案:【AGOODSTUDENT】2、问题：空串与空格串是相同的，这种说法____。选项：A:正确B:不正确答案:【不正确】3、问题：设串sl=″DataStructureswithJava″,s2=“it″，则子串定位函数index(s1,s2)的值为（）；选项：A:15B:16C:17D:18答案:【18】4、问题：串的长度是指（）选项：A:串中所含不同字母的个数B:串中所含字符的个数C:串中所含不同字符的个数D:串中所含非空格字符的个数答案:【串中所含字符的个数】5、问题：串是一种数据对象和操作都特殊的线性表。选项：A:对B:错答案:【对】第五章单元测试1、问题：数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是______。选项：A:80B:100C:240D:270答案:【240】2、问题：假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（）；选项：A:1018B:1024C:1030D:1072答案:【1072】3、问题：若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（）。选项：A:正确B:错误答案:【错误】4、问题：广义表（（（））,a,((b,c),(),d),(((e)))）的长度为（）；选项：A:3B:4C:5D:2答案:【4】5、问题：下面说法不正确的是()。选项：A:广义表的表头总是一个广义表B:广义表的表尾总是一个广义表C:广义表难以用顺序存储结构D:广义表可以是一个多层次的结构答案:【广义表的表头总是一个广义表】6、问题：1.试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。//由广义表L复制广义表TintCopyGList(GList&T,GList&L){if(!L)T=NULL;else{T=newGLNode;if(!T)exit(OVERFLOW);T->tag=L->tag;if(L->选项：答案:【】第六章单元测试1、问题：已知一棵树边的集合为{,,,,,,,,,,,,},问这棵树中结点G的双亲结点为()选项：A:AB:CC:ID:B答案:【C】2、问题：一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为()；选项：A:9B:10D:12答案:【9】3、问题：假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是（）；选项：A:结点A是结点D的双亲结点B:结点A是结点D的右子树上的结点C:结点A是结点D的左子树上的结点D:结点A与结点D具有共同的双亲的右子树上的结点答案:【结点A是结点D的右子树上的结点】4、问题：已知一棵树边的集合为{,,,,,,,,,,,,},将此树转化为二叉树后，E的左孩子为（）；选项：A:AB:CC:ID:B答案:【I】5、问题：一棵哈夫曼树有17个结点，则其叶子结点的个数是_________。选项：A:7B:8C:9D:10答案:【9】6{、问题：写递归算法，将二叉树中所有结点的左、右子树相互交换。选项：A:A.ExchangeBiTree(p);D:ExchangeBiTree(T);答案:【】7、问题：试写一个算法，为一棵二叉树建立后序线索二叉树。首先建立后序线索树再进行查找//后序线索二叉树的算法StatusPostOrderThreading(BiThrTree&Thrt,BiThrTree&T){BiThrTreepre;Thrt=newBiThrNode;//为线索二叉树建立头结点右子树回指if(!T)Thrt->lchild=Thrt;//若二叉树空，左子树回指后序遍历进行后序线索化pre->rchild=Thrt;//最后一个结点线索化>>>选项：B:pre->lchild=TD:pre->rchild=T答案:【】8{、问题：1.编写递归算法，将二叉树中所有结点的左、右子树相互交换。选项：A:ExchangeBiTree(p);D:ExchangeBiTree(T);答案:【】第七章单元测试1、问题：下图中结点B的出度为()选项：A:0B:1C:2D:3答案:【1】2、问题：对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为（）；选项：A:n×nB:(n-1)×(n-1)C:(n-1)×nD:n×(n+1)答案:【n×n】3、问题：采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。选项：A:先序遍历B:中序遍历C:后序遍历D:层次遍历答案:【层次遍历】4、问题：下面的无向带权图的最小生成树包含的边有()选项：A:aegegfebbccdB:aeeddccbegdfC:aggffddccbbeD:aeebbccddfeg答案:【aeeddccbegdf】5、问题：判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）；选项：A:求关键路径的方法B:求最短路径的Dijkstm方法C:宽度优先遍历算法D:深度优先遍历算法答案:【深度优先遍历算法】6、问题：编写算法实现建立图的邻接表StatusCreateAG(ALGraph&G){intn,e,k,i,j;cout<<"请输入顶点数：";cin>>n;cout<<"请输入边数：";cin>>e;G.vernum=n;G.arcnum=e;//建立顶点数组for(k=0;k>G.vertices[k].data;G.vertices[k].firstarc=NULL;}//建立邻接表i>G.vernum-11j>G.vernum-)returnERROR;if(i==j)returnERROR;p=newArcNode;if(!p)returnERROR;p->adjvex=j;p->nextarc=NULL;q=G.vertices[i].firstarc;if(!q)G.vertices[i].firstarc=p;else{while(q->nextarc)__________//指针定位于邻接表的尾结点q->nextarc=p;}}returnOK;}选项：A:p=p->nextarc;B:q->nextarc=NULL;C:q->nextarc=p->nextarcD:q=q->nextarc答案:【q=q->nextarc】7{、问题：编写算法实现从邻接表中取出某个顶点V的存储位置。inti=0;while(______&&i选项：A:A.G.vertices[i++].data!=vB:G.vertices[i].data!=vC:G.vertices[i].data==vD:G.vertices[++i].data!=v答案:【G.vertices[i].data!=v】第八章单元测试1、问题：1.对线性表进行二分查找时,要求线性表必须（）。选项：A:以顺序方式存储B:以链接方式存储C:以顺序方式存储,且结点按关键字有序排序D:以链接方式存储,且结点按关键字有序排序答案:【以顺序方式存储,且结点按关键字有序排序】2、问题：2.下列描述中不符合二叉排序树特点的是()选项：A:左子树中所有结点的关键字小于根结点的关键字B:根结点的关键字大于左、右子树中所有结点的关键字C:右字树中所有结点的关键字大于根节点的关键字C．D:关键字插入的顺序影响二叉排序树的形态答案:【根结点的关键字大于左、右子树中所有结点的关键字】3、问题：3.设哈希表长m=14，哈希函数。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是()选项：A:8B:3C:5D:9答案:【9】4、问题：4.试将折半查找的算法改写成递归算法。Intbisearch(sqlistL,intlow,inthigh,elemtypex){If(low>high)return(0);else{if(L.data[mid]==x)return(mid);elseif(L.data[mid]>x)bisearch(L,low,mid-1,x);elsebisearch(L,mid+1,high,x);}}//bisearch选项：A:A.mid<(low+high)/2B:mid=(low+high)/2C:mid>(low+high)/2;D:mid!=(low+high);答案:【mid=(low+high)/2】5、问题：5.设计算法判定给定二叉树是否为二叉排序树。voidBSTree(BiTreet,int&flag,int&last);//声明{intflag=1;intlast=0;BSTree(t,flag,last);returnflag;}voidBSTree(BiTreet,int&flag,int&last)//取地址不需要返回值{if(t->lchild&&flag)BSTree(t->lchild,flag,last);//遍历左子树if(t->data.key>last&&flag)last=t->data.key;elseflag=0;//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈keyif(t->rchild&&flag)}选项：A:BSTree(t->rchild,flag,last);B:BSTree(t->lchild,flag,last);C:BSTree(t->rchild,last,flag);D:BSTree(t->lchild,last,flag);答案:【BSTree(t->rchild,flag,last);】6、问题：m阶B_树中的m是指？选项：A:每个结点至少有m棵子树B:每个结点至多有m棵子树C:非终端结点中关键字的个数D:m阶B_树的深度（或高度）答案:【每个结点至多有m棵子树】第九章单元测试1、问题：1.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。选项：A:40，50，20，95B:15，40，60，20C:15，20，40，45D:45，40，15，20答案:【15，40，60，20】2、问题：2.快速排序方法在情况下最不利于发挥其长处。()选项：A:要排序的数据量太大。B:要排序的数据中含有多个相同值C:要排序的数据已基本有序D:要排序的数据个数为奇数答案:【要排序的数据已基本有序】3、问题：一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（）。选项：A:79,46,56,38,40,80B:84,79,56,38,40,46C:84,79,56,46,40,38D:84,56,79,40,46,38答案:【84,79,56,38,40,46】4、问题：设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。选项：A:15，2