数据结构与算法考卷

年级：_____________专业：_____________________班级：_________________学号：_______________姓名：__________________…………年级：_____________专业：_____________________班级：_________________学号：_______________姓名：__________________…………..装….订…..线………浙江大学城市学院2011—2012学年第二学期期末考试试卷《数据结构与算法》开课单位：计算分院；考试形式：闭卷；考试时间：2012年____月____日；所需时间：120分钟题序一二三四五总分得分评卷人得分一．选择题(本大题共20题，每题1分，共20分)在定义稀疏矩阵的十字链接存储结构时，每个结点结构需包含________个域。A〕3 B〕4 C〕5 D〕6广义表的存储结构一般采用_________________。A〕链接结构 B〕顺序结构C)静态链接结构D〕都可以在计算机中算术表达式的计算是通过_______________来实现的。A〕树 B〕图 C〕队列 D栈任何一个无向连通图的最小生成树〔〕。A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在关于哈夫曼的表达中错误的选项是__________。哈夫曼树的结点个数不能是偶数。一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其为哈夫曼树，其二叉树的形状不唯一。广义表是一种_____________数据结构。A)递归的 B)非递归的 C)图状 D)树型以下图示的顺序存储结构表示的二叉树是()以下编码是无前缀编码的是__________。A)110,10,01,11B)000,001,10,00C)001,000,01,10D)权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是〔〕。 A)18 B)28 C)19 D)29在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为〔〕。A)e B)2e C)n2-e D)n2-2e将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，那么编号为49的节点的左孩子编号为〔〕。A)98 B)89 C)50 D)没有孩子以下关键字序列中，〔〕是堆。A)16,72,31,23,94,53 B)94,23,31,72,16,53C)16,53,23,94，31,72 D)16,23,53,31,94,72由同一组关键字集合构造的各棵二叉排序树()。A)其形态不一定相同，但平均查找长度相同B)其形态不一定相同，平均查找长度也不一定相同C)其形态均相同，但平均查找长度不一定相同D)其形态均相同，平均查找长度也都相同设图的邻接链表如题12图所示，那么该图的边的数目是〔〕。A)4 B)5 C)10 D)20下面哪一方法可以判断出一个有向图是否有环〔回路〕〔〕。A)求节点的度 B)拓扑排序 C)求最短路径 D)求关键路径在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为〔〕。A)e B)2e C)n2-e D)n2-2e权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是〔〕。 A)18 B)28 C)19 D)29在有n个叶子结点的哈夫曼树中，其结点总数为〔〕。 A)不确定 B)2n C)2n+1 D)2n-1设广义表L=〔〔a,b,c〕〕，那么L的长度和深度分别为〔〕。A)1和1 B)1和3堆的形状是一棵〔〕。A)二叉排序树B)满二叉树 C)完全二叉树D)平衡二叉树得分二．填空题(本大题共10空，每空2分，共20分)稀疏多项式的p(x)=1+6x5-3x12+7x50用线性表表示为_________________________。中缀表达式6+(7-(4*5)/2)*7对应的后缀表达式是_________________________。后缀表达式872-*105/+的值为________。对一棵二叉搜索树进行_______遍历时，得到的是一个有序列表。在有序表{12,23,26,37,54,60,68,75,82,96}中，当用二分法查找关键字为96的数据元素时，比拟________次后查找成功。有7个带权的结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点构造哈夫曼树，用广义表表示为___________________________，WPL=_________。权值越大的结点离树根越____的二叉树才是最优二叉树。一组元素为{55,22,88,54,10,35，77,11}假设依此序将每个元素插入到初始为空的大根堆，最后形成的堆用顺序表表示为：________________________。从该大根堆中依次删除2个元素后的堆用顺序表表示为_________________________。得分三．解答题(本大题共4题，每题6分，共24分)1.画出广义表L=((a,(b,(),c),((d),e)))带表头附加结点的链接结构示意图2.一组元素为(46,25,78,68,26,12,37,70,21)①画出按此元素排列顺序插入生成的一棵二叉搜索树，并以广义表的形式表示结果②画出从①得到的二叉树中依次删除78,68,46后最终得到的二叉树，也以广义表的形式表示结果3.无向带权图G如下：①从节点A出发，画出根据普里姆算法产生的最小生成树的过程〔写出得到各条边的顺序〕②从节点A出发，画出根据克鲁斯卡尔算法产生的最小生成树的过程〔写出得到各边的顺序〕4.一个待散列储存的数据集合为{78,76,99,60,21,27,30}，散列地址空间为HT[11]，假设采用除留取余法构造散列函数，分别采用以下两种方式处理冲突，石球每一个元素的散列地址，画出最后得到的散列表，求平均查找长度。①采用线性探查法处理冲突②采用链接法处理冲突得分四．程序填空题(本大题共10空，每空2分，共20分)1.在链式存储结构上建立一棵二叉排序树。要求在以下算法划线处填上正确的语句。#definen10typedefstructnode{intkey; structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*bt,intkey){ if(bt==NULL){ ①;bt->key=key; ②;} elseif(③)bstinsert(bt->lchild,key);else④;}voidcreatebsttree(bitree*&bt){ inti; for(i=1;⑤;i++)bstinsert(bt,random(100));}2.以下程序是采用顺序存储结构的索引查找算法。请在空白处填入适当的语句，使该算法完整。索引表及主表的存储结构定义如下：typedefstruct{IndexKeyTypeindex;//唯一标识一个子表的索引值intstart;//子表中第一个元素所在的存储位置intlength;//子表的长度}IndexItem;//索引项类型typedefIndexItemindexlist[ILMaxSize];//索引表类型typedefElemTypemainlist[MaxSize];//主表类型算法为：intIndsch(mainlistA,indexlistB,intm,IndexKeyTypeK1,KeyTypeK2){//设数组A是主表，数组B是在主表A上建立的一个索引表，m为索引表B的实际长度，//K1和K2分别为待查找的索引值和关键字inti,j;for(i=0;i<m;i++)//在索引表中查找if(⑥)break;if(i==m)return-1;//查找失败j=B[i].start;while(⑦){//在主表中查找if(K2==A[j].key) break; else⑧;}if(⑨) ⑩;//查找成功else return-1;//查找失败}得分五．程序设计题(本大题共2题，每题8分，共16分)1.设二叉排序树中的个元素值互不相同，编写一个递归算法按递减次序打印出二叉排序树中的各元素值。设函数原型为：VoidPrintBST(BTreeNode*t) 结点结构定义如下：typedefstructnode{ ElemTypedata; structnode*left;structnode*right;}BTreeNode;2.编写一个队整