2023年专升本十套数据结构试题及答案

数据结构试卷(一）一、单选题（每题2分，共20分）栈和队列的共同特点是()。A．只允许在端点处插入和删除元素B.都是先进后出Ｃ.都是先进先出D.没有共同点用链接方式存储的队列,在进行插入运算时（)．A.仅修改头指针B．头、尾指针都要修改Ｃ.仅修改尾指针D.头、尾指针也许都要修改以下数据结构中哪一个是非线性结构?(）Ａ.队列B．栈C.线性表D.二叉树设有一个二维数组A[m]［n]，假设A[0］[０］存放位置在64４（１０),Ａ［２][2]存放位置在676(10)，每个元素占一个空间,问A［3］[3]（10)存放在什么位置？脚注(10)表达用１0进制表达。A.688B．６78C．692Ｄ.696树最适合用来表达（)。A.有序数据元素Ｂ.无序数据元素Ｃ．元素之间具有分支层次关系的数据D.元素之间无联系的数据二叉树的第ｋ层的结点数最多为（).A.2k-1B.2K+１C．２Ｋ-１D．2ｋ-１若有18个元素的有序表存放在一维数组A［19]中，第一个元素放A[1]中，现进行二分查找,则查找A［3］的比较序列的下标依次为(）A．1，2，3ﻩﻩ ﻩ Ｂ．9,５,２,３C．9，5,3 ﻩ D.９，４,2,3对ｎ个记录的文献进行快速排序,所需要的辅助存储空间大体为Ａ.O(1）B.O（ｎ)Ｃ.O(1ｏg2n）D．O(n2)对于线性表（7,34,５５,25,64,46，２0,１０)进行散列存储时，若选用H(K）＝K%9作为散列函数,则散列地址为1的元素有（)个,A．１B.２C．３D．4设有6个结点的无向图,该图至少应有()条边才干保证是一个连通图。A．5Ｂ.６C．7D．8二、填空题(每空1分，共２６分)通常从四个方面评价算法的质量：_＿___＿＿＿_、＿＿＿＿__＿＿＿、____＿_＿__和＿＿_______。一个算法的时间复杂度为(ｎ3+n2lｏｇ2n＋14ｎ)／n2,其数量级表达为＿＿_____＿。假定一棵树的广义表表达为A（C，D（E，F，G)，H(I,Ｊ))，则树中所含的结点数为__＿_____＿＿个，树的深度为＿_____＿__＿_，树的度为_＿_______。后缀算式923+－１０２／-的值为__＿＿______。中缀算式（3+4X）-２Y/3相应的后缀算式为＿＿＿_____＿____＿_＿＿_＿＿______＿_＿__。若用链表存储一棵二叉树时,每个结点除数据域外,尚有指向左孩子和右孩子的两个指针。在这种存储结构中,ｎ个结点的二叉树共有＿______＿个指针域，其中有_＿______个指针域是存放了地址,有＿___＿__＿_______＿个指针是空指针。对于一个具有ｎ个顶点和ｅ条边的有向图和无向图，在其相应的邻接表中，所含边结点分别有______＿个和_＿＿_____个。AOV网是一种_＿___＿__＿___＿__＿___的图。在一个具有n个顶点的无向完全图中,包具有_＿__＿___条边,在一个具有n个顶点的有向完全图中，包具有＿＿_＿____条边。假定一个线性表为(１2，23,7４,5５,63,４0),若按Kｅｙ％4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为__＿＿____＿__＿___________＿＿_＿_、_＿__＿＿＿________＿___、_________＿__＿＿＿＿_____＿_和_＿＿____＿_____＿＿_______＿___。向一棵Ｂ_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度_____＿_＿___。在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_____＿__，整个堆排序过程的时间复杂度为___＿____。在快速排序、堆排序、归并排序中,_________排序是稳定的。三、计算题(每题6分，共24分)在如下数组A中链接存储了一个线性表,表头指针为A[0]．nexｔ,试写出该线性表。Ａ０１２３456７data６05０7890３440nｅxt３572041请画出下图的邻接矩阵和邻接表。已知一个图的顶点集Ｖ和边集E分别为:V={1,２,3,4,５,６,7};E＝｛（1，2)3,(1，3)５，(1,4）8,（2,5)１0，(2,3)6，(3，4）15,(3,5）12,(3，6)9,(4,6)4,(4,7)２０,(5,６）1８,(６，７)25｝；用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。画出向小根堆中加入数据4,２,5,８，3时,每加入一个数据后堆的变化。四、阅读算法(每题7分,共14分）LｉｎｋListmynote（LinkListL){／/L是不带头结点的单链表的头指针iｆ(L＆＆L-＞neｘｔ){q=L；Ｌ=L->nｅxt；p=L;S1:whiｌe（p->next)p＝p－>next;S2：p->ｎｅxｔ＝q；ｑ－>neｘt=NULL;｝retuｒnL;}请回答下列问题:（1）说明语句S1的功能;（2)说明语句组S2的功能；（3)设链表表达的线性表为(ａ1,ａ2,…,ａｎ）,写出算法执行后的返回值所表达的线性表。vｏidABC(BTNｏｄe＊BT){ｉfBT｛ABC(BT-＞ｌｅft）;ABC(BT-＞righｔ）;ｃｏut<<BT-＞data<<'';}｝该算法的功能是：五、算法填空（共8分）二叉搜索树的查找——递归算法:boolＦind(BＴreeＮｏde*ＢＳT，ＥlemType&item){iｆ（BST==NUＬL)rｅturｎｆalｓe；／／查找失败ｅｌse{if(iｔeｍ＝＝ＢＳT->ｄatａ）｛item=ＢST->daｔａ;/／查找成功returｎ_＿＿_＿__＿___;}elseｉf（ｉｔem＜BＳT->daｔａ）ｒetuｒnＦinｄ(_＿____＿＿______,item）;eｌseｒｅtuｒnFｉnd(___＿_＿_____＿＿＿＿,ｉｔem）;}//if}六、编写算法(共８分)记录出单链表HＬ中结点的值等于给定值X的结点数。intCountX(LNodｅ*HL,ＥlemTypｅx)数据结构试卷（二）一、选择题（24分)1．下面关于线性表的叙述错误的是(）。 (A）线性表采用顺序存储必须占用一片连续的存储空间ﻩ（B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现2.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构,则该哈夫曼树中总共有（)个空指针域。ﻩ（A)２m-1ﻩ(Ｂ)2m (C)2m+１ (D)4m3.设顺序循环队列Ｑ[０：Ｍ-1]的头指针和尾指针分别为Ｆ和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为(）。ﻩ(A)R-Fﻩ(B)F-Ｒﻩ（C)(R－F＋Ｍ)%Mﻩ(Ｄ)(F-Ｒ+M）％Ｍ4．设某棵二叉树的中序遍历序列为ＡBCＤ,前序遍历序列为ＣAＢD,则后序遍历该二叉树得到序列为（）。ﻩ(A)BADCﻩ（B)BCDA (C)CＤAB (D)CBDA5．设某完全无向图中有n个顶点,则该完全无向图中有()条边。 (Ａ)ｎ(n-1）/2 (B)n(n-1)ﻩ(C）n2ﻩ(D)n2-１６.设某棵二叉树中有2023个结点,则该二叉树的最小高度为（)。 (A）９ﻩ（B)10 (C)１１ﻩ(D)127.设某有向图中有ｎ个顶点，则该有向图相应的邻接表中有（）个表头结点。 (Ａ)n-1ﻩ(B)ｎ (C)n+1 （D）2n－18.设一组初始记录关键字序列(5,2,6，3,8)，以第一个记录关键字5为基准进行一趟快速排序的结果为()。ﻩ(Ａ）2，3,5,８,6 ﻩ(B)3,2,5，8，6 (C）3，2,5,6,８ﻩ （D)２,３，6,5，8二、填空题(24分）为了能有效地应用HＡＳH查找技术,必须解决的两个问题是__＿__＿_＿___＿___＿__＿_和_________＿__＿________＿_＿__。下面程序段的功能实现数据ｘ进栈，规定在下划线处填上对的的语句。typedefsｔruｃt｛inｔs[100]；intｔｏp;}sqｓtacｋ;ｖｏｉｄpｕsｈ(sｑsｔack&ｓtack，intｘ){if(ｓｔａck．tｏp＝=m-１)pｒintf（“overｆｌow”)；ｅｌsｅ{__＿_____＿_____＿_＿＿＿_;_＿______＿__＿＿____;}}中序遍历二叉排序树所得到的序列是___＿_____＿_序列(填有序或无序)。快速排序的最坏时间复杂度为_＿_________，平均时间复杂度为_____＿____。设某棵二叉树中度数为0的结点数为Ｎ０,度数为1的结点数为N1,则该二叉树中度数为2的结点数为＿＿____＿__;若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有＿＿＿____个空指针域。设某无向图中顶点数和边数分别为n和ｅ,所有顶点的度数之和为d，则e=______＿。设一组初始记录关键字序列为(55，63，44,38，７５,80，31,56），则运用筛选法建立的初始堆为__＿＿__＿＿______＿_＿____＿_____。８．已知一有向图的邻接表存储结构如下:从顶点1出发，DFS遍历的输出序列是,BＦＳ遍历的输出序列是三、应用题(36分)设一组初始记录关键字序列为（45，8０,48,４０，22，78)，则分别给出第4趟简朴选择排序和第4趟直接插入排序后的结果。设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，规定给出在结点Ａ的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llｉnk和rlink）。设一组有序的记录关键字序列为（13，18,２4，3５，47,５0,62，83,9０)，查找方法用二分查找，规定计算出查找关键字6２时的比较次数并计算出查找成功时的平均查找长度。设一棵树Ｔ中边的集合为{(A，B），(A，C),(A，D),(B,E)，(C，F)，(Ｃ,G)}，规定用孩子兄弟表达法(二叉链表）表达出该树的存储结构并将该树转化成相应的二叉树。设有无向图G,规定给出用普里姆算法构造最小生成树所走过的边的集合。设有一组初始记录关键字为(45,80,48,40,２2,78）,规定构造一棵二叉排序树并给出构造过程。四、算法设计题(１6分）设有一组初始记录关键字序列(K1,K2，…,Kn),规定设计一个算法可以在O(n)的时间复杂度内将线性表划提成两部分,其中左半部分的每个关键字均小于Ｋi,右半部分的每个关键字均大于等于Ｋi。设有两个集合A和集合B,规定设计生成集合C＝Ａ∩B的算法,其中集合Ａ、B和C用链式存储结构表达。数据结构试卷(三）一、选择题(每题1分，共20分）1．设某数据结构的二元组形式表达为A=(D，R)，D={01,0２,03，04,05，06，07,08,09},R=｛r}，ｒ={＜0１,02>,<01,03>，＜0１，04>，<02,０５>，<02，06>，<０３,０7>,<０3,08>,<03，09>},则数据结构Ａ是（）。ﻩ(A）线性结构 (B)树型结构ﻩ（C)物理结构ﻩ(Ｄ)图型结构2.下面程序的时间复杂为(）ｆor（i=１,s=０；i<=n；i++）{t=1；fｏr(j=1；j＜=i；j+＋)t=t*j;s=s＋t；}ﻩ(A)O(n)ﻩ(B）Ｏ(ｎ2） (C)O（n3）ﻩ （Ｄ)Ｏ(n４）３.设指针变量p指向单链表中结点Ａ，若删除单链表中结点A，则需要修改指针的操作序列为（)。 (A)q＝p->nｅxt;p－>dａta=ｑ－>dａta;p->next=ｑ-＞next；ｆree（q);（B)ｑ=p－>next；q->daｔa=p－>data；p->ｎｅxt=q->next;ｆree（q）; (Ｃ）q=p->neｘt;p->next=q->ｎext；ｆrｅe（q)；ﻩ(D）q=ｐ->next;p->datａ=q->datａ;fｒee(ｑ)；4.设有n个待排序的记录关键字,则在堆排序中需要(）个辅助记录单元。ﻩ（A）1 (Ｂ)nﻩ（Ｃ)nlog２ｎﻩ（D)n２5.设一组初始关键字记录关键字为（20，15,14,1８,21,３6,４０，1０),则以2０为基准记录的一趟快速排序结束后的结果为（)。(Ａ)１0,15,１4，18，２0,３６,40,21ﻩ(B）10，１5,1４,18，２0，4０，3６，２1 (C)１0，15，14，20，１８,４０,3６,2lﻩ(Ｄ)15,10，14，1８,20，3６，40，216．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为(）。 (A)Ｏ(１)ﻩ(B)Ｏ(log2n）ﻩ(C)ﻩ(D)O(n2）7.设无向图G中有ｎ个顶点e条边，则其相应的邻接表中的表头结点和表结点的个数分别为（)。ﻩ(A)n，ｅﻩ（B）ｅ,n (C）2ｎ，e (Ｄ)n,２e8.设某强连通图中有n个顶点，则该强连通图中至少有()条边。ﻩ(A)n(n-1)ﻩ（B)ｎ+1ﻩ(Ｃ)nﻩ(D)ｎ(n+１）９.设有50００个待排序的记录关键字，假如需要用最快的方法选出其中最小的１０个记录关键字,则用下列()方法可以达成此目的。ﻩ(Ａ）快速排序ﻩ(B)堆排序ﻩ(Ｃ)归并排序 (D)插入排序１0.下列四种排序中（)的空间复杂度最大。 （Ａ)插入排序 （B)冒泡排序 (C）堆排序ﻩ(D)归并排序二、填空殖(每空1分共２0分)数据的物理结构重要涉及__＿＿__＿______和____＿___＿＿__＿_两种情况。设一棵完全二叉树中有500个结点,则该二叉树的深度为＿＿＿_＿＿___＿;若用二叉链表作为该完全二叉树的存储结构,则共有_＿＿_＿___＿_＿个空指针域。设输入序列为1、2、3,则通过栈的作用后可以得到_____＿____＿种不同的输出序列。设有向图Ｇ用邻接矩阵Ａ[n］[ｎ]作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点ｉ的________，第ｉ列上所有元素之和等于顶点i的_＿__＿__＿。设哈夫曼树中共有n个结点，则该哈夫曼树中有_＿＿_____个度数为1的结点。设有向图G中有ｎ个顶点ｅ条有向边，所有的顶点入度数之和为d，则ｅ和ｄ的关系为_＿_______。＿＿___＿＿___遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序)。设查找表中有100个元素,假如用二分法查找方法查找数据元素Ｘ，则最多需要比较_＿_＿__＿_次就可以断定数据元素X是否在查找表中。不管是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为___＿___＿____。设有n个结点的完全二叉树,假如按照从自上到下、从左到右从１开始顺序编号,则第i个结点的双亲结点编号为____＿_______，右孩子结点的编号为＿___＿＿____＿。设一组初始记录关键字为(７2,73，71,23，9４,16,5），则以记录关键字72为基准的一趟快速排序结果为____＿_____＿___＿_____＿___＿__。设有向图G中有向边的集合E={<1,２>，<2，３＞，<1，4>,<4，２>，<4,3＞｝,则该图的一种拓扑序列为_____＿_＿＿_＿_＿______＿。下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上对的的语句。sｔrucｔｒecorｄ{iｎtkｅy；iｎtｏｔhers;}；ｉｎｔhａｓｈsqｓearch（sｔructｒeｃordｈａshtable[],intk){inｔi,j;ｊ＝i=k%ｐ;wｈile(hashtable[j］.key!=ｋ&&haｓhｔaｂle[j］.ｆlag!=0){j＝(_＿__)%ｍ;ｉf(i==ｊ)reｔurn(-1);}if(__________________＿__＿_)retｕrn(j);eｌsereturn(-１);｝下列算法实现在二叉排序树上查找关键值k,请在下划线处填上对的的语句。typedｅfｓｔrｕcｔnode{intkｅy;ｓｔructnode＊lchｉld;strｕcｔnode＊rcｈiｌd;}ｂitreｅ;bitree*ｂstsｅarch(bitｒee＊t,iｎtｋ){ iｆ(t==0）reｔuｒｎ（０）；ｅlseｗhｉle（t！＝0)if(t-＞keｙ=＝k)＿____＿___＿__＿；elｓｅif(t－>keｙ>k)ｔ=t->lchild;ｅｌｓe___＿__＿______;}三、计算题（每题10分,共30分)1．已知二叉树的前序遍历序列是AEFBGCＤHIKJ，中序遍历序列是EＦAGＢCHＫIJD,画出此二叉树,并画出它的后序线索二叉树。2．已知待散列的线性表为（３6，15,40,63,22),散列用的一维地址空间为[0.．６]，假定选用的散列函数是H（K)=Ｋmoｄ7,若发生冲突采用线性探查法解决，试：(1)计算出每一个元素的散列地址并在下图中填写出散列表:｀0123４５６(2）求出在查找每一个元素概率相等情况下的平均查找长度。3.已知序列(１0,18，4，３，6，12,1,９,18,8)请用快速排序写出每一趟排序的结果。四、算法设计题(每题1５分,共30分)设计在单链表中删除值相同的多余结点的算法。设计一个求结点x在二叉树中的双亲结点算法。数据结构试卷(四)一、选择题(每题1分共２0分)１．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。 （A)O(n） (B)Ｏ(nlog２ｎ) (C)Ｏ（1) （D)O（n2)２.设一棵二叉树的深度为k，则该二叉树中最多有()个结点。ﻩ（A)２k-1 (Ｂ)2k （C)２k-1ﻩ(D)2ｋ-１3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。 (A)n （B)e (C)2ｎ (D)２e４.在二叉排序树中插入一个结点的时间复杂度为（)。ﻩ(A）O(１)ﻩ(Ｂ)O(n) (C)Ｏ(loｇ2ｎ）ﻩ（D)O(n2）５.设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有(）条有向边。ﻩ(Ａ)ｎ (B)ｎ－1 (C)mﻩ（D)ｍ-１6.设一组初始记录关键字序列为(３45,253，６７4,924,62７)，则用基数排序需要进行（)趟的分派和回收才干使得初始关键字序列变成有序序列。 (A)3 （B)4 （Ｃ)５ﻩ(D)87．设用链表作为栈的存储结构则退栈操作()。 (A)必须判别栈是否为满ﻩ（B)必须判别栈是否为空 (Ｃ）判别栈元素的类型 （D)对栈不作任何判别8．下列四种排序中(）的空间复杂度最大。ﻩ(A)快速排序ﻩ（B)冒泡排序 (Ｃ）希尔排序ﻩ（D）堆９.设某二叉树中度数为0的结点数为N０,度数为1的结点数为Nl，度数为２的结点数为N２,则下列等式成立的是（)。ﻩ（A)N０=N１+1ﻩ(B)N0=Nl+Ｎ2 (C)Ｎ0＝N2+1ﻩ（D）N0=2N１＋l10.设有序顺序表中有ｎ个数据元素,则运用二分查找法查找数据元素Ｘ的最多比较次数不超过(）。ﻩ(A)loｇ2n+1ﻩ(B)log2n-1ﻩ(Ｃ)log2ｎﻩ(D)lｏｇ2(n+1）二、填空题(每空1分共20分)设有ｎ个无序的记录关键字，则直接插入排序的时间复杂度为__＿___＿_，快速排序的平均时间复杂度为＿__＿_＿__＿。设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为_____＿_____＿______＿___＿_＿_＿_＿_____＿_＿＿________＿＿______＿__（设结点中的两个指针域分别为llink和rlink）。根据初始关键字序列(19，２2,01，３8,10)建立的二叉排序树的高度为＿____＿______。深度为k的完全二叉树中最少有_____＿_＿__＿_个结点。设初始记录关键字序列为(K1,K2，…，Ｋｎ)，则用筛选法思想建堆必须从第____＿＿个元素开始进行筛选。设哈夫曼树中共有９9个结点，则该树中有_＿___＿___个叶子结点;若采用二叉链表作为存储结构，则该树中有_＿_＿_个空指针域。设有一个顺序循环队列中有Ｍ个存储单元,则该循环队列中最多可以存储＿＿___＿__个队列元素；当前实际存储__＿______＿____＿_个队列元素(设头指针Ｆ指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置)。设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中＿__＿＿__个数据元素；删除第i个位置上的数据元素需要移动表中____＿_＿个元素。设一组初始记录关键字序列为(２0，18,22，16，3０,19)，则以20为中轴的一趟快速排序结果为______＿____＿＿_＿_＿＿＿＿__＿___＿_＿_。设一组初始记录关键字序列为(２０，18,22，16，30,1９)，则根据这些初始关键字序列建成的初始堆为_＿__＿__________＿__＿＿____。设某无向图G中有n个顶点，用邻接矩阵Ａ作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是________＿_____＿_＿_____。设无向图相应的邻接矩阵为A,则A中第i上非0元素的个数_________第ｉ列上非0元素的个数(填等于,大于或小于）。设前序遍历某二叉树的序列为ABCD,中序遍历该二叉树的序列为BAＤＣ,则后序遍历该二叉树的序列为＿____＿_＿_____。设散列函数H(ｋ)=kmodｐ,解决冲突的方法为链地址法。规定在下列算法划线处填上对的的语句完毕在散列表haｓhtａlbｅ中查找关键字值等于k的结点，成功时返回指向关键字的指针,不成功时返回标志0。typeｄeｆｓtrucｔnｏde{ｉｎtkeｙ;ｓtrｕctnｏdｅ*nexｔ；｝ｌkｌiｓｔ；voidcreateｌkhash(ｌklist*hashｔable[]）{ｉnｔi,ｋ；lｋliｓt*s；fｏr(i=0;i<m;ｉ++)______＿_＿__＿＿＿＿______；foｒ（i=０；i<n；i++){s=(lｋlist*)malloｃ（sｉzeof(ｌklist）);s->ｋey=ａ[i];k=a［ｉ]%ｐ;ｓ->ｎexｔ=hashｔable［k]；__＿＿_＿__＿＿__＿___＿___＿＿＿;}}三、计算题(每题１0分，共30分）1、画出广义表LS=（()，（e)，(a,（b,c,ｄ))）的头尾链表存储结构。２、下图所示的森林:(１)求树(ａ)的先根序列和后根序列;（2）求森林先序序列和中序序列;(3）将此森林转换为相应的二叉树;３、设散列表的地址范围是[０.．9],散列函数为H(key)=(ｋeｙ2＋2）MＯD9，并采用链表解决冲突,请画出元素7、４、５、3、６、２、8、9依次插入散列表的存储结构。四、算法设计题（每题10分,共30分)设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),规定运用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。设计在链式存储结构上互换二叉树中所有结点左右子树的算法。在链式存储结构上建立一棵二叉排序树。数据结构试卷（五)一、选择题（2０分)１.数据的最小单位是()。ﻩ（Ａ）数据项ﻩ(B)数据类型 (C）数据元素 (D）数据变量2．设一组初始记录关键字序列为(50,40，９5，2０,15,7０，6０,45),则以增量ｄ=4的一趟希尔排序结束后前4条记录关键字为（）。 (Ａ)4０，50,２0,9５ﻩ（B)15,4０,６０，20ﻩ（C)15，20，４０,4５ﻩ（D)45，40,15，203.设一组初始记录关键字序列为(２５,50，１５,3５,8０,85,2０,40，36,70),其中具有5个长度为２的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为()。(A)15，25,35，50,20,４0,8０，85，36，７0(Ｂ)15,25,３5,50，８0，２0，8５，40,7０，36（Ｃ)１５，2５，３５,5０,8０,85，２0,３６，4０,７0(D）１５,25，35,50，80,2０,３6，40，70,854．函数substｒ(“ＤATASTRUCTURE”,5,9)的返回值为(）。 (A)“STRUＣTＵRE” ﻩ(B)“DATA” (C)“ASTRUCTUR” （D)“DATＡSTRUCTUＲE”５.设一个有序的单链表中有ｎ个结点，现规定插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为()。 (A）O(log2ｎ)ﻩ(Ｂ)O(1) (C)Ｏ（n２）ﻩ（Ｄ）Ｏ（n）6.设一棵m叉树中度数为０的结点数为N0，度数为１的结点数为Nl，……,度数为m的结点数为Nm，则Ｎ0=()。 (Ａ)Nｌ+N2+……+Nmﻩﻩ（B)l＋N2+２N3+3Ｎ4＋……+(m-1)Nmﻩ(Ｃ)N2＋2N3+3N4＋……+(ｍ-1)Nmﻩ（D)2Nｌ+3Ｎ2＋……+(m＋１)Nｍ7．设有序表中有100０个元素,则用二分查找查找元素X最多需要比较（）次。 (Ａ)25ﻩ（B)10ﻩ(C)７ﻩﻩ(Ｄ)18.设连通图G中的边集E＝{（a，b)，(ａ,e),（ａ，c),（b，ｅ),(e，d),（d,f)，(f,c）｝，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（)。 (A)aｂedfｃ (B)ａｃfebd (C)ａebdfc (D）ａeｄfcb9．设输入序列是1、２、3、……、n，通过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是(）。 (A)ｎ-iﻩ（Ｂ)ｎ-1-iﻩ(C)ｎ＋1-iﻩ (D)不能拟定10设一组初始记录关键字序列为(45，80,５5，4０，４2,85),则以第一个记录关键字４5为基准而得到一趟快速排序的结果是()。 （A）４0,42，45，55，80,8３ﻩ(B)42，４０，45,8０，８5，88ﻩ（C)4２,40，45，５５,８0,8５ (D）42,４0，4５,85,55,8０二、填空题(共２0分)设有一个顺序共享栈S[０：ｎ-１],其中第一个栈项指针ｔop1的初值为-1，第二个栈顶指针top２的初值为n,则判断共享栈满的条件是____________________。在图的邻接表中用顺序存储结构存储表头结点的优点是_＿＿________＿＿_＿_＿___。设有一个n阶的下三角矩阵A，假如按照行的顺序将下三角矩阵中的元素(涉及对角线上元素）存放在n(n+１)个连续的存储单元中,则A[i][j]与A[０][０]之间有_______个数据元素。栈的插入和删除只能在栈的栈顶进行，后进栈的元素必然先出栈,所以又把栈称为____＿_____表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必然先出队列,所以又把队列称为__＿＿_____表。设一棵完全二叉树的顺序存储结构中存储数据元素为ABＣDEＦ,则该二叉树的前序遍历序列为_＿＿___＿____,中序遍历序列为＿___＿__＿_＿_,后序遍历序列为___＿___＿＿__。设一棵完全二叉树有12８个结点，则该完全二叉树的深度为___＿__＿_，有___＿＿_＿_＿＿个叶子结点。设有向图G的存储结构用邻接矩阵Ａ来表达，则A中第i行中所有非零元素个数之和等于顶点i的________,第ｉ列中所有非零元素个数之和等于顶点i的＿_＿___＿_＿_。设一组初始记录关键字序列(k１,k2，……,kn)是堆,则对i=1，2，…,n／2而言满足的条件为_＿_____＿__＿__＿________＿＿＿__＿___。下面程序段的功能是实现冒泡排序算法，请在下划线处填上对的的语句。vｏｉdbubblｅ(ｉnｔr［n]){fｏr(ｉ=1;i<=n－1;i+＋）{fｏr（exｃｈａnｇｅ=0，ｊ=0；j＜＿__＿＿＿＿_____＿;ｊ++）ｉf(r[j］>r[j+1]){teｍｐ=r[j+1］;___＿____＿_＿___;r[j］=tｅｍp；exｃhanｇe=1;}ｉf(exｃｈanｇe==0)return；}｝下面程序段的功能是实现二分查找算法，请在下划线处填上对的的语句。structｒecord{intｋey;iｎtothers;};intｂisearｃh(ｓtrｕｃtreｃｏrdr[],inｔk）{intloｗ=0,ｍid,higｈ=n-1;whｉｌe(ｌow<=hｉgｈ）{_＿_____＿__＿___＿____＿_＿___＿＿＿____；iｆ(ｒ[ｍｉd］.key==ｋ)retuｒn(mid+１）;elseｉf(_______＿__＿_）hｉgh=miｄ-1;eｌｓｅlow=ｍid+1;}reｔurn(０)；}三、应用题（32分)设某棵二叉树的中序遍历序列为DBEAC,前序遍历序列为ＡBＤEC，规定给出该二叉树的的后序遍历序列。设无向图G(如右图所示）,给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。设一组初始记录关键字序列为(1５,17，１８,２2,35，51,60），规定计算出成功查找时的平均查找长度。设散列表的长度为8，散列函数H(k)=kmoｄ7，初始记录关键字序列为（2５,31,８,2７，13,6８),规定分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。四、算法设计题(28分)设计判断两个二叉树是否相同的算法。设计两个有序单链表的合并排序算法。数据结构试卷(六）一、选择题(30分)１．设一组权值集合W={2,3，4,５,６}，则由该权值集合构造的哈夫曼树中带权途径长度之和为(）。ﻩ(Ａ)２0ﻩ(B)30ﻩ(C)40 (Ｄ)452.执行一趟快速排序可以得到的序列是(）。ﻩ(A)［4１,12,34，4５,27]55[7２,63] (Ｂ)[45，34，１2,4１]55[72，６3,27] (C)［6３,12，34，４５,２7]55［41，７2] （D)[1２，２7，45，４1]5５[3４，63，７２］３．设一条单链表的头指针变量为hｅaｄ且该链表没有头结点,则其判空条件是（）。(A)ｈeａd＝=0 (B)heaｄ->neｘt==0(C)hｅaｄ->next==heａdﻩ(D)head!=04.时间复杂度不受数据初始状态影响而恒为O(ｎloｇ2n)的是()。ﻩ(A）堆排序 (B)冒泡排序ﻩ(C)希尔排序 (Ｄ)快速排序5.设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是（）。 （A)空或只有一个结点ﻩ(Ｂ)高度等于其结点数 (C)任一结点无左孩子 (D)任一结点无右孩子6．一趟排序结束后不一定可以选出一个元素放在其最终位置上的是(）。ﻩ(Ａ)堆排序ﻩ(B）冒泡排序 (Ｃ)快速排序ﻩ(D)希尔排序7．设某棵三叉树中有40个结点,则该三叉树的最小高度为（）。ﻩ(A)3 (B)4ﻩ(C）５ (D)６８.顺序查找不管在顺序线性表中还是在链式线性表中的时间复杂度为(）。 （A)O(n） （B）O(ｎ2) (C)O(ｎ1/２） （Ｄ)O（1og2n）９.二路归并排序的时间复杂度为（)。 （A)Ｏ(n)ﻩ(B)O（n2) (Ｃ)O(nlｏg2ｎ) (Ｄ)Ｏ(１og2ｎ)1０.深度为k的完全二叉树中最少有(）个结点。ﻩ（A)２k-1-1 (B)2k-1ﻩ(C)2k－１+1 (D)2k－111.设指针变量fronｔ表达链式队列的队头指针，指针变量rｅar表达链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为(）。 (A)froｎt->nｅｘt=ｓ；fｒｏｎt＝s；ﻩ(B)s-＞next=rear;ｒｅａr=s;ﻩ(Ｃ)ｒear-＞nexｔ＝s;rear=s； (Ｄ)ｓ－>ｎｅxt=fｒｏnt;front=s;12．设某无向图中有n个顶点e条边,则建立该图邻接表的时间复杂度为（）。ﻩ(A）O(ｎ+ｅ)ﻩ(Ｂ)O（n２) (C）Ｏ(nｅ)ﻩ(D)Ｏ(ｎ３)13.设某哈夫曼树中有1９９个结点,则该哈夫曼树中有（)个叶子结点。ﻩ(A）９9 (Ｂ)100 (C）101ﻩ(D）10214.设二叉排序树上有n个结点,则在二叉排序树上查找结点的平均时间复杂度为(）。ﻩ(Ａ）O(n） (Ｂ)O(ｎ２) (C）O(nlog２n)ﻩ（D)O(1og2n）１5．设用邻接矩阵A表达有向图G的存储结构，则有向图G中顶点i的入度为(）。ﻩ(Ａ)第i行非0元素的个数之和ﻩ(B)第i列非0元素的个数之和ﻩ（Ｃ)第i行0元素的个数之和ﻩ(D)第i列0元素的个数之和二、判断题(２0分)1．调用一次深度优先遍历可以访问到图中的所有顶点。（）2.分块查找的平均查找长度不仅与索引表的长度有关,并且与块的长度有关。（）3.冒泡排序在初始关键字序列为逆序的情况下执行的互换次数最多。(）4．满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。(）5．设一棵二叉树的先序序列和后序序列,则可以唯一拟定出该二叉树的形状。（)6．层次遍历初始堆可以得到一个有序的序列。()７.设一棵树T可以转化成二叉树BT，则二叉树BＴ中一定没有右子树。（)8.线性表的顺序存储结构比链式存储结构更好。(）9．中序遍历二叉排序树可以得到一个有序的序列。（）10.快速排序是排序算法中平均性能最佳的一种排序。(）三、填空题(3０分)1．for(i=1,t=1，s=0；ｉ＜=n;i++)｛t=t*i；s=ｓ＋t;}的时间复杂度为__＿＿＿＿__＿。2.设指针变量p指向单链表中结点A,指针变量ｓ指向被插入的新结点X,则进行插入操作的语句序列为________＿_________＿＿＿_____(设结点的指针域为neｘｔ)。３.设有向图G的二元组形式表达为G=（D，Ｒ），D={1，2,3,4,5},R={r}，r={＜1,2>,<2，４>,<4,5＞，＜1,３>,<3,2>，<3，5＞｝,则给出该图的一种拓扑排序序列＿_________。4.设无向图G中有n个顶点,则该无向图中每个顶点的度数最多是＿___＿____。５．设二叉树中度数为0的结点数为5０,度数为1的结点数为3０，则该二叉树中总共有＿＿＿_＿_＿个结点数。６.设Ｆ和R分别表达顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_＿＿_＿____________＿_＿_。７.设二叉树中结点的两个指针域分别为lｃhｉｌd和rchild，则判断指针变量ｐ所指向的结点为叶子结点的条件是＿＿＿__________＿_____＿＿_＿＿____＿＿___＿＿＿_＿__＿____。8．简朴选择排序和直接插入排序算法的平均时间复杂度为＿＿________＿。9.快速排序算法的空间复杂度平均情况下为_＿____＿___，最坏的情况下为＿__＿___＿__。10．散列表中解决冲突的两种方法是___＿____＿__＿_和＿_＿_＿_＿＿__＿＿_。四、算法设计题(２0分)设计在顺序有序表中实现二分查找的算法。设计判断二叉树是否为二叉排序树的算法。在链式存储结构上设计直接插入排序算法数据结构试卷(七)一、选择题(30分)1.设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。ﻩ(A)2ｎ (B)nﻩ（C)n/2 (D）n(n-１)2．设无向图Ｇ中有ｎ个顶点,则该无向图的最小生成树上有(）条边。 (A)nﻩ(B)ｎ-１ （C）2n （D）2n－１３.设一组初始记录关键字序列为（６0,8０，５5，4０,42,85）,则以第一个关键字４5为基准而得到的一趟快速排序结果是（)。ﻩ（A)4０,42，６0，55，8０,8５ (B)4２，45,55,60,85,８０ﻩ（C）42,40，55，６０,８0，８5 (D）42，４0,６0,85，5５,8０4．（）二叉排序树可以得到一个从小到大的有序序列。 （A)先序遍历ﻩ(Ｂ)中序遍历ﻩ(C)后序遍历 (Ｄ)层次遍历5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,则编号为ｉ结点的左孩子结点的编号为（)。 (A）2i+1 (Ｂ)2iﻩ（C）i／2 （D)２i－１6．程序段s=ｉ＝0；do｛ｉ=i＋１;s=ｓ+i；}whiｌe（ｉ<=ｎ）；的时间复杂度为()。 (A）Ｏ(n) (B）O(ｎloｇ2n) (C）O(n2）ﻩ(D）O(n3/２)7.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是(）。ﻩ(A）hｅad＝=0 ﻩ(B)heａd->next＝＝０ (C)hｅad－>nexｔ==head (D)heaｄ！=０８.设某棵二叉树的高度为１0,则该二叉树上叶子结点最多有（)。 （A)２0ﻩ(B)25６ﻩ(C)51２ (Ｄ)1024９．设一组初始记录关键字序列为(13，18，24，35，4７,50，６2，８３，90,１15，1３4),则运用二分法查找关键字90需要比较的关键字个数为(）。 (A)1ﻩ(B）2 (C)３ (D)410.设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为（）。 (Ａ)top=toｐ+1; (B)top=toｐ-１; （Ｃ）ｔｏp->ｎｅｘt=top;ﻩ(D)top=tｏp->next;二、判断题(20分)１.不管是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。()2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）3.设某堆中有n个结点,则在该堆中插入一个新结点的时间复杂度为O(log2n)。（)４.完全二叉树中的叶子结点只也许在最后两层中出现。（)５.哈夫曼树中没有度数为１的结点。()6.对连通图进行深度优先遍历可以访问到该图中的所有顶点。(）７.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()8．由树转化成二叉树，该二叉树的右子树不一定为空。（）9.线性表中的所有元素都有一个前驱元素和后继元素。(）10.带权无向图的最小生成树是唯一的。（)三、填空题（30分）设指针变量ｐ指向双向链表中的结点A,指针变量s指向被插入的结点X，则在结点A的后面插入结点Ｘ的操作序列为_____＿___=p；ｓ－＞right=ｐ->rigｈt；___＿_＿__＿＿=s；p->right->ｌｅft=ｓ;（设结点中的两个指针域分别为left和righｔ)。设完全有向图中有ｎ个顶点,则该完全有向图中共有_____＿_＿条有向条;设完全无向图中有n个顶点，则该完全无向图中共有＿_＿__＿__条无向边。设关键字序列为（Kl，K2,…，Ｋｎ),则用筛选法建初始堆必须从第_____＿个元素开始进行筛选。解决散列表冲突的两种方法是_______＿____＿___和_＿＿＿______________。设一棵三叉树中有５０个度数为0的结点,21个度数为2的结点，则该二叉树中度数为3的结点数有__＿＿__个。高度为ｈ的完全二叉树中最少有_____＿＿_个结点,最多有_＿__＿___个结点。设有一组初始关键字序列为（24，35,１2,２7，１８，26)，则第3趟直接插入排序结束后的结果的是＿_____＿__＿________＿___＿_＿____＿＿___。设有一组初始关键字序列为(24，35,12,27，18，2６)，则第3趟简朴选择排序结束后的结果的是＿＿_＿＿＿____＿_________＿__＿＿_＿_______。设一棵二叉树的前序序列为ABC,则有__＿___＿_＿＿____种不同的二叉树可以得到这种序列。下面程序段的功能是实现一趟快速排序，请在下划线处填上对的的语句。stｒuctrecord{intｋey;ｄaｔaｔｙpｅoｔｈerｓ;};voidｑuｉckpasｓ(strucｔreｃoｒdｒ[],ｉｎts,intt,iｎｔ&i){ｉnｔj＝t;stｒucｔreｃorｄx=r［s］；ｉ=s;ｗhｉlｅ(ｉ<j)｛ｗhilｅ(ｉ<j&&r[ｊ］.ｋey>x.key)ｊ=ｊ-1;if(i<j)｛r[i］=r[j］;ｉ＝i+1;}while(_____＿＿_______＿__＿＿＿)ｉ=i+１；if(ｉ<j)｛r[j]=ｒ[i];j=ｊ-１;｝｝__________＿____＿_；}四、算法设计题(20分)设计在链式结构上实现简朴选择排序算法。设计在顺序存储结构上实现求子串算法。设计求结点在二叉排序树中层次的算法。数据结构试卷(八）一、选择题(30分）字符串的长度是指()。 （A)串中不同字符的个数 (B）串中不同字母的个数 (C）串中所含字符的个数 (Ｄ)串中不同数字的个数建立一个长度为n的有序单链表的时间复杂度为（） (Ａ)O(n)ﻩ(B）O(１） (C)O(ｎ2）ﻩ(D）O(log2n)两个字符串相等的充要条件是（）。 (A）两个字符串的长度相等ﻩ(B)两个字符串中相应位置上的字符相等ﻩ(C）同时具有（A）和(B)两个条件ﻩ(D)以上答案都不对设某散列表的长度为10０，散列函数Ｈ(k）=k%P,则P通常情况下最佳选择（)。ﻩ（A)99ﻩ(Ｂ）９７ （C）９１ﻩ（D)９3在二叉排序树中插入一个关键字值的平均时间复杂度为()。ﻩ(A)O（n) (Ｂ)O(1oｇ2n） （C)O(nlog２n)ﻩ(D)Ｏ(n2)设一个顺序有序表A[1:1４]中有14个元素，则采用二分法查找元素Ａ[4]的过程中比较元素的顺序为（)。 (A)A[１],Ａ[2]，A[3],A［４］ﻩ(B）A[１]，A[14],A［７]，Ａ[4]ﻩ(C)A[7]，A[3］,A[5],A[4]ﻩ(D）A［7]，A[5]，A[3],A[4］设一棵完全二叉树中有65个结点,则该完全二叉树的深度为（)。ﻩ（A)8 (B)７ (C）6ﻩ(Ｄ)５设一棵三叉树中有2个度数为1的结点,2个度数为２的结点,2个度数为3的结点,则该三叉链权中有()个度数为0的结点。 （A)5ﻩ（B)6 (Ｃ)7ﻩ(D)８设无向图Ｇ中的边的集合E＝｛(ａ,ｂ),(a，e）,（a,ｃ）,(ｂ,ｅ),(ｅ，d)，(d,f）,（f，ｃ)｝,则从顶点ａ出发进行深度优先遍历可以得到的一种顶点序列为(）。ﻩ(Ａ）aedfcｂ (B)ａcfebdﻩ（C)ａｅｂcfd (D)aｅdfbc队列是一种()的线性表。 (Ａ)先进先出ﻩ(B)先进后出 （C）只能插入 (D)只能删除二、判断题（20分)假如两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。(）设初始记录关键字基本有序,则快速排序算法的时间复杂度为O（nｌog2ｎ)。()分块查找的基本思想是一方面在索引表中进行查找，以便拟定给定的关键字也许存在的块号，然后再在相应的块内进行顺序查找。()二维数组和多维数组均不是特殊的线性结构。（）向二叉排序树中插入一个结点需要比较的次数也许大于该二叉树的高度。()假如某个有向图的邻接表中第i条单链表为空,则第i个顶点的出度为零。(）非空的双向循环链表中任何结点的前驱指针均不为空。（）不管线性表采用顺序存储结构还是链式存储结构,删除值为X的结点的时间复杂度均为O(ｎ)。（）图的深度优先遍历算法中需要设立一个标志数组，以便区分图中的每个顶点是否被访问过。(）稀疏矩阵的压缩存储可以用一个三元组表来表达稀疏矩阵中的非０元素。（）三、填空题(30分)设一组初始记录关键字序列为(49，38,65,９７,76，１3，27,５０），则以ｄ=４为增量的一趟希尔排序结束后的结果为__＿__＿＿____＿_＿_____＿＿＿_＿___＿＿。下面程序段的功能是实现在二叉排序树中插入一个新结点,请在下划线处填上对的的内容。typedefstruｃtｎodｅ{ｉntdata；structnodｅ*ｌchild；sｔruｃｔnoｄｅ*rchiｌd;｝biｔrｅｅ；voidｂstinsert(bｉtreｅ*&t,ｉntｋ)｛if(t==０){_＿＿______________＿_＿_＿＿_＿＿＿＿;t->data=k;t->lｃhilｄ＝ｔ->rcｈｉld=0;}elｓeiｆ(t->datａ>k）bstinserｔ(t－>lchiｌｄ,k)；else__＿＿_＿_______＿＿________＿__;｝设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X,则在结点A的后面插入结点X需要执行的语句序列：s->ｎext=ｐ-＞nexｔ;_＿__＿__＿__＿__＿___;。设指针变量heaｄ指向双向链表中的头结点，指针变量ｐ指向双向链表中的第一个结点,则指针变量p和指针变量heａｄ之间的关系是p＝___＿__＿＿_和ｈｅad=_______＿__（设结点中的两个指针域分别为llｉｎｋ和ｒlink）。设某棵二叉树的中序遍历序列为ABCD,后序遍历序列为BADC，则其前序遍历序列为___＿__＿___。完全二叉树中第5层上最少有_______＿＿＿个结点，最多有____＿____个结点。设有向图中不存在有向边＜Vｉ,Vj>,则其相应的邻接矩阵Ａ中的数组元素A[i][j］的值等于＿_______＿___。设一组初始记录关键字序列为(4９，38，65,９7,７6,１3,27，5０),则第４趟直接选择排序结束后的结果为＿_＿______＿_＿_＿___＿_______＿___。设连通图G中有n个顶点e条边，则相应的最小生成树上有___＿＿＿____＿条边。设有一组初始记录关键字序列为（50,１６,２3,６8，94，7０,7３),则将它们调整成初始堆只需把1６与____＿_＿___＿互相互换即可。四、算法设计题(20分)设计一个在链式存储结构上记录二叉树中结点个数的算法。设计一个算法将无向图的邻接矩阵转为相应邻接表的算法。数据结构试卷(九)一、选择题(30分)1．下列程序段的时间复杂度为()。fｏr(i=0;i<ｍ;i+＋)fｏr(j=0；ｊ<ｔ;j++）c[i][j］=0;fｏｒ(i=０;i<m；i++）ｆoｒ（j=0；j<t;j++)ｆor（k＝0；k<n；k＋+)ｃ[i］[j]=c[i][j]＋ａ[ｉ]［ｋ]＊b［k］[j]; （A)Ｏ(m*n*t） （B)Ｏ(m+ｎ+t)ﻩ(Ｃ)Ｏ(ｍ＋n*t） (D)O(m＊t＋n)2．设顺序线性表中有n个数据元素,则删除表中第i个元素需要移动()个元素。 (A)n-i (B)n+l-i （C)n-1－i (D）i3.设F是由Ｔ1、Ｔ２和T3三棵树组成的森林，与F相应的二叉树为B，Ｔ１、T2和T3的结点数分别为N1、N2和Ｎ3，则二叉树Ｂ的根结点的左子树的结点数为（)。 （Ａ)Ｎ1-1ﻩ(B)N2-1ﻩ(C)N2＋Ｎ3 (D)Ｎ1+Ｎ34．运用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。(A)O(n) （Ｂ)O(nloｇ2n） (Ｃ)O(n2)ﻩ（D)Ｏ(1og2n)5．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为()。 (A）ｐ->rｉght=s；ｓ-＞ｌeft=p;p->right－>left=s；s->ｒｉght＝ｐ-＞rｉｇhｔ; (Ｂ)s－>ｌeｆt＝p；s->right=p->rigｈt;p－＞rｉｇhｔ=s；ｐ－＞riｇｈt－>ｌeｆt＝s; (C)p－>rｉgｈｔ=s；p->ｒｉgｈt-＞left=s；s－＞leｆｔ=p；ｓ－＞right=p-＞right； (D）s->left=ｐ；s->ｒight＝p-＞rigｈt;p->right->left=ｓ；p-＞right=s;6.下列各种排序算法中平均时间复杂度为O(n2)是（)。ﻩ（A)快速排序 (B)堆排序ﻩ(C)归并排序ﻩ（D)冒泡排序7．设输入序列1、2、3、…、n通过栈作用后,输出序列中的第一个元素是n,则输出序列中的第ｉ个输出元素是(）。ﻩ（Ａ)ｎ-i (B)ｎ-1-ｉ （C)n+l-ｉ (D)不能拟定８．设散列表中有m个存储单元，散列函数H(key)＝ｋey％p，则p最佳选择（)。ﻩ(A)小于等于m的最大奇数 (B）小于等于m的最大素数 (Ｃ）小于等于ｍ的最大偶数 (D)小于等于m的最大合数9.设在一棵度数为3的树中，度数为3的结点数有2个,度数为2的结点数有1个,度数为１的结点数有2个，那么度数为0的结点数有（）个。ﻩ(A)４ (B)5 （C)6ﻩ(D)７10．设完全无向图中有ｎ个顶点,则该完全无向图中有()条边。(A)n(n－1)/２ﻩ（B)ｎ（n－1) (Ｃ)ｎ(n＋1)/2ﻩ(Ｄ)(n－1)／211．设顺序表的长度为n，则顺序查找的平均比较次数为（)。 (A)ｎﻩ(B)n／2ﻩ（C)(n＋1)/２ (Ｄ）(n-1)/212.设有序表中的元素为（13，18,24，３5,４7,50,６2),则在其中运用二分法查找值为24的元素需要通过(）次比较。ﻩ(A)１ﻩ（B)2 (C)3 (D)4１3.设顺序线性表的长度为30,提成５块,每块６个元素，假如采用分块查找，则其平均查找长度为()。ﻩ(A)６ﻩ(B）11 (C)5ﻩ(D)6．514.设有向无环图Ｇ中的有向边集合E={<1，2＞，＜２,３>,<3,4>,<1，4＞}，则下列属于该有向图Ｇ的一种拓扑排序序列的是()。 (A)１，２，3,４ﻩ（Ｂ)２，3，4，１ (Ｃ）1，4，2,3ﻩ（D)1，2，４，３15．设有一组初始记录关键字序列为（34,76，４5,1８,2６，54，92),则由这组记录关键字生成的二叉排序树的深度为()。 (A）4ﻩ(Ｂ）5ﻩ(C）６ﻩ(D）7二、填空题(30分)设指针p指向单链表中结点A,指针ｓ指向被插入的结点Ｘ,则在结点A的前面插入结点X时的操作序列为:1)s->ｎｅxt=__＿____＿___;２)p－>next=s；３）ｔ=p-＞dａｔa；4）p->data=_____＿_＿___；5)ｓ->datａ＝t；设某棵完全二叉树中有1０0个结点,则该二叉树中有___＿_____＿____个叶子结点。设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置,队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储____＿_＿队列元素。对一组初始关键字序列（40，50，95,20，15，７0，6０，４5，１0)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_____＿___＿，在整个排序过程中最多需要进行＿＿＿_______趟排序才可以完毕。在堆排序和快速排序中,假如从平均情况下排序的速度最快的角度来考虑应最佳选择_____＿___排序，假如从节省存储空间的角度来考虑则最佳选择___＿____排序。设一组初始记录关键字序列为（20,12,４２,31,１8，１4,28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是________＿＿_＿_＿_____＿__＿_＿____＿_。设一棵二叉树的中序遍历序列为BＤＣA,后序遍历序列为ＤBAC，则这棵二叉树的前序序列为__＿____＿_＿________＿＿。设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为７、１9、2、6、３２、3、21、10，根据这些频率作为权值构造哈夫曼树,则这棵哈夫曼树的高度为_______＿_＿_＿＿＿__。设一组记录关键字序列为(８0，７0，33,65,24，56,48)，则用筛选法建成的初始堆为___＿＿_____＿＿______＿__＿_。设无向图G(如右图所示)，则其最小生成树上所有边的权值之和为＿_＿_＿_＿__________。三、判断题（2０分）有向图的邻接表和逆邻接表中表结点的个数不一定相等。（)对链表进行插入和删除操作时不必移动链表中结点。()子串“ABC”在主串“AABＣAＢCＤ”中的位置为2。（)若一个叶子结点是某二叉树的中序遍历序列的最后一个结点,则它必是该二叉树的先序遍历序列中的最后一个结点。()希尔排序算法的时间复杂度为Ｏ(n2)。()用邻接矩阵作为图的存储结构时,则其所占用的存储空间与图中顶点数无关而与图中边数有关。()中序遍历一棵二叉排序树可以得到一个有序的序列。()入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。()顺序表查找指的是在顺序存储结构上进行查找。()堆是完全二叉树,完全二叉树不一定是堆。（）五、算法设计题（２0分)设计计算二叉树中所有结点值之和的算法。设计将所有奇数移到所有偶数之前的算法。设计判断单链表中元素是否是递增的算法。数据结构试卷(十）一、选择题(24分)1.下列程序段的时间复杂度为(）。ｉ=０,s=0;whilｅ（s＜ｎ){ｓ＝s+i；ｉ++；} (A)Ｏ(n1/2) (B)O(n1/3) （Ｃ）O(n）ﻩ（D)O(ｎ2）2.设某链表中最常用的操作是在链表的尾部插入或删除元素,则选用下列(）存储方式最节省运算时间。 （Ａ)单向链表ﻩﻩ（B)单向循环链表(C)双向链表ﻩﻩ（Ｄ)双向循环链表３.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点Ｘ，则在结点A和结点B插入结点X的操作序列为（）。(A)s->nｅxt=p->next；p－>neｘｔ=-s； (B)q－＞ｎexｔ=s；s－>nｅxt＝ｐ；（Ｃ)p－>ｎext=s-＞next;s->nexｔ=p；ﻩ(Ｄ)p-＞ｎext=s;s-＞ｎexｔ=q;4.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为（)。(A)5，３，4,6,1，２ (B）３，２，5,6,4,１(Ｃ)3,1，2,5,4,6 (D)1,5，4，6，2，3５.设有一个10阶的下三角矩阵A（涉及对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间,则A[５][４］地址与A[0][0]的地址之差为（)。ﻩ（A）10ﻩ(B)19ﻩ(C）28ﻩ（Ｄ)556.设一棵ｍ叉树中有N1个度数为1的结点,Ｎ2个度数为2的结点，……,Nm个度数为ｍ的结点，则该树中共有(）个叶子结点。 (A） (B) (C) (D)7.二叉排序树中左子树上所有结点的值均（）根结点的值。ﻩ(A）< (Ｂ)>ﻩ（Ｃ)=ﻩ（D)!=8.设一组权值集合W＝（15，3,14，2,6,9，16，１7),规定根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权途径长度为()。 （A)１29 (B）219ﻩ（C）189 (D）229９.设有n个关键字具有相同的Ｈash函数值,则用线性探测法把这n个关键字映射到HAＳH表中需要做（)次线性探测。ﻩ（A）ｎ2 (B）n(n+1） （C)n（n+1)/2ﻩ(D）n（n-１）/21０.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为ｎ，则这棵二叉中共有（）个结点。 （A)２ｎ （B)n＋l （C)2ｎ-1ﻩ(Ｄ)２ｎ+l11.设一组初始记录关键字的长度为８，则最多通过（）趟插入排序可以得到有序序列。 (Ａ）6ﻩ(B)7ﻩ(C）8ﻩ（D）912．设一组初始记录关键字序列为（Q，Ｈ,C,Y,P,A，M，S，Ｒ,D，F，X),则按字母升序的第一趟冒泡排序结束后的结果是（)。(Ａ)F，H,C，Ｄ，P，A，M,Ｑ，Ｒ,Ｓ，Ｙ，Ｘ（B)P，Ａ,C,S，Q，D,Ｆ，X，R,Ｈ，M，Y（C）A,D,Ｃ，Ｒ，F,Ｑ,M,S,Y，P,Ｈ，X（Ｄ)H，Ｃ，Ｑ,P,A，Ｍ,Ｓ,Ｒ，D，F，X,Ｙ二、填空题(４８分，其中最后两小题各6分）设需要对5个不同的记录关键字进行排序,则至少需要比较＿______＿_＿___次，至多需要比较＿＿___________次。快速排序算法的平均时间复杂度为_______＿____，直接插入排序算法的平均时间复杂度为___________。设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_＿_______次。设在长度为20的有序表中进行二分查找,则比较一次查找成功的结点数有___＿___＿_个，比较两次查找成功有结点数有_______＿_个。设一棵m叉树脂的结点数为ｎ，用多重链表表达其存储结构，则该树中有____＿__＿_个空指针域。设指针变量p指向单链表中结点A，则删除结点A的语句序列为:q=p－>ｎexｔ;p->datａ=q->ｄata;p->neｘt=_____＿____＿；feee(q)；数据结构从逻辑上划分为三种基本类型:_______＿＿＿_、__＿_______和_______＿___。设无向图Ｇ中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为__＿____＿_;用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为__＿__＿__＿。设散列表的长度为8，散列函数H（ｋ)=k%7，用线性探测法解决冲突，则根据一组初始关键字序列(8，１5,１6，22，３0，３２)构造出的散列表的平均查找长度是_＿__＿＿__。设一组初始关键字序列为（３８，65,97，７６,13，27，10)，则第3趟冒泡排序结束后的结果为＿＿_＿____＿____＿______＿。设一组初始关键字序列为（38，65,９7,76,13，27，１０）,则第3趟简朴选择排序后的结果为______＿___＿______＿__＿_。设有向图G中的有向边的集合E=｛＜1，2>，＜2，3>,＜1，4＞，<4，5>，<5，3>，<４,６＞，<6,5>},则该图的一个拓扑序列为＿＿____________＿＿＿________。下面程序段的功能是建立二叉树的算法,请在下划线处填上对的的内容。typedefstrｕcｔnoｄe｛intdatａ;ｓtructnoｄe*lcｈilｄ;____＿＿＿＿＿__＿____;}biｔreｅ;voidcreateｂitreｅ（bitｒee＊&ｂｔ){scanf(“%c”，＆ch）；if(ch==＇#')___＿______＿;ｅlsｅ｛bt=(ｂｉtree*)ｍａllｏc(ｓiｚeof（biｔree)）;bt-＞ｄａta=ch；_______＿;ｃｒｅatebｉｔｒeｅ（bt->ｒchiｌd);}}下面程序段的功能是运用从尾部插入的方法建立单链表的算法，请在下划线处填上对的的内容。tｙpedefstructnode{intdata;struｃtnｏde*next;}lklist;ｖoidｌｋlisｔｃreate(＿＿＿＿__＿__＿___*＆ｈead）{fｏr(i＝1;i<=n;ｉ＋+）{p=（lklist*)ｍａlｌｏc（sizeｏf(lｋlｉst）)；scanｆ(“％ｄ”,＆（p->ｄatａ));p->nｅxｔ=0;if(i==1)head=ｑ＝p;elｓe{ｑ->ｎext=p；_＿_____＿＿＿_＿;}｝｝三、算法设计题（22分)设计在链式存储结构上合并排序的算法。设计在二叉排序树上查找结点X的算法。设关键字序列(k1，k2,…,kn-1)是堆，设计算法将关键字序列(k１,k2,…,kn-1，x)调整为堆。ﻬ数据结构试卷（一）参考答案选择题（每题2分，共20分）1.A2.Ｄ3．D４．C5.C６.Ｄ7．D８．C９．D１０.A二、填空题（每空１分，共26分）对的性易读性强壮性高效率O(n）933-134Ｘ＊＋2Y＊3/－2ｎn－1n＋1ｅ2ｅ有向无回路n(n-1)/2ｎ（n-1)(1２，４０）()(74）(23,５5，63)增长1O(lｏg２n)Ｏ（nlog２n）归并三、计算题（每题6分，共2４分)线性表为:(78，50，４0,6０,34，９0)邻接矩阵：邻接表如图１1所示：图11用克鲁斯卡尔算法得到的最小生成树为:(１,2)3,(4,6)4,(１，３)５,（１,4)8,（２,5)10，（4，7）2０见图1244444222552852834528434444422255285283452843图1２读算法（每题７分，共14分)(１)查询链表的尾结点(2）将第一个结点链接到链表的尾部，作为新的尾结点（3)返回的线性表为（ａ2,ａ3,…,an,a1)递归地后序遍历链式存储的二叉树。法填空（每空2分，共8分)trｕeBSＴ->lｅｆtBST->right编写算法（8分）iｎtCountX(ＬNｏde*HL,EｌemTypex)｛iｎti＝０；ＬNoｄe*p＝HＬ;/／ｉ为计数器whiｌe(ｐ！=NＵＬＬ){if(Ｐ－>ｄata==x）i++;p=p->next;｝//wｈｉlｅ,出循环时i中的值即为x结点个数returｎi；}//ＣoｕｎtX数据结构试卷(二）参考答案一、选择题１.D ﻩ2．B 3.C ﻩ4.A ﻩ５.A 6.Cﻩ 7.B 8.C二、填空题构造一个好的ＨAＳＨ函数，拟定解决冲突的方法stａck.top＋+,stａck．s［stａｃk．toｐ]=x有序O(n2），O(