吉首大学试题库

《吉首大学试题库》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

吉首大学试题库课程测试试题（卷）以下为教师填写I、命题院（部）：数学与计算机科学学院II、课程名称：数据结构III、测试学期：20-20学年度第学期IV、测试对象：学院专业级班V、问卷页数（A4）：页VI、答卷页数（A4）：页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、一、单选题（每题2分，共20分）1.1.对一个算法的评价，不包括如下（）方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度2.2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（）。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3.3.对线性表，在下列哪种情况下应当采用链表表示？（）A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.4.一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是)

1B.321A.231C.312D.1231.5.AOV网是一种()0A.有向图B.无向图C.无向无环图D.有向无环2.6.采用开放定址法处理散列表的冲突时，其平均查找长度()oA.低于链接法处理冲突B.高于链接法处理冲突C.与链接法处理冲突相同D.高于二分查找3.7.若需要利用形参直接访问实参时，应将形参变量说明为()参数。A.值B.函数C.指针D.引用4.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的()oA.行号B.列号C.元素值D.非零元素个数5.9.快速排序在最坏情况下的时间复杂度为()。A.O(log2n)B.O(nlog2n)C.0(n)D.0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为()。A.O(n)B.O(l)C.O(log2n)D.O(n2)一、二、运算题(每题6分，共24分)1.1.数据结构是指数据及其相互之间的o当结点之间存在M对N(M：N)的联系时，称这种结构为o2.2.队列的插入操作是在队列的进行，删除操作是在队列的进行。3.3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是o4.4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为,在表尾插入元素的时间复杂度为。5.5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7,列下标j从0到3,则二维数组W的数据元素共占用个字节。W中第6行的元素和第4列的元素共占用个字节。若按行顺序存放二维数组W,其起始地址为100,则二维数组元素W[6,3]的起始地址为。6.6.广义表A=(a,(a,b),((a,b),c)),则它的深度为,它的长度为7.7.二叉树是指度为2的树。一棵结点数为N的二叉树，其所有结点的度的总和是。8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个o对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的。9.9.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为个，其中个用于指向

2孩子，个指针是空闲的。1.10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[i]元素的左孩子元素为，右孩子元素为,双亲元素为2.11.在线性表的散列存储中，处理冲突的常用方法有和两种。3.12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用排序。一、三、运算题(每题6分，共24分)1.1.已知一个6x5稀疏矩阵如下所示，-00001-000000-10000000-25000000700试：(1)(1)写出它的三元组线性表；(2)(2)给出三元组线性表的顺序存储表示。2.2.设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。3.3.对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；

