数据结构练习题--2011级--参考答案

1、选择题：1.1 数据结构在计算机内存中的表示是指：A 数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系1.2 数据的逻辑结构是指：A. 数据所占的存储空间量B 各数据元素之间的逻辑关系C. 数据在计算机中顺序或链接的存储方式D. 存储在内存或外存中的数据1.3 在下列的叙述中，正确的是：A 数据的逻辑结构是指数据的各数据项之间的逻辑关系。B 数据的物理结构是指数据在计算机内的实际存储形式。C 在顺序存储结构中，数据元素之间的关系是显示体现的。D 链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系填空题:1.4数据结构主要研究数据的逻辑结构，数据的存储结构一 ，数据的

2、运算三个方面的内容。1.5链接存储的特点是通过附加指针域来表示数据元素之间的逻辑关系。1.6数据结构中讨论的三种经典结构包括：线性表，树，图。1.7数据结构中常用的存储方法有:顺序， 链接，索引，散列。1.8顺序存储结构可以通过位置隐含表示关系，链接存储结构通过附加指针来显示表示关系。1.9算法的特性包括有穷性，确定性， 可行性，输入和输岀。1.10算法性能分析的两个主要定量评价指标是时间复杂度和空间复杂度 。简答题：1.11数据结构研究的三方面内容之间有什么联系和区别？数据结构研究的三方面内容包括 ：数据的逻辑结构、存储结构和运算。数据的逻辑结构 是数学模型，存储结构是指逻辑结构到存储区域的

3、映射，运算是定义在逻辑结构上， 实现在存储结构上。1.12简述数据结构中讨论的三种经典结构的逻辑特征是什么？三种经典结构：线性表、树和图。逻辑特征分别为：(1) 线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有 且仅有一个前趋结点和一个后继结点。(2) 树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都 有且仅有一个前趋结点，可以有若干个后继结点。(3) 图：多对多。可有若干个开始结点和终端结点，其余的内部结点可以有若干个前 趋结点和若干个后继结点。1.13简述各种常用存储方法的基本思想。各种方法的基本思想：顺序存储：逻辑上相邻的数据元素存储在物理位置

4、上相邻的存储单元里。链接存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。 散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字-地址转换法。选择题:2.1 线性表L= (ai, a2,，an),下列说法正确的是:A. 每个元素都有一个直接前驱和一个直接后继。B. 线性表中至少有一个元素。C. 表中元素的排列顺序必须是由小到大或由大到小。D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。2.2 下面关于线性表的叙述中，错误的是:A 线性表若采用顺序存储，必须占用一片连续的存储单元B. 线性

