《数据结构》专科综合练习题,附答案

《数据结构》综合练习题

一. 单项选择题

1.如果某图的邻接矩阵是对角线上元素均为零的上三角矩阵，则此图是( )

A.有向完全图

B.连通图

C.无向图

D.有向无环图

2.对n 个关键字的序列进行快速排序，平均情况下的时间复杂度为( )

A.O(1)

B.O(logn)

C.O(n)

D.O(n log 2n)

3.对表长为n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长

度为( ) A.2 1-n B.2n C.2

1n D.n 4.以下排序方法中,最好情况下时间复杂度为O(n)的是（ ） A.直接插入排序

B.直接选择排序

C.堆排序

D.快速排序 5.稠密索引是在索引表中( )

A.为每个记录建立一个索引项

B.为每个页块建立一个索引项

C.为每组记录建立一个索引项

D.为每个字段建立一个索引项

6.设有两个串p 和q ，求 串q 在串p 中首次出现的位置的运算称为（ ）

A.连接

B.求子串

C.模式匹配

D.求串长

7.栈 S 和队列Q 的初始状态为空，元素1、2、3、4、5、6依次通过栈，一个元素出栈后即入队，若六个元素出队顺序为2、4、3、6、5、1，则栈的容量至少是（ ）

A.2

B.3

C.4

D.6

8.二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序（ ）

A.完全相同

B.都不相同

C.先序和中序相同，而与后序不同

D.中序和后序相同，与先序不同

9.下面关于线性表的叙述中，错误的是（ ）

A.线性表采用顺序存储，必须占用一片连续的存储单元

B.线性表采用链接存储，不必占用一片连续的存储单元

C.线性表采用顺序存储，便于进行插入和删除操作

D.线性表采用链接存储，便于进行插入和删除操作

10.一个向量第一个元素的存储地址是100，每个元素的长度是2，则第五个元素地址是（）

A.110

B.108

C.100

D.120

1. D

2. D

3. C

4. A

5. A

6. C

7. B

8. A

9. C 10. B

二. 判断改错题

1. 队列和栈都是运算受限的线性表。（）

2. 若连通网络上各边的权值均不相同，则其最小生成树是唯一的。（）

3. 哈夫曼树中不存在度为1的结点。（）

4. 无论是有向图还是无向图，其邻接矩阵表示都是唯一的。（）

5. 快速排序在任何情况下均可得到最快的排序效果。（）

1. √

2. √

3. √

4. √

5. ⅹ。

三. 填空题 (每小题1分, 共10分)

1. 在数据结构中，数据的逻辑结构分为集合，线性结构，_________和图状结构四类。

2. 一个具有5个顶点有向完全图的弧的条数为_________。

3.q所指向的结点，则需执行下述语句段：q->prior->next＝q->next; _______________。

4.设一棵二叉树中度为2的结点数为10，则该树的叶子数为_________。

5.一棵完全二叉树中结点i的左孩子的编号为_________。

6.无向图中，顶点Vi的度是邻接矩阵中_______________。

7.二维数组A[10][20]，起始地址从A[0][0]开始，采用按行为主序的存储方式，每个元素占1个存储单元，若A[0][0]的存储地址为200，则A[6][12]的地址为___________。

8.若一个图是个无向图，则它的邻接矩阵一定是一个___________。

9.要完全避免散列所产生的“堆积”现象，通常采用___________法。

10.二路归并排序算法的时间复杂度为_______。

1. 树状结构

2.20

3.q->next->prior= q->prior

4.11

5.2i

6. 第i行（或第i列）非零元素个数

7.332

8.对称矩阵

9.公共溢出区

10.O（nlog2n）

四. 名词解释 (每小题3分, 共15分)

1.栈：一种特殊的线性表,进行插入和删除的运算都只限定在表的一端进行。（2分）允许插入和删除的这一端称为栈顶，另一端称为栈底。（1分）

2.邻接表：图的一种链式存储结构，（1分）在邻接表中，对图中每个顶点建立一个单链表，n个顶点就要建n个链表，无向图中，单链表中的结点表示依赖于顶点vi的边，对于有向图，是以顶点vi为尾的弧。（2分）

3.二分查找法：每次将处于查找区间中间位置上（1分）的数据元素的键值和给定值K比较，若不等则缩小查找区间并在新的区间内重复，直到查找成功或查找区间长度为0为止。（2分）

4.二叉排序树：或者是一棵空树，或者是一棵满足下列条件的二叉树：（1分）

若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值。

若它的右子树不空，则右子树上所有结点的键值均大于它的根结点的键值。

它的左右子树也分别是二叉排序树。（2分）

5.冒泡排序：先将第一和第二个键值比较交换，然后比较第二和第三个键值交换，以此类推，直到第n个和n－1个记录比较交换，这称为一趟起泡。（2分）每趟将键值最大的记录换到最后。重复以上过程，每次移动都向最终目标前进，直至没有记录需要交换为止。（1分）

1. 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表在的元素，那么应采用哪种存储结构？为什么？

2. 如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。

3. 以关键字序列{265，301，751，129，937，863，742，694，76，438}为例，给出归并排序算法的各趟排序结束时，关键字序列的状态。

4. 什么是文件的存储结构，常见的有哪几种结构？

1. 顺序结构。（1分）由于顺序结构一旦确定起始位置，线性表中的任何一个元素都可以进行随机存取，既存取速度较高；（2分）并且由于线性表的总数基本稳定，且很少进行插入和删除，所以这一点恰好避开了顺序结构的缺陷。（2分）

2. 一棵哈夫曼树中只有度为2和0的结点（1分），没有度为1的结点（1分），有非空二叉树的性质1可知，n0=n2+1, （1分）即n2=n0-1,则总结点数n=n0+n2=2n0-1（2分）

3. 第一趟: [265,301],[129,751],[863,937],[694,742],[76,438] （2分）

第二趟: [129,265,301,751],[694,742,863,937],[76,438] （1分）

第三趟: [129,265,301, 694,742,751,863,937] ,[76,438] （1分）

第四趟: [76,129,265,301,438,694,742,751,863,937] （1分）

4. 文件在存储介质上的实际组织方式称为文件的存储结构（1分），常见的有顺序组织、索引组织、散列组织和链组织（每项1分）。