数据结构考题.app.doc

数据结构补考必过41.如下函数实现中序遍历的非递归算法。请在程序处填入合适的内容，使其成为完整的算法typedef struct node char data struct node*Ichild, *rchild 左右孩子指针 *BinTree；void inorder( (1) ) InitStack(S) 初始化一个堆栈 Swhile (T |!StackEmpty(S) while ( (2) ) Push(S,T) (3) if ( (4) ) (5) printf(“%c”,Tdata)T=Trchild 快速排序算法。fastsort(int a，int s，int t) int i，j,temp；i=s；j=t；if(st)while（ (1) ） while (aj=j) break；while (ai=j) break；temp=aj；aj=ai；ai= temp；j=j-1；fastsort(a，s， (4) );fastsort(a， (5) ，t);假设一元多项式非零项结构定义如下typedef struct node int coef,exp;/ coef表示该项系数，exp 该项指数 struct node *next;PNode;如下函数实现两个一元n次多项式相加操作，请完成程序。void PADD(PNode *Pa, PNode *Pb, SequenceList *Pc) / 已知单链表Pa和Pb中的元素按指数递增排列。求Pa和Pb和PcPNode *pa，*pb，*pc;pa=Pa-next;/pa指向Pa第一个结点pb=Pb-next; /pb指向Pb第一个结点pc=Pa; /pc指向Pa头结点，也就是新元素的插入位置while ( (1) ) if (pa-expexp) /pa结点的指数next;else if（pa-exppb-exp）/pa结点的指数pb结点的指数，将pb插入到pc之后，pb后移 pc-next=pb; (3) ;pb=pb-next;else/pa结点的值等于pb结点的值，计算系数和 pa-coef=pa-coef+pb-coef; if(pa-coef!=0) /如果系数和不等于0，pa和pb均后移 pc-next=pa; pc=pa;pa=pa-next;pb=pb-next; else/如果系数和等于0删除pa，pb向后移 pc=pa-next; pa=pc;pb=pb-next;if( (4) ) /如果pa=null，说明Pa没有元素，将Pb的所有后继元素插入到pc之后 pc-next=pb;else/如果pb=null，说明Pb集合没有元素，将Pa的所有后继元素插入到pc之后 (5) ; 44在如图所示的的0.M-l的向量空间中建立两个栈stackl和stack2，最多有M个元素入栈到两个堆栈中，若stackl的栈顶指针为stackl.topl,stack2的栈顶指针为stack2.top，请回答如下问题：(1)给出stackl的出栈算法（2分）(2)写出stack2的入栈算法（3分）45.某个公司关系系统中需要用移动电话作为关键字进行员工的查找，现在公司只有80名员工，数据存储空间为100个存储空间，为了快速查找需要用到哈希查找，请给出哈希函数的构建方法，和线性探测序列的开放定址法冲突的解决的函数。 46.写出用prim算法求如下图从顶点V1出发的最小生成树的算法和每步求解结果。47设顺序表为（13，38，27，50，76，65，49，97），请给出由大到小排序时的初始堆和前三趟排序后堆的结构。16. AOV网是一种（ ）。A有向图 B无向图C无向无环图 D有向无环图17在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )Ae B2e Cn2e Dn22e18在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( )A.G中有弧B.G中有一条从Vi到Vj的路径C.G中没有弧D.G中有一条从Vj到Vi的路径19有n个顶点的有向完全图的弧数为( )A.n2B.2nC.n（n-1）D.2n（n+1）20为便于判别有向图中是否存在回路，可借助于( )A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法21连通网的最小生成树是其所有生成树中( )A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树22在一个长度为n的顺序表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。A. n B. n/2C. (n+1)/2 D. (n-1)/223. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。A. O(n) B. O(1)C. O(log2n) D. O(n2)24顺序查找法与折半查找法对存储结构的要求是( )A.顺序查找与折半查找均只适用于顺序表B.顺序查找与折半查找既适用于顺序表，也适用于链表C.顺序查找只适用于顺序表D.折半查找只适用于顺序表25设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序（由小到大）的结果为（ ）。A. 2，3，5，8，6B. 3，2，5，8，6C. 3，2，5，6，8D. 2，3，6，5，826设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序（由小到大）结束后前4条记录关键字为（ ）。A. 40，50，20，95 B. 15，40，60，20 C. 15，20，40，45D. 45，40，15，205