第一章 绪论

一、选择题

1、( )是数据的基本单位。

A) 数据结构 B)数据元素 C)数据项 D)数据类型 2、以下说法不正确的是( )。

Ａ)数据结构就是数据之间的逻辑结构。

Ｂ)数据类型可看成是程序设计语言中已实现的数据结构。 Ｃ)数据项是组成数据元素的最小标识单位。 Ｄ)数据的抽象运算不依赖具体的存储结构。

3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（ ）等5个特性。 A)可执行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性 4、一般而言，最适合描述算法的语言是( )。

A)自然语言 B)计算机程序语言 C)介于自然语言和程序设计语言之间的伪语言 D)数学公式 5、通常所说的时间复杂度指( )。

A)语句的频度 B)算法的时间消耗 C)渐近时间复杂度 D)最坏时间复杂度

6、A算法的时间复杂度为O(n3)，B算法的时间复杂度为O(2n)，则说明( )。 A)对于任何数据量，A算法的时间开销都比B算法小 B)随着问题规模n的增大，A算法比B算法有效 C)随着问题规模n的增大，B算法比A算法有效 D)对于任何数据量，B算法的时间开销都比A算法小 7、算法分析的目的是（ ）。

A)找出数据结构的合理性 B)研究算法中的输入和输出的关系 C)分析算法的效率以求改进 D)分析算法的易懂性和文档性 8、下面程序段的时间复杂度为（ ）。 for( i=0; i

A)O(m2) B) O(n2) C) O(m*n) D) O(m+n) 9、下面算法的时间复杂度为( )。 int f ( int n )

{ if ( n= =0 || n= =1 ) return 1; else return n*f (n-1); }

2

A) O(1) B) O(n) C) O(n) D) O(n!)

二、填空题

1、数据的( )结构依赖于计算机语言。

2、在线性结构中，第一个结点（ ）前驱结点,其余每个结点有且只有（ ）个前驱结点；最后一个结点（ ）后继结点；其余每个结点有且只有（ ）个后继结点。

41

3、在树形结构中,树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点；叶子结点没有（ ）结点，其余每个结点的后继结点可以（ ）。

4、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着( ) 、（ ）和（ ）的关系。

5、评价一个算法优劣的两个主要指标是（ ）和（ ）。

6、数据的逻辑结构被分为( )、( )、( )和( )四种。 7、数据的存储结构被分为( )、（ ）、（ ）、（ ）四种. 8、算法的时间复杂度除了与问题的规模有关外，还与输入实例的( )有关。

三、问答题与算法题

1、 简述下列概念：

数据元素： 数据结构： 数据类型：

数据的逻辑结构及其4种类型： 数据的存储结构及其4种方式：

2、设两个算法在同一台机器上执行，其执行时间分别是 n2和2 n ，要使前者快于后者，n至少需要多大？

3、有时为比较两个同数量级的算法优劣，须突出主项的常数因子，而将低次项用”O”记号表示。如：设T1 ( n ) = 1.39 n log n + 100 n + 256 = 1.39 n log n + O ( n ) ; T2 ( n ) = 2.0 n log n -2 n = 2.0 n log n –O( n ) ;

这两个式子表示，当n足够大时，T1 ( n )优于T2 ( n )，因为前者的系数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣。 (1 ) T1 ( n ) = 5n 2 -3 n +60 log n ; (2 ) T2 ( n ) = 3 n 2 +1000 n + 3 log n ; (3 ) T3 ( n ) = 8 n 2 + 3 log n ; (4 ) T4 ( n ) = 1.5 n 2 + O ( n ) 。

4、计算执行下面程序段时，执行S语句的次数为。 for(i=1; i<=n; i++)

for( j=1; j<=i; j++) S;

第二章 线性表

一、 选择题

1、线性表是具有n个（ ）的有限序列。

A) 数据项； B) 数据元素； C) 数据对象； D) 表元素。 2、以下关于线性表的说法不正确的是( )。

A) 线性表中的数据元素可以是数字、字符、记录等不同类型。 B) 线性表中包含的数据元素个数不是任意的。

C) 线性表中的每个结点都有且只有一个直接前趋和直接后继。

42

D) 存在这样的线性表：表中各结点都没有直接前趋和直接后继。 3、线性表的顺序存储结构是一种( )的存储结构。

A) 随机存取 B) 顺序存取 C) 索引存取 D) 散列存取

4、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。 A) 基地址 B) 结点大小 C) 线性表大小 D) 基地址和结点大小 5、下面关于线性表的叙述中，错误的是哪一个？（ ） A) 线性表采用顺序存储，必须占用一片连续的存储单元。 B) 线性表采用顺序存储，便于进行插入和删除操作。 C) 线性表采用链接存储，不必占用一片连续的存储单元。 D) 线性表采用链接存储，便于插入和删除操作。 6、线性表采用链表存储时其存储地址要求（ ）。 A) 必须是连续的； B) 部分地址必须是连续的； C) 必须是不连续的； D) 连续和不连续都可以。

7、一个长度为n的线性表顺序存储，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移 ( ) 个元素。

A) n-i B) n-i+1 C) n-i-1 D) i 8、( )运算中，使用顺序表比链表好。

A) 插入 B) 删除 C) 根据序号查找 D) 根据元素值查找

9、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n)

10、在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n)时，需要从前向后依次前移( )个元素。

A) n-i B) n-i+1 C) n-i-1 D) i

11、在一个长度为n的线性表中顺序查找值为x的元素时，平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。 A) n B) n/2 C) (n+1)/2 D) (n-1)/2

12、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则 执行的语句是( )。

A) HL = p; p->next = HL; B) p->next = HL; HL = p;

C) p->next = HL; p = HL; D) p->next = HL->next; HL->next = p;

13、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行( )。

A) q->next = p->next ; p->next = q; B) p->next = q->next; q = p;

C) q->next = p->next; p->next = q; D) p->next = q->next ; q->next = p;

14、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行( )。 A) p = q->next ; p->next = q->next; B) p = q->next ; q->next = p;

C) p = q->next ; q->next = p->next; D) q->next = q->next->next; q->next = q;

15、在双向链表中，在指针p所指的结点前插入一个指针q所指的结点，操作是（ ）。

A) p->Prior=q; q->Next=p; p->Prior->Next=q; q->Prior=q；

B) p->Prior=q; p->Prior->Next=q; q->Next=p; q->Prior=p->Prior; C) q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q; D) q->Prior=p->Prior; q->Next=q; p->Prior=q; p->next=q;

二、 填空题

43

1、对于一个具有n个结点的单链表，在已知结点*p的后插入一个新结点的时间复杂度为（ ）,在给定值为x的结点后插入一个新结点的时间复杂度为（ ）。 2、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成

（ ）和（ ）。

3、顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。

4、对于双向链表,在两个结点之间插入一个新结点需修改( )个指针，单链表为 ( )个。

5、循环单链表的最大优点是( ) 。

6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在( )结点的next域中。

7、带头结点的双循环链表L为空表的条件是（ ）。

8、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用( )存储结构。

9、求顺序表和单链表的长度算法的时间复杂度分别是 ( )和 ( )。 10、顺序表存储结构的优点是( )、( )、

( )；缺点是 ( )。

11、单链表存储结构的优点是( )、 ( )；缺点是

( )、 ( )。

12、在单链表中，设置头结点的作用是 ( ) 。

13、链接存储的特点是利用( )来表示数据元素之间的逻辑关系。 14、带头结点的双循环链表DL为空表的条件是：( )。

15、以下算法的功能是：在一个非递减的顺序表中，删除所有值相等的多余元素。在画线处填上适当的语句，将程序补充完整。 # define maxlen 100 typedef struct {

elemtype a[ maxlen ] ; int length ; } sqlist ;

void delequil ( sqlist & S ) { int j=1 , i = 2 ;

while ( _________________ ) { if ( S.a[ i ] != S.a[ j ] ) { ____________ ; ______________ ; } i ++ ; }

______________ ; }

