数据结构自测题(带答案)2013-11-28.doc

第一章 概论
一、填空题
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之
间的 关系 和运算等的学科。
2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。
3. 数据结构包括数据的 逻辑结构 、数据的 物理结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。
5. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。
6． 在线性结构中，第一个结点 无 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结
点 无 后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没
有 后继 结点，其余每个结点的后续结点数可以 有多个后继 。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 有多个 。
9. 一个算法的效率可分为 时间 效率和 空间 效率。
10．数据之间的关系在计算机中有两种不同的表示方法，即 顺序映像 和 非顺序映像 。
11．算法的五个重要特性是 输入性 、 输出性、 有穷性 、 可行性 和 确定性 。
12． 数据项 是数据的不可分割的最小单位。
13．算法分析的两个主要方面是 时间复杂度 和 空间复杂度 。
14． 数据元素 是数据的基本单位，
15．对于给定的n个元素，可以构造的逻辑结构有 线性 ， 集合 ，　树型，
图型 等４种。
16．数据结构包括数据的 集合 、数据的 关系 和数据的 运算 这三个方面的内容。
17．数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构。
二、单项选择题
（ B ）1. 非线性结构是数据元素之间存在一种：
A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系
（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；
A) 存储 B) 物理 C) 逻辑 D) 物理和存储
（ C ）3. 算法分析的目的是：
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
（ A ）4. 算法分析的两个主要方面是：
A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
（ C ）5. 计算机算法指的是：
A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法
（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性

三、分析下面各程序段的时间复杂度

1. for (i=0; i<n; i++)
for (j=0; j<m; j++)
A[i][j]=0;
O（n*m）
2. s=0;
for (i=0; i<n; i++)
for(j=0; j<n; j++)
s+=B[i][j];
O(n*n)
3. x=0;
for(i=1; i<n; i++)
for (j=1; j<=n-i; j++)
x++;
O(n*n)
4. i=1;
while(i<=n)
i=i*3;
O（log3n）
5.求下列算法段的语句频度及时间复杂度。
for(i=1; i<=n; i++)
for(j =1; j<=i ; j++)
x=x+1;
O(n*n)

6.分析下列算法段的时间频度及时间复杂度。
for （i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
}
O(n*n*n)

第2章 线性表
一、填空
1. 在顺序表中插入或删除一个元素，需要平均移动 表中一半 元素，具体移动的元素个数
与 插入位置 有关。
2. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。
3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。
4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) 。
6. 顺序表中逻辑上相邻的元素的物理位置 一定 相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。
7. 在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的指针域的值 指示。
8． 在n个结点的单链表中要删除已知结点*p，需找到它的 直接前驱 ，其时间复杂度为 O（1） 。
二、判断
（ F ）1. 链表的每个结点中都恰好包含一个指针。
（ F ）2. 链表的物理存储结构具有同链表一样的顺序。
（ F ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。
（ F ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（ F ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（ F ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ F ）7. 线性表在物理存储空间中也一定是连续的。
（ F ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ F ）9. 顺序存储方式只能用于存储线性结构。
（ F ）10. 线性表的逻辑顺序与存储顺序总是一致的。
（ F ）11．栈和队列是一种非线性数据结构。
（ T ）12．栈和队列的存储方式既可是顺序方式，也可是链接方式。
（ F ）13．对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
（ F ）14.顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。
（ F ）15.在单链表中，头结点是必不可少的。
（ F ）16.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。
（ T ）17.循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。
三、单项选择题
（ C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构
（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是
（A）110 （B）108 （C）100 （D）120
（ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：
（A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
（B） 在第i个结点后插入一个新结点（1≤i≤n）
（C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序
（ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素
（A）8 （B）63.5 （C）63 （D）7
（ A ）5. 链接存储的存储结构所占存储空间：
（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
（B） 只有一部分，存放结点值
（C） 只有一部分，存储表示结点间关系的指针
（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数
（ B ）6. 链表是一种采用 存储结构存储的线性表；
（A）顺序 （B）链式 （C）星式 （D）网状
（ D ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:
（A）必须是连续的 （B）部分地址必须是连续的
（C）一定是不连续的 （D）连续或不连续都可以
（ B ）8． 线性表Ｌ在 情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂
（ C ）9． 单链表的存储密度
（Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能确定
（ B ）10． 设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为

