《数据结构》已完成

数据结构（本科） 一、简答题1、对于一个栈，若输入序列依次为A,B,C,试给出所有可能的输出序 列。答：所有可能的输出序列有：ABC、ACB、BAC、BCA、CBA3、从空树开始，画出按以下次序向 2_3 树中插入关键字的建树过程20， 30， 50， 52， 60， 68， 70。画出每一步执行后的树的状态。答建战的阳也4、 已知右示有向图，给出该图的： （1） 每个顶点的入度及出度；（2） 邻接表5、设关键字集合为10，2，14，8，12，13，写出用希尔排序方法对序列进行从小到大排序排序时每一趟结束时的关键字状态（设增量 序列为 3，2，1）。答：希尔排序：d1=3: 8 2 13 10 12 14d2=2: 8 2 12 10 13 14d3=1: 2 8 10 12 13 146 、 已知某二叉树的先序序列为 ABHFDECKG ，中序序列为 HBDFAEKCG , 画出该二叉树。答：二叉树是/ / d k g后序是hdfbkgcea二、编程题1、设顺序表va中的数据元素递增有序。设计算法，将x插入到顺序表的适当位置上，并仍保持该表的有序性。答： status insert_Sq(SqList *va,ElemType x)int i;if( va-length=va-listsize) exit OVERFLOW;for( i=va-length-1;i=0 & va-elemix;-i)va-elemi+1= va-elemi;va-elemi+1=x; va-length+;return OK;2、 基于图的广度优先遍历策略写一算法，判断以邻接表方式存储的 无向图中连通分量的个数。答int visitedMAXSIZE; /指示顶点是否在当前路径上int exist path DFS(ALGraph G,int i,int j)深度优先判断有向图 G 中顶点 i 到顶点 j是否有路径,是则返回 1,否则返回0if(i=j)return 1, /i 就是 jelsevisitedi=1;for (p=G.verticesi.firstare;p;p=p-nextare)k=p-adjvex,if(!visitedk&exist _path(k,j) return 1,/i 下游的顶点到 j 有路径1/for/elseH/exist_path_DFS1、对于一个栈，若输入序列依次为A,B,C,试给出所有可能的输出序列。答：所有可能的输出序列有：ABC、ACB、BAC、BCA、CBA2、在单链表中设置头结点有什么作用？ 答：头结点就是在单链表的开始结点之前附加的一个结点，设置头结 点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针 域中，所以在链表的第一个位置上的操作就和在表的其他位置上一 样，无须进行其他特殊处理；（2）无论链表是否为空，其头指针是 指向头结点的非空指针（空表中头结点的指针域空），因此空表和非 空表的处理也就一样了2、写出在循环链表中设立尾指针而非头指针的好处。答：因为尾指针的下一个就是头指针，所以通过尾指针可以迅速的找 到头指针，但是因为是单链表，所以要通过头指针找到尾指针就必须 遍历整个链表答：1234 5234 564是连通图 5、设关键字集合为10, 2,14, 8,12,13，写出用希尔排序方法 对序列进行从小到大排序排序时每一趟结束时的关键字状态（设增量 序列为3, 2, 1）。答：希尔排序：d1=3: 8 2 13 10 12 14d2=2: 8 2 12 10 13 14d3=1: 2 8 10 12 13 146、设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10,试23010为这8个字母设计Huffman编码。答：编码顼率编码1U. Uf0001、设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表（a十a2,.,a ）逆置为（a ,a十,a_,）。12 nn n-丄丄答：void reverse(LinkList L)/*带头结点*/LinkList p;p=L-next; L-next=NULL;for(; p; p=p-next)q=p-next;p-next=L-next;L-next=p;2、基于图的广度优先遍历策略写一算法，判断以邻接表方式存储的 无向图中从顶点vi到顶点vj是否有路径存在。算法： int count (AlGraph G)for (i=0; iG.vexnum; i+) visitedi=false;sum=0;for (i=0; inextarc) k=p-adjvex;if (!visitedk) dfs(G, k);3、设散列函数H(key)二key MOD 7用线性探测再散列法解决冲突。对关键字序列 13, 2& 72, 5, 16, & 7, 11 在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。答：28呂72167513111112 5 114ASL=(1+1+1+2+5+1+1+4)/8=16/8=24、列出图中每个顶点的入度及出度，判断它是强连通图吗?3、编写递归算法，求二叉链表表示的二叉树T的叶子结点个数。#include using namespace std;typedef struct TNode/二叉树结构char nodeValue;/结点的值TNode* left;/ 左子树TNode* right;/右子树*BiTree;void CreateBiTree(BiTree &T)中序遍历方式创建二叉树，输入#代表该结点为空char nodeValue;cin nodeValue;if(nodeValue!二#)/结点非空T=new TNode;T-nodeValue二nodeValue;CreateBiTree (T-left);CreateBiTree(T-right);else T二NULL;int countLeaf(BiTree T)亠static int LeafNumHO*二-F出兰矗磐皿卅 0、迪疇鈿織* if(T)MsEH)亠if(T V _eftH H NUI_LP9P9T V right H NULL)、#出沖、处LeafNum+、二-F出磐nr莒 1e_se、莎皆-F出申处亠countLeafcr V -eft)、si=LlJy-A+aI3-F出磐nr countLeafcr V right)4ffiasMaa4-F二AA-eafNumA Aendb return 0;