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

1、、单项选择题1. 从逻辑上可以把数据结构分为(A.动态结构、静态结构C.线性结构、非线性结构2. 链表不具有的特点是(A插入、删除不需要移动元素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)C O(n2)4. 在一个带头结点的双向循环链表中，个指针域的值。A2C4作业题(一)两大类。顺序结构、链式结构初等结构、构造型结构B .可随机访问任一 元素所需空间与线性长度成正比)。 O(n) O(n3)若要在 p 所指向的结点之前插入一个新结点，

2、 则需要相继修改 ()365、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是 2，则第 6 个元素的存储地址是()。A98 100C102 1066、判定一个栈s (最多元素为 m0为空的条件是()。A. s- top! =0s- top= =0C. s- top! =m0s-top= =m07、循环队列用数组 Am(下标从0到m-1)存放其元素值，已知其头尾指针分别是front和 rear ，则当前队列中的元素个数是()。A.( rear-front+m) %m. rear-front+1C. rear-front-1D. rear-front设有两个串S1与S2,求串S2

3、在S1中首次出现位置的运算称作(A.连接B求子串C.模式匹配D判子串设串S1='ABCDEFG； S2='PQRST'，函数con (x, y)返回x和y串的连接串,从 序 号 i 的 字 符 开 始 的 j 个 字 符 组 成 的 子 串 ， len(s) 返 con(subs(S1,2,len(S2),subs(S1,len(S2),2)的结果是( )。8、9、)。subs(s,i,j) 回 串 S返回串 S 的 的 长 度 ， 则A. BCDEFB . BCDEFGC. BCPQRST.BCDEFEF10、数组常用的两种基本操作是（A.建立与查找C.插入与索引二、

4、填空题1. 所谓稀疏矩阵指的是 删除与查找查找与修改且分布没有规律。2. 队列是的线性表，其运算遵循的原则。3.空格串是4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为，图的深度或广度优先搜索遍历时的空间复杂度均为6、一个图的三、算法设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。四、应用题表示法是唯一的，而表示法是不唯一的。1对关键字无序序列（36, 25, 48, 12, 65, 43, 20, 58）

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

6、素 6，5， 4， 3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1 D. 2 3 4 1 5 62. 栈和队都是（A.顺序存储的线性结构B.链式存储的非线性结构C. 限制存取点的线性结构D.限制存取点的非线性结构3、顺序查找法适合于存储结构为（）的线形表。A.散列存储B. 顺序存储或链接存储C. 压缩存储D.索引存储4、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是A . ( 100， 80， 90， 60， 120 ，110，130)B.100，120，110，130，80，

7、60 ， 90 )C. ( 100， 60， 80， 90， 120 ，110，130)D.(100 ，80， 60 ，90，120 ， 130， 110)5、折半查找的平均比较次数为（）。A. nB.n/2C. log2nD.log2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（A. 必定快B.不一定C.在大部分情况下要快D. 取决于表递增还是递减7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1 出发，所得到的顶点序列是（）。A. v1, v2, v3, v5, v4C. v1, v3, v

8、4, v5, v212A34ASB. v1, v2, v3, v4 , v5D. v1, v4, v3, v5 , v2B.链式存储D.散列存储A. sB.s-1C. s+1D.10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是A. A E C D B F GB. A G B F D E CC. A C E D B G FD. A B D G F E C二、填空题1.设no为哈夫曼树的叶子结点数目则该哈夫曼树共有个结点。2.有数据 WG=7 19, 2, 6, 32,3, 21, 10，则所建 Huffman树的树高是，带权路径长度WPL8、为了方便

9、地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（A.顺序存储C.索引存储9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为S,则所有顶点的入度之和为（为。3、设一棵完全二叉树叶子结点数为4、采用分块查找时，若线性表中共有k,最后一层结点数2,则该二叉树的高度为625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 _个结点最佳。5、 设G为具有N个顶点的无向连通图，贝y G中至少有条边。6、哈夫曼树（Huffman Tree ）又称。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL。;依次先序遍历树7、树的先序遍历过程如下：若树为空，则进

10、行空操作；若树非空，则访问树的 的三、应用题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的图的邻接矩阵,01003010"300CC306002030100贋5010(1).画出逻辑图（2）.画出图的十字链表存储;（3）.基于邻接矩阵写出图的深度、广度优先遍历序列;（

11、4）.计算图的关键路径。作业题（三）一、单项选择题1 .串的长度是指（A.串中所含不同字母的个数B .串中所含非空格字符的个数C.串中所含不同字符的个数D .串中所含字符的个数2. 设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8 , j的值为1到10,数组从内存首地址BA开始顺序存放，当用以列为主存放时,元素 A5, 8的存储首地址为（）。A. BA+141 B. BA+180 C. BA+222D. BA+2253. 算法分析的两个主要方面是（A.空间复杂性和时间复杂性.正确性和简明性C.可读性和文档性.数据复杂性和程序复杂性4. 算法分析的目的是（A.找出数据结构的合理性.研

12、究算法中的输入和输出的关系c.分析算法的效率以求改进.分析算法的易懂性和文档性5. 下面程序段的时间复杂性的量极为Int fun (i nt n) int i=1,s=1;While(s <n)S+= +I;Return I;.O(lbn).O()A. O(n/2)C. 0(n)6.线性表是(A. 个有限序列,可以为空.一个有限序列，不能为空7.C. 一个无限序列,可以为空 一个无限序列，不能为空带头结点的单链表L为空的判定条件是(A. L= =NULL.L-next= =NULLC. L-next= =L.I_! =NULL8.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和

13、移动元素的总次数为(A. (n+1) /2.n/2C. n.n+19.一个顺序存储线性表的第一个元素的存储地址是90,每个元素的长度是2,则第6个元素的存储地址A . 98.100C. 102.10610.如果某链表中最常用的操作是取第i个结点及其前驱，则采用(。存储方式最节省时间。A.单链表.双向链表C .单循环链表二、填空题1.高度为2的二叉树的结点数至少有.顺序表个，高度为3的二叉树的结点数至少有个。2.在顺序表(8,11,15,19,25,26,30,33,42,48,50。中，用折半查找关键字值 20,需做的关键字比较次数 为3. 在有n个顶点的无向图中，每个顶点的度最大可达4. 已

14、知广义表 A= (a, b, c), ( d, e, f),则广义表运算 head (tail (tail(A) =。5. 数组(Array )是n(n> 1)个的有序组合，数组中的数据是按顺序存储在一块 存储单元中。6. 采用顺序存储结构表示三元组表( Triple Table ),来实现对稀疏矩阵的一种压缩存储形式，就称7.为，简称表。m x n的矩阵变成另外一个nx m的矩阵，同时.运算是矩阵运算中最基本的一项，它是将一个使原来矩阵中元素的行和列的位置互换而值保持不变。三、应用题1对于下图所示的二叉树，画出二叉链表存储结构图。2、请画出下图所示的树所对应的二叉树。3.已知一个无向图

15、如下图所示，要求分别用Prim 和 Kruskal算法生成最小树（假设以为起点，试画出构造过程）。4.已知完全二叉树的第 8层有8个结点,则其叶子结点是多少?5.画出如图所示中树的二叉树的表示形式。AC作业题（四）1.2.3.、单项选择题将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（A. nC. 2n.2n-1.n-1一个有n个顶点的无向连通图，它所包含的连通分量个数为（A. 0C. n数据文件的基本操作中最重要的操作是（A.插入C.修改B.D.B.D.n+1删除检索2.3.4.4.对关键码序列 28, 16, 32, 12, 60, 2,5, 72快速排序，从小到大一次划分

16、结果为（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.找出数据结构的合理性.研究算法中的输入和输出的关系C.分析算法的效率以求改进.分析算法的易懂性和文档性7.二叉树的第I层上最多含有结点数为（II-1A. 2 B . 2-1 C . 2I-1D . 2I -1循环队列存储在

17、数组 A中，长度为m则入队时的操作为（A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)9.广义表满足Head（A）=Tail（A），则A为（A.()(0)C. （0,（）10.在一棵度为3的树中，度为3的结点数为2个,（0 , （） , 0）度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（。个。C. 5二、填空题1.在一个循环队列中，队首指针指向队首元素的 数组中每一个数据通常称为 ,一个图的表示法是唯一的，而 _用下标区分， 表示法是不唯一的。其中下标

18、的个数由数组的决定。个,5.在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许 最少允许对关键字序列（52, 80, 63, 44, 48, 91）进行一趟快速排序之后的得到结果为10.高度为 1 的平衡二叉树的结点数至少有个，高度为 2 的平衡二叉树的结点数至少有个。三 判断1. 顺序存储结构属于静态结构，链式结构属于动态结构。2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作， 所得的输出序列也一定相同。3. 带权无向图的最小生成树必是唯一的。 （4. B-树和B+树都可用于文件的索引结构。（5. 在用堆排序算法排序时，如果要进行增序排序， 四、应用

19、题则需要采用"大根堆"。（ ）1.模式串p="abaabcac"的next函数值序列为多少?2. 设二维数组 A56 的每个元素占 4个字节，已知 LOC（a0,0） =1000， A 共占多少个字节? A 的终端结 点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？3.设a,b,c,d,e五个字符的编码分别为1,2,3,4,5,并设标识符依以下次序出现:要求用哈希（Hash）方法将它们存入具有10个位置的表中。ac,bd,aa,be,ab,ad,cd,bc,ae,ce。1）将上述关键字（标识符）构造一个哈希函数，使得发生冲

20、突尽可能地少；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)广义

21、表 A=(a,b,(c,d),(e,(f,g),D.（40,38,46,84,56,79）则下面式子的值为 （GetHead(GetTail(GetHead(GetTail(GetTail(A)A. (g) B. (d) C. c D. d3.对于有n个结点的二叉树，其高度为（A. nlog 2n B . log 2nC . log 2n_+1不确定4.如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是B. 1 3 4 7 6 2 5C.D. 1 2 4 7 6 5 35.采用邻接表存储的图，其深度优先遍历类似于二叉树的（A.中序遍历B.先序遍历C.后序遍

22、历D.按层次遍历6.已 知 有 向 图 G=（V,E）中 V=V 1,V2,V3,V4,V5,V6,V7E=<V 1,V2><V1,V3><V1,V4><V2,V5><V3,V5><V3,V6><V4,V6><V5,V7><V6,V7>,G 的拓扑 序列是C.7.V1,V3,V4,V6,V2,V5,V7V1,V3,V4,V5,V2,V6,V7B. V1,V3,V2,V6,V4,V5,V7D. V1,V2,V5,V3,V4,V6,V7顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较

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

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

25、小相同的结点,每个结点有两个域域和域。其中三.判断域用于用于存放数据,域用于存放下一个结点的指针1. 顺序存储的线性表可以随机存取。2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。3.十字链表是无向图的一种存储结构。（）4.折半查找方法适用于排列连续顺序文件的查找。5.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。()四、应用题1. 用十字链表表示一个有k个非零元素的m x n的稀疏矩阵，则其总的结点数为多少?2. G=(V,E)是一个带有权的连通图,则:(1).请回答什么是G的最小生成树;

26、(2). G为下图所示，请找出G的所有最小生成树。3. 请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文 件中记录应该满足什么条件?4.设待排序文件之排序码为(88, 33, 22, 55, 99, 11 , 66),采用顺序存储。请用直接选择排序算法 对上述文件进行排序，用图示说明排序过程。作业题一参考答案: 一、单项选择题 1、C 2、B 3、D 4、C 5、B 6、B 7、A 8、C 9、D 10、D二、填空题1、非零元很少,先进先出(或2、操作受限(或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊) 后进后出)3、简单选择排序4、

27、0(n2), 0(e), 0(n)5、邻阵矩阵，邻接表三、算法答: int count = 0;void on echild ( Btree t) if ( t!=NULL) on echild ( t->lchild );on echild ( t->rchild );if ( t->lchild!=NULL && (t->rchild!=NULL | t->lchild!=NULL && t->rchild=NULL )coun t+;四、应用题 1、 答:(0)33t25<012 t65432053(1)12吟43

28、36es4320 t53122043 t36654325 t5312202536654348531220253665t43 t48531220253643ES5 t48 +531220253643143J3553 t(T)122025304343L581es2、 答:散列地址10010110210310410510610710S109关键字98637917531961754649比较次数111113510由于地址空间为 10,且从100开始，故散列函数选为 H （key） =key%7+100。3、答:用线性探测再散列解决冲突，ASLsucc=27/104、答：成功查找平均比较查找长度为：（n

29、+1） /nlog2 （ n+1）-1。作业题二参考答案:一、单项选择题1、C 2、C 3、B 4、C 5、D6、C 7、C 8、B 9、A 10、C二填空题1、2n 0-12、6, 2613、flog 2k 平14、255、N-16、最优二叉树，最小的二叉树7、根结点，各子树三、应用题1、 答：不唯一，型对即可此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=452、答:插入10CD插入6CD插入3调整插入2(6)插入5(7)插入(8)42co3、答：当关键字为3时，比较次数为4;当关键字为8时，比较次数为1 ；当关键字为19时,查找不成功;(2)略(3)深度优先遍历序列:

30、ABCD旷度优先遍历序列： ABCE( 4 )关键路径 A-B(长 100)作业题三参考答案:一、单项选择题 1、D 2、B 3、A 4、C 5、D 6、A 7、B 8、C 9、B 10、D 二、填空题 1、2、3、n-14、e5、相同类型数据，地址连续6. 三元组顺序表，三元组7. 矩阵转置 三、应用题 1、答:二叉链表AA AA I(2H|a II a| A3. 答:Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法,构造最小生成树过程如下：(下图也可选(2,4)代替(3,4),(5,6)代替(1,5)4.答：由完全二叉树的定义可知,除最后一层外，其他各层

31、的结点是满的。设该完全二叉树有d层，则除。这里第8层有最后一层外各层的结点个数分别为：1, 2, 4, 8, 16, 32,，即第i层的结点个数为2i-1 8个结点，显然第8/层是最后的一层，那么第 7层的结点个数为27-1=64个，其中的4个结点有8个叶子结点,余下的为叶子结点，个数为64-4=60 ,所以该完全二叉树的叶子结点个数为60+8=68个。5.答:对应的二叉树形式如图所示:作业题四参考答案:一、单项选择题1. A 2. B 3. D4.B 5.6、C 7、C 8、C 9、B 10、二、填空题1.答：前一个位置2.答：数组元素，数组元素，维数3.答：邻阵矩阵，邻接表4.答：9, 4

32、答：48 44 52 64 80 911 , 2三.判断5.6、1.2.答：X3.答：X答：V答：V四、应用题4.5.1.答：模式P的next函数值如下:丈件d）鏑辑th）现宙jifiA d） 幅皿 工具 现心 口俎）S助 :倒译匡英中旦日中出中英困取消设gfl _«l I a I I EJEl I JBl 涉 D *2 4-4 1 i4fii ME 百简述一个字荷串中子串的枸威.智:一个字荷串中任慝连乘化宇符组成的子序测称为字精串子串。空串和空格串有何区别亍字符串中空格苻有何意义？空串在串的址理中有何作用?巻:不含任何字符的电魅菱空串甚虽检廈为零i仅含有空格字符曲齟訓串-它的长度

33、为申空格苻的个数。空格苻在字符串中可用来分隔一般的字荷使于闻读和识别-空格苻会 占用有串长.空串在处理过程中可用于作対任S字符串的子串I 煮基虽曲长度小于一个常数，则采用何聊存循方式最节省空间？答，采用顺序串最节省空间，因为顺序串惡硼比，乔需要指怦罐。模式串p="共勰"的next圃数值序列対多少？客 模式口的next國数值如下ji0L模式串，abneslE-L0算袪设计题（9+4）5 3 4 5 a a b C0 112采闸匝停结构存储带S,騙写一个蔺教删除3中第iJt宇符开始的j个字瓶智；蚯1顯 * .Uj（31 ring * 5. Lal t i.tii Dtj.nl k；ifIcn）Ui q m IJ 申 _ I_a館s* -f gjsmof)- 、 o 匕|風舊阖左I* M r i ” = 两 S 4凶益 押五第型21心3/Efte. 5. zS米宙爵傍-J数老芜杓2.答：A共120个字节。6行刃甜一 ：丁中