16．设双链表的结点的存储结构如下：删除链表中指针p所指结点的两步主要操作是：

p Llink Data Rlink

44

( )， ( )。

三、 问答题与算法题

1、试描述头指针、头结点、首结点的区别、并说明头指针和头结点的作用。

2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

3、为什么在单循环链表中设置尾指针比设置头指针更好?

4、下述算法的功能是什么?

LinkList ABC(LinkList L){ // L 是无头结点单链表 if( L&&L->next )

{ Q=L; L=L->next; P=L; while (P->next) P=P->next; P->next=Q; Q->next=NULL; } return L; }

5、写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。 结点结构为：(prior,data,next)

p 10231530

6、Void AA(SqList &L, int i, int x)

{ if(i>=1&&i<=Length(L)) { FOR(j= Length (L);j>=i;j - -) A[j+1]=A[j]; A[i]=x; }

else exit(ERROR); }

45

假定调用该算法时线性表L的内容为（15，26，37，48，55），i为3, x为51，则调用返回后该单链表的内容变为什么?

7、重写建立单连表的算法CreatList_L(Linklist &L,int n )，要求顺序输入n个元素的值(即先输入a1,a2…..).

CreatList_L(LinkList &L ； int n)

8、设顺序表L是一个递减有序表，试写一算法，插入元素x，插入后仍保持L的有序性。 Void sinsert(Sqlist &S, int x)

9、写一算法，在带头结点的单链表上实现线性表的求表长ListLength(L)运算。 ．．．．

int ListLength(LinkList L)

10、写出从一个带头结点的单链表中删除其值等于给定值x的结点的算法函数。 ．．．． Int delete(LinkList &L, int x) {

46

11、已知递增有序的两个带头结点的单链表La，Lb分别存储了一个非空集合A,B。设计算．．．．法实现求两个集合的并集的运算A=A∪B

void mergelist(linklist &La, linklist Lb)

12、设计算法将不带表头结点的单向链表就地逆转。 ．．．．．．

13、删除整数数组中值相等的多余整数(只保留第一次出现的那个整数)。 Void delDuplicate(int A[]，int & n)

47

第三章 栈和队列

一、 选择题

1、对于栈，操作数据的原则是（ ）。

A) 先进先出 B) 后进先出 C) 后进后出 D) 不分顺序 2、一般情况下，将递归算法转换成非递归应通过设置（ ）实现。 A) 数组； B) 线性表； C) 队列； D) 栈。 3、栈和队列的共同点是（ ）

A) 都是先进后出 B) 都是先进先出 C) 只允许在端点处插入和删除元素 D) 没有共同点

4、若栈的入栈序列是abcde，则栈的不可能的输出序列是( )。 A) edcba B) decba C) dceab D) abcde 5、在对栈的操作中，能改变栈的结构的是( )。

A) StackLength(S) B) StackEmpty(S) C) GetTop(S) D) ClearStack(S) 6、在一个栈顶指针为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;

7、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是p1,p2,p3，…，pn，若p1=n，则pi=( )。

A) I B) n-i C) n-i+1 D) 不确定 8、若用一个大小为６的数组来实现循环队列，且当前尾指针rear和头指针front的值分别为０和３，当从队列中删除一个元素，再加入两个元素后，尾指针rear和头指针front的值分别是（ ）。

A) １和５； B) ２和４； C) ４和２； D) ５和１。 9、要使输入序列为ABC变为序列BAC时，使用的栈操作序列为（ ）

A)push,pop,push,pop,push,pop B)push,push,push,pop,pop,pop C)push,push,pop,pop,push,pop D)push,pop,push,push,pop,pop

10、设用一个大小m=60的顺序表A［m］表示一个循环队列，如果当前的尾指针rear=32，头指针front＝15, 则当前循环队列的元素个数是( )。 A) 42 ； B) 16 ； C) 17 ； D) 41 。

11、设用顺序表a[n]表示循环队列，头、尾指针分别为front和rear，则判断队列为空的条件是（ ），判断队列满的条件是（ ）。

（1）A) a.front +1= =a.rear ； B) a.front = = a.rear +1；

C) a.front = = 0 ； D) a.front = = a.rear。

（2） A) (a.rear -1) % n = a.front ； B) (a.rear +1) % n = a.front；

C) a.rear =( a.front-1) % n； D) a.rear = (a.front +1) % n 。 12、循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 A) rear=rear+1 B) rear=(rear+1) mod (m-1) C) rear=(rear+1) mod m D) rear=(rear+1) mod (m+1) 13、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。

A) 栈； B) 队列； C) 数组； D) 线性表。 14、设栈用向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。

48

A．V[++top]=x ; B. V [top++]=x; C. V[--top] =x ; D. V [top--]=x; 15、 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A. |top[2]-top[1]|=0 B. top[1]+1=top[2]

C. top[1]+top[2]=m D. top[1]=top[2] 16. 表达式a*(b+c)-d的后缀表达式是( )。【南京理工大学 2001 一、2（1.5分）】

A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

二、 填空题

1、在栈中，可进行插入和删除操作的一端称( )。 2、在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。 3、栈的特点是( )，队列的特点是（ ）。

4、由于链栈的操作只在链表头部进行，所以没有必要设置( )结点。 5、带头结点的单链表L是空表的条件是（ ）；顺序栈S是空栈的条件是（ ）；顺序栈S满的条件是（ ）；不带头结点的链栈L是空栈的条件是（ ）；循环队列Q是空队列的条件是（ ）；循环队列Q是满队列的条件是（ ）

6、用数组Q（其下标在0…n-1之间，共有n个元素）表示一个循环队列，front 为当前队头元素的前一个位置，rear为队尾元素的位置，假设队列中的元素个数总小于n，则求队列中元素个数的公式是（ ）。

7、设元素入栈的顺序是１、２、3、…、n ，则所有可能的出栈序列共有（ ）种。 8、在具有n个单元的循环队列中，队满时共有（ ）个元素。

9、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是( )，而栈顶指针值是( )H。(设栈为顺序栈，每个元素占4个字节)

10、用PUSH表示入栈操作，POP 表示出栈操作，若元素入栈的顺序为1234，为了得到1342的出栈顺序，相应的PUSH和POP的操作串为( )。

三、 问答题与算法题

1、 设将整数1，2，3，4依次进栈，若入、出栈次序为Push(s,1), Pop(s,x1),Push(s,2),Push(s,3),

Pop(s,x2), Pop(s,x3),Push(s,4), Pop(s,x4 ),则出栈的数字序列为何?

2、设用不带头结点的单链表表示栈，请分别写出入栈和出栈的算法。 (1) int push_L(Linkstack &s SelemType e)

49

(2) int pop_L(Linkstack &s SelemType &e)

3、假设用带头结点的单循环链表表示队列，并设置一个指向尾结点的指针（无头指针），请．．．．．．．．．．．．．．分别写出队列的入队和出队算法。

(1)int EnQueue_L(Queueptr &QL QelemType e)

(2)int DeQueue_L(Queueptr &QL QelemType &e)

4、指出下述程序段的功能是什么?

(1) void abc1(Stack &S)

{

int i， arr[64] , n=0 ;

while (! StackEmpty(S)) { Pop(S，e);arr[n++]=e};

for (i=0, i< n; i++) Push(S, arr[i]);

}

(2) Void abc2 (Stack S1, Stack & S2);

{ initstack(tmp);

while ( ! StackEmpty (S1))

{pop(S1,x); Push(tmp,x); } while ( ! StackEmpty (tmp) )

{Pop( tmp,x); Push( S1,x); Push( S2, x);}

50

}

(3) void abc3( Stack &S, int m) { InitStack (T);

while (! StackEmpty( S))

{ Pop(S,e); if( e!=m) Push( T,e); } while (! StackEmpty( T)) {Pop(T,e); Push(S,e);} }

(4) void abc4( Queue &Q)

