2010贵州省数据库考试含答案基础
更新时间:2023-12-28 17:43:01 阅读量: 教育文库 文档下载
- 贵州省宏观经济数据库推荐度:
- 相关推荐
1、4、 void LinkList_reverse(Linklist &L)
//链表的就地逆置;为简化算法,假设表长大于2 {
p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) {
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头 }
q->next=p;s->next=q;L->next=s; }//LinkList_reverse
2、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 29. ①试找出满足下列条件的二叉树
1)先序序列与后序序列相同 2)中序序列与后序序列相同 3)先序序列与中序序列相同 4)中序序列与层次遍历序列相同
3、若第n件物品能放入背包,则问题变为能否再从n-1件物品中选出若干件放入背包(这时背包可放入物品的重量变为s-w[n])。若第n件物品不能放入背包,则考虑从n-1件物品选若干件放入背包(这时背包可放入物品仍为s)。若最终s=0,则有一解;否则,若s<0或虽然s>0但物品数n<1,则无解。
(1)s-w[n],n-1 //Knap(s-w[n],n-1)=true (2)s,n-1 // Knap←Knap(s,n-1)
4、约瑟夫环问题(Josephus问题)是指编号为1、2、?,n的n(n>0)个人按顺时针方向围坐成一圈,现从第s个人开始按顺时针方向报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,?,如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法,模拟此过程。 #include
typedef listnode *linklist;
void jose(linklist head,int s,int m) {linklist k1,pre,p; int count=1; pre=NULL;
k1=head; /*k1为报数的起点*/ while (count!=s) /*找初始报数起点*/ {pre=k1;
k1=k1->next; count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/ { p=k1; /*从k1开始报数*/ count=1;
while (count!=m) /*连续数m个结点*/ { pre=p; p=p->next; count++; }
pre->next=p->next; /*输出该结点,并删除该结点*/ printf(\ free(p);
k1=pre->next; /*新的报数起点*/ }
printf(\输出最后一个结点*/ free(k1); }
main()
{linklist head,p,r; int n,s,m,i; printf(\ scanf(\ printf(\ scanf(\ printf(\ scanf(\
if (n<1) printf(\ else {/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n; r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/ { p=(linklist)malloc(sizeof(listnode)); p->data=i; p->next=head; head=p; }
r->next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ } }
5、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
当n=1时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立,现证明当n=m时结论成立。 设中序序列为S1,S2,?,Sm,后序序列是P1,P2,?,Pm。因后序序列最后一个元素Pm是根,则在中序序列中可找到与Pm相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m),因中序序列是由中序遍历而得,所以Si是根结点,S1,S2,?,Si-1是左子树的中序序列,而Si+1,Si+2,?,Sm是右子树的中序序列。
若i=1,则S1是根,这时二叉树的左子树为空,右子树的结点数是m-1,则{S2,S3,?,Sm}和{P1,P2,?,Pm-1}可以唯一确定右子树,从而也确定了二叉树。 若i=m,则Sm是根,这时二叉树的右子树为空,左子树的结点数是m-1,则{S1,S2,?,Sm-1}和{P1,P2,?,Pm-1}唯一确定左子树,从而也确定了二叉树。
最后,当1
6、对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个遍历序列。但对于满二叉树,任一结点的左右子树均含有数量相等的结点,根据此性质,可将任一遍历序列转为另一遍历序列(即任一遍历序列均可确定一棵二叉树)。
void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)
//将满二叉树的先序序列转为后序序列,l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1)
{post[h2]=pre[l1]; //根结点
half=(h1-l1)/2; //左或右子树的结点数
PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost 32. .叶子结点只有在遍历中才能知道,这里使用中序递归遍历。设置前驱结点指针pre,初始为空。第一个叶子结点由指针head指向,遍历到叶子结点时,就将它前驱的rchild指针指向它,最后叶子结点的rchild为空。 LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt)
//中序遍历二叉树bt,将叶子结点从左到右链成一个单链表,表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树
if(bt->lchild==null && bt->rchild==null) //叶子结点
if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 }
return(head); } //InOrder
时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)
7、冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下
沉)请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中,现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向起泡排序即相邻两趟排序向相反方向起泡)
8、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(15分)
(1)下面所示的序列中哪些是合法的?
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。
9、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存储。 10、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序遍历序列,请写出程序所缺的语句。 #define MAX 100 typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv) { TNODE *root; if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }
TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr; char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______;
for((2)_______ ; rpos ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } 11、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存储。
正在阅读:
2010贵州省数据库考试含答案基础12-28
2017年致自己的心情说说02-15
金融实习报告08-22
物料编码管理制度01-09
充满生机的早晨作文450字06-29
炸药库管理制度汇编04-25
陈虚白规中指南12-24
实战:张伟、肖宏伟、海涵三位大师对河北国税所便函企业所得税政05-15
管理学原理复习题1答案01-20
美术课评课稿06-23
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 贵州省
- 答案
- 数据库
- 基础
- 考试
- 2010
- 补牙记
- 塔式起重机安全规程(GB5144-94)
- XX年七年级地理教学计划精选
- 红岩二十章读后感 11
- 浙江省龙游中学2013届高三上学期期中考试英语试题
- 2017年秋部编版二年级语文上册《狐假虎威》第二课时教学设计
- 优秀报告范文:《开发陶艺校本课程创办特色小学的研究》开题报告
- 《空气占据空间吗》教案19
- 25岁用什么眼霜 人尽皆知的最好用的25岁眼霜推荐
- 五年级下册语文第八单元教案
- LED彩色板项目可行性研究报告-范文
- 1.1 建立二元一次方程组 同步练习 2 - 图文
- VNXe3200初始化配置之如何初上手讲解 - 图文
- 如果你只有两周的时间这是最适合你的美西旅行路线
- 人教版小学科学六年级上册第一单元《工具和机械》优质课教学设计 - 0
- 应急救援保障措施汇编
- 花儿为什么这样红教学设计
- 2010年一建工程管理讲义—08
- 优势病种中医诊疗方案临床疗效总结分析报告样稿
- 精校版高考地理二轮(通用版)复习对点练:第1部分 专题十 选修地理 专题10 第1讲 逐题 Word版含答案