《数据结构》期末考试试卷试题及答案2套

《数据结构》期末考试试卷试题及答案一、简答题（每题5分，共20分）1、一棵有n个结点的k叉树采用k叉链表存储，空链域的总数目是多少？写出求解过程。2、在图的遍历中，设置访问标志数组的作用是什么？3、折半查找的前提条件是什么？4、分析冒泡排序的最好性能和最坏性能（性能即关键字比较次数和移动元素的次数）。二、单项选择题（每题1分，共10分）1、栈和队列的共同特点是()。A）只允许在端点处插入和删除元素 B）都是先进后出C）都是先进先出 D）没有共同点2、100个结点的完全二叉树采用顺序存储，从1开始按层次编号，则编号最小的叶子结点的编号应该是（）。A)100B)49C)50D)513、在顺序存储的线性表上R[3]上，从前向后进行顺序查找。若查找第一个元素的概率是1/2，查找第二个元素的概率是1/3，查找第三个元素的概率是1/6。则查找成功的平均查找长度为（）。A）7/3B）2C）3D）5/34、在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（）A)n-sB)nC)sD)s-15、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。A)N0=N1+1B)N0=Nl+N2C)N0=N2+1D)N0=2N1+l6、设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A）5B）6C）7D）87、已知单链表中的指针p所指的结点不是链尾结点，若在p结点后插入s结点，应执行（）。A)s->next=p

;p->next=s

; B)p->next=s

;s->next=p

;C)s->next=p->next

;p=s

; D)s->next=p->next

;p->next=s

