数据结构本期末综合练习6月.doc

数据结构（本）期末综合练习
1. 在数据结构和算法中，与所使用的计算机有关的是 （ B ）。
A．数据元数间的抽象关系 B．数据的存储结构 C．算法的时间复杂度 D．数据的逻辑结构
2. 一种逻辑结构在存储时（ C ）。
A．只要存储数据元素间的关系 B．只能采用一种存储结构
C．可采用不同的存储结构 D．只要存储数据元素的值
3 .对顺序表,以下叙述中正确的是 ( A )。
A．用一组地址连续的存储单元依次存放线性表的数据元素
B．各个数据元素的首地址是连续的
C．数据元素不能随机访问 D．插入操作不需要移动元素
4 .对链表, 以下叙述中正确的是（ A ）。
A．不能随机访问任一结点 B．结点占用的存储空间是连续的
C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问
5．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为
（ C ）。
A．9 B．10 C．15 D．16
6．线性表在存储后,如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用（ A ）存储方式是不可行的。
A．单链表 B．双链表 C．单循环链表 D．顺序表
7. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( A )。
A.p->next=p->next->next; B.p=p->next; C.p=p->next->next; D.p->next=p ;
8．栈和队列的共同特点是（ C ）。
A都是先进后出 B元素都可以随机进出 C只容许在端点处插入和删除元素 D都是先进先出
9．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列该队列
的可能输出序列是（ A ）。（进栈出栈可以交替进行）。
A．7，5，3，1 B．7，3，1,5 C．7，5，1，3 D．5,1，3，7
10．元素2，4，6，8按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能输出序列是（ D ）（进栈出栈可以交替进行）。
A．8，6，2，4 B．8，4，2，6 C．6，2，4，8 D．8，6，4，2
11 ．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（ C ）。
A．p=top->next; top=topànext; B．p->next=top;
C．p->next=top;top=p; D．top=p;
12．在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一
个结点并把结点的值保存在变量x中的运算为（ C ）。
A．x=ràdata；r=rànext; B．r=rànext; x=ràdata
C．x=fàdata；f=fànext; D．f=fànext; x=fàdata

