（完整版）数据结构与算法试题

1、本word文档可编辑可修改 一、选择题1.在逻辑上可以把数据结构分成（A）A.线性结构和非线性结构C.紧凑结构和非紧凑结构B.D.动态结构和静态结构内部结构和外部结构C2.单链表中各结点之间 的地址（）A.必须连续B.部分必须连续C.不一定连续D.以上均不对3.在一个长度为 n 的顺序表中向第 i个元素（ 0ifront=L C.P=NULL D.P-rear=L12.已知 P为单链表中 的非首尾结点，删除P结点 的后继结点 Q 的语句为（A）。A.P-NEXT=Q-NEXT;FREE(Q);C.Q-NEXT=P-NEXT;FREE(Q);B.Q-NEXT=P; FREE(Q);D.P-NEX

2、T=S;S-NEXT=P;13.循环队列 SQ队满 的条件是（B）。第 1页共 16页1 A.SQ-rear=SQ-front B. (SQ-rear+1)%MAXLEN=SQ-frontC.SQ-rear=0 D. SQ-front=014.一组记录 的排序码为（ 46， 79，56，38， 40，84），则利用堆排序 的方法建立 的初始堆B为( )。A、 79，46，56， 38，40，80B、 84，79，56， 38，40，46C、 84，79，56， 46，40，38D、 84，56，79， 40，46，3815.排序趟数与序列原始状态 (原始排列 )有关 的排序方法是（ACD）方法

