《（2020年7月整理）数据结构专升本模拟题及参考答案.doc》由会员分享，可在线阅读，更多相关《（2020年7月整理）数据结构专升本模拟题及参考答案.doc（18页珍藏版）》请在金锄头文库上搜索。
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个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。5、设
2、G为具有N个顶点的无向连通图，则G中至少有条边。6、哈夫曼树（Huffman Tree）又称 。它是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
3、，8，19时，其比较次数分别为多少？4、对有五个结点 A,B, C, D, E的图的邻接矩阵，（1）画出逻辑图 ；（2）画出图的十字链表存储；（3）基于邻接矩阵写出图的深度、广度优先遍历序列；（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+222
4、D. BA+2253算法分析的两个主要方面是（ ）。A空间复杂性和时间复杂性 B正确性和简明性C可读性和文档性 D数据复杂性和程序复杂性4算法分析的目的是（ ）。 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 BL-next= =NULLCL-next= =L DL! =NULL8. 在一个长度为n的线性表中，删除值为x的元素时
