《数据结构与算法分析六套期末复习题含答案1数据结构与算法》由会员分享，可在线阅读，更多相关《数据结构与算法分析六套期末复习题含答案1数据结构与算法（24页珍藏版）》请在金锄头文库上搜索。
1、rom-lchild-data;EnQueue(Qfro分线性表为：(90,40,78,50,34,60)三、本符串，至多可以组成个不同的字符串？A15B14C1设有12个数据25,40,33,47,12,66,72,87试题一一、单项选择题每小题 2 分，共 20 分1 以下数据结构中哪一个是线性结构？ A有向图 B 队列 C线索二叉树 DB 树2在一个单链表 HL 中， 若要在当前由指针 p 指向的结点后面插入一个由q 指向的结点， 则 执行如下 语句序列。Ap=q; p-next=q; B p-next=q; q-next=p;Cp-next=q-next; p=q; Dq-next=p
2、-next; p-next=q;3 不是队列的基本运算。A在队列第 i 个元素之后插入一个元素 B 从队头删除一个元素C判断一个队列是否为空 D 读取队头元素的值4字符 A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 个不同的字符串。A14 B5 C6 D85 由权值分别为 3,8,6,2 的叶子生成一棵哈夫曼树，它的带权路径长度为 。A11B35 C19 D53以下 6-8题基于下图：6 该二叉树结点的前序遍历的序列为 。A E 、G 、F 、A 、C 、D 、B B E 、A 、G 、C 、F 、B 、DC E 、A 、C 、B 、D 、G 、F D E 、G 、
3、A 、C 、D 、F 、B7 该二叉树结点的中序遍历的序列为 。A A 、B 、C 、D 、E 、G 、F B E 、A 、G 、C 、F 、B 、D3)4对n个记录的文件进行快速排序，所需要的辅助存储空间增量d=2按降序执行一遍希尔排序的结果：28,80,27,2少次？三、本题8分假设把n个元素的序列a1,a2,a18,25,29,47,51,58)九、本题9分具有3个C E 、A 、C 、B 、D 、G 、F D B 、D 、C 、A 、F 、G 、E8 该二叉树的按层遍历的序列为 。A E 、G 、F 、A 、C 、D 、B B E 、A 、C 、B 、D 、G 、FC E 、A 、G
4、、C 、F 、B 、D D E 、G 、A 、C 、D 、F 、B9 下面关于图的存储的叙述中正确的是 。A用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10设有关键码序列(q,g,m,z,a,n,p,x,h) ，下面哪一个序列是从上述序列出发建堆的结果? Aa,g,h,m,n,p,q,x,z Ba,g,m,h,q,n,p,x,zCg,m,q,a,n,p,x,h,z
5、D h,g,m,p,a,n,q,x,z二、本题 8 分对于序列8,18,6,16,29,28 ，试写出堆顶元素最小的初始堆。三、本题 8 分一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处 的内容，并画出该二叉树。先序序列： BF ICEHG中序序列： DKFIAEJC后序序列： KFBHJG A四、每小题 2 分，共 8 分设有序列： w=23,24,27,80,28 ，试给出：1 二叉排序树；2 哈夫曼树；3 平衡二叉树；4 对于增量 d=2 按降序执行一遍希尔排序的结果。.表头插入一个由指针p指向的结点，则执行。Ap-nexE、G、F、A、C、D、BBE、A
6、、G、C、F、B、DC29(58,51,47)(10(18,25,12)29(4235每一趟都能选出一个元素放在其最终位置上，并且不稳定五、本题 15 分假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按 如下图所示的树状显示二叉树。答案=一、单项选择题1B 2D 3A 4B5B6C7A8C9B10B二、 本题 8 分所构造的堆如下图所示：三、 本题 8 分在先序序列空格中依次填 ADKJ，中序中依次填 BHG，后序中依次填 DIEC。四、 每小题 2 分，共 8 分 1 二叉排序树如下图所示：2 哈夫曼树如下图所示：.rom-lchild-data;EnQueue
7、(Qfro少次？三、本题8分假设把n个元素的序列a1,a2,a)(47,51,58)第四次调整：(25,18,12,10)ount(BiTreeT)/计算二叉树中叶子结点数目.试题3 平衡二叉树如下图所示：4 对于增量 d=2 按降序执行一遍希尔排序的结果： 28,80,27,24,23五、 本题 15 分从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每 行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。C语言版测试程序见 exam110c ，具体算当如下：void DisplayBT
8、WithTreeShape(BiTree T,int level=1)/ 按树状形式显示二叉树， level 为层次数，可设根结点的层次数为 1if(T) / 空树不显式，只显式非空树DisplayBTWithTreeShape(T-rchild,level+1); / 显示右子树coutendl; / 显示新行for(int i=0;ilevel-1;i+)cout ; / 确保在第 level 列显示结点coutdata; / 显示结点DisplayBTWithTreeShape(T-lchild,level+1); / 显示左子树=.=一=一、单项选择题1B2D3A4基本运算。A在队列第
9、i个元素之后插入一个元素B从队头删除为。AO1BOlog2nCOnDO试题二一、单项选择题每小题 2 分，共 20 分1 设 Huffman 树的叶子结点数为 m ，则结点总数为 。A2m B2m-1C2m+1 Dm+12 若顺序存储的循环队列的 QueueMaxSize=n ，则该队列最多可存储 个元素。An Bn-1C n+1D 不确定3 下述哪一条是顺序存储方式的优点？ A存储密度大 B 插入和删除运算方便C获取符合某种条件的元素方便 D 查找运算速度快4设有一个二维数组Amn ，假设A00 存放位置在600(10) ，A33 存放位置在678(10) ，每个元素占一个空间， 问 A23
10、(10) 存放在什么位置？ 脚注(10) 表示用 10 进制表示， m3 。A658 B648 C633D6535 下列关于二叉树遍历的叙述中，正确的是 。A若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B 若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D 若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6k 层二叉树的结点总数最多为 。A2k-1B2k+1 CK-1 Dk-17 对线性表进行二分法查找，其前
11、提条件是 。.lb-next;/pc永远指向lc的尾结点/pa指向lCDFGHIJ，中序遍历的结果是KBCDAFHIGJ，试画出为：(I,M),(I,N),(E,I),(B,E),(B,、G、A、C、D、F、B9下面关于图的存储的叙述中正确的A线性表以方式存储，并且按关键码值排好序B 线性表以顺序方式存储，并且按关键码值的检索频率排好序C线性表以顺序方式存储，并且按关键码值排好序D 线性表以方式存储，并且按关键码值的检索频率排好序8 对 n 个记录进行堆排序，所需要的辅助存储空间为 。AO(1og2n) BO(n) CO(1) DO(n2)9 对于线性表7，34，77，25，64，49，20，
12、14 进行散列存储时，若选用 HK=K%7作为散列函数，则散列地址为 0 的元素有 个。A 1 B 2 C 3 D 410 下列关于数据结构的叙述中，正确的是 。A数组是不同类型值的集合B 递归算法的程序结构比迭代算法的程序结构更为精炼C树是一种线性结构D 用一维数组存储一棵完全二叉树是有效的存储方法二、本题 8 分假定一棵二叉树广义表表示为 a(b(c),d(e,f) ，分别写出对它进行先序、中序、后序、按层遍历 的结果。三、本题 8 分树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？四、本题 8 分设有数组 A-1:3,0:6,-2:3，按行为主序存放在 2000 开始的连续空间中， 如元素的长度是 5，试 计算出 A1,1,1 的存储位置。五、本题 8 分设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生 成的二叉搜索树。.排序求初始归并段为：归并段1：29,33,38,50,60,叉树；4对于增量d=2按降序执