31.4.已知一个图的顶点集V和边集E分别为:图6V={1,2,3,4,5,67}；E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。一、四、阅读算法(每题7分，共14分)1.1.intPrime(intn)(inti=l;intx=(int)sqrt(n);while(++iv=x)if(n%i==O)break;if(i>x)return1;elsereturn0;}(1)(1)指出该算法的功能；(2)(2)该算法的时间复杂度是多少？2.2.写出下述算法的功能：voidAJ(adjlistGL,inti,intn)(QueueQ;InitQueue(Q);cout«i«**;visited[ij=true;QInsert(Q,i);while(!QueueEmpty(Q)){intk=QDelete(Q);edgenode*p=GL[k];while(p!=NULL)intj=p->adjvex;if(!visited[jj)cout«j«'visited[j]=true;QInsert(Q,j);Jp=p->next;}|

4]五、五、算法填空(共8分)如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA[],intn,KeyTypeK)(intlow=0;inthigh=n-l;while(low<=high){intmid=；if(K==A[mid].key)returnmid;〃查找成功，返回元素的下标elseif(K<[mid].key);〃在左子表上继续查找else;〃在右子表上继续查找)return-1;〃查找失败，返回-1}六、六、编写算法(共8分)HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode*&HL)参考答案一、一、单选题(每题2分，共20分)l.B2.A3.B4.C5.D6.B7.D8.A9.D10.C二、二、填空题(每空1分，共26分)1.1.联系图(或图结构)2.2.尾首3.3.top==0

54.5.6.4.5.6.O(1)1283344O(n)1082.3.4.四、L2.五、65515132-145-2515637图72.3.BFS：4.(2)2.7.8.9.10.11.12.__、1.(2)7.8.9.10.11.12.1.如图8所示。DFS：①②③④⑤②③④⑤①拓朴排序为：436四、阅读算法有序n-1有序序列2nn-12i+l开放定址法快速后缀表达式（或逆波兰式）n+12i+2（i-l）/2链接法(3分)(1)(b)归并运算题(每题6分，共24分)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))5721（每题7分，共14分）（1）判断n是否是素数（或质数）0（4）功能为：从初始点看出发广度优先搜索由邻接表GL所表示的图。五、(low+high)/2、-、-八、八、算法填空（8分）high=mid-l编写算法（8分）low=mid+lElemTypeDeleFront(LNode*&HL)if(HL==NULL){cerrvv”空表"vvendl;exit(l);)LNode*p=HL;HL=HL->next;ElemTypetemp=p->data;deletep;returntemp;吉首大学试题库课程测试试题（卷）

6以下为教师填写I、命题院（部）：数学与计算机科学学院II、课程名称：数据结构IIL测试学期：20-20学年度第学期IV、测试对象：学院专业级班V、问卷页数（A4）：页VI、答卷页数（A4）：页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）Vllk问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、单选题（每题2分，共20分）1.1.栈和队列的共同特点是（）oA.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.2.用链接方式存储的队列，在进行插入运算时（）.A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.3.以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树4.4.设有一个二维数组A[m][n],假设4。⑼存放位置在644（10）,A[2][2]存放位置在676ao）,每个元素占一个空间，问人⑶⑶阿存放在什么位置？脚注（⑼表示用10进制表示。A.688B.678C.692D.6965.5.树最适合用来表示（）oA.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.6.二叉树的第k层的结点数最多为（）.

7A.2k-lB.2K+1C.2K-1D.2k'11.7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[l]中，现进行二分查找，则查找A[3]的比较序列的下标依次为()A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,32.8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A.0(1)B.O(n)C.O(log2n)D.O(n2)3.9.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有()个，A.1B.2C.3D.41.10..设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8二、二、填空题(每空1分，共26分)1.1.通常从四个方面评价算法的质量：、、和O2.2.一个算法的时间复杂度为(7+〃210g2〃+14〃)/〃2,其数量级表示为3.3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中所含的结点数为个，树的深度为,树的度为4.4.后缀算式923+-102/-的值为o中缀算式(3+4X)-2Y/3对应的后缀算式为。5.5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有个指针域，其中有个指针域是存放了地址，有个指针是空指针。6.6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有个和个。7.7.AOV网是一种的图。8.8.在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。9.9.假定一个线性表为(12,23,74,55,63,40),若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为和

81.10.向一棵B一树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度o2.11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为,整个堆排序过程的时间复杂度为。3.12.在快速排序、堆排序、归并排序中，排序是稳定的。二、三、运算题(每题6分，共24分)1.1.在如下数组A中链接存储了一个线性表，表头指针为A[0].next,试写出该线性表。2.3.2.请画出图10的邻接矩阵和邻接表。3.已知一个图的顶点集V和边集E分别为:V={123,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。四、四、阅读算法(每题7分，共14分)1.1.LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L->next；p=L；SI：S2：while(p->next)p=p->next；p->next=q；q->next=NULL；}returnL；)请回答下列问题：(1)说明语句SI的功能；(2)说明语句组S2的功能；(3)设链表表示的线性表为(ai,a2,…,aQ，写出算法执行后的返回值所表示的线性表。2.2.voidABC(BTNode*BT)

9ifBT{ABC(BT->left);ABC(BT->right);cout«BT->data«'})该算法的功能是：四、五、算法填空(共8分)二叉搜索树的查找——递归算法：boolFind(BTreeNode*BST,ElemType&item)(if(BST==NULL)returnfalse;〃查找失败else{if(item==BST->data){item=BST->data;〃查找成功return;}elseif(itemdata)returnFind(,item);elsereturnFind(,item);}//if)五、六、编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)参考答案l.A2.D3.D4.C单选题（每题2分，共20分）5.C6.D7.D8.C9.D10.A二、二、填空题(每空1分，共26分)1.1.正确性易读性强壮性高效率2.2.O(n)3.3.9334.4.-134X*+2Y*3/-5.5.2nn-1n+16.6.e2e7.7.有向无回路8.8.n(n-l)/2n(n-l)9.9.(12,40)()(74)(23,55,63)10.10.增加111.11.O(log2n)O(nlog2n)

1010.12.归并三、运算题(每题6分，共24分)1.1.线性表为：(78,50,40,60,34,90)0111011010111011101012.2.邻接矩阵：L0111邻接表如图11所示：图113.3.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.4,见图12四、四、阅读算法(每题7分，共14分)1.1.(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点(3)返回的线性表为(a2,a3,—,an,ai)2.2,递归地后序遍历链式存储的二叉树。五、五、算法填空(每空2分，共8分)trueBST->leftBST->right六、六、编写算法(8分)intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;}//CountX吉首大学试题库

11课程测试试题（卷）以下为教师填写I、命题院（部）：数学与计算机科学学院II、课程名称：数据结构IIL测试学期：20-20学年度第学期IV、测试对象：学院专业级班V、问卷页数（A4）：页VI、答卷页数（A4）：页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）Vllk问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、一、单选题（每小题2分，共8分）1、1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）oAnBn/2C（n+l）/2D（n-l）/22、2、在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则执行（）。As->link=p->link;p_*link=s;Bp->link=s;s-*link=q;Cp-*link=s_*link;s-*-link=p;Dq-*link=s;s-*link=p;3、3、栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置4、4、由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D53二、填空题（每空1分，共32分）1、1、数据的逻辑结构被分为、、和四种。2、2、一种抽象数据类型包括和两个部分。3、3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next,则该线性表为o

12a012345678605642387425data4376201next4、4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为和o5、5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的,该循环队列的最大长度为o6、6、当堆栈采用顺序存储结构时，栈顶元素的值可用表示；当堆栈采用链接存储结构时，栈顶元素的值可用表示。7、7、一棵高度为5的二叉树中最少含有个结点，最多含有个结点；一棵高度为5的理想平衡树中，最少含有个结点，最多含有个结点。8、8、在图的邻接表中，每个结点被称为,通常它包含三个域：一是；二是；三是O9、9、在一个索引文件的索引表中，每个索引项包含对应记录的和两项数据。10、10、假定一棵树的广义表表示为A（B（C,D（E,F,G）,H（I，J））），则树中所含的结点数为个，树的深度为树的度为结点H的双亲结点为孩子结点为11、11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为整个堆排序过程的时间复杂度为o12、12、在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于个，则必须把它分裂为个结点。二、运算题（每小题6分，共24分）1、1、已知一组记录的排序码为（46,79,56,38,40,80,95,24）,写出对其进行快速排序的每一次划分结果。2、2、一个线性表为B=(12,23,45,57,20,03,78,31,15,36),设散列表为HT[0..12],散列函数为H(key)=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。

134、4、已知一个图的顶点集V各边集G如下：V={0,1,2,3,4,5,6,7,8,9}；E={(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V。出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时二、四、阅读算法，回答问题(每小题8分，共16分)1、假定从键盘上输入一批整数，依次为：786345309134-1,请写出输出结果。#include#includeconsstintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;];#include"stack,h”Voidmain()stacka;initstack(a);intx;cin»x;while(x!=-1){push(a,x);cin»x;}while(!stackempty(a))cout«pop(a)vv"”;cout«endl;)该算法的输出结果为：

142、阅读以下二叉树操作算法，指出该算法的功能。TemplatevoidBinTree：：unknown(BinTreeNode*t){BinTreeNodeleftchild;p-leftchild=p->rightchild;pfrightchild=temp;unknown(p->leftchild);undnown(pfrightchild);})该算法的功能是：五、五、算法填空，在画有横线的地方填写合适的内容(10分)对顺序存储的有序表进行二分查找的递归算法。intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK)(if(low<=high)intmid=1if(K==A[midi.key)returnmid;elseif(K

15数据结构试题(答案)一、单选题(每小题2分，共8分)题号1234答案CDAB二、填空题(每空1分，共32分)1：集合、线性、树、图：2：数据描述、操作声名；3：(38,56,25,60,42,74)；4：HL-next=NULL；HL=HL-next：5：前一个位置；n-1；6：S.stack[S.top];HS—data;7：5318：边结点、邻接点域、权域、链域：9：索引值域、开始位置域；10：10、3、3,B、I和J；11：0(login),O(nlog2n);12：m、m-1三、运算题(每小题6分，共24分)划分次序划分结果第一次[382440]46[56809579]第二次24[3840]46[56809579]第三次24384046[56809579]第四次2438404656[809579]

16第五次243840465679[8095]第六次24384046567980952、012345678910111278150357452031233612查找成功的平均查找长度：ASLSucc=14/10=1.43、此二叉树的后序遍历结果是：EDCBIHJGFA4、图深度优先序列广度优先序列邻接矩阵表示时0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9邻接表表示时0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5四、阅读算法，回答问题(每小题8分，共16分)1、1、该算法的输入结果是：3491304563782、2,该算法的功能是：交换二叉树的左右子树的递归算法。五、算法填空，在画有横线的地方填写合适的内容(10分)是是是是1234(low+high)/2;Binsch(A,low,mid-1,K);Binsch(A,mid+l,high,K);-1:六、编写算法(10分)根据编程情况，酌情给分。(Lnode*P=HL;HL=NULL;While(p!=null)(Lnode*q=p;P=pfnext;q-*next=HL;HL=q;吉首大学试题库课程测试试题(卷)以下为教师填写I、命题院(部)：数学与计算机科学学院IK课程名称：数据结构

17IIL测试学期：20—20学年度第学期IV、测试对象：学院专业级班V、问卷页数（A4）：页VI、答卷页数（A4）：页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIIL问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）第一部分选择题（30分）一、一、项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.算法指的是（）A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（）A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）A.0（1）B.O（n）C.O（m）D.O（m+n）4.由两个栈共享一个向量空间的好处是：（）A.减少存取时间，降低下溢发生的机率B.节省存储空间，降低上溢发生的机率C.减少存取时间，降低上溢发生的机率D.节省存储空间，降低下溢发生的机率5.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A.front=front+1B.front=（front+1）%（m-l）

18C.front=（front-l）%m5.如下陈述中正确的是（）A.串是一种特殊的线性表C.串中元素只能是字母D.front=（front+l）%mB.串的长度必须大于零D.空串就是空白串6.若目标串的长度为n,模式串的长度为[n/3],则执行模式匹配算法时，在最A.0(3)B.0(n)C.0(n2)D.O(n3)8.一个非空广义表的表头（A.不可能是子表B.只能是子表坏情况忖的时间复杂度是（）C.品能是原子D.&以是青表或原子9.假千里磷翅三元组表表示稀疏知族，》我群甲亍表AG洲3公％5B.-900400）出由浙海琉矩际是（）00000）上§@机|0530040j）0000j[030010.在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（）A.4B.5C.6D.711.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A.eB.2eC.n2—eD.n2—2e12.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点Vi相关的所有弧的时间复杂度是（）A.0（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.关键字项的长度不固定第二部分非选择题（共70分）二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分,

19共20分)不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。10.数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关,是独立于计算机的。11.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=。12.栈顶的位置是随着操作而变化的。13.在串S="structure”中，以t为首字符的子串有个。14.假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B[0]存储矩阵中第1个元素aij”则B[31]中存放的元素是o15.已知一棵完全二叉树中共有768结点，则该树中共有个叶子结点。Q22.已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为=X®?©®©23.在单链表上难以实现的排序方法有和o24.在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为。25.多重表文件和倒排文件都归属于文件。三、解答题(本大题共4小题，每小题5分，共20分)26.画出下列广义表的共享结构图形表示P=(((z),(x,y)),((x,y),x),(z))27.请画出与下列二叉树对应的森林。。ioo11OO1o顶点集为｛a,b,c,d,e),其邻接矩阵如下所示OOO1128.已印《5个无1照生1O11o(1)画出该图的图形；(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。29.已知一个散列表如下图所示:35203348590123456789101112

20其散列函数为h(key)=key%13,处理冲突的方法为双重散列法，探查序列为:hj=(h(key)+i*hl(key))%mi=0,1,…,m—1其中h1(key)=key%11+1回答下列问题：(1)对表中关键字35,20,33和48进行查找时，所需进行的比较次数各为多少？(2)该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题(本大题共4个题，海小题5分，共20分)30.下列算法的功能是比较两j链哪以小，其返回值为：comstr(si,S2)=」'Is,>请在空白处填入适当的内容。intcomstr(LinkStringsi,LinkStrings2){//si和s2为两个链用的头指针while(sl&&s2){if(sl—>datedate)retum_1；if(sl—>date>s2—>date)returnl；①；②；}if(③)return—1；if(@)return1；⑤；)①②③④⑤31.阅读下面的算法LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L—>next；p=L；SI：while(p->next)p=p—>next；

21S2：p->next=q；q—>next=NULL；}returnL；}请回答下列问题：(1)说明语句SI的功能；(2)说明语句组S2的功能；表示的线性表。(3)设链表表示的线性表为(ai,a2,-,an)，写出算法执行后的返回值所32.假设两个队列共享一个循环向量空间(参见右下图)，其类型Queue2定义如下：typedefstruct{DateTypedatafMaxSize]；intfront[2],rear[2]；}Queue2；对于i=0或1,front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。intEnQueue(Queue2*Q,inti,DateTypex){〃若第i个队列不满，则元素x入队列，并返回1；否则返回0if(il)return0；if(Q—>rear[i]==Q—>frontF(D1returnO；Q->data[®]=x；Q—>rear[i]=[③1;return1；)①②③33.已知二叉树的存储结构为二叉链表，阅读下面算法。typedefstructnode{DateTypedata；Structnode*next；JListNode；typedefListNode*LinkList；

22LinkListLeafhead=NULL；VoidInorder(BinTreeT)LinkLists；If(T){Inorder(T->lchild)；If((!T->lchild)&&(!T->rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s—>data=T—>data；s->next=Leafhead；Leafhead=s；}Inorder(T->rchild)；)}对于如下所示的二叉树(1)画出执行上述算法后所建立的结构;(2)说明该算法的功能。五、算法设计题(本题共10分)34.阅读下列函数arrange()intarrange(inta[],intl,inth,intx){//l和h分别为数据区的下界和上界inti=l;j=h；while(i=x)j—：while(i=x)i++；if(i

23if(a[i]

24（1）写出该函数的功能；（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。、、1.D单项选择题（本大题共15小题，每小题2分，共30分）2.B3.C4.B5.D6.A7.C8,D9,A10.C11.D12.C13.D14.C15.B数据结构试题参考答案二、填空题（本大题共10小题，每小题2分,16.存储（或存储结构）18.进栈和退栈23.快速排序、堆排序、希尔排序24.2三、解答题（本大题共4小题，每小题5分，26.图1图227.28.该图的图形为：共20分）17.p->next->next19.1220.a4.821.38422.abefcdg25.多关键字共20分）公尔卜zxy

25深度优先遍历序列为：abdce广度优先遍历序列为：abedc29.(1)对关键字35、20、33和48进行查找的比较次数为3、2、1、1；a0i-3+2+1+1+2_9(2)平均查找长度5=5四、算法阅读题(本大题共4小题，每小题5分，共20分)30.①S1=S1—>next②s2=s2—>next③s2(或s2!=NULL或s2&&!sl)④si(或si!=NULL或si&&!s2)©return031.(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点(3)返回的线性表为(a2,a3,--,an,ai)32.①(i+l)%2(或1-i)②Q—>rear[i]③(Q—>rear[i]+)%Maxsize33.(l)LeaflieadgF►H—GDA(2)中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表(或按二叉树中叶子结点数据自右至左链接成一个链表)。五、算法设计题(本题共10分)34.(1)该函数的功能是：调整整数数组a口中的元素并返回分界值i,使所有Vx的元素均落在上，使所有2x的元素均落在a[i+l..h]±o(2)intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arrange(b,0,n-1,0)；p=arrange(b,0,n—1,1)；

26q=arrange(b,p+l,n—1,1)；q=arrange(b,0,p,0)；returnq-p；returnp-q；吉首大学试题库课程测试试题（卷）以下为教师填写1、命题院（部）：数学与计算机科学学院IL课程名称：数据结构III、测试学期：20-20学年度第学期IV、测试对象：学院专业级班V、问卷页数（A4）：页VI、答卷页数（A4）：页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIIL问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、选择题（20分）1.组成数据的基本单位是（）。（A）数据项（B）数据类型（C）数据元素（D）数据变量2.设数据结构A=（D,R）,其中D={1,2,3,4）,R={r},r={,<2,3>,<3,4>,<4,1>},则数据结构A是（）o（A）线性结构（B）树型结构（C）图型结构（D）集合3.数组的逻辑结构不同于下列（）的逻辑结构。（A）线性表（B）栈©队列（D）树4.二叉树中第i（逛1）层上的结点数最多有（）个。（A）2i（B）2j（C）2i-1（D）2i-l

273.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为（）=(A)p->next=p->next->next(B)p=p->next(C)p=p->next->next(D)p->next=p6.设栈S和队列Q的初始状态为空，元素El、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是()o(A)6(B)4(C)3(D)27.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为()„(A)100(B)40(C)55(D)808.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为()o(A)3(B)4(C)5(D)19.根据二叉树的定义可知二叉树共有()种不同的形态。(A)4(B)5(C)6(D)710.10.设有以下四种排序方法，则()的空间复杂度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序二、填空题(30分)1.1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F=；o2.2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为，在链式存储结构上实现顺序查找的平均时间复杂度为o3.3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有个指针域，个空指针域。4.4.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为5.5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有个表头结点和个表结点。6.6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m,则e和m有关系。7.7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为。8.8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是,编号为8的左孩子结点的编号是o

281.9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。intindex(chars[],chart[]){i=j=O；while(inext=p->next;s->next=s

291.5.n,2e2.6.m=2e3.7.CBA4.8.4,165.9.i-j+1,06.10.n-1%九一>8三、应用题；1.1.链式存储结构略，前序ABDEC,中序DBEAC,后序的2.2.哈夫曼树略，WPL=78^->25->323.3.(18,5,16,19,20,23),2(5,31642K23)A->684.4.线性探测：A8A1025322768链地址法：h6->215.5.深度：125364,广度：123456,最小生成树T的边集为E={(1,4),(1,3),(3,5),(5,6),(5,6)}四、算法设计题1.1.设计判断单链表中结点是否关于中心对称算法。typedefstruct{ints[100J;inttop;}sqstack;intlklistsymmetry(lklist*head)(sqstackstack;stack.top=-1;Iklist*p;for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;}for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-l;elsereturn(O);return(l);)2.2.设计在链式存储结构上建立一棵二叉树的算法。typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*&bt)charch;scanf("%c",&ch);if(ch=='#'){bt=O;return;}bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchiId);createbitree(bt->rchi1d);}3.3.设计判断一棵二叉树是否是二叉排序树的算法。intminnum=-32768,flag=l;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt)

30{if(bt!=O){inorder(bt->Ichild);if(minnum>bt->key)flag=O;minnum=bt->key;inorder(bt->rchild);})

31一、选择题(24分)1.下面关于线性表的叙述错误的是()o(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现2.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该哈夫曼树中总共有()个空指针域。(A)2m-1(B)2m(C)2m+l(D)4m3.设顺序循环队列Q[0：M-l]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M4.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()«(A)BADC(B)BCDA(C)CDAB(D)CBDA5.设某完全无向图中有n个顶点，则该完全无向图中有()条边。(A)n(n-l)/2(B)n(n-l)(C)n和.2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-l)printf("overflow’')；else{;;})3.中序遍历二叉排序树所得到的序列是序列(填有序或无序)。4.快速排序的最坏时间复杂度为,平均时间复杂度为。5.设某棵二叉树中度数为0的结点数为No,度数为1的结点数为N1,则该二叉树中度数为2的结点数为；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有个空指针域。6.设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为＜1,则€=。7.设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为。(D)n2-l6.设某棵二叉树中有2000个结点，则该二叉树的最小高度为().(A)9(B)10(C)11(D)127.设某有向图中有n个顶点，则该有向图对应的邻接表中有()个表头结点。(A)n-1(B)n(C)n+1(D)2n-l8.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为().(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8二、填空题(24分)1.1.为了能有效地应用HASH查找技术，必须解决的两个问题是

32v,->3->2->4v2->1->3v3->1->4->28.8.设某无向图G的邻接表为匕->1->3，则从顶点V1开始的深度优先遍历序列为；广度优先遍历序列为o三、应用题(36分)1.1.设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2.2.设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和riink)<>3.3.设一组有序的记录关键字序列为(13,18,24,35,47,50,法用二分查找，要求计算出查找关健字62时的比较次数并计算出查找成功时的平均查找长度。4.4.设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。5.5.设有无向图G(如右图所示)，要求给出用普里姆算法构造最小生成树所走过的边的集合。6.6.设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。62,83,90),四、算法设计题(16分)1.1.设有一组初始记录关键字序列(K|,&K”)，要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K，右半部分的每个关键字均大于等于K。2.2.设有两个集合A和集合B,要求设计生成集合C=AC)B的算法，其中集合A、B和C用链式存储结构表示。

33一、选择题l.D2.B3.C4.A5.A6.C7.B8.C二、填空题1.1.构造一个好的HASH函数，确定解决冲突的方法2.2.stack.top++,stack.s[stack.top]=x3.3.有序4.4.O(n2),O(nlog2n)5.5.N0-h2N()+N|6.6.d/27.7.(31,38,54,56,75,80,55,63)8.8.(1,3,4,2),(1,3,2,4)三、应用题1.1.(22,40,45,48,80,78),(40,45,48,80,22,78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25794.4.树的链式存储结构略，二叉树略5.5.E={(1,3),(1,2),(3,5),(5,6),(6,4)}6.6.略四、算法设计题1.1.设有一组初始记录关键字序列(K|,K2,K„),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Kj,右半部分的每个关键字均大于等于Kiovoidquickpass(intr[],ints,intt)(inti=s,j=t,x=r[s];while(ix)j=j-l;if(inext){fbr(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=O){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}

34一、选择题(30分)1.设某数据结构的二元组形式表示为A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},匚{<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03.07>,<03,08>,<03,09>},则数据结构A是()。(A)线性结构(B)树型结构(C)物理结构(D)图型结构2.下面程序的时间复杂为()for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j-H-)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)0(n3)(D)O(nS3.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为().(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next：free(q)；(C)q=p->next；p->next=q->next；free(q)；(D)q=p->next；p->data=q->data：free(q)：4.设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。(A)1(B)n(C)nlog2n(D)n25.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为()«(A)10,15,14,18.20,36,40,21(B)10,15,14,18,20,40,36,21(C)10,15,14,20,18,40,36,21(D)15,10,14,18,20,36,40,216.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为()。(A)O(l)(B)O(log2n)(C)(D)O(n2)7.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为()«(A)n,e(B)e,n(C)2n,e(D)n,2e8.设某强连通图中有n个顶点，则该强连通图中至少有()条边。(A)n(n-l)(B)n+1(C)n(D)n(n+l)9.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列()方法可以达到此目的。(A)快速排序(B)堆排序(C)归并排序(D)插入排序10.下列四种排序中()的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序二、填空殖(48分，其中最后两小题各6分)1.1.数据的物理结构主要包括和两种情况。2.2.设一棵完全二叉树中有500个结点，则该二叉树的深度为；若用二叉链表作为该完全二叉树的存储结构，则共有个空指针域。3.3.设输入序列为1、2、3,则经过栈的作用后可以得到种不同的输出序歹人4.4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的,第i列上所有元素之和等于顶点i的。5.5.设哈夫曼树中共有n个结点，则该哈夫曼树中有个度数为1的结点。6.6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为O7.7.遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。

351.8.设查找表中有100个元素，如果用二分法查找方法查找数据元素X,则最多需要比较次就可以断定数据元素X是否在查找表中。2.9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为o3.10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为,右孩子结点的编号为。4.11.设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字72为基准的一趟快速排序结果为=5.12.设有向图G中有向边的集合£={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>),则该图的一种拓扑序列为.6.13.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[]jntk)(inti,j;j=i=k%p;while(hashtab!e|j].key!=k&&hashtable[j].flag!=O){j=()%m;if(i=j)retum(-l);}if()retum(j);elseretum(-l);)7.14.下列算法实现在二叉排序树上查找关键值k,请在下划线处填上正确的语句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;)bitree;bitree*bstsearch(bitree*t,intk){if(t==0)retum(0);elsewhile(t!=0)if(t->key==k);elseif(t->key>k)t=t->lchild;else;}三、算法设计题(22分)1.1.设计在单链表中删除值相同的多余结点的算法。2.2.设计一个求结点x在二叉树中的双亲结点算法。

36一、选择题l.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第3小题分析：首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中，最后删除结点B。第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n),二、填空题1.1.顺序存储结构、链式存储结构2.2.9,5013.3.54.4.出度，入度5.5.06.6.e=d7.7.中序8.8.79.9.0(1)10.10.i/2,2i+l11.11.(5,16,71,23,72,94,73)12.12.(1,4,3,2)13.13.j+1,hashtable|j].key==k14.14.retum(t),t=t->rchild第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度l+log2no三、算法设计题1.1.设计在单链表中删除值相同的多余结点的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(Iklist*&head){Iklist*p,*q,*s;for(p=head;p!=0;p=p->next)(fbr(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}2.2.设计一个求结点x在二叉树中的双亲结点算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=O,f=O,flag=O;voidpreorder(bitree*bt,charx)(if(bt!=O&&flag==O)if(bt->data=x){flag=l;return;}else{r=(r+l)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x)；})voidparent(bitree*bt,charx)

37inti;preorder(bt,x)；for(i=f+l;i<=r;i++)if(q[i]->lchild->data==xIIq[i]->rchild->data)break;if(flag==O)printf(Mnotfoundx

38M);elseif(i<=r)printf(,,%c,\bt->data);elseprintf(Hnotparent*');

39数据结构试卷(四)一、选择题(30分)1.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()o(A)O(n)(B)O(nlog2n)(C)O(l)(D)O(n2)2.设一棵二叉树的深度为k,则该二叉树中最多有()个结点。(A)2k-1(B)2k(C)211-1(D)2k-l3.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为()o(A)n(B)e(C)2n(D)2e4.在二叉排序树中插入一个结点的时间复杂度为()。(A)O(l)(B)0(n)(C)O(log2n)(D)O(n2)5.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有()条有向边。(A)n(B)n-l(C)m(D)m-16.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。(A)3(B)4(C)5(D)87.设用链表作为栈的存储结构则退栈操作().(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)对栈不作任何判别8.下列四种排序中()的空间复杂度最大。(A)快速排序(B)冒泡排序(C)希尔排序(D)堆9.设某二叉树中度数为0的结点数为N(),度数为1的结点数为Ni，度数为2的结点数为N2,则下列等式成立的是().(A)No=N|+l(B)N()=Ni+N,(C)No=N2+l(D)No=2N,+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过()o(A)log2n+l(B)log2n-l(C)log2n(D)log2(n+l)二、填空题(42分)1.1.设有n个无序的记录关键字，则直接插入排序的时间复杂度为,快速排序的平均时间复杂度为。2.2.设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为(设结点中的两个指针域分另I］为Hink和rlink)。3.3.根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为。4.4.深度为k的完全二叉树中最少有个结点。5.5.设初始记录关键字序列为(跖，冷，…，K„),则用筛选法思想建堆必须从第个元素开始进行筛选。6.6.设哈夫曼树中共有99个结点，则该树中有个叶子结点：若采用二叉链表作为存储结构，则该树中有个空指针域。7.7.设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储个队列元素；当前实际存储个队列元素(设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置)。8.8.设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中个数据元素；删除第i个位置上的数据元素需要移动表中个元素。9.9.设一组初始记录关健字序列为(20,18,22,16,30,19),则以20为中轴的一趟快速排序结果为.10.10.设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序列建成的初始堆为o11.11.设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是。

401.12.设无向图对应的邻接矩阵为A,则A中第i上非。元素的个数第i列上非0元素的个数(填等于，大于或小于)。2.13.设前序遍历某二叉树的序列为ABCD,中序遍历该二叉树的序列为BADC,则后序遍历该二叉树的序列为»3.14.设散列函数H(k)=kmodp,解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。typedefstructnode{intkey;structnode*next;}Iklist;voidcreatelkhash(lklist*hashtable[])(inti,k;Iklist*s;fbr(i=0;ikey=a[i];k=a[i]%p;s->next=hashtable[k];;三、算法设计题(28分)1.1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。2.2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。3.3.在链式存储结构上建立一棵二叉排序树。

41一、选择题1.C2.D3.D4.B5.C6.A7.B8.A9.C10.A二、填空题1.1.O(n2),O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink3.3.34.4.2kd5.5.n/26.6.50,517.7.m-1,(R-F+M)%M8.8.n+l-i,n-i9.9.(19,18,16,20,30,22)10.10.(16,18,19,20,32,22)11.11.A[i]U]=l12.12.等于13.13.BDCA14.14.hashtable[i]=0,hashtable[k]=s三、算法设计题1.1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){Iklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head)(head=p->next;p->next=0;if(p->data>='A'&&p->data<=,Z,){p->next=ha;ha=p;}elseif(p->data>=,0,&&p->data<=,9,){p->next=hb;hb=p;}else{p->next=hc;hc=p;})}2.2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。typedefstructnode{intdata;structnode*lchild,*rchild;)bitree;voidswapbitree(bitree*bt)(bitree*p;if(bt==O)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}3.3.在链式存储结构上建立一棵二叉排序树。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;Jbitree;voidbstinsert(bitree*&bt,intkey)(if(bt==O){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->IchiId=bt->rchi1d=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}

42voidcreatebsttree(bitree*&bt)inti;for(i=l;i<=n;i++)bstinsert(bt,random(100));

43数据结构试卷(五)一、选择题(30分)1.数据的最小单位是()«(A)数据项(B)数据类型(C)数据元素(D)数据变量2.设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),则以增量d=4的一趟希尔排序结束后前4条记录关键字为()o(A)40,50,20,95(B)15,40,60,20(C)15,20,40,45(D)45,40,15,203.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为()o(A)15,25,35,50,20,40,80,85,36,70(B)15,25,35,50,80,20,85,40,70,36(C)15,25,35,50,80,85,20,36,40,70(D)15,25,35,50,80,20,36,40,70,854.函数substr("DATASTRUCTURE”，5,9)的返回值为().(A)“STRUCTURE”(B)"DATA''(C)“ASTRUCTUR”(D)"DATASTRUCTURE”5.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为().(A)O(log2n)(B)0(1)(C)0(n2)(D)O(n)6.设一棵m叉树中度数为0的结点数为No,度数为1的结点数为Ni度数为m的结点数为Nm,则No=()»(A)N|+N2++Nm(B)I+N2+2N3+3N4++(m-l)Nm(C)N2+2N3+3N4++(m-l)Nm(D)2N|+3N2++(m+l)Nm7.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较()次。(A)25(B)10(C)7(D)18.设连通图G中的边集色{9,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为()»(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb9.设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是().(A)n-i(B)n-l-i(C)n+l-i(D)不能确定10设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45为基准而得到一趟快速排序的结果是().(A)40,42,45,55,80,83(B)42,40,45,80,85,88(C)42,40,45,55,80,85(D)42,40,45,85,55,80二、填空题(共30分)1.1.设有一个顺序共享栈S[0：n-l],其中第一个栈项指针topi的初值为-1,第二个栈顶指针toP2的初值为n,则判断共享栈满的条件是o2.2.在图的邻接表中用顺序存储结构存储表头结点的优点是。3.3.设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在n(n+l)个连续的存储单元中，则与A[0][0]之间有个数据元素。4.4.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为表。

441.5.设•棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF,则该二叉树的前序遍历序列为,中序遍历序列为,后序遍历序列为2.6.设一棵完全二叉树有128个结点，则该完全二叉树的深度为,有个叶子结点。3.7.一而向图G的存话结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的,第i列中所有非零元素个数之和等于顶点i的.4.8.设一组初始记录关键字序列(k|,k2,%)是堆，则对i=l,2n/2而言满足的条件为.5.9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(intr[n]){for(i=l;i<=n-l;i++){fbr(exchange=O,j=O;j<;j++)if(r[j]>r[j+1]){temp=r|j+l];;r[j]=temp;exchange=1;}if(exchange==O)return：})6.10.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk)(intlow=0,mid,high=n-l;while(low<=high).)high=mid-l;elselow=mid+1;if(r[mid].key==k)return(mid+l);elseif(.)return(O);三、应用题(24分)1.2.3.4.1.设某棵二叉树的中序遍历序列为DBEAC,前序遍历序列为ABDEC,要求给出该二义树的的后序遍历序列。2.设无向图G(如右图所示)，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。3.设一组初始记录关键字序列为(15,17,18,22,35,51,60),要求计算出成功查找时的平均查找长度。4.设散列表的长度为8,散列函数H(k)=kmod7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。四、算法设计题(16分)1.1.设计判断两个二叉树是否相同的算法。2.2.设计两个有序单链表的合并排序算法。一、选择题1.A2.B6.B7.B数据结构试卷(五)参考答案3.A4.A5.D8.B9.C10.C二、填空题1.1.topl+l=top22.2.可以随机访问到任一个顶点的简单链表3.3.i(i+l)/2+j-l

451.4.FILO,FIFO2.5.ABDECF,DBEAFC,DEBFCA3.6.8,644.7.出度，入度5.8.ki<=k2i&&kj<=k2i+i6.9.n-i,r[j4-l]=rg]7.10.mid=(low+high)/2,r[mid].key>k三、应用题1.1.DEBCA2.2.E={(1,5),(5,2),(5,3),(3,4)},W=IO3.3.ASL=(1*1+2*2+3*4)77=17/74.4.ASLl=7/6,ASL2=4/3四、算法设计题1.1.设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*btl,bitree*bt2){,if(btl=O&&bt2==0)return(l);elseif(btl==OIIbt2==0llbtl->data!=bt2->data)return(O);elseretum(judgebitree(btl->lchild,bt2->lchild)*judgebitree(btl->rchild,bt2->rchild));2.2.设计两个有序单链表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc)(Iklist*s=hc=O;while(ha!=0&&hb!=O)if(ha->datadata){if(s=O)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s=O)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==O)s->next=hb;elses->next=ha;

46一、选择题(30分)1.设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度之和为()o(A)20(B)30(C)40(D)452.执行一趟快速排序能够得到的序列是()<,(A)[41,12,34,45,27]55[72,63](B)[45,34,12,41]55[72,63,27](C)[63,12,34,45,27]55[41,72](D)[12,27,45,41]55[34,63,72]3.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是()。(A)head==0(B)head->next==0(C)head->next=head(D)head!=04.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是()。(A)堆排序(B)冒泡排序(C)希尔排序(D)快速排序5.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是()。(A)空或只有一个结点(B)高度等于其结点数(C)任一结点无左孩子(D)任一结点无右孩子6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是().(A)堆排序(B)冒泡排序(C)快速排序(D)希尔排序7.设某棵三叉树中有40个结点，则该三叉树的最小高度为()«(A)3(B)4(C)5(D)68.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。(A)O(n)(B)0(n2)(C)O(nl/2)(D)O(log2n)9.二路归并排序的时间复杂度为()。(A)O(n)(B)0(n2)(C)O(nlog2n)(D)O(log2n)10.深度为k的完全二叉树中最少有()个结点。(A)2kl-l(B)2k-'(C)2k*'+1(D)2k-l11.设指针变量front表示链式队列的队头指针，指针变量但ar表示链式队列的队尾指针，指针变量s指向将要入队列的结点X,则入队列的操作序列为()o(A)front->next=s；front=s；(B)s->next=rear；rear=s；(C)rear->next=s；rear=s；(D)s->next=front；front=s；12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为()o(A)O(n+e)(B)0(n2)(C)0(ne)(D)O(n3)13.设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。(A)99(B)100(C)101(D)10214.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()«(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(log2n)15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为()。(A)第i行非0元素的个数之和(B)第i列非0元素的个数之和(C)第i行0元素的个数之和(D)第i列0元素的个数之和二、判断题(2。分)1.调用一次深度优先遍历可以访问到图中的所有顶点。()2.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。()3.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。()4.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()5.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。()6.层次遍历初始堆可以得到一个有序的序列。()7.设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。()8.线性表的顺序存储结构比链式存储结构更好。()

471.中序遍历二叉排序树可以得到一个有序的序列。（）2.快速排序是排序算法中平均性能最好的一种排序。（）三、填空题（30分）1.for（i=l,t=Ls=0；i<=n；i++）{t=t*i；s=s+t；}的时间复杂度为。2.设指针变量p指向单链表中结点A,指针变量s指向被插入的新结点X,则进行插入操作的语句序列为（设结点的指针域为next）。3.设有向图G的二元组形式表示为G=（D,R）,D={1,2,3,4,5},R={r},匚{vl,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},则给出该图的一种拓扑排序序列。4.设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是。5.设二叉树中度数为0的结点数为50,搬为1的结点数为30,则该二叉树中总共有个结点数。6.设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为7.设二叉树中结点的两个指针域分别为khild和rchild,则判断指针变量p所指向的结点为叶子结点的条件是。8.简单选择排序和直接插入排序算法的平均时间复杂度为。9.快速排序算法的空间复杂度平均情况下为,最坏的情况下为o10.散列表中解决冲突的两种方法是和。四、算法设计题（20分）1..1.设计在顺序有序表中实现二分查找的算法。2.2.设计判断二叉树是否为二叉排序树的算法。3.3.在链式存储结构上设计直接插入排序算法

48一、选择题1.D2.A6.D7.B11.C12.A13.3.A8.AB14.D15.4.A5.D9.C10.BB二、判断题1.错2.对6.错7.对3.对4.对5.错8.错9.对10.对三、填空题1.1.O(n)2.2.s->next=p->next;p->next=s3.3.(1,3,2,4,5)4.4.n-15.5.1296.6.F==R7.7.p->lchi1d==0&&p->rchild==08.8.O(n2)9.9.O(nlog2n),O(n)10.10.开放定址法，链地址法四、算法设计题1.1.设计在顺序有序表中实现二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk)(intlow=0,mid,high=n-l;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+l);elseif(r[mid].key>k)high=mid-l;elselow=mid+l;}return(O);)2.2.设计判断二叉树是否为二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=O){inorder(bt->lchiId);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);))3.3.在链式存储结构上设计直接插入排序算法voidstraightinsertsort(lklist*&head)(Iklist*s,*p,*q;intt;if(head==0IIhead->next=O)return;elsefbr(q=head,p=head->next;p!=0;p=q->next)(for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;1f(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}

49数据结构试卷(七)一、选择题(30分)1.设某无向图有n个顶点，则该无向图的邻接表中有()个表头结点。(A)2n(B)n(C)n/2(D)n(n-l)2.设无向图G中有n个顶点，则该无向图的最小生成树上有()条边。(A)n(B)n-1(C)2n(D)2n-l3.设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字45为基准而得到的一趟快速排序结果是()。(A)40,42,60,55,80,85(B)42,45,55,60,85,80(C)42,40,55,60,80,85(D)42,40,60,85,55,804.()二叉排序树可以得到一个从小到大的有序序列。(A)先序遍历(B)中序遍历(C)后序遍历(D)层次遍历5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为().(A)2i+l(B)2i(C)i/2(D)2i-l6.程序段s=i=0；do{i=i+l；s=s+i；)while(i<=n)；的时间复杂度为()»(A)O(n)(B)O(nlog,n)(C)0(n2)(D)O(n3/2)7.设带有头结点的单向循环链表的头指针变量为head,则其判空条件是()。(A)head==0(B)head->next=O(C)head->next==head(D)head!=08.设某棵二叉树的高度为10,则该二叉树上叶子结点最多有()o(A)20(B)256(C)512(D)10249.设一组初始记录关键季序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为()。(A)l(B)2(C)3(D)410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为().(A)top=top+l;(B)top=top-l;(C)top->next=top;(D)top=top->next;二、判断题(2。分)1.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。()2.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。()3.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为OQogzn)。()4.完全二叉树中的叶子结点只可能在最后两层中出现。()5.哈夫曼树中没有度数为1的结点。()6.对连通图进行深度优先遍历可以访问到该图中的所有顶点。()7.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()8.由树转化成二叉树，该二叉树的右子树不一定为空。()9.线性表中的所有元素都有一个前驱元素和后继元素。()10.带权无向图的最小生成树是唯一的。()三、填空题(30分)1.1.设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为=p；s->right=p->right；=s；p->right->left=s；(设结点中的两个指针域分别为left和right).2.2.设完全有向图中有n个顶点，则该完全有向图中共有条有向条；设完全无向图中有n个顶点，则该完全无向图中共有条无向边。3.3.设关键字序列为(K“K2Kn),则用筛选法建初始堆必须从第个元素开始进行筛选。4.4.解决散列表冲突的两种方法是和o

501.5.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结占数有个。2.6.高度为h的完全二叉树中最少有个结点，最多有个结点。3.7.设有一组初始关健字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是。4.8.设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟简单选择排序结束后的结果的是.5.9.设一棵二叉树的前序序列为ABC,则有种不同的二叉树可以得到这种序列。6.10.下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i)(intj=t;structrecordx=r[s];i=s;while(ix.key)j=j-l;if(i

51一、选择题1.B6.A2.B7.C3.C8.C4.B5.B10.D9.B二、判断题1.对2.对3.对4.对5.对6.对7.对8.错9.错10.错三、填空题1.1.s->left=p,p->right2.2.n(n-l),n(n-l)/23.3.n/24.4.开放定址法，链地址法5.5.146.6.2叫2h-l7.7.(12,24,35,27,18,26)8.8.(12,18,24,27,35,26)9.9.510.10.inext==O)return;for(q=head;q!=0;q=q->next)(min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}))2.2.设计在顺序存储结构上实现求子串算法。voidsubstring(chars|],longstart,longcount,chart[]){longi,j,length=strlen(s);if(startlength)printf('Thecopypositioniswrong*');elseif(start4-count-l>length)printf(uToocharacterstobecopied");else{for(i=start-l,j=0;ikey==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);})

52一、选择题(30分)1.1.字符串的长度是指()。(A)串中不同字符的个数(B)串中不同字母的个数(C)串中所含字符的个数(D)串中不同数字的个数2.2.建立一个长度为n的有序单链表的时间复杂度为()(A)O(n)(B)O(l)(C)O(n2)(D)O(log2n)3.3.两个字符串相等的充要条件是()o(A)两个字符串的长度相等(B)两个字符串中对应位置上的字符相等(C)同时具备(A)和(B)两个条件(D)以上答案都不对4.4.设某散列表的长度为100,散列函数H(k)=k%P,则P通常情况下最好选择()o(A)99(B)97(C)91(D)935.5.在二叉排序树中插入一个关键字值的平均时间复杂度为().(A)O(n)(B)O(log2n)(C)O(nlog2n)(D)O(n2)6.6.设一个顺序有序表中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。(A)A[l],A[2],A[3],A[4](B)A[l],A[14],A[7],A[4](C)A[7],A[3],A[5],A[4](D)A[7],A[5],A[3],A[4]7.7.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为()»(A)8(B)7(C)6(D)58.8.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有()个度数为0的结点。(A)5(B)6(C)7(D)89.9.设无向图G中的边的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()o(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc10.10.队列是一种()的线性表。(A)先进先出(B)先进后出(C)只能插入(D)只能删除二、判断题(20分)1.1.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。()2.2.设初始记录关键字基本有序，则快速排序算法的时间复杂度为CKnlogzn)。()3.3.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。()4.4.二维数组和多维数组均不是特殊的线性结构。()5.5.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。()6.6.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。()7.7.非空的双向循环链表中任何结点的前驱指针均不为空。()8.8.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。()9.9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。()10.10.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素()三、填空题(30分)1.1.设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则以d=4为增量的一趟希尔排序结束后的结果为。2.2.下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild;structnode*rchild;}bitree;voidbstinsert(bitree*&t,intk)if(t==0){;t->data=k;t->lchild=t->rchild=O;}elseif(t->data>k)bstinsert(t->lchild,k);else;)3.3.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;

