数据结构精品课程 习题作业 的长度：那么执行操作SubConcat(T,SubString(Sub1,S,2,StrLength(S2.SubString(Sub2,SL,StrLength(S2,2m后，T 是（) (A)BCDEF (B)BCDEFG (C)BCPORST (D)BCDEFEF 三、问答题 1.下列每对术语的区别是什么？ (1)串变量和串常量： (2)主串和子中： (3)串名和串值 2。顺序串静态分配和动态分配的特点分别是什么？ 3.设串S="Iam a student" T="good”,Q='worker (I)SubString(Sub.S.8.刀操作后，Sb的结果是什么 (2)SubString(Sub.T2,1)作后，Sub的结果是什么？ (3)StrReplace(S,&,7,Q)操作后，S的结果是什么？ (4)StrConcat(,SubString(Sub1,S,6,2.StrConcat(B,T.SubString(Sub2,S,7,8操f作后，A的结果是什么g 4.已知串S="(yz+,T="(x+z内y",利用StrConcat、SubString和StrReplace操作如何将S转化为T? 5.下列串的nct函数值是什么？ （1T=mah, (3)T="aaabcaab" (4)T=abcaabbabcabaacbacba". 四、算法设计题 1.试设计一个算法：将子串T插入主串S第pOs个位置上. 2.试设计一个算法：除申S中第0s个字符开始的t个字符。 3.试设计一个算法：用子串T替换主串s中第个字符开始m个字符枸成的子串。 4.试设计一个算法：求解串S和T的最长公共子申 5.如果一个文本串使用事先给定的字母映射表进行加密。例如，设字母映射表如图41山所示 n g=qt c ob m u h e 1 x p d ax f y:vr s3 图411字母映射表 则串enryp"被加密为kzwsdf.试设计一个算法 ()将输入的文本串进行加密后输出： (2)将输入的已加密的文本串进行解密后输出】 第5章数组和广义表 一、填空题 6
数据结构精品课程 习题作业 6 的长度；那么执行操作 SubConcat(T, SubString(Sub1, S1, 2, StrLength(S2)), SubString(Sub2, S1, StrLength(S2), 2)))后，T 是（ ）。 (A) BCDEF (B) BCDEFG (C) BCPQRST (D) BCDEFEF 三、问答题 1．下列每对术语的区别是什么？ （1）串变量和串常量； （2）主串和子串； （3）串名和串值。 2．顺序串静态分配和动态分配的特点分别是什么？ 3．设串 S="I am a student"，T="good"，Q="worker"： （1）SubString(Sub, S, 8, 7)操作后，Sub 的结果是什么？ （2）SubString(Sub, T, 2, 1) 作后，Sub 的结果是什么？ （3）StrReplace(S, 8, 7, Q)操作后，S 的结果是什么？ （4）StrConcat(A, SubString(Sub1, S, 6, 2), StrConcat(B, T, SubString(Sub2, S, 7, 8)))操作后，A 的结果是什么？ 4．已知串 S="(xyz)+*"，T="(x+z)*y"，利用 StrConcat、SubString 和 StrReplace 操作如何将 S 转化为 T？ 5．下列串的 next 函数值是什么？ （1）T="aaab"； （2）T="abcabaa"； （3）T="aaabcaab"； （4）T="abcaabbabcabaacbacba"。 四、算法设计题 1．试设计一个算法：将子串 T 插入主串 S 第 pos 个位置上。 2．试设计一个算法：删除串 S 中第 pos 个字符开始的 t 个字符。 3．试设计一个算法：用子串 T 替换主串 S 中第 n 个字符开始 m 个字符构成的子串。 4．试设计一个算法：求解串 S 和 T 的最长公共子串。 5．如果一个文本串使用事先给定的字母映射表进行加密。例如，设字母映射表如图4-11所示： 图 4-11 字母映射表 则串"encrypt"被加密为"tkzwsdf"。试设计一个算法： （1）将输入的文本串进行加密后输出； （2）将输入的已加密的文本串进行解密后输出。 第5章 数组和广义表 一、填空题
数据结构精品课程 习题作业 1,数组通常只有两种基本运算：()和()。这决定了数组通常采用()结构来实现存储。 2.二维数组A中行下标从10到20列下标从5到10.如果按行优先存储，每个元素占4个存储单元，AN10I5) 的存储地址是1000，则元素A1510)的存储地址是(). 3.设有一个10阶的对称矩阵A,如果采用压缩存储，A0O为第一个元素，其存储地址为LOC(0小，每个元素 的长度是1个字节，则元素A8[5]的存饮地址为()。 4.广义表LSa,(b.c以(@，其长度是()，深度是()表头是()。表尾是()。 5.广义表LSa,b,c,d.e,如果采用函数GetHead和GetTail取出LS中的原子b,则运算是()。 二、选坪题 1.将数组称为随机存取结构是因为()。 (A数组元素是随机的 (B)对数组任一元素存取时间相等 (C随时可以对数组进行访问 D)数组的存储结构是不定 2.二雏数组A的每个元素是8个学节组成的双精度实数，行下标的范围是07刀，列下标的范围是0-9列，则存放 A至少需要《)个字节。 (A80 (B)144 (C)504 (D)640 3.对特殊矩阵采用压缩存储的目的主要是为了()。 (A)表达变得简单 (B)对矩阵元素的存取变得简单 D)减少不必要的存储空间 (A)0 B)(O) (C(0.0) ①)0.0.0) 5.下面的说法中，不正确的是()， (A)广义表是一种多层次的结构 B)广义表是一种非线性结构 (©广义表是一种共享结构 D)广义表是一种递归 三、问答题 1.特殊矩阵和稀疏矩陈哪一种压缩存储后会失去随机存取的功能？为什么？ 2.数组、广义表与线性表之何有什么样的关系？ 3.设一个二维 组A56的每个元素占4个字节，已知L0C(am10O0,那么A共占多少个字节？A的终端 点as的起始地址是多少？当按行和按列优先存储时，2s的起始地址分别为多少？ 4.分别画出下列广义表的图形表示： (1)A(a.B(b.d).C(e.B(b.d).L(C.g (2)A(a,B(b.A)) 5.下列广义表运算的结果是什么 (1)GetHead(GetTail(((a.b).(c.d).(e.f)))) (2)GetTail(GetHead(((a,b),(c.d)(e,f)))) (3GetHead(GetTail(GetHead((ab).) (4)GetTail(GetHead(GietTail (((ab) (5)GetTail(GetTail(GetHead (((a,b).(e,f))))) 四、算法设计题 .如果在矩阵A中存在一个元素a,(0≤i≤n,0j≤m-1),该元素是第i行元素中最小值且又是第j列元素中 最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组常规存储矩阵A,试设计一个算法：求解该矩阵的所有 马撒点。 2.已知两个x的对称矩阵按压缩存储方法存储在一维数组A和B中，试设计一个算法：求解对称矩阵的乘积 3.试设计一个算法：创建稀疏矩阵的十字链表， 4.试设计一个算法：求解一个广义表所拥有的原子结点个数 7
数据结构精品课程 习题作业 7 1．数组通常只有两种基本运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。 2．二维数组 A 中行下标从 10 到 20，列下标从 5 到 10，如果按行优先存储，每个元素占 4 个存储单元，A[10][5] 的存储地址是 1000，则元素 A[15][10]的存储地址是（ ）。 3．设有一个 10 阶的对称矩阵 A，如果采用压缩存储，A[0][0]为第一个元素，其存储地址为 LOC(a00)，每个元素 的长度是 1 个字节，则元素 A[8][5]的存储地址为（ ）。 4．广义表 LS=((a), (((b), c)), (d))，其长度是（ ），深度是（ ），表头是（ ），表尾是（ ）。 5．广义表 LS=(a, (b, c, d), e)，如果采用函数 GetHead 和 GetTail 取出 LS 中的原子 b，则运算是（ ）。 二、选择题 1．将数组称为随机存取结构是因为（ ）。 (A) 数组元素是随机的 (B) 对数组任一元素存取时间相等 (C) 随时可以对数组进行访问 (D) 数组的存储结构是不定 2．二维数组 A 的每个元素是 8 个字节组成的双精度实数，行下标的范围是[0~7]，列下标的范围是[0~9]，则存放 A 至少需要（ ）个字节。 (A) 80 (B) 144 (C) 504 (D) 640 3．对特殊矩阵采用压缩存储的目的主要是为了（ ）。 (A) 表达变得简单 (B) 对矩阵元素的存取变得简单 (C) 去掉矩阵中的多余元素 (D) 减少不必要的存储空间 4．如果广义表 LS 满足 GetHead(LS)=GetTail(LS)，则 LS 为（ ）。 (A) () (B) (()) (C) ((), ()) (D) ((), (), ()) 5．下面的说法中，不正确的是（ ）。 (A) 广义表是一种多层次的结构 (B) 广义表是一种非线性结构 (C) 广义表是一种共享结构 (D) 广义表是一种递归 三、问答题 1．特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能？为什么？ 2．数组、广义表与线性表之间有什么样的关系？ 3．设一个二维数组 A[5][6]的每个元素占 4 个字节，已知 LOC(a00)=1000，那么 A 共占多少个字节？A 的终端结 点 a45的起始地址是多少？当按行和按列优先存储时，a25 的起始地址分别为多少？ 4．分别画出下列广义表的图形表示： （1）A(a, B(b, d), C(e, B(b, d), L(f, g))) （2）A(a, B(b, A)) 5．下列广义表运算的结果是什么？ （1）GetHead(GetTail(((a, b), (c, d), (e, f)))) （2）GetTail(GetHead(((a, b), (c, d), (e, f)))) （3）GetHead(GetTail(GetHead (((a, b), (e, f))))) （4）GetTail(GetHead(GetTail (((a, b), (e, f))))) （5）GetTail(GetTail(GetHead (((a, b), (e, f))))) 四、算法设计题 1．如果在矩阵 A 中存在一个元素 aij（0≤i≤n-1，0≤j≤m-1），该元素是第 i 行元素中最小值且又是第 j 列元素中 最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组常规存储矩阵 A，试设计一个算法：求解该矩阵的所有 马鞍点。 2．已知两个 n×n 的对称矩阵按压缩存储方法存储在一维数组 A 和 B 中，试设计一个算法：求解对称矩阵的乘积。 3．试设计一个算法：创建稀疏矩阵的十字链表。 4．试设计一个算法：求解一个广义表所拥有的原子结点个数