山东省专升本《数据结构》答案备课讲稿.doc

《山东省专升本《数据结构》答案备课讲稿.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、山东省专升本《数据结构》答案精品文档《数据结构》模拟题2010年7月 一、单选题（每空2分，共10分）1、队列的删除操作是在（A）进行。A．队首B．队尾C．队前D．对后2、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则退栈时，用（A）语句修改top指针。A．top++;B．top=0;C．top--;D．top=N;3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（A）。A．51B．23C．53D．744、在一棵二叉树中，第4层上的结点数最多为（B）。A．31B．8C.15D．1

2、65、向堆中插入一个元素的时间复杂度为（A）。A．O(log2n)B．O(n)C．O(1)D．O(nlog2n) 二、填空题（每空1分，共20分）1、数据的逻辑结构被分为顺序结构、链接结构、索引结构和散列结构四种。2、若对一棵二叉树的结点编号从1开始顺序编码，按顺序存储，把编号为1的结点存储到a[1]中，其余类推，则a[i]元素的左孩子元素为2i+1，右孩子元素为2i+2，双亲元素(i>0)为(i-1)/2。3、从一个栈删除元素时，首先取出栈顶元素，然后再前移一位栈顶指针。4、后缀表达式“210+5*6–9/”的值为6。5、假定一棵

3、树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为2、2、0和7个。6、在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为稠密索引，若对应主表中的若干条记录，则称此索引为稀疏索引。8、对于二分查找所对应的判定树，它既是一棵二叉搜索树，又是一棵理想平衡树。三、运算题（每小题5分，共10分）1、1、空堆开始依次向堆中插入线性表（64,52,12,48,45

4、,26）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。（为小根堆）收集于网络，如有侵权请联系管理员删除精品文档 （64）（52，64）（12，64，52）（12，48，52，64）（12，45，52，64，48）（12，45，26，64，48，52） 2、在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。 A：111G：011F：10U：010Y：00Z：110（或0、1相反）四、阅读算法，回答问题（每小题5分，共20分）1、voidAA(

5、LNode*HL,constElemType&item){LNode*newptr=newLnode;newptr->data=item;LNode*p=HL;while(p->next!=HL)p=p->next;newptr->next=HL;p->next=newptr;}对于结点类型为LNode的单链表，以上算法的功能为：向单链表的末尾添加一个元素。  2、voidBB(List&L){inti=0;while(i

6、]){for(intk=j+1;k

7、(){ElemTypeA[]={1,3,5,7,9,2,4,6,8,10},B[10];TwoMerge(A,B,0,4,9);for(inti=0;i<10;i++)cout<

8、head,a[i]);LNode*p=head->next;i=0;while(p!=NULL){a[i++]=p->data;p=p->next;}ClearList(head);deletehead;} 六、编写算法(10分)编写