数据结构专升本模拟题及参考答案

1、东北农业大学网络教育学院数据结构专升本作业题作业题（一）一、单项选择题从逻辑上可以把数据结构分为（）两大类。动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构链表不具有的特点是（）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比下面程序段的时间复杂度的量级为（）。For（i=1;i=n;i+）For（j=1;j=I;j+）For（k=1;k=j;k+）X=x+1;A.O（1）B.O（n）C.O（n2）D.O（n3）在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）

2、个指针域的值。TOC o 1-5 h zA.2B.3C.4D.65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。A.98B.100C.102D.1066、判定一个栈s（最多元素为m0）为空的条件是（）。A.s-top!=0B.s-top=0C.s-top!=m0D.s-top=m07、循环队列用数组Am（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front8、设有两个串S1与

3、S2,求串S2在S1中首次出现位置的运算称作（）A.连接B.求子串C.模式匹配D.判子串9、设串S1=ABCDEFG,S2=PQRST,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(Sl,2,len(S2),subs(Sl,len(S2),2)的结果是()。ABCDEFB.BCDEFGCBCPQRSTD.BCDEFEF10、数组常用的两种基本操作是()。A.建立与查找B删除与查找C.插入与索引D.查找与修改二、填空题1.所谓稀疏矩阵指的是_且分布没有规律2.队列是的线性表，其运

4、算遵循的原则。TOC o 1-5 h z空格串是。简单选择排序和起泡排序中比较次数与序列初态无关的算法有。5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为，图的深度或广度优先搜索遍历时的空间复杂度均为。6、一个图的表示法是唯一的，而表示法是不唯一的。三、算法设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。四、应用题1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。(10分)2、对无向带权图，用克鲁斯卡

5、尔算法构造最小生成树。(10分)3、已知记录关键字集合为(53,17,19,61,98,75,79,63,46,49)要求散列到地址区间(100,101,102,103,104,105,106,107,108,109)内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。(设等概率情况)4、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次数为多少？作业题（二）、单项选择题有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B

6、.453126C.346521D.234156栈和队都是（）A.顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构3、顺序查找法适合于存储结构为（）的线形表。A.散列存储B.顺序存储或链接存储C压缩存储D索引存储4、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。A（l00，80，90，60，l20，ll0，l30)B（l00，l20，ll0，l30，80，60，90)C（l00，60，80，90，l20，ll0，l30)D(l00，80，60，90，l20l30，ll0)5、折半查找的平均比较次数为（）。AnBn/2Clog2

7、nDlog2(n+l)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点vl出发，所得到的顶点序列是（）。B.vl,v2,v3,v4,v5A.vl,v2,v3,v5,v4C.vl,v3,v4,v5,v2D.vl,v4,v3,v5,v2到的顶点序列是（）。B.vl,v2,v3,v4,v5A.vl,v2,v3,v5,v4C.vl,v3,v4,v5,v2D.vl,v4,v3,v5,v2TOC o 1-5

8、 h z8、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（）。A顺序存储B链式存储C索引存储D散列存储9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s,则所有顶点的入度之和为（）。A.ss-1A.ss+1D.n10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是（）。B.AGBFDECA.AECDBFGB.AGBFDECC.ACEDBGF二、填空题设no为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点。有数据WG=7,19,2,6,32,3,21,10,则所建Huffman树的树高是，带权路径长度WPL为。设一棵完全二叉树

9、叶子结点数为k,最后一层结点数2,则该二叉树的高度为。采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳。设G为具有N个顶点的无向连通图，则G中至少有条边。哈夫曼树（HuffmanTree）又称。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL。树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的；依次先序遍历树的。三、应用题1、给定权值集合1,4,2,6,9,构造相应的哈夫曼树,并计算它的带权路径长度。2、对关键字序列10，6，3，2，5，4，构造一棵平衡二叉（排序）树并画图（要求画出建树过程）

