《计算机软件技术基础》课后题答案 - 图文(8)

栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 # # #- #- #-* #-* #- # #+ #+( #+( #+(+ #+(+ #+ #+/ #+/ #+ # 栈 9 9 92 92 924 98 1 1 1 18 18 181 19 19 193 13 4 符 9 - 2 * 4 + ( 8 + 1 ) / 3 # 5．链栈中为何不设置头结点?

答：因为链栈只在链表头插入和删除结点，不可能在链表中间插入或删除结点，算法实现很简单，所以一般不设置头结点。

第四节 数组

36

一、选择题

1．数组通常具有的两种基本操作是( )。

A．建立和删除 B．索引和修改 *C．查找和修改 D．查找和索引 2．二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是( )。 *A．1208 B．1212 C．1368 D．1364 3．对矩阵压缩存储是为了( )。

A．方便运算 *B．节省空间 C．方便存储 D．提高运算速度 4．稀疏矩阵的压缩存储方法通常有两种，即( )。

A．二元数组和三元数组 B．三元组和散列 *C．三元组和十字链表 D．散列和十字链表 二、判断题

√ 1．数组是同类型值的集合。 √2．数组是一组连续的内存单元。

╳3．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

╳4．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

√ 5．使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。 三、填空题

1．二维数组A[10， 20]采用列序为主序方式存储，每个元素占一个存储单元，并且A[1，1]的存储地址是200，则A[6，12]的地址是___315___。

2．有一个10阶对称矩阵A采用压缩存储方式(以行序为主序方式)存储其下三角元素，且第一个元素A[0，0]的存储地址为1，则A[4，5]的地址是__14__，

37

A[8，3]的地址是___31_。

3．下三角矩阵A[N,N]的下三角元素已压缩到一维数组S[N(N+1)／2]中，若按行序为主序存储，则A[i，j]对应的S中的存储位置是__I(I-1)/2+j(i≥j),n(n+1)/2+1(I

1．假设有二维数组A[6,8]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始地址(基地址)为1000，计算：(1)数组A的容量。(2)按行优先方式存储时，元素A[1，4]的地址。(3)按列优先方式存储时，元素A[4,7]的地址。

答：(1)数组A的容量:6*8*6=288。(2)按行优先方式存储时，元素A[1，4]的地址=1000+3*6=1018。(3)按列优先方式存储时，元素A[4,7]的地址=1000+(6*6+3)*6=1234。

2．设有三对角矩阵A[n，n]，将其三条对角线上的元素逐行存放于数组B[3n-3]中，使得B[k]=A[i,j]，求： (1)用i，j表示k的下标变换公式。 (2)用k表示i，j的下标变换公式。

答：(1) k=2i+j-3 (2) I=(k+1)/3+1，j=k-2i+3。 3．画出图5-2所示的稀疏矩阵A的三元组表和十字链表。

答：

row col e 1 2 4 1 2 5

38

2 3 5 5

3 5 1 3 6 8 4 9 4．用三元组表表示图5-3所示的稀疏矩阵的转置矩阵。

答：

row col e 1 2 3 4 5 2 1 3 4 2 2 1 4 5 3 五、算法设计题

1．设计将数组A[n]中的所有奇数移到所有偶数之前的算法。要求不另外增加存储空间且时间复杂度为O(n)。

算法采用两个变量i和j分别表示数组的开头和末尾元素，同时向中间搜索： void change(int a[n]) { I=0; j=n-1; while (I

{while (a[I]%2!=0&&I

39

if (I

{c=a[I];a[I]=a[j];a[j]=c; I++;j--;} } }

*2．当稀疏矩阵A和B均以三元组作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组C中。 略。 第五节 树

(树根结点的高度为1) 一、选择题

1．以下说法错误的是( )。

*A．树形结构的特点是一个结点可以有多个直接前驱 B．线性结构中的一

个结点至多只有一个直接后继 C．二叉树与树是两种不同的数据结构 D．树(及一切树形结构)是一种“分支层次’结构 2．以下说法错误的是( )。

A．二叉树可以是空集 *B．二叉树的任一结点都有两棵子树 C．二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 3．以下说法错误的是( )。

A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 *D．在二叉链表上，求双亲操作的时间性能很好

4．以下说法错误的是( )。

A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有

40