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

作业题（一）一、单项选择题1.从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2.链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。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(n²)D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A．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、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。A．（rear-front+m）%mB．rear-front+1C．rear-front-1D．rear-front8、设有两个串S1与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(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。A．BCDEF B．BCDEFGC．BCPQRSTD．BCDEFEF10、数组常用的两种基本操作是（）。A．建立与查找B．删除与查找C．插入与索引D．查找与修改二、填空题1.所谓稀疏矩阵指的是________且分布没有规律。2.队列是________的线性表，其运算遵循________的原则。3.空格串是________________________________。4.简朴选择排序和起泡排序中比较次数与序列初态无关的算法有________。5、设图G有n个顶点和e条边，则对用邻接矩阵表达的图进行深度或广度优先搜索遍历时的时间复杂度为，而对用邻接表表达的图进行深度或广度优先搜索遍历时的时间复杂度为，图的深度或广度优先搜索遍历时的空间复杂度均为。6、一个图的表达法是唯一的，而表达法是不唯一的。三、算法设二叉树采用二叉链表结构，试设计一个算法记录给定二叉树中的一度结点数目。四、应用题1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。（10分）2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10分）20A3920A39D4FCB8D4FCB81E651E65G2G23、已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）规定散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。规定写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）4、设被查找文献有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次数为多少？作业题（二）、单项选择题1.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341562.栈和队都是（）A．顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构3、顺序查找法适合于存储结构为（）的线形表。A．散列存储 B．顺序存储或链接存储C．压缩存储 D．索引存储4、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。A．（100，80，90，60，120，110，130） B．（100，120，110，130，80，60，90）C．（100，60，80，90，120，110，130） D．(100，80，60，90，120，130，110)5、折半查找的平均比较次数为（）。A．n B．n/2C．log2n D．log2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）A．必然快 B．不一定C．在大部分情况下要快 D．取决于表递增还是递减7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。A．v1，v2，v3，v5，v4 B．v1，v2，v3，v4，v5C．v1，v3，v4，v5，v2 D．v1，v4，v3，v5，v28、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（）。A．顺序存储 B．链式存储C．索引存储 D．散列存储9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（）。A．s B．s-1C．s+1 D．n10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是（）。A．AECDBFG B．AGBFDECC．ACEDBGF D．ABDGFEC二、填空题1.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有________个结点。2.有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是________，带权途径长度WPL为________。3.设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为________________。4.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来拟定结点所在的块时，每块应分个结点最佳。5、设G为具有N个顶点的无向连通图，则G中至少有条边。6、哈夫曼树（HuffmanTree）又称。它是n个带权叶子结点构成的所有二叉树中，带权途径长度WPL。7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的；依次先序遍历树的。三、应用题1、给定权值集合{1,4,2,6,9,},构造相应的哈夫曼树,并计算它的带权途径长度。2、对关键字序列{10，6，3，2，5，4}，构造一棵平衡二叉（排序）树并画图（规定画出建树过程）。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}的图的邻接矩阵，（1）．画出逻辑图；（2）．画出图的十字链表存储；（3）．基于邻接矩阵写出图的深度、广度优先遍历序列；（4）．计算图的关键途径。作业题（三）一、单项选择题1．串的长度是指（）A．串中所含不同字母的个数B．串中所含非空格字符的个数C．串中所含不同字符的个数D．串中所含字符的个数2．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+2253．算法分析的两个重要方面是（）。A．空间复杂性和时间复杂性B．对的性和简明性C．可读性和文档性D．数据复杂性和程序复杂性4．算法分析的目的是（）。A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改善D．分析算法的易懂性和文档性5.下面程序段的时间复杂性的量极为（）。Intfun(intn){inti=1,s=1;While(s<n)S+=++I;ReturnI;}A．O(n/2)B．O(lbn)C．O(n)D．O()6.线性表是（）。A．一个有限序列，可认为空B．一个有限序列，不能为空C．一个无限序列，可认为空D．一个无限序列，不能为空7.带头结点的单链表L为空的鉴定条件是（）。A．L==NULLB．L-〉next==NULLC．L-〉next==LD．L!=NULL8.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。A．（n+1）/2B．n/2C．nD．n+19.一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。A．98B．100C．102D．10610.假如某链表中最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A．单链表B．双向链表C．单循环链表D．顺序表二、填空题1.高度为2的二叉树的结点数至少有________个，高度为3的二叉树的结点数至少有________个。2.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找关键字值20，需做的关键字比较次数为________。3.在有n个顶点的无向图中，每个顶点的度最大可达________。4．已知广义表A=（（a，b，c），（d，e，f）），则广义表运算head（tail（tail（A）））=。5、数组（Array）是n（n≥1）个的有序组合，数组中的数据是按顺序存储在一块的存储单元中。6.采用顺序存储结构表达三元组表（TripleTable），来实现对稀疏矩阵的一种压缩存储形式，就称为，简称表。7.运算是矩阵运算中最基本的一项，它是将一个mxn的矩阵变成此外一个nxm的矩阵，同时使本来矩阵中元素的行和列的位置互换而值保持不变。三、应用题1、对于下图所示的二叉树，画出二叉链表存储结构图。2、请画出下图所示的树所相应的二叉树。AABCDE3.已知一个无向图如下图所示，规定分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。4.已知完全二叉树的第8层有8个结点，则其叶子结点是多少？5.画出如图所示中树的二叉树的表达形式。作业题（四）一、单项选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（）。A．nB．2n-1C．2nD．n-12.一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。A．0 B．1C．n D．n+13.数据文献的基本操作中最重要的操作是（）。A．插入 B．删除C．修改 D．检索4.对关键码序列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)5.假如只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A．堆排序 B．快速排序C．插入排序 D．归并排序6．算法分析的目的是（）。A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改善D．分析算法的易懂性和文档性7.二叉树的第I层上最多具有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-18．循环队列存储在数组A中，长度为m，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)9.广义表满足Head(A)=Tail(A)，则A为（）。A．（）B．（（））C．（（），（））D．（（），（），（））10.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A．3B．4C．5D．6二、填空题1.在一个循环队列中，队首指针指向队首元素的_________。2.数组中每一个数据通常称为，用下标区分，其中下标的个数由数组的决定。3.一个图的表达法是唯一的，而表达法是不唯一的。4.在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许个，最少允许个5.对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后的得到结果为。10.高度为1的平衡二叉树的结点数至少有________个，高度为2的平衡二叉树的结点数至少有________个。三判断1.顺序存储结构属于静态结构，链式结构属于动态结构。（）2.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）3.带权无向图的最小生成树必是唯一的。（）4.B-树和B+树都可用于文献的索引结构。（）5.在用堆排序算法排序时，假如要进行增序排序，则需要采用"大根堆"。（）四、应用题1.模式串p="abaabcac"的next函数值序列为多少？2.设二维数组A[5][6]的每个元素占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。规定用哈希（Hash）方法将它们存入具有10个位置的表中。（1）将上述关键字（标记符）构造一个哈希函数，使得发生冲突尽也许地少；（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。4.给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？作业题（五）一、单项选择题1.一组记录的关键码为（46，79，56，38，40，84），则运用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A．(38,40,46,56,79,84) B．(40,38,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.d3．对于有n个结点的二叉树,其高度为（）A．nlog2nB．log2nC．ëlog2nû+1D．不拟定4.如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是（）。A．1354267 B．1347625C．1534276 D．12476535.采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。A．中序遍历 B．先序遍历C．后序遍历 D．按层次遍历6.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V77.顺序查找法合用于查找顺序存储或链式存储的线性表，平均比较次数为（）。在此假定N为线性表中结点数，且每次查找都是成功的。A．N+1 B．2log2NC．log2N D．N8.下面关于m阶B树说法对的的是（）。①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。A．①②③ B．②③C．②③④ D．③9.已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算Hash地址进行散列存储，若运用链地址法解决冲突，则在该Hash表上进行查找的平均查找长度为（）。A．1.0 B．7/6C．4/3 D．3/210.在排序算法的实行过程中，使用辅助存储空间为O（1）的有（）。A．简朴排序法 B.快速排序法C．归并排序法 D.基数排序法二、填空题1.n（n大于1）个结点的各棵树中，其中深度最大的那棵树的深度是n，它共有________个叶子结点和________个非叶子结点。2.设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60，x是y的左孩子。则拟定x的后继最多需通过________中间结点（不含后继及x自身）3.高度为2（第2层为叶子）的3阶B-树中，最多有________个关键字。4.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是________算法。5.简朴选择排序和起泡排序中比较次数与序列初态无关的算法有________。6.串的链式存储结构是将存储区域提成一系列大小相同的结点,每个结点有两个域域和域。其中域用于用于存放数据，域用于存放下一个结点的指针三．判断1.顺序存储的线性表可以随机存取。（）2.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）3.十字链表是无向图的一种存储结构。（）4.折半查找方法合用于排列连续顺序文献的查找。（）5.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）四、应用题1.用十字链表表达一个有k个非零元素的mxn的稀疏矩阵，则其总的结点数为多少？2.G=(V,E)是一个带有权的连通图,则：（1）．请回答什么是G的最小生成树；（2）．G为下图所示,请找出G的所有最小生成树。3.请分别叙述在一个连续顺序文献中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文献中记录应当满足什么条件？4.设待排序文献之排序码为（88，33，22，55，99，11，66），采用顺序存储。请用直接选择排序算法对上述文献进行排序，用图示说明排序过程。----------------------------------------------作业题一参考答案：一、单项选择题1、C2、B3、D4、C5、B6、B7、A8、C9、D10、D二、填空题1、非零元很少2、操作受限（或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊），先进先出(或后进后出)3、简朴选择排序4、O(n2)，O(e)，O(n)5、邻阵矩阵，邻接表三、算法答：intcount=0;voidonechild(Btreet){if(t!=NULL){onechild(t->lchild);onechild(t->rchild);if(t->lchild!=NULL&&(t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL)count++;}}四、应用题1、答：2、答：（1） （2）CC11C11C2FGGG3AD3AD3AD11C2FG1C1C4422FG（5） （6）33ADEBEB561C61C441CB543A1CB543AD2FG2FG 3、答：由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。用线性探测再散列解决冲突，ASLsucc=27/104、答：成功查找平均比较查找长度为：（n+1）/n[log2（n+1）]-1。作业题二参考答案：一、单项选择题1、C2、C3、B4、C5、D6、C7、C8、B9、A10、C二、填空题1、2n0-12、6，2613、élog2kù+14、255、N-16、最优二叉树，最小的二叉树7、根结点，各子树三、应用题 1、41241263713922此树的带权途径长度WPL=9*1+6*2+4*3+(1+2)*4=452、答：6（1）插入10 (2)插入6 (3)插入3 (4)61010 1010103调整610103调整61066 （5）插入2 （6）插入5 （7）插入4 （8）65365324101063210632调整106325调整106325553、答：当关键字为3时，比较次数为4；当关键字为8时，比较次数为1；当关键字为19时，查找不成功；4、答：（2）略（3）深度优先遍历序列：ABCDE广度优先遍历序列：ABCED（4）关键途径A--B（长100）作业题三参考答案：一、单项选择题1、D2、B3、A4、C5、D6、A7、B8、C9、B10、D二、填空题1、2，32、43、n-14、e5、相同类型数据，地址连续6.三元组顺序表，三元组7.矩阵转置三、应用题1、答： 二叉链表∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②① ∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②① (2 2、答：A ACDBCDB EE 3.答：Prim算法构造最小生成树的环节如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）即：4.答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。设该完全二叉树有d层，则除最后一层外各层的结点个数分别为：1，2，4，8，16，32，…，即第i层的结点个数为2i-1。这里第8层有8个结点，显然第8/层是最后的一层，那么第7层的结点个数为27-1=64个，其中的4个结点有8个叶子结点，余下的为叶子结点，个数为64-4=60，所以该完全二叉树的叶子结点个数为60+8=68个。5.答：相应的二叉树形式如图所示：作业题四参考答案：一、单项选择题1.A2