《数据结构》练习题及答案 清华出版社

数据结构模拟题2010年7月一、单选题 （每空2分，共10分）1、队列的删除操作是在（ ）进行。A队首 B队尾 C队前 D对后2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。Atop+; Btop=0; Ctop-; Dtop=N;3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。A51 B23 C53 D744、在一棵二叉树中，第4层上的结点数最多为（ ）。A31 B8 C.15 D165、 向堆中插入一个元素的时间复杂度为（ ）。AO(log2n) BO(n) CO(1) D O(nlog2n)二、填空题（每空1分，共20分）1、数据的逻辑结构被分为_、_、_和_四种。2、若对一棵二叉树的结点编号从1开始顺序编码，按顺序存储，把编号为1的结点存储到a1中，其余类推，则ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i0)为_。3、从一个栈删除元素时，首先取出 ，然后再前移一位 。4、后缀表达式“2 10 + 5 * 6 9 /”的值为 。5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J),K)，则度为3、2、1、0的结点数分别为_、_、_和_个。6、在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。 7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为_索引，若对应主表中的若干条记录，则称此索引为_索引。8、对于二分查找所对应的判定树，它既是一棵_ _，又是一棵_ _ _。三、运算题（每小题5分，共10分）1、 1、 空堆开始依次向堆中插入线性表（64,52, 12,48,45,26）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。（为小根堆）2、在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。四、阅读算法，回答问题（每小题5分，共20分）1、void AA (LNode * HL,const ElemType & item) LNode * newptr=new Lnode ; newptr-data=item; LNode *p=HL; while ( p-next!=HL ) p=p-next;newptr-next=HL;p-next=newptr;对于结点类型为LNode的单链表，以上算法的功能为：2、void BB(List &L)int i=0;while (iL.size)int j=i+1;while (jL.size)if(L.listj = =L.listi)for (int k=j+1;kL.size;k+)L.listk-1=L.listk;L.size-;else j+;i+;以上算法的功能为：3、void CC(BTreeNode * & BST )ElemType a6 =45，23，78，35，77，25；BST=NULL；for( int i=0,i6;i+)Insert(BST , ai);调用该算法后，生成的二叉搜索数的中序序列为：4、void DD ( )ElemType A =1,3,5,7,9,2,4,6,8,10,B10;TwoMerge(A, B,0,4,9);for ( int i=0; i10; i+)coutBi” “;coutendl; 调用该算法后，输出结果为：五、算法填空，在画有横线的地方填写合适的内容(10分)。利用单链表进行数据排序。void LinkSort (ElemType a ,int n)LNode * head=new LNode;InitList (head);int i;for (i=0;inext;i=0;while ( )ai+=p-data; ClearList (head); 六、编写算法(10分)编写一个非递归算法，在稀疏有序索引表中二分查找出给定值K所对应的索引项，即索引值刚好大于等于K的索引项，返回该索引项的start域的值，若查找失败则返回-1。数据结构模拟题答案及评分标准（供参考）一、单选题 （每空2分，共10分）1、A 2、 A 3、A 4、 B 5 、A 二、填空题（每空1分，共20分）1、顺序结构、链接结构、索引结构、散列结构2、2i+1、2i+2、 3、栈顶元素、栈顶指针 4、6 5、2、2、0、76、n(n-1)/2 、n(n-1) 7、稠密、稀疏 8、二叉搜索树、理想平衡树三、运算题（每小题5分，共10分）1、（64）（52，64）（12，64，52）（12，48，52，64）（12，45，52，64，48）（12，45，26，64，48，52）2、 A：111 G：011 F：10U：010 Y：00 Z：110（或0、1 相反）四、阅读算法，回答问题（每小题5分，共20分）1、向单链表的末尾添加一个元素。2、删除线性表中所有重复的元素。3、23 25 35 45 77 784、 1 2 3 4 5 6 7 8 9 10五、算法填空，在画有横线的地方填写合适的内容(10分)。p!=NULLp=p-next;delete head;六、编写算法(10分)int Binsch(IndexList B, int m, IndexKeyType K)int low=0, high=m-1;while (low= high)int mid=(low+high)/2;if (K