数据结构.docx
- 文档编号:14809760
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:36
- 大小:145.68KB
数据结构.docx
《数据结构.docx》由会员分享,可在线阅读,更多相关《数据结构.docx(36页珍藏版)》请在冰点文库上搜索。
数据结构
给大家五套数据结构的习题,后面都附有答案,有些题目我已删去,但仍个别题目较难,请同学们在复习过程中根据自身情况选做,
试题
(一)
一、单选题
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
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
二、填空题
1. 通常从四个方面评价算法的质量:
____正确性_____、_易读性________、_高效率________和__强壮性_______。
2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为________。
5. 若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。
在这种存储结构中,n个结点的二叉树共有_2n_______个指针域,其中有__n-1______个指针域是存放了地址,有______n+6__________个指针是空指针。
6. 对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有_____e__个和_____2e___个。
7. AOV网是一种________有向无回网___________的图。
8. 在一个具有n个顶点的无向完全图中,包含有________条边,在一个具有n个顶点的有向完全图中,包含有________条边。
9. 假定一个线性表为(12,23,74,55,63,40),若按Key%4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
12. 在快速排序、堆排序、归并排序中,_________排序是稳定的。
三、运算题
1. 在如下数组A中链接存储了一个线性表,表头指针为A[0].next,试写出该线性表。
A01234567
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
2.
请画出图10的邻接矩阵和邻接表。
3. 已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,
(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。
四、阅读算法
1. LinkListmynote(LinkListL)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L;L=L->next;p=L;
S1:
while(p->next)p=p->next;
S2:
p->next=q;q->next=NULL;
}
returnL;
}
请回答下列问题:
(1)说明语句S1的功能;
(2)说明语句组S2的功能;
(3)设链表表示的线性表为(a1,a2,…,an),写出算法执行后的返回值所表示的线性表。
2. voidABC(BTNode*BT)
{
ifBT{
ABC(BT->left);
ABC(BT->right);
cout<
}
}该算法的功能是:
六、编写算法
统计出单链表HL中结点的值等于给定值X的结点数。
intCountX(LNode*HL,ElemTypex)
参考答案
(一)
一、单选题
1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A
二、填空题(每空1分,共26分)
1. 正确性易读性强壮性高效率2. O(n)3. 933
4. -134X*+2Y*3/-5. 2nn-1n+16. e2e
7. 有向无回路8. n(n-1)/2n(n-1)
9. (12,40)()(74)(23,55,63)
10. 增加111. O(log2n)O(nlog2n)12. 归并
三、运算题
1. 线性表为:
(78,50,40,60,34,90)
2. 邻接矩阵:
邻接表如图11所示:
图11
3. 用克鲁斯卡尔算法得到的最小生成树为:
(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20
4. 见图12
4
4
4
4
4
2
2
2
5
5
2
8
5
8
3
4
5
2
8
4
3
2
图12
四、阅读算法
1.
(1)查询链表的尾结点
(2)将第一个结点链接到链表的尾部,作为新的尾结点
(3)返回的线性表为(a2,a3,…,an,a1)
2. 递归地后序遍历链式存储的二叉树。
五、算法填空
trueBST->leftBST->right
六、编写算法
intCountX(LNode*HL,ElemTypex)
{inti=0;LNode*p=HL;//i为计数器
while(p!
=NULL)
{if(P->data==x)i++;
p=p->next;
}//while,出循环时i中的值即为x结点个数
returni;
}//CountX
试题
(二)
一、单选题
1、在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为()。
AnBn/2C(n+1)/2D(n-1)/2
2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。
As→link=p→link;p→link=s;Bp→link=s;s→link=q;
Cp→link=s→link;s→link=p;Dq→link=s;s→link=p;
3、 栈的插入和删除操作在()进行。
A栈顶B栈底C任意位置D指定位置
4、 由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为()
A24B71C48D53
二、填空题
1、数据的逻辑结构被分为__________、___________、________和________四种。
2、一种抽象数据类型包括______________和_____________两个部分。
3、在下面的数组a中链接存储着一个线性表,表头指针为a[o].next,则该线性表为_________________________________________________
a012345678
60
56
42
38
74
25
4
3
7
6
2
0
1
data
next
4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,判断链表为空的条件分别为________________和____________________。
5、用具有n个元素的一维数组存储一个循环队列,则其队首指针总是指向队首元素的___________,该循环队列的最大长度为__________。
6、当堆栈采用顺序存储结构时,栈顶元素的值可用———————表示;当堆栈采用链接存储结构时,栈顶元素的值可用_______________表示。
7、一棵高度为5的二叉树中最少含有_________个结点,最多含有________个结点;一棵高度为5的理想平衡树中,最少含有_________个结点,最多含有_________个结点。
8、在图的邻接表中,每个结点被称为____________,通常它包含三个域:
一是_____________;二是___________;三是_____________。
三、运算题
1、已知一组记录的排序码为(46,79,56,38,40,80,95,24),写出对其进行快速排序的每一次划分结果。
2、一个线性表为B=(12,23,45,57,20,03,78,31,15,36),设散列表为HT[0..12],散列函数为H(key)=key%13并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。
3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。
4、已知一个图的顶点集V各边集G如下:
V={0,1,2,3,4,5,6,7,8,9};
E={(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)}
当它用邻接矩阵表示和邻接表表示时,分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。
假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
图
深度优先序列
广度优先序列
邻接矩阵表示时
邻接表表示时
四、阅读算法
1、假定从键盘上输入一批整数,依次为:
786345309134–1,请写出输出结果。
#include
#include
consstintstackmaxsize=30;
typedefintelemtype;
structstack{
elemtypestack[stackmaxsize];
inttop;
};
#include“stack.h”
Voidmain()
{
stacka;
initstack(a);
intx;
cin>>x;
while(x!
=-1){
push(a,x);
cin>>x;
}
while(!
stackempty(a))
cout< cout< } 该算法的输出结果为: __________________________________________________________. 2、阅读以下二叉树操作算法,指出该算法的功能。 Template : unknown(BinTreeNode BinTreeNode if(p! =NULL){ temp=p→leftchild; p→leftchild=p→rightchild; p→rightchild=temp; unknown(p→leftchild); undnown(p→rightchild); } }该算法的功能是: ________________________________ 六、编写算法 编写算法,将一个结点类型为Lnode的单链表按逆序链接,即若原单链表中存储元素的次序为a1,……an-1,an,则逆序链接后变为,an,an-1,……a1。 Voidcontrary(Lnode*&HL) 试题(二答案) 一、单选题 题号 1 2 3 4 答案 C D A B 二、填空题 1: 集合、线性、树、图;2: 数据描述、操作声名; 3: (38,56,25,60,42,74);4: HL→next=NULL;HL=HL→next; 5: 前一个位置;n-1;6: S.stack[S.top];HS→data; 7: 5318: 边结点、邻接点域、权域、链域; 9: 索引值域、开始位置域;10: 10、3、3、B、I和J; 11: O(log2n)、O(nlog2n);12: m、m-1 三、运算题 1、 划分次序 划分结果 第一次 [382440]46[56809579] 第二次 24[3840]46[56809579] 第三次 24384046[56809579] 第四次 2438404656[809579] 第五次 243840465679[8095] 第六次 2438404656798095 2、 0123456789101112 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度: ASLSUCC=14/10=1.4 3、此二叉树的后序遍历结果是: EDCBIHJGFA 4、 图 深度优先序列 广度优先序列 邻接矩阵表示时 0,1,2,8,3,4,5,6,7,9 0,1,4,2,7,3,8,6,5,9 邻接表表示时 0,4,3,8,9,5,6,7,1,2 0,4,1,3,7,2,8,6,9,5 四、阅读算法,回答问题 1、 该算法的输入结果是: 349130456378 2、 该算法的功能是: 交换二叉树的左右子树的递归算法。 五、算法填空,在画有横线的地方填写合适的内容 1是: (low+high)/2; 2是: Binsch(A,low,mid–1,K); 3是: Binsch(A,mid+1,high,K); 4是: -1; 六、编写算法 根据编程情况,酌情给分。 { Lnode*P=HL; HL=NULL; While(p! =null) { Lnode*q=p; P=p→next; q→next=HL; HL=q; } } 试题(3) 一、单项选择题 1.算法指的是() A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列 2.线性表采用链式存储时,结点的存储地址() A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为() A.O (1)B.O(n)C.O(m)D.O(m+n) 4.由两个栈共享一个向量空间的好处是: () A.减少存取时间,降低下溢发生的机率B.节省存储空间,降低上溢发生的机率 C.减少存取时间,降低上溢发生的机率D.节省存储空间,降低下溢发生的机率 5.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为() A.front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m 6.如下陈述中正确的是() A.串是一种特殊的线性表B.串的长度必须大于零 C.串中元素只能是字母D.空串就是空白串 7.若目标串的长度为n,模式串的长度为[n/3],则执行模式匹配算法时,在最坏情况下的时间复杂度是() A.O( )B.O(n)C.O(n2)D.O(n3) 8.一个非空广义表的表头() A.不可能是子表B.只能是子表C.只能是原子D.可以是子表或原子 9.假设以带行表的三元组表表示稀疏矩阵,则和下列行表 0 2 3 3 5 对应的稀疏矩阵是() 10.在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为() A.4B.5C.6D.7 11.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为() A.eB.2eC.n2-eD.n2-2e 12.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是() A.O(n)B.O(e)C.O(n+e)D.O(n*e) 13.用某种排序方法对关键字序列(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.快速排序 二、填空题 16.数据的逻辑结构是从逻辑关系上描述数据,它与数据的无关,是独立于计算机的。 17.在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head=。 18.栈顶的位置是随着操作而变化的。 19.在串S=“structure”中,以t为首字符的子串有个。 20.假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中,其中B[0]存储矩阵中第1个元素a1,1,则B[31]中存放的元素是。 21.已知一棵完全二叉树中共有768结点,则该树中共有个叶子结点。 22.已知一个图的广度优先生成树如右图所示,则与此相 应的广度优先遍历序列为。 三、解答题 27.请画出与下列二叉树对应的森林。 28.已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示 a b c d e (1)画出该图的图形; (2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。 四、算法阅读题 30.下列算法的功能是比较两个链串的大小,其返回值为: comstr(s1,s2)= 请在空白处填入适当的内容。 intcomstr(LinkStrings1,LinkStrings2) {//s1和s2为两个链串的头指针 while(s1&&s2){ if(s1->date if(s1->date>s2->date)return1; ①; ②; } if(③)return-1; if(④)return1; ⑤; } ① ② ③ ④ ⑤ 31.阅读下面的算法 LinkListmynote(LinkListL) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L;L=L->next;p=L; S1: while(p->next)p=p->next; S2: p->next=q;q->next=NULL; } returnL; } 请回答下列问题: (1)说明语句S1的功能; (2)说明语句组S2的功能; (3)设链表表示的线性表为(a1,a2,…,an),写出算法执行后的返回值所表示的线性表。 32.假设两个队列共享一个循环向量空间(参见右下图), 其类型Queue2定义如下: typedefstruct{ DateTypedata[MaxSize]; intfront[2],rear[2]; }Queue2; 对于i=0或1,front[i]和rear[i]分别为第i个队列的头指针和尾指针。 请对以下算法填空,实现第i个队列的入队操作。 intEnQueue(Queue2*Q,inti,DateTypex) {//若第i个队列不满,则元素x入队列,并返回1;否则返回0 if(i<0||i>1)return0; if(Q->rear[i]==Q->front[①]return0; Q->data[②]=x; Q->rear[i]=[③]; return1; } ① ② ③ 33.已知二叉树的存储结构为二叉链表,阅读下面算法。 typedefstructnode{ DateTypedata; Struct
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构