数据结构模拟试题二

数据结构模拟试题二判断题（每小题1分，共15分）构成数据的最小单位是数据项。空线性表的一个特性是线性表中各结点尚未赋值。非循坏单向链表一定要有表头指针。顺序栈的栈顶指针是一个指针类型的变量。在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。哈夫曼树中不存在度为1的结点。在图中，与W相邻的顶点其序号一定是1+1或1-1。如果是不连通的无向图，则在相应的邻接表中一定有空链表。矩阵的行数和列数可以不相等。广义表的深度与广义表中含有多少个子表元素有关。折半查找可以在有序的双向链表上进行。散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。对n个元素执行简单选择排序，排序码的比较次数总是n（ml）/2次。物理记录的大小与逻辑记录的大小成正比。对索引文件，索引表是建立在内存的，数据区是建立在外存的。填空题（每空1分，共15分）在程序中，描述顺序表的存储空间一般用 变量。若用Q[0]-Q[100]作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r的值”作为队空的标志，则创建一个空队列所要执行的操作是 。栈和顺序栈的区别仅在于 。11个结点的二叉树最大高度是—，最小高度是—。树的存储方法主要有 、 和 三种。11个顶点的强连通图中至少有—条边。10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第—个元素。在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个元素，元素间的平均比较次数至少是TOC\o"1-5"\h\z 次，至多是 次。对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是—次，至少是—次。在B-树中，若某结点有1个孩子，则该结点中一定有—个关键字。选择题（每题2分，共30分）1•数据结构的研究内容不涉及 o算法用什么语言来描述B.数据如何存储C.数据的运算如何实现D.数据如何组织若H1是动态单向链表的表头指针，H2是动态双向链表的表头指针，则 。A.H1和H2占用同样多的内存空间B.H1和H2是同类型的变量H2要比H1占用更多的内存空间双向链表要比单向链表占用更多的内存空间对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用 。A.同一个数组B.某些数组元素C.同一个表头结点D同一个表头指针最不适合用作链接栈的链表是 。只有表头指针没有表尾指针的循坏双向链表只有表尾指针没有表头指针的循坏双向链表

