国家电网数据结构与算法试题

PAGEPAGE5第5页共16页选择题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.队首，队首6.链表适合于（A）查找。A.顺序B.二分C.随机D.顺序或二分7.数据的基本单位是（A）。A.数据元素B.数据结构C.数据项D.数据对象8.下列哪个不是算法的特性（B）。A.有穷性B.可数性C.可行性D.确定性9.在表长为n的顺序表中进行线性查找，它的平均查找长度为（B）。A.ASL=nB.ASL=(n+1)/2C.ASL=+1D.ASL=log2n10.一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址是(C）。A.311B.328C11.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表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->frontC.SQ->rear==0D.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）方法。A、插入排序B、选择排序

C、冒泡排序

D、快速排序16.下列排序方法中，（B）是稳定的排序方法。A、直接选择排序B、二分法插入排序C、希尔排序D、快速排序17.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(C)的两趟排序后的结果。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,69B、32,40,21,46,69,94,90,80C21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,4021.若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（B）。A、10B、15C、21D、3422.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（A）。A、堆排序<快速排序<归并排序B、堆排序<归并排序<快速排序16.由a，b，c三个结点构成的二叉树，共有30种不同形态，若是构成树，共有9种形态。17.树所对应的二叉树其根结点的右子树一定为空。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+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,18），16第五趟：（7,8,10,15,16,18）6.一棵具有6层的满二叉树中结点数为多少？请写出计算公式。解：637.给定一个权集W={4,8,6,9,18}，画出相应的哈夫曼树，并计算WPL。8.已知二叉树的先序遍历序列为:ABDGHCEFI,中序遍历的序列为：GDHBAECIF。请完成以下各题：（1）画出此二叉树。（2）写出它的后序遍历序列。GHGHABDCEFI（1）（2）其后序遍历的序列为：GHDBEIFCA（3）8-1.对下面的带权无向图：1124365（1）画出邻接矩阵。 5 5（2）画出它的一棵最小生成树。11046 3 75 解：（1）124361243655011000边为红色的51004601000300043050060509.有一组关键字{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）3513351325D12660181798D457WPL=(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个字母设计哈夫曼编码。11-1对于下面所示的图，求出：112345（1）画出邻接矩阵和邻接表（2）求出各顶点的入度和出度解：（1）邻接矩阵12345邻接表1235∧24∧35∧41∧54∧（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;12.已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下，画出草图，写出从顶点a出发按深度优先搜索进行遍历的结点序列。0100110010000110110110110解：acacbed（2）深度优先搜索：abdce（答案不唯一）广度优先搜索：abedc（答案不唯一）13.网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。081011080301310304011040701307025425431254318111083413734716.写出图的一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出惟一一种拓扑序列。17.对图中所示图分别写出深度优先遍历和广度优先遍历的项点序列18.对图7-21中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2开始）求出其最小生成树。：19.根据下图，实现下列功能：（1）建立图的邻接表；（2）输出图的拓扑序列。四、算法设计题1、单向链表中，在p指针所指向的结点前插入一个元素x,写出相关算法,并画出图形进行描述。解：#include<stdio.h>#include<malloc.h>typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}Listnode;intInsert(Listnode*head,DataTypea,intb)//这个是插入算法{Listnode*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=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");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<iostream>#include<iomanip>template<classT>classSeqList{ public: TDelete(inti); Tdata[5]; intlength;};template<classT>TSeqList<T>::Delete(inti){ intj; Tx; if(l