P0

3

4

P0
à
a1
3
à
a2
4
à
a3
0
（Ａ）循环链表 （Ｂ）单链表 （Ｃ）双向循环链表 （Ｄ）双向链表
11．（ B ）在表长为ｎ的链表中进行线性查找，它的平均查找长度为
（Ａ） ＡＳＬ＝ｎ; （Ｂ） ＡＳＬ＝（ｎ＋１）／2;
（Ｃ） ＡＳＬ＝＋1; （Ｄ） ＡＳＬ≈ｌｏｇ２（ｎ＋１）－1
12．（ A ）链表适用于 查找
（A）顺序 （B）二分法 （C）顺序，也能二分法 （D）随机
13．（ A ）在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：
（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
（B）在第i个结点后插入一个新结点（1≤i≤n）
（C）删除第i个结点（1≤i≤n）
（D）将n个结点从小到大排序
14．（ D ）线性表若采用链式存储结构时，要求内存中可用存储单元的地址：
（A）必须是连续的 （B）部分地址必须是连续的
（C）一定是不连续的 （D）连续或不连续都可以
15．（B ）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素
（A）8 （B）63.5 （C）63 （D）7
16．（ A ）链接存储的存储结构所占存储空间：
（A）分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
（B）只有一部分，存放结点值。
（C）只有一部分，存储表示结点间关系的指针。
（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数。
17．链表不具有的特点是( A )。
A、可随机访问任一个元素 B、插入删除不需要移动元素
C、不必事先估计存储空间 D、所需空间与线性表的长度成正比
18．带头结点的单链表head为空的判定条件是（ B ）
（A）head==NULL （B） head->next== NULL （C）head （D）head!= NULL
19．若希望从链表中快速确定一个结点的前驱，则链表最好采用（ C ）方式。
A、单链表 B、循环单链表 C、双向链表 D、任意
20．线性表是具有n个（ C ）的有限序列。
A、表元素 B、字符 C、数据元素 D、数据项
21．若希望从链表中快速确定一个结点的前驱，则链表最好采用（ C ）方式。
A、单链表 B、循环单链表 C、双向链表 D、任意
三、简答题
1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

2 . 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。

第3章 栈和队列

一、填空题
1. 线性表、栈和队列都是 线性 结构，可以在表的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队头 删除元素。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。
3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4. 在一个循环队列中，队头指针指向队首元素的 前一个 位置。
5. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。
6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。
7. 从循环队列中删除一个元素时，其操作是 先 移动队头指针 ，后 取出元素 。
8. 带表头结点的空循环双向链表的长度等于 0 。
9．栈和队列都是线性结构，对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和队首删除元素。
10．队列是一种 先进先出 的线性表。
11．在顺序队列Q中，判断队列已空的条件是 Q.rear==Q.front 。
12．在顺序队列Q中，判断队列已满的条件是 Q.rear-Q.fron==maxsize
二、判断正误（判断下列概念的正确性，并作出简要的说明。）
（ F ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（ F ）2. 在表结构中最常用的是线性表，栈和队列不太常用。
（ T ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（ T ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
（ F ）5. 栈和链表是两种不同的数据结构。
（ F ）6. 栈和队列是一种非线性数据结构。
（ T ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
（ T ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（ F ）9. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
（ F ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
三、单项选择题
（ B ）1. 栈中元素的进出原则是
Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出
（ C ）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为
Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定
（ B ）3. 判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0
（ A ）4. 判定一个队列QU（最多元素为m0）为满队列的条件是
Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0
Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1
（ D ）5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为
（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n
5．（ B ）判定一个栈ST（最多元素为m0）为空的条件是
（A）ST->top<>0 （B）ST->top=0 （C）ST->top<>m0 （D）ST->top=m0
6．若已知一个栈的入栈序列是1,2,3,．．．,n，其输出序列为p1,p2,p3,．．．pn，若p1=1,则pi为( D )
（A）i （B）n （C） n-i+1 （D）不确定
7．在一个具有Ｎ个单元的顺序栈中，假定以地址高端（既下标为Ｎ的单元）作为栈底，以TOP作为栈顶指针，向栈中压入一个元素时，TOP的变化（ C ）
（A）TOP不变 （B）TOP=N （C）TOP=TOP+1 （D）TOP=TOP-1
8．栈和队列的共同点是（ C ）。
A、都是先进后出 B、都是先进先出 C、只允许在一端进行插入和删除操作 D、没有共同点
9．将递归算法转换成对应的非递归算法时，通常需要使用（ A ）。
A、栈 B、队列 C、链表 D、树
10．循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ C ）。
A、rear-front B、rear-front+1 C、(rear-front+m)%m D、rear-front-1
11．设计一个判别表达式中左,右括号是否配对出现的算法,采用（ B ）数据结构最佳.
A、线性表的顺序存储结构 B、栈 C、线性表的链式存储结构 D、队列
12．从一个栈顶指针为HS的链栈中删除一个结点时，假定用X保存被删除结点的值，则
执行 D 。
A、 X=HS； HS=HS->NEXT; B、 X=HS->DATA;
C、 HS=HS->NEXT；X=HS->DATA; D、 X=HS->DATA；HS=HS->NEXT;

13. 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。
现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B ；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。
供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E： ①1 ②2 ③ 3 ④ 0
答：A、B、C、D、E分别为 ② 、 ④ 、 ① 、 ② 、 ②
14. 栈是一种线性表，它的特点是 A 。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。
供选择的答案：
A： ① 先进先出 ②后进先出 ③进优于出 ④出优于进 ⑤ 随机进出
B，C： ① 加1 ②减1 ③不变 ④清0 ⑤ 加2 ⑥减2
D： ① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c
E： ① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2
答：A、B、C、D、E分别为 ② 、 ② 、 ① 、 ⑥ 、 ④
15. 在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。
为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。
供选择的答案：
A，B：①空 ② 满 ③ 上溢 ④ 下溢
C： ①n-1 ② n ③ n+1 ④ n/2
D： ① 长度 ②深度 ③ 栈顶 ④ 栈底
E：①两个栈的栈顶同时到达栈空间的中心点 ②其中一个栈的栈顶到达栈空间的中心点
③两个栈的栈顶在达栈空间的某一位置相遇 ④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底
答：A、B、C、D、E分别为 ② 、 ① 、 ② 、 ④ 、 ③
三、简答题
1. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。
4321，3421，3241，3214，2431，2314，2341，2134，2143，1234，1342，1324，1432，1243，
① 全进之后再出情况，只有1种：4，3，2，1
② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4
③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4
④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3
2. 顺序队列的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外，解决队满队空的办法有三：
① 设置一个布尔变量以区别队满还是队空；
② 浪费一个元素的空间，用于区别队满还是队空。
③ 使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N
3. 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？
答：用队列长度计算公式： (N＋rear－fron)% N
① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32
4． 写出下列程序段的输出结果（栈的元素类型SElem Type为char）。
Pop(S,x); Push(S,’t’); Push(S,x);
Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){ Pop(S,y);printf(y); };
Printf(x);
}
void main( ){
Stack S;
Char x,y;
InitStack(S);
x=’c’;y=’k’;
Push(S,x); Push(S,’a’); Push(S,y);
答：输出为“stack”

5． 写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。
void main( ){
Queue Q; Init Queue (Q);
Char x=’e’; y=’c’;
EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q,y);
DeQueue (Q,x); EnQueue (Q,x);
DeQueue (Q,x); EnQueue (Q,’a’);
while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };
Printf(x);
}
答：char
6． 简述以下算法的功能（栈和队列的元素类型均为int）。
void algo3(Queue &Q){
Stack S; int d;
InitStack(S);
while(!QueueEmpty(Q)){
DeQueue (Q,d); Push(S,d);
};
while(!StackEmpty(S)){
Pop(S,d); EnQueue (Q,d);
}
}

