南京晓庄学院数据结构题库参考答案
数据结构与算法
习题册
（课后部分参考答案）
《数据结构与算法》课程组
目录
目录
课后习题部分
第一章绪论 (1)
第二章线性表 (3)
第三章栈和队列 (5)
第四章串 (8)
第五章数组和广义表 (10)
第六章树和二叉树 (14)
第七章图 (17)
第九章查找 (21)
第十章排序 (24)
第一章绪论
一. 填空题
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(i { { k=k+10*i; k=k+10*i; i++; i++; } }while(i<=n) ⑴基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 ⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 2. 设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}， R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种 结构。 其逻辑结构图如下所示，它是一种图结构。 3. 求多项式A(x)的算法可根据下列两个公式之一来设计： ⑴A(x)=a n x n+a n-1x n-1+…+a1x+a0 ⑵A(x)=(…(a n x+a n-1)x+…+a1)x)+a0 根据算法的时间复杂度分析比较这两种算法的优劣。 第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。 第二章线性表 一. 填空题 1. 在顺序表中，等概率情况下，插入和删除一个元素平均需移动表长的一半个元素，具体移动元素的个数与表长和插入的位置有关。 2. 在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动n-i+1 个元素，删除第i（1≤i≤n）个元素时，需向前移动n-i 个元素。 3. 在单循环链表中，由rear指向表尾，在表尾插入一个结点s的操作顺序是s->next =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+1 2. 设栈S和队列Q的初始状态为空，元素e1. e2. e 3. e 4. e 5. e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2. e4. e3. e 6. e5. e1，则栈S的容量至少应该是C 。 A 6 B 4 C 3 D 2 3. 一个栈的入栈序列是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(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 { strcpy (Temp, &S[i+m]);//把删除的字符以后的字符保存到临时串中 strcpy( &S[i],Temp);//用临时串中的字符覆盖位置i之后的字符 } else if(i+m>=strlen(S)&& i { strcpy(&S[i],"\0");//把位置i的元素置为'\0'，表示串结束 } } 第五章数组和广义表 一. 填空 1. 假设有二维数组A6×8，每个元素用相邻的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列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为( A )。（无第0行第0列元素） A 16902 B 16904 C 14454 D 答案A, B, C均不对 2. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[ 1, n(n-1)/2 ]中，下三角部分中任一元素a i,j(i≤j), 在一维数组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+j 3. 一个n*n的对称矩阵，用压缩存储方法处理其对称性质后存储，则其容量为：( C )。 A n*n B n*n/2 C (n+1)*n/2 D (n+1)*(n+1)/2 三. 计算题 1. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？写出计算过程。 (676-644)/1=32 A[2][2]的地址相对A[0][0]偏移量为32，则A[3][3]相较于A[0][0]的偏移量为 32*3/2=48 A[3][3]地址为48+644=692 2. 设A[9][9]是一个10*10对称矩阵，采用压缩存储方式存储其下三角部分，已知每个元素占用两个存储单元，其第一个元素A[0][0]的存储位置在1000，求下面问题的计算过程及结果： 给出A[4][5]的存储位置。 A[4][5]是上三角部分，所以存在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] [4] 3. 一个稀疏矩阵如图所示，则对应的三元组线性表是什么？其对应的十字链表是什么？ 0 0 2 0 3 0 0 0 0 0 -1 5 0 0 0 0 4. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 16 1 6 6 3 5 4 4 4 3 1 3 12 1 2 2 2 1 6 4 6 ) 1 ( 四. 算法设计 1. 设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。 2. 若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小 值且又是第j列元素中最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存储 矩阵A，试设计一个求该矩阵所有鞍点的算法，并分析最坏情况下的时间复杂度void Saddle(int A[m][n]) //A是m*n的矩阵,本算法求矩阵A中的马鞍点. {int max[n]={0}, //max数组存放各列最大值元素的行号,初始化为行号0; min[m]={0}, //min数组存放各行最小值元素的列号,初始化为列号0; i, j; for(i=0;i {for(j=0;j {if(A[max[j]][j] } for (i=0;i {j=min[i]; //第i行最小元素的列号 if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j]); } } 0 2 0 0 12 0 0 0 30 0 0 0 0 0 4 0 0 60 16 0 0 0 }// Saddle 分析算法，外层for循环共执行m次，内层第一个for循环执行n次，第二个for循环最坏情况下执行m次，所以，最坏情况下的时间复杂度为Ｏ(mn+mm)。 第六章树和二叉树 一. 填空题 1. 树是n（n≥0）结点的有限集合。在一棵空树中有0 个元素；在一棵非空树中，有且仅有一个个根结点，其余的结点分成m（m＞0）个互不相交的集合，每个集合都是根结点的子树。 2. 一棵二叉树的第i（i≥1）层最多有2i-1个结点；一棵有n（n>0）个结点的满二叉树共有(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 左. 右线索标志均为1 5. 由权值为{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）试构造出哈夫曼编码树，并对每个字符进行编码 2）问该字符串的编码至少有多少位。 A: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位。 四. 算法设计 A B F D H C G E 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 4 2. 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 n2 5. 设无向图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算法求最小生成树。