数据结构参考

1、数据结构模拟卷A一、选择题1.在一个长度为n的次序表的任一地点插入一个新元素的渐进时间复杂度为（A）。A.O(n)B.O(n/2)C.O(1)D.O(n2)2.带头结点的单链表first为空的判断条件是：（B）。A.first=NULL;B.first-link=NULL;C.first-link=first;D.first!=NULL;3.从逻辑上能够把数据结构分为（C）两大类。A动向结构、静态结构B次序结构、链式结构C线性结构、非线性结构D初等结构、结构型结构4.在系统实现递归调用时需利用递归工作记录保留实质参数的值。在传值参数情况，需为对应形式参数分派空间，以寄存实质参数的副本；在引用参

2、数情况，需保留实质参数的（D），在被调用程序中可直接操控实质参数。A.空间B.副本C.返回地点D.地点5.以下数据结构中，哪一个是线性结构（D）。A广义表B.二叉树C.稀少矩阵D.串6.以部下于逻辑结构的是（C）。A次序表B.哈希表C.有序表D.单链表对于长度为9的有序次序表，若采纳折半搜寻，在等概率状况下搜寻成功的均匀搜寻长度为（C）的值除以9。A.20B.18C.25D.228.在有向图中每个极点的度等于该极点的（C）。A.入度B.出度C.入度与出度之和D.入度与出度之差9.在鉴于排序码比较的排序算法中，（C）算法的最坏状况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C

3、.合并排序D.迅速排序10.当的值较小时，散列储存往常比其余储存方式拥有（B）的查找速度。.A.较慢B.较快C.同样D.不一样二、填空题1.二维数组是一种非线性结构，此中的每一个数组元素最多有_2_个直接前驱（或直接后继）。2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩寄存于一个一维数组B中，A00寄存于B0中。对于随意给定数组元素BK，它应是A中第_(K+1)/3_行的元素。3.链表对于数据元素的插入和删除不需挪动结点，只要改变有关结点的_指针_域的值。4.在一个链式栈中，若栈顶指针等于NULL则为_空栈_。主程序第一次调用递归函数被称为外面调用，递归函数自己调用自己被称为内部调用，

4、它们都需要利用栈保留调用后的_返回_地点。在一棵树中，_叶子_结点没有后继结点。7.一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)，结点f的层数为_3_。假设根结点的层数为0。在一棵AVL树（高度均衡的二叉搜寻树）中，每个结点的左子树高度与右子树高度之差的绝对值不超出_1_。n(n0)个极点的无向图最多有_n(n-1)/2_条边，最罕有_0_条边。10.在索引储存中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_浓密_索引，若对应数据对象表中的若干个表项，则称此索引为_稀少_索引。三、判断题1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性

5、的也不是树形的(对)2.链式储存在插入和删除时需要保持物理储存空间的次序分派，不需要保持数据元素之间的逻辑次序(错)3.在用循环单链表表示的链式行列中，能够不设队头指针，仅在链尾设置队尾指针(对)4.往常递归的算法简单、易懂、简单编写，并且履行的效率也高(错)一个广义表的表尾老是一个广义表(对)当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填充到堆顶地点，而后再按条件把它逐层向下调整，直到调整到适合地点为止(对)对于一棵拥有n个结点，其高度为h的二叉树，进行任一种序次遍历的时间复杂度为O(h)(错).8.储存图的毗邻矩阵中，毗邻矩阵的大小不只与图的极点个数有关，并且与图的边数也有关(

6、错)直接选择排序是一种稳固的排序方法(错)闭散列法往常比开散列法时间效率更高(错)四、运算题1.设有一个1010的对称矩阵A，将其下三角部分按行寄存在一个一维数组B中，A00寄存于B0中，那么A85寄存于B中什么地点。解：依据题意，矩阵A中当元素下标I与J知足IJ时，随意元素AIJ在一维数组B中的寄存地点为I*(I+1)/2+J，所以，A85在数组B中地点为8*(8+1)/2+5=41。2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，此中while循环有错，请从头编写出正确的while循环。intcount(ListNode*Ha,ElemTypex)/Ha为不带头结点的单链表的头

7、指针intn=0;while(Ha-link!=NULL)Ha=Ha-link;if(Ha-data=x)n+;returnn;解：while(Ha!=NULL)if(Ha-data=x)n+;Ha=Ha-link;已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G.后序序列：解：后序序列：C,B,F,E,I,J,H,G,D,A4.已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)次序储存于一维数组a12中，依据折半搜寻过程填写成功搜寻下表中所给元素34,5

8、6,58,63,94时的比较次数。3456586394元素值比较次数解：判断结果元素值3456586394比较次数0213445.设散列表为HT17,待插入重点码序列为Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec，散列函数为H(key)=i2，此中，i是重点码第一个字母在字母表中的序号。现采纳线性探查法解决矛盾。字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526试画出相应的散列表；H(Jan)=102=5，成功.H(Feb)=62=3，成