{ InitStack( S);

while (! QueueEmpty( Q )) {DeQueue( Q,x); Push( S,x);} while (! StackEmpty( S)) { Pop(S,x); EnQueue( Q,x );} }

(5) void invert1( LinkList &L)。

{ p=L;

initstack(S);

while(p) //链表中的元素全部进栈 {push(S,p->data); p=p->next; }

p=L; //利用原来的链表只修改数据域的值（反序） while(!stackempt(S)) {pop(S,e); p->data=e; p=p->next;

}

return OK; }

5、回文是指正读反读均相同的字符序列，如\和\均是回文，但\不是回文。试写一个算法判定给定的用带头结点的单链表表示的字符串是否为回文。 ．．．．

Int hw1(linklist L)

51

6、写一个将不带头结点的链栈S中所有结点均删去的算法

void ClearStack( LinkStack &S)。

7、写一个返回不带头结点的链栈S中结点个数的算法. ．．．．．

int Stacksize( LinkStack S)。

8、利用栈操作，写一个算法把一个不带头结点的链表的元素反序存放（同第二章12题，这．．．．．里要求利用栈操作）。

void invert2( LinkList &L)。

9、试将下列递归过程改写为非递归过程。 void test(int &sum) { int x； scanf(x)； if(x=0) sum=0

else {test(sum); sum+=x;}

printf(sum)； }

52

10、从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$

第四章 串

一、 选择题

1、 串是一种特殊的线性表，其特殊性体现在( )。

A) 可以顺序存储 B) 数据元素是一个字符 C) 可以链接存储 D) 数据元素可以是多个字符 2、有两个串P和Q，求P在Q中首次出现的位置的运算称( )。 A ) 模式匹配 B) 连接 C) 求子串 D) 求串长

3、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。

2222

A） n B）(n/2)+(n/2) C）(n/2)+(n/2)-1 D） (n/2)-(n/2)-1

4、设串s1='ABCDEFG',s2='PQRST',函数concat(x,y)返回x和y串的连接串，subString(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，Strlength(s)返回串s的长度，则concat(subString(s1,2,Strlength(s2)),subString(s1,Strlength(s2),2)))的结果串是( )。 A) BCDEF B) BCDEFG C) BCPQRST D) BCDEFEF 5、顺序串中，根据空间分配方式的不同，可分为( )。

A) 直接分配和间接分配 B) 静态分配和动态分配 C) 顺序分配和链式分配 D) 随机分配和固定分配

6、设串S=”abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（ ）。

A) 8 ； B) 37； C) 36； D) 35。

7、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（ ）。

A) O(m) ； B) O(n)； C) O(m+n)； D) O(n* m)。 8、已知串S=‘aaab’,其Next数组值为（ ）。

A．0123 B．1123 C．1231 D．1211

二、 填空题

1、 在空串和空格串中，长度不为0的是( )。 2、 空格串是指( )，其长度等于( )。 3、按存储结构不同，串可分为( )、（ ）、（ ）。

53

4、C语言中，以字符( )表示串值的终结。

5、在块链串中，为了提高存储密度，应该增大( ).

6、假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占

( )个字节。 7、串操作虽然较多，但都可通过五种操作（ ）、（ ）、（ ）、 （ ）、（ ）构成的最小子集中的操作来实现。 8、设串S=’Ilikecomputer .’，T=’com’，则Length (S ) = （ ）。Index(S,T,1) = ( ) 9、在KMP算法中，next[j]只与（ ）串有关，而与（ ）串无关。 10、字符串’ababaaab’的nextval函数值为（ ）。

11、两个字符串相等的充分必要条件是（ ）。 12．实现字符串拷贝的函数 strcpy为：

void strcpy(char *s , char *t) /*copy t to s*/ { while ( ________ ) ； }

三、 问答题与算法题

1、 简述下列每对术语的区别： 空串和空格串： 串常量和串变量： 主串和子串： 目标串和模式串。

2、在C语言中假设有如下的串说明：

char s1[30]=\ (１)在执行下列语句后，s3的值是什么?

strcpy(s3,s1); strcat(s3,\ (２)调用函数strcmp(s1,s2)的返回值是什么? (３)调用函数strcmp(s1[5],\的返回值是什么? (４)调用函数strlen(strcat(s1,s2))的返回值是什么? ３、 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。

void StrInsert(char *S, char *T, int i)

54

4、利用C的库函数strlen 和strcpy(或strcpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 void StrDelete(char *S, int i ,int m) //串删除

5、若S和T是用结点大小为1的带头结点的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 Int indexst(LinkList S, linkLint T)

6、在KMP算法中，求下列模式串的next[j]。

（1） ‘abaabcac’ （2）’aaabaaba’

55

7、设目标为t=‘abcaabbabcabaacbacba’,模式为p=‘abcabaa’

（1）计算模式p的naxtval函数值；

（2）不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

11．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

第五章 数组与广义表

一、 选择题

1、稀疏矩阵的一般压缩方法是( )。

A) 二维数组 B) 广义表 C) 三元组表 D) 一维数组

?a11?a1n???2、设矩阵A??????是一个对称矩阵，为了节省空间，将其下三角部分按行优先

?a??n1?ann?存放在一维数组B中。对下三角矩阵中任一元素aij (i>=j)，在一维数组B中下标ｋ的值是( )。

A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+j 3、在稀疏矩阵的三元组表示法中，每个三元组表示( )。

A) 矩阵中数据元素的行号、列号和值 B) 矩阵中非零元素的值

C) 矩阵中非零元素的行号和列号 D) 矩阵中非零元素的行号、列号和值 4、对稀疏矩阵进行压缩存储是为了( )。

A) 便于进行矩阵运算 B) 便于输入和输出

C) 节约存储空间 D) 降低运算的时间复杂度

5、 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存

56

储单元，基地址为10，则LOC[5，5]=（ ）。

A） 808 B） 818 C）1010 D） 1020

6、 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。

A） BA+141 B） BA+180 C） BA+222 D） BA+225 7、广义表是线性表的推广，它们之间的区别在于( )。 A) 能否使用子表 B) 能否使用原子项 C) 表的长度 D) 是否能为空 8、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）。

A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)） 9、已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B),下列运算的结果是:

tail(head(tail(C))) =( )。 A）（a） B） A C） a D） (b) E） b F） (A) 10、 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。

A） ( ) B） c,d C） ((c,d)) D） d 11、广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。

A） a B）（） C）（a,b,c,d） D）（b,c,d） 12、设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。

A） 1和1 B） 1和3 C） 1和2 D）2和3 13、下面说法不正确的是( )。

A） 广义表的表头总是一个广义表 B） 广义表的表尾总是一个广义表 C） 广义表难以用顺序存储结构 D） 广义表可以是一个多层次的结构 14、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A）head(tail(LS)) B） tail(head(LS))

C）head(tail(head(tail(LS))) D) head(tail(tail(head(LS)))) 15、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为( )。

2

A) O(1) B) O(n) C) O(n) D) O(log2n)

二、 填空题

1、n维数组中的每个元素都最多有( )个直接前趋。

2、对于一个一维数组A[12]，若一个数据元素占用字节数为S，首地址为1，则A[i](i>=0)的存储地址为( )，若首地址为d，则A[i]的存储地址为( )。

3、已知二维数组A[m][n]采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A[0][0]），则A[i][j]的地址是( )。

4、 多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种

( )存取结构。

5、 矩阵的压缩存储就是为多个相同的非零元素分配( )个存储空间，零元素不分配空间。 6、递归是算法设计的重要方法，递归由（ ）项和（ ）项构成。用递归的方法求广义表LS的深度DEPTH(LS)，写出基本项和递归项。 基本项：

57

递归项：

7、广义表( a , ( a , b ) , d , e , ((i , j ) , k ) ) 的长度是（ ），深度是（ ）。 8、广义表((a) , (( b ) , c ) , (((d )))) 的长度是（ ），深度是（ ）。

9、设广义表S=((a , b) , ( c , d))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则 GetHeat(GetTail(S)) = ( ) ， GetTail (GetHeat (S)) =( )。

