数据结构部分习题.docx

《数据结构部分习题.docx》由会员分享，可在线阅读，更多相关《数据结构部分习题.docx（16页珍藏版）》请在三一办公上搜索。

1、数据结构部分习题数据结构部分习题 第二章 线性表 一、问答题 1、简述下列术语：线性表，顺序表，链表。 2、何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么? 3、在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素? 4、链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的? 二、单选题 1、在表长为n的单链表中,算法时间复杂度为O(n)的操作是( )。 A. 查找单链表中第i个结点 B. 在p结点之后插入一个结点 C. 删除表中第一个结点 D. 删除p结点的直接后继结点 2、 在下列链表中

2、不能从当前结点出发访问到其余各结点的是( )。 A. 单链表 B. 单循环链表 C. 双向链表 D. 双向循环链表 3、线性表采用顺序存储时，其地址 ( ) A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续与否均可以 4、线性表采用链式存储结构时，其地址 ( ) A必须是连续的 B部分地址必须是连续的 C.一定是不连续的 D连续与否均可以 5、在长度为n的顺序表的第i个数据元素(1in)之前插入一个数据元素,元素的移动次数为 ( )。 A. n-i+1 B. n-i C. i D. i-1 6、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 ( )。 A. 顺序

3、表 B. 用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 7、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。 A单链表 B双向链表 C单循环链表 D循环链表 8、在一个单链表h中，若要删除由指针q所指向结点的直接后继结点，则执行。 Ap = q-next ; p-next = q-next; Bp = q-next ; q-next = p; Cp = q-next ; q-next = p-next; Dq-next = q-next-next; q-next = q;9、 9、链表不具有的特点是。 A可随机访问任一元素 B插入删除不需要移动元素 C不必

4、事先估计存储空间 D所需空间与线性表长度成正比 10、对于一个头指针为h的带表头结点单链表，判定其为空表的条件是( )。 A. h=NULL； Bh-next=NULL； Ch!=NULL； Dh-next= h； 11、在非空单链表中，在p结点后插入一个q结点依次执行操作是( )。 A. q-link=p; p-link=q； B. q-link=p-link; p-link=q； C. q-link=p-link；p=q； D. p-link=q；q-link=p； 12、以下关于线性表的叙述中，正确的是 ( )。 A. 顺序表可以随机存取 B. 链表可以随机存取 C. 顺序表便于动态处理

5、 D. 顺序表便于插入或删除数据元素 13、在非空的单循环链表h中，某个p结点为尾结点的条件是( )。 A. p=NULL； Bp-link=NULL； Ch!=NULL； Dp-link= h； 14. 设p结点是带表头结点双向循环链表的表中结点,在p结点后插入s结点语句序列中正确的是( ) A. s-next=p-next；p-next-prior=s； p-next=s；s-prior=p； B. p-next=s；s-next=p-next； p-next-prior=s；s-next=p； C. p-next=s；p-next-prior=s； s-next=p-next；s-nex

6、t=p； D. p-next-prior=s；p-next=s； s-next=p-next；s-next=p； 15、设p结点是带表头结点的双循环链表的表中结点，在p结点之前插入s结点的语句序列中正确的是( )。 A. s-prior=p-prior；p-prior-next=s； p-prior=s；s-next=p； B. p-prior=s；p-prior-next=s； s-prior=p-prior；s-next=p； C. p-prior-next=s；p-prior=s； s-prior=p-prior；s-next=p； D. p-prior=s；s-next=p； p-pr

7、ior-next=s；s-prior=p-prior； 16、以下关于静态链表的叙述中，错误的是 ( )。 静态链表既有顺序存储的优点又有动态链表的优点，所以它存取表中第i个元素的时间与i无关。 .静态链表能容纳的最多元素个数在表定义时就确定了，以后不能增加。 .静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 A.只有 B.只有 C. 和 D. 、和 17、在具有n个结点的单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )。 A. O(1) B. O(n) C. O(nlog2n) D. O(n2) 三、算法题 1、设顺序表L是递增有序表，试写一算法，将x插入到L中并使

8、L仍是递增有序表。 2、写一求单链表的结点数目ListLength(L)的算法。 3、写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。 4、写一算法从一给定的向量A删除值在x到y(xy)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 第三章 栈和队列 一、问答题 1、设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？ 2、循环队列的优点是什么?如何判断它的空和满？ 3、利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SeqStack S) ，并说明S为何不作为引用参数的算法?

9、4、一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S) ，入栈Push(S,i,x)，出栈Pop(S,i,x)算法，其中i为0或1 ，用以表示栈号。 5、假设Q0,5是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。 a. d, e, b, g, h入队 b. d, e出队 c. i , j , k , l , m入队 d. b出队 e. n, o, p, q, r入队 二、选择题 1、在栈中存取数据遵守的原则是 A先进先出 B后进

