2007092数据结构期末试卷B

1、汕头职业技术学院2007-2009学年第二学期期末试卷（B）课程名称数据结构学分_拟题人何汉阳审题人_系(校区)计算机系班级_学号_姓名_题号一二三四五六七八总分评卷人得分一、判断题（每题1分，共15分）1、数据的物理结构是指数据在计算机内的实质储藏形式。（）2、分配给单链表的内存地址必定是连续的。（）3、在有n个元素的序次表中，删除任意一个元素所需搬动结点的平局次数为n-1。（）4、对于单循环链表，从表中任一结点都能扫描表中的全部结点。（）5、栈是一种对进栈、出栈操作总次数做了限制的线性表。（）6、无论是序次队列还是链接队列，插入和删除元素运算的时间复杂度都是O(1）。（）7、表示稀罕矩阵的

2、三元组序次中，各元素的排列序次与矩阵元素值的大小有关。（）8、完好二叉树中只有度为0和度为2的结点。（）9、已知二叉树的先序序列和后序序列，其实不能够唯一确定这棵二叉树。（）10、哈夫曼树中，权值较大的叶结点一般都离根结点较远。（）11、若是表示有向图的毗邻矩阵是对称矩阵，则该有向图必然是完好有向图。（）12、有向图的遍历不能采用广度优先找寻方法。（）13、序次表和单链表表示的有序表均可使用二分查找法来提高查找速度。（）14、只有在记录的要点字的初始状态为逆序排列的情况下，直接选择排序过程中元素的搬动次数才会达到最大值。（）15、内排序中的快速排序方法，在任何情况下均可获取最快的排序收效。（）

3、二、选择题（每题2分，共40分）1_中任何两个结点之间都没有逻辑关系。会集B)图状结构C)树型结构D)线性结构2计算机算法指的是_。A)计算方法B)调换方法C)排序方法D)解决某一问题的有限运算序列3下面_的时间复杂性最好，即执行时间最短。A)O(n)B)O(nlogn)C)O(log3n)D)O(n)224在一个长度为n的序次表中，向第i个元素(1in+1)地址插入一个新元素时，需要从后向前依次后移_个元素。A)n-iB)iC)n-i-1D)n-i+l5对序次储藏的线性表，设其长度为n，在任何地址上插入或删除操作都是等概率的，插入一个元素时-1-/4平均搬动表中的_个元素。A)n/2B)(n

4、-1)2C)(n+1)2D)n6单链表要求内存中可用储藏单元的地址。A)必定是连续的B)必然是不连续的C)部分地址必定是连续的D)能够是连续的，也能够是不连续的7在一个单链表中，若要删除p指针所指向结点的后继结点，则执行_。A)p-next=pB)p=p-next-nextC)p-next=p-next-nextD)p=p-next；p-next=p-next-next8若某链表最常用的操作是在最后一个结点此后插入一个结点和删除最后一个结点，则采用_存储方式最节约时间。单链表B)双链表C)单循环链表D)带头结点的双循环链表9采用链接方式储藏线性表的优点是_。便于随机存取B)开销的储藏空间较序次

5、储藏少便于插入和删除操作D)数据元素的物理序次和逻辑序次相同10在下面栈的基本运算中，不是加工型运算的是_。初始化B)进栈C)退栈D)判栈空11在序次栈中进行退栈操作时，_。A)谁先谁后都能够B)先搬动栈顶指针，后取出元素C)不分先后，同时进行D)先取出元素，后搬动栈顶指针12假设一个栈的输入序列为A，B，C，D，E，则以下序列中不能能是栈的输出序列的是_。A)B，C，D，A，EB)E，D，A，C，BC)B，C，A，D，ED)A，E，D，C，B13在由n个单元组成的序次储藏的循环队列sq中，假设f和r分别为队头指针和队尾指针，则判断队满的条件是_。A)f=(r十1)nB)(r-1)n=fC)f

6、=rD)(f+1)n=r14树最适合于表示_。A)有序数据元素B)无序数据元素C)元素之间无联系的数据D)元素之间拥有分支层次关系的数据15在一棵深度为k的完好二叉树中，所含结点个数不小于_。A)2kB)2k+1C)2k-1D)2k-116在以下储藏形式中，_不是树的储藏形式。A)双亲表示法B)序次储藏表示C)孩子兄弟表示法D)孩子链表表示法17对于长度为8的序次储藏结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为_的值除以8。A)17B)19C)21D)2018若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为_。A)1B)i-1C)iD)i+l1

7、9在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行_。对相邻元素之间的交换。A)n2B)n-1C)nD)n+l20以下四种排序方法中，需要附加的内存空间最大的是_。A)插入排序B)选择排序C)快度排序D)归并排序三、列表说明用Prim算法求解以下列图最小生成树的生成过程。（15分）-2-/4四、试编写在带头结点的单链表中删除（一个）最小值结点的“高效”算法。（10分）五、要点码序列为47,7,29,11,16,92,22,8,3,50,37,89,21，哈希函数为H(k)=k%11，画出其开散列表办理矛盾表示图，并计算查找成功的平均查找长度。（10分）。六、写出序次表大将监察哨设在高端

8、的序次查找算方法程序，并要写出在main()主函数中调用的过程语句。查找表的结构定义同课本一致，查找表的元素值和长度经过键盘输入。（10分）。2007-2009学年第二学期期末试卷（B）答案课程名称数据结构拟题人何汉阳一、判断题（每题1分，共15分）15、610、1115、二、选择题（每题2分，共40分）15、ADCDA610、DCDCD1115、DBADD1620、DBCBD三、解：（15分）设从极点0出发U=0,V-U=1,2,3,4,5,6Adjvex/000000k=5Lowcost02810(0,5)U=0,5,V-U=1,2,3,4,6Adjvex/000500k=4Lowcost

9、028250(5,4)U=0,5,4,V-U=1,2,3,6Adjvex/004504k=3Lowcost028220024(4,3)U=0,5,4,3,V-U=1,2,6Adjvex/034503k=2Lowcost0281200018(3,2)U=0,5,4,3,2,V-U=1,6Adjvex/234503k=1Lowcost016000018(2,1)U=0,5,4,3,2,1,V-U=6Adjvex/234501k=6Lowcost00000014(1,6)U=0,5,4,3,2,1,6,V-U=四、解：（10分）002810128016142160123120221842202524

10、51025061418240voidDelMinNode(LINKLIST*head)LINKLIST*p,*q,*r;/r为指向最小值结点的前一个结点-3-/4p=head-next;q=head;r=q;/假设第一个值结点最小while(pNULL)q=p;p=p-next;if(p-datanext-data)r=q;if(r-next-next=NULL)/若最小值是尾结点p=r-next;r-next=NULL;free(p);elsep=r-next;r-next=p-next;free(p);五、解：（10分）0112217/13查找成功的平均查找长度ASL（1+1+2+1+1+

11、1+2+1+2+1+2+1+1）/13六、解：（10分）891#include2#defineMAXSIZE1004733typedefstructintkey;49237516SSELEMENT;typedefstruct650SSELEMENTrMAXSIZE;29intlen;778SSTABLE;89intseq_search(intk,SSTABLEst)intj=0;1021st.rst.len.key=k;while(st.rj.key!=k)j+;if(jst.len)returnj+1;elsereturn0;voidmain()intk,i;SSTABLEst;printf(InputLen:);scanf(%d,&st.len);for(i=0;ist.len;i+)scanf(%d,&st.ri.key);printf(nsearchthenumber:);scanf(%d,&k);i=