电大数据结构本期末综合练习一.docx

电大数据结构本期末综合练习一.docx

《电大数据结构本期末综合练习一.docx》由会员分享，可在线阅读，更多相关《电大数据结构本期末综合练习一.docx（18页珍藏版）》请在冰点文库上搜索。

电大数据结构本期末综合练习一

数据构造（本）期末综合练习一

一、单项选取题

1．数据元素是数据基本单位，它（）。

A．只能有一种数据项构成B．至少有二个数据项构成

C．至少有一种数据项为指针类型

D．可以是一种数据项也可以由若干个数据项构成

2．（）是性质相似数据元素集合，是数据子集。

A．数据对象B．数据元素C．数据构造D．数据项

3．线性表顺序构造中，（）。

A．逻辑上相邻元素在物理位置上不一定相邻

B．逻辑上相邻元素在物理位置上也相邻

C．数据元素是不能随机访问

D．进行数据元素插入、删除效率较高

4．设链表中结点是NODE类型构造体变量，且有NODE*p；为了申请一种新结点，并由p指向该结点，可用如下语句（）。

A．p=（NODE*）malloc（sizeof（p））;

B．p=（*NODE）malloc（sizeof（NODE））;

C．p=（NODE）malloc（sizeof（p））;

D．p=（NODE*）malloc（sizeof（NODE））;

5．如下表中可以随机访问是（）。

A．单向链表B．顺序表

C．单向循环链表D．双向链表

6．设顺序存储线性长度为n，要在第i个元素之前插入一种新元素，按课本算法当i=（）时，移动元素次数为2

A．n/2B．nC．n-1C．1

7.设顺序存储线性表长度为n，对于删除操作，设删除位置是等概率，则删除一种元素平均移动元素次数为（）。

A．（n+1）/2B．nC．2nD．n-i

8．一种栈进栈序列是1，2，3，4，则栈不也许出栈序列是（）（进出栈操作可以交替进行）

A．3，2，4，1B．3，2，1，4

C．4，3，2，1D．1，4，2，3

9．设top是一种链栈栈顶指针，栈中每个结点由一种数据域data和指针域next构成，设用x接受栈顶元素，则出栈操作为（）。

A．top=top->next;x=top->data；B．x=top->data;top=top->next;

C．x=top->next;top=top->data；D．top->next=top；x=top->data;

10．设有一种带头结点链队列，队列中每个结点由一种数据域data和指针域next构成，front和rear分别为链队列头指针和尾指针。

设p指向要入队新结点（该结点已被赋值），则入队操作为（）。

A．rear->next=p;rear=p；B．rear->next=p；p=rear；

C．p=rear->next;rear=p；D．rear=p;rear->next=p;

11．如下说法对的是（）。

A．队列是后进先出B．栈特点是后进后出

C．栈删除和插入操作都只能在栈顶进行

D．队列删除和插入操作都只能在队头进行

12．如下说法不对的是（）。

A．顺序栈中，栈满时再进行进栈操作称为“上溢”

B．顺序栈中，栈空时再作出栈栈操作称为“下溢”

C．顺序队列中，队列头指针和尾指针均超越队列存储空间上界，则队列已空

D．顺序队列中，当尾指针已经超越队列存储空间上界，则一定是队列已满

13．串函数StrCmp（“abA”,”aba”）值为（）。

A．1B．0C．“abAaba”D．-1

14．设有一种20阶对称矩阵A，采用压缩存储方式，将其下三角某些以行序为主序存储到一维数组中（矩阵A第一种元素为a11，数组b下标从1开始），则矩阵元素a8,5在一维数组b中下标是（）。

A．30B．28C．40D．33

15．设有一种12阶对称矩阵A，采用压缩存储方式将其下三角某些以行序为主序存储到一维数组b中（矩阵A第一种元素为a1,1，数组b下标从1开始），则矩阵A中第4行元素在数组b中下标i一定有（）。

A．7≤i≤10B．11≤i≤15C．9≤i≤14D．6≤i≤9

16．深度为5完全二叉树第5层上有4个结点，该树一共有（）个结点。

A．28B．30C．31D．19

17．已知一种图边数为m，则该图所有顶点度数之和为（）。

A．2mB．mC．2m+1D．m/2

18．已知一种图所有顶点度数之和为m，则m一定不也许是（）。

A．4B．8C．12D．9

19．如下说法不对的是（）。

A．连通图G一定存在生成树

B．连通图G生成树中一定包括G所有顶点

C．连通图G生成树中不一定包括G所有边

D．连通图G生成树可以是不连通

20．如下说法对的是（）。

A．连通图G生成树中可以包括回路

B．连通图G生成树可以是不连通

C．连通图G生成树一定是连通而不包括回路

