数据结构与C语言程序设计试题及答案.doc

数据结构与C语言程序设计答案一. 是非题（210）（）1、队列逻辑上是一个表头和表尾既能插入又能删除的线性表。（）2、任何一个递归过程都可以转换成非递归过程。（）3、 与n个键值的集合k1,k2,kn相对应的堆是唯一的。（）4、在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。（）5、所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。（）6、在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。（）7、B树查找算法的时间复杂性为O（n）。（）8、哈希表查找无需进行关键字的比较。（）9、在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。（）10、任何有向图的顶点都可以按拓扑序排序。二. 填空题（26）1 假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是 5 位。2已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK， 按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为 ABCDGEIHFJK 。3. 设哈希表长度为11， 哈希函数 H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表 。 0 1 2 3 4 5 6 7 8 9 10 21 3 25 16 6 18 7 9 104给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果 7,4,2,5,16,18,20,29,33,40,34 。5已知模式匹配的KMP算法中模式串t=adabbadada，其next函数的值为 0112112343 。6在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为 O(n log w) 。三. 简答题（65）1 有n个不同的英文单词，它们的长度相等，均为m，若n50，m5，试问采用什么排序方法时间复杂度最佳？为什么？采用基数排序方法最佳。因单词长度相等，而只有26个字母组成，符合基数排序的条件。因m1其中 a1, b1, aN, bN为简单起见，设n为b的整数幂。 T(n)=O(n Log b a )5 快速排序的时间复杂度是多少？试推导之。 O(n log n)四. 程序设计题（ 38）1假设有两个集合A和B，均以元素值递增有序排列的带头结点的单链表作为存储结构。请编写算法求C=AB，要求C按元素值递增有序排列，并要求利用原表（即表A和表B）的结点空间存放表C。(12)void Join(LinkList &la , LinkList &lb , LinkList &lc) pa=la-next; pb=lb-next; lc=la; pc=la;while (pa&pb)if (pa-datadata) p=pa; pa=pa-next; free(p); else if (pa-datapb-data) p=pb; pb=pb-next; free(p);else pc-next=pa; pc=pa; pa=pa-next; p=pb; pb=pb-next; free(p); while(pa)p=pa; pa=pa-next; free(p);while(pb)p=pb; pb=pb-next; free(p); pc-next=NULL; free(lb);2 从键盘上输入一串正整数，以1为输入结束的标志，试设计一个算法，生成一棵二叉排序树（即依次把该序列中的结点插入二叉排序树）。(12)void creat(BiTree *b)int x; BiTree *s; b=NULL; do scanf(“%d”,&x); s=(BiTNode *) malloc (sizeof(BiTNode); s-data=x; s-lchild=NULL; s-rchild=NULL; insert(b,s); while(x!=-1);void insert(b,s)BiTree *b, *s; if (b= =NULL) b=s; else if (s-data= =b-data) return();else if(s-datadata) insert(b-lchild,s); else insert(b-rchild,s);3 试设计一个算法，在中序线索二叉树中求指定结点P在后序遍历序列中的前驱结点。要求算法为非递归的，空间复杂度为O（1）。(14)BiThrNode * Postorder_Pre( BiThrTree Thrt, BiThrNode *p) if (p-rtag= = 0) q=p-rch