10、设广义表S=(a , b , ( c , d) , (e , (f , g )))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则GetHeat(GetTail(GetHeat (GetTail(GetTail(S)))))= ( ) 11、二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是( ) 。(设a[0][0][0]的地址是1000,数据以行为主方式存储) 12、设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为( ) 。

13、己知三对角矩阵A[1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为 ( ) 。 14、广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是（ ）。 15、设广义表A((( ),(a,(b),c)))，则head(tail(head(tail(head(A))))=（ ）。

三、 问答题与算法题

１、给出C语言的三维数组A[m][n][s]地址计算公式。

?a11??a21２、设有三对角矩阵 An╳n=?0????0?a12a22a32?00a23a33?0????ann?10??0?0?，将其三条对角线上的元素逐行???ann??地存储到向量B[0...3n-3]中，使得B[k]=aij,求：

(1)用i , j 表示k的下标变换公式。

(2)用 k 表示 i,j 的下标变换公式。

３、设二维数组A5╳6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点A45的起始地位为何? 按行和按列优先存储时，A25的起始地址分别为何?

58

4、已知一个稀疏矩阵如下图所示：

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

(1) 写出它的三元组顺序存储表示；

(2) 给出它的行逻辑链接的顺序存储表示；

(3)

5、画出下列广义表的图形表示：

(1) A=((a,b),(c,d)) (2) B=(a,(b,(c,d)),(e))

6、画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。

59

7、画出广义表LS=(( (b , c) , d ), (a) , ((a) , ( (b , c) , d )) , e , ( ))的具有共享结构的存储表示。 8、设广义表LS=(soldier , (teacher , student) , ( worker , farmer ) )，用取表头函数GetHead ( ) 和

取表尾函数GetTail ( )分离出原子student 。

9、画出下列矩阵的十字链表

?0??7 ?0??2?280??009?

300??062??

10、设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。

第六章 树和二叉树

一、选择题

1、设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少有（ B ）个，至多有（E ）个。

A) 2h ； B) 2h-1 ； C) 2h+1； D) 2 h-1； E) 2 h -1； F) 2 h +1。

2、高度为h的完全二叉树至少有（ D ）个结点，至多有（ B）个结点。 A) 2 h ； B) 2 h -1 ； C) 2 h +1； D) 2 h –1 。 3、具有n个结点的满二叉树有（ ）个叶结点。

A) n/2 ； B) (n-1)/2； C) (n+1)/2； D) n/2+1。 4、一棵具有n个叶结点的哈夫曼树，共有（ ）个结点。 A) 2n B) 2n-1 C) 2n+1 D) 2 n -1；

60

5、一棵具有25个叶结点的完全二叉树最多有（ ）个结点。 A) 48； B) 49； C) 50； D) 51。

6、已知二叉树的前序遍历序列ABCDEF,中序遍历序列CBAEDF,则后序遍历序列是（ ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 ７、已知二叉树的中序遍历序列是debac，后序遍历序列是dabec，则前序遍历序列是（ ）。 A) acbed； B) decab； C) deabc； D) cedba。 8、在线索化二叉树中，t所指结点没有左子树的充要条件是（ ）。

A) t->left=null B) t->ltag=1 C) t->ltag=1且t->left=null D) 以上都不对 9、如图所示的4棵二叉树中，（ ）不是完全二叉树。

A B C D 10、算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++

11、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）个。

A．5 B．6 C．7 D．8

12、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。

A．M1 B．M1+M2 C．M3 D．M2+M3 13、具有10个叶结点的二叉树中有（ ）个度为2的结点，

A．8 B．9 C．10 D．ll 14、一个具有1025个结点的二叉树的高h为（ ）

A．11 B．10 C．11至1025之间 D．10至1024之间

15、对于前序遍历与中序遍历结果相同的二叉树为（ ）;对于前序遍历和后序遍历结果相同的二叉树为（ ）的二叉树。

A．空二叉树 B．只有根结点 C．根结点无左孩子 D．根结点无右孩子

E．空二叉树或所有非叶结点只有左子数 F．空二叉树或所有非叶结点只有右子树 16、．一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）

A．所有非叶结点均无左孩子 B．所有非叶结点均无右孩子 C．只有一个叶子结点 D．A和B同时成立

17、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。

A．空或只有一个根结点 B．任一非叶结点无左子树 C．高度等于其结点数 D．任一非叶结点无右子树 18、线索二叉树是一种（ ）结构。

A． 逻辑 B． 逻辑和存储 C． 物理 D．线性 19、n个结点的线索二叉树上含有的线索数为（ ）

A．2n B．n－l C．n＋l D．n 20、由3 个结点可以构造出多少种不同的二叉树？（ ）

A．2 B．3 C．4 D．5

二．填空题

61

1、含有100个结点的树有( )条边。

2、一棵二叉树有67个结点，结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个。

3、含A、B、C三个结点的不同形态的树有（ ）棵，不同形态的二叉树有（ ）棵。 4、一棵含有n个结点的2叉树，可能达到的最大深度是（ ）和最小深度是（ ）。 5、一棵哈夫曼树有19个结点，则其叶子结点的个数是( )。

6、设二叉树的中序遍历序列是：ABCDEFG，后序遍历序列是：BDCAFGE。则该二叉树的前序遍历序列是：（ ），该二叉树的对应的森林包含（ ）棵树。

7、将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1..50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素( )中。

8、已知一棵树T的边集为{（I ，M），（I ，N），（E ，I），（B ，E），（B ，D），（C ，B），（G ，J），（G ，K），（A ，G），（A ，F），（H ，L），（A ，H），（C ，A）}。则该树的根结点是（ ）、叶结点是：（ ）、树的深度是：（ ）。

9、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有（ ）个叶子结点。

10、一棵有n个结点的满二叉树有（ ）个度为1的结点、有（ ）个分支 （非终端）结点和（ ）个叶子，该满二叉树的深度为（ ）。 11、．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有（ ）结点，右子树中有（ ）个结点。

12、含4个度为2的结点和5个叶子结点的完全二叉树，可有（ ）个度为1的结点。 13、一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为（ ）。 14、n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是（ ）。它共有（ ）个叶子结点和（ ）个非叶子结点，其中深度最大的那棵树的深度是（ ），它共有（ ）个叶子结点和（ ）个非叶子结点。

15、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是（ ）。 16、有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是（ ），带权路径长度WPL为（ ）。

17、现有按中序遍历二叉树的结果为abc，问有（ ）种不同的二叉树可以得到这一遍历结果。 18、．一个无序序列可以通过构造一棵（ ）树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

19、先根次序遍历森林正好等同于按（ ）遍历对应的二叉树；后根次序遍历森林正好等同于（ ）遍历对应的二叉树。

20、有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，则字符c的哈夫曼编码是（ ），电文的编码总长度为（ ）。 问答题与算法题

１、void ABC(BiTree BT)

{ if (BT= =NULL) return; ABC(BT->lchild);

Printf(“%c”,BT->data); ABC(BT->rchild);

62

}

该算法的功能是______________________________________

请模仿写出另外两个类似此算法的算法，并标明这两个算法的功能。

2、写出下列算法的功能．

Void LevelOrderTraverse (BiTree T, Status (*vist)(TelemType e)) {InitQueue(Q);EnQueue(Q,T);

While(!QueueEmpty(Q))

{DeQueue(Q,p);if(Visit(p->data)) return ERROR; if(p->lchild) EnQueue(Q, p->lchild); if(p->rchild) EnQueue(Q, p->rchild); }

return OK; }

3、写出下列算法的功能．

Status PreOrderTraverse (BiTree T, Status (* Visit)(TelemType(e))) { InitStack(S);Push(S,T);

While(!StackEmpty(Q))

{ Pop(S,p);if(Visit(p->data)) return ERROR; if(p->rchild) Push(S, p->rchild); if(p->lchild) Push(S, p->lchild); }

return OK; }

