第一章
基础知识题(一)
简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： (1) i=1; k=0;
while(i<=n-1) { @ k += 10*i; i++;} (2)i=1; k=0; do {
@ k += 10*i; i++;
} while(i<=n-1); (3)i = 1; k = 0;
while (i<=n-1) { i++ ;
@ k+= 10 * i; }
(4) k=0;
for( i=1; i<=n; i++) { for (j=i ; j<=n; j++) @ k++; }
(5) for( i=1; i<=n; i++) { for (j=1; j<=i; j++) { for (k=1; k<=j; k++) @ x += delta; } }
(6) i=1; j=0;
while (i+j<=n) { @ if (i>j ) j++ ; else i++ ; }
(7) x=n; // n 是不小于1的常数 y=0;
while (x>=(y+1)*(y+1)) {
@ y++; }
(8) x=91; y=100;
while (y>0 ) {
@ if (x>100 ) { x -= 10; y- -; } else x++; }
第二章
编程练习题
1. 设顺序表 a 中的数据元素递增有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。
void InsertOrderList( SqList &a, ElemType x)
// 已知顺序表 a 中的数据元素递增有序，将 x 插入到顺序表的适当位置上， // 以保持该表的有序性。
2. 设A=( ,…, ) 和B=( ,…, ) 均为顺序表，A' 和B' 分别为 A 和 B 中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为A'=(x,z) 和 B'=(y,x,x,z)）。若 A'= B'= 空表，则 A = B；若 A'= 空表，而 B'≠ 空表，或者两者均不为空表，且 A'的首元小于 B'的首元，则 A
// 已知顺序表A和B, 返回 '<'(若 'A
void del_between_mink_and_maxk( LinkList& hlink, ElemType mink, ElemType maxk )
// hlink 为指向单链表头结点的指针，删除链表中其值介于 mink 和 maxk 之间的结点。
4. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表( , …, ) 逆置为( , ,…, )。
void invert_sqlist(SqList& va) // 逆转顺序表 va
5. 试写一算法，对单链表实现就地逆置。 void invert_linkst(LinkList& hlink) // 逆转以 hlink 为头指针的单链表
6. 假设有两个按元素值递增有序排列的线性表 A 和 B，均以单链表作存储结构，请编写算法将 A 表和 B 表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表 C，并要求利用原表（即 A 表和 B 表）的结点空间构造 C 表。
void union_linkst( LinkList& lc, LinkList la, LinkList lb ) // 将两个(分别以 la 和 lb 为头指针的)增序有序链表
// 归并为一个逆序(非递增)有序链表，归并后的链表的头指针为 lc 。
7. 假设以两个元素依值递增有序排列的顺序表 A 和 B 分别表示两个非纯集合（即同一表中可能存在值相同的元素），现要求构成一个线性表 C，其元素为 A 和 B 中元素的交集，且表 C 中的元素也依值递增有序排列并各不相同，并要求 C 表和 A 表共享存储空间。
void intersect_sqlist( SqList& va, SqList vb )
// va 和 vb 均为有序(值自小而大)顺序表，且同一表中可能有值相同的 // 数据元素，本函数实现从 va 中删除所有值和 vb 中元素不相同的元素， // 并使最后所得的顺序表 va 中的数据元素值均各不相同。 8. 对单链表重新编写和题7相同要求的算法。
void intersect_linkst( LinkList& hc, LinkList ha, LinkList hb ) // 构造有序链表 hc 表示\纯集合\为有序链表 ha 表示的 // 非纯集合 A 和 有序链表 hb 表示的非纯集合 B 的交集
9. 已知 A、B 和 C 为三个递增有序的顺序表，现要求对 A 表作如下操作：删去那些既在 B 表中出现又在 C 表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 void difference_sqlist( SqList& a, SqList b, SqList c )
// 从增序顺序表 a 中删除那些既在 b 表中出现又在 c 表中出现的数据元素 10. 对单链表重新编写和题9相同要求的算法。
void difference_linkst(LinkList& la, LinkList lb, LinkList lc)
// 从增序有序链表 la 中删除那些既在 lb 表又在 lc 表中出现的数据元素 11. 设有一个双向循环链表，每个结点中除有 pre、data 和 next 三个域外，还增设了一个访问频度域 freq。在链表被起用之前，频度域 freq 的值均初始化为零，而每当对链表进行一次 LOCATE(L,x) 的操作后，被访问的结点（即元素值等于 x 的结点）中的频度域 freq 的值便增 1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述
要求的 LOCATE 操作的算法。
DuLink visit( DuLinkList dh, ElemType x )
// 本题要求返回指向被访问的结点的指针，若链表中不存在和 x 相等的元素， // 这返回 NULL。dh 是指向双向循环链表头结点的指针，结点中还增设了一个 // 访问频度域 freq，其初值为 0，一旦结点被访问，其访问频度域的值增 1， // 并始终保持链表中的结点按 freq 的值非递增排列
12. 假设以如下说明的循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。
typedef struct PolyNode* PolyLink; struct PolyNode {
PolyTerm data; PolyLink next; };
typedef PolyLink LinkedPoly ;
void difference ( LinkedPoly& pa )
// 稀疏多项式 pa 以循环链表作存储结构，将此链表修改成它的导函数， // 并释放无用结点
第三章
进栈序列为123，则可能得到的出栈序列是什么?
如果进栈序列为123456，则能否得到435612和135426的出栈序列，并请说明为什么不能得到。
简述栈和线性表的差别。
简述队列和栈这两种数据类型的相同点和差异处。
写出下列程序段的输出结果（栈的元素类型 SElemType 为 char） void main( ){ Stack S; char x, y; InitStack(S); x='c'; y='k';
Push(S, x); Push(S, 'a'); Push(S, y); 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); }
简述以下算法的功能（栈的元素类型 SElemType 为int） status algo1(Stack S) { int i, n, A [255]; n=0;
while (!StackEmpty(S) ) { n++; Pop(S, A[n]); } for ( i=1; i<= n ; i++) Push(S, A[i]); }
status algo2(Stack S, int e) { Stack T; int d; InitStack(T);
while (!StackEmpty(S)) {Pop(S,d);
if(d!=e ) Push(T, d);} while (!StackEmpty(T)) {Pop(T, d);Push(S, d);} }
简述以下算法的功能（栈和队列的元素类型均为 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); } }
第四章
简述空串和空格串(或称空格符串)的区别。
设s = ‘I AM A STUDENT’, t = ‘GOOD’, q = ‘WORKER’。 求：
StrLength(s) StrLength(t) SubString(s,8,7) SubString(t,2,1) Index(s,'A') Index(s,t),
Replace(s, 'STUDENT',q),
Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) 已知下列字符串 a='THIS‘
f='A SAMPLE‘ c=’GOOD‘ d=’NE’