南昌大学 2008～2009学年第二学期数据结构期末考试标准答案a

《南昌大学 2008～2009学年第二学期数据结构期末考试标准答案a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南昌大学2008～2009学年第二学期期末考试试卷试卷编号：(A)卷课程编号：课程名称：数据结构考试形式：闭卷适用班级：计算机系07级姓名：学号：班级：学院：信息工程学院专业：计算机科学与技术考试日期：题号一二三四五六七八九十总分累分人签名题分2010401515100得分考生注意事项：1、本试卷共7页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每空2分，共20分)得分评阅人1、数据结构有线性结构、树结构、图结构、集合结构等几种逻辑结构。22、已知某算法的执行时间为

2、（n+n）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是2O(n)。3、在一个长度为n的顺序表中插入一个元素，最少需要移动0个元素，最多需要移动n个元素。4、如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为p->lchild==NULL。5、一个无向连通图有6个顶点7条边，则其生成树有5条边。6、如果一个有向图有5个顶点，则它最多有20条弧。7、如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图无环。8、顺序存储的队列如果不采用循环方式，则会出现虚溢出问题。第1页共7页二、判断题（每题1分，共1

3、0分，对的打√，错的打×）得分评阅人1、如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继结点，则必为线性表。（×）22、快速排序法在最坏的情况下时间复杂度是O（n）。（√）3、若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必须是该子树的先序遍历的最后一个结点。（×）4、有向图的邻接矩阵的第i行的所有元素之和等于第i列的所有元素之和。（×）5、二叉排序树中，任一结点的值都大于或等于其孩子的值。（×）6、一棵二叉排序树，根元素不一定是值最大的元素。（√）7、顺序栈进栈操作时，一般情况下需要判断栈是否已满。（√）8、如果某排序算法

4、是稳定的，那么该方法一定具有实际应用价值。（×）9、对长度为100的有序线性表用二分法查找时，最小比较次数为0。（×）10、进栈、出栈操作的时间复杂度为O（1）。（√）第2页共7页三、简答题（共40分）得分评阅人1、排序。（1）写出线性表（26，45，12，2，30，6，15，29，16，2，18）采用快速算法排序后，第一趟结束时的结果。（5分）2012264530（2）线性表采用插入排序算法排序几趟后，有序部分是（16，20，40），无序部分是（18，25），则下一趟的排序需要移动几个元素？写出下一趟结束时的结果。（5分）16182040，需移

5、动2个元素2、给出如图1所示的二叉树的中序遍历结果。（5分）ABCDEFG?1DBAFGEC3、已知5个结点的权值分别是4，6，1，13，7，请画出这结点构成的Huffman树。（5分）3113187115614第3页共7页4、已知图2是一个无向图：（1）画出该无向图的邻接链表。（5分）（2）基于你给出的邻接链表，求从顶点C出发的广度优先遍历。（5分）DCEBGAF?2（1）（2）CADBGFE5、（1）根据线性表（23，49，28，10，30，5，16），画出二叉排序树。（5分）（2）根据上述二叉排序树，查找数7，需要比较哪几个数？（5分）（1

6、）2310495162830（2）23105第4页共7页四、程序填空题（共15分）得分评阅人1、已知QUEUE表示循环队列的数据结构，函数leavequeue是将队头元素的值放入变量e，然后删除队头元素，操作成功返回1，否则返回0。完成以下程序。（10分）typedefstruct{intdata[100];intfront;/*队头元素的下标*/intrear；/*等于队尾元素的下标加1*/}QUEUE;leavequeue(QUEUE*Q,int*e){if(Q->front==Q->rear){return0;}*e=Q->data[Q->

7、front];Q->front=;return1;}2.已知一个单链表的表头指针为h，每个结点含元素值data和下一结点的地址next。链表一共有5个结点，其元素值分别为100，200，300，400，500，经过下列语句后，输出什么结果？（本题5分）for(p=h;p->data<300;p=p->next){p->next=p->next->next;}printf(“%d”,p->data);300第5页共7页五、编程题（共15分）得分评阅人1．编写算法，删除顺序表前面的10个元素。如果顺序表中的元素少于10个，则删完为止。（7分）已知顺序

8、表的数据结构如下：typedefstruct{intelem[100];intlength;}SQ；intdelete(SQ*s){in