大数据结构试题集(含答案)

程序复杂性

3、具有线性结构的数据结构是（ D ）。

A. 图

B. 树

C. 广义表

D. 栈

4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。

A. 可执行性、可移植性和可扩充性

B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性

D. 易读性、稳定性和确定性

5、下面程序段的时间复杂度是（C）。

for(i=0;i

for(j=0;j

a[i][j]=i*j;

A. O(m2)

B. O(n2)

C. O(m*n)

D. O(m+n)

6、算法是（ D ）。

A. 计算机程序

B. 解决问题的计算方法

C. 排序算法

D. 解决问题的有限运算序列

7、某算法的语句执行频度为（3n+nlog

2

n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)

B. O(nlog

2n) C. O(n2) D. O(log

2

n)

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

i=1;

while(i<=n)

i=i*3;

A. O(n)

B. O(3n)

C. O(log

3

n) D. O(n3)

9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ B ）和运算等的学科。

A. 结构

B. 关系

C. 运算

D. 算法

10、下面程序段的时间复杂度是（ C ）。

i=s=0;

while(s

i++;s+=i;

}

A. O(n)

B. O(n2)

C. O(√n)

D. O(n3)

11、抽象数据类型的三个组成部分分别为（ A ）。

A. 数据对象、数据关系和基本操作

B. 数据元素、逻辑结构和存储结构

C. 数据项、数据元素和数据类型

D. 数据元素、数据结构和数据类型

12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（ A ）。

A. 正确性算法应能正确地实现预定的功能

B. 易读性算法应易于阅读和理解，以便调试、修改和扩充

C. 健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果

D. 高效性即达到所需要的时间性能

13、下列程序段的时间复杂度为（ B）。

x=n;y=0;

while(x>=(y+1)*(y+1))

y=y+1;

A. O(n)

B. )

