本科计算机信息第三学期数据结构参考答案

1、数据结构模拟卷A、选择题1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A）。2A.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.串A.顺序表B.哈希表C.有序表单链表D.7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长6.以下属于逻辑结构的是（C）。B.18C.2A5.20D.22度为（C）的值除以9。8. 在有向图中每个顶点的度等于该顶点的（C）。A.入度B.出度9.在基于排序码比较的排序算法中，C.入度与出度之和（C）算法的最坏情况下的时间复杂度不高于D.入度与出度之差A.

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

4、用自己被称为内部调用，它们都需要利用栈保存调用后的返回_地址。6. 在一棵树中，_叶子_结点没有后继结点。7. 一棵树的广义表表示为a（b（c,d（e,f）,g（h）,i（j,k（x,y），结点f的层数为3。假定根结点的层数为0。8. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过1_。9. n（n>0）个顶点的无向图最多有n（n-1）/2_条边，最少有_0条边。10. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_稠密索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏索引。三、判断题1. 数组是一种复杂的

5、数据结构，数组元素之间的关系既不是线性的也不是树形的（对）2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序（错）3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针（对）4. 通常递归的算法简单、易懂、容易编写，而且执行的效率也高（错）5. 一个广义表的表尾总是一个广义表（对）6. 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止（对）7. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）（错）8. 存储图的邻接矩阵中

6、，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关（错）9. 直接选择排序是一种稳定的排序方法（错）10?闭散列法通常比开散列法时间效率更高（错）设有一个 10 10 的B 中， A00四、运算题1.对称矩阵A,将其下三角部分按行存放在一个一维数组存放于B0中，那么A85存放于B中什么位置。解：根据题意，矩阵A中当元素下标I与J满足I>J时，任意元素AIJ在一维数组B中的存放位置为I*（I+1）/2+J，因此，A85在数组B中位置为8*（8+1）/2+5=41。x 的结点数的算法，其中 while 循环有错 ,2. 这是一个统计单链表中结点的值等于给定值请重新编写出正确的whi

7、le循环。intcount(ListNode*Ha,ElemTypex)/Ha为不带头结点的单链表的头指针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->link3. 已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列:A,B,C,D,E,F,G,H,I,J已知一个有序 顺序存储于34, 56, 58, 63, 94中序序列：C,B,A,E,F,D,I,H,J,G后序序列：解：后序序列：C,

8、B,F,E,I,J,H,G,D,A4.表(15,26,34,39,45,56,58,63,74,76,83,94)元素值3456586394比较次数时的比较次数。解：判断结果元素值比较次数34565863940213445.设散列表为 HT17,待插入关键码序列为 Jan, Feb, Mar, Apr, May, June, July,Aug, Sep, Oct, Nov, Dec ,散列函数为 H (key) = li 2 ,其中，i是关键码第字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号141516171819202122232425

9、26个字母在字母表中的序号。现采用线性探查法解决冲突。(1)试画出相应的散列表H(Jan) = _10 2 = 5 ,成功.H(Mar) = I113 2 = 6 ,成功H(May) = I113 2 = 6 , = 7,成功,H(Feb) = _6 2 = 3 ,成功？H(Apr) = _1 2 = 0，成功.H(June) = I110 2 = 5 , = 6,=7,=8,成功H(July)= I110 2 = 5 ,H(Aug)= ：_1 2 = 0 ,=6, = 7 , =8, = 9 ,成功.1,成功？ H(Sep) = ll_19 2 = 9，=:10,成功H(Oct)= _15

10、2 = 7 , = = 8H(Nov)= I114 2 = 7, =8=9, =10, = 11 ,成功？=9, =10, = 11 , = 12 ,成功？H(Dec)= H4 2 = 2 ,成功.AprAugDecFebJanMarMayJuneJulySepOctNov相应的散列表012345678910111213一维数组a12中，根据折半搜索过程填写成功搜索下表中所给元素(1)(5)(2)(5)(6)(2)计算等概率下搜索成功的平均搜索长度;1/12*(1+2+1+1+1+1+2+4+5+2+5+6)=31/12五、算法设计题已知二叉树中的结点类型用BinTreeNode表示，被定义为

