《首钢工学院数据结构期末考试试题A.doc》由会员分享，可在线阅读，更多相关《首钢工学院数据结构期末考试试题A.doc（7页珍藏版）》请在金锄头文库上搜索。
1、首钢工学院数据结构期末考试试题A卷班级：学号： 姓名： 一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列程序段的时间复杂度为( D ) s=0； for(i=1；in；i+) for(j=1；jnext=NULL；C.head!=NULL；D.head-next=head；3.栈是一种操作受限的线性结构，其操作的主要特征是( B )A.先进先出B.后进先出C.进优于出D.出优于进4.判断两个串大小的基本准则是( A )A.两个串长度的大小B.两个串中首字符的大小C.两个串中
2、大写字母的多少D.对应的第一个不等字符的大小5.二维数组A45按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组元素A32的存储地址为( C )A.1012B.1017C.1034 D.10366.高度为5的完全二叉树中含有的结点数至少为( B )A.16B.17C.31D.327.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ C ）A. 栈B. 队列C. 树D. 图8.有n个结点的无向图的边数最多为（ B ）A.n+1B.C.n（n+1）D.2n（n+1）9.在单链表中，存储每个结点需要有两个域，一个是数据域，另
3、一个是指针域，指针域指向该结点的（B）A.直接前趋B.直接后继C.开始结点D.终端结点10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( B )A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)11.栈和队列共同具有的特点是（B）A.都是先进后出B.都是先进先出C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出12.一个有序表为1，3，9，12，32，41，45，62，75，
4、77，82，95，100，当二分查找值为82的结点时，查找成功时的比较次数为（B）A.1B.2C.4D.813.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( C )A.高度等于其结点数B.任一结点无左孩子 C.任一结点无右孩子D.空或只有一个结点14.在完全二叉树中，若一个结点是叶结点，则它没有( D )A.左孩子结点B.右孩子结点 C.左孩子结点和右孩子结点D.左孩子结点，右孩子结点和兄弟结点15.选择排序法的时间复杂度是（C）A.O(n)B.O(1)C.O(n2)D.O(nlog2n)二、简答题（本大题共6小题，每小题5分，共30分）16：什么是数据结构？什么是数
5、据的逻辑结构？逻辑结构有哪几种？它们分别有什么特点？答：数据结构是指具有某种联系得数据元素以及元素之间所构成的各种关系组成的集合。数据的逻辑结构是指数据元素之间的逻辑关系。逻辑结构有线性结构：该结构的数据元素之间形成一对一的线性关系。层次结构（树形结构）：该结构的数据元素之间存在着一对多的关系。网状结构（图形结构）：该结构的数据元素之间存在着多对多的关系。17: 什么是数据的存储结构，数据的存储结构有哪两种基本形式？这两种基本形式有什么基本特点？答：数据的存储结构是指数据元素及其关系在计算机存储内的表示，称为数据的存储结构。1、 顺序存储：逻辑上相邻的元素，物理存储上也相邻。2、 链式存储：逻
6、辑上相邻的元素，物理存储不一定相邻。18：队列和栈各有什么特点？它们有什么不同之处？答：队列的特点是先进先出。 栈的特点是在线性表的固定端进行操作，将进行操作的一端称为栈顶，另一端称为栈底。先进后出。19：.如图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。 答：能。20：写出下面树的以下遍历顺序：（） 先根遍历 A BCDEFG（） 中根遍历 BDFCEGA（） 后根遍历 FDBGECA21：见下图，试给出：（1）邻接矩阵；（2）邻接表。三、应用编程题（本大题共3小题，共40分）要求
7、：（）：请源程序粘贴到相应题目后的空白处（）：将程序的运行结果截图粘贴到相应的空白处22：用数组实现顺序栈的入栈和出栈操作，并将以下数据入栈，并将入栈结果出栈23: 按以下方法接口，实现对以下两个字符串数数组的合并操作第一个数组：char first= g,o,o,d第二个数组：char second=m,o,r,i,n,g合并后的数组: char merge=g,o,o,d, m,o,r,i,n,gpublic char merge(char first,char second)public class Test1 public charmerge(char first,char secon
8、d)char tmp = new charfirst.length+second.length;char loc;for( loc=0;locfirst.length;loc+)tmploc=firstloc;for(char i=0;isecond.length;i+)boolean flag=false;for(char j=0;jfirst.length;j+)if(secondi=firstj)flag=true;break;if(!flag)tmploc=secondi;loc+;char tmpRet=new charloc;for(char i=0;iloc;i+)tmpReti
9、=tmpi;return tmpRet;public static void main(String args)char first=g,o,o,d;char second=m,o,r,i,n,g;Test1 t=new Test1();char ret=t.merge(first,second);for(char i=0;iret.length;i+)System.out.print(reti+);24:使用冒泡法，实现对以下整数的排序，并输出排序后的结果23,55,10,5,1,99,66,88,25,10public class BubbleSort public void bubblS
10、ort(int srcArr)int tmp=0;for(int i=0;isrcArr.length;i+)for(int j=0;jsrcArrj+1)tmp=srcArrj;srcArrj=srcArrj+1;srcArrj+1=tmp;System.out.print(第+(i+1)+次:t);for(int k=0;ksrcArr.length;k+)System.out.print(srcArrk+t);System.out.print(n);public static void main(String args)BubbleSort ss = new BubbleSort();int srcArr=23,55,10,5,1,99,66,88,25,10;ss.bubblSort(srcArr);for(int i=0;isrcArr.length;i+)System.out.print(srcArri+t);