;8、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 A)第i行非0元素的个数之和B)第i列非0元素的个数之和 C)第i行0元素的个数之和 D)第i列0元素的个数之和9、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是（）排序方法的基本思想。A）堆排序 B）直接插入排序 C）快速排序 D）冒泡排序10、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A）快速排序 B）堆排序 C）归并排序 D）基数排序三、填空题（每空2分，共20分）1、下面算法的时间复杂度是。i=1;while(i<=n)i=i*2;2、设线索二叉树中，判断p所指向的结点为叶子结点的条件是____________________________________。2、对任意一棵有n个结点的树，这n个结点的度之和为。3、Prim算法适合求解连通网的最小生成树。（填稀疏或稠密）4、关键路径是从源点到汇点的路径。5、深度为k的二叉树中最少有个结点，最多有个结点。6、设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________7、根据初始关键字序列(25，22，11，38，10)建立的二叉排序树的高度为_________。 8、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是。四、构造题（共30分）1、(8分)设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求：①用孩子兄弟表示法（二叉链表）表示出该树的存储结构；（2分）②将该树转化成对应的二叉树。（2分）③写出该树的先序和后序遍历序列。（4分）2、（8分）某图的邻接表存储结构为图1所示：①画出从V1出发的深度优先生成树；②给出该图的邻接矩阵存储结构。图1第四题第2小题图3、（8分）一个线性序列（36，13，40，63，22，6），假定采用散列函数Hash(key)=key%7来计算散列地址，将其散列存储在A[0~9]中，采用线性探测再散列解决冲突。构造哈希表，并计算等概率情况下的查找成功和不成功的平均查找长度。4、（6分）欲对关键字{36，15,13，40，63，22，6}从小到大排序，若采用堆排序，写出将关键字序列建初堆过程。五、算法设计题（每小题10分，共20分）注：只要求给出描述算法的子函数，不需要编写完整的实现程序。1、编写折半查找算法。（递归、非递归均可）2、已知二叉树采用二叉链表存放，该结点结构为：LChild data RChild level编写算法，将二叉树中每个结点所在的层次值置入相应的level域。《数据结构》期末考试试卷2参考答案一、简答题1、n个结点的k叉树采用k叉链表存储，链域总数为k*n，又：n=B+1,B为分支总数即非空链域总数，B=n-1,所以空链域总数为：（k-1）*n+1。2、访问标志数组的作用是：保证图中的每个顶点都被访问到，且仅访问一次。3、折半查找的前提条件是1）列表元素顺序存储；2）列表元素按关键字有序存储；4、冒泡排序最好情况：移动元素次数为0，关键字比较次数为：n-1次；冒泡排序最坏情况：移动元素次数为3n*(n-1)/2,关键字比较次数为n*(n-1)/2。二、选择题1.A 2.D 3.D 4.C 5.C6.A 7.D 8.B 9.D 10.B三、填空题1、O（log2n） 2、p->ltag==1&&p->rtag==13、n-1 4、稠密 5、最少k,最多2k-1 6、1,4,2,3 7、高度为4 8、快速排序四、构造题1.1)该树的孩子兄弟表示法为：（2分）2)转化的二叉树为:（2分）3）先序遍历序列为：ABECFGD（2分）后序遍历序列为:EBFGCDA（2分）2.1）此为有向图的邻接表表示法，该图为：2）深度优先搜索得到的遍历序列为：V1，V4，V5，V6，V2，V7，V3;深度优先生成树为：3）其邻接矩阵表示法为：顶点数组：邻接矩阵：1 V12 V23 V34 V45 V56 V67 V70 0 0 1 1 0 10 0 0 1 0 0 00 0 0 0 0 1 10 0 0 0 0 0 00 1 0 0 0 1 00 0 0 0 0 0 00 0 1 1 1 0 03、1）构造的哈希表为：（4分）地址 0 1 2 3 4 5 6 7 8 9元素 63 36 22 40 13 6 比较次数 1 1 2 1 1 2 2）（2分）查找成功时的ＡＳＬ＝（１＋１＋２＋１＋１＋２）／６＝８/６ｏｒ４/３（2分）查找不成功时的ＡＳＬ＝（４＋３＋２＋１＋１＋４＋３）／７＝１８/７4、据题意，欲得到递增有序，需要建大根堆（1分）。建初堆过程如下：五．算法设计题1、折半查找算法：1）非递归算法：intBinSearch(RecordListL,KeyTypek){low=1;high=L.length;while(low<=high){mid=(low+high)/2;if(L->r[mid].key==k)returnmid;elseif(k<L->r[mid].key)high=mid-1;elselow=mid+1;}return0;}2)递归算法intBinSearch(RecordListL,KeyTypek，intlow,inthigh)//首次调用，low=1，high=L.length;{if(low<=high){mid=(low+high)/2;if(L->r[mid].key==k)returnmid;elseif(k<L->r[mid].key)return(BinSearch(L,k,low,mid-1));elsereturn(BinSearch(L,k,mid+1,high));}}2、二叉树中每个结点的level域置值算法：利用二叉树的先序遍历给每个结点的level域置值。voidSetLevel（BiTreebt，intlayer）//首次调用时，bt参数为二叉树的根指针，layer参数值为1。 {if（bt） {bt->level=layer; SetLevel（bt->lchild，layer+1）； SetLevel(bt-)rchild，layer+1）；} }注：此题也可以借助层次遍历完成。《数据结构》期末考试试卷及答案一、简答题（每题5分，共20分）1、具有n个结点的k叉树，若采用k叉链表存储，则空链域有多少个？（要求写出求解步骤）。2、分析二叉排序树的性能（最好、最坏和平均查找性能）。3、希尔排序基本思想。4、图遍历中，设置访问标志数组visited[]的作用。二、单项选择题（每题1分，共10分）1、在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是（）A)-1~1 B)-2~2 C)1~2 D)0~12、在单链表中，下列说法正确的是（）A)单链表中头结点是必不可少的；B)单链表中头指针是必不可少的；C)在单链表中可以实现随机存取；D)单链表的存储密度小于顺序表3、假设以数组A[M]存放循环队列的元素，其头尾指示器分别为front和rear，则当前队列中的元素个数为()。A)rear-front+1B)(rear-front+1)%MC)(front-rear+M)%MD)(rear-front+M)%M4、已知广义表L=((a,b,c),(d,e,f)),运用下列（）运算可以得到结果：e。A)head（tail(L)）B)tail(head(L))C)head(tail(head(tail(L))))D)head(tail(tail(head(L))))5、线索二叉树中，某结点p是叶子结点,下列（）表达式的值为真。A)p->lchild==NULL

B)p->ltag==1&&p->rtag==1C)p->ltag==0

D)p->lchild==NULL&&p->rchild==NULL6、一个具有567个结点的完全二叉树的高度为（

）A)9

B)10

C)11

D)127、具有n个顶点的强连通图，至少有（

）条边A)n-1

B)n

C)n(n-1)