10、。3、设有一个有序文件，其中各记录的关键字为（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15）当用折半查找算法查找关键字为3，8，19时，其比较次数分别为多少？4、对有五个结点A,B,C,D,E的图的邻接矩阵，010030g10g0gggg60020gg10g0gggg5001）画出逻辑图；2）画出图的十字链表存储；3）基于邻接矩阵写出图的深度、广度优先遍历序列4）计算图的关键路径。作业题（三）一、单项选择题1串的长度是指（）B.串中所含非空格字符的个数D.B.串中所含非空格字符的个数D.串中所含字符的个数C串中所含不同字符的个数设有数组Ai,j,数组的每个元素长度为3

11、字节，i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（）。BA+222D.BA+225B.BA+222D.BA+225B.正确性和简明性D.数据复杂性和程序复杂性算法分析的两个主要方面是（）。A.空间复杂性和时间复杂性C.可读性和文档性算法分析的目的是（）。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性5.下面程序段的时间复杂性的量极为(Intfun(intn)inti=1,s=1;While(sn)S+=+I;ReturnI;A.O(n/2)。B.O(lbn)C

12、.O(n)D.O()6.线性表是()。A.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空D.一个无限序列，不能为空7.带头结点的单链表L为空的判定条件是()。A.L=NULLB.L-next=NULLC.L-next=LD.L!=NULL&在一个长度为n的线性表中，删除值为X的兀素时需要比较兀素和移动兀素的总次数为()。A.(n+1)/2B.n/2C.nD.n+19.一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是()。A.98B.100C.102D.10610.如果某链表中最常用的操作是取第i个结点及其前驱，则米用()存

13、储方式最节省时间。A.单链表B.双向链表C单循环链表D.顺序表二、填空题1.高度为2的二叉树的结点数至少有个，高度为3的二叉树的结点数至少有个。TOC o 1-5 h z在顺序表(8,11,15,19,25,26,30,33,42,48,50)中，用折半查找关键字值20，需做的关键字比较次数为。在有n个顶点的无向图中，每个顶点的度最大可达。已知广义表A=(a,b,c),(d,e,f),则广义表运算head(tail(tail(A)=。数组(Array)是n(nl)个的有序组合，数组中的数据是按顺序存储在一块的存储单元中。采用顺序存储结构表示三元组表(TripleTable)，来实现对稀疏矩阵的

14、一种压缩存储形式，就称为，简称表。运算是矩阵运算中最基本的一项，它是将一个mxn的矩阵变成另外一个nxm的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。三、应用题1、对于下图所示的二叉树，画出二叉链表存储结构图。2、请画出下图所示的树所对应的二叉树。ABCDE已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以为起点，试画出构造过程）。已知完全二叉树的第8层有8个结点，则其叶子结点是多少?画出如图所示中树的二叉树的表示形式。作业题（四）一、单项选择题将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（）。AnB2n-1TOC o 1-5 h

15、 zC2nDn-1一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。A0B1CnDn+1数据文件的基本操作中最重要的操作是（）。A.插入B.删除C.修改D.检索对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。A（2,5,12,16）26（60,32,72）B（5,16,2,12）28（60,32,72）C（2,16,12,5）28（60,32,72）D（5,16,2,12）28（32,60,72）如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快A.堆排序B.快速排序C插入排序D归并排序6算法分析的目的是

16、（）。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性二叉树的第I层上最多含有结点数为（）A2IB2I-1-1C2I-1D2I-1循环队列存储在数组A中，长度为m,则入队时的操作为（）。A.rear=rear+1B.rear=（rear+1）mod（m-1）C.rear=（rear+1）modmD.rear=（rear+1）mod（m+1）广义表满足Head（A）=Tail（A）,贝山为（）。A（）B（）C（），（）D（），（），（）在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点

17、数为（）个。TOC o 1-5 h zA3B4C5D6二、填空题在一个循环队列中，队首指针指向队首元素的。数组中每一个数据通常称为用下标区分，其中下标的个数由数组的决定。一个图的表示法是唯一的，而表示法是不唯一的。在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许个，最少允许个5.对关键字序列（52,80,63,44,48,91）进行一趟快速排序之后的得到结果为。高度为1的平衡二叉树的结点数至少有个，高度为2的平衡二叉树的结点数至少有个。三判断顺序存储结构属于静态结构，链式结构属于动态结构。（）即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列

18、也一定相同。（）TOC o 1-5 h z带权无向图的最小生成树必是唯一的。（）B-树和B+树都可用于文件的索引结构。（）在用堆排序算法排序时，如果要进行增序排序，则需要采用大根堆。（）四、应用题1.模式串p=abaabcac的next函数值序列为多少？2.设二维数组A的每个元素占4个字节，已知LOC（a0,0）=1000,A共占多少个字节？A的终端结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？3.设a,b,c,d,e五个字符的编码分别为1,2,3,4,5,并设标识符依以下次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Ha

19、sh）方法将它们存入具有10个位置的表中。（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。4.给定一个关键字序列24，19，32，43，38，6，13，22，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。(

20、)CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V74.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7作业题（五）作业题（五）、单项选择题一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。A.(38,40,46,56,79,84)B.(40,38

21、,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)2.广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为()。GetHead(GetTail(GetHead(GetTail(GetTail(A)A.(g)B.(d)C.cD.dA.(g)B.(d)C.cD.d4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()4.折半查找方法适用于排列连续顺序文件的查找。()CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5

22、，V3，V4，V6，V73对于有n个结点的二叉树，其高度为（）A.nlognB.lognC.logn+lD.不确定4.如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是B.B.1347625D.1247653A.1354267C.1534276采用邻接表存储的图，其深度优先遍历类似于二叉树的（）A.中序遍历B.先序遍历C.后序遍历D.按层次遍历已知有向图G=（V,E）,其中VRVpVyVsVqVsV&V?,e=,g的拓扑序列是（）A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V77顺序查找法适用于查找顺序存储或链式存储

23、的线性表，平均比较次数为()。在此假定N为线性表中结点数，且每次查找都是成功的。AN+1B2log2NClog2NDN&下面关于m阶B树说法正确的是()。每个结点至少有两棵非空子树；树中每个结点至多有ml个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后，树长高一层。B.D.B.D.C.已知一个线性表(38,25,74,63,52,48),假定采用h(k)=k%7计算Hash地址进行散列存储，若利TOC o 1-5 h z用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为()A.l.0B.7/6C.4/3D.3/2在排序算法的实施过程中，使用辅助存储空间为O(1)的有

24、()A.简单排序法B.快速排序法C归并排序法D.基数排序法二、填空题n(n大于1)个结点的各棵树中，其中深度最大的那棵树的深度是n,它共有个叶子结点和个非叶子结点。2设一棵后序线索树的高是50,结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60,x是y的左孩子。则确定x的后继最多需经过中间结点(不含后继及x本身)3高度为2(第2层为叶子)的3阶B-树中，最多有个关键字。分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是算法。TOC o 1-5 h z简单选择排序和起泡排序中比较次数与序列初态无关的算法有。串的链式存储结构是将存储区域分成一系列大小

25、相同的结点，每个结点有两个域域和域。其中域用于用于存放数据，域用于存放下一个结点的指针判断顺序存储的线性表可以随机存取。()即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。()十字链表是无向图的一种存储结构。()1123DD1123DDCC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）四、应用题用十字链表表示一个有k个非零元素的mxn的稀疏矩阵，则其总的结点数为多少？2.G=（V,E）是一个带有权的连通图，则

26、：（1）.请回答什么是G的最小生成树；（2）.G为下图所示,请找出G的所有最小生成树。3请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文件中记录应该满足什么条件？设待排序文件之排序码为（88,33，22，55，99,11,66），采用顺序存储。请用直接选择排序算法对上述文件进行排序，用图示说明排序过程。东北农业大学网络教育学院数据结构专升本作业题参考答案作业题一参考答案：一、单项选择题1、C2、B3、D4、C5、B6、B7、A8、C9、D10、D二、填空题1、非零元很少2、操作受限（或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊），先进

27、先出（或后进后出）3、简单选择排序4、0(n2),0(e),0(n)5、邻阵矩阵，邻接表三、算法intcount=0;voidonechild(Btreet)if(t!=NULL)onechild(t-lchild);onechild(t-rchild);if(t-lchild!=NULL&(t-rchild!=NULLIIt-lchild!=NULL&t-rchild=NULL)count+;四、应用题1、35254812f55432053(1)12卡4836654320中5812204S匕3665432550(3)12202536654348581220253665434858t_f122

28、02536436548t_i5S12202536434S555S1t_f1220253fi434B58652、答：(2)(1)(2)(3)A(3)AAG2FG24F(5)(6)A3A3BDBEDCC-t6154154G2FG2F3、答：由于地址空间为10,且从100开始，故散列函数选为H(key)=key%7+100。散列地址100101102103104105106107108109关键字98637917531961754649比较次数12111123510用线性探测再散列解决冲突，ASLsucc=27/104、答：成功查找平均比较查找长度为:(n+1)/nlog2(n+l)-l。作业题二参

29、考答案：一、单项选择题1、C2、C3、B4、C5、D6、C7、C8、B9、A10、C二、填空题TOC o 1-5 h z1、2n-102、6,2613、log2k+14、255、N-16、最优二叉树，最小的二叉树7、根结点，各子树三、应用题CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V71、答：不唯一，型对即可CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7此树的带权路径长度WPL=9*1+6*2+4*3+(1+2)*4=

30、452、答1)插入10(2)插入6/(3)插入1)插入10(2)插入6/(3)插入33、答：当关键字为3时，比较次数为4当关键字为8时，比较次数为1；当关键字为19时，查找不成功；CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7(2)略CC.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7深度优先遍历序列：ABCDE广度优先遍历序列：ABCED(4)关键路径AB(长100)作业题三参考答案:一、单项选择题1、D2、B3、A4、C

31、5、D6、A7、B8、C9、B10、D二、填空题TOC o 1-5 h z1、2，32、43、n-14、e5、相同类型数据，地址连续6、三元组顺序表，三元组7、矩阵转置三、应用题1、答:二叉链表二叉链表AAAAAAAA(2AA2、答:ABCDE答：Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruska1算法，构造最小生成树过程如下：(下图也可选(2,4)代替(3,4),(5,6)代替(1,5)即：答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。设该完全二叉树有d层，则除最后一层外各层的结点个数分别为：1，2,4,8,16,32,，即第i层的结点个数为2i

32、-l。这里第8层有8个结点，显然第8/层是最后的一层，那么第7层的结点个数为27-1=64个，其中的4个结点有8个叶子结点,余下的为叶子结点，个数为64-4=60,所以该完全二叉树的叶子结点个数为60+8=68个。答：对应的二叉树形式如图所示：作业题四参考答案：一、单项选择题1.A2.B3.D4.B5.D6、C7、C8、C9、B10、D二、填空题答：前一个位置答：数组元素，数组元素，维数答：邻阵矩阵，邻接表答：9,4答：4844526480911,2三、判断答：丁答：x答：x答：丁答：丁四、应用题1.答：模式p的next函数值如下:文件注啜watv?JftA.IIbjf.I工且衰格an.I冊S

33、hopEillKi*圉英中叵i日中連中更固取书區设宜-I2I2IIglI2IllOlI1El*:?mEilU简述一于字符串中子串的摘成.客一个字痔用中任童连续伞字轩组啟的子丹列称対字科串的子札空串利空梏伟有何区别?字符串中空格符有何境叉1:?mEilU简述一于字符串中子串的摘成.客一个字痔用中任童连续伞字轩组啟的子丹列称対字科串的子札空串利空梏伟有何区别?字符串中空格符有何境叉1空串在串的处運中有何作用T客不含任何罕符的b祢肖空命县七长虞为零；枚含有空蒂宇符的彩藤空甯曬它的长度为中空格符的个数空格符在字符串中可用来分隔一般的字符，便于闻谀利识别，空格符会占用有效串长空串在处理过程中可用于作竟任惹字痔串的子务|蓋墓趣怅度小于一个常数呱茉坤何种存储方爲最节省空耶客采用顺序串最节省空间.因为顺序串乂犍审帘比.不需要指針域。棋式串p=iL3baabcac的nert函数值序列为参少？晋模戏的next画數值如下012j=棋式孔nextj昴法设廿題OQ兔用顺卉结构存储串S,编頁一牛函数別榮m中第*字符开始的j*字符,strine+=deli1（siring+s,inti,im）忌寸k.aba-100ite