13年电大数据结构1到9章过程性测试习题答案 下载本文

习题解答

else {

qtr = Qs_front ; while (qtr <= Qs_rear) {

printf (“%d”, *qtr); qtr++ ;

} } }

/* 队列非空!*/

3.编写一个算法,它能够取得链式队列首元素的值。

答:取得链式队列首元素的值,只有在队列非空的前途下才有意义。算法编写如下。

Getf_Lq(Lq_front, Lq_rear) {

if (Lq_front == Lq_rear) else {

ptr = Lq_front->Next ; x = ptr->Data ; return (x) ; } }

/* 队列空!*/

/* 队列非空!*/

printf (“The linked queue is empty!”);

4.有五个人顺序坐在一起。问第5个人多少岁,回答说比第4个人大2岁;问第4个人多少岁,回答说比第3个人大2岁;问第3个人多少岁,回答说比第2个人大2岁;问第2个人多少岁,回答说比第1个人大2岁;问第1个人多少岁,回答说是10岁。试给出该递归的公式、结束条件,并编写出相应的递归算法。 答:递归公式为:

age(n)=age(n-1)+2 2<=n<=5

递归的结束条件是: age(1)=10 相应算法为:

Age (n) {

if (n == 1) return (10); else {

x=age(n-1)+2 ; return (x) ; } }

5.将中缀表达式转化为后缀表达式的方法类似于中缀表达式求值。具体地,要开辟一个运算符栈op和一个数组st。在自左至右扫描算术表达式时,遇到操作数就直接顺序存入

- 13 -

习题解答

st;遇到运算符时就与op栈顶元素比较,高则进栈,不高则让栈顶元素出栈,存入st,然后该运算符再次去与新的op栈顶元素比较。最后,在数组st里形成所需要的后缀表达式。试用这种方法,用图示将中缀表达式5+8*3-2转化成为相应的后缀表达式。 答:相应的后缀表达式是583*+2-,其图示如下。

6.语言编译时,总是先将中缀表达式转化成为后缀表达式,然后再计算后缀表达式的值,因为后缀表达式已经去除了括号,没有了运算符的优先级。计算后缀表达式的方法是只开辟一个对象栈ob,当从左往右扫描后缀表达式时,每遇到操作数就让其进入ob栈,每遇到运算符就从ob栈里弹出两个操作数进行当前的计算,并将计算结果进ob栈。该过程直至整个表达式结束。ob栈的栈顶值就是最终结果。试用图示计算后缀表达式583*+2-的值。 答:计算结果为27,其图示如下。

第4章习题解答

一、填空

1.字符串是一种特殊的线性表,特殊在于它的数据元素只能是 字符 ,特殊在于串可以作为一个 整体 参与所需要的处理。 2.空格串是由 空格 组成的串,空串是 不含任何字符 的串,因此空格串和空串不是一个概念。 3.字符串中任意多个 连续 字符所组成的子序列,被称作是这个串的“子串”,这个字符串本身则称为“主串”。 4.我们说两个字符串相等,在计算机内部实际上是通过对相应位置上字符 ASCII 码

- 14 -

习题解答

的比较而得到的结论。 5.设有串s=“I am a teacher”。该串的长度是 14 。 6.设有三个串:s1=“Good”,s2=“Ф”,s3=“bye!”。则s1、s2、s3连接后的结果串应该是 “Good bye! ” 。 7.所谓“数组”,是指n(n>1)个具有 相同 类型的数据的有序集合。 8.矩阵与通常所说的 二维 数组有关。 9.所谓“ 特殊矩阵 ”,是指那些元素在矩阵中的分布具有一定规律性的矩阵;而矩阵中的零元素个数远远多于非零元素的个数,但非零元素的分布却没有规律,这样的矩阵被称为“ 稀疏矩阵 ”。 10.在一个n阶方阵A中,若所有元素都有性质:aij = aji (1≤i, j≤ n),就称其为 对称 矩阵。

二、选择

1.设有两个串s1和s2。求s2在s1中首次出现的位置的操作称为 B 。 A.连接 B.模式匹配 C.求子串 D.求串长

2.有串:“Ф”,那么它的长度是 B 。 A.0 B.1 C.2 D.3 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.设有一个8阶的对称矩阵A,采用以行优先的方式压缩存储。a11为第1个元素,其存储地址为1,每个元素占一个地址空间。试问元素a85的地址是 A 。 A.33 B.30 C.13 D.23 5.一个m*m的对称矩阵,如果以行优先的方式压缩存入内存。那么所需存储区的容量应该是 C 。 A.m*(m-1)/2 B.m*m/2 C.m*(m+1)/2 D.(m+1)*(m+1)/2 6.二维数组M的每个元素含4个字符(每个字符占用一个存储单元),行下标i从1变到5,列下标j从1变到6。那么按行顺序存储时元素M[4][6]的起始地址与M按列顺序存储时元素 B 的起始地址相同。 A.M[3][5] B.M[4][5] C.M[4][6] D.M[5][5] 7.二维数组M中的每个元素占用3个存储单元,行下标i从1变到8,列下标j从1变到10。现从首地址为SA的存储区开始存放A。那么该数组以行优先存放时,元素A[8][5]的起始地址应该是 C 。 A.SA+141 B.SA+180 C.SA+222 D.SA+225 8.设有一个5阶上三角矩阵A,将其元素按列优先顺序存放在一维数组B中。已知每个元素占用2个存储单元,B[1]的地址是100。那么A[3][4]的地址是 A 。 A.116 B.118 C.120 D.122

(分析:把一个上三角矩阵按列优先顺序存放在一个一维数组B中,元素的顺序是: a11a12a22a13?? A[3,4]的地址=100+a34前面的元素个数*2 =100+(前3列的个数+本列a34前面的个数)*2 =100+((1+2+3)+2)*2=116 )

- 15 -

习题解答

三、问答

1.为什么可以把二维数组视为是一种线性结构? 答:实际上,二维数组是一种较为复杂的数据结构,数据元素之间的关系并不是线性的。不过,如果我们把它看作是其每个元素为一维数组的一个一维数组,那么就可以把二维数组视为是线性表的一种推广(因为一维数组即是线性表),因此可以说它的数据元素间的逻辑关系呈现出的是一种线性结构。

2.图4-34(a)所示为一个特殊矩阵A5?5,这种形式的矩阵被称作是“带状矩阵”,因为它的非零元素都分布在以主对角线为中心的一个带状区域里,其他位置上的元素全部为0。可以以行优先的方式,将其压缩存储到一个一维数组里,如图4-34(b)所示。试找出元素下标i、j与存储序号k间的对应关系。

图4-34 带状矩阵

答:压缩存储元素下标i、j与存储序号k间的对应关系是: k = 2*i + j – 2

3.一个稀疏矩阵如图4-35所示。试问,它对应的三元组表是什么?

图4-35 稀疏矩阵示例

答:它所对应的三元组表如下。

四、应用

- 16 -