10、先出 C后进后出 D随机进出 2、设S是顺序栈,元素a,b,c,d,e,f依次栈,如果出栈顺序为b,c,d,f,e,a,则顺序栈的容量至少应为( )个元素。 A. 2 B. 3 C. 4 D. 5 3、用一个大小为N的一维数组顺序存储一个栈时，假定用top=N表示栈空，则向栈中插入一个元素时,首先应执行( )语句修改top指针。 Atop+ B top- C top=0 D top=0 4、设有一个空栈，栈顶指针为1000H,每个元素占一个单位的存储空间，则执行Push,Push,Pop,Push,Pop,Push,Pop,Push操作以后，栈顶指针的位置是。 A. 1000 B. 1001

11、C. 1002 D. 1003 5、表达式a*(b+c)-d的后缀表达式是( ) 。 Aabcd *+- B. abc+*d - C. abc*+d - D. -+ * abcd 6、一个初始输入序列a、b、c、d，顺序进入栈S，然后依次从栈S中出栈并进入队列Q中，再从队列Q中出队进入栈S，则在栈S中从栈顶到栈底的序列是( ) 。 A. abcd B. dcba C. badc D. adcb 7、用一个大小为6的数组来实现循环队列，元素依次按照0,1,2,3,4,5的位置顺序循环存放,当前front和rear的值分别为4和0，现在从队列中删除一个元素,再加入2个元素后,front和rear的

12、值分别是( )。 A5和2 B6和1 C2和4 D3和1 8、设一个循环队列Qmaxsize的队头指针为front 、队尾指针为rear,队列的最大容量为maxsize , 除此之外该队列没有其他数据成员，则该队列的队满条件是( )。 A. Q.rear=Q.front B. Q.rear+Q.front =maxsize C. (Q.rear+1)% maxsize =Q.front D. (Q.front+1)% maxsize =Q.rear 第4章 树的习题 一、选择题 关于二叉树下列说法正确的是。 A.二叉树的度为2 B.二叉树的度可以小于2 C.每一个结点的度都为2 D.至少有一个

13、结点的度为2 设高度为h的二叉树只有度为0和度为2的节点，则此二叉树中结点总数至少为。 A.2h B.2h-1 C. 2h+1 D.h+1 在树种，结点A有4个兄弟，B是A的双亲，则B的度为。 A.3 B.4 C. 5 D. 6 若一棵完全二叉树中，某节点无左孩子，则该结点一定是。 A.度为1的结点 B.度为2的结点 C.分支节点 D.叶子结点 高度为k的完全二叉树至多有个结点，至少有个结点。 A.2K-1-1 B. 2K-1 C.2K-1 D.2K 先序序列为ABC的二叉树有棵。 A. 3 B.4 C.5 D.6 在有200个结点的完全二叉树中，根的编号为1，则编号为60的结点左孩子编号是，

14、右孩子的编号是。 A.30 B.60 C.120 D.121 遍历一棵具有n个结点的完全二叉树，在先序，中序和后序序列中，叶子结点的相对次序。 A.都不同 B.完全相同 C.先序和中序相同 D.中序与后序相同 在由4棵树组成的森林中，1，2，3，4棵树，树中结点的个数分别为30，10，20，5，当把森林转化成为二叉树后，对应的二叉树中根结点的左子树中结点的个数是，右子树中结点的个数是。 A.20 B.29 C.30 D.35 有n个结点的二叉树的先序序列与后序序列相反，则二叉树中除了叶子外，每个结。 A.仅有左孩子 B.仅有右孩子 C.仅有一个孩子 D.都有两个孩子 判断线索二叉树中p有右孩子

15、的条件是。 A.p！=NULL B.p-rchild!=NULL C.p-rtag=0 D.p-rtag=1 每棵树都能唯一的转化为对应的二叉树，由树所转化的二叉树中，一个结点p的左孩子是它在原树中对应结点的，右孩子是它在原树中对应结点的。 A.最左孩子 B.最右孩子 C.右临兄弟 D.左邻兄弟 一棵具有124个叶子的完全二叉树，最多有结点，最少有结点。 A.247 B.248 C.249 D.250 二、填空题 树中每个结点有个孩子，除根之外，每个结点有个双亲。 若树中度为1，2，3，4的结点的个数为4，3，2，2，则叶子结点的个数是。 一棵具有n个结点的二叉树，若叶子结点的个数为m,则度为

