2011安徽大学数据结构b卷

《2011安徽大学数据结构b卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------安徽大学2010—2011学年第2学期《数据结构》考试试卷（B卷）（闭卷时间120分钟）考场登记表序号题号一二三四五六七总分得分阅卷人得分一、填空题（每小题1分，共15分

2、）1．含有36个元素的有序表，进行二分查找时的判定树的深度为6。2．在一个无向图中，所有顶点的度数之和等于所有边数的2倍。3．由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为44。4．由a，b，c三个结点构成的二叉树，共有5种不同形态。5．二维数组A[0‥5][0‥5]以行序为主序存储，每个元素占4个存储单元，且A[0][0]的存储地址是1000，则A[3][4]的地址是1088。6．若串s=，则其子串个数是11。7.设循环队列的空间大小为M，入队时修改队尾指针rear的语句为rear=(r

3、ear+1)%M。8．在顺序存储结构的线性表中，插入或删除一个数据元素大约需移动表中一半元素。9．下列程序段的时间复杂度是O(m*n)。for(i=0;i

4、-1______条边。15.含有100个结点的树有______99______条边。第6页共6页得分二、单项选择题（每小题2分，共20分）1.数据结构可以用二元组来表示，它包括（A）集合D和定义在D上的元素之间的关系集合R。A、数据元素B、存储结构C、元素之间的关系D、逻辑结构2．已知L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入一个结点s的操作（B）。A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->ne

5、xt=s;s->next=p;D、s->next=p;p->next=s;3.假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列。则下列序列（A）是合法的。A、IOIIOIOOB、IOOIOIIOC、IIIOIOIOD、OIIOIOIO4、树最适合用来表示（C）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据5、设W为一个二维数组，其每个数据元素占用6个字节，行下标范围从0到8，列下标范围从2到5，则二维数组W的数据元

6、素共占用（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、链接方式存储第6页共6页C、顺序方式存储且结点按关键字有序排列D、链接方式存储且结点按关键字有序排列9、设散列表长m=14，散列

7、函数H（key）=key%11。表中已有4个结点：addr(15)=4、addr(38)=5、addr(61)=6、addr(84)=7，其余地址为空，如用二次探测再散列解决冲突，关键字为49的结点的散列地址是（D）。A、8B、3C、5D、910.下面序列中哪个是堆？（B）A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，86，40，38D、84，56，19，40，46，38三、判断题（在正确的题后括号内打P，错的则打×，每小题1分，共15分）得分1.链表必须要设置一个

8、头结点。（×）2.堆排序、快速排序和希尔排序都是不稳定的排序方法。（Ö）3.二叉树是度为2的有序树。（×）4.循环队列是指用链表存储的队列。（×）5.若入栈序列为abcd，则出栈序列不可能为cdab。（Ö）答题勿超装订线------------------------------装--------------------------------