531.4.设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=和head=(设结点中的两个指针域分别为Mink和rlink)。2.5.设某棵二叉树的中序遍历序列为ABCD,后序遍历序列为BADC,则其前序遍历序列为.3.6.完全二叉树中第5层上最少有个结点，最多有个结点。4.7.设有向图中不存在有向边,则其对应的邻接矩阵A中的数组元素的值等于.5.8.设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则第4趟直接选择排序结束后的结果为。6.9.设连通图G中有n个顶点e条边，则对应的最小生成树上有条边。7.10.设有一组初始记录关键字序列为(50,16,23,68,94,70,73),则将它们调整成初始堆只需把16与相互交换即可。四、算法设计题(20分)1.1.设计一个在链式存储结构上统计二叉树中结点个数的算法。2.2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

54一、选择题1.C2.C6.C7.B二、判断题1.对2.错6.对7.对3.对8.对4.错5.错9.对10.对1.C4.B5.B8.C9.A10.A三、填空题1.1.(49,13,27,50,76,38,65,97)2.2.t=(bitree*)malloc(sizeof(bitree)),bstinsert(t->rchi1d,k)3.3.p->next=s4.4.head->rlink,p->llink5.5.CABD6.6.1,167.7.08.8.(13,27,38,50,76,49,65,97)9.9.n-110.10.50四、算法设计题1.1.设计一个在链式存储结构上统计二叉树中结点个数的算法。voidcountnode(bitree*bt,int&count)(if(bt!=O){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);})2.2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfb;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixgl[],glinkheadnodeg2[]){inti,j;glinklistnode*p;fbr(i=0;i<=n-1;i++)g2[i].firstarc=0;fbr(i=0;i<=n-1;i++)fbr(j=O;j<=n-1;j++)if(gl.edge[i][j]==l)(p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;

55数据结构试卷(九)一、选择题(30分)1.下列程序段的时间复杂度为()。for(i=0；iright=s；s->left=p；p->right->left=s；s->right=p->right；(B)s->left=p；s->right=p->right；p->right=s；p->right->left=s；(C)p->right=s：p->right->left=s；s->left=p；s->right=p->right；(D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；6.下列各种排序算法中平均时间复杂度为0(1?)是()。(A)快速排序(B)堆排序(C)归并排序(D)冒泡排序7.设输入序列1、2、3n经过栈作用后，输出序列中的第一个元素是n,则输出序列中的第i个输出元素是().(A)n-i(B)n-l-i(C)n+1-i(D)不能确定8.设散列表中有m个存储单元，散列函数H(key)=key%p,则p最好选择().(A)小于等于m的最大奇数(B)小于等于m的最大素数(C)小于等于m的最大偶数(D)小于等于m的最大合数9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有()个。(A)4(B)5(C)6(D)710.设完全无向图中有n个顶点，则该完全无向图中有()条边。(A)n(n-l)/2(B)n(n-l)(C)n(n+1)/2(D)(n-l)/211.设顺序表的长度为n,则顺序查找的平均比较次数为()。(A)n(B)n/2(C)(n+1)/2(D)(n-l)/212.设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分法查找值为24的元素需要经过()次比较。(A)1(B)2(C)3(D)413.设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为()«(A)6(B)11(C)5(D)6.514.设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>},则下列属于该有向图G的一种拓扑排序序列的是()。(A)1,2,3,4(B)2,3,4,1(C)1,4,2,3(D)1,2,4,315.设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则由这组记录关键字生成的二叉排序树的深度为()«(A)4(B)5(C)6(D)7二、填空题(30分)1.1.设指针p指向单链表中结点A,指针s指向被插入的结点X,则在结点A的前面插入结点X时的操作序列为：1)s->next=；2)p->next=s；3)t=p->data；

