当前位置：文档之家 › 数据结构与算法习题及答案

数据结构与算法习题及答案

  • 格式：doc
  • 大小：616.00 KB
  • 文档页数：13

精心整理第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现5A6{x=x-10;y--;}elsex++;（2）for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;（3）s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;（6）x=n;n108 C63.5 C1 C-1 C1 Cext=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;2,=(rear+1)%=(rear+1)%(m+1)（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

A.(rear+1)%n====frontC．rear+1==frontD.(rear-l)%n==front（14）栈和队列的共同点是（）。

A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点（15）一个递归算法必须包括（）。

A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。

试写一个算法判定给定的字符向量是否为回文。

(提示：将一半字符入栈)根据提示，算法可设计为：0’9’0’9’0’0’9’0’0’9’0’0’0’M-1]实现循环队列，其中M是队列长度。

设队头指针front 和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。

定义front=rear时为队空，(rear+1)%m=front为队满。

约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。

（1）#defineM队列可能达到的最大长度typedefstruct{elemtpdata[M];int front,rear;}cycqueue;地址1，在A．1和1B．1和3 C．1和2D．2和3（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。

①计算模式p的naxtval函数值；②不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

①p的nextval函数值为0110132。

（p的next函数值为0111232）。

②利用KMP(改进的nextval)算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)（3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址SHA-Z这[（下面k和p的二层int[第5章树和二叉树1．选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子（2）由3个结点可以构造出多少种不同的二叉树（）A．2B．3 C．4D．5（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A．250B．500 C．254D．501（4）一个具有1025个结点的二叉树的高h为（）。

A．11B．10 C．11至1025之间D．10至1024之间（5）深度为h的满m叉树的第k层有（）个结点。

(1=<k=<h)A．m k-1B．m k-1 C．m h-1D．m h-1（6）利用二叉链表存储树，则根结点的右指针是（）。

A．指向最左孩子B．指向最右孩子C．空D．非空（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

（适。

（（（（（（（2（①先序序列与后序序列相同②中序序列与后序序列相同③先序序列与中序序列相同④中序序列与层次遍历序列相同先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：（１）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（２）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．（３）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（４）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树（2）设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC①画出这棵二叉树。

②画出这棵二叉树的后序线索树。

③将这棵二叉树转换成对应的树（或森林）。

(1)(2)（3）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为，，，，，，，。

①试为这8个字母设计赫夫曼编码。

②试设计另一种由二进制表示的等长编码方案。

③对于上述实例，比较两种方案的优缺点。

解：方案1；哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6],(7,10)】,……19,21,32C。

D ．层（11）广度优先遍历类似于二叉树的（）。

A ．先序遍历B ．中序遍历C ．后序遍历D ．层次遍历 A B F D (CE H G（12）图的BFS 生成树的树高比DFS 生成树的树高（）。

A ．小B ．相等C ．小或相等D ．大或相等（13）已知图的邻接矩阵如图所示，则从顶点0出发按深度优先遍历的结果是（）。

图邻接矩阵（14）已知图的邻接表如图所示，则从顶点0出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。

图邻接表（15）下面（）方法可以判断出一个有向图是否有环。

A ．深度优先遍历B ．拓扑排序C ．求最短路径D ．求关键路径 2．应用题（1）已知如图所示的有向图，请给出： ①每个顶点的入度和出度； ②邻接矩阵； ③邻接表； ④逆邻接表。

（2）已知如图所示的无向网，请给出： ①邻接矩阵； ②邻接表； ③最小生成树 a → b 4 → c 3b → a 4 →c 5 →d 5 →e 9 ^ c → a 3 → b 5 → d 5 → h 5 ^ d → b 5 → c 5 → e 7 →f 6 →g 5 →h 4^e → b 9 → d 7 →f 3 ^ f → d 6 → e 3 →g 2 ^ g → d 5 → f 2 →h 6 ^ h→ c 5 → d 4→ g6^（3）已知图的邻接矩阵如所示。

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

（4）有向网如图所示，试用迪杰斯特拉算法求出从顶点a 到其他各顶点图无向网 图有向图A ．0243156B ．0136542C ．0134256D ．0361542⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110A ．0132B ．0231C ．0321D ．0123间的最短路径，完成表。

3．算法设计题（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：①增添一个新顶点v，InsertVex(G,v)；②删除顶点v及其相关的边，DeleteVex(G,v);③增加一条边<v，w>，InsertArc(G,v,w);④删除一条边<v，w>，DeleteArc(G,v,w)。

dj){[j].adj=1;++;}returnOK;}dj=0;;returnOK;}StatusDelete_Arc(MGraph&G,charv,charw)dj){[j].adj=0;;}returnOK;}余算法请自行写出.StatusInsert_Arc(ALGraph&G,charv,charw)7.3.77.3.8irstarc;p;p=p->nextarc) {k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;irstarc;p;p=p->nextarc，level--) {level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;irstarc;p;p=p->nextarc){l=p->adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;2 C4 C3 Cey==3)k--;ey==1)ey==2)if (i<=j){temp=r[k];r[k]=r[j];r[j]=temp;j++;}j-1]作为红色，r[j..k-1]为白色，r[k..n]为兰色。

