昆明理工大学数据结构总复习题

一、单选题

? 数据结构研究( )。

A.数据的逻辑结构、存储结构及操作的实现 B. 数据的物理结构

C. 数据的逻辑结构与存储结构 D. 数据的逻辑结构。

数据的存储结构包括顺序;链式;散列和( )4 种基本类型。

A. Vector B. Index C. Sets D. Array

若某线性表最常用的操作是取第 i 个元素，则采用( )存储方式最节省运算时间。

A．双链表 B． 单链表 C．顺序表 D． 单循环链表

一个单链表中，已知*q 结点是*p 结点的前趋结点，若在*q 和*p 之间插入*s 结点， 则必须执行( )操作。

A．q->next=p ->next; p ->next=s; B． p ->next=s; s->next=q

C．p ->next=s->next; s->next=p D．q->next=s; s->next= p ;

在一个具有n个结点的有序单链表中，若插入一个新结点，单链表仍然有序，则算法的 时间复杂度为（ ）。 ? ? ? ?

A．O(n) B．O(1) C．O(n2) D．O(nlog2n)

? 队列与一般线性表的区别在于( )。

A. 数据元素的类型不同 B. 插入或删除操作的位置受限制

C. 数据元素的个数不同 D. 逻辑结构不同

? 设进栈的顺序为 a b c d，则不可能得到的出栈序列是( )。

A.a b c d B.d c b a C. d a b c D. a c d b

? 用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

? 循环队列的队满条件为（在牺牲一个存储空间的情况下） ( )

A. rear % maxsize ==(front+1) % maxsize; B. (rear+1)% maxsize == front+1

C. (rear+1)% maxsize == front D. rear == front

? 下面关于串的叙述中，哪一个是不正确的( )

A.串是字符的有限序列 B. 模式匹配是串的一种重要运算

C. 空串是由空格构成的串 D.串既可以采用顺序存储，也可以采用链式存储

? 稀疏矩阵一般的压缩存储方法有( )两种。

A．三元组表和十字链表 B．三元组表和哈希表

C．二维数组和三维数组 D．哈希表和十字链表

? 中序遍历一颗二叉排序树所得到的结点访问序列是结点值的( )序列。

A.递增或递减 B.递增 C. 递减 D. 无序

? 在树中，若结点A 有四个兄弟，而且B 是A 的双亲，则B 的度为( )。

A.3 B.4 C.5 D.6

? 若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点个数是( )

A．9 B．11 C．12 D、不确定

? n 个顶点的连通图至少有( )条边

A. 0 B. n C. n+1 D. n-1

? 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( ) 。

A ．上三角矩阵 B ．稀疏矩阵 C．对角矩阵 D. 对称矩阵 ? AOV网是一种( )。

A．有向图 B．无向图 C．有向无环图 D．无向无环图

?

? 采用折半查找方法进行查找，数据文件应为( )。 A．有序表和链式存储结构 B ．有序表和顺序存储结构 C． 随机表和顺序存储结构 D ．随机表和链式存储结构 在顺序表{2、5、7、10、14、15、18}中，用二分法查找关键码 12需做( )次关键码

比较。

A．2 B．3 C．1 D．5