3、。A、插入排序C、冒泡排序B、选择排序D、快速排序B16.下列排序方法中，（）是稳定 的排序方法。A、直接选择排序C、希尔排序B、二分法插入排序D、快速排序17.数据序列（ 8，9，10，4，5，6，20，1， 2）只能是下列排序算法中(C) 的两趟排序后 的结果。A、选择排序C、插入排序BD、冒泡排序、堆排序18.对序列 (15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据 的排列变为（4，9，-1，8，20，7，15），则采用 的是（C）排序。A、选择C、希尔BD、快速、冒泡19.一组待排序记录 的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为

4、基准元素得到 的一次划分结果为（C）。A(38,40,46,56,79,84)C、 (40,38,46,56,79,84)D、 (40,38,46,84,56,79)B、(40,38,46,79,56,84)20.用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少 的是（C）。A、 94,32,40,90,80,46,21,69C 21,32,46,40,80,69,90,94B、32,40,21,46,69,94,90,80、90,69,80,46,21,32,94,40D21.若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大 的排序，所需进行 的关键

5、字比较总次数是（B）。A、 10 B、15C、21D、3422.就排序算法所用 的辅助空间而言，堆排序、快速排序和归并排序 的关系（A）。A、堆排序 快速排序 归并排序B、堆排序 归并排序 归并排序 快速排序D、堆排序 快速排序 归并排序23.最小生成树 的构造可使用（B）算法。A.Dijkstra算法B.Prim算法C.Haffman算法D.Floyd算法24.具有 32个结点 的完全二叉树 的深度为（A. 5 B.6B）。C.7D.825.在有 n个叶子结点 的哈夫曼树中，其结点总数为（D）。A不确定B2n C2n+1D2n-126.下列陈述正确 的是（B）。A.二叉树是度为 2 的有序树

6、C.二叉树必有度为 2 的结点B.D.二叉树中最多只有二棵树,且有左右子树之分二叉树中结点只有一个孩子时无左右之分27.先序为 A，B，C 的二叉树共有（A）种。A.3B.4C.5D.628.在树结构中 ,若结点 B有 3个兄弟 ,A是 B 的父亲结点 ,则 A 的度为 (B)。A.3B.4C.5D.629.在一个图中，所有顶点 的度数之和等于所有边数 的（A、 1 、2 、3 、4B）倍。BCD30.n个顶点 的强连通图至少有（A）边。A、 n 、n-1 、n+1BCD、n (n-1)31.在一个无向图中，所有顶点 的度数之和等于所有边数 的（C）倍；在一个有向图中，所有顶点 的入度之和等于

7、所有顶点出度之和 的（C）倍。A、 1/2B、2C、1D、432.任何一个无向连通图 的最小生成树（B）。A、只有一棵B、一棵或多棵、可能不存在C、一定有多棵D33.在图 的表示法中，表示形式唯一 的是（A）A、邻接矩阵表示法B、邻接表表示法C、逆邻接矩阵表示法D、逆邻接表表示法34.在一个具有 n个顶点 的无向图中，要连通全部顶点至少需要（B.n+1 C.n-1 D.n+2C）条边。A.n35.在一个图中，所有顶点 的度数之和等于图 的边数 的（B）。第 3页共 16页3 A 1/2B 2C1D4C36有 7个结点 的有向完全图有（）边。A.30B.40C.42D.5637.假定在一棵二叉树

8、中，度为2 的分支结点个数为 15，度为 1 的分支结点个数为 30个，则叶子结点数为（B）。A、 15 B、16C、17 D、4738.设 n，m为一棵树上 的两个结点，在中根遍历时，n在 m前 的条件是（C）。A、 n在 m右方C、 n在 m左方BD、n是 m祖先、n是 m子孙39.某二叉树 的后序遍历序列为： DABEC，中序遍历序列为： DEBAC，则前序遍历序列为（D）。A、 ACBEDC、 DEABCBD、DECAB、CEDBA40.将一棵有 100个结点 的完全二叉树从上到下，从左到右依次对结点编号，根结点 的编号为 1，则编号为 45 的结点 的左孩子 的编号为（90），右孩子

9、 的编号为（ 91）。A、 46B、47 C、91D、91C41.某树中，若结点 B有 4个兄弟， A是 B 的父亲结点，则 A 的度为（）。A、 3B、4C、5D、642.下列叙述正确 的是（D）A、二叉树是度为 2 的有序树B、二叉树结点只有一个孩子时无左右之分C、二叉树中必有度为 2 的结点D、二叉树中最多只有两棵子树，且有左右之分D43.由带权为 9、2、5、7 的四个叶子结点构造一棵哈夫曼树，该树 的带树路径长度为（）。A、 23C、 46BD、37、44C44在图 的表示方法中，表示形式是唯一 的是（）。A.邻接表B.逆邻接表C.邻接矩阵 D.其他44.下列关键字序列中，构成大根堆

10、 的是(D)A.5，8，1， 3，9，6，2，7C.9，8，6， 3，5，l，2，7B.9，8，1，7，5，6， 2，33D.9，8，6，7，5，1， 2，345.对序列 (15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据 的排列变为（4，9，C-1，8，20，7，15），则采用 的是（A.选择）排序。希尔B.快速C.D.冒泡第 4页共 16页4 46.设 n，m为一棵树上 的两个结点，在中根遍历时，n在 m前 的条件是（C）。是 m子孙A.n在 m右方 是 m祖先 在 m左方B.nC.nD.n二、填空题图1.树和都属于非线性结构。也2.顺序表中逻辑上相邻 的元素在物理位置上相

11、邻。3.双向链表有两个指针域，一个指向前趋，另一个指向4.若进栈 的次序是 A,B,C,D,E,写出两种出栈顺序 _5.队列存取数据应遵循 的原则是_后继_。ABCDEEDCBA、。先进先出。6.有 20个结点 的完全二叉树，编号为7 的结点 的父结点编号为3。7.两个序列分别为： L1=3，50，41，42，55，65，70，75，L2=3，50，41，42，65，55，.10，5，用冒泡排序法对 L1和 L2进行排序，交换次数较少 的是序列：L1。8.在排序方法中，从无序序列中选择关键字最小 的记录，与无序区（初始为空） 的第一个选择记录交换 的排序方法，称为排序。9.有向图 的边也称为弧

12、，用邻接矩阵存储有向图，其第i行 的所有元素之和等于顶点i 的出度。10树转换成 的二叉树，其根结点 的右子树一定为空。11.二叉排序树是一种动态查找表。12.对一组记录（ 50，40，95，20，15，70，60， 45，80）进行直接插入排序时，当把第7条记录 60插入到有序表中时，为寻找插入位置需比较15次。113.在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有后继结点，其余结点 的后继结点可以个前驱结点；叶子结点没有任意多个。14.在具有 n个结点 的二叉树中，有15.深度为 k 的完全二叉树至少有n+1个空指针。2k-1k2 -1个结点，若按自上而下，n/2+1。个结点

13、，至多有从左到右次序给结点从1开始编号，则编号最小 的叶子结点 的编号是第 5页共 16页5 16.由 a，b， c三个结点构成 的二叉树，共有30种不同形态，若是构成树，共有9种形态。右17.树所对应 的二叉树其根结点 的子树一定为空。6818.已知完全二叉树 的第 8层有 8个结点，则其叶结点数是三、综合应用题。2.已知完全二叉树 的第程）。（6分）8层有 4个结点，请计算它 的叶子结点数和总结点数。（写出计算过解：由题意可知，该完全二叉树有八层，其中第一层结点数为： 1第二层结点数为： 2第三层结点数为： 4第四层结点数为： 8第五层结点数为： 16第六层结点数为： 32第七层结点数为：

14、 64第八层结点数为： 4因为第八层结点数为 4，且为完全二叉树，则第八层四个结点为叶子结点，第七层前两个结点有子结点，其余 62个结点无子结点，则第七层 的后 62个结点为叶子结点，故叶子结点数有 4+62=66总结点数为 1+2+4+8+16+32+64+4=1313.已知数据序列 10,8,18,15,7,16，写出采用直接插入算法排序时，每一趟排序 的结果。（6分）解：直接插入排序过程如下所示初始列：（10），8,18,15,7,16第一趟：（8,10）,18,15,7,16第二趟：（8,10,18），15,7,16第三趟：（8,10,15,18），7,16第四趟：（7,8,10,15

15、,18），16第五趟：（7,8,10,15,16,18）6.一棵具有 6层 的满二叉树中结点数为多少？请写出计算公式。解： 2 -1 63- 1 2K 67.给定一个权集 W=4,8,6,9,18，画出相应 的哈夫曼树，并计算WPL。8.已知二叉树 的先序遍历序列为:ABDGHCEFI,中序遍历 的序列为： GDHBAECIF。请完成以下各第 6页共 16页6 题：（1）画出此二叉树。（2）写出它 的后序遍历序列。（3）将此二叉树看作森林 的二叉树表示，试将它还原为森林。A（1）BC（2）其后序遍历 的序列为： G H D B E I F C A（3）DEFGHI8-1.对下面 的带权无向图：

16、（1）画出邻接矩阵。155（2）画出它 的一棵最小生成树。321104 6317 5456解：（ 1）0 5 5 0 0 05 0 1 10 0 05 1 0 0 4 60 10 0 0 3 00 0 4 3 0 50 0 6 0 5 0（2）最小生成树边为红色 的324569.有一组关键字 14,15,30,28,5,10,写出冒泡排序过程 的图示。解：第一趟排序结果： 14,15,28,5,10，（30）第二趟排序结果： 14,15,5,10，（28,30）第三趟排序结果： 14,5,10，（15,28,30）第四趟排序结果： 5,10，（14,15,28,30）第五趟排序结果： 5，（1

17、0,14,15,28,30）第六趟排序结果：（5,10,14,15,28,30）第 7页共 16页7 10.给定一个权集 W=4，5，7，8，6，12，18，试画出相应 的哈夫曼树，并计算其带权径长度 WPL。60WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=1592535121317418679811.假设用于通信 的电文仅由A、B、C、D、E、F、G、H等 8个字母组成，字母在电文中出5现 的频率分别为 7、19、2、6、 32、3、 21、10。试为这 8个字母设计哈夫曼编码。11-1对于下面所示 的图，求出：12345（1）画出邻接矩阵和邻接表（2）求出各顶点 的入度

18、和出度解：（ 1）邻接矩阵1 2 3 4 51 0 1 1 0 12 0 0 0 1 03 0 0 0 0 14 1 0 0 0 05 0 0 0 1 0邻接表123452451435（2）ID(1)=1,OD(1)=3;ID(2)=1,OD(2)=1;ID(3)=1,OD(3)=1;ID(4)=2,OD(4)=1;ID(5)=2,OD(5)=1;第 8页共 16页8 12.已知一个无向图 的顶点集为a,b,c,d,e，其邻接矩阵如下，画出草图，写出从顶点a出发按深度优先搜索进行遍历 的结点序列。0 1 0 0 11 0 0 1 00 0 0 1 10 1 1 0 11 0 1 1 0解：（

19、1）acebd（2）深度优先搜索： a b d c e（答案不唯一）广度优先搜索： a b e d c（答案不唯一）13.网 G 的邻接矩阵如下，试画出该图，并画出它 的一棵最小生成树。0 8 10 11 08 0 3 0 1310 3 0 4 011 0 4 0 70 13 0 7 0解：最小生成树：113581141082344231373475第 9页共 16页9 16.写出图 的一种拓扑序列，若在它 的邻接表存储结构中，每个顶点邻接表中 的边结点都是按照终点序号从大到小链接 的，则按此给出惟一一种拓扑序列。17.对图中所示图分别写出深度优先遍历和广度优先遍历 的项点序列18.对图 7-

20、21中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2开始）求出其最小生成树。第 10页共 16页10 ：19.根据下图，实现下列功能：（1）建立图 的邻接表；（2）输出图 的拓扑序列。四、算法设计题1、单向链表中，在 p指针所指向 的结点前插入一个元素x,写出相关算法 ,并画出图形进行描述。解：#include#includetypedef int DataType;typedef struct nodeDataType data;第 11页共 16页11 struct node *next;Listnode;int Insert(Listnode *head,DataType a,int

21、b)/这个是插入算法Listnode *p,*h,*s;int k=1;p=head;h=head-next;while(h!=NULL&knext;if(p=NULL)printf(插入失败 );return 0;s=(Listnode *)malloc(sizeof(Listnode);s-data=a;s-next=h;p-next=s;return 1;void main()Listnode *H,*p;int x,y;H=(Listnode*)malloc(sizeof(Listnode);H-next=NULL;printf(请输入将被存入链表中 的数（0为结束）：);scanf(%d,&x);while(x!=0)p=(Listnode*)malloc(sizeof(Listnode);p-data=x;p-next=H-next;H-next=p;scanf( %d,&x);printf(请输入将被插入 的数 :n);scanf(%d,&x);printf(请输入将被插入 的数 的位置：n);第 12页共 16页