2010山东省分析数据库的考试题目基础

1、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?2、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?3、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）4、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29. 试找出满足下列条件的二叉树1）先序序列与后序序列相同 2）中序序列与后序序列相同3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 5、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。6、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29. 试找出满足下列条件的二叉树1）先序序列与后序序列相同 2）中序序列与后序序列相同3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 7、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）8、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）9、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。10、约瑟夫环问题（Josephus问题）是指编号为1、2、，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedef int datatype;typedef struct nodedatatype data; struct node *next;listnode;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(%4d,p-data); free(p); k1=pre-next; /*新的报数起点*/ printf(%4d,k1-data); /*输出最后一个结点*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head; for (i=n-1;i0;i-) /*建立剩余n-1个结点*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ 11、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，.，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,.，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。Knap(S，n)若S=0则Knaptrue否则若（S0且n1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算法，将R中保存的序列循环左移p（0plchild!=NULL) if (1)_ N2+; else NL+;else if (2)_ NR+; else (3)_ ;if(t-lchild!=NULL)(4)_; if (t-rchild!=NULL) (5)_; 26.树的先序非递归算法。void example(b) btree *b; btree *stack20, *p；int top;if (b!=null) top=1; stacktop=b;while (top0) p=stacktop; top-;printf(“%d”,p-data);if (p-rchild!=null)(1)_; (2)_;if (p-lchild!=null)(3)_; (4)_;15、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。 int Similar(BiTree