资源描述：
《2009数据结构试卷a答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、卷试程rnKil构结据数学大东山题号—二三*五六七八九十总分得分得分阅卷人填空题（每空2分，共30分）得分阅卷人二、问题求解（每题10分，共40分）V24V3a）在初始为空的堆栈中压入元素a，b，c，d以后，紧接着作了两次出栈操作，此吋的栈顶元素是（b）。b）高度为h（h〉0）的二叉树最少有（h）个结点。c）n个顶点的带权无向连通图的最小生成树包含（n）个顶点。d）某算法的空间花费s（n）=100nlogn+1000n+2000,其空间复杂度为（nlogn）oe）中缀表达式A-（B+C）*D/E的前缀形式是（-A/*+BCDE）。
2、f）广义表A=（（），⑻，（b，（c，（d））））的长度为（3）。g）《数据结构》课程讨论的主要内容是数据的逻辑结构、（存储结构）及^其@作i。h）若频繁地对线性表进行查找操作，该线性表应采用（顺序）存储结构。i）在n个结点的单链表屮，在P指向的结点之后插入一个结点的时间复杂度为（常数）。j）设SQ为循环队列，存储在数组d[m]中，则SQ出队操作对其队头指针front的修改是（front=（front+l）%m）ok）串中所含字符个数称为该串的（长度）。l）tail（tail（（a，b，c）））=（nullLm）n（n>0）个结点
3、二叉树对应的森林最多包含（n）棵非空树。n）数组的声明为inta[3][4][5],那么&3[2][3][4]-&&[1][1][1]=（33）。o）二叉树的前序遍历序列为ABDECFGH,屮序遍历序列为DBEACGFH,其后序遍历序列为（DEBGHFCA）。1、己知AOE网为G=（V，E）,其中，V=｛v1，v2，v3,v4，v5，v6，v7｝，E=｛al，a2，a3，a4，a5，a6,a7，a8，a9，al0｝，al:（vl，v2）3，a2:（vl，v3）2，a3:（v2，v4）7，a4:（v2，v5）8，a5:（v3，v4）
4、3，a6:（v3，v6）7，a7:（v4,v5）4,a8:（v4，v6）2，a9:（v5，v7）9，al0:（v6，v7）6;（注：顶点偶对的右括号下方的数据表示该边上的权值）。e[i]与l[i]分别表示活动al的最早开始时间与最晚开始时间，请分别求出e[i]与l[i]（l^i^l0）,填入下面的空格中。e[l:10]003322101014121[1:10]0536710101514172、带权连通图G=,其中V=｛vl，v2，v3，v4，v5，｝，E=｛（vl，v2）7，（vl，v4）6,（vl，v4）3,（v2，v3）8,（
5、v2，v4）4,（v2，v5）4,（v3，v4）6,（v4，v5）2,（注：顶点偶对右边数据为边上的权值）岡出最小生成树，所构成的图。答案不唯一，4条边是2346VI卷试程彐N谒构结据数学大东山3、己知序列（34，76,45,叉排序列树岡出该树。18，26，54，92，65）,按照逐点插入法建立一棵二得分阅卷人三、问答题（共15分）di4、假设字符-a，b，c，d，e，f的使用频度分别是0.27,0.23,0.12,0.22,0.09,0.07，写出a，b，c，d，e，f的Huffman（哈夫曼）编码。ABCDEF01110001
6、00010001110012答案不唯一，abd为两位，c是三位，ef是四位1、用C语言描述图的邻接表存储结构。(10分)#defineMAX一VERTEX一NUM20typedefstructArcNode{intadjvex;/*该弧所指向的顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/InfoType*info;/*网的权值指针)*/}ArcNode;/*表结点*/typedefstruct{VcrtcxTypcdata;/*顶点信息*/ArcNode*firstarc;}VNode，Ad
7、jList[MAX_VERTEX_NUM];/*头结点*/typedefstruct{AdjListvertices;intvexnum,arcnum;/*图的当前顶点数和弧数*/intkind;/*图的种类标志*/JALGraph;2、写出二叉树的中序遍历算法。用递归实现。(5分)StatusInOrderTraverse(BiTreeT,Status(*visit)(TelemType)){if(T){if(InOrderTraverse(T->lchild,visit))if(visit(T-〉data))if(InOrde
8、rTraverse(T->rchild,visit))returnOK;returnERROR;}elsereturnOK;得分阅卷人四、程序分析(每题5分，共15分)11、设有函数：voidfuc(intn){inti;for(i=l;i*i*i