564)p->data=；5)s->data=t；

571.2.设某棵完全二叉树中有100个结点，则该二叉树中有个叶子结点。2.3.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储队列元素。3.4.对一组初始关键字序列（40,50,95,20,15,70,60,45,10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为，在整个排序过程中最多需要进行趟排序才可以完成。4.5.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择排序，如果从节省存储空间的角度来考虑则最好选择排序。5.6.设一组初始记录关键字序列为（20,12,42,31,18,14,28）,则根据这些记录关键字构造的二叉排序树的平均查找长度是。6.7.设一棵二叉树的中序遍历序列为BDCA,后序遍历序列为DBAC,则这棵二叉树的前序序列为o7.8.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10,根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为»8.9.设一组记录关键字序列为（80,70,33,65,24,56,48）,则用筛选法建成的初始堆为o9.10.设无向图G（如右图所示），则其最小生成树上所有边的8权值之和为三、判断题（20分）1.1.有向图的邻接表和逆邻接表中表结点的个数不一定相等。（）2.2.时链表进行插入和删除操作时不必移动链表中结点.（）3.3.子串“ABC”在主串“AABCABCD”中的位置为2。（）4.4.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。（）5.5.希尔排序算法的时间复杂度为O（n2）o（）6.6.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。（）7.7.中序遍历一棵二叉排序树可以得到一个有序的序列。（）8.8.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）9.9.顺序表查找指的是在顺序存储结构上进行查找。（）10.10.堆是完全二叉树，完全二叉树不一定是堆。（）五、算法设计题（20分）1.1.设计计算二叉树中所有结点值之和的算法。2.2.设计将所有奇数移到所有偶数之前的算法。3.3.设计判断单链表中元素是否是递增的算法。