13．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（ D ）。(矩阵中的第1个元素是a1,1 ）
A．a7,6 B．a10,8 C．a9,2 D．a8,5
14．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第38号元素对应于矩阵中的元素是（ C ）。(矩阵中的第1个元素是a1,1 ）
A．a10,8 B．a7,6 C．a9,2 D．a8,5
15．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,6 在一维数组B中的下标是（ C ）。(矩阵中的第1个元素是a1,1 ）
A．45, B．18 C．51 D．53
16．在C语言中，分别存储 “S”和‘s’，各需要占用（ D ）字节。
A．一个和两个 B．两个 C．一个 D．两个和一个
17．串函数StrCmp（“ABCd”，“ABCD”）的值为（ C ）。
A．0 B．-1 C．1 D．3
18．一棵有n个结点，采用链式存储的二叉树中，共有（ C ）个指针域被有效使用（即指针域为非空）。
A．n+1 B．n C．n-1 D．n-2
19．一棵采用链式存储的二叉树中有n个指针域为空,该二叉树共有（ C ）个结点。
A．n+1 B．n C．n-1 D．n-2
20．在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为（ B ）。
A．i/2.0 B．i/2向下取整 C．2i+1 D．i+2
21．设一棵哈夫曼树共有n个非叶结点，则该树有（ D ）个结点。
A．2n B．2n+2 C．2n-1 D．2n+1
22．设一棵哈夫曼树共有2n+1个结点，则该树有（ A ）个非叶结点。
A．n B．n+1 C．n-1 D．2n
23．一棵 结点数31从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ A ）。
A．abedfc B．acfebd C．aebcfd D．aedfbc
b
d
f
e
c
a

图1

26．如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ）。
A．abedfc B．acfebd C．aebcdf D．aebcfd
b
d
f
e
c
a

图2
27．一组记录的关键字序列为（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ B ）。
A．20,30,40，38，46，79，56，84,90,100
B．40，20,30,38，46，56，79，84,90,110
C．30,20,40，38，46，84，56，79,90,100
D．20,30 38，40，46，56，79，84,90,100
28．一组记录的关键字序列为（56，30,89，66，48，50，94,87,100），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ B ）。
A．30，50,48，56，66，89，94,100,87 B． 50，30,48，56，66，89，94,87,100
C．48，30,50，56，66，89，94,87,100 D．50，30,48，66，56，89，94,87,100
29．一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序（堆顶元素是最大元素）的方法建立的初始堆为（ A ）。
A．95，80，75，63，53，45，38，20
B．95，63，75，80，53，45，38，20
c. 95, 80, 45, 63, 53, 75, 38, 20
D．95, 80, 75, 20, 53, 45, 38, 63
30．线性表以（ C ）方式存储，能进行折半查找。
A．关键字有序的链接 B．顺序 C．关键字有序的顺序 D．数组

二、填空题
1．数据元素之间的抽象关系称为___逻辑___结构 。
2. 数据的逻辑结构在计算机中的表示称为__物理__结构。
3．要求在n个数据元素中找值最大的元素，其基本操作为__元素间的比较__。算法的时间复杂度为_ O(n)__。
4. 求两个n阶矩阵的乘积，算法的基本操作为__乘法__，时间复杂度为__ O(n3)__。 5．设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值
为 8,9,10,11,…,25，某人想要删除第8个元素，他的做法是从第25号元素开始,直
到第9号元素依次向前移动1个位置,其结果新表中第9号元素的值为（ 25 ）。
6． 设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为8,9,10,11,…25,
某人想要在第8个元素前插入1个元素7（也就是插入元素作为新表的第8个元素），他
的做法是从第8号元素开始,直到第25号元素依次向后移动1个位置,然后把7存放在
8号位置，其结果是新表中第25号元素的值为（ 8 ）。
7．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，可以先用语句q->next=p->next; （p->next）->prior=q；然后再用语句q->prior=p;和语句_ p->nextq；_。
8．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，其中所用的一条语句（p->next）->prior=q；的功能是使P所指结点的_直接前驱的左指针_指向q 。
9．在一个单向链表中，要删除p所指结点的直接后继结点。则可以用操作__ p->next=p->next->next;_。（用一条语句）
10．设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有
p->next= =NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过
操作head=head->next; __ p->next= head;_。
11．向一个栈顶指针为top的链栈中插入一个p所指结点时，可执行_ p->next=top; top=p；_操作。 ( 填两条语句, 结点的指针域为next)
12．从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行__ d=top->data;top=top->next;_。(结点的指针域为next,数据域为data)
13．在一个带头结点的链队中，设front和rear分别为队头和队尾指针，则删除一个结点的操作为 p=front->next;_ _ front->next __=p->next;(结点的指针域为next, p为辅助用指针)
14.循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少用一个元素的模式),判断循环链队列为满的条件为__ front= =(rear+1)% MaxSize __ 。
15．设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，最后一个元素的下标为27，则n=__7__。(矩阵中的第1个元素是a1,1 ）
16．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组表共有8个元素,则矩阵A共有___34__个零元素。
17. 一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有_5__个叶结点。
18.一棵有8个权重值构造的哈夫曼数，共有 15 个结点。
19．一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有____15___个结点
20．一棵有18个结点的二叉树，其2度结点数的个数为8则该树共有____1___个1度结点
21．如图3所示的二叉树，其中序遍历序列为____512389746_____。
3c
7gd
6f
5e
4dc
2b
1a
8hd
9

图3
22．如图4所示的二叉树，其先序遍历序列为____215347896_____。
3c
7gd
6f
5e
4dc
2b
1a
8hd
9

图4
23．二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是__不正确__的。(回答正确或不正确)
24．在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为__主关键字__。

三、综合题
1．
(1) 以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树。
(2) 给出相应权重值叶结点的哈夫曼编码。
(3) 一棵哈夫曼树有2n-1个结点，它是共有多少个权重值构造而成的？简述理由？
(1)109
8
7
9
129
3
5
4
3933
17155
2218

图7
(2)
3 0000
4 0001
5 001
10 01
8 10
9 11
（3）n个，因为非叶结点数比叶结点数少一个,而权值个数=叶结点数
2．（1）对给定权值3，1 ，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层)
(2) 求树的带权路径长度。
（3）链接存储上述哈夫曼树，结点中共有多少个指针域为空,说明理由.
(1)65
43
54
23418
1451
97
896
43
453
121
3

图8
（2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58
(3) 共11个结点,22个指针域,除根结点外,每个结点对应一个指针域.,共10个指针域非空,故
有 22-10=12个空指针域,
3．（1）简述拓扑排序的步骤。
（2）说明有向图的拓扑序列不一定是唯一的原因。
（3）如何利用拓扑排序算法判定图是否存在回路。
（4）设有向图G如下，写出首先删除顶点1的3种拓扑序列。
1
2
3
4
5434
65

图5
(1) 循环执行以下两步
选择一个度为0的顶点并输出
从网中删除此结点及所有出边
（2） 因为选择一个度为0的顶点时不一定是唯一的
（3） 由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱
(4) 152364 152634 156234
4. (1) 如下的一棵树,给出先序遍历序列
(2) 把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树
提示：设图中的树是二叉排序树，找出中序遍历序列与 1，2，…9的对应关系
(3) 请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。
A1
A2
A43
A7
A5
A9
A8
A3
A6
图6
(1) A1 A2 A4 A7 A8 A5 A9 A3 A6
(2)
(3)
7
4
2
1
5
6
3
8
9
3.5
图9

5．设有序表为（21，22，23，24，25，26，27，28，29，30，31,32），元素的下标从
0开始。
（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到。
（2）画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示）
（3）设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。
（4）求在等概率条件下，成功查找的平均比较次数？
24314
2717
322
2818
2515
22112
31
2101000000
3020
2616
232213
2919
（1) 5
(2)

图10
(3) 3
(4) ASL=(1+2*2+3*4+5*4)/12=37/12
6．设查找表为(5,6,7,8,9,10,11,12,13,14)
（1）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)
(2) 给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树
是否是二叉排序树(设树中没有相同结点)？
(3) 为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？
9
7
10
14
11
8
5
12
13
6
(1)

