数据结构本期末综合练习12月.doc

数据结构期末综合练习2014年12月期末综合练习一一、单项选择题1 .单向链表所具备的特点是( )。A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点 2.头指针为head的带头结点的单向链表为空的判定条件是( )为真。A. head= =NULL B. head-next= =NULLC. head-next=NULL; D. head-next!= NULL 3.设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为（ ）。 A12 B5 C. 13 D6 4设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A9 B8 C25 D24 5栈和队列的共同特点是（ ）。 A都是线性结构 B元素都可以随机进出C都是先进后出 D都是先进先出 6一个栈的进栈序列是2，4，6，8，10，则栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。A2，4，6，8，10 B8，6，10，2，4C8，10，6，4，2 D10，8，6，4，2 7元素1，3，5，7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是（ ）（进栈出栈可以交替进行）。 A7，5，1，3 B7，3，1，5 C5，1，3，7 D7，5，3，1 8一个队列的入队序列是a,b,c,d,按该队列的可能输出序列使各元素依次入栈，该栈的可能输出序列是 （ ）。（进栈出栈可以交替进行）。 Ad,c,b,a Bc,a,b,d Cd,b,a,c Dd,a,b,c 9在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出 队操作中并把结点的值保存在变量e中,其运算为e=fdata；和（ ）。 Ar=rnext; Brnext=r; Cf=fnext; Dfnext=f; 10在一个链队中，假设f和r分别为队头和队尾指针，p指向一个已生成的结点,现要为 该结点的数据域赋值e，并使结点入队的运算为p-data=e; p-next=NULL ; 和（ ）。A . f-next=p; f=p; B r-next=p;r=p; C p-next=r;r=p; D p-next=f;f=p; 11设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素,则该矩阵是（ ）阶的对称矩阵。A15 B11 C10 D9 12设有一个24阶的对称矩阵A，采用压缩存储的方式（矩阵的第一个元素为a1,1），将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第30号元素对应于矩阵中的元素是（ ）。Aa10,8 Ba9,2 C a8,2 Da8 ,5 13. 下列是C语言中abcd321ABCD的子串的选项是（ ）。 A. 21ABC B.abcABCD C. abcD D. 321a 14. 字符串a1=BEIJING, a2 =BEI , a3= BEFANG a4=“BEFI中最大的是（ ）。A. a1 B. a2 C. a3 D. a4 15. 字符串a1=BEIJING, a2 =BEF , a3= BEFANG, a4=“BEFI最小的是（ ）.A. a1 B. a2 C. a3 D. a4 16. 程序段char a =“English”; char *p=a; int n=0; while( *p!=0) n+; p+; 结果中,n的值是（ ）。 A. 6 B.8 C. 5 D.7 17一棵有20个结点采用链式存储的二叉树中，共有（ ）个指针域为空。 A21 B20 C19 D18 18在一棵二叉树中，若编号为5的结点存在左孩子，则左孩子的顺序编号为（ ）。 A9 B10 C11 D12 19设一棵哈夫曼树共有18个叶结点，则该树有（ ）个非叶结点。 A18 B19 C17 D16 20设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空。则该树有（ ）个叶结点。A21 B22 C9 D10 21如图1所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 Agabecdf Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 图122已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 Aabcedfg Babcefdg Caebcfdg Dacfdebg bdfecabdfecag 图223线性表以（ ）方式存储，能进行折半查找。 A关键字有序的 B关键字有序的顺序 C链接 D顺序 24在有序表10,23，32，36，53，66，68，76，87，90,101,120中，用折半查找值53时，经（ ）次比较后查找成功。A6 B3 C8 D4 25有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。A22/8 B20/8 C23/8 D21/8 26有一个长度为11的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。A29/11 B33/11 C26/11 D30/11 27. 排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（ ）。 A折半插入排序 B直接插入排序 C归并排序 D选择排序 28设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（ ）。 A堆排序 B简单选择排序 C快速排序 D归并排序 29排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ ）排序。 A堆 B冒泡 C选择 D快速 30一组记录的关键字序列为（32，65，42，24，26，80），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A26，24，32，42，65，80 B24，26，32，42，65，80 C26，24，32，65，42，80 D26，24，32，80，42，65二、填空题1.广义表( a , (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ 。 2.结构中的数据元素存在一对多的关系称为_结构。3.广义表的( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。 4.栈的操作特点是_。5. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定,可用语句sq-datasq-rear=x;和_ 。 6.广义表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_。 7. 序列4,2,5,3,8,6,采用冒泡排序算法,经一趟冒泡后,序列的结果是_。（按由小到大顺序） 8. 广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ _。9.在对一组记录（50，34，92，19，11，68，56，41，79）进行直接插入排序(由小到大排 序) ，当把第7个记录56插入到有序表时，为寻找插入位置需比较_次。10. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量，要进行元素的出队操作，并把元素赋给边量x, 按教科书约定,可用语句x=sq-datasq-front;和_ 。11.数据结构中, _可以由一个或多个数据项组成。 12. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定,可用语句sq-datasq-rear=x;和_。 13循环队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少用一个元素的模式),判断循环队列为满的条件为_为真 。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,经一趟冒泡后,序列的结果是_。（由小到大排序）15排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素依次进行比较，然后将其放入已排序序列的正确位置的方法是 。16. 数据结构中, _ 之间的抽象关系称为逻辑结构。17对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有34个零元 素，其相应的三元组表共有_个元素。 18. 循环队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,),判断循环队列为空的条件为_为真。19在双向链表中，要删除p所指的结点，可以先用语句（p-prior）-next=p-next；然后再用语句（p-next）-prior= _。 20. 排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是 。21.在双向链表中，每个结点有两个指针域，一个指向结点的直接后继 ，另一个指向_。22. 对稀疏矩阵进行压缩存储,可采用三元组表,矩阵元素a3,4 对应的三元组为_ 。23.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_结构。24在双向链表中，要删除p所指的结点，其中所用的一条语句（p-next）-prior=p-prior; 的功能是：使P所指结点的直接后继的左指针指向_ _。 三、 综合题1.设数据集合a=1,12,5,8,3,10,7,13,9（1）依次取a中各数据，构造一棵二叉排序树。（2）说明如何依据此二叉树得到a的有序序列。（3）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？（4）给出对该二叉树后序遍历的序列。2.设数据集合a=62,74,30,15,56,48（1）依次取a中各数据，构造一棵二叉排序树。（2）为了成功查找到48需要进行多少次元素间的比较?（3）给出对该二叉树后序遍历的序列。3设有序表为(2, 5, 11, 12, 30, 48, 58, 70, 78, 79, 90) ,元素的序号依次为 1,2,3,，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示） （2）说明成功查找到元素2需要经过多少次比较？ (3) 说明不成功查找元素75需要经过多少次比较？ (4) 给出中序遍历该折半查找判定树的序列4设有序表为（3，9，15，26，38，41，53，74，81，96，97，99），元素的 序号依 次为1,2,12。 （1）画出对上述有序表进行折半查找所对应的判定树（树结点用序号表示）。 （2）设查找5号元素(38)，需要进行多少次元素间的比较才能确定不能查到, 依次和 哪些元素进行了比较？（要求写出具体元素）。 （3）给出后序遍历该二叉树的序列。 (4) 给出中序遍历该二叉树的序列。四、程序填空题1. 设有一个不带头结点的单向链表，头指针为head, p 、prep 是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入,以下程序段是在该单向链表中查找这相邻两个结点,，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。 prep=head; p=prep-next; while(p - data!=prep- data) prep=p; _(1)_ printf(“min=%d”, _(2)_); prep-next= _(3)_ 2.学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。数组元素按学号num由小到大有序排列，以下函数在a0到an-1中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标(数组元素的下标)。失败时返回-1，完成程序中的空格。 typedef struct char sex; int num; NODE;int Binary_Search(NODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.num = =k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; return -1 ; 3 . 以下程序是折半插入排序的算法(按记录中关键字key排序) 设待排序的记录序列存放在a1,an中，以a0作为辅助工作单元，以下程序是要把ai 插入到已经有序的序列a1,ai-1中。 void binsort (NODE a ,int n) int x,i,j,s,k,m; for （i=2；i=_(1)_ ; i+） a0=ai; x= ai.key; s=1; j=i-1; while (s=j) m=_(2)_ if( x=j+1;k- -) _(5)_=ak; aj+1=a0; 4以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查找到的树结点，不成功，则p指向为NULL），完成程序中的空格。struct bnode int key; struct bnode *left;struct bnode *right; ; typedef struct bnode Bnode Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序树 的根结点的指针，k用以 接收要查找的关键字*/ Bnode *p; if(bt = = NULL) return (bt); _(1)_ while(p-key !=_(2)_) if(kkey) _(3)_; else _(4)_; if(p=NULL) break; return p ; 期末综合练习一答案一、单项选择题1C 2B 3C 4D 5A 6B 7D 8A 9C 10B 11D 12C 13A 14A 15B 16D 17A 18B 19.C 20D 21D 22B 23B 24D 25D 26B 27A 28B 29C 30A 二、填空题1. 52树形3. 34先进后出5. sq-rear+;63 7.2,4,3,5,6,8849. 310sq-fronf+;11. 数据元素12sq-rear+;13. front= =(rear+1)% MaxSize 1412,14,13,15,16,1815.直接插入排序 16数据元素17.818front= =rear19. p-prior；20折半插入排序21. 结点的直接前驱22(3,4, a3,4)23. 存储24P所指结点的直接前驱三、综合应用题1. (1)图3 (2)中序遍历 1 , 3 , 5 , 7 , 8 , 9 , 10 , 12 , 13 (3) 5次 (4) 3,7,9,10,8,5,13,12,1 图31351213789102 (1)图4 (4)4次 (5)15,48,56,30,74,62 627456481530图43（1）图5 4711852101311396图5 (2) 3次 (3) 4次 (4) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 （序号） 4.(1)图6 (2)4次41,15,26,38 (3) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41) （4）1( 3）,2(9), 3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99) 471285211110639图6四、程序填空题1. (1) p=p-next; (2)p-data或prep-data(3) p-next;2. (1)low=high (2)mid (3)amid.numleft (4)p=p-right期末综合练习二一、单项选择题1.数据的存储结构包括数据元素的表示和（ ）。 A . 数据处理的方法 B. 数据元素间的关系的表示 C . 相关算法 D. 数据元素的类型 2 .下面关于线性表的叙述中,错误的是( )。A . 线性表采用顺序存储,必须占用一片连续的存储空间B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动C. 线性表采用链式存储，不必占用连续的存储空间D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 3设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A15 B22 C14 D23 4 .设有一个长度为28的顺序表，要在第12个元素之前插入一个元素（也就是插入元素作为新表的第12个元素），则移动元素个数为（ ）。 A12 B17 C. 13 D115元素2,6,10,14按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列 的不可能输出序列是是（ ）。（进栈出栈可以交替进行）。 A14,10,6,2 B2,6,10,14 C14,10,2,6 D6,2,14,10 6元素2，4，6,8按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。 A8,6,4,2 B2,4,6,8C4,2,8,6 D8,6,2,4 7对一个栈顶指针为top的链栈进行进栈操作，设P为指向待进栈的结点的指针，把e 的值赋值给该结点的数据域，然后使该结点进栈，则执行（ ）。 Ap-data=e; p=top-next; top=topnext; Bp-data=e;p-next=top;top=p; Cp-data=e;top=p; Dp-data=e;p-next=top-next; top =p; 8对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值 ，则执行 （ ）。 A. e= top-next; top-data=e; Be=top-data; top=top-next; Ctop=top-next; e=top-data; Dtop=top-next; e=data; 9 .对不带头结点的单向链表,判断是否为空的条件是（ ）（设头指针为head）。Ahead=NULL Bhead-next= =NULL Chead-next= =head Dhead =NULL 10在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行（ ）。 Arearnext= s; snext=rearnext Brearnext=snext; Crear=snext Dsnext=rearnext ; rearnext=s;11设有一个25阶的对称矩阵A（矩阵的第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,5在一维数组B中的下标是（ ）。A34 B14 C26 D27 12设有一个28阶的对称矩阵A（矩阵的第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第40号元素对应于矩阵中的元素是（ ）。 Aa10,8 Ba9,4 Ca9,5 Da8,5 13.数组a经初始化 char a =“English”; a7中存放的是（ ）。 A. 字符串的结束符 B. 字符hC. h D. h 14.数组a经初始化 char a =“English”; a1中存放的是（ ）。 A. 字符n B. 字符EC. n D. E 15 .设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。 A. aBc B. BCd C. ABC D .Abc 16. 程序段char a =“English”; char *p=a; int n=0; while( *p!=0) n+; P+;结果中,P指向（ ）。A. 字符h B.aC. 字符串的结束符 D.7 17设一棵哈夫曼树共有11个非叶结点，则该树有（ ）个叶结点。 A22 B。10 C11 D12 18在一棵二叉树中，编号为17的结点的双亲结点的的顺序编号为（ ）。 A34 B7 C9 D8 19一棵具有38个结点的完全二叉树，最后一层有（ ）个结点。 A7 B5 C6 D8 20设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空。则该树共有（ ）个非叶子结点 A21 B22 C 9 D10 21已知如图1所示的一个图，若从顶点V1出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 AV0V1V2V3V6V7V4V5V8 BV0V1V2V3V4V5V8V6V7 CV0V1V2V3V4V5V6V7V8 DV0V1V2V3V4V8V5V6V7 V6V7V1V2V3V8V4V5V0 图122已知如图1所示的一个图，若从顶点V0出发，按深度优先法进行遍历，则可能得到的一种顶点序列为（ ）。 A. V0V1V2V4V8V5V3V6V7 BV0V1V2V4V5V8V3V6V7 CV0V1V2V4V8V3V5V6V7 DV0V1V3V6V7V2V4V5V8 23在有序表10,14，34，43，47，64，75，80，90中，用折半查找法查找值80时，经（ ）次比较后查找成功。A4 B2 C3 D5 24对( )进行中序遍历，可以使遍历所得到的序列是有序序列。 A完全二叉树 B二叉排序树 C满二叉树排 D哈夫曼树25排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，然后将其放入已排序序列的正确位置的方法是（ ）。 A冒泡排序 B直接插入排序 C归并排序 D选择排序