(n

O C. O(1) D. O(n2)

二、填空题

1、程序段“i=1;while(i<=n) i=i*2;”的时间复杂度为 O(log2n) 。

2、数据结构的四种基本类型中,树形结构的元素是一对多关系。

三、综合题

1、将数量级O(1),O(N),O(N2),O(N3),O(NLOG

2N),O(LOG

2

N),O(2N)按增长率由小到大排

序。

答案： O(1) < O(log

2N) < O(N) < O(Nlog

2

N) < O(N2) < O(N3) < O(2N) 第二章线性表

一、选择题

1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（C ）。

A. O(log

2

n) B.O(1) C. O(n) D.O(n2)

2、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ A ）存储方式最节省时间。

A. 顺序表

B. 单链表

C. 双链表

D. 单循环链表

3、具有线性结构的数据结构是（ D ）。

A. 图

B. 树

C. 广义表

D. 栈

4、在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动

（ B）个元素。

A. n-i

B. n-i+1

C. n-i-1

D. i

5、非空的循环单链表head的尾结点p满足（ A ）。

A. p->next==head

B. p->next==NULL

C. p==NULL

D. p==head

6、链表不具有的特点是（ A）。

A. 可随机访问任一元素

B. 插入删除不需要移动元素

C. 不必事先估计存储空间

D. 所需空间与线性表长度成正比

7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（ C ）。

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;

C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

D. q->next=p->next;q->prior=p;p->next=q;p->next=q;

8、线性表采用链式存储时，结点的存储地址（ C ）。

A. 必须是连续的

B. 必须是不连续的

C. 连续与否均可

D. 和头结点的存储地址相连续

9、在一个长度为n的顺序表中删除第i个元素，需要向前移动（ A ）个元素。

A. n-i

B. n-i+1

C. n-i-1

D. i+1

10、线性表是n个（ C）的有限序列。

A. 表元素

B. 字符

C. 数据元素

D. 数据项

11、从表中任一结点出发，都能扫描整个表的是（ C ）。

A. 单链表

B. 顺序表

C. 循环链表

D. 静态链表

12、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（ A）。

A. O(n)

B. O(1)

C. O(n2)

D. O(n-1)

13、线性表L=(a1,a2,……,an)，下列说法正确的是（ D ）。

A. 每个元素都有一个直接前驱和一个直接后继

B. 线性表中至少要有一个元素

C. 表中诸元素的排列顺序必须是由小到大或由大到小

D. 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继

14、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（ B ）。

A. 98

B. 100

C. 102

D. 106

15、在线性表的下列存储结构中，读取元素花费的时间最少的是（ D ）。

A. 单链表

B. 双链表

C. 循环链表

D. 顺序表

16、在一个单链表中，若删除p所指向结点的后续结点，则执行（ A ）。

A. p->next=p->next->next;

B. p=p->next;p->next=p->next->next;

C. p =p->next;

D. p=p->next->next;

17、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（ C ）。

A. O(1)

B. O(n)

C. O(m)

D. O(m+n)

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

A. 随机存取

B. 顺序存取

C. 索引存取

D. 散列存取

19、顺序表中，插入一个元素所需移动的元素平均数是（ D）。

A. (n-1)/2

B. n

C. n+1

D. n/2

10、循环链表的主要优点是（ D ）。

A. 不再需要头指针

B. 已知某结点位置后能容易找到其直接前驱

C. 在进行插入、删除运算时能保证链表不断开

D. 在表中任一结点出发都能扫描整个链表

11、不带头结点的单链表head为空的判定条件是（ A ）。

A. head==NULL

B. head->next==NULL （带头结点判定条件）

C. head->next==head （循环链表判定条件）

D. head!=NULL

12、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ A）。

A. 访问第i个元素的前驱（1

i≤）

B. 在第i个元素之后插入一个新元素(n

≤)

1≤

i

C. 删除第i个元素(n

≤)

i

1≤

D. 对顺序表中元素进行排序

13、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ A ）。

A. q->next=s->next；s->next=p；

B. s->next=p；q->next=s->next；

C. p->next=s->next；s->next=q；

D. s->next=q；p->next=s->next；

14、在以下的叙述中，正确的是（ C）。

A. 线性表的顺序存储结构优于链表存储结构

B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况

D. 线性表的链表存储结构优于顺序存储结构

15、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（ A ）。

A. (n-1)/2

B. n/2

C. (n+1)/2

D. n

16、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（ C ）。

A. s->next=p->next; p->next=s;

B. p->next=s->next;s->next=p;

C. q->next=s;s->next=p;

D. p->next=s;s->next=q;

17、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（ B）。

A. p=p->next;

B. p->next=p->next->next;

C. p->next=p;

D. p=p->next->next;

18、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（ D ）。

A. p指向头结点

B. p指向尾结点

C. p的直接后继是头结点

D. p的直接后继是尾结点

1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：q->next=p->next ；p->next = q 。

二、填空题

答案：q->next=p->next p->next=q

2、线性表的逻辑结构是线性结构，其所含元素的个数称为线性表的长度。答案：线性结构长度

3、写出带头结点的双向循环链表L为空表的条件。

答案：L->prior==L->next==L

4、带头结点的单链表head为空的条件是。

答案：head->next==NULL

5、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q = p->next;

p->next= _q->next ___;

三、判断题

1、单链表不是一种随机存储结构。对

2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。错

3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。对

4、顺序存储方式只能用于存储线性结构。错

5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。错

6、链式存储的线性表可以随机存取。错

四、程序分析填空题

1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。

int GetElem(LinkList L,int i,Elemtype *e){

LinkList p；int j；

p=L->next;j=1;

while(p&&j

(1) ;++j;

}

if(!p||j>i) return ERROR;

*e= (2) ;

return OK;

}

答案：(1)p=p->next (2)p->data

2、函数实现单链表的插入算法，请在空格处将算法补充完整。

int ListInsert(LinkList L,int i,ElemType e){

LNode *p,*s;int j;

p=L;j=0;

while((p!=NULL)&&(jnext;j++;

}

if(p==NULL||j>i-1) return ERROR;

s=(LNode *)malloc(sizeof(LNode));

s->data=e;

(1) ;

(2) ;

return OK;

}/*ListInsert*/

答案：(1)s->next=p->next (2)p->next=s

3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。

int ListDelete_sq(Sqlist *L,int i){

int k;

if(i<1||i>L->length) return ERROR;

for(k=i-1;klength-1;k++)

L->slist[k]= （1） ;

（2） ;

return OK;

}

答案：（1）L->slist[k+1] （2） --L->Length

4、函数实现单链表的删除算法，请在空格处将算法补充完整。

int ListDelete(LinkList L,int i,ElemType *s){

LNode *p,*q;

int j;

p=L;j=0;

while(( （1） )&&(j

p=p->next;j++;

}

if(p->next==NULL||j>i-1) return ERROR;

q=p->next;

（2） ;

*s=q->data;

free(q);

return OK;

}/*listDelete*/

答案：(1)p->next!=NULL (2)p->next=q->next

5、写出算法的功能。

int L(head){

node * head;

int n=0;

node *p;

p=head;

while(p!=NULL)

{ p=p->next;

n++;

}

return(n);

}

答案：求单链表head的长度

五、综合题

1、编写算法，实现带头结点单链表的逆置算法。

答案：void invent(Lnode *head)

{Lnode *p,*q,*r;

if(!head->next) return ERROR;

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

while(q)

{ r=q->next;

q->next=p;

head->next=q;

p=q;

q=r;

}

}

试编写一个算法，将一个顺序表逆置，并使用最少的辅助存储空间实现。答案：typedef struct {

ElemType *elem;

int length;

}Sqlist;

Invert_list(Sqlist *L)/*将顺序表进行逆置*/

{ int i; ElemType t;

for(i=0;i<(L->length-1)/2;i++){

t=L->elem[i];

L->elem [i]= L->elem [L->length-i-1];

L->elem [L->length -i-1]=t;

}/*for*/

}/*invert_list*/

2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。

答案：void merge(Lnode *L1, Lnode *L2)

{Lnode *p,*q ;

while(p->next!=L1)

p=p->next;

while(q->next!=L2)

q=q->next;

q->next=L1; p->next =L2;

}

3、设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data 域的值递增排序。

答案：void assending(Lnode *head)

{Lnode *p,*q , *r, *s;

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

while(q)

{r=q; q=q->next;

if(r->data<=p->data)

{r->next=p; head->next=r; p=r; }

else

{while(!p && r->data>p->data)

{s=p; p=p->next; }

r->next=p; s->next=r;}

p=head->next; }

}

4、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。

答案：

void linklist_c(Lnode *head)

{Lnode *p; p=head;

if(!p) return ERROR;

while(p->next!=NULL)

p=p->next;

p->next=head;

}

设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。

5、已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,…,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：

（1）写出执行下列程序段后的顺序表A中的数据元素；

（2）简要叙述该程序段的功能。

if(head->next!=head)

{

p=head->next;

A->length=0;

while(p->next!=head)

{

p=p->next;

A->data[A->length ++]=p->data;

if(p->next!=head)p=p->next;

}

}

答案：

(1) (a2, a4, …, )

(2)将循环单链表中偶数结点位置的元素值写入顺序表A

6、设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

答案：

void Insert_sq(Sqlist va[], ElemType x)

{int i, j, n;

n=length(va[]);

if(x>=va[n-1])

va[n]=x;

else

{i=0;

while(x>va[i]) i++;

for(j=n-1;j>=I;j--)

va[j+1]=va[j];

va[i]=x; }

n++;

}

试编写一个算法，在一个递增有序排列的单链表中插入一个新结点x，并保持有序。

struct Linknode{

int data ;

struct Linknode *next ;

};

typedef struct Linknode *Link;

Link insert(Link head)

{

int i,e,j ;

Link pointer,s;

printf("\nplease input the elem of you want insert:");

scanf("%d",&e);

pointer= head;

while (pointer->next && e>=pointer->next->data)/*在链表中确定插入的位置*/

pointer=pointer->next;

if (!pointer->next)

{

s=(Link)malloc(sizeof(struct Linknode));

s->data=e;

s->next=NULL;

pointer->next=s;

}

else {

s=(Link)malloc(sizeof(struct Linknode));

s->data=e; /*为插入的结点建立链接关系*/

s->next=pointer->next;

pointer->next=s;

}/*if*/

return head;

}/*LinkList_insert*/

7、假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2，设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f2后的线性表L的数据元素，并描述该算法的功能。

void f2(SeqList *L){

int i,j,k;

k=0;

for(i=0;ilength;i++){

for(j=0;jdata[i]!=L->data[j];j++);

if(j==k){

if(k!=i)L->data[k]=L->data[i];

k++;

}

}

L->length=k;

}

答案：

(3,7,2,1,8) 删除顺序表中重复的元素

8、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。

答案：

void Delete_list(Lnode *head, ElemType x, ElemType y)

{Lnode *p, *q;

if(!head) return ERROR;

p=head; q=p;

while(!p)

{if(p->data>x) && (p->data

if(p==head)

{head=p->next; free(p);

p=head; q=p; }

else

{q->next=p->next; free(p);

p=q->next; }

else

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

}

}

9、在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且a

void Delete_list(Lnode *head, ElemType a, ElemType b)

{Lnode *p, *q;

if(!head->next) return ERROR;

p=head->next; q=p;

while(p->next!=head)

{if(p->data>x) && (p->data

if(p==head)

{head=p->next; free(p);

p=head; q=p; }

else

{q->next=p->next; free(p);

p=q->next; }

else

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

}

}

试编写一个算法，将两个元素值递减排列的顺序表合并为一个非递增的顺序表。

typedef struct {

ElemType *elem;

int length;

}Sqlist;

Merge_list(Sqlist *A, Sqlist *B, Sqlist *C)

{int j=0, k=0, i=0; C->length= A->length+ B->length;

while(ilength&&jlength)

if(A->elem[i]>B->elem[j]) {C->elem[k]= A->elem[i]; i++; k++;}

else { C->elem[k]= B->elem[j]; j++; k++;}

while(i< A->length) { C->elem[k]= A->elem[i]; i++; k++;}

while(j< B->length) { C->elem[k]= B->elem[j]; j++; k++;}

}

第三章栈和队列

一、选择题

1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ C ）。

A. a,b,c,d,e

B. d,e,c,b,a

C. d,c,e,a,b

D. e,d,c,b,a

2、判断一个循环队列Q（最多n个元素）为满的条件是（ C ）。

A. Q->rear==Q->front

B. Q->rear==Q->front+1

C. Q->front==(Q->rear+1)%n

D. Q->front==(Q->rear-1)%n

3、设计一个判别表达式中括号是否配对的算法，采用（ D ）数据结构最佳。

A. 顺序表

B. 链表

C. 队列

D. 栈

4、带头结点的单链表head为空的判定条件是（ B）。

A. head==NULL

B. head->next==NULL

C. head->next!=NULL

D. head!=NULL

5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（ D）。

A. 1243

B. 2134

C. 1432

D. 4312

E. 3214

6、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（B ）。

A. 1和5

B. 2和4

C. 4和2

D. 5和1

7、队列的插入操作是在（ A）。

A. 队尾

B. 队头

C. 队列任意位置

D. 队头元素后

8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（ A ）。

A. front==rear

B. front==0

C. rear==0

D. front=rear+1

9、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（ A ）。

A. *S->top=e;S->top++;

B. S->top++;*S->top=e;

C. *S->top=e

D. S->top=e;

10、表达式a*(b+c)-d的后缀表达式是（B）。

A. abcd+-

B. abc+*d-

C. abc*+d-

D. -+*abcd

11、将递归算法转换成对应的非递归算法时，通常需要使用（ B ）来保存中间结果。

A. 队列

B. 栈

C. 链表

D. 树

12、栈的插入和删除操作在（ B ）。

A. 栈底

B. 栈顶

C. 任意位置

D. 指定位置

13、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（ C ）的编组。

A. 3，4，5，1，2

B. 2，4，1，3，5

C. 3，5，4，2，1

D. 1，3，5，2，4

14、判定一个顺序栈S（栈空间大小为n）为空的条件是（ A ）。

A. S->top==0

B. S->top!=0

C. S->top==n

D. S->top!=n

15、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ C ）。

A. front=front->next

B. s->next=rear;rear=s

C. rear->next=s;rear=s;

D. s->next=front;front=s;

16、一个队列的入队序列是1，2，3，4，则队列的出队序列是（ A ）。

A. 1，2，3，4

B. 4，3，2，1

C. 1，4，3，2

D. 3，4，1，2

17、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ C ）。

A. a

B. b

C. c

D. d

18、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（ D ）。

A. top不变

B. top=0

C. top=top+1

D. top=top-1

19、判断一个循环队列Q（空间大小为M）为空的条件是（ A ）。

A. Q->front==Q->rear

B. Q->rear-Q->front-1==M

C. Q->front+1=Q->rear

D. Q->rear+1=Q->front

20、设计一个判别表达式中左右括号是否配对出现的算法，采用（ C ）数据结构最佳。

A. 线性表的顺序存储结构

B. 队列

C. 栈

D. 线性表的链式存储结构

21、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（ C ）。

A. N

B. N+1

C. N-1

D. N-2

【解析：队列的头指针指向的是第一个元素的前一个结点，而不是指向第一个元素，一次队列的头指针要占用一个结点长度。】

22、队列的删除操作是在（ A ）。

A. 队首

B. 队尾

C. 队前

D. 队后

23、若让元素1，2，3依次进栈，则出栈次序不可能是（ C ）。

A. 3，2，1

B. 2，1，3

C. 3，1，2

D. 1，3，2

24、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ A ）。

A. (rear-front+m)%m

B. rear-front+1

C. rear-front-1

D. rear-front

25、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。

A. 堆栈

B. 队列

C. 数组

D. 线性表

【解析：先进入缓冲区的文件先被打印，选择先进先出的结构，即队列。】

26、栈和队列都是（ C ）。

A. 链式存储的线性结构

B. 链式存储的非线性结构

C. 限制存取点的线性结构

D. 限制存取点的非线性结构

【解析：栈是只允许在栈顶进行插入和删除操作的线性表，队列是只允许在队头进行删除，在队尾进行删除操作的线性表】

27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（ A ）。

A. front=front->next

B. rear= rear->next

C. rear->next=front

D. front->next=rear

28、队和栈的主要区别是（ D ）。

A. 逻辑结构不同

B.存储结构不同

C. 所包含的运算个数不同

D. 限定插入和删除的位置不同

二、填空题

1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是。

答案：3

2、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为。

答案：(rear-front+M)%M

3、在具有n个元素的循环队列中，队满时具有个元素。

答案：n-1

4、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为。

答案：61

5、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的当前的长度为。

答案：15

三、判断题

1、栈和队列都是受限的线性结构。对

2、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。错

3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。对

四、程序分析填空题

1、已知栈的基本操作函数：

int InitStack(SqStack *S); //构造空栈

int StackEmpty(SqStack *S);//判断栈空

int Push(SqStack *S,ElemType e);//入栈

int Pop(SqStack *S,ElemType *e);//出栈

函数conversion实现十进制数转换为八进制数，请将函数补充完整。

void conversion(){

InitStack(S);

scanf(“%d”,&N);

while(N){

（1） ;

N=N/8;

}

while( （2） ){

Pop(S,&e);

printf(“%d”,e);

}

}//conversion

答案：（1）Push(S,N%8) （2）!StackEmpty(S)

2、写出算法的功能。

int function(SqQueue *Q,ElemType *e){

if(Q->front==Q->rear)

return ERROR;

*e=Q->base[Q->front];

Q->front=(Q->front+1)%MAXSIZE;

return OK;

}

答案：循环队列出队操作

3、阅读算法f2,并回答下列问题：

（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f2后的队列Q;

（2）简述算法f2的功能。

void f2(Queue *Q){

DataType e;

if (!QueueEmpty(Q)){

e=DeQueue(Q);

f2(Q);

EnQueue(Q,e);

}

}

答案：（1）6,4,2,5,3,1 （2）将队列倒置

五、综合题

1、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列算法（用函数实现）。

答案：void EnQueue(Lnode *rear, ElemType e)

{ Lnode *new;

New=(Lnode *)malloc(sizeof(Lnode));

If(!new) return ERROR;

new->data=e; new->next=rear->next;

rear->next=new; rear =new;

}

2、已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。

栈的ADT函数有：

void makeEmpty(SqStack s); 置空栈

void push(SqStack s,ElemType e); 元素e入栈

ElemType pop(SqStack s); 出栈，返回栈顶元素

int isEmpty(SqStack s); 判断栈空

队列的ADT函数有：

void enQueue(Queue q,ElemType e); 元素e入队

ElemType deQueue(Queue q); 出队，返回队头元素

int isEmpty(Queue q); 判断队空

答案：void QueueInvent(Queue q)

{ ElemType x;

makeEmpty(SqStack s);

while(!isEmpty(Queue q))

{x=deQueue(Queue q);

push(SqStack s, ElemTypex);}

while(!isEmpty(SqStack s))

{x=pop(SqStack s);

enQueue(Queue q, ElemType x);}

}

3、对于一个栈，给出输入项A,B,C,D，如果输入项序列为A,B,C,D，试给出全部可能的输出序列。

答案：出栈的可能序列：

ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA

CBDA CBAD CDBA DCBA

第四章串

一、选择题

1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ C ）。

A. 连接

B. 求子串

C. 模式匹配

D. 判断子串

2、已知串S=’aaab’，则next数组值为（A）。

A. 0123

B. 1123

C. 1231

D. 1211

3、串与普通的线性表相比较，它的特殊性体现在（ C）。

A. 顺序的存储结构

B. 链式存储结构

C. 数据元素是一个字符

D. 数据元素任意

4、设串长为n，模式串长为m，则KMP算法所需的附加空间为（ A ）。

m)

A. O(m)

B. O(n)

C. O(m*n)

D. O(nlog

2

5、空串和空格串（ B ）。

A. 相同

B. 不相同

C. 可能相同

D. 无法确定

6、与线性表相比，串的插入和删除操作的特点是（ A）。

A. 通常以串整体作为操作对象

B. 需要更多的辅助空间

C. 算法的时间复杂度较高

D. 涉及移动的元素更多

7、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ B ）。

A. ‘ijing’

B. ‘jing&’

C.‘ingNa’

D. ‘ing&N’

二、判断题

（对）1、造成简单模式匹配算法BF算法执行效率低的原因是有回溯存在。（对）2、KMP算法的最大特点是指示主串的指针不需要回溯。

（对）3、完全二叉树某结点有右子树，则必然有左子树。

三、填空题

1、求子串在主串中首次出现的位置的运算称为。

答案：模式匹配

2、设s=’I︺AM︺A︺TEACHER’,其长度是。

答案：14

3、两个串相等的充分必要条件是两个串的长度相等且。

答案：对应位置的字符也相同

四、程序填空题

1、函数kmp实现串的模式匹配，请在空格处将算法补充完整。

int kmp(sqstring *s,sqstring *t,int start,int next[]){

int i=start-1,j=0;

while(ilen&&jlen)

if(j==-1||s->data[i]==t->data[j]){

i++;j++;

}

else j= next[j] ;

if(j>=t->len)

return( i-t->len );

else

return(-1);

}

2、函数实现串的模式匹配算法，请在空格处将算法补充完整。int index_bf(sqstring*s,sqstring *t,int start){

int i=start-1,j=0;

while(ilen&&jlen)

if(s->data[i]==t->data[j]){

i++;j++;

}else{

i= i-j+1 ;j=0;

}

if(j>=t->len)

return i-t->len+1 ;

else

return -1;

}}/*listDelete*/

3、写出下面算法的功能。

int function(SqString *s1,SqString *s2){

int i;

for(i=0;ilength&&ilength;i++)

if(s->data[i]!=s2->data[i])

return s1->data[i]-s2->data[i];

return s1->length-s2->length;

}

答案：.串比较算法

4、写出算法的功能。

int fun(sqstring *s,sqstring *t,int start){

int i=start-1,j=0;

while(ilen&&jlen)

if(s->data[i]==t->data[j]){

i++;j++;

}else{

i=i-j+1;j=0;

}

if(j>=t->len)

return i-t->len+1;

else

return -1;

}

答案：串的模式匹配算法

第五章数组和广义表

一、选择题

1、设广义表L=((a，b，c))，则L的长度和深度分别为（C）。

A. 1和1

B. 1和3

C. 1和2

D. 2和3

2、广义表((a),a)的表尾是（ B ）。

A. a

B. (a)

C. ()

D. ((a))

3、稀疏矩阵的常见压缩存储方法有（ C ）两种。

A. 二维数组和三维数组

B. 三元组和散列表

C. 三元组和十字链表

D. 散列表和十字链表

4、一个非空广义表的表头（D）。

A. 不可能是子表

B. 只能是子表

C. 只能是原子

D. 可以是子表或原子

5、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（ A ）。

A. 1175

B. 1180

C. 1205

D. 1210

6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ A ）。

A. 3

B. 4

C. 7

D. 8

7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ B ）。

A. 正确

B. 错误

C. 无法确定

D. 以上均不对

8、广义表(a,b,c)的表尾是（ B ）。

A. b,c

B. (b,c)

C. c

D. (c)

9、常对数组进行两种基本操作是（ C ）。

A. 建立和删除

B. 索引和修改

C. 查找和修改

D. 查找与索引

10、对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）。

A. 表达变得简单

B.对矩阵元素的存取变得简单

C. 去掉矩阵中的多余元素

D. 减少不必要的存储空间的开销

11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A. 13

B. 33

C. 18

D. 40

12、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ A ）。

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

13、广义表A=((a),a)的表头是（ B ）。

A. a

B. (a)

C. b

D. ((a))

数据结构模拟题(开卷)

《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s

数据结构试题及答案(免费)

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。

数据结构试卷带答案

数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构模拟试题及答案

数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素

《数据结构》题库及答案

《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。

数据结构考试题库

绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系

4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。

《数据结构C》模拟试题

山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。

数据结构试题及答案(10套最新)

单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 )

数据结构试题及答案

数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为

数据结构考试题库含答案

数据结构习题集含答案 目录

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性

7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;

《数据结构》模拟试卷一及答案

模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( )

算法与数据结构题库与答案

一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL;

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i

数据结构模拟试卷(含答案)

数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。

A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

数据结构试题(含答案)

数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。