数据结构练习题及部分答案

1、第一章绪论一选择题1数据结构被形式地定义为（K，R），其中K是的有限集合，R是K上的的有限集合。A.算法B.数据元素C.数据操作D.逻辑结构 A 操作B 映象C.存储D 关系2.算法分析的目的是，算法分析的两个主要方面是。 A找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D分析算法的易懂性和文档性 A空间复杂性和时间复杂性8 .正确性和简明性C.可读性和文档性D数据复杂性和程序复杂性9 在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为A逻辑结构B顺序存储结构C.链表存储结构D.以上都不对4数据结构中，在逻辑上可以把数据结构分成：（）。A.动态结

2、构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5以下属于顺序存储结构优点的是（）。A存储密度大B插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示6数据结构研究的内容是（）。A数据的逻辑结构B数据的存储结构C.建立在相应逻辑结构和存储结构上的算法D.包括以上三个方面）。7链式存储的存储结构所占存储空间（A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数8计算机算法指的是（1），它具备输入，输出和（2）等五个特性。

3、B. 排序方法D. 调度方法B.可行性，确定性和有穷性D. 易读性，稳定性和安全性1 ）A.计算方法C.解决问题的有限运算序列2 ）A.可行性，可移植性和可扩充性C.确定性，有穷性和稳定性9以下关于数据的逻辑结构的叙述中正确的是（）。A数据的逻辑结构是数据间关系的描述B数据的逻辑结构反映了数据在计算机中的存储方式C数据的逻辑结构分为顺序结构和链式结构D数据的逻辑结构分为静态结构和动态结构10算法分析的主要任务是（）。A探讨算法的正确性和可读性B探讨数据组织方式的合理性C为给定问题寻找一种性能良好的解决方案D研究数据之间的逻辑关系11计算机内部数据处理的基本单位是（）。A.数据B.数据元素C.数

4、据项D.数据库二、填空题1 .下面程序段的时间复杂度是。for(I=1;I<n;I+)for(j=1;j<n;j+)x+;for(k=1;k<n;k+)x+;2 下面程序段的时间复杂度是s=0;for(i=0；i<n；i+)for(j=0;j<n;j+)s+=b皿；sum=s;3 .数据结构按逻辑结构可分为两大类，分别是和。4 .一个算法的效率可分为效率和效率。5 .设n为正整数。下列程序段中前置以记号的语句的频度为。i=1;k=0;while(i<=n-1)k+=10*i;i+；6算法时间复杂度的分析通常有两种方法，即和的方法，通常我们对算法求时间复杂度时

5、，采用后一种方法。第二次作业1.对以下单链表分别执行下列各程序段，画出结果示意图。LPRQ=P->next;(2) S=P->next->next;(3) R->data=P->data;(4) R->data=P->next->data;(5) T=P；while(T!=NULL)T->data=T->data*2;T=T->next;2.简述以下算法的功能。StatusA(LinkListL)/L是无表头结点的单链表if(L&&L->next)Q=L;L=L->next;P=L;while(P-&

6、gt;next)P=P->next;P->next=Q;Q->next=NULL;returnOK;/A3. 写一算法在带头结点的单链表结构上实现线性表操作LOCATE（L,x）。（求x在单链表L中的位序）4. 写一算法在带头结点的单链表结构上实现线性表操作LENGTH（L）。（求单链表L中的元素个数）5. 选择题（1）对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A.head=NULLB.heacHnext=NULLC.headfnext=headD.head!=NULL2）完成在双循环链表结点p之后插入s的操作是（）Ap->next=s;s-

7、>prior=p;p->next->prior:=s;s->next=p->next;Bp->next->prior=s;p->next=s;s->prior=p;s->next:=p->next;Cs->prior=p;s->next:=p->next;p->next=s;p->next->prior=s;Ds->prior=p;s->next:=p->next;p->next->prior=s;p->next=s;（ 3）线性表是具有n个（）的有限序列。

8、A.表元素B.字符C.数据元素D.数据项（ 4）下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。（5）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A 顺序表B 双链表（ 6 ）线性表是 。A 一个有限序列，可以为空C 一个无限序列，可以为空（ 7 ）链表不具有的特点是（C.带头结点的双循环链表D.单循环链表B.一个有限序列，不可以为空D.一个无限序列

