2013新疆维吾尔自治区数据库期末考试高级

1、 根据二叉排序树中序遍历所得结点值为增序的性质, 在遍历中将当前遍历结点与其前驱结 点值比较,即可得出结论,为此设全局指针变量 pre(初值为 null)和全局变量 flag,初值 为 true。若非二叉排序树,则置 flag 为 false。 #define true 1 #define false 0 typedef struct node {datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST( BTree t,int flag) // 判断二叉树是否是二叉排序树,本算法结束后,在调用程序中由 flag 得出结论。 { if(t!=null && flag) { Judgebst(t->llink,flag) ;// 中序遍历左子树 if (pre==null)pre=t;// 中序遍历的第一个结点不必判断 else if(pre->data<t->data )pre=t ;//前驱指针指向当前结点 else{flag=flase;} //不是完全二叉树 Judgebst ( t->rlink,flag) ; // 中序遍历右子树 }//JudgeBST 算法结束

2、在有向图 G 中,如果 r 到 G 中的每个结点都有路径可达,则称结点 r 为 G 的根结点。编写 一个算法完成下列功能: (1) .建立有向图 G 的邻接表存储结构; (2) .判断有向图 G 是否有根,若有,则打印出所有根结点的值。 3 、二路插入排序是将待排关键字序列 r[1..n] 中关键字分二路分别按序插入到辅助向量 d[1..n]前半部和后半部(注: 向量 d 可视为循环表) ,其原则为,先将 r[l]赋给 d[1] ,再从 r[2] 记录开始分二路插入。编写实现二路插入排序算法。 4、 我们可用 “破圈法” 求解带权连通无向图的一棵最小代价生成树。 所谓 “破圈法” 就是“任 取一圈,去掉圈上权最大的边” ,反复执行这一步骤,直到没有圈为止。请给出用“破圈法” 求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算 法。注:圈就是回路。 5、本题要求建立有序的循环链表。从头到尾扫描数组 A,取出 A[i] (0<=i<n ),然后到链表 中去查找值为 A[i]的结点,若查找失败,则插入。 LinkedList creat(ElemType A[],int n) //由含 n 个数据的数组 A 生成循环链表,要求链表有序并且无值重复结点 {LinkedList h; h=(LinkedList)malloc(sizeof(LNode));//申请结点 h->next=h; //形成空循环链表 for(i=0;i<n;i++) {pre=h; p=h->next; while(p!=h && p->data<A[i]) {pre=p; p=p->next;} //查找 A[i] 的插入位置 if(p==h || p->data!=A[i]) {s=(LinkedList)malloc(sizeof(LNode));

//重复数据不再输入

s->data=A[i]; pre->next=s; s->next=p;//将结点 s 链入链表中 } }//for return(h); }算法结束 6、假设 K1,?, Kn 是 n 个关键词,试解答: 试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为 K1 ,K2 ,?,Kn 时,用算法建立一棵以 LLINK / RLINK 链接表示的二叉查找树。 7、设计一个尽可能的高效算法输出单链表的倒数第 K 个元素。 8、给出折半查找的递归算法,并给出算法时间复杂度性分析。 9、 由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树, 下面程序的作用是实现由 已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序 遍历序列,请写出程序所缺的语句。 #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; if(n<=0) return NULL; ptr->info=(1)_______; int k;

for((2)_______ ; rpos<ipos+n;rpos++)

if(*rpos==*ppos) break;

k=(3)_______; 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); } 10、在有向图 G 中,如果 r 到 G 中的每个结点都有路径可达,则称结点 r 为 G 的根结点。编 写一个算法完成下列功能: (1) .建立有向图 G 的邻接表存储结构; printf(“ %c”,ptr->info);

(2) .判断有向图 G 是否有根,若有,则打印出所有根结点的值。 11 、 (1)p->rchild (5)ADDQ(Q,p->rchild) 25. (1)t->rchild!=null (2)t->rchild!=null (2) (3)N0++ (4)count(t->lchild) (3)top++ (4)ipos (5)ppos+1 (5)count(t->rchild) 26. .(1)top++ (4)stack[top]=p->lchild 27. (1)*ppos // 根结点 ( 2)rpos=ipos (3)rpos– ipos (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild)

