数据结构习题及答案

《数据结构习题及答案》由会员分享，可在线阅读，更多相关《数据结构习题及答案（18页珍藏版）》请在金锄头文库上搜索。

1、第 1 页 共 18 页答案参见我的新浪博客：http:/ 一1填空题（1）数据的逻辑结构可形式地用一个二元组 B(K，R)来表示，其中 K 是_，R 是_。（2）存储结构可根据数据元素在机器中的位置是否连续分为，。（3）算法的基本要求有，。 （4）度量算法效率可通过，两方面进行。 2简述下列术语：数据 数据元素 数据对象 数据结构 存储结构 数据类型。3. 常用的存储表示方法有哪几种?4.举例说明一下数据结构和算法的关系。5.设有数据逻辑结构为 B=（K，R） ，K=k1，k2，k9r=, ,画出这个逻辑结构的图示，并确定相对于 r 哪些结点是开始结点，哪些结点是终端结点？6.试举一个数据结

2、构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。7.何谓算法？试详述算法设计的目的和算法必须满足的条件。8.编写一个算法，对三个两位数按由大到小的顺序进行排序。描述构造该算法的思维过程。习题二1.如定理 2.1 所描述的，从盒子中往外取球，在 1-4 所给的答案中，哪一个是 i，j，k 对应的值。Red，5，6Blue，5，6Blue，3，Red6，5，Red2如定理 2.1 所描述的，从盒子往外取球，在 1-4 所给的答案中，哪一个是 i,j,k 对应的值。6，7，RedBlue,7,38,2,Red9,Red,13.假设 T1（N）= O（F（N） ） ，T 2（N）= O（F（N

