数据结构试题集_张敏

试卷一一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母代码填写在题后的括号内。错选、多选或未选均无分。1、按值可否分解，数据类型通常可分为两类，它们是（C）A、静态类型和动态类型B、原子类型和表类型C、原子类型和结构类型D、数组类型和指针类型2、若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是(C)A、无头结点的单向链表B、带头结点的单向链表C、带头结点的双循环链表D、带头结点的单循环链表3、对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不．成立的是(C)A、f(n)是0(g(n))B、g(n)是0(f(n))C、h(n)是0(nlogn)D、h(n)是0(n2)4、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）A、O（1）B、O（n）C、O（m）D、O（m+n）5、以下说法正确的是(A)A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串6、已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为(D)A、DEBAFCB、DEFBCAC、DEBCFAD、DEBFCA.7、队和栈的主要区别是(D)A、逻辑结构不同B、存储结构不同C、所包含的运算个数不同D、限定插入和删除的位置不同8、深度为6的二叉树最多有(B)个结点A、64B、.63C、32D、319、如图所示的二叉树的中序遍历序列是(B)A、abcdgefB、dfebagcC、dbaefcgD、defbagc10、下图G=(V,E)是一个带权连通图，G的最小生成树的权为(D)A、15B、16C、17D、1811、若非．连通无向图G含有21条边，则G的顶点个数至少为(B)A、7B、8C、21D、2212、如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B)A、不稳定的B、稳定的C、基于交换的D、基于选择的13、对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为(C)A、(5，1，4，3，6，2，8，7)B、(5，1，4，3，2，6，7，8)C、(5，1，4，3，2，6，8，7)D、(8，7，6，5，4，3，2，1)14、已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是(C)15、ISAM文件和VSAM文件的区别之一是(C)A、前者是索引顺序文件，后者是索引非顺序文件B、前者只能进行顺序存取，后者只能进行随机存取C、前者建立静态索引结构，后者建立动态索引结构D、前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分,共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16、下面程序段的时间复杂度为_____O(n)______。sum=1；for（i=0；sumn;i++）sum+=1；17、如果需要对线性表频繁进行____插入____或___删除_____操作，则不宜采用顺序存储结构。18、抽象数据类型的特点是将________和________封装在一起，从而现实信息隐藏。19、静态存储分配的顺序串在进行插入、置换和_______等操作时可能发生越界。20、用5个权值{3,2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。21、任意一棵完全二叉树中，度为1的结点数最多为______22、影响排序效率的两个因素是关键字的___________次数和记录的移动次数。23、产生冲突现象的两个关键字称为该散列函数的____________。24、若两个关键字通过散列函数映射到同一个散列地址，这种现象称为___________。25、常用的索引顺序文件是_______文件和______文件。三、解答题（本大题共4小题，每小题5分，共20分）26、要在［0..n-l］的向量空间中建立两个栈stackl和stack2，请回答：(1)应该如何设计这两个栈才能充分利用整个向量空间？(2)若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则：栈stackl空的条件是：___________；栈stack2空的条件是：___________；栈stackl和栈stack2满的条件是：___________。27、由字符集{s，t，a，e，i}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。28、已知树如右图所示，（1）写出该树的后序序列；（2）画出由该树转换得到的二叉树。ABCDEFGHIJK题28图ABCDEFGHIJK题28图29、对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。初始堆：第1趟：第2趟：四、算法阅读题（本大题共4小题，每小题5分，共20分）30、已知一个顺序表中的元素按关键字值非递减有序，下列算法删除顺序表中关键字相同的多余元素，使每个关键字不同的元素在表中只保留一个。已知顺序表的存储结构描述如下：#defineNodeSize20typedefstruct{intelem[NodeSize];intlength;}SqList;voidpurge_sq(SqList&la){//删除顺序表la中关键字相同的多余元素，即使操作之后的顺序表中只保留操作之前表中所有按关键字值都不相同的元素k=-1;//k指示新表的表尾for(i=0;i___(1)______;++i)//顺序考察表中每个元素{j=0;while(j=k&&la.elem[j]!=____(2)_________)______(3)______________;//在新表中查询是否存在和la.elem[i]相同的元素if(k==-1||jk)//k=-1表明当前考察的是第一个元素la.elem[++k]=______(4)___________;}//forla.length=____(5)__________;//修改表长}//purge_sq(1)(2)(3)(4)(5)31、下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。voidunion(LinkListLa,LinListLb){//本算法的功能是将所有Lb表中LinkListpre=La,q;LinkListpa=La-next;LinkListpb=Lb-next;free(Lb);while(pa&&pb){if(pa-datapb-data){pre=pa;pa=pa-next;}elseif(pa-datapb-data){(1)____________________________;pre=pb;pb=pb-next;(2)____________________________;}else{q=pb;pb=pb-next;free(q);}}if(pb)(3)____________________________;}32、阅读下列算法，并回答问题：(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；(2)写出上述函数调用过程中进行元素交换操作的总次数。voidf32(intR［］,intn){inti,t;for(i=0;in-1;i++)while(R［i］!=i){t=R［R［i］］;R［R［i］］=R［i］;R［i］=t;}}(1)(2)33、已知二叉树的存储结构为二叉链表，其类型定义如下：typedefstructNodeType{DataTypedata;structNodeType*lchild,*rchild;}BinTNode,*BinTree;阅读算法F32，并回答下列问题：(1)对于如图所示的二叉树，画出执行算法f32的结果；（2）简述算法f32的功能。BinTreef32(BinTreebt1){BinTreebt2;if(bt1==NULL)bt2=NULL;else{bt2=(BinTNode*)malloc(sizeof(BinTNode));bt2-data=bt1-data;bt2-rchild=f32(bt1-lchild);bt2-lchild=f32(bt1-rchild);}returnbt2;}(1)(2)五、算法设计题（本题10分）34、假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。试卷二一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母代码填写在题后的括号内。错选、多选或未选均无分。1、.数据的四种存储结构是（）A、顺序存储结构、链接存储结构、索引存储结构和散列存储结构B、线性存储结构、非线性存储结构、树型存储结构和图型存储结构C、集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D、顺序存储结构、树型存储结构、图型存储结构和散列存储结构2、若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是()A、无头结点的单向链表B、带头结点的单向链表C、带头结点的双循环链表D、带头结点的单循环链表3、在循环链表中，将头指针改设为尾指针rear后,其头结点和尾结点的存储位置分别是()A、rear和rear-next-nextB、rear-next和rearC、rear-next-next和rearD、rear和rear-next4、若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（）A、3B、5C、6D、75、串匹配算法的本质是()A、串复制B、串比较C、子串定位D、子串链接6、串的操作函数str定义为：intstr(char*s){char*p=s；while(*p！=′\0′)p++；returnp-s；}则str(″abcde″)的返回值是()A、3B、4C、5D、6.7、若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是()A、树中没有度为2的结点B、树中只有一个根结点C、树中非叶结点均只有左子树D、树中非叶结点均只有右子树8、对广义表L=(a，())执行操作tail(L)的结果是（）A、()B、(())C、aD、(a)9、在图G中求两个结点之间的最短路径可以采用的算法是()A、.迪杰斯特拉（Dijkstra）算法B、克鲁斯卡尔（Kruskal）算法C、普里姆(Prim)算法D、广度优先遍历(BFS)算法10、具有4个顶点的无向图至多应有（）条边。A、6B、12C、16D、2011、在下图中，从顶点1出发进行深度优先遍历可得到的序列是()A、1234567B、1426375C、1425367D、124653712、在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是()A、快速排序B、堆排序C、归并排序D、基数排序13、设有一组关键字(19,14,23,1，6，20,4，27,5，11,10,9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为()A、1B、2C、3D、414、分块查找方法将