数据结构专升本模拟题及参考答案.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构专升本模拟题及参考答案.doc》由会员分享,可在线阅读,更多相关《数据结构专升本模拟题及参考答案.doc(81页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构专升本模拟题及参考答案东北农业大学网络教育学院作业题(一)一、单项选择题 1. 从逻辑上可以把数据结构分为( )两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构2. 链表不具有的特点是( ) A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比3.下面程序段的时间
2、复杂度的量级为( )。For(i=1;i=n;i+) For(j=1;j=I;j+) For(k=1;k2,则该二叉树的高度为_。4. 采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分 个结点最佳。5、设G为具有N个顶点的无向连通图,则G中至少有条边。6、哈夫曼树(Huffman Tree)又称 。它是n个带权叶子结点构成的所有二叉树中,带权路径长度WPL 。7、树的先序遍历过程如下:若树为空,则进行空操作;若树非空,则访问树的 ;依次先序遍历树的 。三、应用题 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的图的邻接矩阵,(1)画出逻辑图 ;(2)画出图的十字链表存储;(3)基于邻接矩阵写出图的深度、广度优先遍历序列;(4)计算图的关键路径。 作业题(三)一、单项选择题 1串的长度是指( )A串中所含不同字母的个数 B串中所含非空格字符的个数C串中所含不
4、同字符的个数 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+2253算法分析的两个主要方面是( )。A空间复杂性和时间复杂性 B正确性和简明性C可读性和文档性 D数据复杂性和程序复杂性4算法分析的目的是( )。 A找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进 D分析算法的易懂性和文档性5. 下面程序段的时间复杂性的量极为( )。Int fun(
5、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的元素时需要比较元素和移动元素的总次数为( )。A(n+1)/2 Bn/2Cn Dn+19. 一个顺序存储线性表的第一个元素的存储地址是90,每个元素的长度是
6、2,则第6个元素的存储地址是( )。A98 B100C102 D10610. 如果某链表中最常用的操作是取第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)是
7、n(n1)个 的有序组合,数组中的数据是按顺序存储在一块 的存储单元中。6. 采用顺序存储结构表示三元组表(Triple Table),来实现对稀疏矩阵的一种压缩存储形式,就称为 ,简称 表。7. 运算是矩阵运算中最基本的一项,它是将一个m x n的矩阵变成另外一个n x m的矩阵,同时使原来矩阵中元素的行和列的位置互换而值保持不变。三、应用题 1、对于下图所示的二叉树,画出二叉链表存储结构图。 2、请画出下图所示的树所对应的二叉树。 ABCDE3. 已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小树(假设以为起点,试画出构造过程)。4. 已知完全二叉树的第8层有8个结
8、点,则其叶子结点是多少?5. 画出如图所示中树的二叉树的表示形式。 作业题(四)一、单项选择题 1. 将两个各有n个元素的有序表归并成一个有序表,其最少得比较次数是( )。An B2n-1C2n Dn-12. 一个有n个顶点的无向连通图,它所包含的连通分量个数为()。A0B1CnDn+13. 数据文件的基本操作中最重要的操作是( )。A插入B删除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,
9、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-1-1 C 2I-1 D2I -18循环队列存储在数组A中,长度为m,则入队时的操作为( )。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1)
10、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的结点数为( )个。A3 B4C5 D6二、填空题 1. 在一个循环队列中,队首指针指向队首元素的_。 2. 数组中每一个数据通常称为 , 用下标区分,其中下标的个数由数组的 决定。 3. 一个图的表示法是唯一的,而表示法是不唯一的。 4. 在一个10阶的B-树上,每个数根结点中所含的关键字数目最多允许 个,最少允许 个 5
11、. 对关键字序列(52,80,63,44,48,91)进行一趟快速排序之后的得到结果为 。10.高度为1的平衡二叉树的结点数至少有_个,高度为2的平衡二叉树的结点数至少有_个。三 判断 1. 顺序存储结构属于静态结构,链式结构属于动态结构。 ( ) 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所得的输出序列也一定相同。 ( ) 3. 带权无向图的最小生成树必是唯一的。( ) 4. B-树和B+树都可用于文件的索引结构。( ) 5. 在用堆排序算法排序时,如果要进行增序排序,则需要采用大根堆。( )四、应用题 1. 模式串p=abaabcac的next函数值序
12、列为多少? 2. 设二维数组A56的每个元素占4个字节,已知LOC(a0,0)=1000,A共占多少个字节?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、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)D(40,38,46,84,56,79)2广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为( )。GetHead(GetT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 模拟 参考答案
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内