9、功.H(Mar)=132=6，成功.H(Apr)=12=0，成功.H(May)=132=6，=7，成功，H(June)=102=5，=6，=7，=8，成功.H(July)=102=5，=6，=7，=8，=9，成功.H(Aug)=12=0，=1，成功.H(Sep)=192=9，=10，成功.H(Oct)=152=7，=8，=9，=10，=11，成功.H(Nov)=142=7，=8，=9，=10，=11，=12，成功.H(Dec)=42=2，成功.相应的散列表：13AprAugDecFebJanMarMayJuneJulySepOctNov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2

10、)(5)(6).计算等概率下搜寻成功的均匀搜寻长度；1/12*(1+2+1+1+1+1+2+4+5+2+5+6)=31/12五、算法设计题已知二叉树中的结点种类用BinTreeNode表示，被定义为:structBTreeNodechardata;BinTreeNode*leftChild,*rightChild;此中data为结点值域，leftChild和rightChild分别为指向左、右儿女结点的指针域，依据下边函数申明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假设参数BT初始指向这棵二叉树的根结点。intBTreeCount(BinTreeNode*BT);解：intBT

11、reeCount(BinTreeNode*BT)if(BT=NULL)return0;/2分elsereturnBTreeCount(BT-leftChild)+BTreeCount(BT-rightChild)+1;/4分.数据结构模拟卷B一、单项选择题1以下与数据的储存结构没关的术语是（C）。A循环行列B.链表C.哈希表D.栈2以下数据结构中，哪一个是线性结构（D）。A广义表B.二叉树C.稀少矩阵D.串3以下那一个术语与数据的储存结构没关？（B）。A栈B.哈希表C.线索树D.双向链表4在下边的程序段中，对x的赋值语句的频度为（C）。FORi:=1TOnDOFORj:=1TOnDOx:=x+

12、1;AO(2n)BO(n)CO(n2)DO(log2n)5.下边对于线性表的表达中，错误的选项是哪一个（B）。A线性表采纳次序储存，一定占用一片连续的储存单元。B线性表采纳次序储存，便于进行插入和删除操作。C线性表采纳链接储存，不用占用一片连续的储存单元。D线性表采纳链接储存，便于插入和删除操作。6线性表是拥有n个（C）的有限序列（n0）。A表元素B字符C数据元素D数据项E信息项7.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）储存方式最节俭时间。A次序表B双链表C带头结点的双循环链表D单循环链表8.某线性表中最常用的操作是在最后一个元素以后插入一个元素

13、和删除第一个元素，则采纳（D）储存方式最节俭运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表下边给出的四种排序法中(D)排序法是不稳固性排序法。A.插入B.冒泡C.二路合并D.聚积.以下排序算法中，此中（D）是稳固的。A.堆排序，冒泡排序B.迅速排序，堆排序C.直接选择排序，合并排序D.合并排序，冒泡排序11.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(D)。A-A+B*C/DEB.-A+B*CD/EC-+*ABC/DED.-+A*BC/DE12.算术表达式a+b*（c+d/e）转为后缀表达式后为（B）。Aab+cde/

14、*Babcde/+*+Cabcde/*+Dabcde*/+/+*C*-ABDEFG二、填空题，在横线处填写适合内容数据结构的储存结构包含次序、_链接_、索引和散列等四种。在程序运转过程中能够扩大的数组是_动向_分派的数组。这类数组在申明它时需要使用数组指针。在链表中进行插入和删除操作的效率比在次序储存结构中进行同样操作的效率高。4.栈是一种限制在表的一端进行插入和删除的线性表，又被称为_后出先进_表。5.假如一个对象部分地包含自己，或自己定义自己，则称这个对象是_递归_的对象。6.一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)，结点f的层数为_3_。假设树根结点的

15、层数为0。一棵树依据左儿女-右兄弟表示法变换成对应的二叉树，则该二叉树中树根结点必定没有_右_儿女。向一棵二叉搜寻树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_左子树_上。9.设图G=(V,E)，V=1,2,3,4,E=,，从极点1出发，对图G进行广度优先搜寻的序列有_2_种。10.每次直接或经过基准元素间接比较两个元素，若出现逆序摆列就互换它们的地点，这类排序方法叫做_互换_排序。.11.迅速排序在均匀状况下的空间复杂度为_O(log2n)_。12.若对长度n=10000的线性表进行二级索引储存，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为_50

16、0_。三、判断题在次序表中进行次序搜寻时，若各元素的搜寻概率不等，则各元素应依据搜寻概率的降序摆列寄存，则可获得最小的均匀搜寻长度（对）在二叉搜寻树中，若各结点的搜寻概率不等，使得搜寻概率越小的结点离树根越近，则获得的是最优二叉搜寻树（错）3.对于AOE网络，加快任一重点活动都能使整个工程提早达成（错）4.直接选择排序是一种稳固的排序方法（错）5.闭散列法往常比开散列法时间效率更高（错）6.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户依据应用需要成立的（对）7.次序表和一维数组同样，都能够按下标随机（或直接）接见（对）8.在一个次序储存的循环行列中,队头指针指向队头元素的后一个地点（错）

