《数据结构》综合练习题
一. 单项选择题
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分)。