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

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

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

4、机内部数据处理的基本单位是（ ）。A.数据 B.数据元素C.数据项D.数据库二、填空题1.下面程序段的时间复杂度是_。 for (I=1; I<n; I+)for (j=1; j<n; j+) x+;for (k=1; k<n;k+) x+;2下面程序段的时间复杂度是_。 s0； for（i=0；i<n；i+） for（j=0; j<n; j+） s+=bij； sum=s; 3. 数据结构按逻辑结构可分为两大类，分别是_和_。4. 一个算法的效率可分为_效率和_效率。5. 设n为正整数。下列程序段中前置以记号的语句的频度为_。i=1;k=0;while(i<

5、;=n-1) k+=10*i; i+; 6算法时间复杂度的分析通常有两种方法，即_和_的方法，通常我们对算法求时间复杂度时，采用后一种方法。第二次作业1. 对以下单链表分别执行下列各程序段，画出结果示意图。25 6 7 3LPR(1) Q=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. 简述以下算法的功能。Status A

6、(LinkList L) /L是无表头结点的单链表 if(L&&L->next) Q=L; L=L->next; P=L; while(P->next) P=P->next; P->next=Q; Q->next=NULL;return OK;/A3. 写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,x)。（求x在单链表L中的位序）4. 写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。（求单链表L中的元素个数）5. 选择题 （1） 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）Ahe

7、ad=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL（2）完成在双循环链表结点p之后插入s的操作是（ ）A p->next=s ; s->prior=p; p->next->prior:=s ; s->next=p->next;B p->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-&g

8、t;prior=s ;Ds->prior=p; s->next:=p->next; p->next->prior=s ; p->next=s;（3）线性表是具有n个（ ）的有限序列。 A表元素 B字符 C数据元素 D数据项 （4）下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。（5）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式

9、最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表（6）线性表是_。A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空（7）链表不具有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比（8）. 在_运算中，使用顺序表比链表好。  A插入   B删除  C根据序号查找   D根据元素值查找（9）. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行As->next=p->next;

10、p->next=sBq->next=s; s->next=pCp->next=s->next; s->next=pDp->next=s; s->next=q（10）. 在顺序表中，只要知道_，就可在相同时间内求出任一结点的存储地址。A基地址B结点大小 C向量大小 D基地址和结点大小（11）. 以下关于线性表的说法不正确的是_。  A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数是任意的。C线性表中的每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。（12）

11、.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_个元素结点。An/2 BnC（n+1）/2D（n-1）/2第三次作业一 写出下列程序段的输出结果:void main()Stack S;char x,y;InitStack(S);x=c;y=k;Push(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);二 写出下列程序段的输出结果:void main()Que

12、ue Q; InitQueue(Q);char x=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(Q,y); printf(y);printf(x); 三、 假设称正读和反读都相同的字符序列为“回文”，例如，“abba”和“abcba”是回文，“ abcde” ，“ababab”则不是回文。试写一个算法判别读入的一个以 为结束符的字符序列是否是“回文”。四、 选择题一、单选题1. 对于

13、栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ ）Atop不变 Btop=0 Ctop- Dtop+ 3. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的4. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。A. a，c，b，d B. b, c，d，a C. c, d，b, a D.

14、d, c，a，b6. 用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改7. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m8. 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在两端插入和删除元素 D. 没有共同点9. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依

15、次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A 6 B. 4 C. 3 D. 210. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 11. 在作进栈运算时,应先判别栈是否( ),在作出栈运算时应先判别栈是否( )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共

16、享一片连续的内存空间时,应将两栈的 ( )分别设在这片内存空间的两端,这样,当( )时，才产生上溢。 : A. 空 B. 满 C. 上溢 D. 下溢 : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 长度 B. 深度 C. 栈顶 D. 栈底 : A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.12. 栈的输入序列为ABC，输出序列变为CBA时，经过的栈操作为（ ）A. push,pop,push,

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

18、第五次作业1. 设二维数组a0m-10n-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)

