数据结构期末试题(带答案)

模拟试题7一、选择题（每小题1分，共10分）1、如果树的结点A有4个兄弟，而且B为A的双亲，则 B的度为。(A)3 (B)4 (C)5 (D)12、设有一个栈，元素的进栈次序为A，B，C，D，E，则下列是不可能的出栈序列。(A)A,B,C,D,E (B)B,C,D,E,A (C)E,A,B,C,D (D)E,D,C,B,A3、在所有排序方法中，关键字的比较次数与记录的初始排列无关的是。(A)快速排序 (B)冒泡排序 (C)直接插入排序 (D)直接选择排序4、设一棵二叉树共有20个度为2的结点，则叶子结点共有个。(A)4 0 (B)19 (C)20 (D)215、在具有N个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为。(A)front==rear (B)（rear+1）%MAXSIZE==front (C)front-rear==1 (D)rear%MAXSIZE==front6、设有1000个元素，用二分法查找时，最小比较次数为。(A)0 (B)1 (C)10 (D)5007、一个元素进入队列的时间复杂度是。(A)O(1) (B)O(n) (C)O(n2) (D)O(log2n)8、设一颗完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有个结点。(A)24 (B)45 (C)46 (D)47二、判断题（每题1分，共8分，对的打√，错的打×）1、如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继结点，则必为线性表。（）2、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。（）3、若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必须是该子树的先序遍历的最后一个结点。（）4、有向图的邻接矩阵的第i行的所有元素之和等于第i列的所有元素之和。（）5、二叉排序树中，任一结点的值都大于或等于其孩子的值。（）6、图的生成树的边数要小于顶点数。（√）7、进栈操作时，必须判断栈是否已满。（）8、如果某排序算法是稳定的，那么该方法一定具有实际应用价值。（）三、填空题（每题2分，共16分）1、数据结构有线性结构、树结构、、等几种逻辑结构。2、已知某算法的执行时间为（n+n2）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是O(n2)。3、一个无向连通图有6个顶点7条边，则其生成树有条边。4、顺序存储的队列如果不采用循环方式，则会出现问题。5、一个10×10的三角矩阵a采用行优先压缩存储后，如果首元素a[0][0]是第一个元素，那么a[4][2]是第个元素。6、如果一个有向图有5个顶点，则它最多有条弧。7、采用快速排序法进行排序时，如果有序排列时，排序效率会大大降低。8、设无向图G有100条边，则G至少有101个顶点。四、简答题（共38分）1、排序。（1）写出线性表（26，45，12，2.，30，6，15，29，16，2，18）采用快速算法排序后，第一趟结束时的结果。（4分）//答案错，正确如下：//18,2,12,2,16,6,15,26,29,30,45（2）线性表采用插入排序算法排序几趟后，有序部分是（16，20，40），无序部分是（18，25），则下一趟的排序需要移动几个元素？写出下一趟结束时的结果。（4分）//答：采用插入排序算法2趟后，可得到上述结果。下一趟的排序需要移动2个元素，结束时的结果是：有序部分是（16，18，20，40），无序部分是（25）。2、给出如图1所示的二叉树的中序遍历结果。（5分）3、已知5个结点的权值分别是4，6，1，13，7，请画出这结点构成的Huffman树。（5分）4、已知图2是一个无向图：（1）画出该无向图的邻接链表。（5分）（2）基于你给出的邻接链表，求从顶点C出发的广度优先遍历。（5分）5、（1）根据线性表（23，49，28，10，30，5，16），画出二叉排序树。（5分）（2）根据上述二叉排序树，查找数7，需要比较哪几个数？（5分）五、程序填空题（共15分）1、已知QUEUE表示循环队列的数据结构，函数leavequeue是将队头元素的值放入变量e，然后删除队头元素，操作成功返回1，否则返回0。完成以下程序。（4分）typedefstruct{intdata[100];intfront;/*队头元素的下标*/intrear；/*等于队尾元素的下标加1*/}QUEUE;leavequeue(QUEUE*Q,int*e){if(){return0;}*e=Q->data[Q->front];Q->front=;return1;}2、以下函数ins的功能是在顺序表a中找到第一个值为x的元素，然后在该元素之前插入一个值为y的元素，如果找不到值为x的元素，则新元素成为顺序表的最后一个元素。插入成功返回1，否则返回0。完成程序。（6分）typedefstruct{intelem[100];intlength;}SQ;intins(SQ*a,intx,inty){intk,i;if(){return0;}for(k=0;k<a->length;++k){if(a->elem[k]==x){break;}}if(k==a->length){--k;}else{for(i=a->length-1;i>k;--i)//应改为：for(i=a->length-1;i>=k;--i){a->elem[i+1]=a->elem[i];}}a[k+1]=y;a->length;return1;}3、已知一个单链表的表头指针为h，每个结点含元素值data和下一结点的地址next。链表一共有5个结点，其元素值分别为100，200，300，400，500，经过下列语句后，输出什么结果？（本题3分）for(p=h;p->data<300;p=p->next){p->next=p->next->next;}printf(“%d”,p->data);六、编程题（共15分）1、编写算法求二叉树的非叶子结点数目。（8分）已知二叉树结点数据结构如下：typedefstructlinkNode{intdata;structlinkNode*lchild,*rchild;}Node;2、编写算法判断一个单链表中各结点的值是不是由小到大排列，如是（包括空表）返回1，不是返回0。（7分）已知单链表结点数据结构如下：typedefstructlinkNode{intdata;structlinkNode*next;}Node;模拟题7答案一、选择题12345678CCDDBBAC二、判断题12345678××××××××三、填空题1、图结构 集合结构2、O(n2log2n)3、54、虚溢出5、136、207、降序排列8、11四、简答题1、（1）20 12 26 45 30（2）16 18 20 40，需移动2个元素2、（1）D B A F G E C3、4、（1）//下图错误！//正确的邻接表如下：1261260350ABCDEFG0312435012345614（2）C A D B G F E//正确为：C A D B G E F5、（1）（2）23 10 5五、程序填空题1、（1）Q->front==Q->rear(2)(Q->front+1)%1002、（1）a->length>=100（2）a->elem[i]=a->elem[i-1]（3）a[k](4)++或者=a->length+13、300六、编程题1、intcountNotLeaf(Node*BT){if(BT==NULL){return0;

}if((BT->lchild==NULL)&&(BT->rchild==NULL)){return0;

}return(1+countNotLeaf(BT->lchild)+countN