D．连通图G生成树一定是唯一

21．散列查找原理是（）。

A．在待查记录核心字值与该记录存储位置之间建立拟定相应关系

B．按待查记录核心字有序顺序方式存储

C．按核心字值比较进行查找

D．基于二分查找办法

22．对n个元素进行冒泡排序，普通要进行n-1趟冒泡，在第j趟冒泡中共要进行（）次元素间比较。

A．jB．j-1C．n-jD．n-j-1

23．排序过程中，每一趟从无序子表中将一种待排序记录按其核心字大小放置到已经排好序子序列恰当位置，直到所有排好序为止，该排序算法是（）。

A．直接插入排序B．迅速排序

C．冒泡排序D．选取排序

24．在排序过程中，可以有效地减少一趟排序过程中元素间比较次数算法是（）。

A．冒泡B．选取C．折半插入D．直接插入

25．采用顺序查找法对长度为n线性表进行查找（不采用表尾设监视哨办法），最坏状况下要进行（）次元素间比较。

A．n+2B．nC．n-1D．n/2

26．如图若从顶点a出发按深度优先搜索法进行遍历，则也许得到顶点序列为（）。

A．aebcfd

B．abedcf

C．acebdf

D．acfbde

图1

27．如图若从顶点a出发按广度优先搜索法进行遍历，则也许得到顶点序列为（）。

A．acebdfgh

B．aebcghdf

C．aedfbcgh

D．abecdfgh

图2

28．一棵哈夫曼树有n个叶子结点（终端结点），该树总共有（）个结点。

A．2n-2B．2n-1C．2nD．2n+2

29．一棵哈夫曼树总共有23个结点，该树共有（）个叶结点（终端结点）

A．10B．11C．12D．13

30．数据（）构造与所使用计算机无关。

A．逻辑B．物理C．存储D．逻辑与存储

二、填空题

1．普通数据逻辑构造涉及____、____、____、____四种类型。

2．普通可以把一本具有不同章节书目录构造抽象成________构造。

3．设有一种单向链表，结点指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句________。

4．要在一种单向链表中p所指向结点之后插入一种s所指向新结点，若链表中结点指针域为next，可执行________和p->next=s;操作。

5．设有一种单向循环链表，头指针为head，链表中结点指针域为next，p指向尾结点直接前驱结点，若要删除尾结点，得到一种新单向循环链表，可执行操作________。

6．设有一种非空链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点值，栈结点指针域为next，则可执行x=hs->data；________。

7．在一种链队中，f和r分别为队头和队尾指针，队结点指针域为next，则插入一种s所指结点操作为________；r=s；

8．在一种不带头结点非空链队中，f和r分别为队头和队尾指针，队结点数据域为data，指针域为next，若要进行出队操作，并用变量x存储出队元素数据值，则有关操作为x=f->data；________。

9．循环队列队头指针为f，队尾指针为r，当_____时表白队列为空。

10．循环队列最大存储空间为MaxSize=8，采用少用一种元素空间以有效判断栈空或栈满，若队头指针front=4，则当队尾指针rear=________时，队列为空，当rear=________时，队列有6个元素。

11．“A”在存储时占________个字节。

12．稀疏矩阵存储时，采用一种由____、____、____3某些信息构成三元组唯一拟定矩阵中一种非零元素。

13．一棵二叉树没有单分支结点，有6个叶结点，则该树总共有________个结点。

14．一棵二叉树顺序编号为6结点（树中各结点编号与等深度完全二叉树中相应位置上结点编号相似），若它存在右孩子，则右孩子编号为________。

15．按照二叉树递归定义，对二叉树遍历惯用算法有____、____、____三种。

16．构造中数据元素存在多对多关系称为________构造。

17．把数据存储到计算机中,并详细体现数据之间逻辑构造称为________构造。

18．构造中数据元素存在一对多关系称为________构造。

19．如图3所示二叉树，其后序遍历序列为。

图3

20．如图4所示二叉树，其前序遍历序列为_________。

图4

21．二叉树为二叉排序充分必要条件是其任一结点值均不不大于其左孩子值、不大于其右孩子值。

这种说法是__________。

（回答对的或不对的）

22．在队列顺序存储构造中，当插入一种新队列元素时，指针值增1，当删除一种元素队列时，指针值增1。

23．依照搜索办法不同，图遍历有____、____两种办法

24．循环队列引入，目是为了克服。

三、综合题

1．

（1）已知某二叉树后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树

（2）若上述二叉树各个结点字符分别代表不同整数（其中没有相等），并正好使该树成为一棵二叉排序树，试给出a、b、c、d、e大小关系

（3）给出该树前序遍历序列

2．