? 下面的排序算法中，时间复杂度不是O(n2）的是( )。

A.直接插入排序 B.冒泡排序 C.二路归并排序 D.直接选择排序

=============================================

? 算法指的是（ ）

A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列

? 下列数据结构中，（ ）是线性结构。

A．树 B ．队列 C．图 D ．A 和B

? 下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++）

{ t=1；

for(j=1；j<=i；j++) t=t*j；

s=s+t；

}

A. O(n) B. O(n2) C. O(n3) D.O(n4)

? 用链表表示线性表的优点是 ( )。

A. 便于随机存取 B. 花费的存储空间比顺序表少

C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同

? 从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，需

平均比较( )个结点。

A．n B．n/2 C．（n-1 ）/2 D．(n+1)/2

? 在一个单链表中，已知 q 所指节点是 p 所指节点的前驱节点，若在 q 和 p 之间插

入 s 节点，则执行( )。

A. s->next=p->next;p->next=s; B. p->next=s->next;s->next=p;

C. q->next=s;s->next=p; D. p->next=s;s->next=q;

? 栈的插入和删除操作在（ ）进行。

?

? A 栈顶 B 栈底 C 任意位置 D 指定位置 设栈的输入序列是 1 2 3 4,则( )是不可能的出栈序列。 A.1 2 4 3 B. 2 1 3 4 C. 1 4 3 2 D. 4 3 1 2 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则

执行出队操作后其头指针front值为（ ）

A．front=front+1 B．front=(front+1)%(m-1)

C．front=(front-1)%m D．front=(front+1)%m

? 如下陈述中正确的是（ ）

A．串是一种特殊的线性表 B．串的长度必须大于零

C．串中元素只能是字母 D．空串就是空白串

? 树型结构中元素间存在( )的关系。

A. 一对一 B. 多对多 C. 一对多 D. 随机

? 一棵深度为 5 的满二叉树中,结点的总数为 ( )。

A.31 B.32 C.33 D.16

? 一棵二叉树有 67 个结点，这些结点的度或者是 0，或者是 2。这棵二叉树中度为 2 的

结点有( )个。

A. 33 B.34 C.32 D.30

? 下面关于图的存储的叙述中正确的是（ ）

A.邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关；

B.邻接矩阵占用的存储空间只与图中边数有关，而与结点个数无关；

C.邻接表占用的存储空间只与图中结点个数有关，而与边数无关；

D.邻接表占用的存储空间只与图中边数有关，而与结点个数无关。

?

?

?

?

? n 个顶点的连通图至少有( )条边。 A．n-1 B．n C．n+1 D ．0 AOV网是一种（ ）。 A．有向图 B．无向图 C．无向无环图 D．有向无环图 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( ) 。 A ．上三角矩阵 B ．稀疏矩阵 C．对角矩阵 D. 对称矩阵 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的有序序列 A. 前序 B. 中序 C.后序 D.按层序 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}, 如果采用二分查找法, 查

值为 82 的结点时，（ ）次比较后查找成功。

A. 1 B. 2 C. 4 D. 8

假定有 K 个关键字互为同义词,若用线性探测法把这 K 个关键字存入散列表中,至少要进行( )次探测。

A.K-1 次 B. K(K-1)/2 次 C.K+1 次 D.K(K+1)/2 次 ?

=====================================================

? 对一个算法的评价，不包括如下（ ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度

? 对线性表，在下列哪种情况下应当采用链表表示？( )

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变

? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行

( )。

A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p;

C. p->next=HL; p=HL; D. HL=p; p->next=HL;

? 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素

C.都是先进先出

? B.都是先进后出 D.没有共同点 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )

A. 2 3 1

C. 3 1 2 B. 3 2 1 D. 1 2 3

? 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，

则执行出队操作后其头指针front值为（ ）

A．front=front+1 B．front=(front+1)%(m-1)

C．front=(front-1)%m D．front=(front+1)%m

? 用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

? 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置

在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．696

? 树最适合用来表示( )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

? 二叉树的第k层的结点数最多为( ).

A．2k-1 B.2K+1 C.2K-1 D. 2k+1

? 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二

分查找，则查找A［3］的比较序列的下标依次为( )

A. 1，2，3

C. 9，5，3 B. 9，5，2，3 D. 9，4，2，3

? 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为

A. O（1） B. O（n） C. O（1og2n） D. O（n2）

? 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）

=K %9作为散列函数，则散列地址为1的元素有（ ）个，

A．1 B．2 C．3 D．4

? 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5 B.6 C.7 D.8

? AOV网是一种（ ）。

A．有向图 B．无向图 C．无向无环图 D．有向无环图

? 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。

A. 堆排序 B. 冒泡排序 C. 希尔排序 D. 快速排序

? 快速排序在最坏情况下的时间复杂度为（ ）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)

? 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n) B. O(1) C. O(log2n) D. O(n2)

? 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行

排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84

15，20，21，25，27，35，47，68，84

则所采用的排序方法是（ ）

A．选择排序 B．希尔排序 C．归并排序 D．快速排序

? 设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。

(A) n(n-1)/2

(B) n(n-1) (C) n2 (D) n2-1