数据结构期末试题及答案

《数据结构期末试题及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》期末考试试卷一、选择题(单选题，每小题3分，共33分)1.已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA,则该二叉树的后序序列为BA.BCDEAFB.ABDCEFC.DBACEFD.DABECF2.在11个元素的冇序表中进行折半查找(L(/ow+/"02)/2」)，查找元索A[11]时，被比较的元素的下标依次是—。C.6,7,9,11D.6,8,9,A.6,8,10,11B.6,9,10,11113.由元素序列(27,16,75,38,51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为—oA.27B.3

2、8C.51D.754.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二义排序树以后，査找元素30要进行B次元素间的比较。A.4B.5C.6D.75.循环链表的主要优点是DoA.不再需要头指针了B.已知某个结点的位置后，很容易找到它的直接RiJ驱结点C.在进行删除后，能保证链表不断开D.从表屮任一结点出发都能遍历整个链表6.已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A[0...6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均

3、查找长度为A.1.5B.1.7C.2.0D.2.37.由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为COA.23B.37C.44D.468.在最好和最坏情况F的时间复杂度均为O(nlogn)且稳定的排序方法是_D_。A.基数排序B.快速排序C.堆排序D.归并排序9.无向图G=(V,E),其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}。对该图进行深度优先遍历，下面不能得到的序列是A°A.aebdcfB.abedfcC.aedfcbD.acfdeb1.置换•选择排序的功能是—A

4、.产生初始归并段B.选出最人的元素C.产生有序文件记录11.ISAM和VSAM文件属于A°A.索引顺序文件B.索引非顺序文件C.顺序文件D.置换某个D.散列文件二、填空题(1〜8每空2分，9-12每空1分，共20分)1・下而程序段的吋间复朵度为_0(、历)—OSum=1;For(i=0;sumvn;i++)sum+=i;2.稀疏矩阵快速转置算法(见笫三题笫1小题)的时间复杂度为_CXtu+nu)_,空间复杂度为_O(nu)_«3.对广义表A=(a,(b,c,d))的运算head(rail(A))的结果是(b,c,d)。2.将n个数据元索依次按a1,a2,-,an的顺序压入栈屮，共

5、有亠n+1种出栈序列。3.含有4个结点的不相似的二义树有_14_棵。6・设有一个二维数纟RA[m]fnl，假设A[0][0]存放位置在644(I0),A⑵[2]存放位置在676a),每个元素占一个空间，则A[3][3](1O)存放的位置为692。(脚注(⑼表示用W进制表示)7.若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是一69。8.给定一组关键字{49,38,65,97,76,13,27,49'},以下用了4种不同的排序方法分别得到了第--趟排序后的结果，请指出各H对应的排序方法。(每空1分)笫一趟排序后的结果排序方法{27,38,13,49,7

6、6,97,65,49'}丄快速排序1{38,49,65,97,13,76,27,49'}丄二路归并排序』{49',76,65,49,38,13,27,97}丄堆排序1{13,65,76,97,27,38,49,49'}丄链式基数排序】三、算法填空题(每空3分，共18分)1.稀疏矩阵快速转置算法〃稀疏矩阵的三元纽•顺序表存储表示#defineMAXSIZE12500〃非零元个数最人为12500typedefstruct{inti,j;//彳亍号，列号ElemTypee;〃非零元jTriple;typedefstruct{Tripledata[MAXSIZE+l];〃三元组表.0号不

7、用intmu,nu,tu;〃总行数，总列数,非零元总个数JTSMatrix;#defineMAXCOL50statusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组表存储表示，求稀疏短阵M的转置短阵T.intnum[MAXCOL],cpot[MAXCOL],col,t,p,q;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;