3、） ） ，说明下列哪一个正确？T 1 (N)+ T2 (N) = O(F(N)T 1 (N)- T2 (N) = O(F(N)T 1 (N)/ T2 (N) = O(1)T 1 (N) = O(T2 (N)4.假设两个算法的时间复杂度分别为 T1（N）=O（N）和 T2（N）=O（N 2） ，说明下列哪一个第 2 页 共 18 页答案参见我的新浪博客：http:/ 1（N）* T 2（N）= O（N 3）T 1（N）+ T 2（N）= O（N 2）T 2（N）/ T 1（N）= O（N）T 2（N）- T 1（N）= O（N）5.基于定理 2.2 的描述，为什么不能充分获得一个最大连续子序列之

4、和的次平方运行时间？6.读者思考：由算法 2.1 到算法 2.2 的改进过程中，时间复杂度由三次降到二次，那么算法的空间复杂度有没有变化？这种改进是不是无条件的？7.将下列各式组合成与 Big-Oh 相等的函数。x2，x 2 + x，x 2 - x，x 3/( x 1 )8确定以下各式的等价 Big-Oh 函数(估算)。x4/(x+1),x3-x2，x 2+x39.程序 A 和程序 B 经分析，有不超过 150NlogN 和 N2的最坏情况下的运行时间，如可能，分别回答下列各问题：当 N 值很大时（N 10,000）,哪个程序对运行时间有保证？N 值较小（N next=(linklist)ma

5、lloc(size of (lnode);p=p-next;p-data=i*2-1;p-next=null;for (i=4;i=1;i- -；) insert_linklist（l;i+1;i*2）;for(i=1;i=0g(m-1,2n) m0,n=0g（ m， n） =14. 分别在栈和队列（至少含有 3 个结点）中实现删除紧邻栈顶或队头的结点，并用P 返回其值。15. 设将整数 1，2，3，4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为 Push(1), Pop(),Push(2),Push(3), Pop(), Pop(

6、),Push(4), Pop( ),则出栈的数字序列为何(这里 Push(i)表示 i 进栈，Pop( )表示出栈)? (2) 能否得到出栈序列 1423 和 1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的 24 种排列中，哪些序列是可以通过相应的入出栈操作得到的。 16. 回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)。第 6 页 共 18 页答案参见我的新浪博客：http:/ 判断题 (判断下列各题是否正确，若正确在（）内打“” ，否则打“”)(1)

7、 （ ）如果两个串含有相同的字符，则说明它们相等。(2) （ ）如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(3) （ ）串的模式匹配 BF 算法的时间复杂度在最坏情况下为 O（nm） ，因此此算法没有实际使用价值。(4) （ ）设有两个串 p 和 q，其中 q 是 p 的子串，把 q 在 p 中首次出现的位置作为子串 q 在 p 中的位置的算法称为匹配。(5) （ ）KMP 算法的最大特点是指示主串的指针不需回溯。2. 选择题（请在选项 A，B，C，D，E 选择正确答案）(1) 串是（ ）A. 少于一个字母的序列 B. 任意个字母的序列C. 不少于一个字符的序列 D.

8、 有限个字符的序列(2)设字符串 s1=ABCDEFG,s2=PQRST，T，sub1，sub2 为空串。则运算s=Concation(T,SubString(sub1,s1,2,SubLength(s2),SubString(sub2,s1,SubLength(s2),2)后的串 T 的值为（ ）A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF E. BCQR (3) 串的长度是（ ）A. 串中不同字母的个数 B. 串中不同字符的个数C. 串中所含字符的个数，且大于 0 D. 串中所含字符的个数(4) 若某串的长度小于一个常数，则采用（ ）存储方式最为节省空间

9、。A. 链式 B. 堆结构 C. 顺序(5) 设有两个串 p 和 q ,求 q 在 p 中首次出现的位置的运算（ ）A. 连接 B. 模式匹配 C. 求子串 D. 求串长 (6) 串的联结运算不满足（ ）A. 分配律 B. 交换律 C. 结合律 3 空白串与空串有何区别？字符串中的空白符号有何意义？4 假定串采用块链接表示，试写出删除一个子串的算法。5 比较串的三种存储方式的优点和缺点。6 已知：s=xyz* ，t=(x+y)*z。试利用联接、求子串和置换等基本运算，将 s 转换为t。7 试分别写出算法 insert(a,i,b)和算法 delete(a,b)。其中，insert(a,i,b)

10、将串 b 插入在串 a 中位置 i 之后；delete(a,b) 将串 a 中的子串 b 删掉。习题六判断题 (判断下列各题是否正确，若正确在（）内打 “” ，否则打“”)(1) （ ）数组是同类型值的集合。(2) （ ）数组是一组相继的内存单元。(3) （ ）数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树型的。(4) （ ）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。第 7 页 共 18 页答案参见我的新浪博客：http:/ （ ）使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。(6) （ ）广义表是由零或多个单元素或子表所组成

11、的有序列，所以广义表可能为空表。(7) （ ）线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。单选题 (请从下列 A、B、C、D、E、F 选项中选择一项)(1) 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a 11为第一个元素，其存储地址为 1，每个元素占 1 个地址空间，则 a85的地址为（ ）A. 13 B. 33 C. 18 D. 40 (2) 一个 nn 的对称矩阵，如果以行或列为主序存入内存，则其容量为 （ ）A. nn B. nn/2 C. n(n+1)/2 D. (n+1)(n+1)/2 E. (n-1)n/2 F.

12、n(n-1) (3) 二维数组 a 的每个元素是由 6 个字符组成的串，行下标 i 的范围从 08，列下标 j 的范围是从 110。从供选择的答案中选出正确答案填入下列关于数据存储叙述中的( )内。 存放 a 至少需要( )个字节。A. 90 B. 180 C. 240 D. 270 E. 540 a 的第 8 列和第 5 行共占( ) 字节。A. 108 B. 114 C. 54 D. 60 E. 150 若 a 按行存放，元素 a8，5的起始地址与当 a 按列存放的元素( ) 的起始地址一致。A. a8,5 B. a3,10 C. a5,8 D. a0,9 (4) 已知广义表 LS=(a,

13、(b,c,d),e),运用 HEAD 和 TAIL 函数取出 LS 中单元素 b 的运算是（ ） 。A. HEAD（HEAD（LS） ） B. TAIL（HEAD（LS ） ） C. HEAD（HEAD（TAIL（LS） ） ） D. HEAD（TAIL（LS ） ） (5) 已知广义表 A=(a,b,c),(d,e,f),从 A 中取出单元素 e 的运算是（ ） 。A. TAIL（HEAD（A） ） B. HEAD（TAIL（A） ） C. HEAD（TAIL（TAIL （HEAD（A ） ） ） ） D. HEAD（TAIL（HEAD（TAIL（A ） ） ） ）3 假设在树中，结点 x

14、是结点 y 的双亲时,用(x,y)来表示树边.已知一棵树边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形表示法出此树，并回答下列问题：(1)哪个是根结点? (2) 哪些是叶结点? (3)哪个是 g 的双亲? (4) 哪些是 g 的祖先? (5)哪些是 g 的孩子? (6) 哪些是 e 的子孙? (7)哪些是 e 的兄弟 ?哪些是 f 的兄弟? (8)结点 b 和 n 的层次各是多少? (9)树的深度是多少? (10)以结点 c 为根的子树的深度是多少?(11) 树的度数是多少?4一棵度为 2 的有序树与一棵二叉树有何区别?5一个深度为 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余各层上每个结点都有 k 棵非空子树。如果按层次顺序(同层自左至右)从 1 开始对全部结点编号，问：(1)各层的结点数目是多少?(2)编号为 i 的结点的双亲结点