2021年南京晓庄学院数据结构题库参考答案.docx

数据构造与算法习题册（课后某些参照答案）数据构造与算法课程组目录课后习题部分第一章 绪论1第二章 线性表3第三章 栈和队列5第四章 串8第五章 数组和广义表10第六章 树和二叉树13第七章 图16第九章 查找20第十章 排序23第一章 绪论一. 填空题1. 从逻辑关系上讲，数据构造类型重要分为 集合 、线性构造、树构造和 图构造。2. 数据存储构造重要有 顺序存储和 链式存储 两种基本办法，无论哪种存储构造，都要存储两方面内容：数据元素 和 数据元素之间关系 。3. 算法具备五个特性，分别是 有穷性 、拟定性、可行性、输入 、输出 。4. 算法设计规定中健壮性指是 算法在发生非法操作时可以作出解决特性。二. 选取题1. 顺序存储构造中数据元素之间逻辑关系是由 C 表达，链接存储构造中数据元素之间逻辑关系是由 D 表达。A 线性构造 B 非线性构造 C 存储位置 D 指针2. 假设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承爸爸或妈妈遗产；子女间不能互相继承。则表达该遗产继承关系最适当数据构造应当是 B 。A 树 B 图 C 线性表 D 集合3. 算法指是 A 。A 对特定问题求解环节一种描述，是指令有限序列。B 计算机程序 C 解决问题计算办法 D 数据解决三. 简答题1. 分析如下各程序段，并用大O记号表达其执行时间。(1) (2)i=1;k=0;i=1;k=0;While(in-1)do k=k+10*i； k=k+10*i；i+； i+; while(inext =rear-next；rear-next =s；rear =s;；删除开始结点操作顺序为q=rear-next-next；rear-next-next=q-next；delete q；。 二. 选取题1.数据在计算机存储器内表达时物理地址与逻辑地址相似并且是持续，称之为： C A存储构造 B逻辑构造 C顺序存储构造 D链式存储构造2. 在n个结点顺序表中，算法时间复杂度是O（1）操作是： A A 访问第i个结点（1in）和求第i个结点直接前驱（2in） B 在第i个结点后插入一种新结点（1in）C 删除第i个结点（1in） D 将n个结点从小到大排序3. 线性表L在 B 状况下合用于使用链式构造实现。A 需经常修改L中结点值 B 需不断对L进行删除插入C L中具有大量结点 D L中结点构造复杂4. 单链表存储密度 C A不不大于1 B等于1 C不大于1 D不能拟定三. 判断题1. 线性表逻辑顺序和存储顺序总是一致。 F 2. 线性表顺序存储构造优于链接存储构造。 F 3. 设p，q是指针，若p=q，则*p=*q。 F 4. 线性构造基本特性是：每个元素有且仅有一种直接前驱和一种直接后继。 F 四. 简答题1. 分析下列状况下，采用何种存储构造更好些。(1)若线性表总长度基本稳定，且很少进行插入和删除操作，但规定以最迅速度存取线性表中元素。(2)如果n个线性表同步并存，并且在解决过程中各表长度会动态发生变化。(3)描述一种都市设计和规划。 应选用顺序存储构造。很少进行插入和删除操作，因此空间变化不大，且需要迅速存取，因此应选用顺序存储构造。 应选用链式存储构造。链表容易实现表容量扩充，适合表长度动态发生变化。 应选用链式存储构造。由于一种都市设计和规划涉及活动诸多，需要经常修改、扩充和删除各种信息，才干适应不断发展需要。而顺序表插入、删除效率低，故不适当。五. 算法设计1. 已知数组An中元素为整型，设计算法将其调节为左右两某些，左边所有元素为奇数，右边所有元素为偶数，并规定算法时间复杂度为O(n)。2. 线性表存储在整型数组Aarrsize前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表恰当位置上，以保持线性表有序性，并且分析算法时间复杂度。int insert (datatype A,int *elenum,datatype x)/*设elenum为表最大下标*/if (*elenum=arrsize-1) return 0;/*表已满，无法插入*/else i=*elenum; while (i=0 & Aix)/*边找位置边移动*/Ai+1=Ai;i-; Ai+1=x;/*找到位置是插入位下一位*/ (*elenum)+;return 1;/*插入成功*/O（n）第三章 栈和队列一. 填空题1. 设有一种空栈，栈顶指针为1000H，既有输入序列为1. 2. 3. 4. 5， 通过push，push，pop，push，pop，push，push后，输出序列是 23 ，栈顶指针为 1003H 。2. 栈普通采用两种存储构造是 顺序栈 、链栈 ；其鉴定栈空条件分别是 TOP=-1 、 TOP=NULL ，鉴定栈满条件分别是 TOP=数组长度 、存储空间满 。3. 栈 可作为实现递归函数调用一种数据构造。4. 表达式a*(b+c)-d后缀表达式是 abc+*d- 。二. 选取题1. 若一种栈输入序列是1，2，3，n，输出序列第一种元素是n，则第i个输出元素是 D 。A 不拟定 B n-i C n-i-1 D n-i+12. 设栈S和队列Q初始状态为空，元素e1. e2. e3. e4. e5. e6依次通过栈S，一种元素出栈后即进入队列Q，若6个元素出队顺序是e2. e4. e3. e6. e5. e1，则栈S容量至少应当是 C 。A 6 B 4 C 3 D 23. 一种栈入栈序列是1，2，3，4，5，则栈不也许输出序列是 C 。A 54321 B 45321 C 43512 D 12345 三. 判断题 1. 有n个元素依次进栈，则出栈序列有(n-1)/2种。 F 2. 栈可以作为实现过程调用一种数据构造。 T 3. 在栈满状况下不能做进栈操作，否则将产生“上溢”。 T 4. 在循环队列中，front指向队头元素前一种位置，rear指向队尾元素位置，则队满条件是 front=rear。 F 四. 简答题1. 设有一种栈，元素进栈顺序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请阐明因素。 C，E，A，B，D C，B，A，D，E不能，由于在C、E出栈后，A一定在栈中，并且在B下面，不也许先于B出栈可以，设为进栈操作，为入栈操作，则其操作序列为IIIOOOIOIO。2. 在操作序列push(1). push(2). pop. push(5). push(7). pop. push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表达k入栈，pop表达栈顶元素出栈。）栈顶元素为6，栈底元素为1。3. 在操作序列EnQueue(1). EnQueue(3). DeQueue. EnQueue(5). EnQueue(7). DeQueue. EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表达整数k入队，DeQueue表达队头元素出队）。队头元素为5，队尾元素为9。4. 简述如下算法功能（栈元素类型SElemType为int）。 (1) status algo1(Stack S,int e) Stack T；int d；InitStack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d)； Push(S,d); /S中如果存在e，则删除它。(2) void algo2(Queue &Q)Stack S； int d； InitStack(S);while(!QueueEmpty(Q)DeQueue(Q，d)；Push(S，d);while(!StackEmpty(S)Pop(S，d)；EnQueue(Q，d);/队列逆置五. 算法设计1. 试写一种鉴别表达式中开、闭括号与否配对浮现算法BOOL BracketCorrespondency(char a)int i=0;Stack s;InitStack(s);ElemType x;while(ai)switch(ai)case (:Push(s,ai);break;case :Push(s,ai);break;case ):GetTop(s,x);if(x=()Pop(s,x);else return FALSE;break;case :GetTop(s,x);if(x=) Pop(s,x);else return FALSE;break;default:break;i+;if(s.size!=0) return FALSE;return TRUE;2. 假设称正读和反读都相似字符序列为“回文”，例如，abba和abcba是回文，abcde和ababab则不是回文。试写一种算法鉴别读入一种以为结束符字符序列与否是“回文”。Status SymmetryString(char* p)Queue q;if(!InitQueue(q) return 0;Stack s;InitStack(s);ElemType e1,e2;while(*p)Push(s,*p);EnQueue(q,*p);p+;while(!StackEmpty(s)Pop(s,e1);DeQueue(q,e2);if(e1!=e2) return FALSE;return OK;第四章 串一. 填空题1. 不包括任何字符（长度为0）串 称为空串；由一种或各种空格（仅由空格符）构成串 称为空白串。2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 ，“/”字符定位位置为 3 。3. 若n为主串长，m为子串长，则串典型模式匹配算法最坏状况下需要比较字符总次数为 (n-m+1)*m 。二. 选取题1. 串是一种特殊线性表，其特殊性体当前： （ B ）A可以顺序存储 B数据元素是一种字符 C可以链式存储 D数据元素可以是各种字符2. 设有两个串p和q，求q在p中初次浮现位置运算称作：（ B ） A连接 B模式匹配 C求子串 D求串长3. 设串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)成果串是：（ D ） A BCDEF B BCDEFG C BCPQRST D BCDEFEF4. 若串S=”software”，其子串数目是（ B ）。 A 8 B 37 C 36 D 9三. 计算题1. 设s=I AM A STUDENT，t=GOOD，q=WORKER，求：1）Replace(s,STUDENT,q) 2）Concat(t,SubString(s,7,8)1、Replace(s,STUDENT,q)I AM A WORKER2、由于SubString(s,7,8) STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT四. 算法设计1. 运用C库函数strlen，strcpy（或strncpy）写一种算法void StrDelete(char *S,int t,int m) ，删除串S中从位置i开始持续m个字符。若istrlen(S)，则没有字符被删除；若i+mstrlen(S)，则将S中从位置i开始直至末尾字符均被删去。提示：strlen是求串长(length)函数：int strlen(char s)； /求串长度strcpy是串复制(copy)函数：char *strcpy(char to,char from)；/该函数将串from复制到串to中，并且返回一种指向串to开始处指针。void StrDelete(char *S，int i ,int m) /串删除char TempMaxsize;/定义一种暂时串if(i+m=strlen(S)& istrlen(S)strcpy(&Si,0);/把位置i元素置为0，表达串结束第五章 数组和广义表一. 填空1. 假设有二维数组A68，每个元素用相邻6个字节存储，存储器按字节编址。已知A起始存储位置（基地址）为1000，则数组A体积（存储量）为 288 ；末尾元素A57第一种字节地址为 1282 ；若按行存储时，元素A14第一种字节地址为 1072；若按列存储时，元素A47第一种字节地址为 1276 。2. 三元素组表中每个结点相应于稀疏矩阵一种非零元素，它包具有三个数据项，分别表达该元素行下标 、 列下标 和 元素值 。3. 广义表(a)，(b),c),(d)长度是 3 ，深度是 4 ，表头是 (a) ，表尾是(b),c),(d) 。4. 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b运算是Head(Head(Tail(LS) 。二. 选取题1. 假设有60行70列二维数组a160，170以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列元素a32,58存储地址为 ( A )。（无第0行第0列元素）A 16902 B 16904 C 14454 D 答案A，B，C均不对2. 设矩阵A是一种对称矩阵，为了节约存储，将其下三角某些按行序存储在一维数组B 1，n(n-1)/2 中，下三角某些中任一元素ai,j(ij)，在一维数组B中下标k值是：( B )A i(i-1)/2+j-1 B i(i-1)/2+j C i(i+1)/2+j-1 Di(i+1)/2+j3. 一种n*n对称矩阵，用压缩存储办法解决其对称性质后存储，则其容量为：( C )。A n*n B n*n/2 C (n+1)*n/2 D (n+1)*(n+1)/2三. 计算题1. 设有一种二维数组Amn，假设A00存储位置在644，A22存储位置在676，每个元素占一种空间，问A33存储在什么位置？写出计算过程。(676-644)/1=32A22地址相对A00偏移量为32，则A33相较于A00偏移量为32*3/2=48A33地址为48+644=6922. 设A99是一种10*10对称矩阵，采用压缩存储方式存储其下三角某些，已知每个元素占用两个存储单元，其第一种元素A00存储位置在1000，求下面问题计算过程及成果：给出A45存储位置。A45是上三角某些，因此存在 A 5 4若以行序为主序，则地址为1000+2（5（1+5）/ 2+4）=1036若以列序为主序，则地址为1000+2（4（10+7）/ 2+5）=1062给出存储位置为1080元素下标。i(i+1)/2+j或j(10+10-j+1)/2+i=40得i=9，j=4或i=8 j=5，A 8 5 或 A 9 43. 一种稀疏矩阵如图所示，则相应三元组线性表是什么？其相应十字链表是什么？0 0 2 03 0 0 00 0 -1 50 0 0 04. 下列各三元组表分别表达一种稀疏矩阵，试写出它们稀疏矩阵。0 2 0 0 12 0 0 0 3 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 四. 算法设计1. 设计一种算法，计算一种三元组表表达稀疏矩阵对角线元素之和。2. 若在矩阵A中存在一种元素ai,j（0in-1，0jm-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵一种鞍点。假设以二维数组存储矩阵A，试设计一种求该矩阵所有鞍点算法，并分析最坏状况下时间复杂度void Saddle(int Amn) /A是m*n矩阵,本算法求矩阵A中马鞍点. int maxn=0，/max数组存储各列最大值元素行号,初始化为行号0;minm=0，/min数组存储各行最小值元素列号,初始化为列号0;i，j; for(i=0;im;i+) /选各行最小值元素和各列最大值元素.for(j=0;jn;j+) if(AmaxjjAij) mini=j； /修改第i行最小元素列号. for (i=0;i0）个结点满二叉树共有 (n+1)/2 个叶子结点和 (n-1)/2 个非终端结点。3. 设深度为k二叉树上只有度为0和度为2结点，该二叉树结点数也许达到最大值是 2k-1 ，最小值是 2k-1 。4. 深度为k二叉树中，所含叶子个数最多为 2k-1 。5. 在顺序存储二叉树中编号为i和j两个结点处在同一层条件为：二. 选取题1. 前序遍历和中序遍历成果相似二叉树是（ D ）。A 根结点无左孩子二叉树 B 根结点无右孩子二叉树C 所有结点只有左子树二叉树 D 所有结点只有右子树二叉树2. 序存储办法将完全二叉树中所有结点逐级存储在数组A1 An中，结点Ai若有左子树，则左子树根结点是（ D ）。 A A2i-1 B A2i+1 C Ai/2 D A2i3. 完全二叉树中任一结点，若其右分支下子孙最大层次为h，则其左分支下子孙最大层次为（ C ）。A h B h+1 C h或h+1 D 任意4. 在线索二叉树中，一种结点是叶子结点充要条件为（ C ）。 A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左. 右线索标志均为0 D 左. 右线索标志均为15. 由权值为3，8，6，2，5叶子结点生成一棵哈夫曼树，其带权途径长度为（ C ）。 A 24 B 48 C 53 D 72三. 简答题1. 已知二叉树中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，请构造出此二叉树，并写出此树后序遍历序列。2. 将下图所示树转换为二叉树，3. 图5-17所示二叉树转换为树或森林4. 已知某字符串S中共有8种字符A,B,C,D,E,F,G,H，分别浮现2次. 1次. 4次. 5次. 7次. 3次. 4次和9次。1）试构造出哈夫曼编码树，并对每个字符进行编码EH2）问该字符串编码至少有多少位。CGDFBAA:00000 B:00001 C:100 D:001 E:11 F:0001 G:101 H:01其带权途径长度=25+15+34+53+92+43+43+72=98，因此，该字符串编码长度至少为98位。四. 算法设计1. 设计算法求二叉树结点个数2. 以二叉链表为存储构造，编写算法求二叉树中结点x双亲3. 编写算法互换二叉树中所有结点左右子树。第七章 图一. 填空题1. 设无向图G中顶点数为n，则图G至少有 0 条边，至多有 n(n-1)/2 条边；若G为有向图，则至少有 0 条边，至多有 n(n-1) 条边。2. 任何连通图连通分量只有一种，即是 它自身 3. 若一种有向图由邻接矩阵表达，则计算第j个顶点入度办法是 求矩阵第j列元素之和4. 图深度优先遍历类似于树 先根 遍历，广度优先遍历类似于树 层序 遍历。 5. 对于具有n个顶点e条边连通图，运用Prim算法求最小生成树时间复杂度为(n2)，运用Kruskal算法求最小生成树时间复杂度为 (elog2e) 。二. 选取题1. 在一种无向图中，所有顶点度数之和等于所有边数（ C ）倍。A 1/2 B 1 C 2 D 42. n个顶点强连通图至少有（A）条边。 A n B n+1 C n-1 D n(n-1)3. 含n 个顶点连通图中任意一条简朴途径，其长度不也许超过（ C ）。A 1 B n/2 C n-1 D n 4. 对于一种具备n个顶点无向图用邻接矩阵存储，则该矩阵大小是（ D ）。A n B (n-1)2 C n-1 D n25. 设无向图G=(V，E)和G =(V，E )，如果G 是G生成树，则下面说法中错误是（ B ）。A G 为 G子图 B G 为 G连通分量C G 为G极小连通子图且V= V D G 是G一种无环子图6. 鉴定一种有向图与否存在回路除了可以运用拓扑排序办法外，还可以用（ D ）。A 求核心途径办法 B 求最短途径办法C 广度优先遍历算法 D 深度优先遍历算法7. 下面关于工程筹划AOE网论述中，不对的是（ B ）A 核心活动不按期完毕就会影响整个工程完毕时间B 任何一种核心活动提前完毕，那么整个工程将会提前完毕C 所有核心活动都提前完毕，那么整个工程将会提前完毕D 某些核心活动若提前完毕，那么整个工程将会提前完三. 计算题1. 已知一种连通图如图所示，试给出图邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一种按深度优先遍历和广度优先遍历顶点序列。邻接矩阵表达如下：深度优先遍历序列为：v1 v2 v3 v5 v4 v6广度优先遍历序列为：v1 v2 v4 v6 v3 v5邻接表表达如右：2. 已知无向图G邻接表如下图所示，分别写出从顶点1出发深度遍历和广度遍历序列，并画出相应生成树。深度优先遍历序列为：1，2，3，4，5，6相应生成树为：广度优先遍历序列为：1，2，4，3，5，6相应生成树为：3. 下图所示是一种无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。4. 如右图所示有向网图，运用Dijkstra算法求从顶点v1到其她各顶点最短途径。从源点v1到其她各顶点最短途径如下表所示。源点 终点 最短途径 最短途径长度v1 v3 v1 v3 15v1 v5 v1 v5 15v1 v2 v1 v3 v2 25v1 v6 v1 v3 v2 v6 40v1 v4 v1 v3 v2 v4 455. 已知一种AOV网如下图所示，写出所有拓扑序列。拓扑序列为：v0 v1 v5 v2 v3 v6 v4、v0 v1 v5 v2 v6 v3 v4、v0 v1 v5 v6 v2 v3 v4。四. 算法设计1. 设计算法，将一种无向图邻接表转换成邻接矩阵。2. 设计算法，计算图中出度为零顶点个数。3. 已知一种有向图邻接表，编写算法建立其逆邻接表第九章 查找一. 填空题1. 顺序查找技术适合于存储构造为 顺序和链式存储 线性表，而折半查找技术合用于存储构造为 顺序存储 线性表，并且表中元素必要是 按核心码有序 。2. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。3. 在各种查找办法中，平均查找长度与结点个数n无关查找办法是 散列（哈希）查找 。4. 为了能有效地应用哈希查找技术，必要解决两个问题是 构造散列函数 和 解决冲突。5. 有一种表长为m散列表，初始状态为空，现将n（nlchild&flag) Is_BSTree(T-lchild)； if(T-datadata； if(T-rchild&flag) Is_BSTree(T-rchild)； return flag；/Is_BSTree 第十章 排序一. 填空题1. 排序办法有诸各种， 插入排序 法从未排序序列中依次取出元素，与已排序序列中元素作比较，将其放入已排序序列对的位置上。 选取排序 法从未排序序列中挑选元素，并将其依次放入已排序序列一端。互换排序是对序列中元素进行一系列比较，当被比较两元素为逆序时，进行互换； 冒泡排序 和 迅速排序 是基于此类办法两种排序办法，而 迅速排序是比冒泡排序效率更高办法； 堆排序 法是基于选取排序一种办法，是完全二叉树构造一种重要应用。2. 一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。3. 对n个待排序记录序列进行迅速排序，所需要