Question

求c++数据结构问题 1.判断有向树是以v0为根的生成树； 2.求无向图的边数0。

Answer 1

、抽象数据类型 循环队列 最优二叉树 邻接矩阵和邻接表 稳定排序和不稳定排序
2、四种逻辑结构的前驱和后继的关系
3、顺序存储结构要求存储空间是连续的、元素之间的关系用下标表示；链式存储要求存储空间是不连续的，元素之间的关系用指针表示。
4、T(n)和S(n)分别表示什么？
5、何谓上溢和下溢。溢是当一个超长的数据进入到缓冲区时，超出部分被写入上级缓冲区，上级缓冲区存放的可能是数据、上一条指令的指针，或者是其他程序的输出内容，这些内容都被覆盖或者破坏掉。可见一小部分数据或者一套指令的溢出就可能导致一个程序或者操作系统崩溃。

下溢是当一个超长的数据进入到缓冲区时，超出部分被写入下级缓冲区，下级缓冲区存放的是下一条指令的指针，或者是其他程序的输出内容。

5、广义表表长和深度求解
6、无向完全图中边的个数为多少
若一个完全无向图具有n条边，则该图的顶点个数为2n+1/4)+1/2
7、折半查找的前提是？索引查找的表结构的构成？
前提是必须有有序表。只能由于静态查找
8、什么排序的比较次数与元素的初始状态无关。 选择排序和归并排序
9、在一个长度为n的顺序表中第i个元素（1≤i≤n）后插入一个元素时，需向后移动多少元素 n-i-1
10、head和tail的综合使用
11、在有向图中每个顶点的度等于该顶点的( n(n-1)|2 )。
12、二叉树的深度求解
13、二叉树的深度求解
14、将一颗已知树转换成二叉树，写出后序遍历的结果。
#include "iostream.h"
#include "stdlib.h"
#define MaxSize 100
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node *left,*right;
}BTree; //树的单元结构

void creatree(BTree **BT,ElemType *str)
{
//根据括弧表示法创建一棵二叉树
BTree *stack[MaxSize],*p;
int top=-1,k,j=0; //top为栈指针,k指定是左还是右孩子,j为str指针
char ch;
*BT=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':
top++;
stack[top]=p;
k=1; //标示为左孩子
break;//////////////////你这里少了break;
case ')':
top--;
break;
case ',':
k=2;//标示为右孩子
break;
default:
p=(BTree *)malloc(sizeof(BTree));
p->data=ch;
p->left=p->right=NULL;
if(*BT==NULL) //根结点
*BT=p;
else{
switch(k)
{
case 1:
stack[top]->left=(BTree *)malloc(sizeof(BTree));
stack[top]->left=p;break;
case 2:
stack[top]->right=(BTree *)malloc(sizeof(BTree));
stack[top]->right=p;
}
}
}
j++;
ch=str[j];
}
}

void postorder(BTree *BT)
{ //后序遍历
if(BT!=NULL)
{
postorder(BT->left);
postorder(BT->right);
cout<<BT->data;
}
}

int BTreeDepth(BTree *BT)
{ //求二叉树的深度
int leftdep,rightdep;
if(BT==NULL)
return 0;
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if(leftdep>rightdep)
return leftdep+1;
else
return rightdep+1;
}
}

