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

第一章绪论

一、选择题

1、（）是数据的基本单位。

A）数据结构B）数据元素C）数据项D）数据类型

2、以下说法不正确的是（）。

A）数据结构就是数据之间的逻辑结构。

B）数据类型可看成是程序设计语言中已实现的数据结构。

C）数据项是组成数据元素的最小标识单位。

D）数据的抽象运算不依赖具体的存储结构。

3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（）等5个特性。

A）可执行性、可移植性和可扩充性B）可行性、确定性和有穷性

C）确定性、有穷性和稳定性D）易读性、稳定性和安全性

4、一般而言，最适合描述算法的语言是（）。

A）自然语言B）计算机程序语言

C）介于自然语言和程序设计语言之间的伪语言D）数学公式

5、通常所说的时间复杂度指（）。

A）语句的频度B）算法的时间消耗

C）渐近时间复杂度D）最坏时间复杂度

6、A算法的时间复杂度为0（/）,B算法的时间复杂度为0（2〉，则说明（）。

A）对于任何数据量，A算法的时间开销都比B算法小

B）随着问题规模n的增大，A算法比B算法有效

C）随着问题规模n的增大，B算法比A算法有效

D）对于任何数据量，B算法的时间开销都比A算法小

7、算法分析的目的是（）。

A）找出数据结构的合理性B）研究算法中的输入和输出的关系

C）分析算法的效率以求改进D）分析算法的易懂性和文档性

8、下面程序段的时间复杂度为（）。

for（i=0;i<m;i++）

for（j=0;j<n;j++）

a[i][j]=i*j；

A）0（m2）B）O（n2）C)O(m*n)D)O(m+n)

9、下面算法的时间复杂度为（)。

intf（intn）

{if(n==0IIn==1)return1;elsereturnn*f(n-1);}

A)0(1)B)0(n)C)0(n2)D)0(n!)

二、填空题

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

2、在线性结构中，第一个结点（）前驱结点，其余每个结点有且只有（）个前驱结

点；最后一个结点（）后继结点；其余每个结点有且只有（）个后继结点。

3、在树形结构中，树根结点没有（）结点，其余每个结点有且只有（）个前驱结点；叶

子结点没有（）结点，其余每个结点的后继结点可以（）。

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

）和（）的关系。

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

6、数据的逻辑结构被分为（）、（）、（）和（）四种。

7、数据的存储结构被分为（）、（）、（）、（）四种.

8、算法的时间复杂度除了与问题的规模有关外，还与输入实例的（）有关。

三、问答题与算法题

1、简述下列概念：

数据元素：

数据结构：

数据类型：

数据的逻辑结构及其4种类型：

数据的存储结构及其4种方式：

2、设两个算法在同一台机器上执行，其执行时间分别是仔和2口，要使前者快于后者，n

至少需要多大？

3、有时为比较两个同数量级的算法优劣，须突出主项的常数因子，而将低次项用“0“记号

表示。如：ST,（n）=1.39nlogn+100n+256=1.39nlogn+0（n）;

T2（n）=2.0nlogn-2n=2.0nlogn-0（n）;

这两个式子表示，当n足够大时，「（11）优于12（11）,因为前者的系数因子小于后者。请用

此方法表示下列函数，并指出当n足够大时，哪•个较优，哪一个较劣。

22

（I）T,（n）=5n-3n+60logn;（2）T2（n）=3n+1000n+3logn;

z2

（3）T3（n）=8n+3logn;（4）T4（n）=1.5n+O（n）。

4、计算执行下面程序段时，执行S语句的次数为。

for（i=l;i<=n;i++）

for（j=l;jv=i;j++）S;

第二章线性表

一、选择题

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

A）数据项；B）数据元素；C）数据对象；D）表元素。

2、以下关于线性表的说法不正确的是（）。

A）线性表中的数据元素可以是数字、字符、记录等不同类型。

B）线性表中包含的数据元素个数不是任意的。

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

D）存在这样的线性表：表中各结点都没有直接前趋和直接后继。

3、线性表的顺序存储结构是一种（）的存储结构。

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

4、在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。

A）基地址B）结点大小C）线性表大小D）基地址和结点大小

