上海交通大学数据结构与C语言程序设计习题及答案

专业课复习资料（最新版）封面1数据结构与C语言程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一.是非 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 （2’10）（）1、队列逻辑上是一个 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 头和表尾既能插入又能删除的线性表。（）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个字母设计哈夫曼编码，其中编码长度最大的字母的编码是位。2．已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA，按先序遍历所得到的结点序列为。3.设哈希表长度为11，散列函数H(k)=kMOD11,若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 为线性探测再散列，请构造哈希表。4．给出一组关键字T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果。5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为。6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为。三.简答题（6’5）1．有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？2．对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。若输入序列的长度为n，则可能的输出序列有多少？3．求2-3树的结点数和叶子数的范围并证明之。4．求解下列递归方程：1n=1T（n）={aT(n/b)+cn>12其中a>1,b>1,aN,bN为简单起见，设n为b的整数幂。5．快速排序的时间复杂度是多少？试推导之。四.程序设计题（38’）1．假设有两个集合A和B，均以元素值递增有序排列的带头结点的单链表作为存储结构。请编写算法求C=AB，要求C按元素值递增有序排列，并要求利用原表（即表A和表B）的结点空间存放表C。(12’)2．从键盘上输入一串正整数，以—1为输入结束的标志，试设计一个算法，生成一棵二叉排序树（即依次把该序列中的结点插入二叉排序树）。(12’)3．试设计一个算法，在中序线索二叉树中求指定结点P在后序遍历序列中的前驱结点。要求算法为非递归的，空间复杂度为O（1）。(14’)1数据结构与C语言程序设计 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 一.是非题（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)=kMOD11,若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表。012345678910213251661879104．给出一组关键字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个记录的文件而言，生成所有2初始归并段所需时间为O(nlogw)。三.简答题（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，CBAC2nn/（n+1）3．求2-3树的结点数和叶子数的范围并证明之。2h+1-1~（3h+1-1）/22h~3hh为树的高度用数学归纳法证明。4．求解下列递归方程：1n=1T（n）={aT(n/b)+cn>1其中a>1,b>1,aN,bN为简单起见，设n为b的整数幂。T(n)=O(nLogba)5．快速排序的时间复杂度是多少？试推导之。O(nlogn)四.程序设计题（38’）1．假设有两个集合A和B，均以元素值递增有序排列的带3头结点的单链表作为存储结构。请编写算法求C=AB，要求C按元素值递增有序排列，并要求利用原表（即表A和表B）的结点空间存放表C。(12’)voidJoin(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);}elseif(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’)voidcreat(BiTree*b){intx;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);}voidinsert(b,s)BiTree*b,*s;{if(b==NULL)b=s;elseif(s->data==b->data)return();4elseif(s->data<b->data)insert(b->lchild,s);elseinsert(b->rchild,s);}3．试设计一个算法，在中序线索二叉树中求指定结点P在后序遍历序列中的前驱结点。要求算法为非递归的，空间复杂度为O（1）。(14’)BiThrNode*Postorder_Pre(BiThrTreeThrt,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;elseq=NULL;}return(q);} 数据结构与C语言程序设计试题 数据结构与C语言程序设计试题及答案