4、写出下列算法的功能．

void ABC ( BiTree BT , int & c1, int & c2 ) { if ( BT ! = NULL)

{ ABC ( BT-> lchild , c1,c2 ); c1 ++ ;

if ( BT -> lchild = = NULL && BT ->rchild = = NULL ) c2 ++; ABC ( BT -> rchild , c1 , c2 ); }

63

}

5、已知二叉树T的数据域均为正数，写一个算法求数据域的最大值。Int maxdata(Bitree T)

6、已知非空二叉树T的数据域均为字符型数据，数据域的值是’A’只有一个结点，写一个算法求这个结点的双亲。Char Parent(Bitree T)

7、已知非空二叉树T，写一个算法求两度点的个数。

8、用递归方法写一个算法求二叉树的叶子数int Leafnum( BiTree T),先写出基本项和归纳项，然后写算法

9、写一个算法求二叉树的深度 int Depth( BiTree T)

64

10、写一个算法交换二叉树所有结点的左右子树 Status Changchild( BiTree T)

11、试分别画出具有3个结点的有序树和3个结点的二叉树的所有不同形态。

12、一棵有11个结点的二叉树的静态链表存储结构如下表。 Lift[i]

6 7 8 5 2 Data[i]

m f a k b l c r d Right[i]

9 10 4 11 1

画出该二叉树，将此二叉树转化为树或森林。

13、已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

14、对于n个结点的完全二叉树，用1~n的连续整数顺序编号，试回答下列问题：

65

s e （1） 它共有多少层？各层的结点数分别是多少？

（2） 各层最左边的结点的编号分别是多少？各层最右边的结点的编号分别是多少？ （3） 对于编号为i(1?i?n)的结点，它的层是多少？它的双亲（若存在）的编号是

多少？它的左孩（若存在）和右孩（若存在）的编号分别是多少？

15、下图所示的森林：

(1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树；

16、对于如下所示的图，试写出其先序、中序和后序以及按层遍历的结果，并画出其顺序存储结构和二叉链表存储结构。

17、试画出上题所示的二叉树的先序线索二叉树和后序线索二叉树。

66

18、分别画出下图所示各棵树所对应的二叉树，然后将这些二叉树连接成一棵树。 A F H

B C D G I J

E K

19、欲传输一段电文如下：CATEATDATACAECATAEA AE

请你设计出这段电文中的每个字符的哈夫曼二进制编码。并计算整段电文的编码长度．

20、给定叶子结点的权值集合{15，3，14，2，6，9，16，17}，构造相应的哈夫曼树，并计算它的带权路径长度。

67

第七章 图

一、 选择题

1、一个具有n个顶点的无向连通图最多有（ ）边，最少有（ ）边。

A) n2； B) n(n-1)； C) n(n-1)/2； D) n； E) n-1； F) n+1。

2、一个具有n个顶点的有向强连通图最多有（ ）边，最少有（ ）边。

A) n2； B) n(n-1) ； C) n(n-1)/2； D) n； E) n-1； F) n+1。

3、在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A）1； B）2； C）1/2 ； D）4。

4、有N个顶点的有向图用邻接矩阵A表示时，顶点入Vi的度是（ ）。

A．

?A[i,j]i?1n B．

?A?i,j?j?1n C．

?A[j,i]i?1n D．

?A[i,j]?A?j,i?i?1nn+

j?1

5、．无向图G=(V,E),其中：V={a,b,c,d,e,f},

E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 6、下面哪一方法可以判断出一个有向图是否有环（回路）：

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 7、图1给出一个无向图。从顶点1出发，DFS遍历的输出序列是（ ），BFS遍历的输出序列是（ ）。

A)1354267； B)1347625； C)1534276； D)1247653。

8、已知有8个顶点A、B、C、D、E、F、G、H的无向图，其邻接矩阵存储结构如下表。从A点开始， DFS遍历的输出序列是（ ）。

A)BCDGHFE； B)ABCDGFHE； C)ABGHFECD； D)ABFHEGDC。

A B C D E F G H A 0 1 0 1 0 0 0 0 B 1 0 1 0 1 1 1 0 C 0 1 0 1 0 0 0 0 D 1 0 1 0 0 0 1 0 E 0 1 0 0 0 0 0 1 F 0 1 0 0 0 0 1 1 G 0 1 0 1 0 1 0 1 H 0 0 0 0 1 1 1 0 68

9、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A．逆拓扑有序 B．拓扑有序 C．无序的

10、已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是（ (1) ），BFS遍历的输出序列是（ (2) ）。

（1）A)12354； B)12345； C)13452； D)14352。 （2）A)12345； B)13245； C)12354； D)14352。

11、设图有n个顶点和e条边，则采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

23

A. O(n) B. O(n+e) C. O(n) D. O(n)

12、设图有n个顶点和e条边， 求解最短路径的Floyd算法的时间复杂度为( )。

A．O（n） B. O（n+ e） C. O（n*n） D. O（n*n*n）

二、 填空题

1、在一个图中,所有顶点的度数之和等于所有边数的（ ）倍。

2、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 3、具有4个顶点的无向完全图有（ ）条边。

4、具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 5、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（ ）。 6、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（ ），．．．所有邻接表中的结点总数是（ ）。

7、图的深度优先遍历算法类似于二叉树的（ ）遍历；图的宽度优先遍历算法类似于二叉树的（ ）遍历

8、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）度优先遍历算法。

9、在一个无向图的邻接表中，若表结点的个数是m， 则图中边的条数是( )条。 10、具有n个顶点的图，求最小生成树的Prim算法时间复杂度是（ ）。它适用 （ ）图。

11、具有e条边的图，求最小生成树的Kuruscal算法时间复杂度是（ ）。它适用 （ ）图。

12、具有n个顶点和ｍ条边的图，采用邻接表存储结构。则深度优先搜索算法DFS、广度优先搜索算法BFS、求拓扑排序、求关键路径的时间复杂度是都是（ ）。 13、求n个顶点的有向图某顶点到其他各顶点的最短路径的Dijkstra算法时间复杂度是（ ）。14、n个顶点的有向图每对顶点间最短路径的Floyd算法时间复杂度是____________ 。 15、如果含n个顶点n条边的无向图成一个环，则该图有多少棵生成树。____________ 。 16、G是一个非连通的无向图，共有28条边，则该图至少有多少顶点。__________ 。 17、一个含n个顶点的无向连通图的每条边的权重都是a(a>0),则它的最小生成树的权重等

69

于（ ）。

18、已知有向图的邻接矩阵为A 5?6，试问该矩阵的第3行的非零元素之和表示（ ），第3行的非零元素之和表示（ ）。

三、 问答题与算法题

１、在下图所示的各无向图中：

(１)哪些图是连通图?对非连通图给出其连通分量。 (２)哪些图是森林?

２、在右图所给的有向图中：

(1) 请给出每个顶点的度，入度和出度。

(2) 请给出其邻接矩阵、邻接表及逆邻接表。

３、已知右边所给的有向图，求： （1）邻接表； （2）逆邻接表； （3）画出十字链表。

４、已知如下图所示的无向图，求： （1）邻接矩阵； （2）邻接表；

70

1 3 5 2 4 1 2 3 4 5

5、对下图所示的连通图，请用Prim算法构造其最小生成树。

6、用Kruskal算法求下图的最小生成树(写出步骤)。

12

① ② 8 5 15 20 ③ 6 ④ 10 ⑤ 4 8 9 ⑥

7、已知AOE网如图5：顶点表示活动，弧及权重表示活动持续的时间（单位为天）。找出所有关键路径；求出活动V3的最早开始时间。

71

8、已知如下所示的有向图，试列出图中的全部可能的拓扑有序序列。

1 2 3

5 6 4

9、已知一个图的顶点集V和边集G分别为： V={0，1，2，3，4，5，6，7，8}

E={<0，1>，<0，2>，<1，3>，<1，4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>，

<4，8>，<5，7>，<6，7>，<7，8>} 。若采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按照教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（答案是惟一的）。

