数据结构期末试题及答案

E卷一、单项选择题1、线性表若采用链式结构时，要求内存中可用存储单元的地址()。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以2、判定一个栈ST(最多元素为m0)为空的条件是()。A.ST-top!=0B.ST-top==0C.ST-top!=m0D.ST-top==m03、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列j下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为()。A.SA+141B.SA+144C.SA+222D.SA+2254、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空如用二次探测再散列处理冲突，关键字为49的结点的地址是()。A.8B.3C.5D.95、在线索化二叉树中，t所指结点没有左子树的充要条件是()。A.t-left==NULLB.t-ltag==1C.t-ltag==1且t-left==NULLD.以上都不对6、将递归算法转换成对应的非递归算法时，通常需要使用()。A.栈B.队列C.链表D.树7、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，()次比较后查找成功。A.1B.2C.4D.88、对一个满二叉树，m个树叶，n个结点，深度为h，则()。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-19、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_____查找方法。A.分块B.顺序C.二分D.散列10、快速排序方法在()情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数11、在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为________.A.eB.2eC.2n-eD.2n-2e12.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点iV相关的所有弧的时间复杂度是_________.A.O(n)B.O(e)C.O(n+e)D.O(n*e)13.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是_________.A.选择排序B.希尔排序C.归并排序D.快速排序14.适宜于对动态查找表进行高效率查找的组织结构是_____.A.有序表B.分块有序表C.三叉排序表D.线性链表15.不定长文件是指__________.A.文件的长度不固定B.记录的长度不固定C.字段的长度不固定D.关键字项的长度不固定二、填空题16、对数据间关系的描述是数据的逻辑结构，形式地可以用一个二元组B=（D，R）来表示，其中D表示________；R表示___________。17、数据结构的存储一有两种，分为_______和________.18、评价一个数据结构，基本来说有两条，一条是_______，二是_______。19、栈的类型说明为：typedefstrucstack{datatypes(maxlen);intlen;}stack;则：POP（stackst）;算法是：ifst.len=0printf(“underflow”)else__________;20、二叉树的第i层上至多有______结点，深度为k的二叉树至多有________结点。21、图的遍历主要有________和_________两种.22、在hq的链队中，判定只有一个结点的条件是____________。23、在散列函数H(key)=key%p中，p应取_________。24、对于长度为n的线性表，若采用二分法查找，则时间复杂度为_____；若采用分块查找(假定总块数和每块长度均接近n的平方根)，则时间复杂度为_________。三、解答操作题（每小题5分，共20分）25、已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示：（1）画出该图的图形。（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，并写出遍历序列。26、把下列二叉树换成二森林，画出图形27、已知一个散列表如下表示：0110110110110000100110010edcba35203348590123456789101112其散列函数h(key)=key%13,处理冲突的方法为双重散列法，探查序列为：ih=(h(key))+i*h1(key)%mi=0,1,…,m-1其中h1(key)=key%11+1回答以下问题：（1）对表中关键字35，20，33和48进行查找时，所需要进行的比较次数各为多少？（2）该散列表在等概率查找时查找成功的平均查找长度为多少？28、已知序列{17,18,60,40,7,32,73,65,85},请给出采用起泡排序法对该序列作升序排序时的每一趟的结果。四、算法阅读题(每小题6分，共12分)29、面给出了起泡排序算法，请填写算法中的空框，使算法正确。structnode{intkey;datatypeinfo;}node,*lnode；inti，j;intflag;nodeX;nodeR[n];①[每循环一次作一次起泡]循环i以1为步长，从1到n－1，执行下列语句(1)()(2)循环j以1为步长，()，执行若()＜R[j].key则flag←1；X←R[j]；()；R[j＋1]←X(3)若()则跳出循环②算法结束30、下面给出了在对称序穿线树中找指定结点在后序下的前驱算法，请填写算法中的空框，使算法正确。structnode{datatypeinfo;node*llink，*rlink;}*lnode；lnodep;[p指向指定结点]lnodeq;[q指向指定结点在后序下的前驱]①若p-rlink＞0则()，算法结束否则q←p②(1)循环当()时，反复执行()(2)()③算法结束五、算法设计题（共8分）31.设有一个循环双链表，其中有一结点的指针为p,编写一个函数p与其右边的一个结点进行交换。结点结构为E卷一、单项选择题1.D2.B3.C4.D5.B6.A7.C8.D9.A10.C11.D12.C13.D14.C15.B二、填空题16．数据集合数据间的关系17．顺序非顺序18．时间复杂度空间复杂度19．st.len=st.len-120．2i-12k-121．深度广度22．hq-front=hq-rear23．素数24．O(log2n)O(n)三、解答操作题（每小题5分，共20分）25、深度优先遍历序列为：abdce;广度优先遍历序列为：abedc26、27、答：（1）比较次数分别为3、2、1、1。（2）平均查找长度ASL=(3+2+1+1+2)/5=1.828、初始：17，18，60，40，7，32，73，65，85第1趟：17，18，40，7，32，60，65，73，85第2趟：17，18，7，32，40，60，65，73，85第3趟：17，7，18，32，40，60，65，73，85第4趟：7，17，18，32，40，60，65，73，85第5趟：7，17，18，32，40，60，65，73，85四、算法阅读题（每小题6分，共12分）29．(1)flag=0；(2)1到n-1；(3)R[j＋1].key；(4)R[j]=R[j＋1]；(5)flag＝030．q=p-.rlinkq-link＜0q=(－1)*(q-llink)q=q-.llink五、算法设计题（共8分）参考答案voidswap(dnode*p){dnode*q;q=p-right;if(q==NULL)printf(“不能进行交换!/n”);else{p-right=q-right;p-right-left=p;p-left-right=q;q-left=p-left;p-left=q;q-right=p;}}