5、下面关于线性表的叙述中，错误的是哪一个？（）

A）线性表采用顺序存储，必须占用一片连续的存储单元。

B）线性表采用顺序存储，便于进行插入和删除操作。

0线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用链接存储，便于插入和删除操作。

6、线性表采用链表存储时其存储地址要求（

A）必须是连续的；B）部分地址必须是连续的；

C）必须是不连续的；D）连续和不连续都可以。

7、一个长度为n的线性表顺序存储，向第i个元素（lWiWn+1）之前插入一个新元素时，需

要从后向前依次后移（）个元素。

A）n-iB）n-i+1C）n-i-1D）i

8、（）运算中，使用顺序表比链表好。

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

9、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

2

A）0（1）B）O（n）C）0（n）D）O（log2n）

10、在一个长度为n的顺序存储的线性表中，删除第i个元素（iWiWn）时，需要从前向后依

次前移（）个元素。

A）n-iB）n-i+1C）n-i-1D）i

11、在一个长度为n的线性表中顺序查找值为x的元素时，平均查找长度（即x同元素的平

均比较次数，假定查找每个元素的概率都相等）为（）。

A）nB）n/2C）（n+l）/2D）（n-l）/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所指的结点，

则执行（）o

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;

二、填空题

1、对于一个具有n个结点的单链表，在已知结点*p的后插入一个新结点的时间复杂度为

(），在给定值为x的结点后插入一个新结点的时间复杂度为（)«

2、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成

（）和（）o

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

示元素之间的关系的。

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

(）个。

5、循环单链表的最大优点是（）。

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

在（）结点的next域中。

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

8、当线性表的元素总数基本稳定，且很少进行插入和删除操作,但要求以最快的速度存取

线性表中的元素时，应采用（）存储结构。

9、求顺序表和单链表的长度算法的时间复杂度分别是（)和(）。

10、顺序表存储结构的优点是（)、(）、

（）;缺点是（）。

11、单链表存储结构的优点是（）、（）;缺点是

（）、（）。

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

13、链接存储的特点是利用（）来表示数据元素之间的逻辑关系。

14、带头结点的双循环链表DL为空表的条件是：（）。

15、以下算法的功能是：在一个非递减的顺序及中，删除所有值相等的多余元素。在画线处

填上适当的语句，将程序补充完整。

#definemaxlen100

typedefstruct{

elemtypea[maxlenJ;

intlength;

}sqlist;

voiddelequil(sqlist&S)

{intj=l,i=2;

while()

{if(S.a[i]!=S.a[j])

i++；

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

P

LlinkDataRlink

)，)°

三、问答题与算法题

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

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

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

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

LinkListABC(LinkListL){〃L是无头结点单链表

if(L&&L->next)

{Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

returnL;

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

结点结构为：(prior,data,next)

回叵

6、VoidAA(SqList&L,inti,intx)

{if(i>=1&&i<=Length(L))

{FOR(j=Length(L);j>=i;j--)

AU+1]=AU];

A[i]=x;

elseexit(ERROR);

假定调用该算法时线性表L的内容为(15,26,37,48,55),i为3,x为51,则调用返回

后该单链表的内容变为什么？

7^重写建立单连表的算法CreatList_L(Linklist&L,intn),要求顺序输入n个元素的值(即先

输入aba2…).

CreatList_L(LinkList&L；intn)

8、设顺序表L是一个递减有序表，试写一算法，插入元素x,插入后仍保持L的有序性。

Voidsinsert(Sqlist&S,intx)

9、写一算法，在带头组卓的单链表上实现线性表的求表长ListLenglh(L)运算。

intListLength(LinkListL)

10、写出从一个带头筝卓的单链表中删除其值等于给定值x的结点的算法函数。

Intdelete(LinkList&L,intx){

11、已知递增有序的两个带头筝卓的单链表La,Lb分别存储了一个非空集合A,B。设计算

法实现求两个集合的并集的运算A=AUB

voidmergelist(linklist&La,linklistLb)

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

13、删除整数数组中值相等的多余整数(只保留第一次出现的那个整数)。

VoiddelDuplicate(intA[],int&n)

第三章栈和队列

一、选择题

1、对于栈，操作数据的原则是()。

A)先进先出B)后进先出C)后进后出D)不分顺序

2、一般情况下，将递归算法转换成非递归应通过设置()实现。

A)数组；B)线性表；C)队列；D)栈。

