杭州电子科技大学2014年计算机考研数据结构真题

杭州电子科技大学2014年攻读硕士学位研究生入学考试《数据结构》试题（试题共六大题，・共6页，总分150分）姓名报考专业准考证号【所有答案必须写在答题纸上，做在试卷或草稿纸上无效】一、是非题（T正确，F错误，本大题共5小题，每小题2分，本大题共10分）.邻接表可以用以表示无向图,也可用以表示有向图。（）.算法的优劣与第法描述语言无关，但与所用计兑机有关。（）.二义树是一棵结点的度及大为2的树。（）.队列是与线性去完全不同的一种数据结构。（）.对了任何待排序序列来说，快速排序均快下起泡排序。（）二、选择题（本大题共14小题,每小题2分，本大题共28分）.递归程序可借助r（）转化为非递出程序。A.线性表A.线性表B.栈C.队列D.数组.对二义排序树按（）可得到才■序序列.A,层次遍历B.A,层次遍历B.先序遍历C中摩遍历D.后序遍历.顺序存储设计时，存储单元的地址（ >oA.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续.已知一克术表达式的中缀形式为A』B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为（）。A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则卜列情形不可能山现的是（ ）0B.G中没有弧<Vj,Vi>D.GB.G中没有弧<Vj,Vi>D.G中有弧<Vj,Vi>C.G中没。中没i,Vj>.卜列说法不正确的是（ ）。A.图的遍历姑从图中某•顶点出发访遍图中其余顶点，且使每一个顶点仅被访同一次。B.图的遍历的基本算法有两种：深度优先搜索和广度优先搜索。C.图的深度优先搜索不适用了有向图，.图的深度优先搜索是一个递归过程。.n个结点的有向完全图含有弧的数日( )。A.n*n B.n(n+1)C.n/2 D.n*(n—1).在卜面的程序段中，”xr41〃语句的频度为().for(inti巾；i<n;i什)for(intj=0:j<n;j++)x=x+l：A.0(2n)B.0(n)C：0(n2) D.0(log2n).静态链表中指计用()代替，表示结点在数蛆中的相对位置。A.内存地址B.数组卜'标 C.下一元素地址 D.左、石孩子地址10,某内排序方法的稳定性是指()OA.该排序并法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为0(nlogn)的排序方法D,假设关键字Ki=Kj ”j«n,Mj),且在排序前的序列中Ri领先丁Rj(即i<j)，在抖序后的序列中，Ri仍领先丁Rj一组记录的关键码为(47,80,57,39,41,85),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为().A.(39,41,47,57,80,85) B.(41,39,47,80,57,85)C.(41,39,47,57,80,85) D.(41,39,47,85,57,80).比较次数与序列的原始状态无关的排序方法是( )排序法。A.插入B.选择 C.起泡 D.快速.适用丁・折半杳找的表的存储方式及元素界列要求为()A.链接方式存储，元素无序 B,链接方式存储，元素有序C.顺序方式存储，元素无序 D.顺序方式存储，元素有序.卜曲关丁B和B+树的叙述中，不正确的是()B树利树都是平衡的多义树。B树和B+树都可用于文件的索引结构。B树和B•树都能有效地支持顺序检索.B树和B+树都能有效地支持随机检索。三、填空题(本大题共11空，每空2分，本大题共22分).森林的两类遍历方法为无序遍历4：先根遍历树可以借用一义树的遍历算法实现；后根遍历树可以借用二叉树的 遍历算法实现..已知一无向图G=(V,E),其中V={a,b,c,d,e)E={(atb),(a,d),(a,c),(d,c),(h,e)|现川某•一种图遍历方法从顶点a开始遍历图，得到的序列为abecd,则采用的是_遍历方法..将整型数如A[7][7J按行优先次序存储在起始地址为1000的连续的内存单元中，设好个整型元素占2字节，则元素的地址是：.第2臾共6页

1 2 3 4 5 6 7 8.设一棵一叉树BT的存储结构如F：1 2 3 4 5 6 7 8IchiIddatarchild其中Ichild.rchild分别为结点@左、右孩子指针域，data为结点的数据域.则该二叉树的高度为；第3层有:个结点（根结点为第1层），5.当r义表中的每个元素都是原子时，广义表便成了..栈是限定在表尾进行插入或删除操作•的线性表.栈对数据元素的操件是按原则进行的。设有一个空栈，现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP.PUSH.POP.PUSH,PUSH之后，输出序列是 o.对丁•个具有n个结点的单链表，在表中插入1个结点的时间及杂度为。四、图示结构题（本大题共5小题，每小题8分，本大题共40分）L已知某森林的先序遍历次序为：A,D,E,F,G,H,B,I,C,J,K,L,M,N中序遍历次序为：D,F,G,H,E,A,I,B,J.L,GN,K,C1）血山该森林2）画出该森林用孩子兄弟法表示的存储结构.根据插入次序（82,92,102,112,87,72,77,63,74）建立二义持序树。并根据该插入次序建立平衡一义树。.对卜•图所示二义树分别按前序.中序、后序遍历,给出相应的结点序列,并画出中序线索一叉树。4采用哈希困数H（k）=3*kBiod13并用开放池址法处理冲突，增地序列选取采用线性探测再散列方式，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,511）构造哈希表（画示意图）：2）装填因子：3）有找成功时的平均查找长度：4）存找不成功时的平均杳找K度。第3页共6人5.已知某无向图如卜图所示：画出两类图的存法结构示意图1)数蛆表示法(邻接矩阵)存储结构.2)邻接表存储结构.・'a,bz c；/、•・A .•<.id),ef五、阅读以下函数，指出算法的功能(本大题共5小题，每小题6分，本大题共30分)StatusAl(SqListUElenTypecur_e,ElemType&nexi_e)//L为循序线性表(inti=l;KlemType*p=L.elcm：while(i<l..length&&*p!=cur_e)(i"；p++；}if(i==L.length)returnINFEASIBLE：else(ncxi_e=*++p:returnOK;|IStatusA2(SqStack&S.SElemTypee)//S为顺序栈Iif(S.top-S.base>=S.stacksize)]S.base二(SElemType*)real」oc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW)：S.top=S.base+S.stacksizc;第4页共6页S.stacksize+=STACKINCREMENT：)*(S.top)+*=e:returnOK;intA3(HreeT)〃T为双亲袅存储的树{intk,m.def.max=O;for(k-0;k<T.n：++k)(def=l;m=T.nodes[k].parent:while(m!=-l)(m=T.nodes[mJ.parent;def”;}if(max<def)max=def;}returnmax：)voidA4(SSTable&ST)//ST为静态顺序杏找表(intfor(i=l;i<ST.length;i")(k=i;ST.elem[0]=ST.elemCi]:foT(j-i+l;j<=ST.length;j++)ifLT(ST.elem[j].key,ST.clem[0).key)ST.elcm[01-ST.elem[j];}if(k!=i){ST.elen[k]=ST.elem[i]:第5页共6页ST.elcm[i]=ST.elem[O]：voidA5(Sqlist&口〃1,为顺序表(inti,j：for(i=2;i<=Llength：++i)ifLT(L.r[i]