stack[top]=p->rchild

12、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采 用递归算法。 int Similar(BiTree p,q) // 判断二叉树 p 和 q 是否相似 {if(p==null && q==null) return (1); else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束 Similar 13、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱 结点值比较,即可得出结论,为此设全局指针变量 pre(初值为 null)和全局变量 flag ,初 值为 true。若非二叉排序树,则置 flag 为 false 。 #define true 1 #define false 0 typedef struct node {datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST( BTree t,int flag) // 判断二叉树是否是二叉排序树,本算法结束后,在调用程序中由 flag 得出结论。 { if(t!=null && flag) { Judgebst(t->llink,flag) ;// 中序遍历左子树 if (pre==null)pre=t;// 中序遍历的第一个结点不必判断 else if(pre->data<t->data )pre=t ;//前驱指针指向当前结点 else{flag=flase;} //不是完全二叉树 Judgebst ( t->rlink,flag) ; // 中序遍历右子树 }//JudgeBST 算法结束

14、给定 n 个村庄之间的交通图,若村庄 i 和 j 之间有道路,则将顶点 i 和 j 用边连接,边 上的 Wij 表示这条道路的长度,现在要从这 n 个村庄中选择一个村庄建一所医院,问这所医 院应建在哪个村庄, 才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的 算法,并应用该算法解答如图所示的实例。20 分 void Hospital(AdjMatrix w,int n) //在以邻接带权矩阵表示的 n 个村庄中,求医院建在何处,使离医院最远的村庄到医院 的路径最短。 {for (k=1;k<=n;k++) //求任意两顶点间的最短路径

for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (w[i][k]+w[k][j]<w[i][j]) m=MAXINT; for (i=1;i<=n;i++) w[i][j]=w[i][k]+w[k][j]; //设定 m 为机器内最大整数。 //求最长路径中最短的一条。

{s=0; for (j=1;j<=n;j++) //求从某村庄 i(1<=i<=n)到其它村庄的最长路径。 if (w[i][j]>s) s=w[i][j]; if (s<=m) {m=s; k=i;}//在最长路径中,取最短的一条。m 记最长路径,k 记出发 顶点的下标。 Printf(“医院应建在 %d 村庄,到医院距离为 %d\n”,i,m); }//for }//算法结束 对以上实例模拟的过程略。各行中最大数依次是 9,9 ,6,7 ,9,9 。这几个最大数中最小者 为 6,故医院应建在第三个村庄中, 离医院最远的村庄到医院的距离是 6。 1、对图 1 所示的连通网 G ,请用 Prim 算法构造其最小生成树(每选取一条边画一个图) 。 15、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序 列可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否则称为非法序列。 (15 分) (1)下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回 true,否则返回 false(假定被判定的操作序列已存入一维数组中) 。


相关文档

新疆维吾尔自治区乌鲁木齐市第一中学第二学期高一年级英语期中考试答案精品版
新疆维吾尔自治区公务员录用考试面试真题2013年10月
新疆维吾尔自治区2013年5月公务员考试大纲20130515
河南省开封市第二实验高级中学2013-2014学年高一下学期第二次月考英语试卷Word版含答案
新疆维吾尔自治区第二师华山中学2018-2019学年高一年级上学期期末考试生物试卷
河南省开封市第二实验高级中学2013-2014学年高一上学期期中考试化学试题
河南省开封市第二实验高级中学2013-2014学年高一上学期期中考试数学试题(无答案)
河南省扶沟县高级中学2013届高三第三次考试地理试题
河南省开封市第二实验高级中学2013-2014学年高二下学期第二次月考语文试题Word版含答案
河南省开封市第二实验高级中学2013-2014学年高二上学期期中考试历史试题(无答案)
电脑版