数据结构与算法试题.doc

《数据结构与算法试题.doc》由会员分享，可在线阅读，更多相关《数据结构与算法试题.doc（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一、 选择题1.在逻辑上可以把数据结构分成（ A）A.线性结构和非线性结构 B.动态结构和静态结构C.紧凑结构和非紧凑结构 D.内部结构和外部结构2. 单链表中各结点之间的地址（C） 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); B.Q-NEXT=P; FREE(Q); C.Q-NEXT=P-NEXT;FREE(Q); D.P-NEXT=S;S-NEXT

2、=P;13.循环队列SQ队满的条件是（B）。 A.SQ-rear=SQ-front B. (SQ-rear+1)%MAXLEN=SQ-front23.最小生成树的构造可使用（B）算法。 A.Dijkstra算法 B.Prim算法 C.Haffman算法 D.Floyd算法24. 具有32个结点的完全二叉树的深度为（B）。 A. 5 B.6 C.7 D.825. 在有n个叶子结点的哈夫曼树中，其结点总数为（D）。A不确定 B2n C2n+1 D2n-126.下列陈述正确的是（B）。 A.二叉树是度为2的有序树 B. 二叉树中最多只有二棵树,且有左右子树之分 C.二叉树必有度为2的结点 D. 二叉

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

4、B）。A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在33.在图的表示法中，表示形式唯一的是（A）A、邻接矩阵表示法 B、邻接表表示法 C、逆邻接矩阵表示法 D、逆邻接表表示法34.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。 A.n B.n+1 C.n-1 D.n+235. 在一个图中，所有顶点的度数之和等于图的边数的（B）。A1/2 B2 C1 D436有7个结点的有向完全图有（C）边。 A.30 B.40 C.42 D.5637.假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（B）。A、15 B、16 C、17

5、 D、4738.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（C）。A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙39.某二叉树的后序遍历序列为：DABEC，中序遍历序列为：DEBAC，则前序遍历序列为（D ）。A、ACBED B、DECAB C、DEABC D、CEDBA40.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子的编号为（90），右孩子的编号为（91）。A、46 B、47 C、91 D、9141.某树中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（C）。A、3 B、4 C、5 D、

6、642.下列叙述正确的是（D）A、二叉树是度为2的有序树 B、二叉树结点只有一个孩子时无左右之分 C、二叉树中必有度为2的结点 D、二叉树中最多只有两棵子树，且有左右之分43.由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D）。A、23 B、37 C、46 D、4444在图的表示方法中，表示形式是唯一的是（C）。 A.邻接表 B.逆邻接表 C.邻接矩阵 D.其他46.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（C）。A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙二、填空题1.树和 图 都属于非线性结构。2.顺序表中逻辑上相邻的元素

7、在物理位置上 也 相邻。3.双向链表有两个指针域，一个指向前趋，另一个指向_后继_。4.若进栈的次序是A,B,C,D,E,写出两种出栈顺序_ABCDE、EDCBA。5.队列存取数据应遵循的原则是先进先出。6.有20个结点的完全二叉树，编号为7的结点的父结点编号为 3 。7.两个序列分别为：L1=3，50，41，42，55，65，70，75，L2=3，50，41，42，65，55，.9.有向图的边也称为 弧，用邻接矩阵存储有向图，其第i行的所有元素之和等于顶点i的 出度 。10树转换成的二叉树，其根结点的 右 子树一定为空。11.二叉排序树是一种 动态 查找表。12.对一组记录（50，40，95

8、，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较 15 次。13.在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后继 结点，其余结点的后继结点可以任意多个。14.在具有n个结点的二叉树中，有n+1个空指针。15.深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是n/2+1。16.由a，b，c三个结点构成的二叉树，共有 30种不同形态，若是构成树，共有9 种形态。17.树所对应的二叉树其根结点的 右

9、子树一定为空。18.已知完全二叉树的第8层有8个结点，则其叶结点数是 68 三、综合应用题。2.已知完全二叉树的第8层有4个结点，请计算它的叶子结点数和总结点数。（写出计算过程）。（6分）解：由题意可知，该完全二叉树有八层，其中第一层结点数为：1第二层结点数为：2第三层结点数为：4第四层结点数为：8第五层结点数为：16第六层结点数为：32第七层结点数为：64第八层结点数为：4因为第八层结点数为4，且为完全二叉树，则第八层四个结点为叶子结点，第七层前两个结点有子结点，其余62个结点无子结点，则第七层的后62个结点为叶子结点，故叶子结点数有4+62=66总结点数为1+2+4+8+16+32+64+

10、4=1316.一棵具有6层的满二叉树中结点数为多少？请写出计算公式。解：637.给定一个权集W=4,8,6,9,18，画出相应的哈夫曼树，并计算WPL。 8.已知二叉树的先序遍历序列为:ABDGHCEFI,中序遍历的序列为：GDHBAECIF。请完成以下各题：（1）画出此二叉树。（2）写出它的后序遍历序列。GHABDCEFI（3）将此二叉树看作森林的二叉树表示，试将它还原为森林。（1）（2）其后序遍历的序列为：G H D B E I F C A （3） 351325D12660181798D45710.给定一个权集W=4，5，7，8，6，12，18，试画出相应的哈夫曼树，并计算其带权径长度WP

11、L。WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15911.假设用于通信的电文仅由A、B、C、D、E、F、G、H等8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。12.已知一个无向图的顶点集为a,b,c,d,e，其邻接矩阵如下，画出草图，写出从顶点a出发按深度优先搜索进行遍历的结点序列。 解：acbed（1）（2）深度优先搜索：a b d c e （答案不唯一） 广度优先搜索：a b e d c （答案不唯一）13.网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 0 8 10 11 0 8 0 3

12、0 13 10 3 0 4 0 11 0 4 0 7 0 13 0 7 02543125431解： 最小生成树： 8 11 10 8 3 4 13 7 3 4 7四、算法设计题1、单向链表中，在p指针所指向的结点前插入一个元素x,写出相关算法,并画出图形进行描述。解：#include#includetypedef int DataType;typedef struct node DataType data; struct node *next;Listnode;int Insert(Listnode *head,DataType a,int b)/这个是插入算法 Listnode *p,*h,

13、*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); w

14、hile(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); scanf(%d,&y); p=H-next; printf(插入前，链表：); while(p!=NULL) printf(%d,p-data); p=p-next ; if(Insert(H,x,y)/这里是调用插入算法 p=H-next; printf(插入后处理后的链表：n)

15、; while(p!=NULL) printf(%d,p-data); p=p-next; printf(n); 2、在单链表中删除第i个结点,若删除成功返回1,否则返回0,并要求画出图形进行描述。解：#include#includetemplateclass SeqListpublic:T Delete(int i);T data5;int length;templateT SeqList:Delete(int i)int j;T x;if(length=0) throw下溢;if(ilength) throw位置异常;x=datai-1;for(j=i;jnext!=NULL) Del_Elem (p,x); /*调用删除已知结点p之后结点函数*/ return 1;elsereturn 0;int main()SeqList a;couta.length;cout请输入单链表中的数据：; for(int i=0;ia.datai; for(i=0;ia.length;i+) coutsetw(5)a.datai;coutendl; couti;a.Delete(i);coutendl;for(i=0;ia.length;i+) coutsetw(5)a.datai;coutendl;