《2022年数据结构专升本模拟题及参考答案定义 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构专升本模拟题及参考答案定义 .pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、东北农业大学网络教育学院数据结构专升本作业题作业题（一）一、单项选择题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;k2，则该二叉树的高度为_。4.采用分块查找时，若线性表中共有625 个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块
2、应分个结点最佳。5、设 G为具有 N个顶点的无向连通图，则G中至少有条边。6、哈夫曼树（ Huffman Tree ）又称。它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 。7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的；依次先序遍历树的。三、应用题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - 1、给定权值集合1, 4, 2, 6, 9, 构造相应的哈夫曼树, 并计算它的带权路径长度。
3、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的图的邻接矩阵，05001020060010301000（1） 画出逻辑图；（2） 画出图的十字链表存储；（3） 基于邻接矩阵写出图的深度、广度优先遍历序列；（4） 计算图的关键路径。作业题（三）一、单项选择题1串的长度是指（）A串中所含不同字母的个数 B串中所含非空格
4、字符的个数C串中所含不同字符的个数 D串中所含字符的个数2设有数组Ai,j，数组的每个元素长度为3 字节， i 的值为 1 到 8 ，j 的值为 1 到 10，数组从内存首地址 BA开始顺序存放，当用以列为主存放时，元素A5， 8 的存储首地址为( )。A. BA+141 B. BA+180 C. BA+222 D. BA+225 3算法分析的两个主要方面是（） 。A空间复杂性和时间复杂性 B正确性和简明性C可读性和文档性 D数据复杂性和程序复杂性4算法分析的目的是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心
5、整理 - - - - - - - 第 5 页，共 20 页 - - - - - - - - - A找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进 D分析算法的易懂性和文档性5.下面程序段的时间复杂性的量极为（） 。Int fun(int n) int i=1,s=1; While(sn) S+= +I; Return I; AO(n/2) BO(lbn) CO(n) DO( ) 6.线性表是（） 。A一个有限序列，可以为空 B一个有限序列，不能为空C一个无限序列，可以为空 D一个无限序列，不能为空7.带头结点的单链表L 为空的判定条件是（） 。AL= =NULL
6、BL- next= =NULL CL-next= =L DL! =NULL 8.在一个长度为n的线性表中，删除值为x 的元素时需要比较元素和移动元素的总次数为（） 。A （n+1） /2 Bn/2 Cn Dn+1 9.一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6 个元素的存储地址是（） 。A98 B100 C102 D106 10.如果某链表中最常用的操作是取第i 个结点及其前驱，则采用（）存储方式最节省时间。A单链表 B双向链表C单循环链表 D顺序表二、填空题1. 高度为 2 的二叉树的结点数至少有_个，高度为3 的二叉树的结点数至少有_个。2. 在顺序表（ 8
7、,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）个的有序组合， 数组中的数据是按顺序存储在一块的存储单元中。6.采用顺序存储结构表示三元组表（Triple Table） ，来实现对稀疏矩阵的一种压缩存储形式，就称为，简称表。7. 运算是矩阵运算中最基本的一项，它是将一个m x n 的矩阵变成另外一个n x
8、m 的矩阵，同时名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 20 页 - - - - - - - - - 使原来矩阵中元素的行和列的位置互换而值保持不变。三、应用题1、对于下图所示的二叉树，画出二叉链表存储结构图。2、请画出下图所示的树所对应的二叉树。3.已知一个无向图如下图所示，要求分别用Prim 和 Kruskal算法生成最小树（假设以为起点，试画出构造过程）。4.已知完全二叉树的第8 层有 8 个结点，则其叶子结点是多少？5. 画出如图所示中树的二叉树的表示形式
9、。A B C D E 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 20 页 - - - - - - - - - 作业题（四）一、单项选择题1. 将两个各有n 个元素的有序表归并成一个有序表，其最少得比较次数是（） 。An B 2n-1 C2n D n-1 2. 一个有 n 个顶点的无向连通图，它所包含的连通分量个数为（） 。A0 B 1 Cn D n+1 3. 数据文件的基本操作中最重要的操作是（） 。A插入B删除C修改D检索4. 对关键码序列28，16，32，12，
10、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 层上最多含有结点数为（）A2I B 2I-
11、1-1 C 2I-1 D2I -1 8循环队列存储在数组A中，长度为m ，则入队时的操作为（） 。A. rear=rear+1 B. 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 （）B （ （） ）C （ （） ， （） ）D （ （） ， （） ， （） ）10. 在一棵度为 3的树中，度为 3的结点数为 2个，度为 2的结点数为 1个，度为 1的结点数为 2个，则度为 0的结点数为（）个。A 3 B4 C 5 D6 二、
12、填空题 1. 在一个循环队列中，队首指针指向队首元素的_。 2. 数组中每一个数据通常称为，用下标区分，其中下标的个数由数组的决定。 3. 一个图的表示法是唯一的，而表示法是不唯一的。 4. 在一个 10 阶的 B-树上，每个数根结点中所含的关键字数目最多允许名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 20 页 - - - - - - - - - 个，最少允许个 5. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后的得到结果为。10. 高度为
13、1 的平衡二叉树的结点数至少有_个，高度为2 的平衡二叉树的结点数至少有_个。三 判断1. 顺序存储结构属于静态结构，链式结构属于动态结构。（）2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）3. 带权无向图的最小生成树必是唯一的。（）4. B-树和 B+树都可用于文件的索引结构。（）5. 在用堆排序算法排序时，如果要进行增序排序，则需要采用大根堆 。 （）四、应用题1. 模式串 p=abaabcac的 next 函数值序列为多少？2. 设二维数组A56 的每个元素占4 个字节，已知LOC（a0,0）=1000，A 共占多少个字节？
14、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，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上
15、述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - 作业题（五）一、单项选择题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 (4
16、0,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. c D. d 3对于有 n 个结点的二叉树, 其高度为（）Anlog2n B log2n C log2n +1 D 不确定4. 如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是（） 。A 1 3 5 4 2 6 7 B1 3 4 7 6 2 5 C 1 5 3 4 2 7 6 D 1 2 4 7 6 5 3 5. 采用邻接表存储
17、的图，其深度优先遍历类似于二叉树的（） 。A中序遍历B先序遍历C后序遍历D按层次遍历6. 已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓 扑序 列是（） 。A V1,V3,V4,V6,V2,V5,V7BV1,V3,V2,V6,V4,V5,V7C V1,V3,V4,V5,V2,V6,V7D V1,V2,V5,V3,V4,V6,V7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - - - - - - - 7.
18、顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（） 。在此假定 N为线性表中结点数，且每次查找都是成功的。A N+1 B2log2NC log2N D N 8. 下面关于 m阶B树说法正确的是（） 。每个结点至少有两棵非空子树；树中每个结点至多有m一1个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后，树长高一层。ABCD 9. 已知一个线性表（38，25，74，63，52，48） ，假定采用 h(k)=k%7 计算 Hash地址进行散列存储，若利用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为（） 。A 1.0 B7/6 C 4/3 D 3/2 1
19、0. 在排序算法的实施过程中，使用辅助存储空间为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. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是_
20、算法。5. 简单选择排序和起泡排序中比较次数与序列初态无关的算法有_。6. 串的链式存储结构是将存储区域分成一系列大小相同的结点,每个结点有两个域域和域。其中域用于用于存放数据，域用于存放下一个结点的指针三判断1. 顺序存储的线性表可以随机存取。（） 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（） 3. 十字链表是无向图的一种存储结构。（） 4. 折半查找方法适用于排列连续顺序文件的查找。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
21、- - - - 第 11 页，共 20 页 - - - - - - - - - 5. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）四、应用题1. 用十字链表表示一个有k个非零元素的 m x n的稀疏矩阵，则其总的结点数为多少？ 2. G=(V,E)是一个带有权的连通图,则：（1） 请回答什么是G的最小生成树；（2） G为下图所示 ,请找出 G的所有最小生成树。 3. 请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文件中记录应该满足什么条件？ 4. 设待排序文件之排序码为（88，33， 22，55，99，1
22、1，66） ，采用顺序存储。请用直接选择排序算法对上述文件进行排序，用图示说明排序过程。东北农业大学网络教育学院数据结构专升本作业题参考答案作业题一参考答案：一、单项选择题1、C 2、B 3、D 4、C 5、B 6、B 7 、A 8、C 9、D 10、D 二、填空题1、非零元很少2、操作受限 （或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊），先进先出 ( 或后进后出 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 20 页 - - - - -
23、- - - - 3、简单选择排序4、O(n2)，O(e)，O(n) 5、邻阵矩阵，邻接表三、算法答：int count = 0; void onechild ( Btree t) 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）（3）（4）1 G C 3 A D 3 A D 1 C 2 F G 名师资料总结 - - -精品资料欢
24、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - （5）（6）3、答：由于地址空间为10，且从 100开始，故散列函数选为H（key）=key%7+100 。用线性探测再散列解决冲突，ASLsucc=27/104、答：成功查找平均比较查找长度为：（n+1）/nlog2（n+1）-1 。作业题二参考答案：一、单项选择题1、C 2、C 3、B 4 、C 5、D 6、C 7、C 8、B 9 、A 10 、C 二、填空题1、2n0-1 2、6，261 3、log2k
25、+1 4、25 5、N-1 6、最优二叉树，最小的二叉树7、根结点，各子树三、应用题2 F G 4 2 F G 3 A D 4 B 5 E 6 1 C 2 F G 1 C 1 C 2 F G 3 A D 4 B 5 1 C 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - 1、答：不唯一，型对即可此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=45 2、答：（1）插入 10 (2) 插入 6 (3) 插入
26、3 (4) （5）插入 2 （6）插入 5 （7）插入 4 （8）3、答：当关键字为3时，比较次数为4；当关键字为 8时，比较次数为1；当关键字为19 时，查找不成功；4 1 2 6 3 7 13 9 22 调整10 10 6 10 6 调整10 6 3 10 6 3 2 10 6 3 2 5 10 6 3 2 5 6 5 3 2 4 10 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - 4、答：（2）略（3）深度优先遍历序
27、列：ABCDE 广度优先遍历序列：ABCED （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 2、4 3、n-1 4、e 5、相同类型数据，地址连续6. 三元组顺序表，三元组7. 矩阵转置三、应用题1、答：二叉链表(2 2、答：3. 答： Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下： （下图也可选 (2,4)代替 (3,4),(5,6) 代替 (1,5)）B C D E A 名师资料总结 - - -精品
28、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 20 页 - - - - - - - - - 即：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=
29、68个。5. 答：对应的二叉树形式如图所示：作业题四参考答案：一、单项选择题1. A 2. B 3. D 4. B 5. D6、C 7、C 8、C 9、B 10 、D 二、填空题1. 答：前一个位置2. 答：数组元素，数组元素，维数3. 答：邻阵矩阵，邻接表4. 答： 9，4 5. 答： 48 44 52 64 80 916、1，2 三判断名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 20 页 - - - - - - - - - 1. 答：2. 答： 3. 答： 4.
30、 答：5. 答：四、应用题1. 答：模式 p的next函数值如下：2. 答： A共 120个字节。a4,5的起始地址为：1116。按行优先存储时，a2,5的起始地址为：1068。按列优先存储时，a2,5的起始地址为：1108。3. 答： （1）哈希函数 H（key）=（关键字各字符编码之和）MOD 7（2）4. 答：一趟快速排序：22,19,13,6,24,38,43,32 初始大堆： 43,38,32,22,24,6,13,19 二路并归：第一趟：19,24,32,43,6,38,13,22 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
31、 - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - 第二趟： 19,24,32,43,6,13,22,38 第三趟： 6,13,19,22,24,32,38,43 堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差。作业题五参考答案：一、单项选择题1. 答： C 2、D 3、D 4. 答： C 5. 答： B 6. 答： A 7. 答： D 8. 答： B 9. 答： C 10. 答： A 二、填空题1、1，n-1 2、60 3、2 4、快速排序5、简单选择排序6数据，指针，数据，指针三 判断1. 答：2. 答： 3. 答：
32、 4. 答：5. 答：四、应用题1. 答：该十字链表有一个十字链表表头结点，max(m,n)个行列表头结点。另外，每个非零元素对应一个结点，即 k个元素结点，所以共有max(m,n)+k+1 个结点。2. 答： （1）最小生成树的定义略。（2）最小生成树有两棵。 （限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W ）形式），其中 W代表权值。 V（G）=1 ，2，3，4，5 E1(G)=(4 ，5，2)， （2，5，4） ， （ 2，3，5） ， （1，2，7）；E2(G)=(4 ，5，2） ， （ 2，4，4） ， （2， 3，5） ， （1，2，7）3. 答：采用顺
33、序查找法：文件中记录可以以任意持续存放。采用折半查找法：文件中的记录必须按照关键字从小到大有序存放。采用分块查找法：将文件分成若干个块，每一个快中的记录可以任意的存放，但块之间的必须按照关键字名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 20 页 - - - - - - - - - 从小到大的次序存放，即前一块中的所有记录的关键字的值必须小于后一块的所有记录的关键字的字值。4. 答：排序过程如下：(1)88,33,22,55,99,11,66 (2)11,33,22,55,99,88,66 (3)11,22,33,55,99,88,66 (4)11,22,33,55,99,88,66 (5)11,22,33,55,99,88,66 (6)11,22,33,55,66,99,88 (7)11,22,33,55,66,88,99 (8)11,22,33,55,66,88,99名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -