A、顺序存储
B、链式存储 C、顺序存储且已排序 D、链式存储且已排序
三、判断题
1. 2. 3. 4. 5. 6. 7. 8.
（ ）单链表从任何一个结点出发，都能访问到所有结点。 （ ）顺序表是一种随机存取的存储结构。
（ ）线性表的逻辑顺序与存储顺序总是一致的。 （ ）线性表的链式存储结构优于顺序存储结构。
（ ）数据的存储结构是数据的逻辑结构在存储单元中的表示形式。 （ ）程序的执行效率与数据存储结构的选择没有直接的关系。 （ ）线性表的长度是指线性表所占存储空间的大小。
（ ）线性表的长度决定了线性表所占存储空间的大小，但它不等于线性表所占存储空间的大小。
9. （ ）在采用链式存储结构的线性表上查找某个元素的平均效率比在采用顺序存储结
构的线性表上查找的平均效率高。
10. （ ）链式存储结构的线性表适用于对数据进行频繁的查找操作，而顺序存储结构的
线性表则适宜于进行频繁地插入、删除操作。
11. （ ）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p
的后面：p->next = s; s->next = p->next;
12. （ ）二维数组是其数据元素为线性表的线性表。 13. （ ）N（N>1）维数组可以看作是线性表的推广。 14. （ ）循环队列也存在空间溢出问题。 15. （ ）队列和栈都是运算受限的线性表，插入或者删除运算只允许在表的同一端进行。 16. （ ）从数据元素插入、删除的规则来看，队列的本质特征是LIFO,栈的本质特征是
FIFO。
17. （ ）所有插入排序算法均是稳定的。
18. （ ）顺序存储方式只能用于存储线性结构。
19. （ ）程序的执行效率只决定于算法设计的技巧，与程序设计中所采用的数据的表示
方式及数据逻辑模型的实际存储形式无关。
20. （ ）线性表的特点是每个元素都有一个前驱结点和一个后继结点。 21. （ ）链表的每个结点中都包含一个指针。 22. （ ）算法一定要有输入和输出。
23. （ ）顺序查找算法可以用在顺序存储结构表示的线性表上查找数据元素，但不可以
用在链式存储结构的线性表上查找数据元素。
24. （ ）折半查找方法只能用在采用顺序存储结构的有序线性表中来实现对某一数据项
的快速查找。
25. （ ）折半查找方法可以用在采用单向链表形式存储的有序线性表中实现对某一数据
项的快速查找。
26. （ ）判断某个排序方法的稳定性可以通过一次或几次输入数据序列，看排序结果是
否改变了原始待排数据序列中关键字值相同的数据是否发生了相对次序的改变，从而作出该排序算法是否稳定的结论。
四、简答题
1. 什么是算法？具有哪些特性？如何衡量一个算法的好坏？算法与程序有何不同？ 2. 线性表顺序存储结构的优缺点是什么？
3. 4. 5. 6. 7.
线性结构与非线性结构有何差别？ 简述顺序表和链表之间的差异。 什么是排序方法的稳定性？
什么叫栈？它有哪些基本操作？各个基本操作的含义是什么？ 什么叫队列？它有哪些基本操作？各个基本操作的含义是什么？
五、综合题
1. 给出下列稀疏矩阵A的三元组表示法的存储模型。
A =
0 33 0 22 0 -15 0 0 3 0 0 0 0 0 0 -12 0 0 0 0 0 0 -10 0 0 0 0 0 0 0 0 0 0 0 0 2
2. 给出下列稀疏矩阵所对应的三元组表示方法存储模型。
0?0129?0000???3000??00240?01800???1500?700?000??0140??000?000??000??0
3. 给出下列稀疏矩阵A的三元组表示法的存储模型。
4. 设单链表的结点为： typedef struct node
{ int data;
struct node *next } LinkList;
LinkList *p,q;
如果要求将由指针变量q所指向的结点插入到单向链接表中p所指向的结点之后，则应执行的语句是什么？要将p所指向的结点的数据部分修改为23，应执行的语句是什么？ 5. 对于给定的一组关键字:503,087,512,067,908,170,889,276,675,453；请按关键字递减
排序，写出直接插入排序、冒泡排序的各趟运行结果。
6. 某长度为10的有序表存储于一维结构数组中下标0~9的位置中,其中记录的关键键码值
依次是：5,10,18,21,33,47,48,55,80，125，现要查找关键码值为18及83的记录，现规定在中间位置计算时采用“向下取整”的方法，写出折半查找的过程及查找结果。 7. 有序表中关键字序列为：5，10，19，21，31，37，42，48，55，150，现要查找k为
37及32的记录，写出其折半查找过程。
8. 设待排序的记录共7个，关键码分别为8，3，2，5，9，1，6。试用直接插入、直接选
择两种方法，以关键码的变化描述排序全过程（动态过程），要求按递减顺序排序。 9. 设待排序文件共有12个记录，其关键字依次分别是28，55，06，33，161，81，91，
11，25，55′，57，02，请按选择排序的思想写出降序排序的全过程。
10. 设有待排序的8个数据记录，其排序用关键字的取值依次是14，35，18，5，7，21，
35，8，请用简单选择排序法写出降序排序的每一趟结果。
11. 设有待排序的8个数据记录，其排序用关键字的取值依次是68，45，20，90，15，10，
50，8，请按直接选择排序的思想写出升序及降序排序的每一趟结果。
12. 假设待排序的一批记录的关键字序列为{14，35，18，5，7，21}，请给出按照简单选择
排序方法依据关键字取值升序和降序两种情况下的排序过程。
13. 一个有序表的一批记录的关键字序列为（7，11，15，20，32，45，63，70，82，91），
存放在一个采用顺序存储结构表示的线性表中，其中数组元素的下标为0，…，9的位置上分别对应存储有序表的第一元素直到最后一个元素。在折半查找中，中间位置指示器的计算式子中采用取下整的方法，请给出查找关键字值为82和关键字值为13的记录的查找过程。
14. 某长度为10的有序表存储于一维结构数组中下标0~9的位置中，其中记录的关键码值
依次是：5,10,18,21,33,47,48,55,80,125，现要查找关键码值为18及83的记录，现规定在中间位置计算时采用“取下整”的方法，写出折半查找的过程及查找结果。
15. 设有待排序的8个数据记录，其排序用关键字的取值依次是68，45，20，90，15，10，
50，8，请用冒泡排序法写出升序排序的每一趟结果。
16. 对于给定的一组关键字: 50,38,27,16,97,76,53,66；按关键字递减排序，写出冒泡排
序的各趟运行结果。
六、算法分析与设计题
1. 下面给出的算法的功能是在顺序存储结构表示的线性表中插入一个数据元素，请画出算
法的流程图，在算法中对各个分支给出功能性注释。 #define Null 0
#define MaxSize 1024 typedef int DataType; typedef struct node {
DataType data[MaxSize]; int last; }SequenList;
int Insert(SequenList *L,DataType x,int i) {
SequenList *p; int j; p=L;
if(p->last==(MaxSize-1))
{
printf(\线性表已经满了，无法再加入!\ return Null; } else
if( (i<1) ||( i>(p->last+1))) {
printf(\所给插入位置不在有效范围之内!\ return Null; } else {
for(j=L->last;j>=i-1;j--) L->data[j+1]=L->data[j]; L->data[i-1]=x; L->last=L->last+1; }
return (1); }
2. 现要求完成同类型的两个线性表的合并运算，该运算将给定第二个线性表的元素追加到
第一个线性表的最后一个元素之后，假定不会产生因空间不足而上溢的现象，运算完成后应修改第一个线性表的last分量以反映新的表长，运算不破坏第二个线性表。预期的功能用下面的计算示例及算法流程图表示。请将下列给定的算法设计填写完整。 算法功能描述：计算前 L1={1,3,5,7,9}, L2={2,4,6,8}
计算后： L1={1,3,5,7,9,2,4,6,8},L2={2,4,6,8} 线性表的顺序存储结构定义：
#define MaxSize 1024 /*允许的最大数据元素数目*/ typedef int DataType; /*数据元素的类型*/
typedef struct node{
DataType data[MaxSize]; /*存储线性表中数据元素用的数组*/
int last; /*存储表的最后一个元素存放在data数组中的下标号*/
} SequenList;
计算前：
在L1表的存储结构体变量中，
data[0]=1,data[1]=3,data[2]=5,data[3]=7,data[4]=9
last=4;
在L2表的存储结构体变量中，计算前：
data[0]=2,data[1]=4,data[2]=6,data[3]=8 last=3
计算后：
在L1表的存储结构体变量中，
data[0]=1,data[1]=3,data[2]=5,data[3]=7,data[4]=9,data[5]=2, data[6]=4,data[7]=6,data[8]=8