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

东北农业大学网络教育学院数据结构专升本作业题 作业题(一)一、单项选择题 1从逻辑上可以把数据结构分为( ）两大类。动态结构、静态结构 B顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构2 链表不具有的特点是( ) A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D所需空间与线性长度成正比3下面程序段的时间复杂度的量级为( ）。F(;i<=n;i+） Fo（1;j<=I;j) or(1;kj；k+) X=x1;A(1） B.O(）C.(n²） O(n³)4.在一个带头结点的双向循环链表中,若要在p所指向的结点之前插入一个新结点,则需要相继修改( )个指针域的值。A B.3C.4 6、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是( ）。A.98 B100C.10 D.066、鉴定一个栈s(最多元素为m)为空的条件是( )。As-top! 0 B.s-top= =0C.s-p！ m D.stop=m7、循环队列用数组A(下标从0到m-1）存放其元素值,已知其头尾指针分别是front和ear,则当前队列中的元素个数是（ ）。A(rearfront+m）%m reafont1C.rear-front-1 D rer-frt8、设有两个串S1与2,求串S2在S1中初次出现位置的运算称作（ )。A.连接 .求子串C模式匹配 .判子串9、设串1='ACFG'，S2='QRS',函数cn(x,y）返回x和y串的连接串，sus(,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串,ln(s)返回串的长度,则cn(sub(1，2,n(2)，su（S1,len（S),2)）的结果是（ ）。A.CDEF B.BDEGC.CQRT .BCDFE10、数组常用的两种基本操作是( ）。.建立与查找 B删除与查找C插入与索引 D.查找与修改二、填空题 所谓稀疏矩阵指的是_且分布没有规律。2. 队列是_的线性表，其运算遵循_的原则。3 空格串是_。4.简朴选择排序和起泡排序中比较次数与序列初态无关的算法有_。5、设图G有个顶点和e条边,则对用邻接矩阵表达的图进行深度或广度优先搜索遍历时的时间复杂度为 ,而对用邻接表表达的图进行深度或广度优先搜索遍历时的时间复杂度为 ，图的深度或广度优先搜索遍历时的空间复杂度均为 。6、一个图的 表达法是唯一的，而 表达法是不唯一的。三、算法设二叉树采用二叉链表结构,试设计一个算法记录给定二叉树中的一度结点数目。四、应用题 1、对关键字无序序列(36，2，8,，65，43，8)进行直接选择排序,请写出每一趟排序的结果。(10分）2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（1分）20A39D4FCB81E65G2、已知记录关键字集合为（3,19,61,8，5，9,63,6,49）规定散列到地址区间(100，10,10,10,4,10,106,107,08,109)内,若产生冲突用开型寻址法的线性探测法解决。规定写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）、设被查找文献有49个记录,对每个记录查找记录概率相等，若采用顺序查找,成功查找平均比较次数为多少? 作业题(二）、单项选择题. 有六个元素6，5,4，3，的顺序进栈,问下列哪一个不是合法的出栈序列？（ )A. 5 4 3 6 12 B. 453 1 2 6 C. 3 4 5 2 1 D. 2 4 1 5 62.栈和队都是（ ）A顺序存储的线性结构 B.链式存储的非线性结构. 限制存取点的线性结构 . 限制存取点的非线性结构3、顺序查找法适合于存储结构为( ）的线形表。A.散列存储B顺序存储或链接存储C压缩存储.索引存储4、分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )。A.（00，80, 0， 60，12，10,130）B.（00，120，110，0,80， 60, 90).（10，6， 80, 90, 20，10，10)D (10,8， 60， 0， 10,，10)5、折半查找的平均比较次数为（ )。AnBn/ Clog2nD.lo2(n)6、当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找，但前者比后者的查找速度( )必然快.不一定C.在大部分情况下要快D取决于表递增还是递减7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法,从顶点1出发,所得到的顶点序列是( )。v1，v2,v，v5，v4v1,v2，v3,v,v5C.v1，,4，v5,2D.v,v4,v3,v，v28、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（)。A顺序存储B链式存储.索引存储D散列存储9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。A.sB.-1C.s1.n10、如图所示,给出由7个顶点组成的无向图。从顶点A出发,对它进行深度优先搜索得到的顶点序列是( ）。A E D F BA G B F E CA C D BGFD. BD G F E 二、填空题 1.设0为哈夫曼树的叶子结点数目,则该哈夫曼树共有_个结点。. 有数据WG7，19,2,6,32，3，21,0,则所建Huffma树的树高是_,带权途径长度PL为_。3.设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为_。4. 采用分块查找时，若线性表中共有25个元素,查找每个元素的概率相同,假设采用顺序查找来拟定结点所在的块时,每块应分 个结点最佳。5、设G为具有N个顶点的无向连通图，则G中至少有 条边。6、哈夫曼树(Huffman Tree)又称 。它是n个带权叶子结点构成的所有二叉树中，带权途径长度L 。、树的先序遍历过程如下：若树为空,则进行空操作；若树非空,则访问树的 ;依次先序遍历树的 。三、应用题 1、给定权值集合1, 4, , 6， ,， 构造相应的哈夫曼树， 并计算它的带权途径长度。、对关键字序列10，6，2,5，4,构造一棵平衡二叉(排序）树并画图（规定画出建树过程)。、设有一个有序文献,其中各记录的关键字为(1,2,3，4，5，6,7,8，9,1,11，2，3，14，15),当用折半查找算法查找关键字为3,19时,其比较次数分别为多少？4、对有五个结点A,B, C, D, E的图的邻接矩阵，（1）画出逻辑图 ;（2）画出图的十字链表存储；(3）基于邻接矩阵写出图的深度、广度优先遍历序列；（4)计算图的关键途径。 作业题（三）一、单项选择题 串的长度是指（ )A.串中所含不同字母的个数 .串中所含非空格字符的个数C串中所含不同字符的个数 D串中所含字符的个数.设有数组Ai，j，数组的每个元素长度为3字节，i的值为 到8 ,j的值为1 到10，数组从内存首地址A开始顺序存放，当用以列为主存放时，元素5,8的存储首地址为（ )。A. BA41 B B+18 C 222 D A+2253.算法分析的两个重要方面是( ）。A.空间复杂性和时间复杂性 .对的性和简明性可读性和文档性 数据复杂性和程序复杂性4算法分析的目的是（ )。 找出数据结构的合理性 B.研究算法中的输入和输出的关系C分析算法的效率以求改善 D.分析算法的易懂性和文档性5. 下面程序段的时间复杂性的量极为( )。tfu(intn) int=1,=;Whie（s<）S +;Retur I;A.(/) B(lbn)C.O(n） D( ）. 线性表是( ）。A一个有限序列,可认为空 B一个有限序列，不能为空C一个无限序列，可认为空 D.一个无限序列，不能为空7. 带头结点的单链表L为空的鉴定条件是（ )。.L= NL B.-xt= NULL.Lnext= =L DL! =LL. 在一个长度为n的线性表中,删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。.（n+1)/2 B./Cn D.n+19.一个顺序存储线性表的第一个元素的存储地址是9,每个元素的长度是,则第个元素的存储地址是( ）。A.98 B.10.02 D.0610. 假如某链表中最常用的操作是取第个结点及其前驱,则采用（ )存储方式最节省时间。A单链表 B双向链表单循环链表 顺序表二、填空题 高度为的二叉树的结点数至少有_个,高度为3的二叉树的结点数至少有_个。 在顺序表（，11,5,9,25,26,0,33，2，8,50）中,用折半查找关键字值0,需做的关键字比较次数为_。3.在有个顶点的无向图中,每个顶点的度最大可达_。4.已知广义表A=(（a，b，c）,(d,e，)，则广义表运算h(a（t（）)）= 。5、数组（Array)是n（n1）个 的有序组合,数组中的数据是按顺序存储在一块 的存储单元中。6.采用顺序存储结构表达三元组表(Trpl Table),来实现对稀疏矩阵的一种压缩存储形式，就称为 ，简称 表。7. 运算是矩阵运算中最基本的一项,它是将一个m x 的矩阵变成此外一个n x 的矩阵,同时使本来矩阵中元素的行和列的位置互换而值保持不变。三、应用题 、对于下图所示的二叉树,画出二叉链表存储结构图。、请画出下图所示的树所相应的二叉树。 ABCDE3. 已知一个无向图如下图所示，规定分别用Prim和ruskl算法生成最小树(假设以为起点，试画出构造过程）。4. 已知完全二叉树的第8层有个结点，则其叶子结点是多少?5.画出如图所示中树的二叉树的表达形式。 作业题（四）一、单项选择题 1. 将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是( )。A. B.nC.2n D.n-2 一个有个顶点的无向连通图,它所包含的连通分量个数为（ )。A.0B.n.n13.数据文献的基本操作中最重要的操作是（ ）。A.插入B删除C.修改D.检索4.对关键码序列28,16，3,12，60,，5,72快速排序,从小到大一次划分结果为( )。(,12,1)26(6，32,7) (5,1,2,2)2（60，2,7)C.(2,16,1,5)28(6,3，72)D.(,16,2,2)28(2，60,2)5. 假如只想得到1000个元素组成的序列中第个最小元素之前的部分排序的序列,用（ ）方法最快。A.堆排序 B.快速排序C.插入排序.归并排序6.算法分析的目的是（ ）。 A.找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改善 D分析算法的易懂性和文档性. 二叉树的第层上最多具有结点数为( )AI B 2I-1- C.2I-1 DI 18.循环队列存储在数组A中,长度为，则入队时的操作为（ ）。A. rer=rea+1 B. ar(ear+1）mod （1) C. rar(rer+) mod D. rear(rear+）m(+1） 9 广义表满足Hed(A)=ai(A),则A为( ）。A(） .（） .(（)，()） .(）,（),（）) 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为个，则度为0的结点数为( )个。A.3 B.4C.5 .6二、填空题 1. 在一个循环队列中，队首指针指向队首元素的_。 2. 数组中每一个数据通常称为 ， 用下标区分，其中下标的个数由数组的 决定。 . 一个图的 表达法是唯一的，而 表达法是不唯一的。 4.在一个0阶的B-树上,每个数根结点中所含的关键字数目最多允许 个，最少允许 个 5 对关键字序列(5，80,63,44,48,)进行一趟快速排序之后的得到结果为 。10.高度为的平衡二叉树的结点数至少有_个,高度为2的平衡二叉树的结点数至少有_个。三 判断 .顺序存储结构属于静态结构,链式结构属于动态结构。 （ ） 2.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。 （ ） 3. 带权无向图的最小生成树必是唯一的。（ ） . -树和B+树都可用于文献的索引结构。（ ) 5. 在用堆排序算法排序时，假如要进行增序排序,则需要采用大根堆"。（ )四、应用题 1 模式串p=ababcac"的net函数值序列为多少？ 2.设二维数组A6的每个元素占4个字节，已知OC(a0,0）=,共占多少个字节?的终端结点4,的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少? . 设a,d,e五个字符的编码分别为1,2,4,5,并设标记符依以下顺序出现:a,b，aa,be,ab,ad,cd，bc,ce。规定用哈希（Hsh）方法将它们存入具有1个位置的表中。(1)将上述关键字（标记符）构造一个哈希函数,使得发生冲突尽也许地少；（2)线性探测再散列法解决冲突。写出上述各关键字在表中位置。 4. 给定一个关键字序列24,1，32，43，38，6,1,2,请写出快速排序第一趟的结果;堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？ 作业题(五)一、单项选择题 1. 一组记录的关键码为(46,79，6，38,8)，则运用快速排序的方法，以第一个记录为基准得到的一次划分结果为( ）。 A(8,0,46,56,79,84） B.(40,38，4,7,6,84)C(0,38，46，56,79,84)D.(0,3，6,84,79)2.广义表=(a,b,（c,)，(，(f,g）),则下面式子的值为（ )。GeHead(GetTil(GeHad(Gtail(Geti（A)）)A(g） B. （) C.c D d对于有n个结点的二叉树, 其高度为（ )nog2 B.g2n .ëlog2û+1 D.不拟定 如图所示，给出由个顶点组成的无向图。从顶点1出发,对它进行深度优先搜索得到的顶点序列是( ）。1 3 5 4 2 7B.1 7 6 25C. 427 6D.1 24 7 6 5. 采用邻接表存储的图，其深度优先遍历类似于二叉树的( )。中序遍历B先序遍历.后序遍历 D.按层次遍历 6. 已知有向图G=(V，E),其中V=，V2，3,4,V5，V6,V7,E=<V1，V2>,<V1,V3,<V,V4>，<V2,>,3,5>,<,V>,<V4,6>,5,V7,6,V7,的拓扑序列是（ ）。A.1，V3，V4,V6,V2,V,7B.V,V,V2,V,V5,V7C.V1,V3,V4,5,V2，V6，V7D.V1,V2,5,V3,V,V6,V 7. 顺序查找法合用于查找顺序存储或链式存储的线性表,平均比较次数为( ）。在此假定N为线性表中结点数,且每次查找都是成功的。.N+1B.lo2NClg2DN 8. 下面关于m阶B树说法对的的是（ ）。每个结点至少有两棵非空子树； 树中每个结点至多有m一1个关键字;所有叶子在同一层上; 当插入一个数据项引起B树结点分裂后，树长高一层。.B.CD 9. 已知一个线性表(38,25,7，3，52，8)，假定采用h(k)=k%7计算Hash地址进行散列存储，若运用链地址法解决冲突，则在该Hah表上进行查找的平均查找长度为( )。A.B6C.4/33/2 0 在排序算法的实行过程中，使用辅助存储空间为O（1)的有（ )。A简朴排序法B.快速排序法C.归并排序法D.基数排序法二、填空题1. （大于1)个结点的各棵树中,其中深度最大的那棵树的深度是n，它共有_个叶子结点和_个非叶子结点。.设一棵后序线索树的高是5,结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60，x是y的左孩子。则拟定x的后继最多需通过_中间结点（不含后继及自身)3.高度为2(第2层为叶子）的3阶B-树中，最多有_个关键字。4.分别采用堆排序,快速排序，冒泡排序和归并排序,对初态为无序的表，则平均情况下最省时间的是_算法。5简朴选择排序和起泡排序中比较次数与序列初态无关的算法有_。6串的链式存储结构是将存储区域提成一系列大小相同的结点,每个结点有两个域 域和 域。其中 域用于用于存放数据, 域用于存放下一个结点的指针三判断 1. 顺序存储的线性表可以随机存取。 ( ） 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所得的输出序列也一定相同。 ( ） 3. 十字链表是无向图的一种存储结构。( ) . 折半查找方法合用于排列连续顺序文献的查找。（ ) 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动,则该算法是不稳定的。( )四、应用题 1. 用十字链表表达一个有k个非零元素的 x n的稀疏矩阵，则其总的结点数为多少? 2. =(V,)是一个带有权的连通图，则:（）请回答什么是G的最小生成树；(）G为下图所示,请找出G的所有最小生成树。 3 请分别叙述在一个连续顺序文献中采用顺序查找法,折半查找法和分块查找法查找一个记录，该文献中记录应当满足什么条件？ 4. 设待排序文献之排序码为(88，33,2，99,11，66），采用顺序存储。请用直接选择排序算法对上述文献进行排序,用图示说明排序过程。东北农业大学网络教育学院数据结构专升本作业题参考答案作业题一参考答案：一、单项选择题 1、 2、B3、 4、C 5、B6、B 7、A 8、 9、D0、D二、填空题1、非零元很少2、操作受限（或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊），先进先出(或后进后出)3、简朴选择排序4、O（n2)，O（e)，O（)5、邻阵矩阵,邻接表三、算法 答:nt count= ;vid nechild (Btree t) f ( t!=NU) onecil ( t->lhild ）; onechild(t->child ); if ( t>hld!NUL & (t->rcild!=UL | t>lld!=ULL & t->chil=ULL )ount+; 四、应用题 1、答:2、答:(1）()C11C2FGG3AD3AD（3)（4）1C2FG1C42FG(5）（6）3ADEB561C41CB543AD2FG2FG3、答：由于地址空间为10,且从10开始,故散列函数选为H(e)key%7+00。用线性探测再散列解决冲突，ALuc2710、答：成功查找平均比较查找长度为：（n+）/lo2(n)-1。作业题二参考答案:一、单项选择题 1、C 2、C3、B 、C 5、D6、C 、C 、B 9、A 10、C二、填空题 1、20-12、6，2613、 élogkù14、25、N-1、最优二叉树,最小的二叉树、根结点，各子树三、应用题1、41263713922答：不唯一，型对即可此树的带权途径长度L =91+*2+4*+(1+2)*4=42、答：6()插入10(2) 插入6（3)插入3(） 1010103调整6106(5)插入2(6)插入 （7）插入4 (8)65324101063210632调整10632553、答:当关键字为3时，比较次数为;当关键字为8时，比较次数为;当关键字为时，查找不成功;4、答：（）略（3）深度优先遍历序列:ABC广度优先遍历序列:ABCED（4)关键途径-B（长100）作业题三参考答案:一、单项选择题 1、D2、3、A4、C、D6、A 7、B8、C 9、B 、二、填空题 1、2，2、43、-14、5、相同类型数据,地址连续6.三元组顺序表,三元组矩阵转置三、应用题 1、答： 二叉链表(2、答：ACDBE3. 答：Pim算法构造最小生成树的环节如24题所示，为节省篇幅，这里仅用ruskal算法，构造最小生成树过程如下：（下图也可选(2,)代替(3，4),(，6)代替(1,5）即：4. 答:由完全二叉树的定义可知,除最后一层外,其他各层的结点是满的。设该完全二叉树有d层,则除最后一层外各层的结点个数分别为：1，2，8，1,，即第层的结点个数为21。这里第层有8个结点，显然第8层是最后的一层，那么第7层的结点个数为2-1=个,其中的4个结点有个叶子结点,余下的为叶子结点，个数为64-4，所以该完全二叉树的叶子结点个数为60+88个。5. 答:相应的二叉树形式如图所示:作业题四参考答案:一、单项选择题 . 2B3.D .B 5.D6、 7、C 8、C 、 0、D二、填空题 1. 答:前一个位置2. 答：数组元素，数组元素，维数.答:邻阵矩阵，邻接表4 答:9,4. 答:8452 60916、,2三判断1 答:2. 答：×3 答:×4. 答:. 答：四、应用题1.答：模式p的next函数值如下：2. 答:A共20个字节。a,5的起始地址为:1116。按行优先存储时，a2,的起始地址为:1068。按列优先存储时，a2,5的起始地址为:1108。3. 答：（1)哈希函数（key）(关键字各字符编码之和）M7(2)4.答:一趟快速排序:22,19,13,6，24,8,4,32初始大堆:3,38,2，2，2，6,13,9二路并归：第一趟：19,2,32,43,6,1, 第二趟：1,2,32，43,6,1，2,38 第三趟：6，1，1,2,24,3,43堆排序辅助空间最少,最坏情况下快速排序时间复杂度最差。作业题五参考答案:一、单项选择题 1. 答：C2、D 3、D4. 答:C5. 答：B6 答:A7. 答： 8. 答：B9. 答：C10.答：A二、填空题1、，n-1、2、快速排序5、简朴选择排序6数据，指针,数据,指针三 判断 1 答:. 答:×3. 答：×4. 答:. 答：×四、应用题 1 答:该十字链表有一个十字链表表头结点，ax(，n)个行列表头结点。此外,每个非零元素相应一个结点,即个元素结点，所以共有mx(，n)+k+1个结点。2.答：（1）最小生成树的定义略。(）最小生成树有两棵。（限于篇幅,下面的生成树只给出顶点集合和边集合，边以三元组（Vi，j,W)形式）,其中W代表权值。V(G)=1,3,，5 (G)=(4,5,2)，（，5，)，（2,3,5)，(，2,7）；E2（)(,)，（2,4）,（,，5),(，7）3.答:采用顺序查找法:文献中记录可以以任意连续存放。采用折半查找法:文献中的记录必须按照关键字从小到大有序存放。采用分块查找法:将文献提成若干个块,每一个快中的记录可以任意的存放,但块之间的必须按照关键字从小到大的顺序存放,即前一块中的所有记录的关键字的值必须小于后一块的所有记录的关键字的字值。4 答:排序过程如下：(）8,3,2,5,11,(2）11，33,22,5，99,8,66(3)11,2,33,99,8,6(）11,22,33,5，9,8,6(5)11,22,33,5,99,88,6(6)1，2，3,55，66,99，88(7)11,2，3，5,6,88,99（8)1,22，33，5，6,8,99