(2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树
非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子
树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值;
左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。
(3) 3次
四、程序填空题
1．以下程序是快速排序的算法设待序的记录序列存放在a[start],…a[end]中，按记录的关键字进行快速排序， 先进行一次划分，再分别进行递归调用
void quicksort ( NODE a[ ], int start ,int end )
{ int i，j;
NODE mid ;
if (start>=end )
return;
i=start;
j=end;
mid=a[i];
while (imid.key)
j- -;
if(i
__ j--;__}
}
a[i]=mid;
quicksort (a,stat, i-1);
quicksort __(a, i+1,end);__}
2．以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完成程序中的空格
typedef struct
{ int key;
……}
NODE;
void selsort(NODE a[],int n)
{int i,j,k;
NODE temp;
for(i=1;i<= ___n-1____;i++)
{k=i;
for(j=i+1;j<= ___n____;j++)
if(a[j].key队操作，x为要入队的结点的数据域的值，front、rear分别是 链
队列的队头、队尾指针
struct node
{ ElemType data;
struct node *next;};
struct node *front，*rear;
void InQueue(ElemType x)
{ struct node *p;
p= (struct node*) ___(1) malloc(sizeof (struct node)_____;
p->data=x;
p->next=NULL;
___(2) rear->next=p _____;
rear= ___(3)p_____; }
4 .设有一个头指针为head的不带头结点单向链表, 且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同）, 写出相关语句
(1).使该单向链表成为单向循环链表
(2) 删去a结点
q=p; x=p->data;
while （q->next!=NULL）q=q->next;
(1) __(1) q->next=head;___
q=p; p=p->next;
while(p->data!=x)
{ q=p;
__(2) p=p->next;___}
__(3) q->next=p->next;___
期末综合练习二
一、单项选择题
1. 数据结构在计算机内存中的表示是指 ( B ) 。
A．数据元素之间的关系 B．数据的存储结构 C．数据元素的类型 D．数据的逻辑结构
2 .结构中的元素之间存在一对多的关系是（ C ）。
A．集合 B．线性结构 C．树形结构 D．图状结构
3 . 结构中的元素之间存在多对多的关系是（ D ）。
A．集合 B．线性结构 C．树形结构 D．图状结构
4.对不带头结点的单向链表,判断是否为空的条件是（ A ）（设头指针为head）。
A．head==NULL B．head->next= =NULL C．head->next= =head D．head =NULL
5 . 设有一个长度为20的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（ B ）。
A．15 B．16 C. 5 D．4
6. 在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，可用的语句是（ D ）。
A．p=q->next; p=p->next; B．p->next=q ; p=p->next;
C．p->next=q->next;q=p; D．p=p->next; q->next=p;
7．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行（ D ）。
A．rearànext= s; sànext=rearànext B．rearànext=sànext;
C．rear=sànext D．sànext=rearànext ; rearànext=s;
8．一个栈的进栈序列是1，2，3，4，5，则栈的不可能输出序列是（ B ）（进栈出栈可以交替进行）。
A．12345 B．43512 C．45321 D．54321
9．元素a，b，c,d按顺序依次进栈，则该栈的可能输出序列是（ C ）（进栈出栈可以交替进行）。
A．c,a,b，d B．d，b，c,a C．a,c，b，d D．d，c，a,b
10．一个队列的入队序列是2，4，6，8，按该队列的输出序列使各元素依次入栈，该栈的可能输出序列是 （ A ）。
A．8，6，4，2 B．6，2，4，8 C．8，4，2，6 D．8，2，4，6
11．从一个栈顶指针为top的链栈中取栈顶元素，用变量x保存该元素的值，则执行（ B ）。
A．x=top->data; top=topànext; B．x=top->data;
C．top=top->next; x=top->data; D．top=top->next; x=data;
12．在一个链队中，假设f和r分别为队头和队尾指针，已生成一个结点p,要为结点p赋
值x,并入队的运算为（ B ）。
A . p->data=x; p->next=NULL; f->next=p; f=p;
B． p->data=x; p->next=NULL ;r->next=p;r=p;
C． p->data=x; p->next=r;r=s;
D． p->data=x; p->next=f;f=s;
13．设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ C ）阶的对称矩阵。(矩阵中的第1个元素是a1,1 ）
A．5 B．20 C．10 D．15
14．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素．a7,6在一维数组B中的下标是（ D ）。
(矩阵中的第1个元素是a1,1 ）
A．34 B．14 C．26 D．27
15．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第53号元素对应于矩阵中的元素是（ B ）。(矩阵中的第1个元素是a1,1 ）
A．a8,5 , B．a10,8 C．a8,1, D．a7,6
16.以下程序段的结果是 c的值为（ B ）。
char a[8]= “1236789”, int *p=a, int c=0;
while(*p++)c++;
A．8, B．7 C．10 D．12
17 .以下程序段的结果是 c的值为（ A ）。
char * a[5]={“12378”, “1237”, “1236789”, “1237”, “123708”};
int i,c=0;
for(i=0;i<5:i++)
if(StrCmp(a[i], “1237”)==0)c++;
A．2, B．5 C．0 D．1237
18．一棵有23个结点，采用链式存储的二叉树中，共有（ A ）个指针域为空。
A．24 B．25 C．23 D．45
19．一棵采用链式存储的二叉树中，共有n个指针域被有效使用（即指针域为非空）。该二叉树有（ A ）个结点。
A．n+1 B．n C．n1 D．n-2
20在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号为（A）。
A．i/2 B．2i-1 C．2i+1 D．i/2 -1
21在一棵二叉树中，若编号为i的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（D）。
A．i/2.0 B．i/2+1 C．2i+1 D．i/2向下取整
22．设一棵哈夫曼树共有2n+1个叶结点，则该树有（ C ）个叶结点。
A．n-1 B．n C．n+1 D．2n
23．设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有2n个指针域为空。则该树有（ D ）个叶结点。
A．2n B．2n+1 C．2n+2 D．n
24．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ D ）。
A．abecdf B．acfebd C．aebcfd D．aedbfc
b
d
f
e
c
a

图1
25．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ）。
A．acedfb B．aecfdb C．aecdfb D．acebfd
b
d
f
e
c
a

图2
26．已知如图3所示的一个图，若从顶点B出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（ C ）。
A.BADEHCFG B.BADEHCGF C.BADECHFG D.BADEHCFG F
GV7
A
B
C
HV8
DV4
E

图3
27．一组记录的关键字序列为（42，37，62，40，32，92），利用快速排序算法，以第一个关键字为分割元素，算法经过一次划分后结果为（ A ）。
A．32，37，40，42，62，92 B．37，32,40，42，62，92
C．32，40，37，42，62，92 D．32，37，42，40，62，92
28．一组记录的关键字序列为（46，38，56，40，79，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ B ）。
A．40，38，46，79，56，84 B．40，38，46，56，79，84
C．40，38，46，84，56，79 D．38，40，46，56，79，84
29．一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ A ）。
A．39，46，41,57,80，47 B．39，47，46，80，41，57
C．41，39，46，47，57，80 D．39，80，46，47，41，57
30．在有序表{21，23，28，33，43，45，46，73，77，78，89，99，106