长沙理工大学数据结构期末考试试卷

-长沙理工大学计算机与通信工程学院2013-2014学年二学期数据结构期末考试试卷(B卷)班级:_学号:_姓名:_得分:_题号一二三四五六七八九十成绩复核得分阅卷题目部分，(卷面共有31题,100分,各大题标有题量和总分)一、应用题(1小题,共8分)1已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。二、判断正误(7小题,共14分)1串中任意个字符组成的子序列称为该串的子串。2带权无向图的最小生成树是唯一的。（ ）3如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）4无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。（ ）5向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ）6堆是完全二叉树，完全二叉树不一定是堆。（ ）7数据的逻辑结构和数据的存储结构是相同的。（ ）三、单项选择题(10小题,共20分)1在顺序表中，只要知道（ ），就可以求出任一结点的存储地址。A基地址 B结点大小 C 向量大小 D基地址和结点大小 2设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。 A q=p-next；p-data=q-data；p-next=q-next；free(q)； B q=p-next；q-data=p-data；p-next=q-next；free(q)；C q=p-next；p-next=q-next；free(q)；D q=p-next；p-data=q-data；free(q)；3循环队列占用的空间( )。 A必须连续 B不必连续 C不能连续 D可以不连续4若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。 A5和1 B4和2 C2和4 D1和55设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 A 20 B 256 C 512 D 10246设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。 A 4 B 5 C 6 D 77若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3 D. 9，4，2，38在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择（ ）排序，如果从节省存储空间的角度来考虑则最好选择（ ）排序。9设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。 A 40，42，45，55，80，83 B 42，40，45，80，85，88 C 42，40，45，55，80，85 D 42，40，45，85，55，8010下列叙述正确的是（ ）A算法的执行效率与数据的存储结构无关 B算法的空间复杂度是指算法程序中指令（或语句）的条数 C算法的有穷性是指算法必须能在执行有限个步骤之后终止 D算法的时间复杂度是指执行算法程序所需要的时间四、算法设计题(4小题,共32分)1设计判断单链表中元素是否是递增的算法。2一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。3设计一个在链式存储结构上统计二叉树中结点个数的算法。4设计算法，计算图中出度为零的顶点个数。五、填空题(6小题,共12分)1当循环队列为空时，不能进行出队运算，这种情况称为（ ）。2已知顺序栈S，在对S进行进栈操作之前首先要判断（ ），在对S进行出栈操作之前首先要判断（ ）。3设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为( )。4完全二叉树中第5层上最少有（ ）个结点，最多有（ ）个结点。5表示一个有100个顶点，1000条边的有向图的邻接矩阵有（ ）个非零矩阵元素。6若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为（ ）六、简答题(2小题,共10分)1设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列， 能否得到输出顺序为154623的序列。2设有无向图G（如下图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。七、名词解释(1小题,共4分)1什么是AOE网?长沙理工大学计算机与通信工程学院2013-2014学年二学期数据结构期末考试试卷(B卷)答案部分，(卷面共有31题,100.0分,各大题标有题量和总分)一、应用题(1小题,共8分)1【解答】深度优先遍历序列为：1，2，3，4，5，6 广度优先遍历序列为：1，2，4，3，5，6二、判断正误(7小题,共14分)1错2错3对4错5错6对7错三、单项选择题(10小题,共20分)1D2A3A4B5C6A7D8快速 堆9C10C四、算法设计题(4小题,共32分)1int isriselk(lklist *head)if(head=0|head-next=0) return(1);else For(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) return(0);return(1);2解：用一个循环数组Queue0，n-1表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。（1）入队算法： void inqueqe(int x) int temp;if (count=n) printf( 队列上溢出n); Else count+ temp=(front+count)%n; Queuetemp=x （2）出队算法： int outqueue() int temp;if (count=0) printf( 队列下溢出n); Else temp=Queuefront; front=(front+1)%n; count-; return temp; 3void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,count);4在有向图的邻接矩阵中，一行对应一个顶点，每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行的非零元素个数是否为零，若是则计数器加1。具体算法如下：五、填空题(6小题,共12分)1下溢2栈是否满 栈是否空 30（1）41，16510006 O（n2）六、简答题(2小题,共8分)1不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出