数据结构第五章课后答案

第五章 练习

1. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A[9,9]在B中的存储位置k=_______。（注：矩阵元素下标从1开始）。

2. 三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]

的地址是_______。(设a[0][0][0]的地址是1000,数据以行为主序方式存储)。

3. 假设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000 (2)a1111 (3)a3125 (4) a8247

4. 按高下标优先存储方式（最右的下标为主序），顺序列出数组A[2][2][3][3]中所有元素

aijkl,列出aijkl的序列。 5. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 6. 求下列广义表操作的结果 GetHead 【(p,h,w)】 GetTail 【(b,k,p,h)】 GetHead 【((a,b),(c,d))】 GetTa

第五章 练习

1. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A[9,9]在B中的存储位置k=_______。（注：矩阵元素下标从1开始）。

2. 三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]

的地址是_______。(设a[0][0][0]的地址是1000,数据以行为主序方式存储)。

3. 假设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000 (2)a1111 (3)a3125 (4) a8247

4. 按高下标优先存储方式（最右的下标为主序），顺序列出数组A[2][2][3][3]中所有元素

aijkl,列出aijkl的序列。 5. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 6. 求下列广义表操作的结果 GetHead 【(p,h,w)】 GetTail 【(b,k,p,h)】 GetHead 【((a,b),(c,d))】 GetTa

第五章习题

5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为

1000，计算：

数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A36的地址； 按列存储时元素A36的地址；

5.2 设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij ，

求：

（1） 用i,j表示k的下标变换公式； （2） 用k表示i,j的下标变换公式。

5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放

结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个

辅助向量空间。 5.5写一个在十字链表中删除非零元素aij的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; （2） TAIL[((a,b),(c,d))]; （3） TAIL[HEAD[((a,b

05 图

【单选题】

1. 设无向图G中有五个顶点，各顶点的度分别为2、4、3、1、2，则G中边数为（C）。 Ａ、4条 Ｂ、5条 Ｃ、6条 Ｄ、无法确定

2. 含n个顶点的无向完全图有（D）条边；含n个顶点的有向图最多有（C）条弧；含n个顶点的有向强连通图最多有（C）条弧；含n个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n个顶点，则要接通全部顶点至少需（G）条边。

A、n2 B、n(n+1) C、n(n-1) D、n(n-1)/2 E、n+1 F、n G、n-1

3. 对下图从顶点a出发进行深度优先遍历，则（A）是可能得到的遍历序列。 A、acfgdeb B、abcdefg C、acdgbef D、abefgcd

对下图从顶点a出发进行广度优先遍历，则（D）是不可能得到的遍历序列。 A、abcdefg B、acdbfge C、abdcegf D、adcbgef

?010???4. 设图G的邻接矩阵A=101，则G中共有（C）个顶点；若G为有向图，则G中共有（D）????010??条弧；若G为无向图，则G中共有（B）条边。

A、1 B、2 C、3 D、4 E、5 F、9 G、以上答案都不对

5. 含n个顶点的图，最少有（B）个连通

第5章 数组和广义表

前面几章我们讨论了线性表、栈、队列和串都是线性数据结构，它们的组成元素都是数据元素，元素的值都是不可分解的。而这章将要讨论的数组和广义表是一种复杂的线性结构，它的组成元素是可以分解的。数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 数组的定义与存储

数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。

5.1.1 数组的定义

数组是由n(n>1)个相同类型的数据元素a0，al，…，ai，…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，它可以是整型、实型等简单数据类型，也可以是数组、结构体、指针等构造类型。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。

1.一维数组

一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。一维数组记为A[n]或A=( a0，al，…ai，…，an-1)。

一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数k确定，则

第五章数组和广义表：习题

习 题

一、选择题

1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单

元，基地址为10，则LOC(A[5，5])=( )。 A. 808 B. 818 C. 1010 D. 1020 2．同一数组中的元素( )。

A. 长度可以不同 B．不限 C．类型相同 D. 长度不限

3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范

圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。 (1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址

一致。

供选择的答案：

(1)A. 90 B. 180 C. 240 D. 270 E.540 (2) A. 108 B. 114 C. 54 D. 60 E.150 (3)A.A[8][5]

习题五 数组和广义表

一、单项选择题

1．常对数组进行的两种基本操作是（ ）

A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引

2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.

A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k

B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k

3．稀疏矩阵的压缩存储方法是只存储 ( )

A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175 B. 1180

习题五 数组和广义表

一、单项选择题

1．常对数组进行的两种基本操作是（ ）

A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引

2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.

A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k

3．稀疏矩阵的压缩存储方法是只存储 ( )

A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j

4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175 B. 1180

5.10 假设对指令Cache的访问占全部访问的75%；而对数据Cache的访问占全部访问的25%。Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期，32KB的指令Cache的失效率为0.39%，32KB的数据Cache的失效率为4.82%，64KB的混合Cache的失效率为1.35%。又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比，哪种Cache的失效率更低？两种情况下平均访存时间各是多少？

解：（1）根据题意，约75%的访存为取指令。 因此，分离Cache的总体失效率为：（75%×0.15%）＋（25%×3.77%）＝1.055%； 容量为128KB的混合Cache的失效率略低一些，只有0.95%。 （2）平均访存时间公式可以分为指令访问和数据访问两部分：

平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋ 数据所占的百分比×（数据命中时间

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

第一章 绪论 一、选择题

1. 算法的计算量的大小称为计算的（ B ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C ）

A．问题的规模 B. 待处理数据的初态 C. A 和B 3.计算机算法指的是（1C） ，它必须具备（2B） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（ B ） 。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A 和C. 5