10、已知一个图如下：

1）分别写出从顶点1开始的DFS和BFS遍历序列； 2）找出一棵生成树；

3）求顶点4到各点的最短路径；

11、A,B是图G的两个顶点。写一个算法，判断他们是否连通。

Int AlinkB(Graph G, VertexType A, VertexType B)

72

12、写一个算法，求图G的连通分支数。

Int num(Graph G)

第九章 查找

一、 选择题

1、对线性表进行二分查找时，要求线性表必须（ ）。

A) 以顺序方式存储； B) 以顺序方式存储，且结点按关键字值有序排列； C) 以链接方式存储； D) 以链接方式存储，且结点按关键字值有序排列。

2、用二分查找法查找具有n个结点的线性表时，查找每个元素的平均比较次数是（ ）。

A) O（n2）； B) O（n*log2 n）； C) O（n）； D) O（log2 n）。

3、利用逐个插入结点的方法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉树排序以后，查找元素35时，需要进行（ ）次元素比较。

A) 4； B) 5； C) 7； D) 10。

4、设哈希表的长度为m=14，哈希函数H（key）= key MOD 11，表中已有4个结点，其地址分别是：addr（15）= 4；addr（38）= 5；addr（61）= 6；addr（84）= 7；其余地址空。如果采用二次探测再散列处理冲突，则关键字49的结点的地址是（ ）。

A) 8； B)3 ； C) 5； D) 9。

5、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有（ ）结点。

A) 2 k-1-1； B) 2 k-1+1； C) 2 k -1； D) 2 k +1。

6、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素查找概率相等的情况下，查找成功所需的平均比较次数为（ ）。

A)35/12； B)37/12； C)39/12； D)43/12。

7、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A)顺序存储结构 B)链式存储结构 C)索引存储结构 D)散列存储结构 8、具有5层结点的平衡二叉树至少有（ ）个结点。

A) 12； B)11； C) 10； D) 9。 9、既希望较快的查找又便于线性表动态变化的查找方法是 ( ) A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找

10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR

11、设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链 地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个 记录。

73

A．1 B. 2 C. 3 D. 4

12、假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次

13、散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。

A. 同等概率 B. 最小概率 C. 最大概率 D. 平均概率

14、散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并

将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的地址是（ ）。

A． 8 B. 9 C. 10 D. 11

（2）存放元素59需要搜索的次数是（ ）。

A． 2 B. 3 C. 4 D. 5

15、下面关于B和B+树的叙述中，不正确的是( )

