《数据结构》课后题及答案

第一章 绪论

一、选择题

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

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

本文来源：https://www.bwwdw.com/article/njkr.html