数据结构与c语言程序设计答案 .是非题(2,×10) (×)1、队列逻辑上是一个表头和表尾既能插入又能删除 的线性表 (v)2、任何一个递归过程都可以转换成非递归过程 (x)3、与n个键值的集合{k1,k2,…,kn相对应的堆是唯 的 (x)4、在索引顺序表上实现分块查找,在等概率查找情 况下,其查找长度只与表中元素个数有关,而与 每块中元素个数无关 (x)5、所谓加权无向图G的最小生成树T就是将G中各 结点间的最短路径作为边所构造出来的G的子图 (x)6、在10万个随机排列的数据中,要选出5个最小的 数,采用快速排序比采用 Shell排序、堆排序及 各种直接排序法都快。 (x)7、B树查找算法的时间复杂性为0(n)。 (×)8、哈希表查找无需进行关键字的比较 (x)9、在执行某个排序过程中,出现排序码朝着最终位 置相反方向移动,则该算法是不稳定的。 (×)10、任何有向图的顶点都可以按拓扑序排序 填空题(2’×6) 1.假设用于通信的电文由8个字母组成,其频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,为这8 个字母设计哈夫曼编码,其中编码长度最大的字母的编 码是5位。 2.已知二叉树按中序遍历所得到的结点序列为 DCBGEAHFIJK,按后序遍历所得到的结点序列为 DCEGBFHKJIA,按先序遍历所得到的结点序列为 ABCDGEIHFK 3.设哈希表长度为11,哈希函数H(k)=kMD11,若输 入顺序为(18,10,21,9,6,3,16,25,7),处理冲突方法为 线性探测再散列,请构造哈希表 012345678910 21 325166187910 4.给出 0,7),要求从小到大进行排序,试给出快速排序(选第 个记录为枢轴)第一趙排序结果 74,2,5,16,1820,29,33,40,34 5.已知模式匹配的KP算法中模式串t= adabbadada’,其 next函数的值为0112112343 6.在置换选择排序中,假设工作区的容量为w,若不计输 入、输出的时间,则对n个记录的文件而言,生成所有
1 数据结构与 C 语言程序设计答案 一. 是非题（2’10） （）1、队列逻辑上是一个表头和表尾既能插入又能删除 的线性表。 （√）2、任何一个递归过程都可以转换成非递归过程。 （）3、 与 n 个键值的集合{k1,k2,…,kn}相对应的堆是唯 一的。 （）4、在索引顺序表上实现分块查找，在等概率查找情 况下，其查找长度只与表中元素个数有关，而与 每块中元素个数无关。 （）5、所谓加权无向图 G 的最小生成树 T 就是将 G 中各 结点间的最短路径作为边所构造出来的 G 的子图。 （）6、在 10 万个随机排列的数据中，要选出 5 个最小的 数，采用快速排序比采用 Shell 排序、堆排序及 各种直接排序法都快。 （）7、B 树查找算法的时间复杂性为 O（n）。 （）8、哈希表查找无需进行关键字的比较。 （）9、在执行某个排序过程中，出现排序码朝着最终位 置相反方向移动，则该算法是不稳定的。 （）10、任何有向图的顶点都可以按拓扑序排序。 二. 填空题（2’6） 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 10 4．给出一组关键字 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 个记录的文件而言，生成所有
初始归并段所需时间为_0(n10gW 三.简答题(6’×5) 1.有n个不同的英文单词,它们的长度相等,均为皿,若 n>50,m<5,试问采用什么排序方法时间复杂度最佳 为什么? 采用基数排序方法最佳 因单词长度相等,而只有26个字母组成,符合基数排序 的条件。 因m<<n,故时间复杂性由0m(n+rm))变成0(n)。 2.对于一个栈,给出输入序列A,B,C,试给出全部可能 的输出序列。若输入序列的长度为n,则可能的输出序 列有多少? ABC, ACB, BAC, BCA, CBA C2n/(n+1) 3.求2-3树的结点数和叶子数的范围并证明之。 h+1 h+1 2-1(3-1)/2 h为树的高度 用数学归纳法证明。 4.求解下列递归方程: n=1 T(n)=f aT(n/b)+c 其中a>1,b>1,a∈N,b∈N 为简单起见,设n为b的整数幂 T(n)=0(n Log ba 5.快速排序的时间复杂度是多少?试推导之。 四.程序设计题(38’) 1.假设有两个集合A和B,均以元素值递增有序排列的带
2 初始归并段所需时间为 O(n log w) 。 三. 简答题（6’5） 1． 有 n 个不同的英文单词，它们的长度相等，均为 m，若 n>>50，m<5，试问采用什么排序方法时间复杂度最佳？ 为什么？ 采用基数排序方法最佳。 因单词长度相等，而只有 26 个字母组成，符合基数排序 的条件。 因 m<<n，故时间复杂性由 O(m(n+rm))变成 O(n)。 2． 对于一个栈，给出输入序列 A，B，C，试给出全部可能 的输出序列。若输入序列的长度为 n，则可能的输出序 列有多少？ ABC，ACB，BAC，BCA，CBA C2n n /（n+1） 3． 求 2-3 树的结点数和叶子数的范围并证明之。 2 h +1 -1 ~ （3 h+1 -1）/2 2 h ~ 3h h 为树的高度 用数学归纳法证明。 4． 求解下列递归方程： 1 n=1 T（n）={ aT(n/b)+c n>1 其中 a>1, b>1, aN, bN 为简单起见，设 n 为 b 的整数幂。 T(n)=O(n L og b a ) 5． 快速排序的时间复杂度是多少？试推导之。 O(n log n) 四. 程序设计题（ 38’） 1．假设有两个集合 A 和 B，均以元素值递增有序排列的带
头结点的单链表作为存储结构。请编写算法求C=MB, 要求C按元素值递增有序排列,并要求利用原表(即表 A和表B)的结点空间存放表C。(12’) void Join(LinkList &la, LinkList &lb, Linklist &lc) i pa=la->next; pb=lb->next; Ic=la; pc=la; while(pa&&pb) if (pa->data<pb->data) ip=pa; pa=pa->next; free(p); else if(pa->data>pb->data) p=pb; pb=pb->next; free(p); 1 else i pc->next=pa; pe=pa; pa=pa->next p=pb; pb=pb->next; free(p); while(pa)p=pa; pa=pa->next; free(p); 3 while(pb)ip=pb; pb=pb->next; free(p); l pe->next-NULLs e(b); 2.从键盘上输入一串正整数,以一1为输入结束的标志, 试设计一个算法,生成一棵二叉排序树(即依次把该序 列中的结点插入二叉排序树)。(12’) void creat( BiTree *b) BiTree *s: b=NULL { scanf“%d,&x); s=(BiTNode " )malloc (sizeof( BiTNode)); s->lchild=NULL; s->rchild=NULLs insert(b, S); I while(x!=-1); void insert(b, s) BiTree *b f if (b==nUll) b=s; else if(s->data==b->data)return
3 头结点的单链表作为存储结构。请编写算法求 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->data<pb->data) {p=pa; pa=pa->next; free(p); } else if (pa->data>pb->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->data<b->data) insert(b->lchild, s); else insert(b->rchild, s) 3.试设计一个算法,在中序线索二叉树中求指定结点P在 后序遍历序列中的前驱结点。要求算法为非递归的,空 间复杂度为O(1)。(14) BiThrNode Postorder Pre( BithrTree Thrt, BiThrNode f if(p-rtag==0)q=p->rchild else (q=p: hile(q->ltag==l&& q->lchild!=Thrt) q=q->lchild; if(q->ltag==0)q=q->lchild else nULL return(q)
4 else if(s->data<b->data) 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->rchild; else {q=p; while (q->ltag= =1 && q->lchild!=Thrt) q=q->lchild; if (q->ltag= =0) q=q->lchild; else q=NULL; } return(q); }