3、栈和队列的共同点是()

A)都是先进后出B)都是先进先出

C)只允许在端点处插入和删除元素D)没有共同点

4、若栈的入栈序列是abcde,则栈的不可能的输出序列是()。

A)edcbaB)decbaC)dceabD)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,其输出序列是pl,p2,p3,...，pn,若pl=n,

则pi=()o

A)IB)n-iC)n-i+lD)不确定

8、若用一个大小为6的数组来实现循环队列，且当前尾指针rear和头指针front的值分别为

0和3,当从队列中删除•个元素，再加入两个元素后，尾指针rear和头指针front的值分

别是()o

A)1和5；B)2和4；C)4和2；D)5和1。

9、要使输入序列为ABC变为序列BAC时，使用的栈操作序列为()

A)push,pop,push,pop,push,popB)push,push,push,pop,pop,pop

C)push,push,pop,pop,push,popD)push,pop,push,push,pop,pop

10、设用一个大小m=60的顺序表A[m]表示一个循环队列，如果当前的尾指针rear=32,

头指针front=15,则当前循环队列的元素个数是()。

A)42；B)16；C)17；D)41o

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

件是()，判断队列满的条件是()o

(1)A)a.front+1==a.rear；B)a.front==a.rear+1；

C)a.front==0；D)a.front==a.rearo

(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、循环队列存储在数组中，则入队时的操作为()o

A)rear=rear+1B)rear=(rear+l)mod(m-1)

C)rear=(rear+1)modmD)rear=(rear+l)mod(m+1)

13、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主:机

将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区应该

是一个()结构。

A)栈；B)队列；C)数组；D)线性表。

14、设栈用向量V[l..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确操作是()。

A.V[++top]=x;B.V[top++]=x;

C.V[—top]=x;D.V[top--]=x;

15、若栈采用顺序存储方式存储,现两栈共享空间top[i]代表第i个栈（i=1,2）

栈顶，栈1的底在v[l],栈2的底在V[m],则栈满的条件是（）o

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

C.top[l]+top[2]=mD.top[l]=top[2]

16.表达式a*（b+c）-d的后缀表达式是（）。【南京理工大学2001一、2（L5分）】

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、设元素入栈的顺序是1、2、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,l）,Pop（s,xl）,Push（s,2）,Push（s,3）,

Pop（s,x2）,Pop（s,x3）,Push（s,4）,Pop（s,x4），则出栈的数字序列为何？

2、设用不带头结点的单链表表示栈，请分别写出入栈和出栈的算法。

（1）intpush_L（Linkstack&sSelemTypee）

(2)intpop_L(Linkstack&sSelemType&e)

3、假设用带头结点的单循环链表表示队列，并设置一个指向尾结点的指针(无头指针)，请

分别写出队列的入队和出队算法。

(l)intEnQueue_L(Queueptr&QLQelemTypee)

⑵intDeQueue_L(Queueptr&QLQelemType&e)

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

(1)voidabc1(Stack&S)

(

inti,arr[64],n=0;

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

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

(2)Voidabc2(StackS1,Stack&S2);

{initstack(tmp);

while(!StackEmpty(SI))

{pop(Sl,x);Push(tmp,x);}

while(!StackEmpty(tmp))

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

(3)voidabc3(Stack&S,intm)

{InitStack(T);

while(!StackEmpty(S))

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

while(!StackEmpty(T))

{Pop(T,e);Push(S,e);)

(4)voidabc4(Queue&Q)

{InitStack(S);

while(!QueueEmpty(Q))

{DeQueue(Q,x);Push(S,x);}

while(!StackEmpty(S))

{Pop(S,x);EnQueue(Q,x);)

)

(5)voidinvert1(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;

)

returnOK;

5、回文是指正读反读均相同的字符序列，如"abba"和"abdba”均是回文，但“good”不是回文。

试写一个算法判定给定的用带去绡，卓的单链表表示的字符串是否为回文。

Inthwl(linklistL)

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

voidClearStack(LinkStack&S)o

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

intStacksize(LinkStackS)。

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

里要求利用栈操作)。

voidinvert2(LinkList&L)。

9、试将下列递归过程改写为非递归过程。

voidtest(int&sum)

{intx；

scanf(x)；

if(x=0)sum=0

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

printf(sum)；

)

10、从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度

不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、*、/四种

运算。例如:23434+2*$

第四章串

一、选择题

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

A)可以顺序存储B)数据元素是一个字符

C)可以链接存储D)数据元素可以是多个字符