D)n(n-1)/28、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A)eB)2eC)n2-eD)n2-2e9、对关键字序列(20,15,14,18,36,40,10,21)进行快速排序，以第一个关键字为基准得到的一趟划分后的结果是（）。A)(10,15,14,18,20,36,40,21)B)(10,15,14,18,20,40,36,21)C)(10,15,14,20,18,40,36,21)D)(15,10,14,18,20,36,40,21)10、下列四种排序方法中，不稳定的方法是()。A)冒泡排序B)直接插入排序C)归并排序D)快速排序三、填空题（每空2分，共20分）1、一个算法中，基本操作的语句频度为(n3+n2log2n+14n)/n2，该算法的时间复杂度为()2、65个结点的完全二叉树，按层次，从左到右编号，则最后一个非叶子结点的编号为()。3、折半查找的两个前提条件分别是（）和（）4、一个有序表为{4，8，12，16，20，24，28}，采用折半查找法查找值为24时需要比较（）次。5、有向图的邻接表表示法中，第i条链上边表结点的个数为该顶点的（）。6、已知一个带头结点的链栈，其头指针为top；指针s指向一个新结点，要将结点s进栈，则进栈的语句应为：（）和（）。7、有一种排序算法，其时间复杂度为O（n2），关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定，则该排序算法是（）8、对二叉排序树进行中序遍历，会得到一个（）序列。四、构造题（每题6分，共30分）1、假定用于通信的某电文仅由8个字母构成，各字母在电文中出现的频率分别为（12，5，3，7，14，21，9，15）。请完成：1）构造哈夫曼树；2）为这8个字母设计不等长的Huffman编码，并计算WPL。2、已知一个图的顶点为A、B、C、D，其邻接矩阵的下三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。3、用普利姆算法从顶点A出发，构造图1所示连通网的最小生成树（写出过程）。图14、一个线性序列{38，25，74，63，52，48}，假定采用散列函数Hash(key)=key%7来计算散列地址，将其散列存储在A[0~9]中，采用线性探测再散列解决冲突。构造哈希表，并计算等概率情况下的查找成功和不成功的平均查找长度。5、对序列{57，40，38，11，13，34，48，75，6，19，9，7}，采用堆排序算法进行递减排序，请构造相应的初始堆即建初堆（只写初堆结果即可）。五、算法设计题（每题10分共20分）注：算法设计题只要求给出描述算法的子函数，不需要编写完整的实现程序。1、在一个带头结点的循环链队列中只有尾指针rear，请给出这种队列的入队和出队操作的实现过程。队列的定义如下：typedefstructNode{

QueueElementType

data;

/*数据域*/

structNode

*next;

/*指针域*/}LinkQueueNode,*LinkQueue;2、假设二叉树上的结点值各不相同，设计一个在二叉树中求值为e的结点的双亲结点。函数名已给出，如下：/*若e有双亲，则返回双亲结点指针；若e是根结点或二叉树中无e结点，则返回NULL*/BiTNode*Parent(BiTreebt，ElemTypee)《数据结构》期末考试试卷1参考答案一、简答题（5分*4=20分）1、n个结点的k叉树，共nk个链域；分支树为n-1个，即n-1个非链域，则空链域有nk-n+1个2、当二叉排序树的左右子树比较均衡时，查找性能最好，此时时间复杂度为O(nlogn)；当二叉排序树每个结点为单分支时，查找性能最差，与顺序查找类似，此时时间复杂度为O(n2)。但二叉排序的平均查找时间复杂度为O(nlogn)。3、按某个间隔，将待排序记录序列分割成若干个子序列，分别进行直接插入排序；继续缩小间隔，对每个子序列进行直接插入排序；最后再对全部记录进行一次直接插入排序。4、防止重复访问；防止遗漏访问。 二、选择题（1分*10=10分）(1~5) A D D C B(6~10) B B D B D三、填空题（2分*10=20分）1、O(n)或O(n+logn) 2、323、元素有序顺序存储 4、25、出度 6、s->next=top->next;top->next=s;7、简单选择排序 8、递增或非递减或从小到大四、构造题（6分*6=30分）1、WPL=21*2+(14+15+9+12+7)*3+(5+3)*4=245(该哈夫曼树有多种形态)2、3、4、构造的哈希表为：0 1 2 3