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

1、数据结构专升本模拟题及参考 答案3)东北农业大学网络教育学院数据结构专升本作业题作业题（一）、单项选择题1.从逻辑上可以把数据结构分为（A.动态结构、静态结构B结构C.线性结构、非线性结构D.初等结构、构造型结构2.链表不具有的特点是（）A.插入、删除不需要移动元素B可随机访问任一元素C.不必事先估计存储空间D所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。For（i=1;i=n ;i+）For（j=1;j=l;j+）For（k=1;ktop! =0Btop= =0C. s-top! =m0 top= =m07、循环队列用数组Am（下标从0到m-1）存放其元 素值，已知其头尾指

2、针分别是front和rear，贝U当前队 列中的元素个数是（）。A（rear-fro nt+m）%mB. rear-front+1Crear-fr ont-1D. rear-fr ont&设有两个串 的运算称作（90,）。100106）。s-s-S1与S2,求串S2在S1中首次出现位置A.连接B求子串 -9、设串S1=ABCDEFG S2=PQRST,函数con(x, y) 返回x和y串的连接串，subs(s,i,j)返回串S的的从 序号i的字符开始的j个字符组成的子串，len(s)返回 串S的长 度，贝Icon(subs(S1,2,len(S2),subs(S1,len(S2),2)

3、的 结果是()。A. BCDEFB.BCDEFGCBCPQRSTD. BCDEFEF10、数组常用的两种基本操作是(A.建立与查找除与查找C.插入与索引找与修改二、填空题1._所谓稀疏矩阵指的是分布没有规律。子串C模式匹配D判A.连接B求2._队列是_ 的线性表，其运算遵循 _ 的原则。3.空格串是_ 。4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有_ 。5、 设图G有n个顶点和e条边，则对用邻接矩阵表示 的图进行深度或广度优先搜索遍历时的时间复杂度为_ ，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为_，图的深度或广度优先搜索遍历时的空间复杂度均为_。6、 一个图

4、的 _ 表示法是唯一的，而 _ 表示法是不唯一的。三、 算法设二叉树采用二叉链表结构，试设计一个算法统计给定 二叉树中的一度结点数目。四、 应用题1、对关键字无序序列（36，25，48,12，65，43,20,58）进行直接选择排序，请写出每一趟排序的结果。（10分）2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。 （10分）3、 已知记录关键字集合为(53,17,19,61,98,75,79,63,46,49)要求散列到地址区间(100,101,102,103,104,105,106,107,108,109)内，若产生冲突用开型寻址法的线性探测法解决。要求 写出选用的散列函数；形成的散列表

5、；计算出查找成功 时平均查找长度与查找不成功的平均查找长度。(设等概 率情况)4、设被查找文件有4095个记录，对每个记录查找记录 概率相等，若采用顺序查找，成功查找平均比较次数为 多少？作业题（二）、单项选择题1.有六个元素6,5,4,3, 哪一个不是合法的出栈序列？A. 5 4 3 6 1 2 B. 4 5 3 12 1 D. 2 3 4 1 5 62.栈和队都是（）A.顺序存储的线性结构线性结构C.限制存取点的线性结构D.非线性结构3.顺序查找法适合于存储结构为（A散列存储2,1的顺序进栈，问下列（ ）2 6 C. 3 4 6 5B.链式存储的非限制存取点的）的线形表。B顺序存储或链接存

6、储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. nB. n/2C Iog2nD. Iog2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找 速度()A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减7、已知一

7、有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是()。二、填空题1.设no为哈夫曼树的叶子结点数目，则该哈夫曼树共A.v1,v2,v3,v5,v4v4,v5C.v1,v3,v4,v5,v2&为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（A.顺序存储C.索引存储B. v1,v2,v3,D. v1,v4,v3,）。B.链式存储9、在一个具有n个顶点的有向图中，若所有顶点的出 度之和为s，则所有顶点的入度之和为（）。A. sB. s-1C. s+1D. n10、如图所示，给出由7个顶点组成的无向图。从顶A出发，对它进行深度

8、优先搜索得到的顶点序列是（ ）。A. A E C D B F G占八B. A G B F D E CCA C E D B G FD. A B D G F E C有_结点。2.有数据WG=7 19,2,6,32,3,21,10，则所建Huffman树的树高是 _ ，带权路径长度WPL为。3.设一棵完全二叉树叶子结点数为k,最后一层结点数2,则该二叉树的高度为 _。4.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点 所在的块时，每块应分_ 个结点最佳。5、设G为具有N个顶点的无向连通图，贝U G中至少有 条边。6、哈夫曼树(Huffman Tree)

9、又称_。它是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, E0 100 30

10、10060 0 2010 0500(1) .画出逻辑图；(2) .画出图的十字链表存储；(3) .基于邻接矩阵写出图的深度、(4) 计算图的关键路径。的图的邻接矩阵,广度优先遍历序列;作业题（三）一、单项选择题1串的长度是指（）A.串中所含不同字母的个数B串中所含非空格字符的个数C.串中所含不同字符的个数D串中所含字符的个数2.设有数组Ai,j， 数组的每个元素长度为3字节，i的值为1到8,j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（）。A. BA+141B.BA+180C. BA+222D.BA+2253算法分析的两个主要方面是（）。A

11、.空间复杂性和时间复杂性B.壬确性和简明性C.可读性和文档性D.数牧据复杂性和程序复杂性4.算法分析的目的是（）。A.找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性5.下面程序段的时间复杂性的量极为(Int fun (i nt n) int i=1,s=1;While(snext= =LD=NULL8.在一个长度为n的线性表中，删除值为需要比较元素和移动元素的总次数为()O( n/2)0()。.L-A.(n+1)/2B.n/2C. nD.n+19.一个顺序存储线性表的第一个元素的存储地址是90,每个元素的长度是2,则第6个元素的存储地址是

12、()。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（n1）个_的有序组合，数组中的

13、数据是按顺序存储在一块 _ 的存储单元中。6.采用顺序存储结构表示三元组表（Triple Table来实现对稀疏矩阵的一种压缩存储形式，就称 为，简称表。7. _运算是矩阵运算中最基本的一项，它是将一一个mx n的矩阵变成另外一个n x m的矩阵，同时使原 来矩阵中元素的行和列的位置互换而值保持不变。三、应用题1、对于下图所示的二叉树，画出二叉链表存储结构图。2、请画出下图所示的树所对应的二叉树） ，3.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以为起点，试画出构造过程）4.已知完全二叉树的第8层有8个结点，则其叶子结点是多少?5.画出如图所示中树的二叉树

14、的表示形式。单项选择题2011g1014IS4/61.将两个各有n个元素的有序表归并成一个有序表， 其最少得比较次数是（ ）。D n-12.一个有n个顶点的无向连通图，它所包含的连通分 量个数为（ ）。A. 0B. 1C. nD. n+13.数据文件的基本操作中最重要的操作是（A.插入B.删除C.修改D.检索4.对关键码序列28,16,32,12,60,2,排序，从小到大一次划分结果为（）。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）

15、5.如果只想得到1000个元素组成的序列中第5个最小 元素之前的部分排序的序列，用B. 2n-12n）。5,72快速（）方法最快。A.堆排序B.快速排序C.插入排序D.归并排序6.算法分析的目的是（）。A.找出数据结构的合理性 法中的输入和输出的关系B.研究算C.分析算法的效率以求改进D分析算法的易懂性和文档性7.二叉树的第I层上最多含有结点数为()A. 21B.2I-1-1 C.21-1D.21-18.循环队列存储在数组A中，长度为m则入队时的操作为()。A. rear=rear+1 B.rear=(rear+1) mod(m-1)C. rear=(rear+1) mod mD.rear=(

16、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，4

17、8，91）进行一趟快速排序之后的得到结果为_。10.高度为1的平衡二叉树的结点数至少有 _ 个,高度为2的平衡二叉树的结点数至少有_。三判断1顺序存储结构属于静态结构，链式结构属于动态结 构。 （）2.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也 一定相同。（）3.带权无向图的最小生成树必是唯一的。（）4. B-树和B+树都可用于文件的索引结构。（）5.在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆“。（）四、应用题1.模式串p=abaabcac的next函数值序列为多少？2.设二维数组A56的每个元素占4个字节，已知LOC（aO,O

18、）=1000,A共占多少个字节？A的终端结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起 始地址分别为多少？3.设a,b,c,d,e五个字符的编码分别为123,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,请写出快速排序第一趟的结果；堆排序时所建的初 始堆；归并排序的全过

19、程。然后回答上述三中排序方法 中那一种方法使用的辅助空间最少？在最坏情况下那种 方法的时间复杂度最差？作业题(五)亠、单项选择题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)

20、B. (d) C. c D. d3.对于有n个结点的二叉树，其高度为( )A. nlog2n B.log2nC.log?n +1 D确定4.如图所示，给出由7个顶点组成的无向图。从顶点 出发，对它进行深度优先搜索得到的顶点序列是(A.C.采用邻接表存储的图，其深度优先遍历类似于二叉)。B先序遍历D按层次遍历B.1 3 4 7 6 2 5D.1 2 4 7 6 5 35.树的(A中序遍历C后序遍历6.已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7,E=VV1,V2,VV1,V4,VV2,V5,VV3,V5,VV3,V6,VV4,V6,VV5,V7,G的拓扑序列是()A

21、Vl,V3,V4,V6,V2,V5,V7BVi,V3,V2,VqV4,V5,V7CVl,V3,V4,V5,V2,V6,V7DVl,V2,V5,V3,V4,V6,V77.顺序查找法适用于查找顺序存储或链式存储的线 性表，平均比较次数为（ ）。在此假定N为线性表中结点数，且每次查找都是成功的。A.N+1B.2log2NC.logzND.N8.每个结点至少有两棵非空子树； 至多有m1个关键字；所有叶子在同一层上；当插入一个据项引起B树结点分裂后，树长高一层。AB.C.D.9.已知一个线性表（38,25,74,63,52,48）,假定采用h（k）=k%7计算Hash地址进行散列存储，若利用 链地F面关

22、于数址法处理冲突，则在该Hash表上进行查找的平均查 找长度为（）。A.1.0C.4/310.在排序算法的实施过程中，使用辅助存储空间为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.分别采用堆排序，快速排序，冒泡排序和归并

23、排序， 对初态为无序的表，则平均情况下最省时间的是法。5.简单选择排序和起泡排序中比较次数与序列初态无关的算法有_。6.串的链式存储结构是将存储区域分成一系列大小相B.7/6D.3/2同的结点 海个结点有两个域 _ 域和_ 域。其中域用于用于存放数据，域用于存放下一个结点的指针三判断1顺序存储的线性表可以随机存取。（）2.即使对不含相同元素的同一输入序列进行两组不 同的、合法的入栈和出栈组合操作，所得的输出序列也 一定相同。 （）3.十字链表是无向图的一种存储结构。（）4.折半查找方法适用于排列连续顺序文件的查找。（ ）5.在执行某个排序算法过程中，出现了排序码朝着 最终排序序列位置相反方向移

24、动，则该算法是不稳定的。（ ）四、应用题1.用十字链表表示一个有k个非零元素的m x n的稀 疏矩阵，则其总的结点数为多少？2.G=(V,E)是一个带有权的连通图，则：(1).请回答什么是G的最小生成树；(2) . G为下图所示，请找出G的所有最小生成树3.请分别叙述在一个连续顺序文件中采用顺序查找 法，折半查找法和分块查找法查找一个记录，该文件中 记录应该满足什么条件？4.设待排序文件之排序码为(88,33,22,55,99,11,66),采用顺序存储。请用直接选择排序算法对上 述文件进行排序，用图示说明排序过程。东北农业大学网络教育学院数据结构专升本作业题参考答案作业题一参考答案:一、单项

25、选择题1、C 2、B 3、D 4、C 5、B 6、B 7、A 8、C 9、D 10、D二、填空题1、非零元很少2、操作受限(或限定仅在表尾进行插入和限定仅在表 头进行删除操作或限制存取点或特殊)，先进先出(或后 进后出)3、简单选择排序4、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!=NULLt-lchil

26、d!=NULL & t-rchild=NULL )coun t+;|四、应用题1、LF4G2F(5)(6)3、答：由于地址空间为10,且从100开始，故散列函数 选为H（key）=key%7+100。教列地址100101102103104106107108109关键字98791751196175649比较次数121i112351C用线性探测再散列解决冲突，ASLsucc=27/104、答：成功查找平均比较查找长度为：（n+1）/nlog2（n+1）-1。12作业题二参考答案：一、 单项选择题1、C 2、C 3、B 4、C 5、D6、C 7、C 8、B 9、A 10、C二、 填空题1、2

27、no-12、6,2613、log2k +14、255、N-16、最优二叉树，最小的二叉树7、根结点，各子树三、 应用题1、答：不唯一，型对即可10(6)插入5(7)插入4此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=452、答：(1)插入10(2)插入6(4)-10调插入36 -(5)插入2(8)3、答：当关键字为3时，比较次数为4; 当关键字为8时，比较次数为1;作业题三参考答案：一、 单项选择题1、D 2、B 3、A 4、C 5、D6、A 7、B 8、C 9、B 10、D二、 填空题1、2，32、4 3、n-1 4、e4、（3）深度优先遍历序列:ABCE（4）关键路径

28、A-B略ABC当关键字为19时，查找不成功;05.相同类型数据，地址连续6.三元组顺序表，三元组7.矩阵转置应用题1、答:3.答：Prim算法构造最小生成树的步骤如24题所示， 为节省篇幅，这里仅用Kruskal算法，构造最小生成树过二叉链表(22、答：A人人匚人程如下：(下图也可选(2,4)代替(3,4),(5,6)代替(1,5)4.答：他各层的结点是满的。设该完全二叉树有d层，则除 后一层外各层的结点个数分别为：1,2, 4, 8, 16,32, 即第i层的结点个数为2i-1 o这里第8层有8个结点， 然第8/层是最后的一层，那么第7层的结点个数为27-仁64个， 其中的4个结点有8个叶子

29、结点，余下的为 叶子结点， 个数为64-4=60， 所以该完全二叉树的叶子 结点个数为60+8=68个o5.答：对应的二叉树形式如图所示：由完全二叉树的定义可知，除最后一层外，其(9 v J(O0作业题四参考答案：一、 单项选择题1. A 2. B 3. D 4. B 5. D6、C 7、C 8、C 9、B 10、D二、 填空题1.答：前一个位置2.答：数组元素，数组元素，维数3.答：邻阵矩阵，邻接表4.答：9,45.答：48 44 52 64 80 916. 1，2三判断1.答：“2.答：x3.答：x4.答：“5.答：“四、应用题1.答：模式p的next函数值如下：2.答：A共120个字节a4,5的起始地址为：1116。按行优先存储时，a2,5的起始地址为：1068按列优先存储时，a2,5的起始地址为：110 8。3.答：（1）哈希函数H（key）=（关键字各字符编码