数据结构(本)期末综合练习(2013年12月)

数据结构期末综合练习

2013年12月

期末综合练习一

一、单项选择题

1. 数据结构在计算机内存中的表示是指 ( ) 。 A．数据元素之间的关系 B．数据的存储结构 C．数据元素的类型 D．数据的逻辑结构 2 .结构中的元素之间存在一对多的关系是（ ）。 A．集合 B．线性结构 C．树形结构 D．图状结构

3 .对不带头结点的单向链表,判断是否为空的条件是（ ）（设头指针为head）。 A．head==NULL B．head->next= =NULL

C．head->next= =head D．head =NULL

4.设有一个长度为20的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（ ）。 A．15 B．16 C.5 D．4

5.在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，可用的语句是（ ）。

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;

6．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行（ ）。

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; 7．一个栈的进栈序列是1，2，3，4，5，则栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。

A．12345 B．43512 C．45321 D．54321

8．元素a，b，c,d按顺序依次进栈，则该栈的可能输出序列是（ ）（进栈出栈可以交替进行）。

A．c,a,b，dB．d，b，c,a

C．a,c，b，dD．d，c，a,b

9．一个队列的入队序列是2，4，6，8，按该队列的输出序列使各元素依次入栈，该栈的可能输出序列是（ ）。

A．8，6，4，2 B．6，2，4，8

C．8，4，2，6D．8，2，4，6 10．从一个栈顶指针为top的链栈中取栈顶元素，用变量x保存该元素的值，则执行（ ）。 A．x=top->data; top=top?next; B．x=top->data;

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

11．在一个链队中，假设f和r分别为队头和队尾指针，已生成一个结点p,要为结点p赋

1

值x,并入队的运算为（ ）。

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;

12．设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维

数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ ）阶的对称矩阵。

(矩阵中的第1个元素是a1,1 ）

A．5 B．20 C．10 D．15

13．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素．a7,6在一维数组B中的下标是（ ）。 (矩阵中的第1个元素是a1,1 ）

A．34 B．14 C．26 D．27

14．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储

到一维数组B中（数组下标从1开始），则数组中第53号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ）

A．a8,5 , B．a10,8 C．a8,1, D．a7,6 15.以下程序段的结果是 c的值为（ ）。

char a[8]=“1236789”, int *p=a, int c=0; while(*p++)c++;

A．8, B．7 C．10 D．12 16.以下程序段的结果是 c的值为（ ）。

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

17．一棵有23个结点，采用链式存储的二叉树中，共有（ ）个指针域为空。 A．24B．25C．23D．45

18．一棵采用链式存储的二叉树中，共有n个指针域被有效使用（即指针域为非空）。该二叉

树有（ ）个结点。

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

19．在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号为

（ ）。

A．i/2B．2i-1 C．2i+1 D．i/2-1

20．在一棵二叉树中，若编号为i的结点是其双亲结点的右孩子，则双亲结点的顺序编号为

（ ）。

A．i/2.0B．i/2+1C．2i+1 D．i/2向下取整

21．设一棵哈夫曼树共有2n+1个叶结点，则该树有（ ）个叶结点。 A．n-1 B．n C．n+1 D．2n

22．设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有2n个

指针域为空。则该树有（ ）个叶结点。

2

A．2n B．2n+1 C．2n+2 D．n

23．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。

A．abecdf B．acfebd C．aebcfd D．aedbfc

a e c b d f 图1

24．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到

的一种顶点序列为（ ）。

A．acedfbB．aecfdbC．aecdfbD．acebfd

a e c b d f

图2

25．已知如图3所示的一个图，若从顶点B出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（ ）。

A.BADEHCFGB.BADEHCGFC.BADECHFG

3

A B C DE F GHD.BADEHCFG

图3

26．一组记录的关键字序列为（42，37，62，40，32，92），利用快速排序算法，以第一个关

键字为分割元素，算法经过一次划分后结果为（ ）。 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 27．一组记录的关键字序列为（46，38，56，40，79，84），利用快速排序，以第一个关键字

为分割元素，经过一次划分后结果为（ ）。

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 28．一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ ）。

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

29．在有序表{21，23，28，33，43，45，46，73，77，78，89，99，106}中，用折半查找值43时，经（ ）次比较后查找成功。 A．6 B．3 C．8 D．4

二、填空题

1．数据元素可以有一个或________组成。

2. 本书中介绍的树形结构和_______ 属非线性结构。

3. 结构中的数据元素存在一对一的关系称为线性结构。而数据元素存在 _______ 的关系 称为图状结构。

4．设有一个长度为18的顺序表，要在第4个元素之前插入2个元素（也就是插入元素作为 新表的第5个和第4个元素），则最少要移动元素的个数为（ ）。

5．设有一个长度为25的顺序表，要删除前3个元素,则最少要移动元素的个数为（ ）。 6．在双向链表中，要删除p所指的结点，可以先用语句（p->prior）->next=p->next；然 再用语句________。

7．在双向链表中，要删除p所指的结点，其中所用的一条语句（p->prior）->next=p->next； 的功能是：使P所指结点的直接前驱的右指针指向________。

8．在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s->next=p->next; 和_______的操作.

4