数据结构09级期末试卷(1-2班)

1浙江中医药大学滨江学院2010-2011学年第一学期计算机专业本科2009年级《数据结构与算法》考试试卷A考生姓名学号专业年级班级考试日期2011年1月21日考试时间9：00-11：00考试方式闭卷题型一二三四……总分得分登分人复核人说明：本试卷共8页，卷面100分，占总成绩60%。…………………………………………………………………………………………………一．单项选择题(本大题共_22_题，每空_2_分，共__50_分。)1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间②和运算等的学科。①A.操作对象B.计算方法C.逻辑存储D.数据映象②A.结构B.关系C.运算D.算法2.在下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)3.从逻辑上可以把数据结构分为（）两大类。得分阅卷人2A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构4.下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。5.链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比6.完成在双循环链表结点p之后插入s的操作是（）；A．p^.next:=s;s^.priou:=p;p^.next^.priou:=s;s^.next:=p^.next;B．p^.next^.priou:=s;p^.next:=s;s^.priou:=p;s^.next:=p^.next;C．s^.priou:=p;s^.next:=p^.next;p^.next:=s;p^.next^.priou:=s;D．s^.priou:=p;s^.next:=p^.next;p^.next^.priou:=s;p^.next:=s;7.执行完下列语句段后，i值为：（）intf(intx){return((x0)?x*f(x-1):2);}Main(){inti;i=f(f(1));}A．2B.4C.8D.无限递归8.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表9.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front10.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是()。A．6B.4C.3D.211.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）3A．求子串B．联接C．匹配D．求串长12.若串S=“software”,其子串的数目是①。A．8B．37C．36D．913.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。A.1175B.1180C.1205D.121014.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（ij）的位置k的关系为()。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i15.有n个叶子的哈夫曼树的结点总数为（）。【青岛大学2002二、1（2分）】A．不确定B．2nC．2n+1D．2n-116.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定17.一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；18.下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程19.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V720.二叉查找树的查找效率与二叉树的(（1）)有关,在(（2）)时其查找效率最低(1):A.高度B.结点的多少C.树型D.结点的位置(2):A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。21.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（）。A．2B.3C.4D.522.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。4A.选择B.快速C.希尔D.冒泡二．填空题（(本大题共_7_题，每题_2_分，共_14_分。)1.数据的物理结构包括的表示和的表示。2.带头结点的双循环链表L中只有一个元素结点的条件是：________3.顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。4.8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为______。5.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。6.在有n个顶点的有向图中，每个顶点的度最大可达______。7.已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。三．分析题(本大题共_3_题，每空_2_分，共_24_分。)1.下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。voidreverse（linklist&L）{p=null；q=L；while（q！=null）{(1);q-next=p；p=q；(2)___;}(3)_____;}2.下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空；操作完成后A，B保持不变，C中元素按递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A,B)实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链表的表头结点。得分阅卷人得分阅卷人5typedefstructnode{intelement;structnode*link;}NODE;NODE*A，*B，*C;NODE*append(NODE*last,inte){last-link=(NODE*)malloc(sizeof(NODE));last-link-element=e;return(last-link);}NODE*difference(NODE*A,NODE*B){NODE*C,*last;C=last=(NODE*)malloc(sizeof(NODE));while(1)___if(A-elementB-element){last=append(last,A-element);A=A-link;}elseif(2)___{A=A-link;B=B-link;}ELSE(3)___;while(4)__{last=append(last,A-element);A=A-link;}(5)___;last=C;C=C-link;free(last);return(C);}3.本程序完成将二叉树中左、右孩子交换的操作。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。typedefstructnode*tree;structnode{intdata;treelchild,rchild;}exchange(treet){treer,p;treestack[500];inttp=0;(1)_______while(tp=0){(2)_______if((3)_______)6{r=p-lchild;p-lchild=p-rchild;p-rchild=rstack[(4)_______]=p-lchild;stack[++tp]=p-rchild;}}}四．综合题(本大题共_1_题，共_12_分。)1．已知一图如下图所示：（1）．写出该图的邻接矩阵；(3分)（2）．写出1种拓扑排序；（2分）（3）．以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；（7分）得分阅卷人V1V2V4V6V8V7V5V331032546123