从j=1开始查看，若r[j]为白色，则j=j+1；若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1；若r[j]为兰色，则交换r[j]与r[k];k=k-1。

算法进行到j>k 为止。

算法片段如下：int i=1,j=1,k=n;while(j<=k)if(r[j]==1)n]中。

若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。

请简要说明算法思想并编写算法。

[题目分析]把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。

int index(RecTypeR[],int l,h,datatypekey){int i=l,j=h;while(i<j){while(i<=j&&R[j].key>key)j--;if(R[j].key==key)return j;whileif}。

合集下载

数据结构与算法复习题库含答案

数据结构与算法复习题库含答案

数据结构与算法复习题库含答案1. 问题描述：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

答案：可以使用哈希表来解决此问题。

首先初始化一个空的哈希表，然后遍历数组中的每个元素。

对于每个元素，首先计算目标值与当前元素的差值，然后在哈希表中查找该差值。

如果找到了该差值，则说明存在两个数的和等于目标值，返回这两个数的下标；否则，将当前元素插入到哈希表中。

时间复杂度为O(n)，其中n为数组的长度。

2. 问题描述：给定一个字符串，找出其中不含重复字符的最长子串的长度。

答案：可以使用滑动窗口来解决此问题。

维护一个窗口，其中包含没有重复字符的子串。

遍历字符串中的每个字符，如果该字符不在窗口中，将其加入窗口；如果该字符在窗口中，移动窗口的左边界直到窗口中不包含重复字符。

记录窗口的最大长度。

时间复杂度为O(n)，其中n为字符串的长度。

3. 问题描述：给定一个字符串和一个单词列表，找出字符串中可以由单词列表中的单词组成的所有子串的起始位置。

答案：可以使用滑动窗口和哈希表来解决此问题。

首先统计单词列表中每个单词的出现次数。

然后遍历字符串中的每个位置作为子串的起始位置，维护一个滑动窗口。

在窗口中依次取出长度和单词列表中单词总长度相等的子串，在哈希表中统计子串中每个单词出现的次数。

如果窗口中的子串与单词列表中的单词出现次数一致，则记录该子串的起始位置。

时间复杂度为O(n*m)，其中n为字符串的长度，m为单词列表中的单词个数。

4. 问题描述：给定一个无序的整数数组，找出其中缺失的第一个正整数。

答案：可以使用原地哈希表来解决此问题。

遍历数组中的每个元素，将每个正整数放到数组中对应的位置上。

遍历数组中的每个元素，如果该位置上的数不等于数组索引加一，则该索引加一即为缺失的第一个正整数。

时间复杂度为O(n)，其中n为数组的长度。

5. 问题描述：给定一个字符串s，找到s中最长的回文子串。

答案：可以使用动态规划来解决此问题。

《数据结构与算法》课后习题答案

《数据结构与算法》课后习题答案

2.3 课后习题解答2.3.2 判断题1．线性表的逻辑顺序与存储顺序总是一致的。

〔×〕2．顺序存储的线性表可以按序号随机存取。

〔√〕3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

〔×〕4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有一样的特性，因此属于同一数据对象。

〔√〕5．在线性表的顺序存储构造中，逻辑上相邻的两个元素在物理位置上并不一定相邻。

〔×〕6．在线性表的链式存储构造中，逻辑上相邻的元素在物理位置上不一定相邻。

〔√〕7．线性表的链式存储构造优于顺序存储构造。

〔×〕8．在线性表的顺序存储构造中，插入和删除时移动元素的个数与该元素的位置有关。

〔√〕9．线性表的链式存储构造是用一组任意的存储单元来存储线性表中数据元素的。

〔√〕10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储构造。

〔×〕11．静态链表既有顺序存储的优点，又有动态链表的优点。

所以它存取表中第i 个元素的时间与i 无关。

〔×〕12．线性表的特点是每个元素都有一个前驱和一个后继。

〔×〕2.3.3 算法设计题1．设线性表存放在向量A[arrsize] 的前 elenum 个分量中，且递增有序。

试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

【提示】直接用题目中所给定的数据构造〔顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个构造体〕，因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，假设有，那么根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，〔也可以从高低标端开始一边比拟，一边移位〕然后插入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. 用于分离由加权无向边组成的完全连通图中连通分量中不相邻顶点的单纯形算法是（C）A. 最小生成树算法B. 广度优先搜索算法C. 最大流算法D. 关键路径算法2. 要设计一个使用图来表示的行业里的公司的决策问题，图的顶点应该表示（B）A. 公司拥有的资源B. 公司所面对的决策选择C. 公司内部的组织结构D. 公司的竞争对手3. 算法的计算时间复杂度O(log2n)中的n表示（A）A. 求解问题规模B. 求解算法所处理的数据量C. 求解问题中所涉及的参数量D. 求解算法所进行的求解步骤4. 以树形结构存储的优先队列中元素出队的操作时间复杂度是（C）A. O(1)B. O(n)C. O(log2n)D. O(n2)5. 以下关于贝尔曼-福特算法的描述错误的是（A）A. 贝尔曼-福特算法是求图 G=(V,E)最小生成树的法B. 贝尔曼-福特算法克服了Prim算法因存储顶点增量重复而带来的内存浪费C. 求解过程中，要维护贝尔曼-福特树中任意两个顶点之间的最短距离D. 贝尔曼-福特算法可以解决单源最短路径问题二、简答题1. 请说明拓扑排序的概念，以及如何使用拓扑排序解决求解关键路径的问题。

拓扑排序是指对有向无环图进行排序，得到一个顶点的线性序列，使得对于图中的每条有向边（u,v），均有u在v之前。

拓扑排序可用于求解关键路径，首先对所有活动按照拓扑排序的方法进行排序，计算该活动的最早开始时间ESi和最晚开始时间LSi，若ESi=LSi，则此活动运行期间不能延迟，为关键活动；若ESi≠LSi，则此活动可以合理推迟，不为关键活动。

数据结构与算法设计课后习题及答案详解

数据结构与算法设计课后习题及答案详解

数据结构与算法设计课后习题及答案详解1. 习题一：数组求和题目描述：给定一个整数数组，编写一个函数来计算它的所有元素之和。

解题思路：遍历数组，将每个元素累加到一个变量中，最后返回累加和。

代码实现：```pythondef sum_array(arr):result = 0for num in arr:result += numreturn result```2. 习题二：链表反转题目描述：给定一个单链表，反转它的节点顺序。

解题思路：采用三指针法，依次将当前节点的下一个节点指向上一个节点，然后更新三个指针的位置，直到链表反转完毕。

代码实现：```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev```3. 习题三：二叉树的层序遍历题目描述：给定一个二叉树，返回其节点值的层序遍历结果。

解题思路：采用队列来实现层序遍历，先将根节点入队，然后循环出队并访问出队节点的值，同时将出队节点的左右子节点入队。

代码实现：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None): self.val = valself.left = leftself.right = rightdef level_order(root):if not root:return []result = []queue = [root]while queue:level = []for _ in range(len(queue)):node = queue.pop(0)level.append(node.val)if node.left:queue.append(node.left)queue.append(node.right)result.append(level)return result```4. 习题四：堆排序题目描述：给定一个无序数组，使用堆排序算法对其进行排序。