在线教育网站模板,打不开网站怎么办,设计网页机构,河南郑州做网站大连理工大学2003年硕士入学试题 数据结构部分(共75分) 一、回答下列问题(20分) 1#xff0e;循环队列用数组A[0#xff0e;#xff0e;m—1)存放其数据元素。设tail指向其实际的队尾#xff0c;front指向其实际队首的前一个位置#xff0c;则当前队列中的数据元素有多少个…大连理工大学2003年硕士入学试题 数据结构部分(共75分) 一、回答下列问题(20分) 1循环队列用数组A[0m—1)存放其数据元素。设tail指向其实际的队尾front指向其实际队首的前一个位置则当前队列中的数据元素有多少个?如何进行队空和队满的判断? 2设散列表的地址空间为0~10散列函数为H(key)key11(为求余函数)采用线性探查法解决冲突并将键值序列{153650271948}依次存储到散列表中请画出相应的散列表当查找键值48时需要比较多少次? 3什么是m阶B-树?在什么情况下向一棵m阶B-树中插入一个关键字会产生结点分裂?在什么情况下从一棵m阶B-树中删除一个关键字会产生结点合并? 4什么是线索二叉树?一棵二叉树的中序遍历序列为由djbaechif前序遍历序列为abdjcefhi请画出该二叉树的后序线索二叉树。 二、请用类C或类PASCAL语言进行算法设计并回答相应问题。(45分) 1设计一非递归算法采用深度优先搜索对无向图进行遍历并对算法中的无向图的存储结构予以简单说明。 2用链式存储结构存放一元多项式Pn(x)P1xelP2xe2…Pnxen其中Pi是指数为ei的项的非零系数且满足0≤e1≤e2…enn。请设计算法将多项式BPn2(x)加到多项式APn1(x)同时对算法及链表的结点结构给出简单注释。要求利用Pnl(x)和Pn2(x)的结点产生最后求得的和多项式不允许另建和多项式的结点空间。 3(1){RlR2…Rn}为待排序的记录序列请设计算法对{R1R2…Rn}按关键字的非递减次序进行快速排序。 (2)若待排序的记录的关键字集合是{30448259513902718)请给出采用快速排序的第一趟、第二趟排序结果。 (3)若对(2)中给出的关键字集合采用堆排序请问初建的小根堆是什么? (4)当给定的待排序的记录的关键字基本有序时应采用堆排序还是快速排序?为什么? 三、算法填空(10分) 1一棵树以孩子兄弟表示法存储递归算法numberofleaf计算并返回根为r的树中叶子结点的个数(NULL代表空指针)。 typedef struct node{struct node *firstchild*nextbrother}TFNNode int numberofleaf(TFNNode *r) { int num if(rNULL) num0 else if(r-firstchildNULL) num numberofleaf (r-nextbrother) else return(num) } 2在根结点为r的二叉排序树中插人数据域值为x的结点要求插入新结点后的树仍是一棵二叉排序树(NULL代表空指针)。 二叉排序树的结点结构为 typedef struct node { int key struct node *lc,*rc }BiNode BiNode *insert(BiNode *r,int x) { BiNode *p,*q,s; s(BiNode)malloc(sizeof(BiNode)); s-keyx; s-lcNULL;s-rcNULL; qNULL; if(rNULL) {rs;return®;} pr; while( ) { qp; if( ) pp-lc; else pp-rc } if(xkey) ; else ; return; }