A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。 C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。 16、二叉查找树的查找效率与二叉树的( （1） )有关, 在 ( （2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 二、填空题

１、己知一个有序表为(1,8,12,25,29,32,40,62,98),当二分查找值为29和98的元素时,分别需要( )次和( )次比较才能查找成功；若采用顺序查找时,分别需要( )次和( )次比较才能查找成功。

２、采用散列（Hash）技术进行查找，需要解决的两个问题是（ ）、（ ）。

３、在各种查找方法中，平均查找长度与结点个数n无关的是（ ）。 4、对于长度为255的表，采用分块查找，每块的最佳长度为（ ）。 长度是（ ）。对哈希表查找，若用链表处理冲突，则平均查找长度是（ ）。 ５、在分块查找中，对256个元素组成的线性表分成（ ）块最好，每块最佳长度是（ ）。若每块的长度是8，则平均查找长度是（ ）。

6、在n个记录的有序顺序表中进行折半查找，最大比较次数是（ ）。

7、假设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少需要进行（ ）次探测

8、设有一个长度为10的已排好序的表，用二分查找法进行查找，若查找不成功，至少与关键字比较（ ）次。

9、高度为8的平衡二叉树的结点数至少有（ ）个。

10、动态查找表和静态查找表的重要区别在于前者包含有（ ）和（ ）运算，而后者不包含这两种运算。

11、查找算法基本上分成（ ）查找，（ ）查找和（ ）查找三类。处理哈希冲突的方法有（ ）、（ ）、（ ）和（ ）四种。 12、以下是有序的二分查找的递归算法，在画线处填入适当成分将算法补充完整。 int Binsch(ElemTye A[ ] , int low , int high ,KeyType K)

{ if ( ) { int mid = (low + high) / 2;

if ( )return mid; //查找成功，返回元素的下标

74

else if (K < A[mid].key)

return Binsch(A , low , mid –1 , K ); //在左子表上继续查找

else return ; //在右子表上继续查找 }

else ; //查找失败，返回 -1 }

三． 问答题与算法题 1、画出对长度为10的有序线性表进行折半查找的一棵判定树，并求其在等概率时查找成功的平均查找长度。

2、计算以下二叉树在等概率条件下,查找成功和失败时的平均查找长度。 ASL成功＝（ ）,ASL失败＝（ ）.

⑥ ⑤ ⑨ ② ⑦ ⑩ ① ④

3、用序列（46，88，45，39，70，58，101，10，66，34）建立一棵二叉排序树，画出此树，并求在等概率情况下查找成功时的平均查找长度。

4、给定的一组关键字K={4，5，2，3，6，1}，试按二叉排序树生成规则画出这棵二叉排序树，并说明用这组关键字以不同的次序输入后建立起来的二叉排序树的形态是否相同？当以中序遍历这些二叉排序树时，其遍历结果是否相同？为什么？

75

5、设有二叉排序树，画出依次插入8，3后的情形。

⑥ ⑤ ⑨ ② ⑦ ⑩ ① ④

6、设上题（5题插入前的）所示的二叉排序树，画出依次删除5，6后的情形。

7、构造以{4,5,7,2,1,3,6}为关键字的平衡二叉树,并注明用了何种旋转．(写出步骤)

8、设有3阶B-树（图5），画出依次插入18，33，97后的B-树。

43

26 55 60

16 35 41 48 57 66 88

图5

76

9、在上题的B-树上（图5），分别画出删除66，16，43后的B-树（都从图5出发）。

10、设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

11、已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表：

` 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。

77

12、有字集合K= {15，22，50，13，20，36，28，48，31，41，18}，散列表地址空间为HT [ 0..15 ]，散列函数H（K）= K MOD 13，采用二次探测再散列的开放地址法解决冲突，试将K值填入HT中，并把查找每个关键字所需的比较次数m填入下表中，然后计算出查找成功时的平均查找长度。 I K M 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

13、编写在以BT为树根指针的二叉搜索树上进行查找值为key的结点的非递归算法。 BiTree search(BiTree BT , keytype key)

14、已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉树，画出插入完成后的平衡二叉树，并求其在等概率的情况下查找成功的平均查找长度。

15、写出从哈希表中删除关键字为K的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。

78

16、设二叉排序树中结点的结构为下述三个域构成: 数据域data；左孩子结点地址left； 右孩子结点地址right。 设data 域为正整数，该二叉树的根结点地址为T。 现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除掉。

第十章 内部排序

一、 选择题

1、在下列排序算法中，稳定的是（ ），平均速度最快的是（ ），所需辅助存储空间最多的是（ ）。

A．希尔排序； B．快速排序； C．堆排序； D．归并排序。

2、若要在O（n.log 2 n）数量级的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法应该是（ ）。

A．快速排序； B．堆排序； C．归并排序； D．希尔排序。

3、在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。

A． 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序 4、一组纪录的关键码序列是（46，79，56，38，40，84），则用堆排序方法建立的初始大根堆是（ ）。

A．79，46，56，38，40，84； B．84，79，56，38，40，46； C．84，79，56，46，40，38； D．84，56，79，40，46，38。 5、一组纪录的关键码序列是（46，79，56，38，40，84），则用快速排序方法，以第一个关键字为基准，得到的第一次划分结果是（ ）。

A．38，40，46，56，79，84； B．40，38，46，79，56，84； C．40，38，46，56，79，84； D．40，38，46，84，56，79。

6、一组纪录的关键码序列是（25，48，16，35，79，82，23，40，36，72），用二路归并排序方法进行排序，则第二趟归并的结果是（ ）。

A．16，25，35，48，23，40，79，82，36，72； B．16，25，35，48，79，82，23，36，40，72； C．16，25，35，46，23，36，40，79，82，72； D．16，25，35，48，79，23，36，40，72，82。

7、在以下排序方法中，关键字比较的次数与记录的初始排列次序有关的是（ ）。

79

A．归并排序； B．堆排序； C．插入排序； D．选择排序。 8、下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 A、堆排序 B、冒泡排序 C、希尔排序 D、快速排序

9、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 10、直接插入排序在最好的情况下，其时间复杂度为（ ）。

A. O（log n）； B．O（n）； C．O（n 2）； D．O（n*log n）。

11、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。

A. 选择 B. 冒泡 C. 快速 D. 插入

12、下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序

13、在文件\局部有序\或文件长度较小的情况下，最佳内部排序的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D. 快速排序

14、如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用

（ ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序

15、对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的

是（ ）算法。

A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序 16、起泡排序在最好情况下的时间复杂度为（ ）

2

A． O(logn) B． O(n) C． O(n*logn) D． O(n)

二、填空题

1、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的（ ）

和记录的（ ）。

2

2、不受待排序初始序列的影响，时间复杂度为O(n)的排序算法是（ ）。

3、分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，最省时间的是

（ ）算法，最费时间的是（ ）算法。 4、设有字符序列（Q,H,C,Y,P,A,M,S,E,D,F,X），则用初始步长为4的希尔排序方法将其按字

符升序排序，第一趟扫描的结果是（ ）。 5、快速排序的最大递归深度是（ ），最小递归深度是（ ）。

6、对n个元素的序列利用起泡法排序时，最好情况时的最少比较次数是（ ）。

7、在插入序排、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是（ ），需要辅助内存空间最大的是（ ）。 8、在插入序排、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序算法不稳定的有（ ）。

9、在插入排序和选择排序两种算法中，若待排序的序列已基本正序，则选用（ ）较好，若待排序的序列已基本反序，则选用（ ）较好。

10、在堆排序和快速排序两种算法中，若待排序的序列已基本有序，则选用（ ）较好，若待排序的序列完全无序，则选用（ ）较好

80

三． 问答题与算法题

1、已知序列（10，18，4，3，6，12，1，9，18，8）请用希尔排序(增量d1=3,d2=1),写出每一趟排序的结果。

2、已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 （每次取第一个元素的关键字为支点）

3、已知序列（10，18，4，3，12，9，18，8）请用堆排序写出每一趟（建好初始堆，L.r[1]与 L.r[n]互换后为第一趟）排序的结果。

4、已知关键字序列（K1，K2，K3，…，Kn-1）是大根堆。

(1) 试写出一算法将（K1，K2，K3，…，Kn-1，Kn）调整为大根堆； (2) 利用（1）的算法写一个建大根堆的算法。

参考答案

第一章、绪论

一、选择题 1 B； 2 A； 3 B； 4 C ；5 C； 6 B； 7 C； 8 C； 9 B。

81

二、填空题1、存储 ；2、无 ，1，无，1； 3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；7、顺序结构，链式结构，索引结构，散列结构；8、顺序。 三、问答题与算法题 1、3 ；

2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ;

T4 ( n ) = 1.5 n 2 + O ( n ) 。T4 ( n ) 较优，T3 ( n )较劣。

3、T4 ( n )较优 ，T3 ( n )较劣； 4．1+2+3+…+n = n(n+1)/2

第二章 线性表

一、选择题 1B；2C；3A；4D；5B；6D；7B；8C；9B；10A；11C；12D；13D；14C. 15 C；

二、填空题 1、O ( 1 ), O ( n )；2、单链表，双链表；3、相邻地址，指针；4、4，2； 5、便于从任何头结处开始查找；6、前驱；7、L->next== L且L->prior== L；8、顺序。 9．、O ( 1 ), O ( n )；10．逻辑顺序与物理顺序一致、可随机访问、节省存储空间、占用连续存储空间、不便于插入、删除和动态增长。11．不需占用连续存储空间，便于插入、删除和动态增长，不能随机访问、只能顺序存取，需额外存储空间、12．在任何位置查入和删除操作一致。13．指针 14．DL->next = DL->prior = DL 15．(1)i<=S. length ∥L.length 为元素个数

(2) j++ ∥有值不相等的元素 (3)S.a[j]:=S.a[i] ∥元素前移 (4)L. length =j ∥元素个数

16．p->prior->next = p->next ; p->next->prior = p->prior 三、问答题与算法题

1、头指针：结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址，从头指

针出发可以找到链表中所有结点的信息。

头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。

其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。

首结点：是链表的第一个结点。

2、(1)基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

(2)基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

3、尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)

4、:将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针

5、S=P->Prior; P->Prior=S->Prior; S->Prior->Next=P; S->Prior=P;

82

S->Next=P->Next; P->Next=S; S->Next->Prior=S; 6、15，26，51，37，48，55。

7、CreatList_L(LinkList &L int n) {

L= (LinkList) molloc (sizeof (Lnode)); // 建立头结点 L->next==NULL; q=L;

For(i=1;i<=n;++i)

{ P= (LinkList) molloc (sizeof (Lnode));

Scanf(&(p->data));

p->next=NULL; q->next=p; q=p; }

returen OK; }

8、Void sinsert(Sqlist &S, int x) {int i=0; n=S.Length;

while(x

if(i= =n) S.elem[n]= x; //插在最后一个结点的后面 else {for(j=n-1;j>=i;j++)

S.elem[j+1]=S.elem[j]; //元素后移 S.elem[i]=x; //插入 }

}

9、int ListLength(LinkList L)

{ q=L->next; i=0; while (q)

{i++; q=q->next; }

return i; }

10、int delete(LinkList &L, int x) {

p=L->next; //p为定位指针

q=L; //q为定位指针的前导 while((p->data!=x) && p)

{ q=p; //q前进 p=p->next; //p前进 }

if(!q) return ERROR; //查找失败 q->next=p->next ; free(p); return OK; }

11、void mergelist(linklist &La, linklist Lb) {pa=La->next; pb=Lb->next;pc=La; while (pa && pb)

if (pa->data< pa->data)

{pc->next=pa;pc=pa;pa=pa->next;}

83

else if(pa->data== pa->data)

{pc->next=pa; pc=pa; pa=pa->next; pb=pb->next;}

else ({pc->next=pb;pc=pb;pb=pb->next;} pc->next=pa? pb:pb; }

12、Void invertlinklist(linklist &L) {if(!L) return OK; //空表 p=L->next;

if(!p) return OK; //仅有一个结点的表 else{q=p->next; //q指向p的后继 p->next=NULL; while(q)

{ r=q->next ; //r指向q的后继 q->next=p; //逆置

p=q; //p前进 q=r; //q前进

}

L=p; //第一个结点 } }

13、Void delDuplicate(int A[]，int & n)

{ for(i=0;i

for(j=i+1;j<=n-1;j++) if(a[i]==a[j]) {n--;

for(k=j+1;k<=n-1;k++) a[k-1]=a[k]; } }

第三章 栈和队列

一、选择题1B；2D；3C；4C；5D；6C；7C；8B；9C；10C；11Ｄ，Ｂ；12Ｄ；13Ｂ；

14C；15B；16B。

二、填空题 1、栈顶；2、满，空，n；3、后进先出，先进先出；4、头；5、L->next==NULL，S.top==S.base， S.top-S.base==S.stacksize，L==NULL，Q.front==Q.rear，（Q.rear＋１）%maxQsize ==Q.front; 6、Q.rear-Q.front+n)%n； 7、

1nC2n； 8、n-1 9、2，1008； n?110、push 、pop、push、push、pop、push、pop、pop. 三、问答题与算法题 2、 １３２４；

2、(1) int push_L(Linkstack &s SelemType e) { p= (LinkStack) molloc (sizeof (Snode)); if (!p) return ERROR;

84

p->data=e; p->next=s; s=p;

Return Ok; }

(2) int pop_L(Linkstack &s SelemType &e) { if (!S) return ERROR;

q = s;

e = s->data; s=s->next; free (q); Retuen Ok; }

3、(1)int EnQueue_L(Queueptr &QL QelemType e) { p= Queueptr} molloc (sizeof (Qnode)); if(!p) return ERROR; p->data=e;

p->next=QL->next->next; QL->next->next= p; Retuen Ok; }

(2)int DeQueue_L(Queueptr &QL QelemType &e) { if(QL->next==QL)} return ERROR; p= QL->next

while(p->next!=QL) p =p->next; p->next=QL->next; e=QL->next;

free(QL); QL=p; Return Ok;

}

4、(1) 栈S元素反序存放； (2) 把栈s1复制到s2；

(3) 把栈S中值等于m的元素删除； (4) 队列Q元素反序存放; (5) 链表中的元素反序存放； 5、Int hw (LinkList L) { initstack(S);

bool=1;n=0; p=L->next;

while(p){n++; p=p->next;} //求串长

p=L->next; //p指向第一个结点 for(i=0; idata); p=p->next;} if(n%2= =1) p=p->next;

85

while(p&&bool) {pop(S,ch);

if(ch!=p->data) bool=0;

p=p->next; }

return bool; ｝

6、void ClearStack( LinkStack &S)。

{while (!S) {p=s;

s=s->next; free(p); }

return OK; }

7、int Stacksize( LinkStack S)。

{ n=0; p=s; While(!p) {n++; p=p->next;

}

return n;

}

8、见４、(5)

9、void test(int &sum)

{ int x,sun=0; initstack(S);

scanf(“%d”,&x);

while(x) { push(S,x); scanf(“%d”,&x); } while(!emptystack(S)) { pop(S,x); sum+=x; }

printf(“sum=%d\\n”,sum) ;

}

10、float expr( )

//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。 ｛float OPND[30]; // OPND是操作数栈。 init(OPND); //两栈初始化。 float num=0.0; //数字初始化。 scanf (“%c”,&x);//x是字符型变量。 while(x!=’$’) {switch

{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数 if(x!=’.’) //处理整数

{num=num*10+（ord(x)-ord(‘0’)）; scanf(“%c”,&x);}

else //处理小数部分。

86

{scale=10.0; scanf(“%c”,&x); while(x>=’0’&&x<=’9’)

{num=num+(ord(x)-ord(‘0’)/scale; scale=scale*10; scanf(“%c”,&x); } }//else

push(OPND,num); num=0.0;//数入栈，下个数初始化 case x=‘ ’:break; //遇空格，继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch

scanf(“%c”,&x);//读入表达式中下一个字符。 }//结束while（x！=‘$’）

printf(“后缀表达式的值为%f”,pop(OPND)); }//算法结束。

第四章 串

一、选择题

1 B；2A；３C；4 D；5B；6 D；7C；8A。 二、填空题

１、空格串；2、由空格字符构成的串，空格字符的个数；

3、静态分配的顺序串、动态分配顺序串、块连串； 4、‘\\0’ 5、块的大小；6、２； 7、StrAssing，StrCompare，StrLength，Concat，SubString； 8、14, 6； 9、模式，目标（主）； 10、01010421；

11、长度相等且相应位置上的字符相同。12、*s++=*t++ 或（*s++=*t++）!=‘\\0’ 三、问答题与算法题

1、 空串是指不包含任何字符的串，它的长度为零。

空格串是指包含一个或多个空格的串，空格也是字符, 长度不为零。 串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。 主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子

串的串就称为主串。

目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为

模式串，两者是相对的。 2、(１) \；(２) 正数；(３) 正数；(４)１８

emp[Maxsize]; //定义一个临时串 if(i+m

{ strcpy (Temp, &S[i+m]); //把删除的字符以后的字符保存到临时串中

strcpy( &S[i],Temp); //用临时串中的字符覆盖位置i之后的字符 }

3、void StrInsert(char *S, char *T, int i)

{//将串T插入到串S的第i个位置上

87

char *Temp; if(i<=strlen(S))

{Temp=(char *)malloc(sizeof(char[Maxsize])); // 设置一个临时串 strcpy(Temp,&S[i]); //将第i位起以后的字符拷贝到临时串中 strcpy(&S[i], T); /将串T拷贝到串S的第i个位置处，覆盖后面的字符 strcat(S,Temp); //把临时串中的字符联接到串S后面 free( Temp ); } }

４、void StrDelete(char *S, int i , int m) //串删除

{ char Temp[Maxsize]; //定义一个临时串 if(i+m

{ strcpy (Temp, &S[i+m]); //把删除的字符以后的字符保存到临时串中 strcpy( &S[i],Temp); //用临时串中的字符覆盖位置i之后的字符 }

else if(i+m>=strlen(S)&& i

strcpy(&S[i],\ //把位置i的元素置为'\\0'，表示串结束 }

5、int indexst(LinkList S, linkLint T)

{p=S->next;n=1; while(p) {q=T->next; while(q)

{if(p->data==q->data) return n; q=q->next;} p=p->next; n++; } return 0; }

6、 ‘abaabcac’ （2）’aaaabaab’

j 1 2 3 4 5 6 7 8 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c 模式串 a a a a b a a b next[j] 0 1 1 2 2 3 1 2 next[j] 0 1 2 3 4 1 2 3 7、（1）p的nextval函数值为0110132。（p的next函数值为0111232）。 （2）利用KMP(改进的nextval)算法，每趟匹配过程如下：

第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5)

第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1)

第四趟匹配： abcaabbabcabaac bacba

88

(成功) abcabaa(i=15,j=8)

8、void InvertStore(char A[]) //字符串逆序存储的递归算法。

{ char ch;

static int i = 0;//需要使用静态变量 scanf (\

if (ch!= '.') //规定'.'是字符串输入结束标志 {InvertStore(A);

A[i++] = ch;//字符串逆序存储 }

A[i] = '\\0'; //字符串结尾标记 }//结束算法InvertStore。

第五章、数组与广义表

一、

选择题1C，2A，3D，4C，5A，6B，7A，8D，9F，10A，

11C、B， 12C， 13A， 14C， 15B。

二、填空题

1、1； 2、1+s*i，d+s*i； 3、Loc(A[ 0 ][ 0 ])+(i*n+j)*k)； 4、随机； 5、1； 6、基本项，递归项，

基本项：DEPTH(LS)=1 当LS是空表 DEPTH(LS)=0 当LS是原子

递归项： DEPTH(LS)=1+MAX(DEPTH(?i))，1?i?n.

7、5, 3； 8、3，4； 9、（c,d）, (b)； 10、d； 11、1164 ； 12、232； 13、1038； 14、head(tail(tail(head(tail(head(A))))))； 15、(b)。

三、问答题与算法题

１、LOC(i,j,k)=LOC(0,0,0)+(i*n*s+j*s+k)L ２、k=2i+j-3

??k?1?i??1????3?? ??j?k?2?k?1??1???3???３、A共占120字节；A的终端结点A45的起始地址是1116。

按行和按列优先存储时，A25的起始地址分别1068和1108。 4、(1) i j e (2) i j e

1 2 4 1 2 4 2 4 -3 2 4 -3 2 7 1 2 7 1 3 1 8 3 1 8

89

4 4 5 4 4 5

5 2 -7 5 2 –7 row 1 2 3 4 5 6 7 5 6 2 5 6 2 rpos[row] 1 2 4 5 7 8 9 6 4 6 6 4 6

5、

ABaa6、 LS1^---->110eabecd

bcd---->11^---->10a1^---->10b---->10c^0d^1

7

LS1110b0d0c^^^10a^110a^110b0^0d^0c^e1^^

8、Gethead(Gettail(Gethead(Gettail(LS)))) 9、

122173412221^38^234^92^^^

4^4^2

90