数据结构与算法试题

1、一、选择题1 .在逻辑上可以把数据结构分成（A）A.线性结构和非线性结构B.动态结构和静态结构C.紧凑结构和非紧凑结构D.内部结构和外部结构2 .单链表中各结点之间的地址（C）A.必须连续B.部分必须连续C.不一定连续D.以上均不对3 .在一个长度为n的顺序表中向第i个元素（0<i<=n+1）之前插入一个新元素时，需向后移动（B）个元素。A、n-iB、n-i+1C、n-i-1D、i4 .插入和删除操作只能在一端进行的线性表，称为（C）。A.队列B.线性表C.栈D.循环队列5、队列是仅允许在（）进行插入，而在（）进行删除。（A）A.队尾，队首B.队尾，队尾C.队首，队尾D.队首，队首

2、6 .链表适合于（A）查找。A.顺序B.二分C.随机D.顺序或二分7 .数据的基本单位是（A）。A.数据元素B.数据结构C.数据项D.数据对象8 .下列哪个不是算法的特性（B）。A.有穷性B.可数性C.可行性D.确定性9 .在表长为n的顺序表中进行线性查找，它的平均查找长度为（B）。iA.ASL=nB.ASL=（n+1）/2C.ASL='n+1D.ASL=log2n10 .一个线性表第一个元素的存储地址是320,每个元素的长度为3,则第五个元素的地址是（C）。A.311B.328C.332D.31311 .设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素

3、是双循环链表L的尾元素的条件是（D）。A.P=LB.P->front=LC.P=NULLD.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=P;13 .循环队列SQ队满的条件是（B）。A.SQ->rear=SQ->frontB.（SQ->rear+1）%MAXLEN=SQ->front23

4、.最小生成树的构造可使用（B）算法。A.Dijkstra算法B.Prim算法C.Haffman算法D.Floyd算法24 .具有32个结点的完全二叉树的深度为（B）。A.5B.6C.7D.825 .在有n个叶子结点的哈夫曼树中，其结点总数为（D）。A.不确定B.2nC.2n+1D.2n-126 .下列陈述正确的是（B）。A.二叉树是度为2的有序树B.二叉树中最多只有二棵树，且有左右子树之分C.二叉树必有度为2的结点D.二叉树中结点只有一个孩子时无左右之分27 .先序为A,B,C的二叉树共有（A）种。A.3B.4C.5D.628 .在树结构中，若结点B有3个兄弟,A是B的父亲结点，则A的度为（B

5、）。A.3B.4C.5D.629 .在一个图中，所有顶点的度数之和等于所有边数的（B）倍。A1B、2C、3D、430 .n个顶点的强连通图至少有（A边。AnB、n-1C、n+1D、n（n-1）31 .在一个无向图中，所有顶点的度数之和等于所有边数的（C）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A1/2B、2C、1D、432 .任何一个无向连通图的最小生成树（B）。A、只有一棵B、一棵或多棵C一定有多棵D、可能不存在33 .在图的表本法中，表木形式唯一"的是（A）A、邻接矩阵表示法B、邻接表表示法C逆邻接矩阵表示法D、逆邻接表表示法34 .在一个具有n个顶

6、点的无向图中，要连通全部顶点至少需要（C）条边。A.nB.n+1C.n-1D.n+235 .在一个图中，所有顶点的度数之和等于图的边数的（B）。A.1/2B.2C.1D.436 .有7个结点的有向完全图有（C）边。A.30B.40C.42D.5637 .假定在一棵二叉树中，度为2的分支结点个数为15,度为1的分支结点个数为30个，则叶子结点数为（B）。A15B、16C、17D、4738 .设n,m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（C）。An在m右方B、n是m祖先Cn在m左方D、n是m子孙39 .某二叉树的后序遍历序列为：DABEC中序遍历序列为：DEBAC则前序遍历序列为（

7、D）。AACBEDB、DECABCDEABCD、CEDBA40 .将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1,则编号为45的结点的左孩子的编号为（90）,右孩子的编号为（91）。A46B、47C、91D、9141 .某树中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（C）。A3B、4C、5D、642 .下列叙述正确的是（D）A、二叉树是度为2的有序树B、二叉树结点只有一个孩子时无左右之分C二叉树中必有度为2的结点D二叉树中最多只有两棵子树，且有左右之分43 .由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D）。A23B

8、、37C46D、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 .顺序表中逻辑上相邻的元素在物理位置上也相邻。3 .双向链表有两个指针域，一个指向前趋，另一个指向后继_。4 .若进栈的次序是A,B,C,D,E,写出两种出栈顺序_ABCDEEDCBA5 .队列存取数据应遵循的原则是先进先出。6 .有20个结点的完全二叉树，编号为7的结点的父结点编号为3。7 .两个序列分别为:

