上海交通大学《数据结构》2020-2021学年期末试卷

课程名称数据结构成绩A.head==nullB.head->next==nullC.head->next==headD.head!=nuA.单链表B.顺序表C.双链表D.单循4.在操作系统内部，函数调用是用下面哪种数据结构来实现的？C7.下面哪种数据结构最适合用于创建一个优先级A.栈B.双向链表C.单向链表8.对于下列关键字序列，不可能构成某二叉排序树中 我承诺，我将严我承诺，我将严A.置换-选择排序是完成将一个磁盘文件排序成有序文件的有效的外B.置换-选择排序生成的初始归并段长度是内存工作区的2倍D.置换-选择排序是对外排序中输入/归并/输出A.根节点一定有2~M个子节点B.一个叶节点和一个非叶节点之C.任意两个叶节点的深度不一定相同D.所有的非叶节点都有⌈M/2⌉~ {if(head->next==NULL)head->next->next=NUL{p->next=head->next;}}2.从空栈开始依次将1,2,3,4,5入栈，判断2,4,5,3,1是否是一个合法的出栈序列？如果是，给出对应的pushpushpoppushpushpoppushpoppoppop字符ABCDEFG权值0.180.150.140.050.120.190.17父结点左孩子右孩子 字符ABCDEFGABCDEFG101122435566342476800000003590000000字符ABCDEFG010011000000010018838637 BCHFJIBCHFJIAAGGDDEE{intadjvex;{chardata;{VNodeadjlist[MAXSIZE];/intvisit[MAXSIZE];//全局{cout<<v<<endl; {if(visit[p->adjvex]=={ }}publicstaticvoidbubblesort(int[]a){booleanis_sorted=true;for(intj=0;j<a.length-i;j++){if(a[j]>a[j+1]){}}}}排序好，故可避免对数组靠近尾部已经排序好的元素做不必要的比较。请填充以下代码完成上面的功能：publicstaticvoidbubblesort(int[]a){booleanis_sorted=true;for(intj=0;j<;j++){if(a[j]>a[j+1]){ ;_____________}}if(is_sorted)return;;_______________}}currentSwap=j;Node*left;Node*right;Node*find(intvalue,Node*root){if(root==NULL||value==rif(value<root->value)}returnfind(value,root->lreturnfind(value,root->rig {private:public:intDelRepeat();//删除所有重复元素status=newbool[cufor(i=0;i<2*currentLefor(i=0;i<currentLen{pos=data[i]%(2*currentLength);while(tmp[pos]!=noData&&tmp[pos]!=data[i])pif(tmp[pos]==noData){}}j=0; for(i=0;i<currentLenif(status[i])tmp[j++]=data[i];currentLength=j;returnoldLen-currentLengt}intoldLen=currentLfor(i=0;i<currentLength;i{for(j=0;j<k;j++)//检查i元素是否与前面k个元素重复if(data[i]==data[j])break;if(j==k)data[k++]=data[i];//将第i}returnoldLen-currentLengt}输入:/\/\/\\ 输出:合并后的树:3/\/\\/\/***Definitionforabinarytreenode.public:可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。（3）如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点}} }（1）如果两个原始二