16、1的结点的个数是。 高度为k的二叉树至多有个结点，第i层有个结点；高度为k的二叉树至少有个结点。 已知二叉树中有30个叶子，则二叉树中结点个数最少为。 一个含有68个结点的完全二叉树，它的高度是。 已知一棵完全二叉树第6层有6个叶子结点，则总结点数至少是，其中叶子结点个数是；则总结点数至多是，其中叶子结点个数是。 一棵树转化成二叉树后，这棵二叉树的根节点一定没有孩子，若树中有m个分支结点，则对应二叉树中个结点没有右孩子。 若用二叉链表表示具有n个结点的二叉树，则有个空链域。 具有m个叶子结点的赫夫曼树，共有个结点。 树的后序序列与对应二叉树的遍历序列相同。 线索二叉树的左线索指针指向，右线索指

17、向。 三、简答题 具有n个结点的满二叉树的叶子结点的个数是多少？ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。 一棵深度为h的满k叉树有如下性质： 第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： 各层的结点数是多少? 编号为i的结点的双亲结点(若存在)的编号是多少? 编号为i的结点的第j个孩子结点(若存

18、在)的编号是多少? 编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索二叉树。 设给定权值集合w=3,5,7,8,11,12 ，请构造关于w的一棵huffman树，并求其加权路径长度WPL 。 假设用于通信的电文是由字符集a, b, c, d, e, f, g, h中的字符构成， 这8个字符在电文中出现的概率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 。 请画出对应的huffman树(按左子树根结点的权小

19、于等于右子树根结点的权的次序构造)。 求出每个字符的huffman编码。 第5章 图的习题 一、选择题 有n个顶点的无向完全图具有( A )条边. A、n(n-1)/2 B、n-1 C、n D、n(n-1) 在一个图中，所有顶点的度数之和等于图的边数的( C )倍。 A、1/2 B、 1 C、 2 D、 4 有8个结点的连通图最少有( C )条边。 A、5 B、 6 C、 7 D、 8 有8个结点的强连通图最少有( D )条边。 A、5 B、 6 C、 7 D、 8 下面关于图的存储结构正确的是。 A.用邻接矩阵存储图占用的空间大小只与图中的顶点数相关，与边数无关。 B.用邻接矩阵存储图占用的

20、空间大小只与图中的边数相关，与顶点数无关。 C.用邻接表存储图占用的空间大小只与图中的顶点数相关，与边数无关。 D.用邻接矩阵存储图占用的空间大小只与图中的边数相关，与顶点数无关。 下面哪种图的邻接矩阵是对称的。 A.AOE B. AOV C.无向图 D.有向图 设有向无权图G中有n个顶点，它的邻接矩阵存在于二维数组A中，则顶点i的度为。 深度优先遍历类似于二叉树的( ) A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 广度优先遍历类似于二叉树的( ) A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 连通图的生成树。 A.可能不存在 B.只有一棵 C.一棵或多棵 D.一定有多棵

21、 下列关于BFS和DFS生成树论述正确的是。 A.BFS生成树的高度DFS生成树的高度 B.BFS生成树的高度DFS生成树的高度 D.BFS生成树的高度=DFS生成树的高度 G是一个非连通无向图，共有28条边，则该图至少应该有个顶点。 A.7 B.8 C.9 D.10 下面关于关键路径叙述是正确的。 A.从开始顶点到完成顶点具有最大长度路径，关键路径的长度是完成工期的最短时间。 B.从开始顶点到完成顶点具有最小长度路径，关键路径的长度是完成工期的最短时间。 C.从开始顶点到完成顶点具有最大长度路径，关键路径的长度是完成工期的最长时间。 D.从开始顶点到完成顶点具有最小长度路径，关键路径的长度是

22、完成工期的最长时间。 二、填空题 有n个顶点和e条边的有向图和无向图用邻接表表示，则邻接表边结点的个数分别是和。 图的邻接表存储顶点的邻接点，逆邻接表存储顶点的邻接点。 设有一稀疏图G，则G采用 存储较省空间；设有一稠密图G，则G采用存储较省空间。 已知一个图的邻接矩阵，删除所有从第i个顶点出发的方法是。 n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接表存储时，该算法的时间复杂度为 。 三、判断题 图的邻接矩阵表示是唯一的。 图的邻接表表示是唯一的。 无向图的邻接矩阵一定是对称的。 有向图的邻接矩阵一定是不对称的。 有向图用邻接表表示，顶点i的出度是对应顶点i

23、链表中结点的个数。 有向图用邻接表表示，顶点i的度是对应顶点i链表中结点的个数。 若从无向图的任意顶点出发，进行一次深度优先搜索，可以访问图中全部顶点，则该图一定是连通的。 在非连通图的遍历中，调用深度优先遍历算法的次数等于连通分量的个数。 在具有n个顶点的强连通图邻接矩阵中，至少有n个小于的非零元素。 连通图的生成树一个极小连通子图。 带权连通图的最小生成树是唯一的。 在AOE网中仅存在一条关键路径。 在有向图的邻接矩阵中，主对角线以下的元素均为0，则该图一定有拓扑序列。 在图的邻接表表示中，表中有奇数个边结点，则该图一定是有向图。 在AOE网中，任何一个关键活动提前完成，则整个工程的工期都

