数据结构典型习题.doc

《数据结构典型习题.doc》由会员分享，可在线阅读，更多相关《数据结构典型习题.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构典型习题.精品文档.第一章至第五章算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态 C. A和B从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构下列程序段的时间复杂度为( )。 for(i=0；i5；i+) for(j=0；jn；j+) x=x+1；A.O(5) B.O(5+n) C.O(n5 ) D.O(n)当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。顺序存储结构是通过

2、_表示元素之间的关系的;链式存储结构是通过_表示元素之间的关系的。对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 设栈的输入序列是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

3、时，对象栈和算符栈为（ ），其中为乘幂 。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

4、.便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度设广义表L=（a,b,c），则L的长度和深度分别为（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ ）。Head(Tail(Head(Tail(TailA)A. (g) B. D C. c D. d编程实现线性链表的基本操作如GetElem（）,ListInsert(),ListDelete(),CreateList()，MergeList（）等。第六章 树和二叉树一、选择题1树最适合用来表示（ ）。A. 有序数据元素 B. 无序数据元

5、素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据2深度为5的二叉树至多有（ ）个结点。A 16 B 32 C 31 D 103有32个结点的完全二叉树的深度为（ ）（根的层次为1）。 A8 B7 C6 D54若二叉树中度为2的结点有15个，度为1的结点有10个，则有（ ）个叶结点。 A25 B15 C16 D416有64个结点的完全二叉树的深度为（ ）（根的层次为1）。 A8 B7 C6 D57对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A 3 B 1 C 2 D 不存在8某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）二叉树。

6、A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子9前序遍历与中序遍历结果相同的二叉树为（）；前序遍历和后序遍历结果相同的二叉树为（ ）。 A一般二叉树 B只有根结点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子树的二叉树 F所有结点只有右子树的二叉树14设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所含的结点数至少为（ ）。A 2h B 2h-1 C 2h+1 D h+116设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。A2n+2 B 2n+1 C 2n D 2n-117设哈夫曼树的

7、叶子结点数为n，则它的结点总数为（ ）。A 2n-1 B 2n C 2n+1 D 不确定18由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为（ ）。A 50 B 60 C. 52 D. 6519二叉树的先序遍历序列和中序遍历序列分别为：EFHIGJK和HFIFJKG,该二叉树根的右子树的根是（ ）。A E B F C. G D. H21二叉树上叶结点数等于（ ）。A 分支结点数加 B 单分支结点数加C. 双分支结点数加 D. 双分支结点数减二、填空题1. 具有n个结点的完全二叉树的深度为 。2. 二叉树第i层上最多有 个结点。3. 深度为k的二叉树最多有 个结点7分别画出和

8、下列树对应的二叉树。A B8画出和下列二叉树相应的森林。A B9以数据集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. 对给出的

9、数据序列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) 为每个

10、字母设计huffman编码, (2) 给出八个字母二进制表示的等长编码并比较两方案的优缺点。18.编程实现二叉树的三种遍历方法，并统计特殊元素，如最大值，最小值,和值，终端节点。第七章 图1在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( )A.n-1B.nC.n+1D.n*227. 有n个顶点e条边的无向图G,它的邻接表中的表结点总数是( ) A 2n Bn C 2e D e3有4个顶点的无向完全图的边数为( )A.6B.12C.16D.204具有n个叶结点的赫夫曼树共有 个结点5N个顶点的连通图的生成树有 条边。6图的深度、广度优先遍历算法分别类似于二叉树的（ ）。A. 先序

11、遍历和中序遍历 B. 先序遍历和层序遍历C. 后序遍历和中序遍历D. 层序遍历和先序遍历7 若某无向图G的邻接表如图所示，试给出以顶点V1为出发点，按深度、广度优先搜索所产生的一棵生成树。8下图为一无向连通网络，分别根据普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法从顶点出发构造出它的最小生成树。（要求写出求解步骤）。9. 对如下带权图，请： (1) 给出结点的一个拓扑序列；（2）找出一条从v1 到v7的最短路径（要求写出求解步骤）。10对下图所示的AOE网络，给出其关键路径，（要求写出相关时间表格）。第九章 查找一、选择题1顺序查找法适合于存储结构为（ ）的线性表。 A散列存储 B

12、.顺序存储或链式存储 C.压缩存储 D.索引存储2二分查找法要求查找表中各元素的关键字必须是（ ）排列。 A递增或递减 B.递增 C. 递减 D.无序6有一个有序表为3，9，12，32，41，45，62，75，77，82，99 ，用二分查找法查找82成功时的查找次数是( )。 A 1 B 2 C 3 D 47. 平衡二叉树上结点的平衡因子是指 。12. 在散列函数H(k)=k MOD m 中，一般来讲，m应取（ ）。A 奇数 B 偶数 C 素数 D 充分大的数11若待散列的序列为（18，25，63，50，42，32，9），散列函数为H(key)=key mod 9，与18发生冲突的元素有 个。

13、三、基础知识题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 选择排

14、序3希尔排序属于（ ）.A 插入排序 B 交换排序 C 归并排序 D 选择排序4冒泡排序属于（ ）.A 插入排序 B 交换排序 C 归并排序 D 选择排序14下列序列中，（ ）才可能是执行第一趟快速排序后得到的序列。A 8,6,181916,10,50 B 6,4,81881,19,36,18C 81,1,23699,81,69 D 2,3,48978,98,68 15对于关键字序列72,73,71,23,94,16,5,68,76,103，用筛选法建堆，必须从关键字为（ ）的结点开始。A 103 B 72 C 94 D 23 16以下序列中，（ ）不是堆。A 15,26,38,49,27,5

15、1,39,62 B 15,23,26,72,94,71,68,73C 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)。（小根堆?）