数据结构考试卷

1．组成数据的基本单位是（C）。A.数据项B.数据类型C.数据元素D.数据变量y2．在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的(B)A．直接前趋B．直接后继C．开始结点D．终端结点3．一棵深度为８（根的层次号为１）的满二叉树有（B）个结点。Ａ.256Ｂ.255Ｃ.128Ｄ.124．对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为（C）A.O（n）B.O（1）C.O（n2）D.O（log2n）5．顺序栈的上溢是指（C）A.栈满时作退栈运算B.栈空时作退栈运算C.栈满时作进栈运算C.栈空时作进栈运算6．若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（C）A.n-iB.n-i-1C.n-i+1D.不确定7．已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，需（B）次比较可检索成功。A.1B.2C.3D.48．在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法的时间的复杂度是（D）。A.O(1)B.O(n)C.O(n)D.O(log2n)9．已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，那么该树中共有（B）个叶子结点。A.miin1B.miini1)1(1C.miin2D.miini2)1(110．已知数据表A中每个元素距其最终位置不远，则采用（B）排序算法最省时间。A.堆排序B.插入排序C.直接选择排序D.快速排序11．下面算法的时间复杂度为(B)intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1)}A.O(1)B.O(n)C.O(n2)D.O(n!)12．若让元素1，2，3依次进栈，则出栈次序不可能出现（C）种情况。A.3，2，1B.2，1，3C.3，1，2D.1，3，213．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（B）型调整以使其平衡。A.LLB.LRC.RLD.RR14．已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（B）A.4B.5C.6D.715．一个算法只能有（C）A．零个或多个输入，零个或多个输出B．一个或多个输入，零个或多个输出C．零个或多个输入，一个或多个输出D．一个或多个输入，一个或多个输出16.线性表的链表存储结构与顺序结构相比优点是（C）A.所有的操作算法实现简单B.便于随机存取C.便于插入和删除D.便于利用零散的存储器空间17.在带有头结点的单链中插入一个新结点时不可能修改（A）A.头指针B.头结点指针域C.开始结点指针域D.其它结点指18.图的广度优先搜索使用的数据结构是（）A.队列B.树C.栈D.集19.一个有向图中所有顶点的度之和等于所有弧的(C)A．4倍Ｂ．2倍Ｃ．1倍Ｄ．0.5倍20.快速排序算法在最好情况下的时间复杂度为(C)A.O（n）B.O（n2）C.O（nlog2n）D.O（log2n）21．在双向链表中，前趋指针和后继指针分别为prior和next。若要指针p往后移动两个结点，即指向当前结点后继的后继，则需执行语句。若要指针p向前移动一个结点，即指向当前结点的前趋，则需执行语句。p=p-next-next；p=p-prior22．队列的插入操作在进行，删除操作在进行。队尾;队头23．数据的逻辑结构被分为集合结构、线性结构、和。树状结构；图状结构24．下列语句组所代表的算法的时间复杂度为。{for(i=1；i=n；i++)for(j=1；j=n；j++)for(k=1；k=n；k++){s=i+j+k；printf(“%d”，s)；}25.线性表中所含结点的个数称为。表长为0的线性表称为。线性表的长度(表长),空表26.在一棵树中，（)节点没有前驱节点，()没有后继节点。27．在单链表中，若要插入一个新结点需修改个指针。228．如果要将序列{50，16，23，68，94，70，73}建成堆，则只需把16与相互交换。5029.冒泡排序属于排序方法；堆排序属于排序方法。交换、选择30．在一个具有n个顶点的无向完全图中，包含条边；在一个具有n个顶点的有向完全图中，包含条边。n(n-1)/2、n(n-1)31．已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。32．给定如下所示无向图，（1）写出其邻接矩阵；（2）写出一种以顶点A为起点的深度优先搜索顶点序列。ABEDGCFH0000000100011000000001000100001001000010001000010001100110000110AHBDGECF;ABEGDCF;ABDGEHCF等等(只写其中一个)33．以数据集｛2，5，7，9，13｝为权值构造一棵哈夫曼（Huffman）树，并计算其带权路径长度。构造的哈夫曼树如图所示，其带权路径长度WPL=（2+5）×3+（7+9+13）×2=7934.给定表{15,11,8,20,14,13}试按元素在表中的顺序将他们依次插入一个初始时为空的二叉排序树，画出插入完成后的二叉排序树.并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。35．写出下图所示的AOV网的所有拓扑有序序列。共有8种：ADBECFADBEFCADEBCFADEBFCDABECFDABEFCDAEBCFDAEBFC#includestring.h#includestdio.h#includestdlib.h#includemath.hcharw[200];inti;charsign[8]=+-*/()#;charprec[8][8]={,,,,=@,@,@=,};typedefstructnode1{chardata;structnode1*link;}czuofu;czuofu*top1;typedefstructnode2{intdata;structnode2*link;}czuoshu;czuoshu*top2;voidpushf(charc){czuofu*p;p=(czuofu*)malloc(sizeof(czuofu));p-data=c;p-link=top1-link;top1-link=p;}voidpushn(intnum){czuoshu*p;p=(czuoshu*)malloc(sizeof(czuoshu));p-data=num;p-link=top2-link;top2-link=p;}charpopf(czuofu*top1){czuofu*q;charc;if(top1-link!=NULL){q=top1-link;c=q-data;top1-link=q-link;free(q);}return(c);}intpopn(czuoshu*top2){czuoshu*q;intnum;if(top2-link!=NULL){q=top2-link;num=q-data;top2-link=q-link;free(q);}return(num);}chargettopf(czuofu*top1){czuofu*p;charc;if(top1-link!=NULL){p=top1-link;c=p-data;}return(c);}intgettopn(czuoshu*top2){czuoshu*p;intnum;if(top2-link!=NULL){p=top2-link;num=p-data;}return(num);}intnumb(){intnum;inttemp;temp=10.0;if(w[i]='0'&&w[i]='9'){num=w[i]-'0';i++;while(w[i]='0'&&w[i]='9'){num=num*10+w[i]-'0';i++;}if(w[i]=='.'){i++;while(w[i]='0'&&w[i]='9'){num=num+(w[i]-'0')/temp;temp=temp*10;i++;}}return(num);}elsereturn(0);}charcompare(chara,charb){inti,j;i=j=0;while(sign[i]!=a)i++;while(sign[j]!=b)j++;return(prec[i][j]);}intoperate(inta,charx,intb){intnum;switch(x){case'+':num=b+a;break;case'-':num=b-a;break;case'*':num=b*a;break;case'/':num=b/a;break;}return(num);}intgoal(){intnum,a,b;charx;top1=(czuofu*)malloc(sizeof(czuofu));top1-data='0';top1-link=NULL;top2=(czuoshu*)malloc(sizeof(czuoshu));top2-data=0;top2-link=NULL;pushf('#');i=0;while(w[i]!='#'||gettopf(top1)!='#'){num=numb();if(num){pushn(num);}elseswitch(compare(gettopf(top1),w[i])){case'':pushf(w[i++]);break;case'=':popf(top1),i++;break;case'':{x=popf(top1);a=popn(top2);b=popn(top2);pushn(operate(a,x,b));break;}}}return(gettopn(top2))}intmain(){printf(输入要计算的数据，并以“#”结束：\n);scanf(%s,w);printf(=%d\n,goal());return0;}