(完整word版)安工大数据结构试卷(带完整答案)

1、课程班级姓名学号密封线安 徽 工 业 大 学 试 题 纸(一)题号一二三四五六七八九十十一十二十三十四十五十六十七十八十九二十总分得分安徽工业大学20122013学年第二学期期末考试数据结构试卷(A)一、单项选择题(1M10=10分)1、在数据结构中，从逻辑上可以把数据结构分为( C )。(A)动态结构和静态结构(B)紧凑结构和非紧凑结构(C)线性结构和非线性结构(D)内部结构和外部结构2 .设某棵二叉树的中序遍历序列为 ABCD前序遍历序列为CABD则后序遍历该二叉树得到序列为(A )。(A) BADC (B) BCDA (C) CDAB(D) CBDA3 .将10阶对称矩阵压缩存储到一维数

2、组 A中，则数组A的长度最少为(C)。(A) 100(B) 40(C) 55(D) 804 .设顺序循环队列Q0: M-1的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( C)。(A) R-F (B) F-R(C) (R-F+M)%M (D) (F-R+M)%M5 .设某棵三叉树中有40个结点，则该三叉树的最小高度为( B)。(A) 3(B) 4(C) 5(D) 66 .设某强连通图中有n个顶点，则该强连通图中至少有( C)条边。 (A) n(n-1)(B) n+1(C) n(D) n(n+1)7 .设有5000

3、个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列(B)方法可以达到此目的。(A)快速排序 (B)堆排序 (C)归并排序(D)插入排序8 .若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用(D)存储方式最节省时间。(A)单链表(B) 双链表(C)单向循环(D) 顺序表9 .设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为( D )。(A) n(B) e(C) 2n(D) 2e10 .设有序表中有1000个元素，则用二分查找查找元素 X最多需要比较(B )次。(A) 25(B) 10(C) 7(D) 1二、填空题(每空格1分，共

4、17分)1 .数据的物理结构主要包括 连续存储结构 和非连续存储结构两种情况。2 .设一棵完全二叉树中有500个结点，则该二叉树的深度为 9；若用二叉链表作为该完全二叉树的存储结构，则共有 501 个空指针域。3 .设输入序列为1、2、3,则经过栈的作用后可以得到 5 种不同的输出序列。4 .设哈夫曼树中共有99个结点，则该树中有50 个叶子结点；若采用二叉链表彳为存储结构，则该树中有_100一个空指针域。5 .设一棵完全二叉树的顺序存储结构中存储数据元素为ABODEF则该二叉树的中序遍历序列为 DBEAFC。课程班级姓名学号密封线安 徽 工 业 大 学 试 题 纸（二）6 .设F和R分别表示

5、顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为 F=R7 .设二叉树中结点的两个指针域分别为Ichild 和rchild，则判断指针变量p所指向的结点为叶子结点的条件是 p->lchild=NULL&&p->rchild=NULL_ 8 .简单选择排序和直接插入排序算法的平均时间复杂度为 0mA2）。9 .快速排序算法的空间复杂度平均情况下为 O（log2n）,最坏的#况下为 0（nA2）。10 .散列表中解决冲突的两种方法是 开放地址圣?口链地址法11 .平衡因子是指 左子树的深度减去右子树的深度 12 .数组A0.6,0.8 的每个元素占4个字节，将

6、其按行优先次序存储在起始地址为2000的内存单元中，元素A5,6的地址是 22040三、应用题。（共35分）1 .已知8个待排序的记录，其关键码分别为 53, 36, 30, 91, 47, 12, 24, 85,用希尔排序、快速排序和堆排序对其进行排序，写出第一趟排 序后结果。（9分）答：希尔排序：1224309147533685（步长为5）快速排序：2436301247539185小堆排序：12365385473024912 .假定有字符a1, a2, a3, a4, a5在一篇文章中出现的次数分别为3, 2, 4, 5, 1 试以它们为叶子结点构造哈夫曼树，并计算WPL（8分）答：见三、

7、2图WPL= （3+4+5） *2+ （1+2） *3=333,已知广义表L=（a,（b,c）,（d,e）,试画出其存储结构图并利用取头函数head和取尾函数tail求出原子e。（6分）答：见三、3图e=head（tail（head（tail（tail（L）4 .（共6分）设有下列带权无向图：请用PRIM求该图的一棵最小生成树。答：见三、4图5.设一棵二叉树的先序序列为 ABDGECF片序序列为：DGBAECH就画出该二叉树。（6分）答：见三、5图四、判断题（1*10'=10分）1、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（错）2、两个栈共享一片连续内存空间时，为提高内

8、存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端3、一个栈的输入序列是12345,则栈的输出序列不可能是12345。（错）4、用是一种数据对象和操作都特殊的线性表。（对）5、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（错）6、对于一棵非空二叉树，它的根结点作为第一层，则它的第 i层上最多能有2i-1个结点。（错）7、最小代价生成树是唯一的。（错）8、归并排序的空间复杂度为O（n） （对）9、为了方便操作，一般在二叉树排序树中插入一个新结点，总是作为叶结点。（对 ）10、在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n ）。

9、（错）五、编写算法（28分）1、试编写算法将两个有序的单链表归并成一个新的有序单链表。（10分）linklist Merge(linklist A, linklist B) /* 将有序单链表合并后由函数带回*/答：LinkList Merge(LinkList A,LinkList B)LinkList p,q,r;p=A;q=B->next;while(p)if(q->next->dtat<p->data)r=q；r->next=p->next;p->next=r; q=q->next; elsep=p->next;q=q->

10、;next;if(!p&&q)p=q； return A;2、试编写算法计算二叉树中度为1的结点数。(9分)int count(bintree t) /*求二叉链表结构二叉树t度为1的结点数*/答：int count(bintree t)int count=0;PSeqStack S;bintree p=t;S=Init_SeqStack();while(p|Empty_SeqStack(S)if(p)Push_SeqStack(S,p);p=p->lichild;elsePop_SeqStack(S,&p);if(p->lchild!=NULL)&&(p->rchild=NULL)|(p->lchild=NULL)&&(p->rchild!=NULL) count+;p=p->rchild;return count;3、试编写算法在二叉排序树T中查找值为X的算法。(9分)BinSTree BSTSearch (BinSTree t , KeyType X ,) /* 二