资源描述：
《2011安徽大学数据结构a卷_》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------安徽大学2010—2011学年第2学期《数据结构》考试试卷（A卷）（闭卷时间120分钟）考场登记表序号题号一二三四五六七总分得分阅卷人得分一、填空题（每小题1分，共15分）1.设循环队列的空
2、间大小为M，头指针和尾指针分别为front和rear，则判断队列满的语句为。2.n个顶点的连通图至少有___________条边。3．下列程序段的时间复杂度是。for(i=2;i<=n;i++)for(j=2;j<=i-1;j++)s++;4.广义表L=（(a，b)，（c）），进行Head（L）操作后的结果为。5．由带权为7、5、2、4的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。6.在栈中删除栈顶元素的出栈函数是。7.数据结构在计算机中的表示称为数据的结构。8．在无向图的邻接表中，表结点的个数等于边数的倍。9．二维数组A[0‥
3、4][0‥6]以行序为主序存储，每个元素占2个存储单元，且A[0][0]的存储地址是30，则A[4][5]的地址是。10.深度为5的二叉树至多有个结点。11．子串p=’or’在主串s=’HelloWord’中的位置是。12.含有100个结点的树有____________条边。13．含有11个元素的有序表，进行二分查找时的判定树的深度为。14．在树中，一个结点的直接孩子结点的个数称为该结点的。15．在顺序存储结构的线性表中，插入或删除一个数据元素大约需移动表中元素。第7页共7页得分二、单项选择题（每小题2分，共20分）1.在数据结构中，从
4、逻辑上可以把数据结构分成（）。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构2．在一个单链表中，若要删除p结点的后续结点，则应执行（）。A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、delete(p->next);D、p=p->next->next;3.对于一个栈，如果输入序列为123,则共有（）种可能的输出序列。A、3B、4C、5D、64、设森林F中有3棵树。第一、第二和第三棵树的结点个数分别是m1,m2和m3，则与
5、森林F对应的二叉树根结点的右子树上的结点个数是（）。A、m3B、m2+m3C、m1D、m1+m25、二维数组M[i,j]的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素（）的起始地址相同。A、M[2,4]B、M[3,4]C、M[3,5]D、M[4,4]6、若一棵完全二叉树有1450个结点，则叶子结点的个数为（）。A、1B、724C、725D、47.对用邻接表表示的图进行任深度优先搜索遍历时，其时间复杂度为（）。A、O(n2)B、O
6、(e)C、O(n)D、O(n+e)8.在表长为n的顺序表中，实行顺序查找，在查找不成功时，与关键字比较的次数为（）。A、nB、1C、n+1D、n-19、设散列表的地址区间为0-17，散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列(26,25,72,38,8,18,59)依次存储到散列表中。第7页共7页存放元素59需要搜索的次数是（）。A、2B、3C、4D、510.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（）。A、79，46，56，38，40，84B、84，79，
7、56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，38，46三、判断题（在正确的题后括号内打P，错的则打×，每小题1分，共15分）得分1．冒泡排序是插入排序的一种。（）2．具有n个结点的完全二叉树的深度为log2n。（）3．希尔排序在效率上较直接接入排序有较大的改进。但是不稳定的。（）4.赫夫曼树中不存在度为1的结点。（）5．栈在数据中的存储原则是先进先出。（）6．平衡二叉树是指这样的二叉树：树中任一结点的左右子树深度之差的绝对值不超过2。（）7.直接插入排序、快速排序和堆排序都是不稳定的排序方法。
8、（）8.一个无向图的邻接矩阵一定是一个对称矩阵。（）答题勿超装订线------------------------------装---------------------------------------