（1）设head1和p1分别是不带头结点单向链表A头指针和尾指针，head2和p2分别是不带头结点单向链表B头指针和尾指针，若要把B链表接到A链表之后，得到一种以head1为头指针单向循环链表，写出其中两个核心赋值语句（不用完整程序，结点链域为next）。

（2）单向链表链域为next，设指针p指向单向链表中某个结点，指针s指向一种要插入链表新结点，现要把s所指结点插入p所指结点之后，某学生采用如下语句：

p->next=s；s->next=p->next;

这样做对的吗？

若对的则回答对的，若不对的则阐明应如何改写

3．

（1）设有一种整数序列{40，28，6，72，100，3，54}依次取出序列中数，构造一棵二叉排序树

（2）对上述二叉排序树，在等概率条件下，求成功查找平均查找长度

4．

（1）画出对长度为10有序表进行折半查找鉴定树（以序号1，2，……10表达树结点）

（2）对上述序列进行折半查找，求等概率条件下，成功查找平均查找长度

5．

（1）运用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应完全二叉树（不规定中间过程）

（2）写出对上述堆相应完全二叉树进行中序遍历得到序列

6．

（1）运用筛选法，把序列{37，77，62，97，11，27，52，47}建成堆（小根堆），画出相应完全二叉树

（2）写出对上述堆所相应二叉树进行前序遍历得到序列

四、程序填空题

1．如下函数在a[0]到a[n-1]中，用折半查找算法查找核心字等于k记录，查找成功返回该记录下标，失败时返回-1，完毕程序中空格

typedefstruct

{intkey;

……

}NODE;

intBinary_Search（NODEa[],intn，intk）

{

intlow,mid,high;

low=0;

high=n-1;

while（___

（1）_____）

{

mid=（low+high）/2;

if（a[mid].key==k）

return__

（2）______;

elseif（___（3）_____）

low=mid+1;

else__（4）______;

}

___（5）_____;

}

2．如下函数为直接选取排序算法，对a[1],a[2],…a[n]中记录进行直接选取排序，完毕程序中空格

typedefstruct

{intkey;

……

}NODE;

voidselsort（NODEa[],intn）

{

inti,j,k;

NODEtemp;

for（i=1;i<=___

（1）_____;i++）

{

k=i；

for（j=i+1;j<=___

（2）_____;j++）

if（a[j].key

if（i!

=k）

{

temp=a[i];

___（4）_____;

____（5）____;

}

}

}

3．如下函数为链队列入队操作，x为要入队结点数据域值，front、rear分别是链队列队头、队尾指针

structnode

{ElemTypedata;

structnode*next;

};

structnode*front，*rear;

voidInQueue（ElemTypex）

{

structnode*p;

p=（structnode*）___

（1）_____；

p->data=x；

p->next=NULL；

___

（2）_____；

rear=___（3）_____；

}

4．如下程序是中序遍历二叉树递归算法程序，完毕程序中空格某些（树构造中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

voidInorder（structBTreeNode*BT）

{if（BT!

=NULL）{

（1）;

（2）;

（3）;

}

}

答案

一、单项选取题

1．D2．A3．B4．D5．B6．C7．A8．D9．B10．A11．C12．D13．D14．D15．A16．D17．A18．D19．D20．C21．A22．C

23．A24．C25．B26．B27．D28．B29．C30．A

二、填空题

1．集合；线性；树形；图状

2．树形

3．p->next=head;

4．s->next=p->next；

5．p->next=head；

6．hs=hs->next;

7．r->next=s

8．f=f->next;

9．r==f

10．4；2

11．1；2

12．行号；列号；非零元

13．11

14．13

15．先序；中序；后序

16．图状

17．物理（存储）

18．树形

19．gdbeihfca

20．abdefcg

21．错误

22．尾头

23．深度优先广度优先

24．假上溢

三、综合应用题

1．

（1）

（2）d

（3）abdec

2．

（1）p1->next=head2；p2->next=head1；

（2）不对，s->next=p->next；p->next=s；

3．

（1）

（2）ASL=（1x1+2x2+3x3+4）/7=18/7

4．

（1）

（2）ASL=（1x1+2x2+3x4+4x3）/10=29/10

5．

（1）

初始树堆

（2）102，52，42，82，16，67，32，57

初始树堆

6．

（1）

（2）11，37，47，97，77，27，62，52

四、程序填空题

1．

（1）low<=high

（2）mid

（3）a[mid].key

（4）high=mid-1

（5）return-1;

2．

（1）n-1

（2）n

（3）k=j

（4）a[i]=a[k]

（5）a[k]=temp

3．

（1）malloc（sizeof（structnode））

（2）rear->next=p

（3）p

4．

（1）Inorder（BT->left）

（2）printf（“%c”,BT->data）

（3）Inorder（BT->right）