9、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,20,15,70,60,45,80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较15次。13 .在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有J个前驱结点；叶子结点没有后继结点,其余结点的后继结点可以任意多个。14 .在具有n个结点的二叉树中，有

10、n+1个空指针。15 .深度为k的完全二叉树至少有疆个结点，至多有2二1个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是n/2+1q16 .由a,b,c三个结点构成的二叉树，共有J0种不同形态，若是构成树，共有9_种形态。17 .树所对应的二叉树其根结点的业_子树一定为空。18 .已知完全二叉树的第8层有8个结点，则其叶结点数是68三、综合应用题。2 .已知完全二叉树的第8层有4个结点，请计算它的叶子结点数和总结点数。（写出计算过程）。（6分）解：由题意可知，该完全二叉树有八层，其中第一层结点数为：1第二层结点数为：2第三层结点数为：4第四层结点数为：8第五层

11、结点数为：16第六层结点数为：32第七层结点数为：64第八层结点数为：4因为第八层结点数为4,且为完全二叉树，则第八层四个结点为叶子结点，第七层前两个结点有子结点，其余62个结点无子结点，则第七层的后62个结点为叶子结点，故叶子结点数有4+62=66总结点数为1+2+4+8+16+32+64+4=1316 .一棵具有6层的满二叉树中结点数为多少？请写出计算公式。解：2k-1=26-1=637 .给定一个权集W=4,8,6,9,18,画出相应的哈夫曼树，并计算WPL8 .已知二叉树的先序遍历序列为：ABDGHCEFI,中序遍历的序列为：GDHBAECIF请完成以下各画出此二叉树。写出它的后序遍历

12、序列。BCDEGH题:(1)(2)(3)将此A2树看作森林的二叉树表示，试将它还原为森林。(2)其后序遍历的序列为：GHDBEIFCA(3)10 .给定一个权集W=4,长度WPL5,7,8,6,12,18,试画出相应的哈夫曼树，并计算其带权径WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15911 .假设用于通信的电文仅由现的频率分别为7、19、2、6、A、B、C、DE、32、3、21、10。F、G试为这12.已知一个无向图的顶点集为a,b,c,d,e其邻接矩阵如下，画出草图，写出从顶点出发按深度优先搜索进行遍历的结点序列。(答案不呵一)(答案屁一)(2)深度优先搜索：abd

13、ce广度优先搜索：abedc13.网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。081011080301310304011040130四、算法设计题1、单向链表中，在p指针所指向的结点前插入一个元素x,写出相关算法，并画出图形进行描述。解：#include<stdio.h>#include<malloc.h>typedefintDataType;typedefstructnodeDataTypedata;structnode*next;Listnode;intInsert(Listnode*head,DataTypea,intb)这个是插入算法Listnod

14、e*p,*h,*s;intk=1;p=head;h=head->next;while(h!=NULL&&k<=b-1)k+;p=h;h=h->next;if(p=NULL)printf("插入失败")；return0;s=(Listnode*)malloc(sizeof(Listnode);s->data=a;s->next=h;p->next=s;return1;)voidmain()(Listnode*H,*p;intx,y;H=(Listnode*)malloc(sizeof(Listnode);H->next

15、=NULL;printf("请输入将被存入链表中的数(。为结束)：");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");sc

16、anf("%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");while(p!=NULL)(printf("%d",p->data);p=p->next;)printf("n");)图27。在结点p之后插

17、入结点32、在单链表中删除第i个结点，若删除成功返回1,否则返回0,并要求画出图形进行描述。解：#include<iostream>#include<iomanip>template<classT>classSeqListpublic:TDelete(inti);Tdata5;intlength;template<classT>TSeqList<T>:Delete(inti)intj;Tx;if(length=0)throw"下溢"if(i<1|i>length)throw"位置异常"

18、;；x=datai-1;for(j=i;j<length;j+)dataj-1=dataj;length-;returnx;intDelElem(LinkList*L,inti,datatype*x)LinkList*p;p=GetList(L,i-1);/*调用按序号查找第i-1个元素地址p函数*/if(p!=NULL&&p->next!=NULL)Del_Elem(p,x);/*调用删除已知结点p之后结点函数*/return1;elsereturn0;)intmain()(SeqList<int>a;cout<<"请输入单链表的长度：length="cin>>a.length;cout<<"请输入单链表中的数据："f