数据机构复习大纲.docx
- 文档编号:14588953
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:41
- 大小:271.63KB
数据机构复习大纲.docx
《数据机构复习大纲.docx》由会员分享,可在线阅读,更多相关《数据机构复习大纲.docx(41页珍藏版)》请在冰点文库上搜索。
数据机构复习大纲
复习大纲(信计)
习题2线性表---------------------------------------------------------------------------------8
习题3栈和队列------------------------------------------------------------------------------11
习题5数组------------------------------------------------------------------------------------15
习题6树与二叉树---------------------------------------------------------------------------17
习题7图---------------------------------------------------------------------------------------24
习题8查找------------------------------------------------------------------------------------31
习题9排序------------------------------------------------------------------------------------34
习题2线性表
2.1单项选择题
1.一个向量(即一批地址连续的存储单元)第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是____。
A.110B.108C.100D.120
2.线性表的顺序存储结构是一种___的存储结构,而链式存储结构是一种___的存储结构。
A.随机存取B.索引存取C.顺序存取D.散列存取
3.线性表的逻辑顺序与存储顺序总是一致的,这种说法___。
A.正确B.不正确
4.线性表若采用链式存储结构时,要求内存中可用存储单元的地址___。
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续或不连续都可以
5.在以下的叙述中,正确的是___。
A.线性表的顺序存储结构优于链表存储结构
B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D.线性表的链表存储结构优于顺序存储结构
6.每种数据结构都具备三个基本运算:
插入、删除和查找,这种说法___。
A.正确B.不正确
7.不带头结点的单链表head为空的判定条件是____。
A.head==NULLB.head->next==NULL
C.head->next==headD.head!
=NULL
8.带头结点的单链表head为空的判定条件是____。
A.head==NULLB.head->next==NULL
C.head->next==headD.head!
=NULL
9.非空的循环单链表head的尾结点(由p所指向)满足____。
A.p->next==NULLB.p==NULL
C.p->next==headD.p==head
10.在双向循环链表的p所指结点之后插入s所指结点的操作是____。
A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;
11.在一个单链表中,已知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;
12.在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行____。
A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;
C.s->next=p->next;p=s;C.p->next=s;s->next=p;
13.在一个单链表中,若删除p所指结点的后续结点,则执行____。
A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;
C.p=p->next;D.p=p->next->next;
14.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较____个结点。
A.nB.n/2C.(n-1)/2D.(n+1)/2
15.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。
A.O
(1)B.O(n)C.O(n2)D.O(nlog2n)
16.给定有n个元素的向量,建立一个有序单链表的时间复杂度是____。
A.O
(1))B.O(n)C.O(n2)D.O(n*log2n)
2.2填空题(将正确的答案填在相应的空中)
1.单链表可以做____的链接存储表示。
2.在双链表中,每个结点有两个指针域,一个指向______,另一个指向_____。
3.在一个单链表中p所指结点之前插入一个s(值为e)所指结点时,可执行如下操作:
q=head;
while(q->next!
=p)q=q->next;
s=newNode;s->data=e;
q->next=;//填空
s->next=;//填空
4.在一个单链表中删除p所指结点的后继结点时,应执行以下操作:
q=p->next;
p->next=____;//填空
delete;//填空
5.在一个单链表中p所指结点之后插入一个s所指结点时,应执行s->next=____和p->next=____的操作。
6.对于一个具有n个结点的单链表,在已知p所指结点后插入一个新结点的时间复杂度是____;在给定值为x的结点后插入一个新结点的时间复杂度是____。
习题答案
2.11.B2.A,C3.B4.D5.C6.B7.A8.B
9.C10.D11.C12.B13.A14.D15.B16.C
2.21.线性结表2.前驱结点、后继结点
3.s,p4.q->next,q
5.p->next,s6.O
(1),O(n)
习题3栈和队列
3.1单项选择题
1.一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是____。
A.edcbaB.decbaC.dceabD.abcde
2.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为____。
A.iB.n-iC.n-i+1D.不确定
3.栈结构通常采用的两种存储结构是____。
A.顺序存储结构和链式存储结构
B.散列方式和索引方式
C.链表存储结构和数组
D.线性存储结构和非线性存储结构
4.判定一个顺序栈ST(最多元素为m0)为空的条件是____。
A.top!
=0B.top==0C.top!
=m0D.top==m0-1
5.判定一个顺序栈ST(最多元素为m0)为栈满的条件是____。
A.top!
=0B.top==0C.top!
=m0D.top==m0-1
6.栈的特点是____,队列的特点是____。
A.先进先出B.先进后出
7.向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行____。
(不带空的头结点)
A.HS—>next=s;
B.s—>next=HS—>next;HS—>next=s;
C.s—>next=HS;HS=s;
D.s—>next=HS;HS=HS—>next;
8.从一个栈顶指针为HS的链栈中删除一个结点时,用x保存被删结点的值,则执行____。
(不带空的头结点)
A.x=HS;HS=HS—>next;B.x=HS—>data;
C.HS=HS—>next;x=HS—>data;D.x=HS—>data;HS=HS—>next;
9.一个队列的数据入列序列是1,2,3,4,则队列的出队时输出序列是____。
A.4,3,2,1B.1,2,3,4
C.1,4,3,2D.3,2,4,1
10.判定一个循环队列QU(最多元素为m0)为空的条件是____。
A.rear-front==m0B.rear-front-1==m0
C.front==rearD.front==rear+1
11.判定一个循环队列QU(最多元素为m0,m0==Maxsize-1)为满队列的条件是____。
A.((rear-front)+Maxsize)%Maxsize==m0
B.rear-front-1==m0C.front==rearD.front==rear+1
12.循环队列用数组A[m]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是____。
A.(rear-front+m)%mB.rear-front+1
C.rear-front-1D.rear-front
13.栈和队列的共同点是____。
A.都是先进后出B.都是先进先出
C.只允许在端点处插入和删除元素D.没有共同点
3.2填空题(将正确的答案填在相应的空中)
1.向量、栈和队列都是____结构,可以在向量的____位置插入和删除元素;对于栈只能在____插入和删除元素;对于队列只能在____插入元素和____删除元素。
2.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时,需向后移动____个元素。
3.向一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动____个元素。
4.栈顶指针指向站定元素,向栈中压入元素的操作是先________,后。
5.栈顶指针指向站定元素,对栈进行退栈时的操作是先________,后____。
6.在一个循环队列中,队首指针指向____位置。
7.从循环队列中删除一个元素时,其操作是先________,后____。
8.在具有n个单元的循环队列中,队满时共有____个元素。
9.一个栈的输入序列是12345,则栈的输出序列43512是____。
10.一个栈的输入序列是12345,则栈的输出序列12345是____。
习题答案
3.11.C2.C3.A4.B5.D6.BA7.C8.D9.B10.C
11.A12.A13.C
3.21.线性、任何、栈顶、队尾、队首2.n-i+13.n-i
4.先移动栈顶指针,后存入元素5.先取出元素,后移动栈顶指针
6.队首元素前一个存储7.先移动队首元素,后取出元素
8.n-19.不可能的10.可能的
习题5数组
5.1单项选择题
1.常对数组进行的两种基本操作是____。
A.建立与删除B.索引和修改
C.对数据元素的存取和修改D.查找与索引
2.二维数组M的元素是6个字符(每个字符占一个存储单元,即一个字节)组成的串,行下标i的范围从0到8,列下标j的范围从0到9,则存放M至少需要①__个字节;M数组的第8列和第5行共占②____个字节。
①A.90B.180C.240D.540
②A.108B.114C.54D.60
3.二维数组A中,每个元素的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,存放该数组至少需要的字节数是____。
A.80B.100C.240D.270
4.二维数组A中,每个元素A的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按行存放时,数组元素A[7][4]的起始地址为____。
A.SA+141B.SA+144C.SA+222D.SA+225
5.二维数组A中,每个元素A的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为____。
A.SA+141B.SA+180C.SA+222D.SA+225
5.2填空题(将正确的答案填在相应的空中)
1.已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是_______。
2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元并且A[0][0]的存储地址是200,则A[6][12]的地址是____。
3.二维数组A[10..20][5..10]采用行序为主方式存储,每个元素占4个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的地址是____。
习题答案
5.11.C2.D,A3.C4.C5.B
5.21.LOC(A[0][0])+(n*i+j)*k2.200+(6*20+12)=326
3.1000+((18-10)*6+(9-5))*4=1208
习题6树和二叉树
6.1单项选择题
1.有关二叉树下列说法正确的是
A.二叉树的度为2B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2
2.假定在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为个。
A.15B.16C.17D.47
3.按照二叉树的定义,具有3个结点的不同形状的二叉树有____种。
A.3B.4C.5D.6
4.按照二叉树的定义,具有3个不同数据结点的不同的二叉树有____种。
A.5B.6C.30D.32
5.深度为5的二叉树至多有____个结点。
A.16B.32C.31D.10
6.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为____。
A.2hB.2h-1C.2h+1D.h+1
7.对一个满二叉树,m个树叶,n个结点,深度为h,则____。
A.n=h+mB.h+m=2nC.m=h-1D.n=2h-1
8.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。
A.不发生改变B.发生改变C.不能确定D.以上都不对
9.如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为____。
A.uwvtsB.vwutsC.wuvtsD.wutsv
10.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法____。
A.正确B.错误
11.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是____。
A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca
12.在一非空二叉树的中序遍历序列中,根结点的右边____。
A.只有右子树上的所有结点B.只有右子树上的部分结点
C.只有左子树上的部分结点D.只有左子树上的所有结点
13.如图6.1所示二叉树的中序遍历序列是____。
A.abcdgefB.dfebagcC.dbaefcgD.defbagc
图6.1
14.一棵二叉树如图6.2所示,其中序遍历的序列为____。
A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh
15.设a,b为一棵二叉树上的两个结点,在中序遍历时,a在b前的条件是。
A.a在b的右方B.a在b的左方
C.a是b的祖先D.a是b的子孙
16.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是____。
A.acbedB.decabC.deabcD.cedba
17.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是____
A.9B.11C.15D.不确定
18.如图6.3所示的4棵二叉树,____不是完全二叉树。
19.一棵完全二叉树上有1001个结点,其中叶子结点的个数是
A.250B.500C.254D.505E.以上答案都不对
20.在线索化二叉树中,t所指结点没有左子树的充要条件是____。
A.t—>left=NULLB.t—>ltag=1
C.t—>ltag=1且t—>left=NULLD.以上都不对
*21.二叉树按某种顺序线索化后,任一结点均有指向其前驱和后续的线索,这种说法____。
A.正确B.错误
22.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。
这种说法____。
A.正确B.错误
23.一个具有1025个结点的二叉树的高h为____。
A.11B.10C.11至1025之间D.10至1024之间
24.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里,我们把由树转化得到的二叉树叫做这棵数对应的二叉树。
结论____是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
25.树最适合用来表示____。
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
6.2填空题(将正确的答案填在相应的空中)
1.有一棵树如图6.5所示,回答下面的问题:
⑴这棵树的根结点是____;
⑵这棵树的叶子结点是____;
⑶结点k3的度是____;
⑷这棵树的度是____;
⑸这棵树的深度是____;
⑹结点k3的子女是____;
图6.5一棵树
⑺结点k3的父结点是____;
2.指出树和二叉树的两个主要差别____、____。
3.树可采用做存储结构,并利用解决树的有关问题。
4.一棵二叉树的结点数据采用顺序存储结构,存储于数组t中,如图6.6所示,则该二叉树的链接表示形式为____。
5.深度为k的完全二叉树至少有____个结点。
至多有____个结点,若按自上而下,从左到右次序给结点编号(从1开始),则编号最小的叶子结点的编号是____。
6.在一棵二叉树中,度为零的结点的个数为n0,度为2的结点的个数为n2,则有n0=____。
7.一棵二叉树的第i(i≥1)层最多有____个结点;一棵有n(n>0)个结点的满二叉树共有____个叶子和____个非终端结点。
8.一棵树T中,包括一个度为1的结点,两个度为2的结点,三个度为3的结点,四个度为4的结点和若干叶子结点,则T的叶结点数为______。
9.现有按中序遍历二叉树的结果为abc,问有____种不同形态的二叉树可以得到这一遍历结果,这些二叉树分别是____(作图)。
10.由如图6.7所示的二叉树,回答以下问题:
⑴其中序遍历序列为____;
⑵其前序遍历序列为____;
⑶其后序遍历序列为____;
6.3简答题
1.根据二叉树的定义,具有三个结点的二叉树有5种不同的形态,请将它们分别画出。
2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。
请画出该树。
3.由如图6.7所示的二叉树,回答以下问题:
(1)画出该二叉树的中序线索二叉树;
(2)画出该二叉树对应的森林。
4.已知一棵树如图6.8所示,转化为一棵二叉树,表示为___
5.以数据集{4,5,6,7,10,12,18}为结点权值,画出构造Huffman树的每一步图示,计算其带权路径长度为。
6.一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?
习题答案
6.11.D2.B3.C4.C5.C6.A7.D8.A9.C10.A
11.D2.A13.B14.B15.B16.D17.B18.C
19.E20.B*21.B22.B23.C24.A25.C
6.2
1.⑴k1⑵k2,k5,k7,k4⑶2⑷3⑸4⑹k5,k6⑺k1
2.树中结点的最大度数没有限制,而二叉树结点的最大度数为2;
树的结点无左、右之分,而二叉树的结点有左、右之分;
3.孩子-兄弟链表(二叉链表),二叉树的已有算法。
4.如图6.9所示
5.2k-1、2k-1、2k-2+1
6.n2+1
7.2i-12[log2n+1]-12[log2n+1]–1
8.21
9.5;如图6.10所示
10.dgbaechif、abdgcefhi、gdbeihfca、
6.31.5种,图6.11
2.二叉树如图6.12所示。
3.中序线索二叉树如图6.13(左)所示;后序线索二叉树如图6.13(右)所示;
该二叉树转换后的的森林如图6.14所示。
4.图6.8的树转化为一棵二叉树如下,图6.15:
5.画出构造Huffman树如图6.16所示,计算其带权路径长度为。
6.一棵含有N个结点的k叉树,可能达到的最大深度h=N-k+1,
最小深度各为:
logkN+1。
习题7图
7.1单项选择
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 机构 复习 大纲