当前位置:文档之家› 数据结构(C语言版)第三版__清华大学出版社_习题参考答案

数据结构(C语言版)第三版__清华大学出版社_习题参考答案

数据结构(C语言版)第三版__清华大学出版社_习题参考答案
数据结构(C语言版)第三版__清华大学出版社_习题参考答案

今天多一份拼搏明天多几份欢笑。

附录习题参考答案

习题1参考答案

1.1.选择题

(1). A. (2). A. (3). A. (4). B.

C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A.

1.2.填空题

(1). 数据关系

(2). 逻辑结构物理结构

(3). 线性数据结构树型结构图结构

(4). 顺序存储链式存储索引存储散列表(Hash)存储

(5). 变量的取值范围操作的类别

(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系

(7). 关系网状结构树结构

(8). 空间复杂度和时间复杂度

(9). 空间时间

(10). Ο(n)

1.3 名词解释如下:

数据:数据是信息的载体

是计算机程序加工和处理的对象

包括数值数据和非数值数据

数据项:数据项指不可分割的、具有独立意义的最小数据单位

数据项有时也称为字段或域

数据元素:数据元素是数据的基本单位

在计算机程序中通常作为一个整体进行考虑和处理

一个数据元素可由若干个数据项组成

数据逻辑结构:数据的逻辑结构就是指数据元素间的关系

数据存储结构:数据的物理结构表示数据元素的存储方式或者数据元素的物理关系数据类型:是指变量的取值范围和所能够进行的操作的总和

算法:是对特定问题求解步骤的一种描述

是指令的有限序列

1.4 语句的时间复杂度为:

(1) Ο(n2)

(2) Ο(n2)

(3) Ο(n2)

(4) Ο(n-1)

(5) Ο(n3)

1.5 参考程序:main()

{

int X

Y

Z;

scanf("%d %d

%d"

&X

&Y

Z);

if (X>=Y)

if(X>=Z)

if (Y>=Z) { printf("%d %d

%d"

X

Y

Z);}

else

{ printf("%d %d

%d"

X

Z

Y);}

else

{ printf("%d %d

%d"

Z

X

Y);}

else if(Z>=X)

if (Y>=Z) { printf("%d %d

%d"

Y

Z

X);}

else

{ printf("%d

%d

%d"

Z

Y

X);}

else

{ printf("%d

%d

%d"

Y

X

Z);}

}

1.6 参考程序:

main()

{

int i

n;

float x

a[]

p;

printf("\nn=");scanf("%f"

&n);

printf("\nx=");scanf("%f"

&x);

for(i=0;i<=n;i++)

scanf("%f "

&a[i]);

p=a[0];

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

{ p=p+a[i]*x;

x=x*x;}

printf("%f"

p)'

}

习题2参考答案

2.1选择题

(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.

2.2.填空题

(1). 有限序列

(2). 顺序存储和链式存储

(3). O(n) O(n)

(4). n-i+1 n-i

(5). 链式

(6). 数据指针

(7). 前驱后继

(8). Ο(1) Ο(n)

(9). s->next=p->next; p->next=s ;

(10). s->next

2.3. 解题思路:将顺序表A中的元素输入数组a

若数组a中元素个数为n

将下标为0

1

2

...

(n-1)/2的元素依次与下标为n

n-1

...

(n-1)/2的元素交换

输出数组a的元素

参考程序如下:

main()

{

int i

n;

float t

a[];

printf("\nn=");scanf("%f"

&n);

for(i=0;i<=n-1;i++)

scanf("%f "

&a[i]);

for(i=0;i<=(n-1)/2;i++)

{ t=a[i]; a[i] =a[n-1-i]; a[n-1-i]=t;} for(i=0;i<=n-1;i++)

printf("%f"

a[i]);

}

2.4 算法与程序:

main()

{

int i

n;

float t

a[];

printf("\nn=");scanf("%f"

&n);

for(i=0;i

scanf("%f "

&a[i]);

for(i=1;i

if(a[i]>a[0]

{ t=a[i]; a[i] =a[0]; a[0]=t;}

printf("%f"

a[0]);

for(i=2;i

if(a[i]>a[1]

{ t=a[i]; a[i] =a[1]; a[1]=t;}

printf("%f"

a[0]);

}

2.5 算法与程序:

main()

{

int i

j

k

n;

float x

t

a[];

printf("\nx=");scanf("%f"

&x);

printf("\nn=");scanf("%f"

&n);

for(i=0;i

scanf("%f "

&a[i]); // 输入线性表中的元素

for (i=0; i

k=i;

for (j=i+1; jj) {t=a[i];a[i]=a[k];a[k]=t;}

}

for(i=0;i

if(a[i]>x) break;

for(k=n-1;k>=i;i--) // 移动线性表中元素

然后插入元素x

a[k+1]=a[k];

a[i]=x;

for(i=0;i<=n;i++) // 依次输出线性表中的元素printf("%f"

a[i]);

}

2.6 算法思路:依次扫描A和B的元素

比较A、B当前的元素的值

将较小值的元素赋给C

如此直到一个线性表扫描完毕

最后将未扫描完顺序表中的余下部分赋给C即可

C的容量要能够容纳A、B两个线性表相加的长度

有序表的合并算法:

void merge (SeqList A

SeqList B

SeqList *C)

{ int i

j

k;

i=0;j=0;k=0;

while ( i<=https://www.doczj.com/doc/411676244.html,st && j<=https://www.doczj.com/doc/411676244.html,st )

if (A.data[i]<=B.data[j])

C->data[k++]=A.data[i++];

else

C->data[k++]=B.data[j++];

while (i<=https://www.doczj.com/doc/411676244.html,st )

C->data[k++]= A.data[i++];

while (j<=https://www.doczj.com/doc/411676244.html,st )

C->data[k++]=B.data[j++];

C->last=k-1;

}

2.7 算法思路:依次将A中的元素和B的元素比较

将值相等的元素赋给C

如此直到线性表扫描完毕

线性表C就是所求递增有序线性表

算法:

void merge (SeqList A

SeqList B

SeqList *C)

{ int i

j

k;

i=0;j=0;k=0;

while ( i<=https://www.doczj.com/doc/411676244.html,st)

while(j<=https://www.doczj.com/doc/411676244.html,st )

if (A.data[i]=B.data[j])

C->data[k++]=A.data[i++];

C->last=k-1;

}

习题3参考答案

3.1.选择题

(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB (11). D (12). B (13). D (14). C (15). C (16). D(17). D (18). C (19). C (20). C 3.2.填空题

(1) FILO

FIFO

(2) -1

3 4 X * + 2 Y * 3 / -

(3) stack.top

stack.s[stack.top]=x

(4) p>llink->rlink=p->rlink

p->rlink->llink=p->rlink

(5) (R-F+M)%M

(6) top1+1=top2

(7) F==R

(8) front==rear

(9) front==(rear+1)%n

(10) N-1

3.3 答:一般线性表使用数组来表示的

线性表一般有插入、删除、读取等对于任意元素的操作

而栈只是一种特殊的线性表

栈只能在线性表的一端插入(称为入栈

push)或者读取栈顶元素或者称为"弹出、出栈"(pop)

3.4 答:相同点:栈和队列都是特殊的线性表

只在端点处进行插入

删除操作

不同点:栈只在一端(栈顶)进行插入

删除操作;队列在一端(top)删除

一端(rear)插入

3.5 答:可能序列有14种:ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA

3.6 答:不能得到4

3

5

6

1

2

最先出栈的是4

则按321的方式出

不可能得到1在2前的序列

可以得到1

3

5

4

2

6

按如下方式进行push(1)

pop()

push(2)

push(3)

pop()

push(4)

push(5)

pop()

pop()

pop()

push(6)

pop()

3.7 答:stack

3.8 非递归:

int vonvert (int no

int a[]) //将十进制数转换为2进制存放在a[] 并返回位数

{

int r;

SeStack s

*p;

P=&s;

Init_stack(p);

while(no)

{

push(p

no%2);

no/=10;

}

r=0;

while(!empty_stack(p))

{

pop(p

a+r);

r++;

}

return r;

}

递归算法:

void convert(int no)

{

if(no/2>0)

{

Convert(no/2);

Printf("%d"

no%2);

}

else

printf("%d"

no);

}

3.9 参考程序:

void view(SeStack s)

{

SeStack *p; //假设栈元素为字符型

char c;

p=&s;

while(!empty_stack(p))

{

c=pop(p);

printf("%c"

c);

}

printf("\n");

}

3.10 答:char

3.11 参考程序:

void out(linkqueue q)

{

int e;

while(q.rear !=q.front )

{

dequeue(q

e);

print(e); //打印

}

}

习题4参考答案

4.1 选择题:

(1). A (2). D (3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D 4.2 填空题:

(1)串长相等且对应位置字符相等

(2)不含任何元素的串

(3)所含字符均是空格

所含空格数

(4) 10

(5) "hello boy"

(6) 13

(7) 1066

(8)模式匹配

(9)串中所含不同字符的个数

(10) 36

4.3 StrLength (s)=14

StrLength (t)=4

SubStr( s

8

7)=" STUDENT"

SubStr(t

2

1)="O"

StrIndex(s

"A")=3

StrIndex (s

t)=0

StrRep(s

"STUDENT"

q)=" I AM A WORKER"

4.4 StrRep(s

"Y"

"+");StrRep(s

"+*"

"*Y");

4.5 空串:不含任何字符;空格串:所含字符都是空格

串变量和串常量:串常量在程序的执行过程中只能引用不能改变;串变量的值在程序执行过程中是可以改变和重新赋值的

主串与子串:子串是主串的一个子集

串变量的名字与串变量的值:串变量的名字表示串值的标识符

4.6

int EQUAl(S

T)

{

char *p

*q;

p=&S;

q=&T;

while(*p&&*q)

{

if(*p!=*q)

return *p-*q;

p++;

q++;

}

return *p-*q;

}

4.7

(1)6*8*6=288

(2)1000+47*6=1282

(3)1000+(8+4)*8=1096

(4)1000+(6*7+4)*8=1368

4.8

习题5参考答案

5.1 选择

(1)C(2)B(3)C(4)B(5)C(6)D(7)C(8)C(9)B(10)C (11)B(12)C(13)C(14)C(15)C(16)B

5.2 填空

(1)1

(2)1036;1040

(3)2i

(4) 1 ; n ; n-1 ; 2

(5)2k-1;2k-1

(6)ACDBGJKIHFE

(7)p!=NULL

(8)Huffman树

(9)其第一个孩子; 下一个兄弟

(10)先序遍历;中序遍历

5.3

叶子结点:C、F、G、L、I、M、K;

非终端结点:A、B、D、E、J;

各结点的度:

结点: A B C D E F G L I J K M

度: 4 3 0 1 2 0 0 0 0 1 0 0

树深:4

无序树形态如下:

二叉树形态如下:

5.5

二叉链表如下:

三叉链表如下:

5.6

先序遍历序列:ABDEHICFJG

中序遍历序列:DBHEIAFJCG

后序遍历序列:DHIEBJFGCA

5.7

(1) 先序序列和中序序列相同:空树或缺左子树的单支树;

(2) 后序序列和中序序列相同:空树或缺右子树的单支树;

(3) 先序序列和后序序列相同:空树或只有根结点的二叉树

5.8

这棵二叉树为:

先根遍历序列:ABFGLCDIEJMK

后根遍历序列:FGLBCIDMJKEA

层次遍历序列:ABCDEFGLIJKM

5.10

证明:设树中结点总数为n

叶子结点数为n0

n=n0 + n1 + ...... + nm (1)

再设树中分支数目为B

B=n1 + 2n2 + 3n3 + ...... + m nm (2)

因为除根结点外

每个结点均对应一个进入它的分支

所以有

n= B + 1 (3)

将(1)和(2)代入(3)

n0 + n1 + ...... + nm = n1 + 2n2 + 3n3 + ...... + m nm + 1 从而可得叶子结点数为:

n0 = n2 + 2n3 + ...... + (m-1)nm + 1

5.11

由5.10结论得

n0 = (k-1)nk + 1

又由 n=n0 + nk

得nk= n-n0

代入上式

n0 = (k-1)(n-n0)+ 1

叶子结点数为:n0 = n (k-1) / k

5.12

int NodeCount(BiTree T)

{ //计算结点总数

if(T)

if (T-> lchild==NULL )&&( T --> rchild==NULL )

return 1;

else

return NodeCount(T-> lchild ) +Node ( T --> rchild )+1; else

return 0;

}

void ExchangeLR(Bitree bt){

/* 将bt所指二叉树中所有结点的左、右子树相互交换 */ if (bt && (bt->lchild || bt->rchild)) {

bt->lchild<->bt->rchild;

Exchange-lr(bt->lchild);

Exchange-lr(bt->rchild);

}

}/* ExchangeLR */

5.14

int IsFullBitree(Bitree T)

{/* 是则返回1

否则返回0

*/

Init_Queue(Q); /* 初始化队列*/

flag=0;

In_Queue(Q

T); /* 根指针入队列

按层次遍历*/

while(!Empty_Queue (Q))

{

Out_Queue(Q

p);

if(!p) flag=1; /* 若本次出队列的是空指针时

则修改flag值为1

若以后出队列的指针存在非空

则可断定不是完全二叉树 */

else if (flag) return 0; /*断定不是完全二叉树 */ else

{

In_Queue(Q

p->lchild);

In_Queue(Q

p->rchild); /* 不管孩子是否为空

都入队列

*/

}

}/* while */

return 1; /* 只有从某个孩子指针开始

之后所有孩子指针都为空

才可断定为完全二叉树*/

}/* IsFullBitree */

转换的二叉树为:

5.16

对应的森林分别为:

5.17

typedef char elemtype;

typedef struct

{ elemtype data;

int parent;

} NodeType;

(1) 求树中结点双亲的算法:

int Parent(NodeType t[ ]

elemtype x){

/* x不存在时返回-2

否则返回x双亲的下标(根的双亲为-1 */

for(i=0;i

if(x==t[i].data) return t[i].parent; return -2;

}/*Parent*/

(2) 求树中结点孩子的算法:

void Children(NodeType t[ ]

elemtype x){

for(i=0;i

if(x==t[i].data)

break;/*找到x

退出循环*/

}/*for*/

if(i>=MAXNODE) printf("x不存在\n"); else {

flag=0;

for(j=0;j

if(i==t[j].parent)

{ printf("x的孩子:%c\n"

t[j].data);

flag=1;

}

if(flag==0) printf("x无孩子\n");

}/*Children*/

5.18

typedef char elemtype;

typedef struct ChildNode

{ int childcode;

struct ChildNode *nextchild;

}

typedef struct

{ elemtype data;

struct ChildNode *firstchild;

} NodeType;

(1) 求树中结点双亲的算法:

int ParentCL(NodeType t[ ]

elemtype x){

/* x不存在时返回-2

否则返回x双亲的下标 */

for(i=0;i

if(x==t[i].data) {

loc=i;/*记下x的下标*/

break;

}

if(i>=MAXNODE) return -2; /* x不存在 */

/*搜索x的双亲*/

for(i=0;i

for(p=t[i].firstchild;p!=NULL;p=p->nextchild) if(loc==p->childcode)

return i; /*返回x结点的双亲下标*/

}/* ParentL */

(2) 求树中结点孩子的算法:

void ChildrenCL(NodeType t[ ]

elemtype x){

for(i=0;i

if(x==t[i].data) /*依次打印x的孩子*/

{

flag=0; /* x存在 */

for(p=t[i].firstchild;p;p=p->nextchild)

{ printf("x的孩子:%c\n"

t[p-> childcode].data);

flag=1;

}

if(flag==0) printf("x无孩子\n");

return;

}/*if*/

printf("x不存在\n");

return;

}/* ChildrenL */

5.19

typedef char elemtype;

typedef struct TreeNode

{ elemtype data;

struct TreeNode *firstchild; struct TreeNode *nextsibling; } NodeType;

void ChildrenCSL(NodeType *t

elemtype x){ /* 层次遍历方法 */

Init_Queue(Q); /* 初始化队列 */

In_Queue(Q

t);

count=0;

while(!Empty_Queue (Q)){

Out_Queue(Q

p);

if(p->data==x)

{ /*输出x的孩子*/

p=p->firstchild;

if(!p) printf("无孩子\n");

else

{ printf("x的第%i个孩子:%c\n"

++count

p->data);/*输出第一个孩子*/

p=p->nextsibling; /*沿右分支*/

while(p){

printf("x的第%i个孩子:%c\n"

++count

p->data);

p=p-> nextsibling;

}

}

return;

}

if(p-> firstchild) In_Queue(Q

p-> firstchild);

if(p-> nextsibling) In_Queue(Q

p-> nextsibling);

}

}/* ChildrenCSL */

5.20

(1) 哈夫曼树为:

(2) 在上述哈夫曼树的每个左分支上标以1

右分支上标以0

并设这7个字母分别为A、B、C、D、E、F和H

如下图所示:

则它们的哈夫曼树为分别为:

A:1100

B:1101

C:10

D:011

E:00

F:010

H:111

习题6参考答案

6.1 选择题

(1)C (2)A (3)B(4)C(5)B______条边

(6)B(7)A(8)A(9)B(10)A

(11)A(12)A(13)B(14)A(15)B(16)A(17)C 6.2 填空

(1) 4

(2) 1对多 ; 多对多

(3) n-1 ; n

(4) 0_

(5)有向图

(6) 1

(7)一半

(8)一半

(9)___第i个链表中边表结点数___

(10)___第i个链表中边表结点数___

(11)深度优先遍历;广度优先遍历

(12)O(n2)

(13)___无回路

6.3

(1)邻接矩阵:

(2)邻接链表:

(3)每个顶点的度:

顶点度

V1 3

V2 3

V3 2

V4 3

V5 3

6.4

(1)邻接链表:

(2)逆邻接链表:

(3)顶点入度出度

V1 3 0

V2 2 2

V3 1 2

V4 1 3

V5 2 1

V6 2 3

6.5

(1)深度优先查找遍历序列:V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2 (1)广度优先查找遍历序列:V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V5

6.6

有两个连通分量:

6.7

顶点

(1)

(2)

(3)

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C)

数据结构C语言版期末考试试题(有答案)

“数据结构”期末考试试题 一、单选题(每小题2分,共12分) 1.在一个单链表HL中,若要向表头插入一个由指针p指向的结点,则执行( )。 A. HL=ps p一>next=HL B. p一>next=HL;HL=p3 C. p一>next=Hl;p=HL; D. p一>next=HL一>next;HL一>next=p; 2.n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)/2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( )。 A.24 B.48 C. 72 D. 53 5.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时,应最好把它说明为( )参数,以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6.向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A.O(n) B.O(1) C.O(n2) D.O(10g2n) 二、填空题(每空1分,共28分) 1.数据的存储结构被分为——、——、——和——四种。 2.在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分别为——域和——域。 3.——中缀表达式 3十x*(2.4/5—6)所对应的后缀表达式为————。 4.在一棵高度为h的3叉树中,最多含有——结点。 5.假定一棵二叉树的结点数为18,则它的最小深度为——,最大深度为——· 6.在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定——该结点的值,右子树上所有结点的值一定——该结点的值。 7.当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层——调整,直到被调整到——位置为止。 8.表示图的三种存储结构为——、——和———。 9.对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时,其时间复杂度为——,对用邻接表表示的图进行任一种遍历时,其时间复杂度为——。 10.从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时,其查找长度分别为——和——· 11.假定对长度n=144的线性表进行索引顺序查找,并假定每个子表的长度均

数据结构习题及参考答案

习题1 一、单项选择题 A1.数据结构是指()。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为()。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种()。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间,则以下语句的时间复杂度为()。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是(1),算法分析的两个主要方面是(2)。 (1) A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 (2) A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是(1),它具备输入,输出和(2)等五个特性。 (1) A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 (2) A.可行性,可移植性和可扩充性 B.可行性,确定性和有穷性 C.确定性,有穷性和稳定性 D.易读性,稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储比顺序存储要()。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在()年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构,这种观点()。 A.正确 B.错误 C.前半句对,后半句错 D.前半句错,后半句对

数据结构复习题集答案(c语言版严蔚敏)

人生难得几回搏,此时不搏更待何时? 第1章绪论 1.1 简述下列术语:数据 数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型 解:数据是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的基本单位 在计算机程序常作为一个整体进行考虑和处理 数据对象是性质相同的数据元素的集合 是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 存储结构是数据结构在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 解:抽象数据类型包含一般数据类型的概念 但含义比一般数据类型更广、更抽象 一般数据类型由具体语言系统部定义 直接提供给编程者定义用户数据 因此称它们为预定义数据类型 抽象数据类型通常由编程者定义 包括定义它所使用的数据和在这些数据上所进行的操作 在定义抽象数据类型中的数据部分和操作部分时 要求只定义到数据的逻辑结构和操作说明 不考虑数据的存储结构和操作的具体实现 这样抽象层次更高 更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中

试按图论中图的画法惯例画出其逻辑结构图 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数) 解: ADT Complex{ 数据对象:D={r i|r i为实数} 数据关系:R={} 基本操作: InitComplex(&C re im) 操作结果:构造一个复数C 其实部和虚部分别为re和im DestroyCmoplex(&C) 操作结果:销毁复数C Get(C k &e) 操作结果:用e返回复数C的第k元的值 Put(&C k e) 操作结果:改变复数C的第k元的值为e IsAscending(C) 操作结果:如果复数C的两个元素按升序排列 则返回1 否则返回0 IsDescending(C) 操作结果:如果复数C的两个元素按降序排列 则返回1 否则返回0 Max(C &e) 操作结果:用e返回复数C的两个元素中值较大的一个 Min(C &e) 操作结果:用e返回复数C的两个元素中值较小的一个

数据结构 习题答案

第1章概论 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①C、数据信息在计算机中的②A以及一组相关的运算等的课程。 ①A.操作对象B.计算方法C.逻辑结构D.数据映象 ②A.存储结构B.关系C.运算D.算法 2. 计算机算法指的是① C ,它必具备输入、输出和② B 等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 3.下面程序段的时间复杂度是D for(i=0;inext = p; p->next = s; B. s->next = p->next; p->next = s; C. s->next = p->next; p = s; D. p->next = s; s->next = p; 2.非空的不带头结点的循环单链表,首结点由first指向,尾结点由p指向,则满足: C A. p->next == NULL; B. p == NULL; C. p->next == first; D. p == first; 3.在一个长度为n的顺序存储的线性表中,删除第i个元素(0≤i≤n-1)时,需要移动多少个元素?C A. n-i B. n-i+1 C. n-i-1 D. I 4.在带头结点指针head的单链表中,链表为空的判断条件是?B A. head == NULL B. head->next == NULL C. head != NULL D. head->next == head; 5.在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是B A. p=p->next; B. p->next=p->next->next; C. p->next=p; D. p=p->next->next;

数据结构c语言版期末考试复习试题

《数据结构与算法》复习题 一、选择题。 1在数据结构中,从逻辑上可以把数据结构分为 C 。 A ?动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2?数据结构在计算机内存中的表示是指_A_。 A .数据的存储结构B.数据结构 C .数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的A结构。 A .逻辑 B .存储C.逻辑和存储 D .物理 4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_C A .数据的处理方法 B .数据元素的类型 C.数据元素之间的关系 D .数据的存储方法 5.在决定选取何种存储结构时,一般不考虑A A .各结点的值如何C.对数据有哪些运算 B .结点个数的多少 D .所用的编程语言实现这种结构是否方 6.以下说法正确的是D A .数据项是数据的基本单位 B .数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D .一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ,算法分析的两个主要方面是 A 。 (1) A .找出数据结构的合理性B.研究算法中的输入和输出的关系 C .分析算法的效率以求改进C.分析算法的易读性和文档性 (2) A .空间复杂度和时间复杂度B.正确性和简明性 &下面程序段的时间复杂度是0( n2) s =0; for( I =0; i

数据结构(C语言版)复习题概论

一、单项选择题: 1、树形结构不具备这样的特点:() A. 每个节点可能有多个后继(子节点) B. 每个节点可能有多个前驱(父节点) C. 可能有多个内节点(非终端结点) D. 可能有多个叶子节点(终端节点) 2、二叉树与度数为2的树相同之处包括()。 A. 每个节点都有1个或2个子节点 B. 至少有一个根节点 C. 至少有一个度数为2的节点 D. 每个节点至多只有一个父节点 3、一棵完全二叉树有999 个结点,它的深度为()。 A.9 B.10 C.11 D.12 4、在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行() A. s->next=p;p->next=s; B. s->next=p->next;p->next=s; C. s->next=p->next;p=s; D. p->next=s;s->next=p; 5、对于一棵具有n个结点、度为5的树来说,() A. 树的高度至多是n-3 B. 树的高度至多是n-4 C. 树的高度至多是n D. 树的高度至多是n-5 6、在顺序队列中,元素的排列顺序()。 A. 由元素插入队列的先后顺序决定 B. 与元素值的大小有关 C. 与队首指针和队尾指针的取值有关 D. 与数组大小有关 7、串是一种特殊的线性表,其特殊性体现在()。 A.可以顺序存储 B.数据元素是一个字符 C.可以链式存储 D.数据元素可以是多个字符若 8、顺序循环队列中(数组的大小为 6),队头指示 front 和队尾指示 rear 的值分别为 3 和 0,当从队列中删除1个元素,再插入2 个元素后,front和 rear的值分别为()。 A.5 和1 B.2和4 C.1和5 D.4 和2 9、一棵完全二叉树上有1001 个结点,其中叶子结点的个数为()。 A.250 B.500 C.254 D.501 10、已知一个有向图如下图所示,则从顶点a出发进行深度优先遍历,不可能得到的DFS序 列为()。 A.adbefc B.adcefb C.adcebf D.adefbc

数据结构习题及答案——严蔚敏

第一章绪论 一、选择题 1.组成数据的基本单位是() (A)数据项(B)数据类型(C)数据元素(D)数据变量 2.数据结构是研究数据的()以及它们之间的相互关系。 (A)理想结构,物理结构(B)理想结构,抽象结构 (C)物理结构,逻辑结构(D)抽象结构,逻辑结构 3.在数据结构中,从逻辑上可以把数据结构分成() (A)动态结构和静态结构(B)紧凑结构和非紧凑结构 (C)线性结构和非线性结构(D)内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的(①)以及它们之间的(②)和运算等的学科。 ① (A)数据元素(B)计算方法(C)逻辑存储(D)数据映像 ② (A)结构(B)关系(C)运算(D)算法 5.算法分析的目的是()。 (A)找出数据结构的合理性(B)研究算法中的输入和输出的关系 (C)分析算法的效率以求改进(D)分析算法的易懂性和文档性 6.计算机算法指的是(①),它必须具备输入、输出和(②)等5 个特性。 ① (A)计算方法(B)排序方法(C)解决问题的有限运算序列(D)调度方法

② (A)可执行性、可移植性和可扩充性(B)可行性、确定性和有穷性 (C)确定性、有穷性和稳定性(D)易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。() 2.算法就是程序。() 3.数据元素是数据的最小单位。() 4.算法的五个特性为:有穷性、输入、输出、完成性和确定性。() 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。() 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点;最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点;叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、

数据结构(c语言版)期末考试复习试题

《数据结构与算法》(c语言版)期末考复习题 一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指 A 。 A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A.逻辑B.存储C.逻辑和存储D.物理 4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C 。A.数据的处理方法B.数据元素的类型 C.数据元素之间的关系D.数据的存储方法 5.在决定选取何种存储结构时,一般不考虑 A 。 A.各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 D 。 A.数据项是数据的基本单位

B.数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ,算法分析的两个主要方面是 A 。(1)A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进C.分析算法的易读性和文档性(2)A.空间复杂度和时间复杂度B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 8.下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

数据结构习题与答案

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

数据结构(C语言版)期末复习

数据结构(C语言版)期末复习汇总 第一章绪论 数据结构:是一门研究非数值计算程序设计中的操作对象,以及这些对象之间的关系和操作的学科。 数据结构分为:逻辑结构、物理结构、操作三部分 逻辑结构:集合、线性结构、树形结构、图(网)状结构 物理结构(存储结构):顺序存储结构、链式存储结构 算法:是为了解决某类问题而规定的一个有限长的操作序列。 算法五个特性:有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准(4个):正确性、可读性、健壮性、高效性及低存储量 语句频度的计算。 算法的时间复杂度: 常见有:O(1),O(n),O(n2),O(log2n),O(nlog2n),O(2n) 第二章线性表 线性表的定义和特点: 线性表:由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度,n=0时称为空表。 非空线性表或线性结构,其特点: (1)存在唯一的一个被称作“第一个”的数据元素; (2)存在唯一的一个被称作“最有一个”的数据元素; (3)除第一个之外,结构中的每个数据元素均只有一个前驱; (4)除最后一个之外,结构中的每个数据元素均只有一个后继。 顺序表的插入:共计n个元素,在第i位插入,应移动(n-i+1)位元素。 顺序表的删除:共计n个元素,删除第i位,应移动(n-i)位元素。 线性表的两种存储方式:顺序存储、链式存储。 顺序存储 概念:以一组连续的存储空间存放线性表; 优点:逻辑相邻,物理相邻;可随机存取任一元素;存储空间使用紧凑; 缺点:插入、删除操作需要移动大量的元素;预先分配空间需按最大空间分配,利用不充分;表容量难以扩充; 操作:查找、插入、删除等 查找: ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i

数据结构C语言版(第2版)严蔚敏人民邮电出版社课后习题答案

数据结构(C语言版)(第2版) 课后习题答案 李冬梅 2015.3

目录 第1章绪论 (1) 第2章线性表 (5) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (43) 第7章查找 (54) 第8章排序 (65)

第1章绪论 1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案: 数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构:数据对象在计算机中的存储表示,也称为物理结构。 抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案: 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。 即相同的逻辑结构,可以对应不同的存储结构。 3.简述逻辑结构的四种基本关系并画出它们的关系图。

数据结构习题参考答案

第1章概论 1.数据、数据元素、数据结构、数据类型的含义分别是什么? 数据:对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素:数据的基本单位,在计算机程序中通常作为一个整体考虑。 数据结构:数据元素之间的关系+运算,是以数据为成员的结构,是带结构的数据元素的集合,数据元素之间存在着一种或多种特定的关系。 数据类型:数据类型是用来区分不同的数据;由于数据在存储时所需要的容量各不相同,不同的数据就必须要分配不同大小的内存空间来存储,所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构?什么是数据的物理结构?数据的逻辑结构与物理结构的区别和联系是什么? 逻辑结构:数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息: ①数据元素的信息; ②各数据元素之间的关系。 物理结构:也叫储存结构,是指逻辑结构的存储表示,即数据的逻辑结构在计算机存储空间中的存放形式,包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的,一个操作算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所采与的存储结构。采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处理时,针对不同问题,选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些? 对于各种数据结构而言,他们在基本操作上是相似的,最常用的操作有: ●创建:建立一个数据结构; ●清除:清除一个数据结构; ●插入:在数据结构中增加新的结点; ●删除:把指定的结点从数据结构中删除; ●访问:对数据结构中的结点进行访问; ●更新:改变指定结点的值或改变指定的某些结点之间的关系; ●查找:在数据结构中查找满足一定条件的结点; ●排序:对数据结构中各个结点按指定数据项的值,以升序或降序重新排列。 4.什么是抽象数据类型?如何定义抽象数据类型? 抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型,因此,不论ADT的内部结构如何变化,只要其数据结构的特性不变,都不影响其外部使用。 对抽象数据类型的描述一般用(D,R,P)三元组表示,抽象数据类型的定义格式为: ADT<抽象数据类型名> { 数据对象D:<数据对象的定义> 数据关系R:<数据关系的定义> 基本操作P:<基本操作的定义>

数据结构(c语言版)课后习题答案完整版

第1章绪论 5.选择题:CCBDCA 6.试分析下面各程序段的时间复杂度。 (1)O(1) (2)O(m*n) (3)O(n2) (4)O(log3n) (5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2) (6)O(n) 第2章线性表 1.选择题 babadbcabdcddac 2.算法设计题 (6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; } return pmax->data; (7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。 void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; }

} (10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。 [题目分析] 在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动(删第i个元素,第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素,并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1,j=n),从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为item的数据元素位置。 void Delete(ElemType A[ ],int n) ∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素。 {i=1;j=n;∥设置数组低、高端指针(下标)。 while(i

数据结构习题及答案

习题八查找 一、单项选择题 1.顺序查找法适合于存储结构为()的线性表。 A.散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 3.适用于折半查找的表的存储方式及元素排列要求为( ) A.链接方式存储,元素无序 B.链接方式存储,元素有序 C.顺序方式存储,元素无序 D.顺序方式存储,元素有序 4.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( ) A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5.当采用分块查找时,数据的组织方式为 ( ) A.数据分成若干块,每块内数据有序 B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块 C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块 D. 数据分成若干块,每块(除最后一块外)中数据个数需相同 6.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法()。 A.正确 B. 错误 7. 二叉查找树的查找效率与二叉树的((1) )有关, 在 ((2) )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )。 A.(100,80, 90, 60, 120,110,130) B.(100,120,110,130,80, 60, 90) C.(100,60, 80, 90, 120,110,130) D. (100,80, 60, 90, 120,130,110) 10.下图所示的4棵二叉树,( )是平衡二叉树。 (A)(B)(C)(D) 11.散列表的平均查找长度()。 A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关且与表的长度有关 D.与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有()个

严蔚敏《数据结构(c语言版)习题集》答案第四章串

《一定能摸到红球吗?》说课稿 林银花 一、教材说明: 1、课题:《一定能摸到红球吗?》 2、本节内容的地位和作用 在现代社会中,人们面临着更多的机会和选择,常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. 3、教学目标设计: (1)认知目标: (A)经历猜测.实验.收集与分析试验结果等过程 (B)体会事件的发生的不确定性知道事情发生的可能性有多大。 (2)、能力目标: (A)经历游戏等的活动过程,初步认识确定事件和不确定事件 (B)在与其它人交流的过程中,能合理清晰地表达自己的思维过程; (3)、情感目标: (A)通过创设游戏情境,让学生主动参与,做“数学实验”,激发学生学习的热情和兴趣,激活学生思维。 (B)在与他人的合作过程中,增强互相帮助、团结协作的精神。 (C)体会到在生活中我们可以从确定和不确定两方面分析一件事情. 4、本课重点、难点分析: 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析: 1、初一学生性格开朗活泼,对新鲜事物特别敏感,且较易接受,因此,教学过程中创设的问题情境应较生动活泼,直观形象,且贴近学生的生活,从而引起学生的有意注意。 2、初一学生的概括能力较弱,推理能力还有待不断发展,所以在教学时,可让学生充分试验,收集,分析,帮助他们直观形象地感知。 3、初一学生已经具备了一定的学习能力,所以本节课中,应多为学生创造自主学习、

数据结构课程__课后习题答案

C.分析算法的效率以求改进 答:C D.分析算法的易懂性和文档性 (5)计算机算法指的是 ()。 答:C 答:B 2. 填空题 答:①逻辑结构 ②存储结构 ③运算 数据结构简明教程》练习题及参考答案 练习题1 1.单项选择题 (1)线性结构中数据元素之间是 ()关系。 A. 一对多 B.多对多 C.多对一 答:D D.—对一 (2)数据结构中与所使用的计算机无关的是数据 的 A.存储 B.物理 答:C C ?逻辑 ()结构。 D.物理和存储 (3)算法分析的目的是 ( A.找出数据结构的合理性 )。 B.研究算法中的输入和输出的关系 (4)算法分析的两个主要方面 是 )。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 答:A D.数据复杂性和程序复杂性 A.计算方法 B.排序方法 C ?求解问题的有限运算序列 D.调度方法 (6)计算机算法必须具备输入 A. 可行性、可移植性和可扩充性 、输出和()等5个特性。 B. 可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 (1)数据结构包括数据的 卫 、数据的 ② 和数据的 ③ 这三个方面的内容。

数据结构简明教程 (2)数据结构按逻辑结构可分为两大类,它们分别是 ①和②。 答:①线性结构②非线性结构 (3)数据结构被形式地定义为(D,R),其中D是① 的有限集合,R是D上的止有限集合。 答:①数据元素②关系 (4)在线性结构中,第一个结点①前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点②后继结点,其余每个结点有且只有1个后继结点。 答:①没有②没有 (5)在树形结构中,树根结点没有①结点,其余每个结点有且只有②个前驱结 点;叶子结点没有③结点,其余每个结点的后继结点数可以是④。 答:①前驱②1③后继④任意多个 (6)在图形结构中,每个结点的前驱结点数和后继结点数可以是 ()。 答:任意多个 (7)数据的存储结构主要有四种,它们分别是①、②、③和④存储结构。答:①顺序②链 式③索引④哈希 (8)一个算法的效率可分为① 效率和② 效率。 答:①时间②空间 3. 简答题 (1)数据结构和数据类型两个概念之间有区别吗? 答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素,而且还在其上定义了一组操作。 (2)简述线性结构、树形结构和图形结构的不同点。 答:线性结构反映结点间的逻辑关系是一对一的,树形线性结构反映结点间的逻辑关系是一对多的,图在结构反映结点间的逻辑关系是多对多的。 (3 )设有采用二元组表示的数据逻辑结构S=(D,R),其中D={ a,b, ?★}, R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)},问相对于关系R,哪些结点是开始结点,哪些结点是终端结点? 答:该逻辑结构为树形结构,其中a结点没有前驱结点,称为根结点,b、e、g、i结点没有后继结点,是终端结点,也称为叶子结点。 (4) 以下各函数是算法中语句的执行频度,n为

数据结构习题及答案

第一章 1.在数据结构中,从逻辑上可以把数据结构分为(C ) A.动态结构和静态结构 B. 紧凑结构和非紧凑结构 C.线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O(mn)_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是(A) A 可以随机访问任一结点(顺序) B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为(A ),带头结点的单链表head为空的判定条件为(B ) A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中,读取元素花费时间最少的是(D) A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表,宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点,并保持链表元素仍然有序, 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上,设有头和尾两个指针,执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比,双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针,则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针,则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续,这句话正确吗? (不正确) 11. 某线性表采用顺序存储结构,元素长度为4,首地址为100,则下标为12的(第13个)元素的存储地址为148。V 100+4*12=148 11.在顺序表的(最后一个结点之后)插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除,则该线性表宜采用(顺序)存储结构,若频繁地对线性表进行插入和删除操作,则该线性表宜采用( 链 )存储结构。

相关主题
相关文档 最新文档