2、有两个串P和Q,求P在Q中首次出现的位置的运算称()。

A)模式匹配B)连接C)求子串D)求串长

3、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串(非

空且不同于S本身)的个数为()。

A)n2B)(n72)+(n/2)C)(n2/2)+(n/2)-lD)(n72)-(n/2)T

4、设串sl='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)BCDEFB)BCDEFGC)BCPQRSTD)BCDEFEF

5、顺序串中，根据空间分配方式的不同，可分为()。

A)直接分配和间接分配B)静态分配和动态分配

C)顺序分配和链式分配D)随机分配和固定分配

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

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

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

A)O(m)；B)O(n)；C)O(m+n)；D)O(n*m)。

8、已知串S='aaab',其Next数组值为()。

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

二、填空题

1、在空串和空格串中，长度不为0的是()。

2、空格串是指(),其长度等于()。

3、按存储结构不同，串可分为()、()、()«

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

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

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

()个字节。

7、串操作虽然较多，但都可通过五种操作()、()、()、

()、()构成的最小子集中的操作来实现。

8、设串S='IlikecomputerT='com',则Length(S)=()。Index(S,T,l)=()

9、在KMP算法中，next|j］只与()串有关，而与()串无关。

10、字符串'ababaaab)的nextval函数值为()。

11＞两个字符串相等的充分必要条件是()。

12.实现字符串拷贝的函数strcpy为：

voidstrcpy(char*s,char*t)/*copyttos*/

{while()；}

三、问答题与算法题

1、简述下列每对术语的区别:

空串和空格串：

串常量和串变量：

主串和子串：

目标串和模式串。

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

charsH30J="Stocktom",s2[30J="March51999",s3[30J,

(1)在执行下列语句后，s3的值是什么？

strcpy(s3,sl);strcat(s3,",");strcat(s3,s2);

(2)调用函数strcmp(sl,s2)的返回值是什么？

(3)调用函数strcmp(sl[5],"Ton")的返回值是什么？

(4)调用函数strlen(strcat(sl,s2))的返回值是什么?

3、利用C的库函数strlen,strcpy和strcat写一算法voidStrlnsert(char*S,char*T,inti),将串

T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。

voidStrlnsert(char*S,char*T,inti)

4、利用C的库函数strlen和strcpy(或strcpy)写一算法voidStrDelete(char*S,inti,

intm)删去串S中从位置i开始的连续m个字符。若iestrlen(S),则没有字符被删除；若

i+m》strlen(S),则将S中从位置i开始直至末尾的字符均删去。

voidStrDelete(char*S,inti,intm)〃串删除

5、若S和T是用结点大小为1的带头结点的单链表存储的两个串，试设计一个算法找出S

中第一个不在T中出现的字符。

Intindexst(LinkListS,linkLintT)

6、在KMP算法中,求下列模式串的next。］。

(1)'abaabcac'(2)'aaabaaba'

7、设目标为t='abcaabbabcabaacbacba',模式为p=<abcabaa,

(1)计算模式p的naxtval函数值;

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

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

第五章数组与广义表

一、选择题

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

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

a\\a\n

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

存放在一维数组B中。对下三角矩阵中任一元素atJ(i>=j),在一维数组B中下标k的值是

()。

A)i(i-l)/2+j-lB)i(i-l)/2+jC)i(i+l)/2+j-lD)i(i+l)/2+j

3、在稀疏矩阵的三元组表示法中，每个三元组表示()。

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

C)矩阵中非零元素的行号和列号D)矩阵中非零元素的行号、列号和值

