2007-09(2)数据结构期末试卷(B)

--#-汕头职业技术学院TOC\o"1-5"\h\z2007-2009学年第二学期期末试卷（ B）课程名称数据结构 学分_题人何汉阳审题人r。系校区计算机系班级学号姓名题号一二三四五六七八总分评卷入得分TOC\o"1-5"\h\z一、判断题（每小题1分，共15分）1、数据的物理结构是指数据在计算机内的实际存储形式。（ ）2、分配给单链表的内存地址必须是连续的。（ ）3、在有n个元素的顺序表中，删除任意一个元素所需移动结点的平局次数为n-1。（ ）4、对于单循环链表，从表中任一结点都能扫描表中的全部结点。（ ）5、栈是一种对进栈、出栈操作总次数做了限制的线性表。（ ）6、无论是顺序队列还是链接队列，插入和删除元素运算的时间复杂度都是0（1）。（ ）7、表示稀疏矩阵的三元组顺序中，各元素的排列顺序与矩阵元素值的大小有关。（ ）8、完全二叉树中只有度为0和度为2的结点。（）9、已知二叉树的先序序列和后序序列，并不能唯一确定这棵二叉树。（ ）10、哈夫曼树中，权值较大的叶结点一般都离根结点较远。（ ）11、如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图。（ ）12、有向图的遍历不可采用广度优先搜索方法。（ ）13、顺序表和单链表表示的有序表均可使用二分查找法来提高查找速度。（ ）14、只有在记录的关键字的初始状态为逆序排列的情况下，直接选择排序过程中元素的移动次数才会达到最大值。（ ）15、内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。（ ）二、选择题（每小题2分，共40分）1． 中_任_何_两_个_结点之间都没有逻辑关系。集合 图状结构 树型结构 线性结构2．计算机算法指的是 。 计算方法 调度方法排序方法 解决某一问题的有限运算序列3．下面 的_时_间_复_杂_性_最好，即执行时间最短。.在一个长度为的顺序表中，向第个元素1W 位置插入一个新元素时，需要从后向前依次后移 个_元_素_。5对顺序存储的线性表，设其长度为，在任何位置上插入或删除操作都是等概率的，插入一个元素时平均移动表中的 个_元_素_。TOC\o"1-5"\h\z/ /6．单链表要求内存中可用存储单元的地址 。必须是连续的 一定是不连续的部分地址必须是连续的 可以是连续的，也可以是不连续的7在一个单链表中，若要删除指针所指向结点的后继结点，则执行 。8．若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用___存_储方式最节省时间。单链表 双链表 单循环链表 带头结点的双循环链表9．采用链接方式存储线性表的优点是 。 便于随机存取 花费的存储空间较顺序存储少便于插入和删除操作 数据元素的物理顺序和逻辑顺序相同10．在下面栈的基本运算中，不是加工型运算的是 。___初始化 进栈 退栈 判栈空1．1在顺序栈中进行退栈操作时， 。 谁先谁后都可以 先移动栈顶指针，后取出元素不分先后，同时进行 先取出元素，后移动栈顶指针.假设一个栈的输入序列为AB,DE则下列序列中不可能是栈的输出序列的是 _.在由个单元组成的顺序存储的循环队列中，假定和分别为队头指针和队尾指针，则判断队满的条件是 。___十% % %1.4树最适合于表示 。 有序数据元素 无序数据元素元素之间无联系的数据 元素之间具有分支层次关系的数据.在一棵深度为的完全二叉树中，所含结点个数不小于 _

6．在下列存储形式中，6．在下列存储形式中，双亲表示法孩子兄弟表示法_不_是_树_的存储形式。顺序存储表示孩子链表表示法1．7对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为 的_值_除_以__8。.若对个元素进行直接插入排序，则进行第趟排序过程前，有序表中的元素个数为.在对个元素进行冒泡排序的过程中，第一趟排序至多需要进行 _对相邻元素之间的交换。／A2)nB)n-1C)nD)n+l20.以下四种排序方法中，需要附加的内存空间最大的是 。_插入排序 选择排序 快度排序 归并排序三、列表说明用算法求解下图最小生成树的生成过程。(分)四、试编写在带头结点的单链表中删除（一个）最小值结点的“高效”算法。（10分）五、关键码序列为47,7,29,11,16,92,，2哈2希,函数8为,H3（,k）%5=画出其开散列表处理冲突示意图，并计算查找成功的平均查找长度。（10分）。六、写出顺序表上将监视哨设在高端的顺序查找算法子程序，并要写出在 主函数中调用的过程语句。查找表的结构定义同课本一致，查找表的元素值和长度通过键盘输入。（10分）。2007-2009学年第二学期期末试卷（B）答案课程名称数据结构拟题人何汉阳、判断题（每小题1分，共15分）〜、JXXJX〜0xxxvx、xxxjx、选择题（每小题2分，共40分）1〜5、ADCDA 6〜10、DCDCD11〜15、DBADD16〜20、DBCBDU={0},V-U={1,2,3,4,5,6}Adjvex/000000k=5Lowcost028ggg10g(0,5)U={0,5},V-U={1,2,3,4,6}Adjvex/000500k=4Lowcost028gg250g(5,4)U={0,5,4},V-U={1,2,3,6}Adjvex/004504k=3Lowcost028g220024(4,3)U={0,5,4,3},V-U={1,2,6}Adjvex/034503k=2Lowcost0281200018(3,2)U={0,5,4,3,2},V-U={1,6}Adjvex/234503k=1Lowcost016000018(2,1)U={0,5,4,3,2,1},V-U={6}Adjvex/234501k=6Lowcost00000014(1,6)U={0,5,4,3,2,1,6},V-U={}三、解：（1、分）设从顶点0出发四、解：(10分)voidDelMinNode(LINKLIST*head){LINKLIST*p,*q,*r; 为指向最小值结点的前一个结点p=head->next;q=head;r=q;/假/设第一个值结点最小while(p<>NULL){q=p;p=p->next;if(p->data<r->next->data)r=q;}if(r->next->next==NULL)/若/最小值是尾结点{p=r->next;r->next=NULL;free(p);}else{p=r->next;r->next=p->next;free(p);}00288881081280168881428160128883881202281848882202524510888250868148182480五、解：（10分）012345678910查找成功的平均查找长度 =（六、解：(10分)#include<stdio.h>#defineMAXSIZE100typedefstruct{intkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intseq_search(intk,SSTABLEst){intj=0;st.r[st.len].key=k;while(st.r[j].key!=k)j++;if(j<st.len)returnj+1;elsereturn0;}voidmain(){intk,i;SSTABLEst;printf("InputLen