2010-2011数据结构B卷及答案

第1页共6页安徽大学2010—2011学年第2学期《数据结构》考试试卷（B卷）（闭卷时间120分钟）考场登记表序号一、填空题（每小题1.5分，共15分）1．含有36个元素的有序表，进行二分查找时的判定树的深度为6。2．在一个无向图中，所有顶点的度数之和等于所有边数的2倍。3．由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为44。4．由a，b，c三个结点构成的二叉树，共有5种不同形态。5．二维数组A[0‥5][5‥10]以行序为主序存储，每个元素占4个存储单元，且A[0][5]的存储地址是1000，则A[3][9]的地址是1088。6．若串s=''soft，则其子串个数是11。7.设循环队列的空间大小为M，入队时修改队尾指针rear的语句为rear=(rear+1)%M。8．在顺序存储结构的线性表中，插入或删除一个数据元素大约需移动表中一半元素。9．下列程序段的时间复杂度是O(m*n)。for(i=0;in;i++)for(j=0;jm;j++)A[i][j]+=5;10.在数据结构中，与所使用的计算机无关的是数据的逻辑结构。二、单项选择题（每小题2分，共20分）1.数据结构可以用二元组来表示，它包括（A）集合D和定义在D上的（C）集合R。A、数据元素B、存储结构C、元素之间的关系D、逻辑结构2．已知L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在题号一二三四五六七总分得分阅卷人院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------得分得分第2页共6页p结点的后面插入一个结点s的操作（B）。A、p-next=s;s-next=p-next;B、s-next=p-next;p-next=s;C、p-next=s;s-next=p;D、s-next=p;p-next=s;3.假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列。则下列序列（A）是合法的。A、IOIIOIOOB、IOOIOIIOC、IIIOIOIOD、OIIOIOIO4、空串和空格串是（B）。A、相同的B、不相同的C、不能确定5、设W为一个二维数组，其每个数据元素占用6个字节，行下标范围从0到8，列下标范围从2到5，则二维数组W的数据元素共占用（C）个字节。A、480B、192C、216D、1446、假设在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30，则该二叉树的结点总数为（D）。A、45B、60C、46D、617.对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（A）。A、O(n2)B、O(e)C、O(n)D、O(n+e)8.对线性表进行折半查找时，要求线性表必须（C）。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排列D、以链接方式存储，且结点按关键字有序排列9、设散列表长m=14，散列函数H（key）=key%11。表中已有4个结点：addr(15)=4、addr(38)=5、addr(61)=6、addr(84)=7，其余地址为空，如用二次探测再散列解决冲突，关键字为49的结点的散列地址是（D）。A、8B、3C、5D、910.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为(B)。第3页共6页A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，38三、判断题（在正确的题后括号内打，错的则打×，每小题1分，共8分）1.链表必须要设置一个头结点。（×）2.堆排序、快速排序和希尔排序都是不稳定的排序方法。（）3.二叉树是度为2的有序树。（×）4.循环队列是指用循环链表存储的队列。（×）5.若入栈序列为abcd，则出栈序列不可能为cdab。（）6.在拓扑排序过程中，如果图中已不存在无前驱的顶点了，而此时还有顶点没有输出，则说明图中存在环。（）7．平衡二叉树是指这样的二叉树：树中任一结点的左右子树深度都相同。（×）8．在任何情况下，快速排序都是最快的。（×）四、简答题（每小题10分，共40分）1．已知二叉树如图1所示，要求：（1）将其转换为树，并画出该树；（2）分别写出对（1）所得到的树进行先根遍历和后根遍历得到的结点序列。ABCEFIDGH图12．对如图2所示的连通图，试分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskar)算法构造其最小生成树，并给出其构造过程。得分得分答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------第4页共6页3．假定一个待散列存储的线性表为（32，75，29，63，48，94，25，36，18，70），散列地址空间为HT[0~12]，若采用除留余数法构造散列函数H(key)=key%13和线性探测法处理冲突，试求出每个元素的散列地址，画出最后得到的散列表，并求出平均查找长度。散列地址为：H(32)=32%13=6H(75)=75%13=10H(29)=29%13=3H(63)=63%13=11H(48)=48%13=9H(94)=94%13=3（冲突）H1=(3+1)%13=4图21234561742253634第5页共6页H(25)=25%13=12H(36)=36%13=10（冲突）H1=(10+1)%13=11（冲突）H2=(10+2)%13=12（冲突）H3=(10+3)%13=0H(18)=18%13=5H(70)=70%13=5（冲突）H1=(5+1)%13=6（冲突）H2=(5+2)%13=7散列表为：012345678910111236299418327048756325ASL=（7*1+1*2+1*3+1*4）/10=16/10=1.64．对一组记录（50，40，95，20，15，70，60，45，80）进行快速排序，请写出每一趟排序结束时的序列。初始序列：504095201570604580第一趟结束后：{45401520}50{70609580}第二趟结束后：{204015}4550{60}70{9580}第三趟结束后：{15}20{40}4550607080{95}第四趟结束后：152040455060708095五、算法阅读题（第1小题4分，第2小题3分，共7分）1、画出执行下列程序段后得到的链表示意图。L=(LinkList)malloc(sizeof(LNode);P=L;for(k=1;k=4;k++){P-next=(LinkList)malloc(sizeof(LNode));P=P-next;P-data=2*k-1;}P-next=NULL;得分答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------第6页共6页2、已知q是指向中序线索二叉树上某个结点的指针，请阅读下面函数，说明其功能。BiTreeInX(BiTreeq){r=q-rchild;if(!q-rtag)while(!r-ltag)r=r-lchild;returnr;}六、算法设计（每小题10分，共10分）1、试设计算法，对带头结点的单链表实现就地逆置，即利用原单链表中的结点的存储单元，将链表L逆置为：其中，单链表及结点定义如下：typedefstructLNode{ElemTypedata；structLNode*next；}LNode，*LinkList；a1a2an^L…anan-1a1^L…得分