2023年8月1日发(作者：)
一、选择题
1.在逻辑上可以把数据结构分成（
A）
A.线性结构和非线性结构 B.动态结构和静态结构
C.紧凑结构和非紧凑结构 D.内部结构和外部结构
2.
单链表中各结点之间的地址（C）
A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对
3.在一个长度为n的顺序表中向第i个元素（0 C）。 A) A、n-i B、n-i+1 C、n-i-1 D、i 4. 插入和删除操作只能在一端进行的线性表，称为（ A.队列 B.线性表 C.栈 D.循环队列 5、队列是仅允许在（）进行插入，而在（）进行删除。(A.队尾，队首 B.队尾，队尾 C.队首，队尾 D.队首，队首 6.链表适合于（A）查找。 A）。 B）。 B）。 A.顺序 B.二分 C.随机 D.顺序或二分 7.数据的基本单位是（A.数据元素 B.数据结构 C.数据项 D.数据对象 8.下列哪个不是算法的特性（A.有穷性 B.可数性 C.可行性 D.确定性 9.在表长为n的顺序表中进行线性查找，它的平均查找长度为（=n =(n+1)/2 =n+1 =log2n 10. 一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址是(C）。 D）。 A）。 A.311 B.328 C.332 D.313 11.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（ A.P==L B.P->front==L C.P==NULL D.P->rear==L 12. 已知P为单链表中的非首尾结点，删除P结点的后继结点Q的语句为（ 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）。 第 1 页 共 16 页 1 ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front ->rear==0 D. SQ->front==0 14.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为(B)。 A、79，46，56，38，40，80 B、84，79，56，38，40，46 C、84，79，56，46，40，38 D、84，56，79，40，46，38 15.排序趟数与序列原始状态(原始排列)有关的排序方法是（A、插入排序 B、选择排序 C、冒泡排序 D、快速排序 16.下列排序方法中，（ACD）方法。 B）是稳定的排序方法。 C)的两趟排序后A、直接选择排序 B、二分法插入排序 C、希尔排序 D、快速排序 17.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(的结果。 A、选择排序 B、冒泡排序 C、插入排序 D、堆排序 18.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C）排序。 A、选择 B、快速 C、希尔 D、冒泡 19.一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（ C ）。 A(38,40,46,56,79,84) B、(40,38,46,79,56,84) C、(40,38,46,56,79,84) D、(40,38,46,84,56,79) 20.用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。 A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80 C 21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,40 21.若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（B）。 A）。 2 A、10 B、15 C、21 D、34 22.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（A、堆排序<快速排序<归并排序 B、堆排序<归并排序<快速排序 第 2 页 共 16 页 C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序 23.最小生成树的构造可使用（B）算法。 B）。 D）。 ra算法 算法 n算法 算法 24. 具有32个结点的完全二叉树的深度为（ A. 5 B.6 C.7 D.8 25. 在有n个叶子结点的哈夫曼树中，其结点总数为（A．不确定 B．2n C．2n+1 D．2n-1 26.下列陈述正确的是（B）。 A）种。 B)。 A.二叉树是度为2的有序树 B. 二叉树中最多只有二棵树,且有左右子树之分 C.二叉树必有度为2的结点 D. 二叉树中结点只有一个孩子时无左右之分 27.先序为A，B，C的二叉树共有（ A.3 B.4 C.5 D.6 28.在树结构中,若结点B有3个兄弟,A是B的父亲结点,则A的度为( A.3 B.4 C.5 D.6 29.在一个图中，所有顶点的度数之和等于所有边数的（A、1 B、2 C、3 D、4 30.n个顶点的强连通图至少有（B）倍。 A）边。 C）倍；在一个有向图中，所A、n B、n-1 C、n+1 D、n (n-1) 31.在一个无向图中，所有顶点的度数之和等于所有边数的（有顶点的入度之和等于所有顶点出度之和的（C）倍。 A、1/2 B、2 C、1 D、4 32.任何一个无向连通图的最小生成树（B）。 A） C）条边。 A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在 33.在图的表示法中，表示形式唯一的是（A、邻接矩阵表示法 B、邻接表表示法 C、逆邻接矩阵表示法 D、逆邻接表表示法 34.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ A.n B.n+1 C.n-1 D.n+2 35. 在一个图中，所有顶点的度数之和等于图的边数的（第 3 页 共 16 页 B）。 3 A．1/2 B．2 C．1 D．4 36．有7个结点的有向完全图有（C）边。 A.30 B.40 C.42 D.56 37.假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（B）。 C）。 D ）。 A、15 B、16 C、17 D、47 38.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙 39.某二叉树的后序遍历序列为：DABEC，中序遍历序列为：DEBAC，则前序遍历序列为（A、ACBED B、DECAB C、DEABC D、CEDBA 40.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子的编号为（A、46 B、47 C、91 D、91 41.某树中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（A、3 B、4 C、5 D、6 42.下列叙述正确的是（90），右孩子的编号为（91）。 C）。 D） A、二叉树是度为2的有序树 B、二叉树结点只有一个孩子时无左右之分 C、二叉树中必有度为2的结点 D、二叉树中最多只有两棵子树，且有左右之分 43.由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（A、23 B、37 C、46 D、44 44．在图的表示方法中，表示形式是唯一的是（D）。 C）。 A.邻接表 B.逆邻接表 C.邻接矩阵 D.其他 44.下列关键字序列中，构成大根堆的是(D) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，3 45.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C）排序。 4 A.选择 B.快速 C.希尔 D.冒泡 第 4 页 共 16 页 46.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（ 二、填空题 1.树和 C）。 A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙 图 都属于非线性结构。 也 相邻。 3.双向链表有两个指针域，一个指向前趋，另一个指向__后继__。 4.若进栈的次序是A,B,C,D,E,写出两种出栈顺序_ABCDE、EDCBA。 5.队列存取数据应遵循的原则是先进先出。 6.有20个结点的完全二叉树，编号为7的结点的父结点编号为 3 。 2.顺序表中逻辑上相邻的元素在物理位置上 7.两个序列分别为：L1={3，50，41，42，55，65，70，75}，L2={3，50，41，42，65，55，. 10，5}，用冒泡排序法对L1和L2进行排序，交换次数较少的是序列： L1 。 8.在排序方法中，从无序序列中选择关键字最小的记录，与无序区（初始为空）的第一个记录交换的排序方法，称为 9.有向图的边也称为 的 选择 排序。 弧，用邻接矩阵存储有向图，其第i行的所有元素之和等于顶点i右 子树一定为空。 出度 。 动态 查找表。 15 次。 10．树转换成的二叉树，其根结点的 11.二叉排序树是一种 12.对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较 1 个前驱结点；叶子结点没有后继 结点，其余结点的后继结点可以任意多个。 14.在具有n个结点的二叉树中，有n+1个空指针。 k-1k15.深度为k的完全二叉树至少有2个结点，至多有2-1个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是n/2+1。 13.在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有 第 5 页 共 16 页 5 16.由a，b，c三个结点构成的二叉树，共有 形态。 30种不同形态，若是构成树，共有9 种右 子树一定为空。 18.已知完全二叉树的第8层有8个结点，则其叶结点数是 68 17.树所对应的二叉树其根结点的 三、综合应用题。 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+4=131 3.已知数据序列{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,18），16 第五趟：（7,8,10,15,16,18） 6.一棵具有6层的满二叉树中结点数为多少？请写出计算公式。 解：2K-126-163 7.给定一个权集W={4,8,6,9,18}，画出相应的哈夫曼树，并计算WPL。 8.已知二叉树的先序遍历序列为:ABDGHCEFI,中序遍历的序列为：GDHBAECIF。请完成以下各第 6 页 共 16 页 6 题： （1）画出此二叉树。 （2）写出它的后序遍历序列。 （3）将此二叉树看作森林的二叉树表示，试将它还原为森林。 （1） A B C （2）其后序遍历的序列为：G H D B E I F C A （3） F D E G H I 8-1.对下面的带权无向图： （1）画出邻接矩阵。 （2）画出它的一棵最小生成树。 1 5 2 5 3 1 10 4 6 解：（1） 3 7 5 4 5 6 0 5 5 0 0 0 （2）最小生成树 5 0 1 10 0 0 边为红色的 2 1 3 5 1 0 0 4 6 0 10 0 0 3 0 0 0 4 3 0 5 0 0 6 0 5 0 9.有一组关键字{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，（10,14,15,28,30） 第六趟排序结果：（5,10,14,15,28,30） 第 7 页 共 16 页 7 4 5 6 10.给定一个权集W={4，5，7，8，6，12，18}，试画出相应的哈夫曼树，并计算其带权径长度WPL。 60 WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159 2535 12 13 17 18 9 6 7 8 11.假设用于通信的电文仅由A、B、C、D、E、F、G、H等8个字母组成，字母在电文中出5 4 现的频率分别为7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。 11-1对于下面所示的图，求出： （1）画出邻接矩阵和邻接表 （2）求出各顶点的入度和出度 解：（1）邻接矩阵 1 2 3 4 5 4 5 2 1 3 1020304150邻接表 1 2 3 4 5 110100100001 00000010 2 4 5 1 4 3 5 ∧ ∧ ∧ ∧ ∧ （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 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 解：（1） a b c e d （2）深度优先搜索：a b d c e （答案不唯一） 广度优先搜索：a b e d c （答案不唯一） 13.网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 0 8 10 11 0 8 0 3 0 13 10 3 0 4 0 11 0 4 0 7 0 13 0 7 0 解： 最小生成树： 8 1 11 1 10 8 2 3 3 4 4 2 3 4 13 7 3 4 5 5 7 第 9 页 共 16 页 9 16.写出图的一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出惟一一种拓扑序列。 17.对图中所示图分别写出深度优先遍历和广度优先遍历的项点序列 18.对图7-21中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2开始）求出其最小生成树。 第 10 页 共 16 页 10 ： 19.根据下图，实现下列功能： （1）建立图的邻接表； （2）输出图的拓扑序列。 四、算法设计题 1、单向链表中，在p指针所指向的结点前插入一个元素x,写出相关算法,并画出图形进行描述。 解： #include #include typedef int DataType; typedef struct node { DataType data; 第 11 页 共 16 页 11 struct node *next; }Listnode; int Insert(Listnode *head,DataType a,int b)//这个是插入算法 { Listnode *p,*h,*s; int k=1; p=head; h=head->next; while(h!=NULL&&k<=b-1) { k++; p=h; h=h->next; } 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 页 12 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"); while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("n"); } } 2、在单链表中删除第i个结点,若删除成功返回1,否则返回0,并要求画出图形进行描述。 解： #include #include template class SeqList { 第 13 页 共 16 页 13 public: T Delete(int i); T data[5]; int length; }; template T SeqList { int j; T x; if(length==0) throw"下溢"; if(i<1||i>length) throw"位置异常"; x=data[i-1]; for(j=i;j data[j-1]=data[j]; length--; return x; } int DelElem(LinkList *L,int i,datatype *x) { LinkList *p; p=GetList(L, i-1); /*调用按序号查找第i-1个元素地址p函数*/ 第 14 页 共 16 页 14 if (p!=NULL && p->next!=NULL) { Del_Elem (p,x); /*调用删除已知结点p之后结点函数*/ return 1; } else return 0; } int main() { SeqList cout<<"请输入单链表的长度：length="; cin>>; cout<<"请输入单链表中的数据："; for(int i=0;i<;i++) { cin>>[i]; } for(i=0;i<;i++) cout< cout< cout<<"请输入单链表中要删除数据的位置： cin>>i; 第 15 页 共 16 页 15 i="; (i); cout< for(i=0;i<;i++) cout< cout< } 第 16 页 共 16 页 16 2023年8月1日发(作者：) 一、选择题 1.在逻辑上可以把数据结构分成（ A） A.线性结构和非线性结构 B.动态结构和静态结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构 2. 单链表中各结点之间的地址（C） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n的顺序表中向第i个元素（0 C）。 A) A、n-i B、n-i+1 C、n-i-1 D、i 4. 插入和删除操作只能在一端进行的线性表，称为（ A.队列 B.线性表 C.栈 D.循环队列 5、队列是仅允许在（）进行插入，而在（）进行删除。(A.队尾，队首 B.队尾，队尾 C.队首，队尾 D.队首，队首 6.链表适合于（A）查找。 A）。 B）。 B）。 A.顺序 B.二分 C.随机 D.顺序或二分 7.数据的基本单位是（A.数据元素 B.数据结构 C.数据项 D.数据对象 8.下列哪个不是算法的特性（A.有穷性 B.可数性 C.可行性 D.确定性 9.在表长为n的顺序表中进行线性查找，它的平均查找长度为（=n =(n+1)/2 =n+1 =log2n 10. 一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址是(C）。 D）。 A）。 A.311 B.328 C.332 D.313 11.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（ A.P==L B.P->front==L C.P==NULL D.P->rear==L 12. 已知P为单链表中的非首尾结点，删除P结点的后继结点Q的语句为（ 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）。 第 1 页 共 16 页 1 ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front ->rear==0 D. SQ->front==0 14.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为(B)。 A、79，46，56，38，40，80 B、84，79，56，38，40，46 C、84，79，56，46，40，38 D、84，56，79，40，46，38 15.排序趟数与序列原始状态(原始排列)有关的排序方法是（A、插入排序 B、选择排序 C、冒泡排序 D、快速排序 16.下列排序方法中，（ACD）方法。 B）是稳定的排序方法。 C)的两趟排序后A、直接选择排序 B、二分法插入排序 C、希尔排序 D、快速排序 17.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(的结果。 A、选择排序 B、冒泡排序 C、插入排序 D、堆排序 18.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C）排序。 A、选择 B、快速 C、希尔 D、冒泡 19.一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（ C ）。 A(38,40,46,56,79,84) B、(40,38,46,79,56,84) C、(40,38,46,56,79,84) D、(40,38,46,84,56,79) 20.用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。 A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80 C 21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,40 21.若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（B）。 A）。 2 A、10 B、15 C、21 D、34 22.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（A、堆排序<快速排序<归并排序 B、堆排序<归并排序<快速排序 第 2 页 共 16 页 C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序 23.最小生成树的构造可使用（B）算法。 B）。 D）。 ra算法 算法 n算法 算法 24. 具有32个结点的完全二叉树的深度为（ A. 5 B.6 C.7 D.8 25. 在有n个叶子结点的哈夫曼树中，其结点总数为（A．不确定 B．2n C．2n+1 D．2n-1 26.下列陈述正确的是（B）。 A）种。 B)。 A.二叉树是度为2的有序树 B. 二叉树中最多只有二棵树,且有左右子树之分 C.二叉树必有度为2的结点 D. 二叉树中结点只有一个孩子时无左右之分 27.先序为A，B，C的二叉树共有（ A.3 B.4 C.5 D.6 28.在树结构中,若结点B有3个兄弟,A是B的父亲结点,则A的度为( A.3 B.4 C.5 D.6 29.在一个图中，所有顶点的度数之和等于所有边数的（A、1 B、2 C、3 D、4 30.n个顶点的强连通图至少有（B）倍。 A）边。 C）倍；在一个有向图中，所A、n B、n-1 C、n+1 D、n (n-1) 31.在一个无向图中，所有顶点的度数之和等于所有边数的（有顶点的入度之和等于所有顶点出度之和的（C）倍。 A、1/2 B、2 C、1 D、4 32.任何一个无向连通图的最小生成树（B）。 A） C）条边。 A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在 33.在图的表示法中，表示形式唯一的是（A、邻接矩阵表示法 B、邻接表表示法 C、逆邻接矩阵表示法 D、逆邻接表表示法 34.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ A.n B.n+1 C.n-1 D.n+2 35. 在一个图中，所有顶点的度数之和等于图的边数的（第 3 页 共 16 页 B）。 3 A．1/2 B．2 C．1 D．4 36．有7个结点的有向完全图有（C）边。 A.30 B.40 C.42 D.56 37.假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（B）。 C）。 D ）。 A、15 B、16 C、17 D、47 38.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙 39.某二叉树的后序遍历序列为：DABEC，中序遍历序列为：DEBAC，则前序遍历序列为（A、ACBED B、DECAB C、DEABC D、CEDBA 40.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子的编号为（A、46 B、47 C、91 D、91 41.某树中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（A、3 B、4 C、5 D、6 42.下列叙述正确的是（90），右孩子的编号为（91）。 C）。 D） A、二叉树是度为2的有序树 B、二叉树结点只有一个孩子时无左右之分 C、二叉树中必有度为2的结点 D、二叉树中最多只有两棵子树，且有左右之分 43.由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（A、23 B、37 C、46 D、44 44．在图的表示方法中，表示形式是唯一的是（D）。 C）。 A.邻接表 B.逆邻接表 C.邻接矩阵 D.其他 44.下列关键字序列中，构成大根堆的是(D) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，3 45.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C）排序。 4 A.选择 B.快速 C.希尔 D.冒泡 第 4 页 共 16 页 46.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（ 二、填空题 1.树和 C）。 A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙 图 都属于非线性结构。 也 相邻。 3.双向链表有两个指针域，一个指向前趋，另一个指向__后继__。 4.若进栈的次序是A,B,C,D,E,写出两种出栈顺序_ABCDE、EDCBA。 5.队列存取数据应遵循的原则是先进先出。 6.有20个结点的完全二叉树，编号为7的结点的父结点编号为 3 。 2.顺序表中逻辑上相邻的元素在物理位置上 7.两个序列分别为：L1={3，50，41，42，55，65，70，75}，L2={3，50，41，42，65，55，. 10，5}，用冒泡排序法对L1和L2进行排序，交换次数较少的是序列： L1 。 8.在排序方法中，从无序序列中选择关键字最小的记录，与无序区（初始为空）的第一个记录交换的排序方法，称为 9.有向图的边也称为 的 选择 排序。 弧，用邻接矩阵存储有向图，其第i行的所有元素之和等于顶点i右 子树一定为空。 出度 。 动态 查找表。 15 次。 10．树转换成的二叉树，其根结点的 11.二叉排序树是一种 12.对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较 1 个前驱结点；叶子结点没有后继 结点，其余结点的后继结点可以任意多个。 14.在具有n个结点的二叉树中，有n+1个空指针。 k-1k15.深度为k的完全二叉树至少有2个结点，至多有2-1个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是n/2+1。 13.在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有 第 5 页 共 16 页 5 16.由a，b，c三个结点构成的二叉树，共有 形态。 30种不同形态，若是构成树，共有9 种右 子树一定为空。 18.已知完全二叉树的第8层有8个结点，则其叶结点数是 68 17.树所对应的二叉树其根结点的 三、综合应用题。 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+4=131 3.已知数据序列{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,18），16 第五趟：（7,8,10,15,16,18） 6.一棵具有6层的满二叉树中结点数为多少？请写出计算公式。 解：2K-126-163 7.给定一个权集W={4,8,6,9,18}，画出相应的哈夫曼树，并计算WPL。 8.已知二叉树的先序遍历序列为:ABDGHCEFI,中序遍历的序列为：GDHBAECIF。请完成以下各第 6 页 共 16 页 6 题： （1）画出此二叉树。 （2）写出它的后序遍历序列。 （3）将此二叉树看作森林的二叉树表示，试将它还原为森林。 （1） A B C （2）其后序遍历的序列为：G H D B E I F C A （3） F D E G H I 8-1.对下面的带权无向图： （1）画出邻接矩阵。 （2）画出它的一棵最小生成树。 1 5 2 5 3 1 10 4 6 解：（1） 3 7 5 4 5 6 0 5 5 0 0 0 （2）最小生成树 5 0 1 10 0 0 边为红色的 2 1 3 5 1 0 0 4 6 0 10 0 0 3 0 0 0 4 3 0 5 0 0 6 0 5 0 9.有一组关键字{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，（10,14,15,28,30） 第六趟排序结果：（5,10,14,15,28,30） 第 7 页 共 16 页 7 4 5 6 10.给定一个权集W={4，5，7，8，6，12，18}，试画出相应的哈夫曼树，并计算其带权径长度WPL。 60 WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159 2535 12 13 17 18 9 6 7 8 11.假设用于通信的电文仅由A、B、C、D、E、F、G、H等8个字母组成，字母在电文中出5 4 现的频率分别为7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。 11-1对于下面所示的图，求出： （1）画出邻接矩阵和邻接表 （2）求出各顶点的入度和出度 解：（1）邻接矩阵 1 2 3 4 5 4 5 2 1 3 1020304150邻接表 1 2 3 4 5 110100100001 00000010 2 4 5 1 4 3 5 ∧ ∧ ∧ ∧ ∧ （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 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 解：（1） a b c e d （2）深度优先搜索：a b d c e （答案不唯一） 广度优先搜索：a b e d c （答案不唯一） 13.网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 0 8 10 11 0 8 0 3 0 13 10 3 0 4 0 11 0 4 0 7 0 13 0 7 0 解： 最小生成树： 8 1 11 1 10 8 2 3 3 4 4 2 3 4 13 7 3 4 5 5 7 第 9 页 共 16 页 9 16.写出图的一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出惟一一种拓扑序列。 17.对图中所示图分别写出深度优先遍历和广度优先遍历的项点序列 18.对图7-21中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2开始）求出其最小生成树。 第 10 页 共 16 页 10 ： 19.根据下图，实现下列功能： （1）建立图的邻接表； （2）输出图的拓扑序列。 四、算法设计题 1、单向链表中，在p指针所指向的结点前插入一个元素x,写出相关算法,并画出图形进行描述。 解： #include #include typedef int DataType; typedef struct node { DataType data; 第 11 页 共 16 页 11 struct node *next; }Listnode; int Insert(Listnode *head,DataType a,int b)//这个是插入算法 { Listnode *p,*h,*s; int k=1; p=head; h=head->next; while(h!=NULL&&k<=b-1) { k++; p=h; h=h->next; } 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 页 12 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"); while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("n"); } } 2、在单链表中删除第i个结点,若删除成功返回1,否则返回0,并要求画出图形进行描述。 解： #include #include template class SeqList { 第 13 页 共 16 页 13 public: T Delete(int i); T data[5]; int length; }; template T SeqList { int j; T x; if(length==0) throw"下溢"; if(i<1||i>length) throw"位置异常"; x=data[i-1]; for(j=i;j data[j-1]=data[j]; length--; return x; } int DelElem(LinkList *L,int i,datatype *x) { LinkList *p; p=GetList(L, i-1); /*调用按序号查找第i-1个元素地址p函数*/ 第 14 页 共 16 页 14 if (p!=NULL && p->next!=NULL) { Del_Elem (p,x); /*调用删除已知结点p之后结点函数*/ return 1; } else return 0; } int main() { SeqList cout<<"请输入单链表的长度：length="; cin>>; cout<<"请输入单链表中的数据："; for(int i=0;i<;i++) { cin>>[i]; } for(i=0;i<;i++) cout< cout< cout<<"请输入单链表中要删除数据的位置： cin>>i; 第 15 页 共 16 页 15 i="; (i); cout< for(i=0;i<;i++) cout< cout< } 第 16 页 共 16 页 16
发布评论