资源描述：
《安徽大学数据结构期末考试题 (2).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、安徽大学2004-2005学年第2学期《数据结构》期末考试试卷（A卷）一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题后的括号内。每题2分，共20分）01．堆是一种数据结构,()是堆.A、(10,50,80,30,60,20,15,18)B、(10,18,15,20,50,80,30,60)C、(10,15,18,50,80,30,60,20)D、(10,30,60,20,15,18,50,80)02．广义表有两个重要的基本操作,取列表表头Head(Ls),和取列表表尾Tail(Ls),请利用这两个操作取出Ls中原子f的运算是(),已知广义表Ls=(
2、(a,b,c,d),(e,f,g,h)).A、Head(Tail(Ls))B、Tai(Head(Ls))C、.Head(Tail(Head(Tail(Ls))))D、Head(Tail(Tai(Head(Ls))))03.若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则他的后序序列是()A、EFGHBCDB、FEGHDCBC、FEGBHDCD、EFBGCHD04.在下列常用内部排序方法中属于不稳定排序的是()A、希尔排序,快速排序,简单选择排序,堆排序B、希尔排序,快速排序,2-路归并排序,堆排序C、直接插入排序,起泡排序,希尔排序,简单
3、选择排序D、2-路归并排序,堆排序,希尔排序,起泡排序05.有一个具有n个顶点的连通图生成的最小生成树中,具有()条边A、nB、n-1C、n+1D、2n-106.下面的二叉树中，（ ）不是平衡二叉树。A B C D07.如下图给出由七个顶点组成的无向图,从顶点1出发,对它进行深度优先遍历得到的顶点序列是()A、1354267①②B、1347625C、1534276③④⑦D、1247653⑤⑥.08.将pascal语言的数组A[0..8,0..8]按行优先次序存储在起始地址为1000的连续的内存单元中，每个存储单元
4、的长度为2，则元素A[7,3]的地址是()A、1132B、1134C、1114D、111209.依次读入数据元素序列{a,b,c,d,e,f}进栈,每进一个元素机器可要求下一个元素进栈和出栈.如此进行,则栈空时弹出的元素构成的序列不可能出现()A、{c,d,b,e,f,a}B、{d,c,e,b,f,a}C、{b,d,c,e,a,f}D、{b,e,d,a,c,f}10.从具有n个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为()A、0(n)B、0(1)C、0(logn)D、O(n²)二、填空题（每空2分，共20分） 1.对于双向链表,在
5、两个结点之间插入一个新结点时需要修改的指针共有____个。2.已知完全二叉树的第10层有10个叶子结点,则整个二叉树的结点数最多为_______个。3.有K个叶子结点的哈夫曼树，其结点的总数为 。4.对于17个元素的有序表A[1..17]作二分查找,在查找其等于A[8]的元素时需比较_____次.5.树的三种存储结构是双亲表示法、孩子表示法和 。6.对二叉排序树进行遍历，就可以得到排好序的顶点序列。7.一个“好”的算法要考虑以下标准：正确性、可读性、 和效率与低存储量需求。8.已知一个无向图的邻接表如下图所示:则从顶点Vo出发进行深度优先搜索遍
6、历得到的顶点序列为_____________和广度优先搜索得到的顶点序列为_______________.01234569.在含有n个结点的二叉链表中，其空链域个数是。三、分析计算题（第1,2,3每题7分，4,5,6每题8分，共45分）1.试以数据集{2，5，7，9，13}为权值构造一棵哈夫曼树，并计算其带权路径长度2．对于如下的连通图，请给出从顶点Vo出发，利用普里姆（Prim）算法求出它的最小生成树的过程中得到的顶点集和边集及最小生成树的权，并画出所得到的最小生成树。1268151316412920105（第2题图）3．设F={T1，T2，T3}是森林（如下
7、图所示），试将它转换为二叉树，画出所对应的二叉树。T1T2T3森林（第3题图）4．某赋权有向图如下图所示：用迪杰斯特拉（Dijkstra）算法思想，求源点A到各其余顶点的最短路径及路径长度1323311215（第4题图）5.已知一组关键字序列（35213244155486711101324130），请给出采用快速排序法进行排序时每趟划分后的排序结果（选第一个记录为枢轴（支点）分割）。6．假定一个待散列存储的数据集合为｛15,38,61,84,49,60,71,33,24,29,36｝，散列表长m=11，散列地址为HT[11]，若采用除留余数法（哈希函数H（K）＝
8、K MOD 11）和线性