19、, b), ( ), d), (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. 对下图

20、所示二叉树进行先序线索化，为每个空指针建立相应的前驱或后继线索。ADBFCGEH4. 给出下图所示的森林的先序遍历结点序列、中序遍历结点序列，然后画出该森林对应的二叉树。ABDEFCGHJIKNOML5. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。6. 对下图所示二叉树写出先序遍历序列、中序遍历序列、后序遍历序列. 八 单选题1. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。A. 4B. 5C

21、. 6D. 72. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ ）个。A. 15B. 16C. 17D. 473. 假定一棵三叉树的结点数为50，则它的最小高度为（ ）。A. 3 B. 4C. 5D. 64. 在一棵二叉树上第4层的结点数最多为（ ）。A. 2B. 4 C. 6D. 85. 下面叙述正确的是（ ）。A. 二叉树是特殊的无序树B. 二叉树等价于度为2的树C. 完全二叉树必为满二叉树D. 二叉树的左右子树有次序之分6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。A. 24B. 48C. 72D. 537.

22、 线索二叉树是一种（ ）结构。A. 逻辑 B. 逻辑和存储C. 物理 D. 线性8. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ ）。A. 中序B. 前序C. 后序D. 层次序9. 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（ ）。A. 1 B. 2C. 3D. 410.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R1.n，结点Ri若有左孩子，其左孩子的编号为结点（ ）。A. R2i+1B. R2iC. Ri/2D. R2i-1第七次作业1. （1）对于一个无向图(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶

23、点序列和按广度优先搜索遍历得到的顶点序列。（2）对于一个有向图(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。0165948372(a)603451278(b)2. 对下无向带权图：（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。abdhcefg435555973656243 试对下图所示的AOE网络，解答下列问题。(1)求每个事件的最

24、早发生时间ve i和最迟发生时间vli。(2)求每个活动的最早开始时间e(s)和最迟开始时间l(s)。(3)指出哪些活动加速可使整个工程提前完成。四、单选题1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为()。A. sB. s-1C. s+1D. n 2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为()。A. s B. s-1C. s+1D. 2s 3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为()。A. n B. eC. n+eD. 2e 4. 在一个具有n个顶点的无向完全图中，所含的边数

25、为()。A. nB. n(n-1)C. n(n-1)/2D. n(n+1)/2 5. 在一个具有n个顶点的有向完全图中，所含的边数为( )。A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。A. k B. k+1 C. k+2 D. 2k7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。A. 0 B. 1 C. n D. n+18. 若要把n个顶点连接为一个连通图，则至少需要( )条边。A. n B. n+1 C. n-1 D. 2n9. 对于一个有向图，若一个顶点的

26、度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为( )。A. k1 B. k2 C. k1-k2 D. k1+k210. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。A. 出边数 B. 入边数 C. 度数 D. 度数减111. 已知一个有向图的边集为<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>，则由该图产生的一种可能的拓扑序列为( )。A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e第九次作业1. 已知

27、一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。2. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为HT13，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 最终哈希地址 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 3. 假定一个线性表为(38,52,2

28、5,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，则下一次的哈希地址为()。A. d B. d+1 C. (d+1)/m D. (d+1)%m3. 对于长度为18的顺序存储

29、的有序表，若采用折半查找，则查找第15个元素的比较次数为()。A. 3 B. 4 C. 5 D. 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. -11 B. -22 C. 12 D. 01第十次作业1. 已知一组记录为(46,74,53,14,26,38,86,65,27,34

30、)，给出采用直接插入排序法进行排序时每一趟的排序结果。 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-路归并排序法进行排序时每一趟的排序结果。、单选题1.

31、 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素ri+1的插入位置为rj，则需要移动元素的次数为（ ）。A. j-i B. i-j-1 C. i-j D. i-j+1 2. 在对n个元素进行简单选择排序的过程中，需要进行（ ）趟选择和交换。 A. n B. n+1 C. n-1 D. n/2 3. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。A. n B. n+1 C. n-1 D. 2n 4. 对n个元素进行直接插入排序时间复杂度为（ ）。A. O(1) B. O(n) C. O(n2) D. O(log2n) 5. 在对n个元素进行冒泡排序的过程中，第一趟排序需要

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

33、, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（ ）。 A. 1, 3, 5, 7, 9, 12 B. 1, 3, 5, 9, 7, 12 C. 1, 5, 3, 7, 9, 12 D. 1, 5, 3, 9, 12, 710.假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）。 A. 2 B. 3 C. 4 D. 511. （ ）是稳定的排序方法。A起泡排序 B快速排序 C堆排序 D希尔排序答案第六次12. 3.4.先根序列：ABCDEFGHIJKLMNO后根序列: BDEFCAH

34、JIGKNOML5.8个字母的哈夫曼编码依次为：0.07: 10100.19： 000.02： 100000.06： 10010.32： 11 0.03： 100010.21： 010.1： 10116.先序序列：ABDCEGF 中序序列：DBAEGCF后序序列：DBGEFCA单选题：CBCDD DCBBB第七次1， (1) DFS： 0 1 2 8 3 4 5 6 7 9 BFS: 0 1 4 2 7 3 8 6 5 9(2) DFS：0 4 7 5 8 3 6 1 2BFS:0 4 3 1 7 5 6 2 82(1)(2) 3.事件ABCDEF最早发生时间vei032668最迟发生时间vl

35、i042678活动a1a2a3a4a5a6a7a8最早开始时间ee(i)00332266最迟开始时间el(i) 10442567关键活动为a2 a5 a7,加速这些关键活动可使整个工程提前完成。四、单选题ADDCB BBCCA A第九次和第十次1.ASL=2.92.哈希函数 H（key）=key%13 32 75 29 63 48 94 25 46 18 70 初始哈希地址 6 10 3 11 9 3 12 7 5 5最终哈希地址 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 48 75 63

36、 25平均查找长度： 14/10=1.4哈希函数 H（key）=key%11 32 75 29 63 48 94 25 46 18 70 初始哈希地址 10 9 7 8 4 6 3 2 7 4最终哈希地址 10 9 7 8 4 6 3 2 11 5 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 46 25 48 70 94 29 63 75 32 18 平均查找长度：15 /10=1.53.ASL=2.54. ASL=7/3单选题：DDBDA A第10章 答案1. 直接插入排序 46 74 53 14 26 38 86 65 27 34 第1趟 46 74 53 14 26 38 86 65 27 34 第2趟 46 53 74 14 26 38 86 65 27 34 第3趟 14 46 53 74 26