17、9.用非递归方法实现递归算法时必定要使用递归工作栈（错）在一棵二叉树中，假设每个结点只有左儿女，没有右儿女，对它分别进行中序遍历和后序遍历，则拥有同样的结果（对）四、运算题1.设有一个二维数组A1020，按行寄存于一个连续的储存空间中，A00的储存地点是200，每个数组元素占1个储存字，则A62的储存字地点是多少。A62的储存字地点：322答案说明：按行储存时，计算Aij地点的公式为LOC(i,j)=LOC(0,0)+(i*n+j)*d此中首地点LOC(0,0)=200,每个数组元素的储存占用数d=1,二维数组的列数n=20，依据题意，元素A62的储存地点为LOC(6,2)=200+(6*20

18、+2)*1=3222.已知一棵二叉树的中序和后序序列以下，求该二叉树的高度（假设空树的高度为-1）和度为2、度为1及度为0的结点个数。中序序列：c,b,d,e,a,g,i,h,j,f.后序序列：c,e,d,b,i,j,h,g,f,a求解一下问题：高度：4度为2的结点数：3度为1的结点数：3度为0的结点数：43.假设一组记录为(36,75,83,54,12,67,60,40)，将按序次把每个结点插入到初始为空的一棵AVL树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？左单旋转结点个数：1右单旋转结点个数：0先左后右双旋转结

19、点个数：1先右后左双旋转结点个数：0不调整结点个数：6已知一个带权图的极点集V和边集G分别为：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12;试依据迪克斯特拉(Dijkstra)算法求出从极点0到其余各极点的最短路径，在下边填写对应的路径长度。极点：0123456路径长度：01610142521315.已知一个数据表为36,25,25*,62,40,53，请写出在进行迅速排序的过程中每次区分后数据表的变化。.362525*62405325*

20、253662405325*253653406225*2536405362五、算法设计题1设有一个表头为first的单链表。试设计一个算法，经过遍历一趟链表，将链表中全部结点按逆序链接。解答1templatevoidList:Tnerse()if(first=NULL)return;ListNode*p=firstlink;,*pr=NULL;While(p!=NULL)Firstlink=pr;Pr=first;first=p;p=plink;first-link=pr;解答2templatevoidList:Tnerse()ListNode*p,*head=newListNode();Whi

21、le(first!=NULL)P=first;first=firstlink;plink=headlink;headlink=p;first=headlink;deletehead;.数据结构模拟卷C一、单项选择题1数据结构是（D）。A一种数据种类B数据的储存结构C一组性质同样的数据元素的会合D互相之间存在一种或多种特定关系的数据元素的会合2算法剖析的目的是（B）。A鉴识数据结构的合理性B评论算法的效率C研究算法中输入与输出的关系D鉴识算法的可读性3在线性表的以下运算中，不改变数据元素之间结构关系的运算是（D）。A插入B删除C排序D定位4若进栈序列为1，2，3，4，5，6，且进栈和出栈能够穿插

22、进行，则可能出现的出栈序列为（B）。A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，15设串sl=DataStructureswithJava,s2=it，则子串定位函数index(s1,s2)的值为（D）。A15B16C17D186二维数组A89按行优先次序储存，若数组元素A23的储存地点为1087，A47的储存地点为1153，则数组元素A67的储存地点为（A）。A1207B1209C1211D12137在按层次遍历二叉树的算法中，需要借助的协助数据结构是（A）。.A行列B栈C线性表D有序表8在随意一棵二叉树的前序序列和后序序列中，各叶子之间的相

23、对序次关系（B）。A不必定同样B都同样C都不同样D互为逆序9若采纳孩子兄弟链表作为树的储存结构，则树的后序遍历应采纳二叉树的（C）。A层次遍历算法B前序遍历算法C中序遍历算法D后序遍历算法10若用毗邻矩阵表示一个有向图，则此中每一列包含的1的个数为（A）。A图中每个极点的入度B图中每个极点的出度C图中弧的条数D图中连通重量的数量11图的毗邻矩阵表示法合用于表示（C）。A无向图B有向图C浓密图D稀少图12在对n个重点字进行直接选择排序的过程中，每一趟都要从无序区选出最小重点字元素，则在进行第i趟排序以前，无序区中重点字元素的个数为（D）。AiBi+1Cn-iDn-i+1二、填空题1栈是_特别_的

24、线性表，其运算依据_后进先出_的原则。2_栈_是限制仅在表尾进行插入或删除操作的线性表。一个栈的输入序列是：1，2，3则不行能的栈输出序列是_3，1，2_。4二叉树由_根结点、左子树、右子树_三个基本单元构成。5在二叉树中，指针p所指结点为叶子结点的条件是P-Lchild=NULL&P-Rchild=NULL_。6拥有256个结点的完整二叉树的深度为_9_。7已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_12_个叶子结点。8若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是重点字的_比较_和记录的_挪动_。.9.分别采纳堆排序，迅速排序，冒泡排序和合并排序，对初态为有序的表，则最省时间的是_冒泡排序_算法，最费时间的是_迅速排序_算法。10不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_选择排序_，在排序算法的最后一趟开始以前，全部元素都可能不在其最后地点上的排序算法是_合并排序_。三、解答题1某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。2已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。1）画出该二叉树；2）画出与（1）求得的二叉树对应的丛林。.3已知