• / 28
  • 下载费用:8 金币  

【可编辑】南京晓庄学院数据结构题库参考答案.doc

关 键 词:
可编辑 编辑 南京 学院 数据结构 题库 参考答案
资源描述:
数据结构与算法习题册(课后部分参考答案)《数据结构与算法》课程组目录目录课后习题部分第一章 绪论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(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个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) B 在第i个结点后插入一个新结点(1≤i≤n)C 删除第i个结点(1≤i≤n) 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. 已知数组A[n]中的元素为整型,设计算法将其调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数,并要求算法的时间复杂度为O(n)。2. 线性表存放在整型数组A[arrsize]的前elenum 个单元中,且递增有序。编写算法,将元素x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。int insert (datatype A[],int *elenum,datatype x)    /*设elenum为表的最大下标*/{if (*elenum==arrsize-1)  return 0;     /*表已满,无法插入*/else {i=*elenum;         while (i>=0 && A[i]>x)      /*边找位置边移动*/{A[i+1]=A[i];i--;}          A[i+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出栈⑵可以,设I为进栈操作,O为入栈操作,则其操作序列为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(a[i]){switch(a[i]){case '(':Push(s,a[i]);break;case '[':Push(s,a[i]);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 ‘BCDEFEF’4. 若串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 WORKER’2、因为SubString(s,7,8)=‘ STUDENT’Concat(t,SubString(s,7,8))=’GOOD STUDENT’四. 算法设计1. 利用C的库函数strlen, strcpy(或strncpy)写一个算法void StrDelete(char *S,int t,int m) ,删除串S中从位置i开始的连续的m个字符。若i≥strlen(S),则没有字符被删除;若i+m≥strlen(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 Temp[Maxsize];//定义一个临时串   if(i+m=strlen(S)&& iA[i][j]) min[i]=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. 序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中,结点A[i]若有左子树,则左子树的根结点是( D )。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i]3. 完全二叉树中的任一结点,若其右分支下的子孙的最大层次为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其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=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算法求最小生成树的时间复杂度为O(n2),利用Kruskal算法求最小生成树的时间复杂度为 O(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个待排序记录序列进行快速排序,所需要的最好时间是 O(nlog2n),最坏时间是 O(n2) 二. 选择题1. 下列序列中,(A)是执行第一趟快速排序的结果。A [da,ax,eb,de,bb] ff [ha,gc] B [cd,eb,ax,da] ff [ha,gc,bb]C [gc,ax,eb,cd,bb] ff [da,ha] D [ax,bb,cd,da] ff [eb,gc,ha]2. 堆的形状是一棵(C)。A二叉排序树 B满二叉树 C完全二叉树 D 判定树3. 希望用最快的速度从5000个元素挑选出前10个最大的,采用( B )方法最好。A快速排序 B堆排序 C希尔排序 D 归并排序4. 设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按升序排列,则( D )是起泡排序一趟扫描的结果,( B )是增量为4的希尔排序一趟扫描的结果,( E )二路归并排序一趟扫描的结果,( A )是以第一个元素为轴值的快速排序一趟扫描的结果,( C )是堆排序初始建堆的结果。A(F,H,C,D,P,A,M,Q,R,S,Y,X) B(P,A,C,S,Q,D,F,X,R,H,M,Y) C(A,D,C,R,F,Q,M,S,Y,P,H,X) D(H,C,Q,P,A,M,S,R,D,F,X,Y) E(H,Q,C,Y,A,P,M,S,D,R,F,X)5. 下述几种排序方法中,要求内存最小的是(AD )A 插入排序 B快速排序 C堆排序 D选择排序三. 简答题1. 已知数据序列为(12,5,9,20,6,31,24),对该数据序列进行排序,写出插入排序. 起泡排序. 快速排序. 简单选择排序以及二路归并排序每趟的结果。2. 判别下列序列是否为堆,如不是,按照堆排序思想把它调整为堆,用图表示建堆的过程。⑴(1,5,7,25,21,8,8,42)⑵(3,9,5,8,4,17,21,6)【解答】序列⑴是堆,序列⑵不是堆,调整为堆(假设为大根堆)的过程如下图所示。四. 算法设计1. 直接插入排序中寻找插入位置的操作可以通过折半查找来实现。据此写一个改进的插入排序的算法。#region 折半插入排序算法 void HalfInsertSort(int[] array) { for(int i=2;i= high + 1; --j) { array[j + 1] = array[j]; } array[j + 1] = array[0]; } } #endregion2. 已知(k1, k2, …, kn)是堆,试写一算法将(k1, k2, …, kn, kn+1)调整为堆
展开阅读全文
  语墨文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:【可编辑】南京晓庄学院数据结构题库参考答案.doc
链接地址:http://www.wenku38.com/p-81526.html

                                            站长QQ:1002732220      手机号:18710392703    


                                                          copyright@ 2008-2020 语墨网站版权所有

                                                             经营许可证编号:蜀ICP备18034126号

网站客服微信
收起
展开