只有表尾指针没有表头指针的循坏单向链表只有表头指针没有表尾指针的循坏单向链表TOC\o"1-5"\h\z栈和队列的共同点在于 。A.都对存储方法作了限制B.都是只能进行插入、删除运算C.都对插入、删除的位置作了限制D.都对插入、删除两种操作的先后顺序作了限制如果5个元素的出栈的顺序是1,2,3,4,5,则进栈的顺序可能是 。A.3,5,4,1,2 B.1,4,5,3,2 C.2,4,3,1,5 D.5,1,3,2,4若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树 oA.每个结点都没有右孩子B.不存在度为2的结点C.每个结点都没有左孩子D.不存在对于一棵具有n个结点，度为3的树来说，树的高度至少是 oA.厂log32niB.厂log3（3n一1）-|C.厂log3（3n+l）-|D.|-log3（2n+l）-|对n个顶点的带权连通图来说，它的最小生成树是指图中任意一个由n-1条 oA.权值最小的边构成的子图B.权值之和最小的边构成的子图C.权值之和最小的边构成的连通子图D.权值之和最小的边构成的无环子图所谓特殊矩阵是指 比较特殊。A.矩阵元素之间的关系B.矩阵的处理方法C.矩阵元素的取值 D.矩阵的存储方法11•若长度为n且有n种不同原子的广义表用链接方法存储，则时间复杂度为O（11）的运算是 。A.复制一个广义表B.求广义表的长度C.查找某个子表D.查找某个原子待查找元素关键字的值依次是47,且已存入变量k中，如果在查找过程中，和K进行比较的关键字值依次是47,32,46,25,47,则采用的查找方法—oA.是一种错误的查找方法B.可能是分块查找C.可能是顺序查找D.可能是折半查找如果元素R】和&有相同的排序码，并且进行堆排序前，R】在R：的前面，则当排序结束后， 。A.Ri—定在R）的前面B.Ri—定在R：的后面C.Ri有可能在Rz的后面D.选择Ri或Rz中的一个留在线性表中下面4种排序方法中，属于稳定的排序方法是 排序和 排序。A.堆B.基数C.快速D.起泡在线性表中元素很多，且各元素已有序排列的情况下，执行 排序 排序，排序码比较次数最多。A.简单选择B.堆C.归并D.堆图表题（每小题4分，共8分）已知5个叶子结点的权值分别为2,5,5,6,9,13请画出相应的哈夫曼树。对图1所示无向网络，画出从顶点V6开始用普里姆方法构造的最小生成树。算法填空题（每空2分，共8分）假设待排序的n个元素已存放在顺序表R[1卜R[n]中，排序码字段名是key。下面的算法用于对顺序表进行归并排序，请在空内填入适当内容，将算法补充完整。图1Voidmergesort(listR,listS.inti,intj){lilta,b,c,k;图1If(Kj){K=(i+j)/2;meigesoit(R,S丄k);meigesoit(R,S.k+1J);(1)While((a<=k)&&(b<=j))If(R[a].key<=R[b].key){S[c]=R[a];a++；}Else{⑵—}C++；}(3)Wlule(b<^j){S[c]=R[b];b++;C++；}(4)}}算法设计题(每小题12分，共24分)1•假设head是某个带头结点单链表的表头指针，每个结点数值字段的类型为整型。写一个算法，从该链表中删除一个值最人的结点，并将该结点的值存入表头结点的数值字段。2.如果一个十进制正整数首位数字不为零，而且从左往右读和从右往读都一样，则称其为回文数。对一个n位的正整数x,反复执行下列操作，有可能得到一个回文数：生成一个位数和x相同的正整数y,其中yi=XnM,i=l,2,3…;将y累加到x中。如对于正整数87,按上述方法重复4次后，将得到回文数4884：87+78=165 165+561=726726+627=1353 1353+3531=4884写一个按上述方法求回文数的算法。要求：x的初始值从键盘输入，其位数最多允许10位。如呆得到回文数，就输出这个数,并输出上述步骤重复执行的次数，如果上述步骤重复了30次还得不到回文数，则放弃。数据结构模拟题二参考答案判断题1、X2、X3、J4、X5、J6、J7、X.8、X9、J10、X11、X12、X13、J14、X.15、X填空题1•数组2.给f和r赋同一个值x,0WxW1003.前者没有指定存储方法，后者指定存储方法4.n厂1。引(n+l)i5.双亲数组孩子链表左孩子和右兄弟链表6,n7.5745 478.—— ——9.n+1 2 10.i-114 14选择题1.A2.A3.A4.D5.C6.D7.B8.D9.D10.C11.B12.B13.C14.BD15.AB图表题4016 U42•有两种町能，如下图所示{S[c]=R[a];a++;c++;}五•⑴a=i;b=k+l;c=i; (2)S[c]二R[b];b++;(3)while(a<=k){S[c]=R[a];a++;c++;}(4)for(k=i;k<=j;k++)R[k]=S[k];六.算法设计题1・Struetnode{intdata;node*next;}typedefnode*pointer;pointerhead;voiddel(){pointerp,q,r,s;q二head;p=q~>next;s=q;r=p;while(r!=Null){if(r~>dat&>p->data){q=s;p=r;}s=r;r=r~>next;}q->next二p~>next;p->next二head;head二p;2・constmaxiength=4O,maxtimes=30;struetlist{intv[maxlength+1];ints;}intcount,resuIt;voidtest(list&A){inti,j;i=A・s;j=maxlength;while((i<j)&&(A.v[i]=A.v[j])){i++；j—；}if(i<j)resuIt二0;elseresuIt二1;if(result==l)for(i=A・s;i<=maxlength;i++)cout<<A.v[i];}voidadd(list&A,list&B){inti,j,x;i=A・s;x=0;for(j=maxlengt