第5章 数组
一、填空题
1. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 ；末尾元素A[5][7]的第一个字节地址为 1282 ；若按行存储时，元素A[1][4]的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A[4][7]的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。
2. 设数组a[60][70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32][58]的存储地址为 9072 。
3. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素
的行号 、 列号 和 数值 。
4.求下列广义表操作的结果：
（1） GetHead[((a,b),(c,d))]=== (a,b) ;
（2） GetHead[GetTail[((a,b),(c,d))]]=== (c,d) ;
（3） GetHead[GetTail[GetHead[((a,b),(c,d))]]]=== b ;
（4） GetTail[GetHead[GetTail[((a,b),(c,d)) ]]]=== (d) ;
5．二维数组A[0..20][0..10]采用以行序为主方式存储，每个元素占4个存储单元,并且A[0][0]的存储地址是1016，则A[9][8]的存储地址是 1444
6．假设线性表的每个元素占用L个存储单元，线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个元素的存储位置LOC(ai)之间满足的关系式为： 不确定
7．稀疏矩阵常用的两种存储方法有 三元组表 和 十字链表 。
二、单选题
（ A ）1 假设有60行70列的二维数组a[60][70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32][58]的存储地址为 。（无第0行第0列元素）
Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不对
( B ) 2. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是：
Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j
Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j
3. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。
存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是 B 和 C 。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是 D 和 E 。
供选择的答案
A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108 ⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188
答案：A＝ ⑧ B＝ ③ C＝ ⑤ D＝ ① E= ⑥
4. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 A 个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A[2,4]的第一个字节的地址是 C 。若按列存储，则A[5,7]的第一个字节的地址是 D 。
供选择的答案
A～D：①12 ②66 ③72 ④96 ⑤114 ⑥120 ⑦156 ⑧234 ⑨276 ⑩282 （11）283 （12）288
答案：A＝ （12） B＝ ⑩ C＝ ③ D＝ ⑨
5．设有50行的二维数组A[50][60]，其元素长度为2字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（ D 2410 ）。
A、1850 B、188 C、1950 D、2410
6．广义表(a,b,(c,(d)))的表尾是（ D ）。
A．(d) B. (c,(d))
C. b,(c,(d)) D. (b,(c,(d)))
三、简答题
1. 已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？
解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；
按行存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K
按列存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K
四、计算题
1. 用三元组表表示下列稀疏矩阵：

解：参见填空题4. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。
所以（1）可列表为： （2）可列表为：
8
8
6
6
4
1
6
-2
2
5
9
4
3
5
6
5
3

5
3
2
3
3
6
8
5
4
6
7
8
5
8
1
2

2. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。

解：（1）为6×4矩阵，非零元素有6个。 （2）为4×5矩阵，非零元素有5个
0 2 0 0
12 0 0 0
3 0 0 0
0 0 0 4
0 0 6 0
16 0 0 0

1 0 0 0 0
0 0 0 9 0
0 8 0 0 6
0 0 7 0 0

3．试画出下列稀疏矩阵以行序为主序的三元组表。

答：

4．设一稀疏矩阵为6行5列，其三元组表中存储的非零元素依将为（-90，28，7，24，35，5，-98）,列号依次为1，4，5，2，5，1，4，行表cpot的值依次为0,0,2,2,3,5,5,请画出该稀疏矩阵。
答案为：
0
0
0
0
0
-90
0
0
28
0
0
0
0
0
0
0
0
0
0
7
0
24
0
0
32
5
0
0
-98
0

5．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]（10）存放在什么位置？脚注（10）表示用10进制表示。
答案：设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中。
因为：Loc(2,2)= Loc(0,0)+2*n+2=644+2*n+2=676
所以：n=(676-2-644)/2=15
所以：Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=692
6．数组A中，每个元素A[i,j]的长度均为2个字节,行下标从1到9，列下标从1到11，从首地址S开始连续存