5、表若采用顺序存储，便于进行插入和删除操作C. 线性表若采用链接存储，不必占用一片连续的存储单元D. 线性表若采用链接存储，便于插入和删除操作2.3 在长度为n的顺序表的第i(1 i n+1)个位置上插入一个元素，元素的移动次数为:A .n-i+1B .n-iC .iD .i-12.4 删除长度为n的顺序表中的第i(1 inext=L;C. s=L; s-next=L;L，在表头元素前插入新结点*s的语句为:B. s-next=L-next; L-next=s;D. s-next=L; s=L;2.6 已知一个不带头结点单链表的头指针为L,则在表头元素之前插入一个新结点*s的语句为:A. L=s

6、; s-next=L;B. s-next=L; L=s;C. s=L; s-next=L;D. s-next=L; s=L;2.7 已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为:A p-next=s; s-next=p-next;B. s-next=p-next; p-next=s;C. p-next=s; p-next=s-next;D. p-next=s-next; p-next=s;2.8 已知单链表上一结点的指针为p,则删除该结点后继的正确操作语句是：A. s= p-next; p=p-next; free(s);B.p=p-next;free(p);C.

7、s= p-next; p-next=s-next; free(s);D.p=p-next; free(p-next);2.9 设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构效率最高?A.单链表 B.双链表 C.单循环链表D.带尾指针的单循环链表2.10线性表的链接存储结构是一种(A.随机存取B.顺序存取2.11链表不具备的特点是：A.插入删除不需要移动元素C.可随机访问任一结点)存储结构。C.索引存取D.散列存取B.不必事先估计存储空间D. 所需空间与其长度成正比填空题:2.1在单链表L中，指针p所指结点有后继结点的条件是 _p-next!=NULL_。2.2判

8、断带头结点的单链表 L为空的条件 L-next=NULL。2.12顺序表和链表中能实现随机存取的是顺序表!，插入、删除操作效率高的是链表2.13对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为O (1).；若已知一个结点的值为 x,在其后插入一个新结点的时间复杂度为O (n)。2.14顺序表的存储密度_，链表的存储密度.小简答题：2.15比较顺序表和链表这两种线性表不同存储结构的特点顺序表存储密度大存储空间连续静态分配随机存取插、删效率低链表存储密度大存储空间可不连续动态分配顺序存取插、删效率高2.16简述头结点的作用。头结点的作用是使得单链表在表头位置的

9、插、删操作同中间位置的插、删操作完全相 同。即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操 作完全一致，无须特殊处理。2.17写岀单链表存储结构的 C语言描述。typedef int DataType;typedef struct Node DataType data; struct Node *n ext;Lin kList;完善程序题：2.18设计一个算法，其功能为：向一个带头结点的有序单链表(从小到大有序)中插入一个元素X,使插入后链表仍然有序。请将代码补充完整。typedef int DataType;typedef struct Node DataType d

10、ata;/*定义指向该结构类型的指针变量next*/Linklist;void insert(Linklist *L,DataType x) Linklist *s,*p=L;while(p-next & p-next-datadata=x;/*将*s结点插入到*p结点的后面*/struct Node * n ext;p=p-n ext:s=(L in kList *)malloc(sizeof(L in kList):s-n ext=p-n ext:p-n ext=s:2.19设计一个函数功能为：在带头结点的单链表中删除值最小的元素。请将代码补充完整。typedef int DataType

11、;typedef Node/*定义结构体类型*/ DataType data;struct Node * next;LinkList;void deleteMin(LinkList *L) LinkList *p=L-next,*q;/*首先查找值最小的元素，指针q指向最小元素结点*/q=p;while(p) if( p-data data)q=p;/* p指针后移一步，比较单链表中的每一个结点*/if(!q) return;/*不存在最小结点(空表)时，直接退出 */p=L;/*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/while()p=p-next;/*从单链表中删除最小元素

12、结点(指针q所指结点)*/;/*释放指针q所指结点的空间*/structp=p-n ext:pn ext!=qpn ext=q n ext;free(q):算法设计题：2.20已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：(1)线性表采用顺序存储；(2)线性表采用单链表存储。(1) 线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataTyp

13、e item) int i,j=0;for(i=0;ilast :i+)if( L-datai item )j+;return j;(2) 线性表采用单链表存储typedef int DataType;typedef struct Node DataType data;struct Node *n ext;Lin kList;in t locateElem(Li nkList *L, DataType item )Li nkList *p=L- next;int i=0;while ( p )if( p-data item) i+; return i ;2.21试写一算法实现对不带头结点的单链

14、表H进行就地(不额外增加空间)逆置typedef int DataType; typedef struct Node DataType data; struct Node *n ext;Lin kList;Lin kList * Reverse(Li nkList * L) Lin kList *p,*q;if (!L) return;p=H-n ext;q=H-n ext;L-n ext=NULL;while(q)q=q_n ext;p_n ext= L;L=p; p=q;return L;选择题：3.1 设一个栈的输入序列是 1，2，3，4, 5,则下列序列中，是栈的合法输岀序列的是:A.

15、 5 1 2 3 4B. 4 5 1 3 2C. 4 3 2 1 5D. 3 5 2 4 13.2 设有一顺序栈，元素1, 2, 3, 4, 5依次进栈，如果出栈顺序是2, 4, 3, 5, 1则栈的容量至少是：A .1B. 2C. 3D. 43.3 若用一个大小为6的数组来实现循环队列，且当前 rear和front的值分别为0和3,当入队一个元素， 再出队两个元素后，rear和front的值分别为：A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 1填空题：3.4 栈和队列都是操作受限的线性表，栈的运算特点是LIFO _，队列的运算特点是FIFO3.5 若序列a、b、c、d、e按

16、顺序入栈，假设P表示入栈操作，S表示出栈操作，则操作序列PSPPSPSPSS 后得到的输出序列为 acdeb。3.6 已知一个顺序栈*s，栈顶指针是top，它的容量为MAXSIZE，则判断栈空的条件为s-top=-1 ,栈满的条件是s-top=MAXSIZE-1 。3.7 对于队列来说，允许进行删除的一端称为队头| ，允许进行插入的一端称为队尾 。3.8 某循环队列的容量 MAXSIZE =6,队头指针front=3，队尾指针rear=0,则该队列有 3_个元素。简答题：3.9 栈上的基本运算有哪些？栈的基本运算有：(1) 初始化栈initStack (s):构造了一个空栈 s。(2) 判栈空

17、empty (s)：若栈s为空栈，返回值为“真”(1),否则返回值为“假”(0 )。(3) 入栈push (s, x):在栈s的顶部插入一个新元素 x, x成为新的栈顶元素。(4) 出栈pop (s):删除栈s的栈顶元素。(5) 读栈顶元素top( s)：栈顶元素作为结果返回，不改变栈的状态。3.10循环顺序队列的存储结构图示及C语言描述?循环顺序队列图示:frontC语言描述：#define MAXSIZE 1024typedef int DataType;typedef struct DataType dataMAXSIZE; int rear , front;SeQueue;SeQueu

18、e *sq;3.11简述栈和队列有哪些联系与区别？栈和队列都是运算运算受限的线性表，逻辑结构相同；都可以顺序存储和链接存储， 存储结构也相同；插入和删除运算都限制在线性表的表端完成，且不需要查找运算。 二者差别主要体现在运算的限制不同：栈是后进先出( LIFO )的线性表，限制它的 插入和删除操作仅在表的一端进行。队列是先进先出(FIFO )的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。算法设计题：3.12通常称正读和反读都相同的字符序列为回文”例如，“abcdeedcba “abcdcba是回文。若字符序列存储在一个单链表中，编写算法判断此字符序列是否为回文。(提示：将一半字符

19、先依次进栈)#defi ne maxsize 100typedef char datatype1;typedef struct datatype1 datamaxsize;int top; seqstack;typedef int datatype;typedef struct node datatype data;struct node *n ext; Lin klist;Duiche n(Li nklist *head) int i=1;Li nklist *p;seqstack *s;s=i nitSeqStack();p= head-n ext ;n=0;while(p) n+; p=

20、p-n ext;p=head-n ext;while(idata); i+;if (n %2!=0)p=p- next;while(p&p-data=pop(s) p=p-n ext;if (p) return 0 else return 1; 选择题：5.1 设数据结构D-S可以用二元组表示为 D-S=(D , S),疋S,其中:D=A，B，C，D，r=A，B，A，C，B，D，则数据结构 D-S 是：A .线性结构 B.树形结构C .5.2 树最适合用来表示：A.有序数据元素C.元素之间具有分支层次关系的数据5.3 有关二叉树下列说法正确的是：A 二叉树是度为2的有序树C. 二叉树中至少有一

21、个结点的度为2图形结构 D 集合B.无序数据元素D.元素之间无联系的数据B 二叉树中结点的度可以小于 2D .二叉树中任何一个结点的度都为25.4 深度为10的完全二叉树，第3层上的的结点数是：A .15 B .16 C . 4 D .325.5 设一棵树的度为4,其中度为1、2、3、4的结点个数分别为6、3、2、1，则这棵树中叶子结点的个 数为：A .8B. 9C. 10D. 115.6 对于二叉树来说，第i层上最多包含的结点个数为：A. 2- 1B. 21 + 1C. 2D.2i5.7 树的后根遍历序列等同于与该树对应的二叉树的哪种序列？A.前序序列B.中序序列 C.后序序列D.层序序列5

22、.8 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是：A . M1B . M1+M2C. M3D . M2+M 3填空题：5.9 二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 11。5.10包含n个结点的二叉树，高度最大为n，高度最小为log2 n 1。5.11某完全二叉树共有200个结点，则该二叉树中有1个度为1的结点。5.12 一棵高度为10的满二叉树中的结点总数为 _210-1个，其中叶子结点数为 _29 。5.13某完全二叉树结点按层顺序编号(根结点的编号是1)，若21号结点有左孩子结点

23、，则它的左孩子结点的编号为_42_o5.14深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点。5.15 n个结点的线索二叉树上含有n+1 条线索。简答题：5.16画出包含三个结点的树和二叉树的所有不同形态。5.17找出满足下面条件的二叉树：(1) 前序遍历与中序遍历结果相同：只有右分支的单分支二叉树(2) 前序遍历和后序遍历结果相同：只有一个根结点的二叉树(3) 中序遍历和后序遍历结果相同：只有左分支的单分支二叉树5.18 一棵二叉树的中序、后序遍历序列分别为：G L D H B E I A C J F K 和L G H D I E B J K F C A，请回答：(1) 画岀二

24、叉树逻辑结构的图示。(2) 画岀此二叉树的二叉链表存储结构的图示并给岀C语言描述。(3) 画岀上题中二叉树的中序线索二叉树。(4) 画岀中序线索二叉链表存储结构图示并给岀C语言描述。(1) 二叉树的逻辑结构图示：roo31厶FAJAa KAAGAHAAIALA(2) 二叉链表存储结构的图示及 C语言描述:typedef char DataType; typedef struct Node DataType data;struct Node *lchild,*rchild; BiTree;(3) 中序线索二叉树:NULLft-(4) 中序线索二叉链表的图示及 C语言描述:typedef char

25、 DataType; typedef struct Node DataType data;struct Node *lchild,*rchild;int ltag,rtag;BiThrTree;5.19设有森林如图5.31所示，请回答:(1) 画岀与该森林对应的二叉树的逻辑结构图示(2) 写岀该二叉树的前序、中序、后序遍历序列(3)画岀该二叉树的中序线索二叉链表的图示并给岀C语言描述。CE图 5.31(1) 二叉树的逻辑结构图示:(2)前序遍历序列：ABCDFGEH ,中序遍历序列：ADGFCBHE后序遍历序列：GFDCHEBA(3) 中序线索二叉链表的图示及 C语言描述:A1A01G10 I

26、 B 0typedef char DataType; typedef struct Node DataType data;struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;5.20设有森林B=(D,S),D=A,B,C,D,E,F,G ,H,I,J, r S r=vA,B,vA,C,vB,E,vC,F,vG,H,请回答:(1) 画岀与森林对应的二叉树的逻辑结构图示。(2) 写岀此二叉树的前序、中序、后序遍历序列(3) 画岀此二叉树的二叉链表存储结构的图示并给岀C语言描述。(1) 与森林对应的二叉树的逻辑结构图示：(2)前序遍历序列：ABE

27、CFDGHIJ ,(3)二叉链表存储结构的图示及C语言描述:roottypedef char DataType;typedef struct Node DataType data;struct Node *lchild,*rchild;BiTree;5.21请画出5.32中的各二叉树对应的森林。(a)B(d)(b)(c)中序遍历序列：EBFCDAHJIG 后序遍历序列：EFDCBJIHGA图 5.32(d )(b )(c)(1) 画岀哈夫曼树(按根点权值左小右大的原则)。(2) 写岀依此哈夫曼树对各个字母的哈夫曼编码。(3) 求出此哈夫曼树的带权路径长度WPL。(1)哈夫曼树：2)各字母的哈夫

28、曼编码:a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:1011(3)哈夫曼树的带权路径长度WPL :406011932g 001111710WPLWilii 15.22假设用于通信的电文由字符集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，试为这8个字母进行哈夫曼编码。请 回答：=0.07 4+0.19 2+0.02 3+0.06 +0.32 2+0.03 爲+0.21 2+0.10 rchild;/* 若结点 *

29、p 无右孩子 */else/*若结点*p有右孩子*/while(p-ltag=0)return *rchild p_rtag=1 p=p-rchild选择题:6.1 n个顶点的有向图中有向边的数目最多为:A.n-1B. nC.n(n-1)/26.2 下面哪一方法可以判断出一个有向图是否有环(回路)A 深度优先遍历B.求最短路径C.拓扑排序填空题：某无向图的邻接矩阵如下所示，则该图中有D .n(n-1)D.广度优先遍历6.39条边，有6个顶点。6.46.5A=0101011 01011010001100011010100111100在无向图的邻接矩阵存储结构中，第i列上非零元素的个数是顶点Vi的

30、矩阵中，第i列上非零元素的个数是顶点 Vi的 入度 。度.，而在有向图的邻接顶点一的个数有关。6.6简答题:若无向图采用邻接矩阵存储，则存储空间的大小只与图中对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为n 和 n-1 。6.7 设一个有向图为 G=(V,E)，其中 V= V 1,V2,v3,V4， 答下列各问：画岀该有向图，求岀每个顶点的入度和岀度。 画岀该图的邻接矩阵存储结构图示。对(2)中的邻接矩阵，给岀从顶点对(2)中的邻接矩阵，给岀从顶点E=,V V4,V1,，请回(1)(2)(3)(4)V2出发的V2出发的DFS序列和BFS序列和DFS生成树。BFS生成树。(

31、1)有向图：顶点V1的入度是顶点V2的入度是顶点V3的入度是顶点V4的入度是出度是 出度是 出度是 出度是1；2；0；2。(2)邻接矩阵存储结构图示:数组r10V1V2V3V4(3) DFS 序列:生成树：V2, V1,V4,V3(4) BFS 序列： V2, V1,V3,V4生成树：J*-V1126.8 对图6.44所示的无向图，依次输入各边：（V1,V2）、 （V1,V4）、（V2,V3）、（V3,V4）、（V3,V5），请回答下列各问:（1）写出该无向图的二元组表示。（2）画岀该图的邻接表（头插法建表）存储结构图示。（3） 对（2）中的邻接表，给出从顶点V1出发的DFS序列和DFS生成树

32、。（4） 对（2）中的邻接表，给出从顶点Vi出发的BFS序列和BFS生成树。（1 ）无向图的二元组表示：设G=（V, E） , V为顶点集，E为边集，则V= Vi, V2, V3, V4, V5E=（V1,V2）、 （V1,V4）、 （V2,V3）、（V3,V4）、（V3,V5）（2）图的邻接表（头插法建表）存储结构图示：Vertex link2A（3）从顶点V1出发：DFS 序列：V1,V4,V3,V5,V2（4）从顶点V1出发：BFS 序列：V1 ,V4,V2,V3,V5画出图6.45中所有可能的最小生成树。图 6.446.1图6.45的所有可能的最小生成树:2选择题:7.1 在对n个元素

33、进行起泡排序的过程中，最好情况下的时间复杂度为：A . 0(n3)B.0(n2)C.0(n)D. 0(1)7.2 堆排序属于下列哪类排序？A.插入B.交换C.归并D.选择7.3 下列哪组序列是堆：A . (79,40,46,56,38,84)B. (84,56,79,46,38,40)C. (40,38,46,56,79,84)D. (84,38,46,40,56,79)7.4 下列排序算法中，哪种排序方法在一趟结束后不一定能选岀一个元素放在其最终位置上。A. 简单选择排序B.冒泡排序 C.归并排序D.堆排序7.5 就平均性能而言，目前最好的内排序方法是:A.冒泡B.希尔插入7.6 在下面的排

34、序方法中，平均时间复杂度为A.快速排序B.直接插入排序填空题：C.交换D.快速O(n2)且是不稳定的排序方法为：C.直接选择排序D.起泡排序7.7 每次从无序子表中取岀一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做插入排序。7.8 快速排序的平均时间复杂度是 0 ( nloggn)，平均空间复杂度是 0 (log?n),。7.9 设记录的排序码序列为：(49, 38, 65，97，76，13, 27)，若采用快速排序，则第一趟划分的结果为27,38,134976,97,65。7.10快速排序、堆排序和归并排序的平均时间复杂度都是0( nloggn)，但其中稳定的排序方法只有归并塁_

35、next; L-next=NULL;while(p) q=L;while(q-next & )/*指针q从头开始查找，寻找合适的插入位置*/s=p-next;J/*将指针p所指的结点插入到 q之后*/p=s;struct node *n ext;q-n ext-datadataq=q-n ext:pn ext=q n ext;qn ext=p;选择题：8.1 对线性表进行二分查找时，要求线性表必须：A 以顺序方式存储B 以顺序方式存储，且按关键字有序C.以链接方式存储D.以链接方式存储，且按关键字有序8.2 顺序查找法适合于存储结构为（）的线性表。A 散列存储B.顺序存储或链接存储C.压缩存储

36、D.索引存储8.3 若结点的存储地址与其关键字之间存在某种函数关系，则称这种存储结构为：A. 顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构8.4 下面关于散列查找的说法正确的是：A 在采用线性探测法处理冲突的散列表中，同义词在表中一定相邻；B. 除留余数法是所有散列函数中最好的；C. 在散列表中进行查找，“比较”次数的多少与冲突有关；D. 散列函数构造的越复杂越好，因为这样随机性好，冲突小。填空题：8.5 对于n个元素的顺序表采用顺序查找，且使用监视哨。若查找成功，则比较关键字的次数最多为_n 次；若查找失败，则比较关键字的次数最少为n+ 1。8.6 在有序表（9,10,14,18,23,27,30,32,42）中，用二分法查找关键字值32 （成功），需做的关键字比较次数为 3 ;查找关键字值35 （失败），需做的关键字比较次数为_4 。8.7 具有8个关键字的有序表，二