数据结构复习题.docx
- 文档编号:16384606
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:16
- 大小:46.16KB
数据结构复习题.docx
《数据结构复习题.docx》由会员分享,可在线阅读,更多相关《数据结构复习题.docx(16页珍藏版)》请在冰点文库上搜索。
数据结构复习题
一、选择题
1.栈和队列的共同特点是()。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2.用链接方式存储的队列,在进行插入运算时().
A.仅修改头指针 B.头、尾指针都要修改
C.仅修改尾指针D.头、尾指针可能都要修改
3.以下数据结构中哪一个是非线性结构?
()
A.队列 B.栈C.线性表 D.二叉树
4.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在()位置,脚注(10)表示用10进制表示。
A.688B.678C.692D.696
5.树最适合用来表示()。
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
6.二叉树的第k层的结点数最多为().
A.2k-1B.2K+1C.2K-1 D.2k-1
7.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为()
A.1,2,3B.9,5,2,3
C.9,5,3D.9,4,2,3
8.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为()
A.O
(1) B.O(n) C.O(1og2n)D.O(n2)
9.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有()个,
A.1B.2C.3D.4
10.设有6个结点的无向图,该图至少应有()条边才能确保是一个连通图。
A.5B.6C.7D.8
11.一个链队列中,f,r分别为队首、队尾指针,则插入s所指结点的操作为()。
A)f->next=c;f=s;B)r->next=s;r=s;
C)s->next=r;r=s;D)s->next=f;f=s;
12.下列说法正确的是()。
A)二叉树中每个结点的度都为2B)二叉树的度为2
C)一棵二叉树的度可小于2D)二叉树中至少有一个结点的度2
13.一棵非空二叉树先序遍历与后序遍历序列正好相反,则该二叉树()。
A)所有的结点均无左孩子B)所有的结点均无右孩子
C)只有一个叶子结点D)是任意一棵二叉树
14.二叉排序树中,键值最小的结点一定()。
A)左指针为空B)右指针为空
C)左右指针均为空D)左右指针均非空
15.n个顶点的强连通图至少有()条边。
A)n-1B)nC)n+1D)n(n-1)
16.在一个有向图中,顶点入度之和与顶点出度之和的比值()。
A)1/2B)1C)2D)4
17.高度为h的二叉树只有度为0和2的结点,则此二叉树至少为( )结点。
A)2*hB)2*h1C)2*h+1D)h+1
18.设某完全无向图中有n个顶点,则该完全无向图中有()条边。
(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1
19.设某棵二叉树中有2000个结点,则该二叉树的最小高度为()。
(A)9(B)10(C)11(D)12
20.设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。
(A)n-1(B)n(C)n+1(D)2n-1
21.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。
(A)2,3,5,8,6(B)3,2,5,8,6
(C)3,2,5,6,8(D)2,3,6,5,8
22.按照二叉树的定义,具有3个结点的二叉树有()种形态。
A)3B)4C)5D)6
23.下列排序算法中,可能会出现在最后一趟开始之前,所有元素都不在其最终
位置上是().
A)堆排序B)冒泡排序C)快速排序D)插入排序
24.一组记录的排序码为46,79,56,38,40,84。
用堆排序方法建立的初始堆为()。
A)79,46,56,38,40,80B)84,79,56,38,40,46
C)84,79,56,46,40,38D)84,56,79,40,46,38
25.将递归算法转换成对应的非递归算法时,通常需要使用()。
A)栈B)队列C)链表D)树
26.有10个结点的连通无向图,其边数至少有()。
A)8条B)9条C)10条D)11条
27.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。
A)edcbaB)decbaC)dceabD)abcde
28.高度为h的完全二叉树中所包含的结点数至少为()。
A)2*h个B)2h1个C)2*h+1个D)h+1个
29.设一维数组中有n个数组元素,则读取第i个数组元素的平均时间复杂度为()。
(A)O(n)(B)O(nlog2n)(C)O
(1)(D)O(n2)
30.设一棵二叉树的深度为k,则该二叉树中最多有()个结点。
(A)2k-1(B)2k(C)2k-1(D)2k-1
31.设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为()。
(A)n(B)e(C)2n(D)2e
32.在二叉排序树中插入一个结点的时间复杂度为()。
(A)O
(1)(B)O(n)(C)O(log2n)(D)O(n2)
33.设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有()条有向边。
(A)n(B)n-1(C)m(D)m-1
34.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。
(A)3(B)4(C)5(D)8
35.设用链表作为栈的存储结构则退栈操作()。
(A)必须判别栈是否为满(B)必须判别栈是否为空
(C)判别栈元素的类型(D)对栈不作任何判别
36.设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为()。
(A)O
(1)(B)O(log2n)(C)(D)O(n2)
37.设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为()。
(A)n,e(B)e,n(C)2n,e(D)n,2e
38.设某强连通图中有n个顶点,则该强连通图中至少有()条边。
(A)n(n-1)(B)n+1(C)n(D)n(n+1)
39.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列()方法可以达到此目的。
(A)快速排序(B)堆排序(C)归并排序(D)插入排序
40.下列四种排序中()的空间复杂度最大。
(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序
二、填空题
1.设有n个无序的记录关键字,则直接插入排序的时间复杂度为________,快速排序的平均时间复杂度为_________。
2.设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为_________________________________________________________(设结点中的两个指针域分别为llink和rlink)。
3.根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为____________。
4.深度为k的完全二叉树中最少有____________个结点。
5.设初始记录关键字序列为(K1,K2,…,Kn),则用筛选法思想建堆必须从第______个元素开始进行筛选。
6.设哈夫曼树中共有99个结点,则该树中有_________个叶子结点;若采用二叉链表作为存储结构,则该树中有_____个空指针域。
7.设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储________个队列元素;当前实际存储________________个队列元素(设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。
8.设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中_______个数据元素;删除第i个位置上的数据元素需要移动表中_______个元素。
9.设一组初始记录关键字序列为(20,18,22,16,30,19),则以20为中轴的一趟快速排序结果为______________________________。
10.设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序列建成的初始堆为____________。
11.头结点为H的单循环链表为空的条件是__。
12.线性表作为栈时,被称为__。
13.在堆排序、快速排序和归并排序中,若只从最坏情况下排序最快并且要节省内存空间考虑,应选取方法。
14.一棵二叉树有11个度数为0的结点,则该二叉树的二度结点个数为__。
15.平衡二叉树是每个结点的左右子树深度之差的绝对值不超过1的__。
16.关键码序列为21,12,20,35,40,51,87,33,42,90,2,18,34。
步长因子序列为3,1时,一趟希尔排序结果序列为__。
17.顺序存储的线性表相对与链接存储的线性表,其优点是__。
18.就排序的稳定性而言,简单选择排序方法是__。
19.设某无向图G中有n个顶点,用邻接矩阵A作为该图的存储结构,则顶点i和顶点j互为邻接点的条件是________。
20.设无向图对应的邻接矩阵为A,则A中第i上非0元素的个数_________第i列上非0元素的个数(填等于,大于或小于)。
21.for(i=1,t=1,s=0;i<=n;i++){t=t*i;s=s+t;}的时间复杂度为_________。
22.设指针变量p指向单链表中结点A,指针变量s指向被插入的新结点X,则进行插入操作的语句序列为__________________________(设结点的指针域为next)。
23.设有向图G的二元组形式表示为G=(D,R),D={1,2,3,4,5},R={r},r={<1,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},则给出该图的一种拓扑排序序列__________。
24.设无向图G中有n个顶点,则该无向图中每个顶点的度数最多是_________。
25.设二叉树中度数为0的结点数为50,度数为1的结点数为30,则该二叉树中总共有_______个结点数。
26.设F和R分别表示顺序循环队列的头指针和尾指针,则判断该循环队列为空的条件为_____________________。
27.设二叉树中结点的两个指针域分别为lchild和rchild,则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。
28.简单选择排序和直接插入排序算法的平均时间复杂度为___________。
29.快速排序算法的空间复杂度平均情况下为__________,最坏的情况下为__________。
30.散列表中解决冲突的两种方法是_____________和_____________。
31.设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为_________=p;s->right=p->right;__________=s;p->right->left=s;(设结点中的两个指针域分别为left和right)。
32.设完全有向图中有n个顶点,则该完全有向图中共有________条有向条;设完全无向图中有n个顶点,则该完全无向图中共有________条无向边。
33.设关键字序列为(Kl,K2,…,Kn),则用筛选法建初始堆必须从第______个元素开始进行筛选。
34.解决散列表冲突的两种方法是________________和__________________。
35.设一棵三叉树中有50个度数为0的结点,21个度数为2的结点,则该三叉树中度数为3的结点数有______个。
36.高度为h的完全二叉树中最少有________个结点,最多有________个结点。
37.设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是__________________________________。
38.设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟简单选择排序结束后的结果的是__________________________________。
39.设一棵二叉树的前序序列为ABC,则有______________种不同的二叉树可以得到这种序列。
40.顺序存储的长度为m的循环队列为空的条件是__。
41.线性表作为队时,被称为__。
42.就快排序和堆排序,若原始记录接近正序或反序,则最好选用方法。
43.在有序表(12、24、36、48、60、72、84)中二分查找关键字72时所需进行的关键字比较次数为__。
44.二叉排序树每个结点的左右子树深度之差的绝对值不超过1,称为__。
45.n阶对称方阵A,以下三角矩阵压缩到一维数组S[n*(n+1)/2]中,若按行序为主存储,则A的第i行第j列元素(i>=j)对应在S中的存储位置是__。
46.顺序存储的线性表相对与链接存储的线性表,其缺点是__。
47.就排序的稳定性而言,快排序方法是__。
48.设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则第4趟直接选择排序结束后的结果为_________________。
49.设连通图G中有n个顶点e条边,则对应的最小生成树上有___________条边。
50.设有一组初始记录关键字序列为(50,16,23,68,94,70,73),则将它们调整成初始堆只需把16与___________相互交换即可。
三、解答题
1、序列70,50,18,26,37,45,62,23,46,59,105,按顺序插入结点,建立一棵二叉排序树,然后删除结点37,删除后树高不能增高。
分别画出该二叉排序树及删除结点37后的二叉排序树。
2、对带权图,给出以Prim算法构造最小生成树过程,并计算该树的权。
3、对带权图,给出以克鲁斯卡亚算法构造最小生成树过程,并计算该树的权。
4、正文为“CDDDAABBEECAAECDAACEDDABE”,设计ABCDE这5个字母的哈夫曼编码,使得正文编码最短。
5、给定权值6,12,3,75,40,30,20,65,34,给出按算法建立的哈夫曼树静态三叉链表存储结构。
6、给定权值6,12,3,75,40,30,20,65,34,构建哈夫曼树。
7、先序遍历序列a,b,c,s,g,f,d,e,j,h,k,i和中序遍历序列s,c,b,d,f,e,g,a,h,k,j,i,的二叉树,画出此二叉树,并给出其后序遍历序列。
8、画出深林转化的二叉树,并给出二叉树的先序、中序、后序遍历序列。
9、给定按关键码序列76,42,32,17,73,54,48,62,98,89,92,105,构建小顶堆逐步筛选过程。
10、给定按关键码序列76,42,32,17,73,54,48,62,78,89,2,10,构建大顶堆逐步筛选过程。
11、画出有向图的邻接表和逆邻接表存储示意图。
12、画出图的邻接表存储示意图,并按邻接表给
出深度优先搜索序列和广度优先搜索序列。
13、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7,基本表长度为10,用线性探测法解决冲突,关键码按给出的顺序填入表中。
请画出哈希表,并求等概率情况下查找成功的平均查找长度。
14、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7,基本表长度为10,用二次探测法解决冲突,关键码按给出的顺序填入表中。
请画出哈希表,并求等概率情况下查找成功的平均查找长度。
15、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7,基本表长度为7,用拉链法解决冲突,关键码按给出的顺序填入表中,且总是在链表的第一个结点前插入。
请画出哈希表,并求等概率情况下查找成功的平均查找长度。
四、算法设计题
typedefstruct{
intc,m;……}ELEM;//c为语文成绩,m为数学成绩
typedefstruct{ELEMt;intcnt;}TBL;//表定义
1、对数学成绩,将不及格和及格的学生分成前后两部分,使表前面为不及格的学生,后面为及格的学生。
不要求对这些元素按数学成绩排序,但要求尽量减少交换次数。
voidF1(TBL*tbl)
{//tbl为学生表
intlow,high;ELEMm;
for(low=0,high=t-1;low {while(low while(low if(low {m=tbl.t[low];tbl.t[low]=tbl.t[high];tbl.t[high]=m;} } } 2、表A按语文成绩非递减有序,表B按语文成绩非递增有序,将B表学生添加到A表,使A表依然按语文成绩非递减有序,B表不变。 要求移动元素次数不超过两表长度之和。 voidF2(TBL*pa,TBL*pb) {//pa、pb分别指向学生表a和b inti,j,len; i=pa->cnt-1;j=0;pa->cnt+=pb->cnt;len=pa->cnt-1; while(i>=0&&j {if(pa->t[i].c>pb->t[j].c)pa->t[len]=pa->t[i--]; elsepa->t[len]=pb->t[j]++; len--; } for(;j } 5、表A按语文成绩非递减有序,向表中添加一个学生,并保持A表的有序性。 voidF5(TBL*ta,ELEMe) {//ta为学生表A,e为添加的学生元素 inti; for(i=ta->cnt-1;i>=0&&ta->t[i].c>e.c;i--) ta->t[i+1]=ta->t[i]; ta->t[i+1]=e; } typedefstructnode{ELEMe;structnode*next;}NODE;//链表结点类型 6、对两个按语文成绩非递减有序的带头结点单链表A和B,将B表并入A表,而不改变其排序性,并将B表设置为空表。 voidF6(NODE*ah,NODE*bh) {//ah、bh分别为a表和b表的头结点 NODE*pa,*pb,*s; for(pa=ah,pb=bh->next;pb;) {for(;pa->next&&pb->e.c>=pa->next->e.c;)pa=pa->next; s=pb;pb=pb->next; s->next=pa->next;pa->next=s;pa=s; } bh->next=NULL; } 7、逆置单链表,即将结点顺序为: H->a1->a2->…->an,置换为: H->an->…->a2->a1。 要求,不交换元素值,通过修改结点指针完成。 voidF7(NODE*ah) {//ah为表的头结点 NODE*p,*s; for(p=ah->next,ah->next=NULL;p;) {s=p;p=p->next; s->next=ah->next;ah->next=s; } 8、求带头结点的单循环链表中的结点个数,不包括头结点。 intF8(NODE*ah) {//ah为表的头结点 intnum=0;NODE*s; for(s=ah->next;s! =ah;s=s->next)num++; returnnum; } 下列各题使用的结点类型: typedefstructnode{ELEMe;structnode*lc,rc;}NODE; 9、统计二叉树中叶子结点数目 intF9(NODE*t) {intnum=0; if(t){if(t->lc==NULL&&t->rc==NULL)num++; num+=F9(t->lc)+F9(t->rc); } returnnum; } 10、统计二叉树中只有一个子女(度为1)的结点数目 intF10(NODE*t) {intnum=0; if(t) {if((t->lc==NULL&&t->rc! =NULL)||(t->lc! =NULL&&t->rc==NULL) num++; num+=F10(t->lc)+F10(t->rc); } returnnum; } 11、统计二叉树中有两个子女(度为2)的结点数目 intF11(NODE*t) {intnum=0; if(t){if(t->lc&&t->rc)num++; num+=F11(t->lc)+F11(t->rc); } returnnum; } 12、统计二叉树中空指针域个数 intF12(NODE*t) {intnum=0; if(t){if(t->lc==NULL)num++; if(t->rc==NULL)num++; num+=F12(t->lc)+F12(t->rc); } returnnum; } 13、求二叉树深度 intF13(NODE*t) {intnum=0,k; if(t) {num=F13(t->lc);k=F13(t->rc); if(num num++; } returnnum; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题
![提示](https://static.bingdoc.com/images/bang_tan.gif)