int nodecount(BTree *BT)
{ //求结点数
if(BT==NULL)
return 0;
else
{
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
}

int leafcount(BTree *BT)
{ //叶子结点
if(BT==NULL)
return 0;
else if(BT->left==NULL && BT->right==NULL)
return 1;
else
return (leafcount(BT->left)+leafcount(BT->right)+1);
}

int noleafcount(BTree *BT){ //非叶子结点
if(BT==NULL)
return 0;
else if(BT->left==NULL && BT->right==NULL)
return 0;
else
return(noleafcount(BT->left)+noleafcount(BT->right)+1);
}

int main(){
char yumensi[100],tianla;
int i=0;
cout<<"请用括号表示法输入一棵二叉树并以一个.结束,例如"<<"'A(B(D,E(H,I)),C(G)).'"<<endl;
cout<<"请注意正确输入因为程序不能判断输入是否正确!!否则后果自负!!"<<endl;
cin>>tianla;
while(tianla!='.')
{
yumensi[i]=tianla;
i++;
cin>>tianla;
}
yumensi[i]='\0';
BTree *tree;
creatree(&tree,yumensi);
cout<<"先序遍历结果:";
preorder(tree); cout<<endl;
cout<<"中序遍历结果:";
inorder(tree); cout<<endl;
cout<<"后序遍历结果:";
postorder(tree); cout<<endl;
cout<<"深处为:"<<BTreeDepth(tree)<<endl;
cout<<"结点个数:"<<nodecount(tree)<<endl;
cout<<"叶子结点个数:"<<leafcount(tree)<<endl;
cout<<"非叶子结点个数:"<<noleafcount(tree)<<endl;
cout<<"BY: B.Lee 版权没有，盗版不究"<<endl;
return 1;
}
15、已知有向图，请给出该图的邻接表的表示和计算顶点的度
16、写出直接插入排序的排序过程。
for(i = 1; i < n; ++i)
{
int temp = a[i];
for (j = i; j > 0 && temp < a[j - 1]; --j)
{
a[j] = a[j - 1];
}
a[j] = temp;
17、给定四个结点A,B,C,D的权值来构造一棵哈夫曼树，写出哈夫曼编码，求出平均编码长度。
18、对给定的带权无向图用PRIM算法求出最小生成树，并写出计算过程。
PRIM(简单版) 最小生成树算法 (Minimum Spanning Tree)
* 输入：图g； // 有向图或者无向图
* 输出：(1)最小生成树长sum；
* (2)最小生成树prev。
* 结构: 图g用邻接矩阵表示，最短边长dist用数组表示。
* 算法：Prim算法
* 复杂度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n; // n : 顶点个数
vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示)
vector<bool> known; // known : 各点是否已经选取
vector<int> dist; // dist : 已选取点集到未选取点的最小边长
vector<int> prev; // prev : 最小生成树中各点的前一顶点
int s; // s : 起点(start)
int sum; // sum : 最小生成树长

bool Prim() // 贪心算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起点到自身的路径长为0。
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i < n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 寻找未知的最短路径长的顶点v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，将顶点v设为已知，
sum += dist[v]; // 调整最小生成树长
for (int w = 0; w < n; ++w) // 遍历所有v指向的顶点w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。 */
}
return i == n; // 如果选取顶点个数为n，成功。
}

int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;

s = 0; // 起点任选
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}

system("pause");
return 0;
}
19、对于给定7个数据元素的有序表,采用顺序查找, 假设查找表中每个元素的概率相同,求查找成功时的平均查找长度。
20、写出不带头结点的单链表的合并算法,删除重复结点。
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}LNode,*LinkList;
LinkList Create_LinkList()
{
LinkList L=NULL;
LNode *s,*h=NULL;
int x;
scanf("%d",&x);
while(x!=-1)
{
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
if(L==NULL) L=s;
else h->next=s;
h=s;
scanf("%d",&x);
}
if(h!=NULL) h->next=NULL;
return L;
}
void pur_linklist(LinkList H)
{
LNode *q,*r;
q=H;
if(q==NULL) return;
while(q->next)
{
if(q->data==q->next->data)
{ r=q->next;
q->next=r->next;
free(r);
q=q->next;
}
else q=q->next;
}
}
main()
{
LinkList H;
LNode *p;
H=Create_LinkList();
pur_linklist(H);
p=H;
while(p)
{
printf("%d\n",p->data);
p=p->next;
}
}

#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAXSIZE 100
typedef int DataType;
typedef struct
{
DataType * elem; //线性表的基地址
int length; //线性表当前的长度
int listsize; //线性表当前分配的最大存储内容容量
}SeqList;

void CreatList(SeqList *L)
{
cout<<"输入线性表当前长度：";
cin>>L->length;

//分配空间
L->elem = (int*) malloc(L->length*sizeof(int));
cout<<"请按从小到大升序输入线性表的各个元素";
for(int i = 0;i< L->length;i++)
{
cin>>L->elem[i];
}
L->listsize = L->length;
}

void MergeSeqList(SeqList *A, SeqList *B, SeqList *C)
{
DataType *pa, *pb, *pc, *palast, *pblast;
pa = A->elem; pb = B->elem;
C->length = A->length + B->length;
C->elem = (DataType*)malloc(C->length*sizeof(DataType));
if(!C->elem) exit(-1);

palast = A->elem + A->length - 1;

pblast = B->elem + B->length - 1;

pc = C->elem;

while(pa <= palast && pb <= pblast)
{
if(*pa <= *pb)
{
*pc = *pa;
pc++;
pa++;
}
else
{
*pc=*pb;
pc++;
pb++;
}
}
while(pa<=palast) {
*pc=*pa;
pc++;
pa++;
}

while(pb<=pblast)
{
*pc=*pb;
pc++;
pb++;
}
}

void DisList(SeqList *L)
{
for(int i=0;i<L->length;i++)
{
cout<<L->elem[i]<<" ";
}
cout<<endl;
}

void main()
{
SeqList A,B,C;
cout<<"顺序表A："<<endl;
CreatList(&A);
cout<<"顺序表B："<<endl;
CreatList(&B);
MergeSeqList(&A,&B, &C);
cout<<"顺序表C："<<endl;
DisList(&C);
}