《数据结构》网上教学活动文本(20031225).doc

《《数据结构》网上教学活动文本(20031225).doc》由会员分享，可在线阅读，更多相关《《数据结构》网上教学活动文本(20031225).doc（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构网上教学活动文本（2003.12.25）问：今年的数据结构有期末复习提纲吗？或是以什么为准来复习呢？徐孝凯：每年都有，由中央电大教育杂志社发表。问：请问我们该如何复习数据结构徐孝凯：按该课程期末复习指导和作业进行复习。问：请问这次数据结构考试的重点在哪里徐孝凯：和以往题型与复习范围相同。按期末复习指导去做。问：本科和专科的卷子一样吗？徐孝凯：不一样，各一份。问：数据结构的习题有答案吗?考试题型是什么?能给我一份样题吗?徐孝凯：中央广播电视大学2002年春计算机应用专业 数据结构 课程考试（闭卷）1题 号一二三 四 五六总 分得 分2002年9月补考 一、单选题（每小题2分，共8分） 1

2、. 若需要利用形参直接访问实参，则应把形参变量说明为_参数 A 指针 B 引用 C 值 D 常量 2. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行_。 A q-next=p-next; p-next=q; B p-next=q-next; q-next=p; C q-next=p-next; p-next=q; D p-next=q-next; q=p; 3. 在一个顺序循环队列中，队首指针指向队首元素的_位置。 A 后两个 B 后一个 C 当前 D前一个 4. 从二叉搜索树中查找一个元素时，其时间复杂度大致为_。 A O(1) B O(n) C O(l

3、og2n ) D O(nlog2n) 二、填空题（每空1分，共32分） 1. 数据的存储结构被分为_、_、_和_四种。 2. 对于一个长度为n的顺序存储的单链表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。 3. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_、_和_三项。 4一个广义表的深度等于它所有子表的最大深度加_。 5当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件为_。 6. 假定一棵四叉树的结点个数为50，则它的最小深度为_。 7在一棵二叉树和三叉树中，第5层上的结点数最多分别为_个和_个结点。 8在一棵高度为h的理想平

4、衡树中，最少含有_个结点，最多含有_个结点。 9. 在一个小根堆中，_结点的值是所有结点中的最小值，向一个小根堆中插入一个元素时，若它的值小于原堆中的所有结点的值，则需要逐层调整到_结点为止。 10. 在一个具有n个顶点的无向完全图中，共包含有_条边。 11. 假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为_、_和_。 12用二分查找方法在有序表上查找一个关键字为K的元素时，若K小于中点元素的关键字，则继续在_子表上查找，若K大于中点元素的关键字，则继续在_子表上查找。 13在索引表中，若一个索引项对应主表中的一条记录，则称此索引为_索引，若对

5、应主表中的若干条记录，则称此索引为_索引。 14. 在线性表的散列存储中，处理冲突有_和_两种方法。 15在向一棵B_树插入一个元素的过程中，若最终引起树根结点的分裂，则新树的高度比原树增_；从一棵B_树删除一个元素的过程中，若最终引起树根结点的合并，则新树的高度比原树减_。 16堆排序在平均情况下的时间复杂度为_，空间复杂度为_。 三、运算题（每小题6分，共24分） 1. 假定一个大根堆为(56,38,42,30,25,40,35)，则依次从中删除三个元素后得到的堆为_。 2. 已知一个图的顶点集V和边集G分别为： V=0,1,2,3,4,5,6,7; E=(0,1)4,(0,2)13,(0

6、,3)5,(1,3)6,(1,5)7,(2,3)10,(2,4)15,(3,5)9,(3,6)8, (4,6)12,(5,7)3; 按照克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 _, _, _, _, _, _, _。 3假定一组数据的初始堆为(84,79,56,42,40,46,50,38)，请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。 数据排列情况： 4假定一组记录的排序码为(46,25,56,38,40,80,36,40,75,66,84,79)，对其进行快速排序，进行前两层划分后的结果为：_。 四、阅读算法，回答问题（每小题8分，共16分） 1

7、. void AA(List& L) InitList(L); InsertRear(L,30); Insert(L,50); int a5=25,38,12,60,45; for(int i=0;i5;i+) Insert(L,ai); 该算法被调用执行后，得到的线性表L为：_ 2. void AF(Queue& Q) InitQueue(Q); int a4=5,8,12,15; for(int i=0;i4;i+) QInsert(Q,ai); QInsert(Q,QDelete(Q); QInsert(Q,30); QInsert(Q,QDelete(Q); QInsert(Q,QDe

8、lete(Q)+20); while(!QueueEmpty(Q) coutQDelete(Q) ; 该算法被调用后得到的输出结果为： 五、算法填空，在画有横线的地方填写合适的内容(10分)。 在一维数组An上进行快速排序的递归算法。 void QuickSort(ElemType A, int s, int t) int i=s, j=t+1; ElemType x=As; do do _; while(Ai.stnx.stn); if(ij) ElemType temp=Ai; Ai=Aj; Aj=temp; while(ij); As=Aj; Aj=x; if(sj-1) _; if(j+1left)+Count(BT-right)+1; 7