9、，不可以为空）B 可随机访问任一元素A插入、删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性长度成正比8） .在运算中，使用顺序表比链表好。A.插入B.删除C.根据序号查找D.根据元素值查找9） .在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行As->next=p->next;p->next=sBq->next=s;s->next=pCp->next=s->next;s->next=pDp->next=s;s->next=q（10）.在顺序表中，只要知道，就可在相同时间内求出任一结点的存储

10、地址。A.基地址B.结点大小C.向量大小D.基地址和结点大小（ 11） .以下关于线性表的说法不正确的是。A.线性表中的数据元素可以是数字、字符、记录等不同类型。B.线性表中包含的数据元素个数是任意的。C.线性表中的每个结点都有且只有一个直接前趋和直接后继。D.存在这样的线性表：表中各结点都没有直接前趋和直接后继。（ 12） .从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较个元素结点。An/2BnC（n+1）/2D（n-1）/2第三次作业一写出下列程序段的输出结果:voidmain()StackS;charx,y;InitStack(S);x=c;y=k;P

11、ush(S,x);Push(S,a);Push(S,y);Pop(S,x);Push(S,t);Push(S,x);Pop(S,x);Push(S,s);While(!StackEmpty(S)Pop(S,y);printf(y);printf(x);二写出下列程序段的输出结果:voidmain()QueueQ;InitQueue(Q);charx=e,y=c;EnQueue(Q,h);EnQueue(Q,r);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,a);While(!QueueEmpty(Q)DeQueue

12、(Q,y);printf(y);printf(x);3、 假设称正读和反读都相同的字符序列为回文”，例如，“abbaf口“abcba是回文，“abcde"，“abababW不是回文。试写一个算法判别读入的一个以旗结束符的字符序列是否是“回文”。4、 选择题一、单选题1 .对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序2 .在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）Atop不变Btop=0Ctop-Dtop+3 .若一个栈的输入序列为1,2,3，,n,输出序列的第一个元素是i,则

13、第j个输出元素是（）。A.i-j-1B.i-jC.j-i+1D.不确定的4 .某堆栈的输入序列为a,b,c,d,下面的四个序列中，不可能是它的输出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b6. 用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改7 .假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A（rear-front+m）%mBrear-front+1C（front-rear+m）%mD（rear-front）%m8 .

14、栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在两端插入和删除元素D.没有共同点9 .设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少应该是（）。A6B.4C.3D.210 .若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（）A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 111 .在作进栈运算时，应先判别栈是否()，

15、在作出栈运算时应先判别栈是否()。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时应将两栈的()分别设在这片内存空间的两端,这样,当()时，才产生上溢。:A.空B.满C.上溢D.下溢:A.空B.满C.上溢D.下溢:A.n-1B.nC.n+1D.n/2:A.长度B.深度C.栈顶D.栈底:A.两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.12. 栈的输入序列为ABC，输出序列变

16、为CBA时，经过的栈操作为()A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop13. 设计一个判别表达式中左，右括号是否配对出现的算法，采用()数据结构最佳。A线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈14最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是()。A.(rear+1)MODn=frontB.rear=frontCrear+1=frontD.(rear-l)MODn=

17、front第五次作业1. 设二维数组a0-m-10i-1按行优先顺序存储在内存中，第一个元素的地址为p,每个元素占k个字节，则元素aij的地址是2. 一个广义表为(a,(a,b),d,e,(i,j),k)，则该广义表的长度为，深度为。3. 求下列广义表操作的结果：GetHead(p,h,w)=GetTail(b,k,p,h)=GetHead(a,b),(c,d)=GetTail(a,b),(c,d)=GetHead(GetTail(a,b),(c,d)=GetTail(GetHead(a,b),(c,d)=4 .按教材中图5.8所示结点结构，画出下列广义表的存储结构图(a),b),(),d),

18、(e,f)5 .已知一个6行5列的稀疏矩阵中非零元的值分别为：-90,41,-76,28,-54,65,-8,它们在矩阵中的列号依次为：1,4,5,1,2,4,5。当以带行表的三元组表作存储结构时，其行表中的值依次为1,1,3,3,4,6(行列号均从1开始)，写出该稀疏矩阵。第六次作业1 .试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2 .(1)假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA,请画出该二叉树。(2)已知一个二叉树的先序序列为ABDEGCF,中序序列为DBGEACF,画出该二叉树。3 .对下图所示二叉树进行先序线索化，为每个空指

19、针建立相应的前驱或后继线索。4 .给出下图所示的森林的先序遍历结点序列、中序遍历结点序列，然后画出该森林对应的二叉树。AG：KLBCHI；M5 .假设用于通信白产吵、8个字母组成，六R在电文中出现的峥河0.07,0.19,0.02,0.06,0xD2皿3221,0.10。iJk8个字母设计哈娅)编码。(O6 .对下图所示二叉树写出先序遍历序列、中序遍历序列、后序遍历序歹U.八单选题1 .在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A.4B.5C.6D.72 .假设在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子

20、结点数为（）个。A.15B.16C.17D.473 .假定一棵三叉树的结点数为50,则它的最小高度为（）。A.3B.4C.5D.64 .在一棵二叉树上第4层的结点数最多为（）。A.2B.4C.6D.85 .下面叙述正确的是（）。A.二叉树是特殊的无序树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.24B.48C.72D.537.线索二叉树是一种（）结构。A.逻辑B.逻辑和存储C.物理D.线性8.如果F是由有序树T转换用来的一义树，那么T中结点的前序就是A.中序B.前序C

21、.后序D.层次序F中结点的（）c9.已知一棵完全二叉树的结点总数为9个，则最舟-层的结点数为（A.1B.2C.3D.4）。10.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中若有左孩子，其左孩子的编号为结点（）。A.R2i+1B.R2iC.Ri/2D.R2i-1R1.n,结点Ri第七次作业1.(1)对于一个无向图(a),假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(2)对于一个有向图(b),假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索

22、遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。(1)(2)2.对下无向带权图:写出它的邻接矩阵，并按普里姆算法求其最小生成树；写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。D7=23试对下图所示的AOE网络，解答下列问题。(1) .求每个事件的最早发生时间vei和最迟发生时间vli。(2) .求每个活动的最早开始时间e(s)和最迟开始时间l(s)。(3) .指出哪些活动加速可使整个工程提前完成。a4=3a1=3=2四、单选题1 .在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s,则所有顶点的入度数之和为（）。A.sB.s

23、-1C.s+1D.n2 .在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s,则所有顶点的度数之和为（）。A.sB.s-1C.s+1D.2s3 .在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（）。A.nB.eC.n+eD.2e4 .在一个具有n个顶点的无向完全图中，所含的边数为（）。A.nB.n（n-1）C.n（n-1）/2D.n（n+1）/25 .在一个具有n个顶点的有向完全图中，所含的边数为（）。A.nB.n（n-1）C.n（n-1）/2D.n（n+1）/26 .在一个无向图中，若两顶点之间的路径长度为k,则该路径上的顶点数为（）。A.kB.k+1C.k+2D.

24、2k7 .对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（）。A.0B.1C.nD.n+18 .若要把n个顶点连接为一个连通图，则至少需要（）条边。A.nB.n+1C.n-1D.2n9 .对于一个有向图，若一个顶点的度为k1,出度为k2,则对应逆邻接表中该顶点单链表中的边结点数为（）。A.k1B.k2C.k1-k2D.k1+k210 .在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。A.出边数B.入边数C.度数D.度数减111 .已知一个有向图的边集为<a,b>,<a,c>,<a,d>,<b,d>,<b,e&

25、gt;,<d,e>,则由该图产生的一种可能的拓扑序列为（）。A.a,b,c,d,eB.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e第九次作业1 .已知一个顺序存储的有序表为（15,26,34,39,45,56,58,63,74,76）,试画出对应的折半查找判定树，求出其平均查找长度。2 .假定一个待哈希存储的线性表为（32,75,29,63,48,94,25,46,18,70）,哈希地址空间为HT13,若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。兀索初始哈希地址最终

26、哈希地址3275296348942546187001234567891011123 .假定一个线性表为(38,52,25,74,68,16),画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。4 .假定一个线性表为(38,52,25,74,68,16),画出按线性表中元素的次序生成的一棵AVL树,求出其平均查找长度。五、单选题1 .若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为()。A.nB.n+1C.(n-1)/2D.(n+1)/22 .若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d,则下一次的哈

27、希地址为()。A.dB.d+1C.(d+1)/mD.(d+1)%m3 .对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为()。A.3B.4C.5D.64 .对具有n个元素的有序表采用折半查找，则算法的时间复杂度为()。A.O(n)B.O(n2)C.O(1)D.O(log2n)5 .从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为()。A.O(n)B.O(1)C.O(log2n)D.O(n2)6 .在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是()。A.-1、1B.-22C.12D.0J第十次作业1.已知一组记录为(46,74,53,

28、14,26,38,86,65,27,34),给出采用直接插入排序法进行排序时每一趟的排序结果。2 .已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用冒泡排序法进行排序时每一趟的排序结果。3 .已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用简单选择排序法进行排序时每一趟的排序结果。4 .已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用快速排序法进行排序时每一趟的排序结果。5 .已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用2-路归并排序法进行

29、排序时每一趟的排序结果。、单选题1 .若又n个元素进行直接插入排序，在进彳T第i趟排序时，假定元素ri+1的插入位置为rj,则需要移动元素的次数为()。A.j-iB.i-j-1C.i-jD.i-j+12 .在n个元素进行简单选择排序的过程中，需要进行()趟选择和交换。A.nB.n+1C.n-1D.n/23 .在n个元素进行直接插入排序的过程中，共需要进行()趟。A. nB. n+1C. n-1D. 2n4 .对n个元素进行直接插入排序时间复杂度为()。A.O(1)B.O(n)C.O(n2)D.O(log2n)5 .在n个元素进行冒泡排序的过程中，第一趟排序需要进行()对相邻元素之间的交换。A.

30、 nB. n-1C. n+1D. n/26 .在n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为()。A.0(1)B.O(log2n)C.O(n2)D.O(n)7.在n个元素进行冒泡排序的过程中，至少需要()趟完成。A. 1B. n8.下列序列中，构成小根堆的是(A. (1, 2, 5, 3, 4, 6, 7, 8, 9, 10)C. (10, 9, 8, 7, 3, 5, 4, 6, 2)C. n-1D. n/2)B. (10, 5, 8, 4, 2, 6, 7, 1, 3)D. (1, 2, 3, 4, 10, 9, 8, 7, 6, 5)9 .假定对元素序列(7,3,5,9,1,1

31、2)进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为()。A.1,3,5,7,9,12B.1,3,5,9,7,12C.1,5,3,7,9,12D.1,5,3,9,12,710 .假定对元素序列(7,3,5,9,1,12,8,15)进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为()。A.2B.3C.4D.511 .()是稳定的排序方法。A.起泡排序B.快速排序C.堆排序D.希尔排序3 .4 .先根序歹U:ABCDEFGHIJKLMNO后根序歹U:BDEFCAHJIGKNOML5.8个字母的哈夫曼编码依次为:0.07:10100.19:000.02:100000.06:1001

32、0.32:110.03:100010.21:010.1:10116.先序序歹U:ABDCEGF中序序列：DBAEGCF后序序歹U:DBGEFCA单选题：CBCDDDCBBB第七次1,(1)DFS:0128345679BFS:0142738659(2)DFS:047583612BFS:0431756282(1)000000GO90000GO00ao85765400300003oo2oooo2oo6800600-co43oo485535oo5oo55aooo9oo700ooco60000005_GO0054012345673.事件AB:CDEF最早发生时间vei032668最迟发生时间vli042678活动ala2a3a4a5a6a7a8最早开始时间ee(i)0033226n6最迟开始时间el(i)10442567关键活动为a2a5a7,加速这些关键活动可使整个工程提前完成。四、单选题ADDCBBBCCAA第九次和第十次1.ASL=2.92.哈希函数H(key)=key%13初始哈希地址最终哈希地址013275296348942546187010311931275510311941275866哈希表平均查找长度：14/10=1.42994183246704875632523456789101112哈希函数H(key)=key%11初始哈希地址最终哈希地址013275296348