数据结构导论试题和部分答案

数据结构导论试题和部分答案

ID:33849342

大小:972.00 KB

页数:14页

时间:2019-03-01

数据结构导论试题和部分答案_第1页
数据结构导论试题和部分答案_第2页
数据结构导论试题和部分答案_第3页
数据结构导论试题和部分答案_第4页
数据结构导论试题和部分答案_第5页
资源描述:

《数据结构导论试题和部分答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、全国2012年1月数据结构导论试题课程代码:02142一、单项选择题(本大题共15小题,每小题2分,共30分)1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是()A.集合B.线性结构C.树形结构D.图状结构2.下面算法程序段的时间复杂度为()for(inti=0;i

2、删除由某个指针变量指向的结点的直接后继,该算法的时间复杂度是()A.O(1)B.O()C.O(log2n)D.O(n)5.关于串的叙述,正确的是()A.串是含有一个或多个字符的有穷序列B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有零个或多个字符的有穷序列6.栈的输入序列依次为1,2,3,4,则不可能的出栈序列是()A.1243B.1432C.2134D.43127.队列是()A.先进先出的线性表B.先进后出的线性表C.后进先出的线性表D.随意进出的线性表8.10阶上三角矩阵压缩存储时需存储的元素个数为()A.11B.56C.100D.1019.

3、深度为k(k≥1)的二叉树,结点数最多有()A.2k个B.(2k-1)个C.2k-1个D.(2k+1)个10.具有12个结点的二叉树的二叉链表存储结构中,空链域NULL的个数为()A.11B.13C.23D.2511.具有n个顶点的无向图的边数最多为()A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)12.三个顶点v1,v2,v3的图的邻接矩阵为,该图中顶点v3的入度为()A.0B.1C.2D.313.顺序存储的表格中有60000个元素,已按关键字值升序排列,假定对每个元素进行查找的概率是相同的,且每个元素的关键字值不相同。用顺序查找法查找时,平均比较次数约为(

4、)A.20000B.30000C.40000D.6000014.外存储器的主要特点是()A.容量小和存取速度低B.容量大和存取速度低C.容量大和存取速度高D.容量小和存取速度高15.在待排数据基本有序的前提下,效率最高的排序算法是()A.直接插入排序B.直接选择排序C.快速排序D.归并排序二、填空题(本大题共13小题,每小题2分,共26分)16.数据的不可分割的最小标识单位是______,它通常不具有完整确定的实际意义,或不被当作一个整体对待。17.运算分为加工型运算和引用型运算,读取操作是______运算。1418.带有头结点的单向循环链表L(L为头指针)中,指针p所指结点为

5、尾结点的条件是______。19.在双链表中,前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点,则需执行语句______。20.元素s1,s2,s3,s4,s5,s6依次进入顺序栈S,如果6个元素的退栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少为______。21.稀疏矩阵一般采用的压缩存储方法是______。22.在一棵树中,______结点没有双亲。23.一棵具有n个结点的完全二叉树中,从树根起,自上而下、自左至右给所有结点编号。设根结点编号为1,若编号为i的结点有父结点,那么其父结点的编号为______。24.二叉树的二叉链表存储

6、结构中判断指针p所指结点为叶子结点的条件是______。25.边稀疏的无向图采用______存储较省空间。26.除第一个顶点和最后一个顶点相同外,其余顶点不重复的回路,称为______。27.二分查找算法的时间复杂度是______。28.要将序列{51,18,23,68,94,70,73}建成堆,则只需把18与______相互交换。三、应用题(本大题共5小题,每小题6分,共30分)29.将题29图所示的一棵二叉树转换成对应的森林。题29图题31图题32图30.给定权值{3,9,13,5,7},构造相应的哈夫曼(Huffman)树,并计算其带权路径长度。31.写出题31图的邻接矩

7、阵和每个顶点的入度与出度。32.二叉排序树的各结点的值依次为20~28,请在题32图中标出各结点的值。33.用冒泡排序法对数据序列(55,38,65,97,76,138,27,49)进行排序,写出排序过程中的各趟结果。四、算法设计题(本大题共2小题,每小题7分,共14分)34.设线性表A=(a1,a2,…,am),B=(b1,b2,…,bn),试写一个按下列规则合并A,B为线性表C的算法,使得C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时;或者C=(a1,b1,…,an,b

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。