数据结构习题(c语言版).doc

习题1 绪论一、基本内容 数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；算法设计的基本要求以及从时间和空间角度分析算法的方法。二、要点：1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构 2理解算法五个要素的确切合义： 动态有穷性(能执行结束)； 确定性(对于相同的输入执行相同的路径)；有输入；有输出；可行性(用以描述算法的操作都是可以通过已经实现的基本的运算执行有限次来实现的)。3. 掌握计算语句频度和估算算法时间复杂度的方法。1.1 选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 、数据信息在计算机中的 以及一组相关的运算等的课程。 A操作对象 计算方法 逻辑结构 数据映象 A存储结构 关系 运算 算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系3. 在数据结构中，从逻辑上可以把数据结构分成 。A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构4. 算法分析的目的是 ，算法分析的两个主要方面是 。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性5. 计算机算法指的是 ，它必具备输入、输出和 等五个特性。 A. 计算方法 B. 排序方法C. 解决问题的有限运算序列 D. 调度方法 A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1数据结构的三个要点是 数据元素的逻辑结构、数据在计算机中的存储结构和数据的运算。1. 数据逻辑结构包括 线性结构、树形结构、图形结构三种类型，树形结构和图形结构合称为 非线性结构。2. 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有1 个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有 1 个后续结点。3. 在树形结构中，树根结点 没有 前驱结点，其余每个结点有且只有 1 个直接前驱结点，叶子结点 没有 后续结点，其余每个结点的直接后续结点可以 任意多个 。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个。5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多 关系，图形结构中元素之间存在 多对多 关系。6. 算法的五个重要特性是有穷性、确定性、可行性、输入、输出。7. 分析下面算法（程序段），给出最大语句频度：n2 ， 时间复杂度：. O (n2)。for (i=0;in;i+) for (j=0;jn; j+) Aij=0;8. 分析下面算法（程序段），给出最大语句频度：n (n+1)/2 ， 时间复杂度：. O (n2)for (i=0;in;i+) for (j=0; ji; j+)Aij=0;9. 分析下面算法（程序段），最大语句频度：n3 ， 时间复杂度：. O (n3)s=0;for (i=0;in;i+) for (j=0;jn;j+) for (k=0;kn;k+) s=s+Bijk;sum=s;10. 分析下面算法（程序段）给出最大语句频度：n ， 时间复杂度：. O (n) i=s=0;while (sn) i+; s+=i; 11. 分析下面算法（程序段）给出最大语句频度：log2n， 时间复杂度：. O (log2n )i=1;while (i=n) i=i*2;1.3简答题1、试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。 每个记录( 有姓名，学号，成绩等字段) 就是一个结点，对于整个表来说，只有一个开始结点( 它的前面无记录) 和一个终端结点( 它的后面无记录) ，其他的结点则各有一个也只有一个直接前趋和直接后继( 它的前面和后面均有且只有一个记录) 。这几个关系就确定了这个表的逻辑结构。 那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。2、 常用的存储表示方法有哪几种? 常用的存储表示方法有两种: 顺序存储方法和链接存储方法 3、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0 while(in) k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 这个函数是按线性阶递增的 （2) i=0; k=0; dok=k+10*i; i+; while(i1 while (x=(y+1)*(y+1) y+; T(n)=n 1/2 T(n)=O(n 1/2) 最坏的情况是y=0，那么循环的次数是n 1/2 次，这是一个按平方根阶递增的函数。 (4) x=91; y=100; while(y0) if(x100) x=x-10;y-; else x+; T(n)=O(1) 这个程序总共循环运行了1000次，但是我们看到n没有? 没有。这段程序的运行是和n无关的，只是一个常数阶的函数。4、算法的时间复杂度仅与问题的规模相关吗? No, 事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。 我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。习题2 线性表一、基本内容 线性表的逻辑结构定义和各种存储结构的描述方法；在线性表的两类存储结构(顺序的和链式的)上实现基本操作；一元多项式的表示及相加。二、学习要点 1了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2熟练掌握这两类存储结构的描述方法，如一维数组中一个区域的上、下界和长度之间的变换公式，链表中指针P和结点p的对应关系(结点p一next是结点P的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。 3熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。 4熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。5从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。2.1 单项选择题1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_ _。 A. 110 B. 108 C. 100 D. 1202. 线性表的顺序存储结构是一种_ _的存储结构，而链式存储结构是一种_ _的存储结构。A随机存取 B索引存取 C顺序存取 D散列存取3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_ _。A. 正确 B. 不正确4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_ _。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续或不连续都可以5. 在以下的叙述中，正确的是_ _。线性表的顺序存储结构优于链表存储结构线性表的顺序存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构优于顺序存储结构6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法_ _。A. 正确 B. 不正确7. 不带头结点的单链表head为空的判定条件是_。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head!=NULL8. 带头结点的单链表head为空的判定条件是_。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head!=NULL9. 非空的循环单链表head的尾结点（由p所指向）满足_。A. p-next= =NULL B. p= =NULLC. p-next= =head D. p= =head 10. 在双向循环链表的p所指结点之后插入s所指结点的操作是_。A. p-right=s; s-left=p; p-right-left=s; s-right=p-right;B. p-right=s; p-right-left=s; s-left=p; s-right=p-right;C. s-left=p; s-right=p-right; p-right=s; p-right-left=s;D. s-left=p; s-right=p-right; p-right-left=s; p-right=s;11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;B. q-next=s; s-next=p; C. p-next=s; s-next=q;12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s-next=p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=p-next; p=s; C. p-next=s; s-next=p;13. 在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p-next= p-next-next； B. p= p-next; p-next= p-next-next；C. p-next= p-next; D. p= p-next-next；14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。A. n B. n/2 C. (n-1)/2 D. (n+1)/215. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_ _。A. O(1) B. O(n) C. O (n2) D. O (nlog2n)16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是_ _。A. O(1)） B. O(n) C. O (n2) D. O (n*log2n)2.2 填空题（将正确的答案填在相应的空中）1. 对于顺序表（采用顺序存储结构的线性表） (a1，a2，, an)，设L表示一个元素占用的存储单元个数，LOC(ai)表示线性表第i个元素的地址，已知第1个元素的地址为LOC(a1)，则LOC(ai)= 2. 向一个长度为n的顺序表的第i个元素（1in+1）之前插入一个元素时，需向后移动_ n-i+1 _个元素。3. 向一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动_ n-i _个元素。4. 单链表可以看做_线性表_的链式存储表示。5. 在双链表中，每个结点有两个指针域，一个指向_前驱结点_，另一个指向_后继结点 _。6.带头结点的单链表中，除头结点外，任一结点的存储位置是在其前驱结点的指针域中。7.单链表中引入头结点的作用是在链表的第一个位置上行插入和删除等操作时无须进行特殊处理8. 一个长为n的线性表，其排序时间性能最优为O(n*Log2n)。9. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：q=head;while (q-next!=p) q=q-next;s= (struct node *)malloc(sizeof(struct node); s-data=e;q-next= s ; /填空s-next= p ; /填空10. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p-next;p-next= _ q-next _; /填空free( q _) ; /填空11. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next= p-next 和p-next=_s_的操作。12. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是_ O (1) _；在给定值为x的结点后插入一个新结点的时间复杂度是O (n) _。13.第二章作业题习题3 栈和队列一、基本内容栈和队列的结构特点；在两种存储结构上如何实现栈和队列的基本操作以及栈和队列在程序设计中的应用。 二、学习要点 1. 掌握栈和队列的特点。 2熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。 3熟练掌握循环队列的基本操作实现算法持别注意队满和队空的描述方法。 4理解递归算法执行过程中栈的状态变化过程。3.1 单项选择题1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是_。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_。 A. i B. n=i C. n-i+1 D. 不确定3. 栈结构通常采用的两种存储结构是_。A. 顺序存储结构和链式存储结构 B.散列方式和索引方式C.链表存储结构和数组 D.线性存储结构和非线性存储结构4. 判定一个顺序栈ST（最多元素为m0）为空的条件是_。A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-15. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是_。A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-16. 栈的特点是_B_，队列的特点是_A_。 A. 先进先出 B. 先进后出7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_ _。(不带空的头结点)A. HSnext=s;B. snext= HSnext; HSnext=s;C. snext= HS; HS=s;D. snext= HS; HS= HSnext;8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行_ _。(不带空的头结点) A. x=HS; HS= HSnext; B. x=HSdata;C. HS= HSnext; x=HSdata; D. x=HSdata; HS= HSnext;9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是_ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，110. 判定一个循环队列QU（最多元素为m）为空的条件是_。A. rear - front= =m B. rear-front-1= =mC. front= = rear D. front= = rear+111. 判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是_。A. (rear+1)% Maxsize = =frontB. rear-front-1= =m C. front= =rear D. front= = rear+112. 循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_。A. (rear-front+m)%m B. rear-front+1C. rear-front-1 D. rear-front13. 栈和队列的共同点是_。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点3.2 填空题（将正确的答案填在相应的空中）1. 向量、栈和队列都是 线性_结构，可以在向量的_任何_位置插入和删除元素；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和_队首_删除元素。3. 向栈中压入元素的操作是_先移动栈顶指针，后存入元素_。4. 对栈进行退栈时的操作是_先取出元素，后移动栈顶指针_。5. 在一个循环队列中，队首指针指向队首元素的_前一个位置_。6. 从循环队列中删除一个元素时，其操作是_先移动队首元素，后取出元素_。7. 在具有n个单元的循环队列中，队满时共有_ n-1_个元素。8. 一个栈的输入序列是12345，则栈的输出序列43512是_不可能的_。9. 一个栈的输入序列是12345，则栈的输出序列12345是_可能的_。10.想象六辆列车位于图中堆栈的输入一边，列车编号为123456，按此顺序开进堆栈，且可在任意时刻开走，则能否得到32564l出站序列?能否得到154623出站序列?在可能的情况下，说明如何实现。能得到325641实现过程为；Push，push，push，pop，pop，Push，push，pop，push，pop，pop，pop。不能得到154623。11. 设循环队列存放在向量sq.dataom中，则队头指针sq.front在循环意义下的加1操作可用模运算表示为 (sq.front+1) MOD m 。若用牺牲一个单元的办法来区分队满和队空条件，则队满条件可表示为 (sq.rear+1) MOD msq.front 。12. 设顺序栈存放在一维数组sM，栈底位置是m-1，则栈空条件 top=0 ，栈满条件是 top=m 。13.循环队列只有下溢，没有上溢。(错误)14队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（正确）初始状态a4a5a66012345endstart15.栈有哪几种不同的存储结构?请分别画出在这些存储结构中元素a，b，c，J依次进栈后堆栈的状态。链栈和顺序栈17.循环队列入队、出队算法如下：321入队算法：void en_cycque(int sq,int start,int end,int x) if(end+1)%M)=start) printf(overflow); else end=(end+1)%M; sqend=x; 出队算法：int dl_cycque(int sq,int start,int end,int *q) if(start=end) return(0); else start=(start+1)%M; *q=sqstart; return(1); 队列某个时刻的初始状态如图所示。1).在初始状态上，画出a7、a8和a9入队后的状态图，2).在初始状态上，画出a4、a5和a6出队后的状态图。习题4 串一、基本内容 串的 定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现。二、学习要点 1熟悉串的基本操作的定义 2掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3. 掌握串的堆存储结构以及在其上实现串操作的基本方法。4.1 单项选择题1以下叙述中正确的是 。A.串是一种特殊的线性表 B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串2空串与空格串是相同的，这种说法_。A. 正确 B. 不正确3串是一中特殊的线性表，其特殊性体现在_。A. 可以顺序存储 B. 数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符4设有两个串p和q，求q在p中首次出现的位置的运算称作_。A. 连接 B. 模式匹配C. 求子串 D. 求串长5设串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)的结果串是_。A. BCDEF B. BCDEFGC. BCPQRST D. BCDEFEF6设串的长度为n，则它的子串个数为 。A.nB.n(n+1)C.n(n+1)/2D.n(n+1)/2+14.2 填空题（将正确的答案填在相应的空中）1串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构2两个串相等的充分必要条件是_两个串的长度相等且对应位置的字符相同_。3空串是_零个字符的串_，其长度等于_零_。4空格串是_由一个或多个空格字符组成的串_，其长度等于_其包含的空格个数_。5设s=IAMATEACHER,其长度是_14_。6串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。（）7如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）4.3 算法设计题写一个递归算法来实现字符串逆序存储，要求不另设存储空间。 void reverse(char arr)char ch; int i=1;doch=getchar(); reverse(arr); arri=ch; i+; while(ch!=#&i0）个结点的满二叉树共有_2log2n+1-1 _个叶子和_ 2log2n+1 1_个非终端结点。8. 结点最少的树为_只有一个结点的树 _，结点最少的二叉树为_空的二叉树_。9. 现有按中序遍历二叉树的结果为abc，问有_5_种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_。iaedbchHf图6.9 一棵二叉树gia图6.8 树形5种aaaacccccbbbbbb10. 由如图6.9所示的二叉树，回答以下问题： 其中序遍历序列为_dgbaechif_； 其前序遍历序列为_abdgcefhi_； 其后序遍历序列为_gdbeihfca_；11设有n个结点的完全二叉树顺序存放在向量aln中，对任一结点ai，若ai有父母，则其父母是 ai/2 。若ai有左子女，则左子女为 a2i ，若ai有右子女，则右子女 a2i+1 ；i值最大的分支结点是 an/2 。12设T是非空的二叉树，若T的先序序列和中序序列相同，则T的形态是所有左子树为空的二叉树，若T的先序序列和后序序列相同，则T的形态是 所有右子树为空的二叉树 ；若