资源描述
作业题(一)一、单项选择题1. 从逻辑上可以把数据结构分为()两大类。A. 动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构2. 链表不具有的特点是()A. 插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比3. 下面程序段的时间复杂度的量级为( )。For(i=1;i=n;i+)For(j=1;j=I;j+)For(k=1;k=j;k+)X=x+1;AO(1)BO(n)C. O(n2)D. O(n3)4在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改() 个指针域的值。A. 2B.3C.4D.65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6 个元素的存储地址 是( )。A. 98B.100C.102D.1066、判定一个栈s (最多元素为mO)为空的条件是()。A. s-top! =0B. s-top= =0C.s-top! =mOD.s-top= =mO7、循环队列用数组Am(下标从0到m-1)存放其元素值，已知其头尾指针分别是front和rear,贝ij当 前队列中的元素个数是( )。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D. rear-front&设有两个串S1与S2,求串S2在S1中首次出现位置的运算称作()。A.连接B.求子串C.模式匹配D.判子串9、设串 S1=ABCDEFG, S2=PQRST，函数 con (x, y)返回 x和 y 串的连接串，subs(s,i,j)返回串 S 的 的 从 序 号 i 的 字 符 开 始 的 j 个 字 符 组 成 的 子 串 , len(s) 返 回 串 S 的 长 度 , 则 con(subs(S1,2,len(S2),subs(S1,len(S2),2)的结果是()。ABCDEFBBCDEFGCBCPQRSTDBCDEFEF10、数组常用的两种基本操作是（ ）。A.建立与查找B.删除与查找C.插入与索引D.查找与修改二、填空题1. 所谓稀疏矩阵指的是_且分布没有规律。2. 队列是的线性表，其运算遵循的原则。3. 空格串是4. 简单选择排序和起泡排序中比较次数与序列初态无关的算法有。5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度 为，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为，图的深度或广度优先搜索遍 历时的空间复杂度均为。6、一个图的表示法是唯一的，而表示法是不唯一的。三、算法 设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。四、应用题1、对关键字无序序列（36，25，48，12，65，43，20，58）进行直接选择排序，请写出每一趟排序的结果。（10 分）2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10 分）3、已知记录关键字集合为（ 53,17,19,61,98,75,79,63,46,49 ）要求散列到地址区间 （100,101,102,103,104,105,106,107,108,109），若产生冲突用开型寻址法的线性探测法解决。要求写出 选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等 概率情况）4、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次 数为多少？作业题（二）、单项选择题1. 有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？A. 5 4 3 6 1 2 B. 4 5 3 1 2 62. 栈和队都是（）A.顺序存储的线性结构C. 限制存取点的线性结构3、顺序查找法适合于存储结构为（A.散列存储C. 3 4 6 5 2 1 D. 2 3 4 1 5 6B. 链式存储的非线性结构D. 限制存取点的非线性结构）的线形表。B. 顺序存储或存储C. 压缩存储D.索引存储4、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。A（100，80，90，60，120，110，130)B（100，120，110，130，80， 60， 90)C（100，60，80，90，120，110，130)D (10080，60，90，120，130，110)5、折半查找的平均比较次数为（）。AnBn/2Clog2nDlog2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）A.必定快B.不一定C. 在大部分情况下要快D.取决于表递增还是递减7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。A. v1, v2, v3, v5, v4B. v1, v2, v3, v4, v5C. v1, v3, v4, v5, v2D. v1 , v4, v3, v5, v2&为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（）。A.顺序存储B.链式存储C索引存储D散列存储9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s,则所有顶点的入度之和为（）。A. sB. s-1C. s+1D. n10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列 是（ ）。A. A E C D B F GB. A G B F D E CC. A C E D B G FD. A B D G F E C二、填空题1. 设n为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点。2. 有数据WG=7, 19, 2, 6, 32, 3, 21, 10,贝ij所建Huffmon树的树高 ，带权路径长度WPL 为。3设一棵完全二叉树叶子结点数为k,最后一层结点数2,则该二叉树的高度为。4、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定 结点所在的块时，每块应分个结点最佳。5、设G为具有N个顶点的无向连通图，则G中至少有条边。6、哈夫曼树（Huffman Tree）又称。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL。7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的；依次先序遍历树的。三、应用题1、给定权值集合1,4, 2, 6, 9,构造相应的哈夫曼树，并计算它的带权路径长度。2、对关键字序列10，6，3，2，5，4，构造一棵平衡二叉（排序）树并画图（要求画出建树过程）。3、设有一个有序文件，其中各记录的关键字为（1，2，3，4，5，6，7，8，9，10，11，12，13，1415），当用折半查找算法查找关键字为3，8，19 时，其比较次数分别为多少？4、对有五个结点 A,B, C, D, E的图的邻接矩阵，010030g10g0gggg60020gg10g0gggg5001）画出逻辑图；2）画出图的十字链表存储；3）基于邻接矩阵写出图的深度、广度优先遍历序列4）计算图的关键路径。作业题（三）一、单项选择题1串的长度是指（）B.串中所含非空格字符的个数D.串中所含字符的个数A.串中所含不同字母的个数C.串中所含不同字符的个数 2设有数组Ai,j,数组的每个元素长度为3字节，i的值为1到8 ,j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5, 8的存储首地址为（）。A. BA+141B. BA+1803算法分析的两个主要方面是（A.空间复杂性和时间复杂性C.可读性和文档性C. BA+222 D. BA+225）。B. 正确性和简明性D. 数据复杂性和程序复杂性4算法分析的目的是（ ）。B.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性)。A.找出数据结构的合理性C. 分析算法的效率以求改进5. 下面程序段的时间复杂性的量极为(Int fun(int n) int i=1,s=1;While(s1)个的有序组合，数组中的数据是按顺序存储在一块的存储单元中。6. 采用顺序存储结构表示三元组表(Triple Table)，来实现对稀疏矩阵的一种压缩存储形式，就称为，简 称表。7运算是矩阵运算中最基本的一项，它是将一个m xn的矩阵变成另外一个n x m的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。三、应用题1、对于下图所示的二叉树，画出二叉链表存储结构图。2、请画出下图所示的树所对应的二叉树。3. 已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以为起点，试画出 构造过程）。4. 已知完全二叉树的第8层有8个结点，则其叶子结点是多少?5. 画出如图所示中树的二叉树的表示形式。作业题（四）一、单项选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（）。A. nB 2n-1C2nDn-12.个有n个顶点的无向连通图，它所包含的连通分量个数为（）。A0B3.CnDn+1数据文件的基本操作中最重要的操作是（A插入）。B删除D检索C修改对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大次划分结果为（A. （2,5,12,16）26（60,32,72）B. （5,16212）28（60,32,72）C. （2,16,12,5）28（60,32,72）D. （5,16,2,12）28（32,60,72）5.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快B.快速排序D.归并排序4.AC6堆排序插入排序算法分析的目的是（ ）。）。ABC7.找出数据结构的合理性分析算法的效率以求改进二叉树的第I层上最多含有结点数为（）A. 2iB.2i-i-1C.2i-i D.D研究算法中的输入和输出的关系分析算法的易懂性和文档性2I -189.循环队列存储在数组A中，长度为m,则入队时的操作为（）。B. rear=（rear+1） mod （m-1）C. rear=（rear+1） mod m D. rear=（rear+1）mod（m+1） 广义表满足Head（A）=Tail（A）,则|A为（）。A. rear=rear+1C（），（）A.（）B.（）D（），（），（）10. 在棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0 的结点数为（）个。B4A3C.5D.6二、填空题1. 在个循环队列中，队首指针指向队首元素的。2. 数组中每一个数据通常称为,用下标区分，其中下标的个数由数组的决定。3- 一个图的表示法是唯一的，而表示法是不唯一的。4. 在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许个，最少允许个5. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后的得到结果为。10.高度为 1 的平衡二叉树的结点数至少有个，高度为 2 的平衡二叉树的结点数至少有个。三判断1. 顺序存储结构属于静态结构，链式结构属于动态结构。（）2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列 也一定相同。（）3. 带权无向图的最小生成树必是唯一的。（）4. B-树和B+树都可用于文件的索引结构。（）5. 在用堆排序算法排序时，如果要进行增序排序，则需要采用大根堆。（）四、应用题1. 模式串p=aboobcoc的next函数值序列为多少？2. 设二维数组A56的每个元素占4个字节，已知LOC （。0,0） =1000, A共占多少个字节？ A的终端 结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？3. 设 a,b,c,d,e 五个字符的 编码分别为 1,2,3,4,5, 并设标识符依以下次序 出现： oc,bd,oo,be,ob,od,cd,bc,oe,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。（1）将上述关键字（标识符）构造一个哈希函数,使得发生冲突尽可能地少；（2）线性探测再散列法解 决冲突。写出上述各关键字在表中位置。4. 给定一个关键字序列24,19,32,43,38,6,13,22,请写出快速排序第一趟的结果；堆排序时 所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最 坏情况下那种方法的时间复杂度最差？作业题(五)一、单项选择题1. 组记录的关键码为(46, 79, 56, 38,40, 84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。A. (38,40,46,56,79,84)C. (40,38,46,56,79,84)B. (40,38,46,79,56,84)D. (40,38,46,84,56,79)2. 广义表 A=(a,b,(c,d),(e,(f,g),贝U下 面式子 的值为 ()。GetHeod(GetToil(GetHeod(GetToil(GetToil(A)A. (g) B. (d)C. cD. d3对于有n个结点的二叉树，其高度为()A. nlogn B. lognC. logn +1 D.不确定4.如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是( )。B. 1 3 4 7 6 2 5D. 1 2 4 7 6 5 3A. 1 3 5 4 2 6 7C. 1 5 3 4 2 7 65. 采用邻接表存储的图，其深度优先遍历类似于二叉树的()。A.中序遍历B.先序遍历C.后序遍历D.按层次遍历6. 已 知 有 向图 G=(V,E),其 中V=V1,V2,V3,V4,V5,V6,V7,E=,G 的 拓 扑 序列 是12131425353646577( )。A. V ,V ,V ,V ,V ,V ,V B. V ,V ,V ,V ,V ,V ,V13462571326457C. V ,V ,V ,V ,V ,V ,V D. V ,V ,V ,V ,V ,V ,V134526712534677顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（）。在此假定N为线性表中结 点数，且每次查找都是成功的。AN+1B2log NClog NDN8. 下面关于m阶B树说法正确的是（）。每个结点至少有两棵非空子树；树中每个结点至多有m1个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后，树长高一层。A.B.C.D.9. 已知一个线性表（38, 25, 74, 63, 52, 48）,假定采用h（k）=k%7计算Hash地址进行散列存储，若利 用链地址法处理冲突，则在该H ash表上进行查找的平均查找长度为（）。A.1.0B.7/6C.4/3D.3/210. 在排序算法的实施过程中，使用辅助存储空间为O （1）的有（）。A.简单排序法B.快速排序法C.归并排序法D.基数排序法二、填空题1. n （n大于1）个结点的各棵树中，其中深度最大的那棵树的深度是n,它共有个叶子结点和个非叶子结点。2设一棵后序线索树的高是50,结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60, x是y的左孩子。则确定x的后继最多需经过中间结点（不含后继及x本身）3高度为2 （第2层为叶子）的3阶B-树中，最多有个关键字。4.分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为无序的表,则平均情况下最省时间的是5. 简单选择排序和起泡排序中比较次数与序列初态无关的算法有。6. 串的链式存储结构是将存储区域分成一系列大小相同的结点,每个结点有两个域域和域。其中域用于用 于存放数据,域用于存放下一个结点的指针三. 判断1. 顺序存储的线性表可以随机存取。（）2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所得的输出序列 也一定相同。（）3. 十字链表是无向图的一种存储结构。（）4. 折半查找方法适用于排列连续顺序文件的查找。()5. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定 的。()四、应用题1. 用十字链表表示一个有k个非零元素的m x n的稀疏矩阵，贝慎总的结点数为多少?2. G=(V,E )是一个带有权的连通图，则：(1) .请回答什么是G的最小生成树；(2) . G为下图所示,请找出G的所有最小生成树。3. 请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文件 中记录应该满足什么条件？4. 设待排序文件之排序码为(88, 33, 22, 55, 99,11, 66),采用顺序存储。请用直接选择排序算法 对上述文件进行排序，用图示说明排序过程。作业题一参考答案：一、单项选择题1、C 2、B 3、D 4、C 5、B6、B 7、A 8、C 9、D 10、D二、填空题1、非零元很少2、操作受限(或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊)，先进先出(或 后进后出)3、简单选择排序4、O(n2), O(e), O(n)5、邻阵矩阵，邻接表三、算法答：int count = 0;void onechild ( Btree t) if ( t!=NULL) onechild ( t-lchild );onechild ( t-rchild );if ( t-lchild!=NULL & (t-rchild!=NULL | t-lchild!=NULL & t-rchild=NULL ) count+;四、应用题1、答：(036 2吕4812 f6543205S12卡4836654320 中58122043仁3665432550122025366543485S1220253665434858t_f12202536436548t_i5S12202536434S055S1t_f122025434058652、答:A3(G3、答：由于地址空间为10,且从100开始，故散列函数选为H (key) =key%7+100。散歹-坦址100101102103104105106107108109关键字986379175319754649比较次数12111123510用线性探测再散列解决冲突，ASLsucc=27/104、答：成功查找平均比较查找长度为：(n+1) /nlog2 (n+1)-1。作业题二参考答案：一、单项选择题1、C 2、C 3、B 4、C 5、D6、C 7、C 8、B 9、A 10、C二、填空题1、2n -102、6, 2613、log k +124、255、N-16、最优二叉树，最小的二叉树7、根结点，各子树三、应用题1、答：不唯一，型对即可此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=45 2、答：1）插入 10(2) 插入 6C10 / CO(3) 插入3(4)匚-10丿3、答：当关键字为3时，比较次数为4 当关键字为8时，比较次数为1； 当关键字为1 9时，查找不成功；略深度优先遍历序列：ABCDE广度优先遍历序列：ABCED关键路径A-B (长100)作业题三参考答案：一、单项选择题1、D 2、B 3、A 4、C 5、D6、A 7、B 8、C 9、B 10、D二、填空题1、2, 32、43、n-14、e5、相同类型数据，地址连续6三元组顺序表，三元组7. 矩阵转置三、应用题1、答：(E)3. 答：Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成 树过程如下：(下图也可选(2,4)代替(3,4),(5,6)代替(1,5)4. 答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。设该完全二叉树有d层，则除最后一层外各层的结点个数分别为：1,2,4, 8,16, 32,，即第层的结点个数为2i-1。这里第8层有8个结点，显然第8/层是最后的一层，那么第7层的结点个数为27-1=64个，其中的4个结点有8个叶子结点, 余下的为叶子结点，个数为64-4=60,所以该完全二叉树的叶子结点个数为60+8=68个。5. 答：对应的二叉树形式如图所示：作业题四参考答案：一、单项选择题1. A2. B3. D4. B5. D6、C 7、C 8、C 9、B 10、D二、填空题1答：前一位置2. 答：数组元素，数组元素，维数3. 答：邻阵矩阵，邻接表4. 答: 9, 45. 答：48 44 52 64 80 916x1,2三判断1. 答72. 答：x3. 答：x4. 答：5. 答：四、应用题1.答：模式P的next函数值如下:凹；汕注亠 上乂2冲皿L1文件（Z） 術很医1出播：，J 16式工且 衰格 a：.帮Shop文件（Z）術很医1出播：，J 16式心工且衰格 a：.帮BbQP2.答：A共120个字节。a ,的起始地址为：1116。4 5按行优先存储时，。2,5的起始地址为：1068。按列优先存储时，。2,5的起始地址为：1108。3. 答：（1）哈希函数H（key）=（关键字各字符编码之和）MOD 7散列地址0123456789曲nt：x： .1bendaaabacadbdbnaece比较次数12111113394. 答：一趟快速排序：22,19,13,6,24,38,43,32初始大堆：43,38,32,22,24,6,13,19二路并归：第一趟：19,24,32,43,6,38,13,22第二趟：19,24,32,43,6,13,22,38第三趟：6,13,19,22,24,32,38,43堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差作业题五参考答案：一、单项选择题1. 答：C2、D 3、D4. 答：C5. 答：B6. 答: A7. 答: D8. 答：B9. 答：C10. 答：A二、填空题1、1，n-12、603、24、快速排序5、简单选择排序6数据，指针，数据，指针判断1.答：V2.答：X3.答：X4.答：V5.答：X四、应用题1. 答：该十字链表有一个十字链表表头结点，max（m,n）个行列表头结点。另外，每个非零元素对应一个 结点，即k个元素结点，所以共有ma x（m,n）+k+1个结点。2. 答：（1）最小生成树的定义略。（2）最小生成树有两棵。（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W）形式），其中W代表权值。V （G） =1, 2, 3,4, 5E1（G）=（4, 5,2），（2，5，4），（2，3，5），（1，2，7）；E2（G）=（4，5，2），（2，4，4），（2，3，5），（1，2，7）3. 答：采用顺序查找法：文件中记录可以以任意持续存放。 采用折半查找法：文件中的记录必须按照关键字从小到大有序存放。采用分块查找法：将文件分成若干个块，每一个快中的记录可以任意的存放，但块之间的必须按照关键字 从小到大的次序存放，即前一块中的所有记录的关键字的值必须小于后一块的所有记录的关键字的字值。4. 答：排序过程如下：(1) 88,33,22,55,99,11,66(2) 11,33,22,55,99,88,66(3) 11,22,33,55,99,88,66(4) 11,22,33,55,99,88,66(5) 11,22,33,55,99,88,66(6) 11,22,33,55,66,99,88(7) 11,22,33,55,66,88,99(8) 11,22,33,55,66,88,99
展开阅读全文