内容发布更新时间 : 2024/6/12 16:36:22星期一 下面是文章的全部内容请认真阅读。

数据结构（本）课程期末综合练习

（2008年12月6日）

一、单项选择题（每小题2分）

1．针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。

A．单链表 B．顺序表 C．单循环链表 D．双链表 2．链表所具备的特点是（ ）。

A．可以随机访问任一结点 B．占用连续的存储空间

C．可以通过下标对链表进行直接访问

D．插入删除元素的操作不需要移动元素结点

3．数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A．物理 B．存储 C．逻辑 D．逻辑与物理 4．线性结构中数据元素的位置之间存在（ ）的关系。 A．一对多 B．一对一

C．多对多 D．每一个元素都有一个直接前驱和一个直接后继 5．以下特征中，（ ）不是算法的特性。

A．有穷性 B．确定性 C．有0个或多个输出 D．可行性 6．算法的时间复杂度与（ ）有关。

A．所使用的计算机 B．与计算机的操作系统 C．与数据结构 D．与算法本身

7．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ ）。

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

8．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是（ ）。

A．p=q->next B．p->next=q C．p->next=q?next D．q->next=NULL 9．栈的插入删除操作在（ ）进行。

A．栈底 B．栈顶 C．任意位置 D．指定位置 10．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ ）。 A．r=f->next; B．r=r->next; C．f=r->next; D．f=f->next; 11．以下说法正确的是（ ）。

A．栈的特点是先进先出，队列的特点是先进后出 B．栈和队列的特点都是先进后出 C．栈的特点是先进后出，队列的特点是先进先出 D．栈和队列的特点都是先进先出 12．元素3，6，9按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。

A．9，3，6 B．9，6，3 C．6，3，9 D．3，9，6

13．元素2，4，6，8按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈

可以交替进行）。

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

C．4，2，8，6 D．8，6，2，4

1

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

A．33 B．32 C．85 D．41

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

序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,6在一维数组B中的下标是（ ）。

A．42 B．13 C．27 D．32

16．在C语言中，顺序存储长度为3的字符串，需要占用（ ）个字节。 A．3 B．4 C．6 D．12 17．串函数StrCmp（“d”，“D”）的值为（ ）。

A．0 B．1 C．-1 D．3

18．一棵有n个结点采用链式存储的二叉树中，共有（ ）个指针域为空。 A．n+1 B．n C．n-1 D．n-2

19．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A．2i B．2i-1 C．2i+2 D．2i+1 20．设一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。 A．n-1 B．n C．n+1 D．2n

21．设一棵有n个结点采用链式存储的二叉树，则该树共有（ ）个指针域为空。

A．2n B．n+1 C．2n+1 D．2n+2 22．在一个无向图中，所有顶点的度数之和等于边数的（ ）倍。 A．3 B．2.5 C．1.5 D．2

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

得到的一种顶点序列为（ ）。

A．abcedf B．aebcfd C．abcefd D．acfdeb

a

b e c

d f

图1

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

A．V1V2V3V6V7V4V5V8 B．V1V2V3V4V5V8V6V7 C．V1V2V3V4V5V6V7V8 D．V1V2V3V4V8V5V6V7

2

V1 V2 V3 V4 V5 V6 V7 V8 图1

25．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（ ）次比较后查找成功。

A．3 B．4 C．6 D．8

26．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120}中，用折半查找

法查找值80时，经（ ）次比较后查找成功。 A．2 B．3 C．4 D．5

27．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成

功的平均比较次数为（ ）。

A．31/10 B．29/10 C．26/10 D．29/9

28．排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进

行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（ ）。

A．冒泡 B．直接插入 C．选择排序 D．折半插入 29．一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个

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

A．29，31，37，47，70，85 B．31，29，37，47，70，85 C．31，29，37，70，47，85 D．31，29，37，85，47，70

30．排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）

的一端的方法，称为（ ）排序。

A．归并 B．插入 C．选择 D．快速

二、填空题（每小题2分） 1．把数据存储到计算机中,并具体体现数据之间的 称为物理（存储）结构。 2．结构中的数据元素存在多对多的关系称为_____ ___结构。 3．结构中的数据元素存在一对一的关系称为________结构。

4．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为________和 O(n)。

5．在双向链表中，每个结点有两个指针域，一个指向结点的直接后继，另一个指向________ _。

3