24、会提前。 图的深度优先遍历序列一定是唯一的。 拓扑排序输出的顶点个数小于图中的顶点个数，则该图一定存在环。 四、简答题 已知图G=(V,E),其中V=a,b,c,d,e ,E=,要求： a.画出图； b.给出图的邻接矩阵和邻接表； c.给出图的所有拓扑序列。 已知带权无向图的如下图所示，要求。 a.给出从0点出发深度优先和广度优先的遍历序列； b.画出从0点出发的深度优先生成树和广度优先生成树； c.给出普利姆算法构造最小生成树的过程； d.给出克鲁斯卡尔算法构造最小生成树的过程。 已知有向带权图如下图所示，要求 a.各处图的邻接矩阵； b.利用迪杰斯特拉算法求从1到其余各顶点的最短路径； c

25、.利用弗洛伊德算法求任意两顶点间的最小路径。 已知AOE 网如下图所示，要求 a.每个顶点的最早和最晚发生时间； b.工程的最短工期； c.关键路径。 第六章 矩阵存储 二维数组A05,06的每个元素占有5字节，按列优先存储在起始地址为1000的单元中，则A5,5的地址是. 在三维数组A8,8,10采用行优先存储从 A0,0,0初开始存储，若每个元素的大小为L,则A3,2,8的存储地址是。 A.A0,0,0+198*L B. A0,0,0+108*L C.A0,0,0+268*L D. A0,0,0+13*L n阶矩阵A，采用压缩存储方式，用一维数组 Fm存放该矩阵的下三角元素，则 m为 A.

26、n(n-1) B.n(n-1)/2 C.n(n+1) D.n(n+1)/2 若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组Fn(n+1)/2中，第一个非零元素a11存于F0中，非零元素aij应存放到Fk中, 则k是( )。 A.(2n-j+1)j/2+i-j B.(2n-j+2)(j-1)/2+i-j C.(2n-i+1)i/2+j-i D. (2n-i+2)i/2+j-I 第七章 查找 一、选择题 1下面哪些操作不属于静态查找表。 A）查询某个特定元素是否在表中。 B）检索某个特定元素的属性。 C）插入一个数据元素。 D）建立一个查找表。 2下面描述不正确的是 A）顺序查找对表中元素存放

27、位置无任何要求，当n较大时，效率低。 B）静态查找表中关键字有序时，可用二分查找。 C）分块查找也是一种静态查找表。 D）经常进行插入和删除操作时可以采用二分查找。 3对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一个元素的平均查找长度为。 A）11/8 B）7/4 C）9/4 D）11/42 4对有14个数据元素的有序表R14进行二分查找，搜索到R4的关键码等于给定值，此时元素比较顺序依次为。 A）R1，R2，R3，R4 B）R1，R13，R2，R3 C）R7，R3，R5，R4 D）R7，R4，R

28、2，R3 5分块查找时确定块的查找可以用顺序查找，也可以用，而在块中只能是。 A）静态查找，顺序查找 B）二分查找，顺序查找 C）二分查找，二分查找 D）散列查找，顺序查找 6对一棵二叉排序树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是 A）小于 B）大于 C）等于 D）不小于 7设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列不可能是在二叉排序树上查找到的序列。 A）2,252,401,398,330, 344,397,363 B）924, 220, 911, 244, 898, 258, 362, 363 C）2, 399, 3

29、87, 219, 266, 382, 381, 278, 363 D）925, 202, 911, 240, 912, 245, 363 8若根据查找表建立长度为 m 的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则下一次的散列地址为 ( ) 。 A） d B）(d+1)%m C） (d+1)/m D） d+19 9.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其余地址为空，如用二次探测处理冲突，关键字为49的结点的地址是 A）8 B）3 C）5

30、D）9 二、简答题 10已知已下元素序列:10,18,3,12,6,4,2要求： a.构造二叉排序树 b.查找6需要比较那些关键字 c.求其平均查找长度 d.画出删除10后的结果 11. 已知散列表的表长为12，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。 12设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。 13. 输入关键字序列为 16,3,7,11,9,26,18 ，构造平衡二叉树。 14. 画出长度是10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 15. 设关键字为字符，一组关键字的插入顺序为C,S,M,T,A,E,P,U,K,N,B,要求： (1)给出从空树开始,顺序插入构造3阶B-树。 (2)分别给出在该树上删除E、P后的结果。