数据结构典型习题.docx
- 文档编号:16830191
- 上传时间:2023-07-17
- 格式:DOCX
- 页数:11
- 大小:88.02KB
数据结构典型习题.docx
《数据结构典型习题.docx》由会员分享,可在线阅读,更多相关《数据结构典型习题.docx(11页珍藏版)》请在冰点文库上搜索。
数据结构典型习题
第一章至第五章
算法的时间复杂度取决于()
A.问题的规模B.待处理数据的初态C.A和B
从逻辑上可以把数据结构分为()两大类。
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
下列程序段的时间复杂度为()。
{for(i=0;i<5;i++)
for(j=0;j x=x+1; } A.O(5)B.O(5+n)C.O(n5)D.O(n) 当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用_______存储结构。 顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。 对于栈操作数据的原则是()。 A.先进先出B.后进先出C.后进后出D.不分顺序 有六个元素6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列? () A.543612B.453126C.346521D.234156 设栈的输入序列是1,2,3,4,则()不可能是其出栈序列。 A.1,2,4,3,B.2,1,3,4,C.1,4,3,2, D.4,3,1,2,E.3,2,1,4, 表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和算符栈为(),其中^为乘幂。 A.3,2,4,1,1;(*^(+*-B.3,2,8;(*^- C.3,2,4,2,2;(*^(-D.3,2,8;*^(- 下面关于串的的叙述中,哪一个是不正确的? () A.串是字符的有限序列 B.空串是由空格构成的串 A.模式匹配是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储 设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为() A.求子串B.联接C.匹配D.求串长 串的长度是指() A.串中所含不同字母的个数B.串中所含字符的个数 C.串中所含不同字符的个数D.串中所含非空格字符的个数 对稀疏矩阵进行压缩存储目的是()。 A.便于进行矩阵运算B.便于输入和输出 C.节省存储空间D.降低运算的时间复杂度 设广义表L=((a,b,c)),则L的长度和深度分别为()。 A.1和1B.1和3C.1和2D.2和3 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为()。 Head(Tail(Head(Tail(TailA)))) A.(g)B.DC.cD.d 编程实现线性链表的基本操作如 GetElem(),ListInsert(), ListDelete(),CreateList(),MergeList()等。 第六章树和二叉树 一、选择题 1.树最适合用来表示()。 A.有序数据元素B.无序数据元素 C.元素之间具有分支层次关系的数据D.元素之间无联系的数据 2.深度为5的二叉树至多有()个结点。 A.16B.32C.31D.10 3.有32个结点的完全二叉树的深度为()(根的层次为1)。 A.8B.7C.6D.5 4.若二叉树中度为2的结点有15个,度为1的结点有10个,则有()个叶结点。 A.25B.15C.16D.41 6.有64个结点的完全二叉树的深度为()(根的层次为1)。 A.8B.7C.6D.5 7.对含有()个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相同。 A.3 B.1C.2D.不存在 8.某二叉树的先序序列和后序序列正好相反,则该二叉树一定是()二叉树。 A.空或只有一个结点B.高度等于其结点数 C.任一结点无左孩子D.任一结点无右孩子 9.前序遍历与中序遍历结果相同的二叉树为( );前序遍历和后序遍历结果相同的二叉树为( )。 A.一般二叉树B.只有根结点的二叉树 C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树 E.所有结点只有左子树的二叉树F.所有结点只有右子树的二叉树 14.设高度为h的二叉树上只有度为0和度为2的结点,则此二叉树中所含的结点数至少为()。 A.2hB.2h-1 C.2h+1D.h+1 16.设一棵二叉树中没有度为1的结点,已知叶子结点数为n,此树的结点数为()。 A.2n+2B.2n+1 C.2nD.2n-1 17.设哈夫曼树的叶子结点数为n,则它的结点总数为()。 A.2n-1B.2n C.2n+1D.不确定 18.由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为()。 A.50B.60 C.52D.65 19.二叉树的先序遍历序列和中序遍历序列分别为: EFHIGJK和HFIFJKG,该二叉树根的右子树的根是()。 A.EB.F C.GD.H 21.二叉树上叶结点数等于()。 A.分支结点数加1 B.单分支结点数加1 C.双分支结点数加1 D.双分支结点数减1 二、填空题 1.具有n个结点的完全二叉树的深度为。 2.二叉树第i层上最多有个结点。 3.深度为k的二叉树最多有个结点 7.分别画出和下列树对应的二叉树。 AB 8.画出和下列二叉树相应的森林。 AB 9.以数据集{4,5,6,7,10,12,18}为结点权值构造的Huffman树,并求其带权路径长度。 10.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK,请画出该树并给出其后序序列。 12.已知某二叉树按后序遍历序列为CEDBHJIGFA,按中序遍历序列为CBEDAHGIJF,试画出该二叉树形状(要求写出中间过程),并写出它的先序遍历序列。 13.设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设计huffman编码并画出对应huffman树。 14.对给出的数据序列4,5,6,7,10,12,15,18,23,构造一棵huffman树,并求其带权路径长度。 15.设a,b,c,d,e,f,g,h,i九个字母出现的次数分别为4,5,6,7,10,12,15,18,23,构造一棵huffman树,并给出每个字符的huffman编码。 16.设一棵二叉树的先序、中序遍历序列分别为EBADCFHGIKJ和ABCDEFGHIJK,要求: (1)画出该二叉树(要求写出中间步骤); (2)将这棵二叉树转换成对应的树(或森林)。 17.设一份电文中a,b,c,d,e,f,g,h八个字母出现的次数分别为7,19,2,6,32,3,21,10,要求: (1)为每个字母设计huffman编码, (2)给出八个字母二进制表示的等长编码并比较两方案的优缺点。 18.编程实现二叉树的三种遍历方法,并统计特殊元素,如最大值,最小值,和值,终端节点。 第七章图 1.在一个具有n个顶点的无向图中,要连通全部顶点至少需要的边数为() A.n-1 B.n C.n+1 D.n*2 2.7.有n个顶点e条边的无向图G,它的邻接表中的表结点总数是() A.2nB.nC.2eD.e 3.有4个顶点的无向完全图的边数为() A.6 B.12 C.16 D.20 4.具有n个叶结点的赫夫曼树共有个结点 5.N个顶点的连通图的生成树有条边。 6.图的深度、广度优先遍历算法分别类似于二叉树的()。 A.先序遍历和中序遍历B.先序遍历和层序遍历 C.后序遍历和中序遍历D.层序遍历和先序遍历 7. 若某无向图G的邻接表如图所示,试给出以顶点V1为出发点,按深度、广度优先搜索所产 生的一棵生成树。 8.下图为一无向连通网络,分别根据普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法从顶点1出发构造出它的最小生成树。 (要求写出求解步骤)。 9.对如下带权图,请: (1)给出结点的一个拓扑序列; (2)找出一条从v1到v7的最短路径(要求写出求解步骤)。 10.对下图所示的AOE网络,给出其关键路径,(要求写出相关时间表格)。 第九章查找 一、选择题 1.顺序查找法适合于存储结构为()的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储D.索引存储 2.二分查找法要求查找表中各元素的关键字必须是()排列。 A.递增或递减B.递增C.递减D.无序 6.有一个有序表为{3,9,12,32,41,45,62,75,77,82,99},用二分查找法查找82成功时的查找次数是()。 A.1B.2C.3D.4 7.平衡二叉树上结点的平衡因子是指。 12.在散列函数H(k)=kMODm中,一般来讲,m应取()。 A.奇数B.偶数C.素数D.充分大的数 11.若待散列的序列为(18,25,63,50,42,32,9),散列函数为H(key)=keymod9,与18发生冲突的元素有个。 三、基础知识题 1.简述顺序查找法和二分查找法的区别。 2.取适当Hash函数及处理冲突的方法,试在0--12散列地址空间中对关键字序列(2,41,53,46,30,13,01,67)构造Hash表,并求出等概率下查找成功的平均查找长度。 4.已知一组元素为(37,70,29,46,25,78,62,12),画出按元素排列输入生成的一棵二叉排序树,并求其在等概率情况下查找成功的平均查找长度(要求写出每插入一个元素时二叉排序树形状)。 第十章内部排序 一、选择题 1.堆排序属于()。 A.插入排序B交换排序C归并排序D.选择排序 2.快速排序属于()。 A.插入排序B交换排序C归并排序D.选择排序 3.希尔排序属于(). A.插入排序B交换排序C归并排序D.选择排序 4.冒泡排序属于(). A.插入排序B交换排序C归并排序D.选择排序 14.下列序列中,()才可能是执行第一趟快速排序后得到的序列。 A.{8,6,18}19{16,10,50}B{6,4,8}18{81,19,36,18} C{81,1,2}36{99,81,69}D.{2,3,4}89{78,98,68} 15.对于关键字序列{72,73,71,23,94,16,5,68,76,103},用筛选法建堆,必须从关键字为()的结点开始。 A.103B72C94D.23 16.以下序列中,()不是堆。 A.{15,26,38,49,27,51,39,62}B{15,23,26,72,94,71,68,73} C{15,23,71,94,72,68,26,73}D.{15,23,26,68,94,72,71,73} 二、填空题 2.最简单的交换排序方法是。 5.归并排序的时间复杂度为。 6.快速排序是一种类型的排序;对含有n个元素的序列进行排序时,快速排序的时间复杂度是。 7.对具有n个记录的序列进行快速排序,在最坏情况下的时间复杂度是;在最好情况下的时间复杂度是。 三、基础知识题 1.以关键字序列(25,84,21,47,15,27,68,35,20)为例,手工执行各种排序算(从小到大),写出每一趟排序结束时的关键字状态。 (冒泡排序,快速排序,堆排序) 3.试按堆的构造方法,写出对应于序列(26,5,77,1,61,11,59,15,48,19)的初始堆(大根堆、小根堆均可,要求给出调整过程)。 4.判别以下序列是否为堆(小根堆或大根堆)。 如果不是,则把它调整为堆(要求记录交换次数最少)。 (1)(100,86,48,73,35,39,42,58,66,22);(大根堆? ) (2)(12,70,33,65,24,56,46,90,86,34)。 (小根堆? )
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 典型 习题
![提示](https://static.bingdoc.com/images/bang_tan.gif)