(2)从类型为list的线性表L中删除其值等于x的所有元素。

(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。 5.编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。 (1)将一个单链表中的所有结点按相反次序链接。 (2)删除单链表中第i个（i≥1）结点。 (3)删除单链表中由指针p所指向的结点。

(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (6)从循环单链表中查找出最小值。

(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结

点的单链表。

(8)请指出下面的过程执行p(5)和p(6)时分别输出的结果。 void P(int n); {

if n>0

{

p(n-2);

printf(\ } }

(9)假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针，设

队首指针，试编写下列算法：

(1)向循环链队插入一个元素为x的结点；

(2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结

点）。

5

第三章

一、 选择题

1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为 。

A. top不变 Ｂ. top＝ -n C. top＝top-1 D. top=top+1 2.向顺序栈中压入元素时，是 。

A. 先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入元素 3.在一个顺序存储的循环队列中，队首指针指向队首元素的 。

A. 前一个位置 B. 后一个位置 C. 队首元素位置 D. 队尾元素位置 ５.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 ６.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 。

A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0 ７.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是 。

A. rear % n= =front B. (rear-1) % n= =front C. (rear-1) % n= =rear D. (rear+1) % n= =front

８.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 。 A. hs->next=s; B. s->next=hs->next; hs->next=s;

C. s->next=hs；hs=s; D. s->next=hs; hs=hs->next;

9.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行 。

A. front->next=s; front=s; B. rear->next=s; rear=s; C. front=front->next; D. front=rear->next; 二、填空

1.在具有n个单元、顺序存储的循环队列中，队满时共有 个元素。 2.无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复 杂性均相同，则为 。 三、综合题

1. 试述栈的基本性质?

2. 何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。 3. 两个字符串相等的充要条件是什么?

6

第四章

一、 选择题

1.设字符串s1='abcdefg',s2='pqrst'，则运算 s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为 。

A. 'bcdef' B. 'bcdefg' C. 'bcpqrst' D. 'bcdefef' 2.设a、b、c、d都是串名，a＝'THIS IS A BOOK'，b＝'ESE ARE'，C＝'S'。 求d＝CONCAT(SUB(a,1,2)，b，SUB(a,10,5),c)＝

A. 'bcdef' B. 'bcdefg' C. 'bcpqrst' D. 'bcdefef'

二、综合题

1.设a、b、c、d都是串名，a＝'THIS IS A BOOK'，b＝'ESE ARE'，C＝'S'。求d＝CONCAT(SUB(a,1,2)，b，SUB(a,10,5),c)＝？

第五章

一、 填空

1.一个数据结构用二元组表示时，它包括 的集合K和K上 的集合R。 2．对于一个二维数组A[1..m,1..n]，若按行序为主序存储，则任一元素A[i,j]的相对地址（即偏移地址）为 。 二、判断题

1．数组是同类型值的集合（ ）。

2．使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间（ ）。

3.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表（ ）。 四、综合题

1. 用三元组表示下面稀疏矩阵的转置矩阵。 ┏0 1 0 0 0┓ ┃2 0 0 0 3┃ M＝┃0 0 4 0 0┃

┗0 0 0 5 0┛

2．在n×n(n≥3)的稀疏矩阵A中，只有下标满足1

等于零，若这些非零元素按行优先的顺序存入首地址为FIRST的一个连续的存储空间中， 试写出任一非零元素A[i,j]的存储地址公式。

3.数组b[1..10,-2..6,2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。试求元素b[5,0,7]的存储首址。

4.在n×n(n≥3)的稀疏矩阵A中，只有下标满足1

7

等于零，若这些非零元素按行优先的顺序存入首地址为FIRST的一个连续的存储空间中， 试写出任一非零元素A[i,j]的存储地址公式。

5. 画出广义表(A(B(E，F(J))，C，D(G(K，L)，H，I)))对应的树型结构。

8