4、对稀疏矩阵进行压缩存储是为了()。

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

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

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

储单元，基地址为10,则L0C[5,5]=()。

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

6、设有数组A[i,j],数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,

数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为

()o

A)BA+141B)BA+180C)BA+222D)BA+225

7、广义表是线性表的推广，它们之间的区别在于()o

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(tai1(head(tail(L))))D.head(tail(head(tail(tail(L)))))

9、已知广义表：A=(a,b),B=(A,A),C=(a,(b,A),B),下列运算的结果是：

tail(head(tai1(C)))=()。

A)(a)B)AC)aD)(b)E)bF)(A)

10、广义表运算式Tail(((a,b),(c,d)))的操作结果是()。

A)()B)c,dC)((c,d))D)d

II、广义表((a,b,c,d))的表头是(),表尾是(

A)aB)()C)(a,b,c,d)D)(b,c,d)

12、设广义表1=((a,b.c)),则L的长度和深度分别为()。

A)1和1B)1和3C)1和2D)2和3

13、下面说法不正确的是()o

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(tai1(head(tai1(LS)))D)head(tail(tail(head(LS))))

15、设一个广义表中结点的个数为n,则求广义表深度算法的时间复杂度为()。

2

A)0(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⑼⑼)，则的地址是()o

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

()存取结构。

5、矩阵的压缩存储就是为多个相同的非零元素分配()个存储空间，零元素不分配空间。

6、递归是算法设计的重要方法，递归由()项和()项构成。用递归的

方法求广义表LS的深度DEPTH(LS),写出基本项和递归项。

基本项:

递归项:

7、广义表(2,5,1)),(1,6,3/),1<))的长度是()，深度是()。

8、广义表((a),((b),c),(((d))))的长度是(),深度是()0

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

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有N*5*6个元素)，每个元素的长度是2,

则a[2][3][4]的地址是()。(设a[0][0][0]的地址是1000,数据以行为主方式存储)

12、设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100,

若按列优先顺序存储，则元素A[6,6]存储地址为()。

13、己知三对角矩阵AE1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐

行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为()。

14、广义表A=(((a,b),(c,d,e))),取出A中的原子e的操作是()。

15、设广义表A(((),(a,(b),c))),JU!)head(tail(head(tai1(head(A))))=()。

三、问答题与算法题

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

。120…0、

Clf।Cl22。23・••0

2、设有三对角矩阵A,将其三条对角线上的元素逐行

nXn=0a32%3…0

••・«••«•»«••»««

、000

地存储到向量B[O...3n-3]中,使得B[k]=aij,求:

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

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

3、设二维数组A5X6的每个元素占4个字节，已知LocSooAlOOO,A共占多少个字节？A的

终端结点A45的起始地位为何？按行和按列优先存储时，A25的起始地址分别为何？

4、己知一个稀疏矩阵如下图所示:

[-0400000-i

000-3001

8000000

0005000

0-700020

-000600o-

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

⑵给出它的行逻辑链接的顺序存储表示;

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

(1)A=((a,b),(c,d))

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

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

7,画出广义表LS=(((b,c),d),(a),((a),((b,c),d)),e,())的具有共享结构的存储表示。

8、设广义表LS=(soldier,(teacher,student),(worker,farmer)),用取表头函数GetHead()和

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

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

‘0280、

7009

0300

、2062,

10、设任意n个整数存放于数组A(l:n)中，试编写程序，将所有正数排在所有负数前面(要

求算法复杂性为0(n))。

第六章树和二叉树

一、选择题

1、设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少有(B)

个，至多有(E)个。

A)2h；B)2h-1；C)2h+l；0)2^'；E)2h-1；F)2h+lo

2、高度为h的完全二叉树至少有(D)个结点，至多有(B)个结点。

A)2h；B)2h-1；C)2h+1；D)2h-1»

3、具有n个结点的满二叉树有()个叶结点。

A)n/2；B)(n-l)/2；C)(n+l)/2；D)n/2+l»

4、一棵具有n个叶结点的哈夫曼树，共有()个结点。

A)2nB)2n-1C)2n+lD)2”“；

5、一棵具有25个叶结点的完全二叉树最多