《数据结构专升本模拟题及参考答案（2020年整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构专升本模拟题及参考答案（2020年整理）.pdf（20页珍藏版）》请在金锄头文库上搜索。
1、 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、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的 ；依次先序遍历树 的 。 三、应用题三、应用题 1、给定权值集合1, 4, 2, 6, 9, 构造相应的哈夫曼树, 并计算它的带权路径长度。 5 2、对关键字序列10，6，3，2，5，4，构造一棵平衡二叉（排序）树并画图（要求画出建树过程） 。 3、设有一个有序文件，其中各记录的关键字为（1，2，3，4
3、，5，6，7，8，9，10，11，12，13，14，15） ， 当用折半查找算法查找关键字为 3，8，19 时，其比较次数分别为多少？ 4、对有五个结点 A,B, C, D, E的图的邻接矩阵， 050 010 20060 0 10301000 （1） 画出逻辑图 ； （2） 画出图的十字链表存储； （3） 基于邻接矩阵写出图的深度、广度优先遍历序列； （4） 计算图的关键路径。 作业题作业题（三（三） 一、单项选择题一、单项选择题 1串的长度是指（ ） A串中所含不同字母的个数 B串中所含非空格字符的个数 C串中所含不同字符的个数 D串中所含字符的个数 2设有数组 Ai,j，数组的每个元素长
4、度为 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算法分析的目的是（ ） 。 6 A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性 5. 下面程序段的时间复杂性的量极为（ ） 。 Int fun(int n) int
5、 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 BL-next= =NULL CL-next= =L DL! =NULL 8. 在一个长度为 n 的线性表中，删除值为 x 的元素时需要比较元素和移动元素的总次数为（ ） 。 A （n+1）/2 Bn/2 Cn Dn+1 9. 一个顺序存储线性表的第一个元素的存
6、储地址是 90，每个元素的长度是 2，则第 6 个元素的存储地址 是（ ） 。 A98 B100 C102 D106 10. 如果某链表中最常用的操作是取第 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
7、） ， （d，e，f） ） ，则广义表运算 head（tail（tail（A） ） ）= 。 5、数组（Array）是 n（n1）个 的有序组合，数组中的数据是按顺序存储在一块 的 存储单元中。 6. 采用顺序存储结构表示三元组表（Triple Table） ，来实现对稀疏矩阵的一种压缩存储形式，就称 为 ，简称 表。 7. 运算是矩阵运算中最基本的一项，它是将一个 m x n 的矩阵变成另外一个 n x m 的矩阵，同时 7 使原来矩阵中元素的行和列的位置互换而值保持不变。 三、应用题三、应用题 1、对于下图所示的二叉树，画出二叉链表存储结构图。 2、请画出下图所示的树所对应的二叉树。 3.
8、 已知一个无向图如下图所示，要求分别用 Prim 和 Kruskal 算法生成最小树（假设以为起点，试画出 构造过程） 。 4. 已知完全二叉树的第 8 层有 8 个结点，则其叶子结点是多少？ 5. 画出如图所示中树的二叉树的表示形式。 A B C D E 8 作业题作业题（四（四） 一、单项一、单项选择题选择题 1. 将两个各有 n 个元素的有序表归并成一个有序表，其最少得比较次数是（ ） 。 An B2n-1 C2n Dn-1 2. 一个有 n 个顶点的无向连通图，它所包含的连通分量个数为（ ） 。 A0 B1 Cn Dn+1 3. 数据文件的基本操作中最重要的操作是（ ） 。 A插入 B
9、删除 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分析算法的效率以求改进
10、 D分析算法的易懂性和文档性 7. 二叉树的第 I 层上最多含有结点数为（ ） A2 I B 2I-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个，度为
11、2的结点数为1个，度为1的结点数为2个，则度为0的 结点数为（ ）个。 A3 B4 C5 D6 二、填空题二、填空题 1. 在一个循环队列中，队首指针指向队首元素的_。 2. 数组中每一个数据通常称为 ， 用下标区分，其中下标的个数由数组的 决定。 3. 一个图的 表示法是唯一的，而 表示法是不唯一的。 4. 在一个 10 阶的 B-树上，每个数根结点中所含的关键字数目最多允许 9 个，最少允许 个 5. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后的得到结果为 。 10.高度为 1 的平衡二叉树的结点数至少有_个，高度为 2 的平衡二叉树的结点数至少有_ 个。 三三
12、 判断判断 1. 顺序存储结构属于静态结构，链式结构属于动态结构。 （ ） 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列 也一定相同。 （ ） 3. 带权无向图的最小生成树必是唯一的。 （ ） 4. B-树和 B+树都可用于文件的索引结构。 （ ） 5. 在用堆排序算法排序时，如果要进行增序排序，则需要采用大根堆。 （ ） 四、应用题四、应用题 1. 模式串 p=abaabcac的 next 函数值序列为多少？ 2. 设二维数组 A56的每个元素占 4 个字节，已知 LOC（a0,0）=1000，A 共占多少个字节？A 的终端结 点 a4,5
13、的起始地址为多少？按行和按列优先存储时，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，请写出快速排序第一趟的结果；堆排序时 所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最 坏情况下那种方法的时间复杂度最差？ 10 作业题作业题（五（五） 一、单项选择题一、单项选择题 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(GetTa