58一、选择题1.A2.A6.D7.C11.C12.C13.D14.A15.A3.A4.C5.D8.B9.C10.A二、填空题1.1.p->next»s->data2.2.503.3.m-14.4.6,85.5.快速，堆6.6.19/77.7.CBDA8.8.69.9.(24,65,33,80,70,56,48)10.10.8三、判断题1.错2.对3.对4.对5.错6.错7.对8.对9.错10.对四、算法设计题1.1.设计计算二叉树中所有结点值之和的算法。voidsum(bitree*bt,int&s)(if(bt!=O){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);})2.2.设计将所有奇数移到所有偶数之前的算法。voidquickpass(intr[],ints,intt)(inti=s,j=t,x=r[s];while(inext==O)retum(l);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)retum(O);return(l);

59数据结构试卷(十)一、选择题(24分)1.下列程序段的时间复杂度为()。i=0,s=0；while(snext=p->next：p->next=-s；(B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；4.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为().(A)5,3,4,6,1,2(B)3,2,5,6,4,1(C)3,1,2,5,4,6(D)1,5,4,6,2,35.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为()。(A)10(B)19(C)28(D)556.设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，Nm个度数为m的结点，则该树中共有()个叶子结点。Z(i-DM2mi+Z(DM(A)i=!(B)Ml(C)i=2(D)7.二叉排序树中左子树上所有结点的值均()根结点的值。(A)<(B)>(C)=(D)!=8.设一组权值集合W=(15,3,14,2,6,9,16,17),要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为()。(A)129(B)219(C)189(D)2299.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做()次线性探测。(A)n2(B)n(n+l)(C)n(n+l)/2(D)n(n-l)/210.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉中共有()个结点。(D)2n+l趟插入排序可以得到有序序列。(D)9M,S,R,D,F,X),则按字母(A)2n(B)n+1(C)2n-l11.设一组初始记录关键字的长度为8,则最多经过()(A)6(B)7(C)812.设一组初始记录关键字序列为(Q,H,C,Y,P,A,升序的第一趟冒泡排序结束后的结果是()。(A)F,H,C,D,P,A,M,Q,R,S,Y,X(B)P,A,C,S,Q,D,F,X,R,H,M,Y(C)A,D,C,R,F,Q,M,S,Y,P,H,X(D)H,C,Q.P,A,M,S,R,D,F,X,Y二、填空题(48分，其中最后两小题各6分)1.1.设需要对5个不同的记录关键字进行排序，则至少需要比较次，至多需要比较次。2.2.快速排序算法的平均时间复杂度为,直接插入排序算法的平均时间

60复杂度为.

611.3.设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较次。2.4.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有个，比较两次查找成功有结点数有个。3.5.设一棵m叉树脂的结点数为n,用多重链表表示其存储结构，则该树中有个空指针域。4.6.设指针变量p指向单链表中结点A,则删除结点A的语句序列为：q=p->next：p->data=q->data：p->next=；feee(q)；5.7.数据结构从逻辑上划分为三种基本类型:、和6.8.设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为:用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为o7.9.设散列表的长度为8,散列函数H(k)=k%7,用线性探测法解决冲突，则根据一组初始关键字序列(8,15,16,22,30,32)构造出的散列表的平均查找长度是«8.10.设一组初始关键字序列为(38,65,97,76,13,27,10),则第3趟冒泡排序结束后的结果为.9.11.设一组初始关键字序列为(38,65,97,76,13,27,10),则第3趟简单选择排序后的结果为o10.12.设有向图G中的有向边的集合E={<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>},则该图的一个拓扑序列为.11.13.下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild;;}bitree;voidcreatebitree(bitree*&bt)(scanf(tt%c,\&ch);if(ch==,#,);else{bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;;createbitree(bt->rchild);})12.14.下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*next;)Iklist;voidlklistcreate(*&head){for(i=l;i<=n;i++){p=(lklist*)malloc(sizeof(lklist));scanf(M%d,,,&(p->data));p->next=0;if(i==l)head=q=p;else{q->next=p;;}})三、算法设计题(22分)1.1.设计在链式存储结构上合并排序的算法。2.2.设计在二叉排序树上查找结点X的算法。3.3.设关键字序列(k“k2,...»%)是堆,设计算法将关键字序列(k”k2kn.px)调整为堆。一、选择题1.A2.D7.A8.D数据结构试卷(十)参考答案3.B4.B5.B6.D9.D10.C11.B12.D二、填空题1.1.4,102.2.O(nlog2n),0(n2)3.3.n4.4.1,25.5.n(m-l)+l6.6.q->next7.7.线性结构，树型结构，图型结构8.8.O(n2),O(n+e)9.9.8/3

621.10.(38,13,27,10,65,76,97)2.11.(10,13,27,76,65,97,38)3.12.1246534.13.structnode*rchild,bt=O»createbitree(bt->lchild)5.14.Iklistyq=p三、算法设计题1.1.设计在链式存储结构上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc)(Iklist*s=hc=O;while(ha!=0&&hb!=O)if(ha->datadata){if(s=O)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s=O)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==O)s->next=hb;elses->next=ha;)2.2.设计在二叉排序树上查找结点X的算法。bitree*bstsearchl(bitree*t,intkey)(bitree*p=t;while(p!=0)if(p->key==key)retum(p);elseif(p>>key>key)p=p->lchiId;elsep=p->rchild;return(O);)3.3.设关键字序列(k],k2,hi)是堆，设计算法将关键字序列(％,k2,knd,x)调整为堆。voidadjustheap(intr[],intn){intj=n,i=j/2,temp=r[j-1];while(i>=l)if(temp>=r[i-l])break;else{r[j-l]=r[i-1];j=i;i=i/2;}r|j-l]=temp;