2010湖南工业大学09级数据结构试题(A)

课程名称：数据结构(A卷闭卷)适用专业年级：计本09级软件09通信09级网络工程09级考试时间:100分钟题号一二三四五六七八九十总分统分人签名题分242021101015100得分考生注意事项：1、本试卷共3页，试卷如有缺页或破损，请立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。(答案请写在密封线内和纸卷正面，否则不记分)一、单项选择题(每个选项1.5分，共24分)1．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n≤n+1)时，需要从前向后依次前移(A)个元素。A．n-iB．n-i+1C.n-i-1D.i2．在广义表的存储结构中，每个结点包含有(CC)个域。A．1B．2C．3D．43．若让元素1，2，3，4，5，6依次进栈，则出栈次序不可能出现的是(BB)情况。A.325641B.154623C.135426D.6543214.关键路径是事件结点网络中(A)。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路5.假设以行序为主序存储二维数组A=array[1..100][1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=(DB)。A.808B.818C.1010D.10206．若需要利用形参直接访问实参，则应把形参变量说明为(AB)参数。A．指针B．引用C．值7．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行(D)。A．q-next＝p-next；p-next＝q；B．p-next＝q-next；q＝p；C．q-next＝p-next；p-next＝q；D．p-next＝q-next；q-next＝p；8．在一个顺序队列中，队首指针指向队首元素的(BC)位置。A．后一个B．前一个C．当前9．向二叉搜索树中插入一个元素时，其时间复杂度大致为(vAAA)。A．O(㏒2n)B．O(n)C．O(1)D．O(㏒n2)10．执行下面程序段时，执行S语句的次数为(DDd)。for(i=1;i=n;i++)for(j=1;j=i;j++)S;A.n*nB.n*n/2C.n(n+1)D.n(n+1)/211.设有两个串p和q，求q在p中首次出现的位置的算法称为(CC)。A．求子串B．联接C．模式匹配D．求串长12.已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列运算的结果:tail(head(tail(C)))=(FF)。A.(a)B.AC.aD.(b)E.bF.(A)13.已知串S=‘aaab’,在KMP算法中其Next数组值为(AAA)。A．0123B．1123C．1231D．121114.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为19的结点的右孩子的编号为(CC)。A.38B.99C.39D.5015.下面关于二分查找的叙述正确的是(CD);在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分折半法查找关键码值11，需做的关键码比较次数为(AAAA).（1）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序，而且只能从小到大排列C.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储（2）A.3B.4C.5D.6湖南工业大学考试试卷纸系(院)课程名称班级姓名学号密封线第1页共3页第2页共3页二、填空题(每空1分，共20分)1．在线性表的顺序存储结构中，若一个元素所在结点的地址为P，则其后继结点的地址为p+2。2.在线性表的单链表存储结构中，若一个元素所在结点的地址为P，则其后继结点的地址为p-next。3．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为HL-next=NULL和HL-next=HL。4.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素行、列和元素的值三项。5．队列的插人操作在队尾进行，删除操作在队首进行。6．操作数是一位正整数的后缀表达式“79*45+-”的值为54。7．在一棵三叉树中，度为3的结点数有1个，度为2的结点数有2个，度为1的结点数为2个，那么度为0的结点数有5个。8．若对一棵二又树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a中，则a[i]元素的左孩子元素为a[i-1]/2，右孩子元素为a[2i+2]，双亲元素（i＞0）为a[i-1/2]。9．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。10．以顺序查找方式从长度为n的线性表中查找一个元素时，平均查找长度为n/2，时间复杂度为O(n)。11．以M分查找方法在一个线性表中进行查找时，此线性表必须是顺序存储的线性表表。12．在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为。三、运算题(每小题7分，共21分)1．有七个带权结点，其权值分别为2,9,8,4,10,12,16,试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度WPL。2．已知一个AOV网的邻接表表示如下所示(顶点为V0,V1,V2,V3,V4,V5)，请按照教材上给出的拓扑排序算法，写出此AOV网的拓扑序列。3．假定一个待散列存储的线性表(32,75,29,63,48,94,25,36,18,70)散列地址空间HT[11]，若采用除留余数法构造散列函数，处理冲突用线性探查法，试画出最后得到的散列表。设散列表为：01234567891070182548369429637532四、阅读算法题(每题5分，共10分)1．voidAD(LNode*&HL){Insert(HL，30)；//前插方法Insert(HL，50)；Delete(HL，26)；Delete(HL，55)；}假定调用该算法时以HL为表头指针的单链表中的内容为(15，26，48，55)，则调用返回后该单链表中的内容变为：50301548湖南工业大学考试答卷纸系(院)课程名称班级姓名学号密封线2．现有一个二叉树的算法如下：inttest2(BtreeNode*BT){if(BT==NULL)return0;else{inth1=test2(bt-left);inth2=test2(bt-right);if(h1h2)returnh1+1;elsereturnh2+1;}}此算法的功能是：五、构造题(10分)已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程，要求按此表完成：（1）画出这六大城市的交通网络图。（2）画出该图的邻接表表示法以及基于该邻接表的深度优先序列（假定邻接表中邻接点的编号按从小到大排列，并且遍历起始顶点为PE）。（3）画出该图的最小生成树（不必写出构建过程）。世界六大城市交通里程表(单位:百公里)解答PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M124329289113六、算法设计题(共15分)1.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。（该题9分）假定该算法的数据结构如下：typedefstructLnode{intdata;structLnode*next;}*LinkList;假定该算法的函数头为：LinkListMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc）//已知单链表La和Lb的元素按值递增排列，La和Lb分别是指向两个链表头结点的头指针，算法返回指向归并后的单链表头指针Lc。2.已知奇偶交换排序算法描述如下：第一趟对所有奇数i，将a[i]和a[i+1]进行比较，第二趟对所有偶数i，将a[i]和a[i+1]进行比较，每次比较时若a[i]a[i+1]，则将两者交换，以后重复上述两趟过程，直到整个数组有序。编写一个实现上述排序过程的算法。（该题6分）湖南工业大学考试答卷纸系(院)课程名称班级姓名学号密封线第3页共3页