1、南京晓庄学院数据结构题库参考答案数据结构与算法习题册（课后部分参考答案）数据结构与算法课程组第一章 绪论一. 填空题1. 从逻辑关系上讲，数据结构的类型主要分为 集合 、线性结构、树结构和 图结构。2. 数据的存储结构主要有 顺序存储和 链式存储 两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素 和 数据元素之间的关系 。3. 算法具有五个特性，分别是 有穷性 、 确定性、可行性、 输入 、 输出 。4. 算法设计要求中的健壮性指的是 算法在发生非法操作时可以作出处理的特性。二. 选择题1. 顺序存储结构中数据元素之间的逻辑关系是由 C 表示的，链接存储结构中的数据元素之间的逻辑
2、关系是由 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+; w
3、hile(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个结点从小到大排序
4、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)若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线
5、性表中的元素。(2)如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。(3)描述一个城市的设计和规划。 应选用顺序存储结构。很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 应选用链式存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 应选用链式存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。五. 算法设计1. 已知数组An中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(
6、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;/
7、*插入成功*/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，输出序
8、列的第一个元素是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. 栈可以作为实现过程调用的
9、一种数据结构。 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).
10、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) S
11、tack 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.
12、 试写一个判别表达式中开、闭括号是否配对出现的算法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; b
13、reak; 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);
14、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
15、可以顺序存储 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”，
16、其子串的数目是（ 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,i
17、nt 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
18、+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),
19、 (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是一个对称矩阵，为了节省存储，将其下三角部分按行序存放
20、在一维数组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
21、偏移量为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
22、，A 8 5 或 A 9 43. 一个稀疏矩阵如图所示，则对应的三元组线性表是什么？其对应的十字链表是什么？4. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。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
23、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的结点，该二叉树的结点数可能达到的最大值
24、是 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，则其左分支
25、下的子孙的最大层次为（ 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）试构造出哈夫曼编码树，并对每个字符进行编码2）问该字符串的编码至少有多少位。