11、：structBTreeNodechardata;BinTreeNode*leftChild,*rightChild;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。intBTreeCount(BinTreeNode*BT);解：intBTreeCount(BinTreeNode*BT)if(BT=NULL)return0;2分elsereturnBTreeCount(BT->leftChild)+BTreeCount(BT-&

12、gt;rightChild)+1;4分数据结构模拟卷B一、单项选择题1 .以下与数据的存储结构无关的术语是(A.循环队列B.链表C.哈希表D.2 .以下数据结构中,哪一个是线性结构(A.广义表B.二叉树C.稀疏矩阵D.3 .以下那一个术语与数据的存储结构无关?A.栈B.哈希表C.线索树D.双向链表4 .在下面的程序段中，对x的赋值语句的频度为(C)FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)5 .下面关于线性表的叙述中，错误的是哪一个(B)。A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，

13、便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。6 .线性表是具有n个(C)的有限序列(n>0)。A.表元素B.字符C.数据元素D.数据项E.信息项7 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用(A)存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表8 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用(D)存储方式最节省运算时间。A.单链表B?仅有头指针的单循环链表C?双链表D?仅有尾指针的单循环链表9 .下面给出的四

14、种排序法中(D)排序法是不稳定性排序法。A.插入B.冒泡C.二路归弁D.堆积10.下列排序算法中，其中(DA.堆排序，冒泡排序C.直接选择排序，归弁排序)是稳定的。B.快速排序，堆排序D. 归弁排序，冒泡排序11.已知一算术表达式的中缀形式为A+B*C-D/E ,后缀形式为 ABC*+DE/-,其前缀形式为(D )。A. -A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DEabcde/*+ D . abcde*/+A. ab+cde/* Babcde/+*+ C12.算术表达式a+b*(c+d/e)转为后缀表达式后为(B)二、填空题，在横线处填写合适内容

15、1. 数据结构的存储结构包括顺序、一链接一、索引和散列等四种。2. 在程序运行过程中可以扩充的数组是_动态一分配的数组。这种数组在声明它时需要使用数组指针。3. 在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。一后出先进表。4. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为一递归的对象。5. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是结点f的层数为6. 一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)3。假定树根结点的层数为0。7. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有右子女

16、。8 .向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的左子树一上。9 .设图G=(V,E),V=1,2,3,4,E=<1,2>,<1,3>,<2,4>,<3,4>,从顶点1出发，对图G进行广度优先搜索的序列有一2种。10.每次直接或通过基准元素间接比较两个元素,若出现逆序排列就交换它们的位置,这种排序方法叫做交换排序。11. 快速排序在平均情况下的空间复杂度为_O（log2n）_。12. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为_500。

17、三、判断题1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（对）2. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树（错）3. 对于AOE网络，加速任一关键活动都能使整个工程提前完成（错）4. 直接选择排序是一种稳定的排序方法（错）5. 闭散列法通常比开散列法时间效率更高（错）6. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（对）7. 顺序表和一维数组一样，都可以按下标随机（或直接）访问（对）8. 在一个顺序存储的循环队列中,队头指针指向队头元素

18、的后一个位置（错）9. 用非递归方法实现递归算法时一定要使用递归工作栈（错）10. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果（对）四、运算题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

19、（6,2）=200+（6*20+2）*1=322-1 ）和2. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为度为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树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少?左单旋转结点个数:右单旋转结点个数：0

20、先左后右双旋转结点个数:先右后左双旋转结点个数:不调整结点个数：64.已知一个带权图的顶点集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到其余各顶点的最短路径,在下面填写顶点:路径长度:0161014252131对应的路径长度。5.已知一个数据表为36,25,25*,62,40,53在进行快速排序的过程中每次划分后数据表的变化。(0)362525*624053(2)2

21、5*253662405325*253653406225*2536405362五、算法设计题1设有一个表头first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。解答1template<classType>voidList<Type>:Tnerse()if(first=NULL)return;ListNode<Type>*p=firstlink;,*pr=NULL;While(p!=NULL)Firsttlink=pr;Pr=first;first=p;p=ptlink;first->link=pr;解答2template<

22、;classType>voidList<Type>:Tnerse()ListNode<Type>*p,*head=newListNode<Type>();While(first!=NULL)P=first;first=firsttlink;ptlink=headtlink;headtlink=p;first=headtlink;deletehead;数据结构模拟卷C一、单项选择题1 数据结构是（D）。A. 种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2算法分析的目的是（B）。A.

23、辨别数据结构的合理性B. 评价算法的效率C. 研究算法中输入与输出的关系D. 鉴别算法的可读性3. 在线性表的下列运算中，不.改变数据元素之间结构关系的运算是（D）。A.插入B.删除C. 排序4. 若进栈序列为 1D.定位3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。A. 3 ， 2，6，1，4，B.3， 41 ， 6， 5C. 1， 2，5，3，4，D.5， 62， 3 ， 15.设串sl="DataStructureswithJava" ,s2= it,则子串定位函数index （s1,s2 ）的值为（A.15B.16C.17D.186.二维数

24、组A89 按行优先顺序存储，若数组元素 A231087A471153，则数组元素A67的存储地址为（A）。A.1207B.1209C.1211D.12137.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）。A.队列B.栈C.线性表D.有序表&在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（A.不一定相同B.都相同C.都不相同D.互为逆序9.弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（A层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法若采用孩子兄C）。10?若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（A）A.图中每个顶点的

25、入度C.图中弧的条数11.A.无向图C.稠密图B.图中每个顶点的出度D.图中连通分量的数目图的邻接矩阵表示法适用于表示（B.有向图D.稀疏图12?在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素,则在进行第i趟排序之前，无序区中关键字元素的个数为（D）。A.iB.i+1C.n-iD.n-i+1二、填空题1. .栈是特殊的线性表，其运算遵循后进先出的原则。2. 栈一是限定仅在表尾进行插入或删除操作的线性表。3. 一个栈的输入序列是：1,2,3则不可能的栈输出序列是_3,1,24.二叉树由一根结点、左子树、右子树_三个基本单元组成。5.在二叉树中，指针p所指结点为叶子结点的条件是P->Lchild=NULL&&P->Rchild=NULL6.具有256个结点的完全二叉树的深度为97.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有12仝叶子结点&若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的和记录的移动_。则最省9 .分别采用堆排序，快速排序，冒泡排序和归弁排序，对初态为有序的表一冒泡排序一算法，最费时间的是一快速排序一算法。10 .不受待排序初始序列的影响，度为0(M)的排序算法是_选择排序,在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是