《数据结构与算法》期末考试试题及答案

第第页《数据结构与算法》期末考试试题及答案一、选择题A、94,32,40,90,80,46,21,691.在规律上可以把数据结构分A.P-NE*T=Q-NE*T;FREE(Q);B、32,40,21,46,69,94,90,80成〔A〕B.Q-NE*T=P;FREE(Q);C21,32,46,40,80,69,90,94A.线性结构和非线性结构D、90,69,80,46,21,32,94,40B.动态结构和静态结构C.Q-NE*T=P-NE*T;FREE(Q);21.假设用冒泡排序对关键字序C.紧凑结构和非紧凑结构D.P-NE*T=S;S-NE*T=P;列〔18,16,14,12,10,8〕进行从D.内部结构和外部结构2.单链表中各结点之间的地址〔C〕A.需要连续B.部分需要连续C.不肯定连续D.以上均不对3.在一个长度为n的顺次表中向第i个元素〔0i=n+1〕之前插入一个新元素时，需向后移动〔B〕个元素。A、n-iB、n-i+1C、n-i-1D、i4.插入和删除操作只能在一端进行的线性表，称为〔C〕。A.队列B.线性表C.栈D.循环队列5、队列是仅允许在〔〕进行插入，而在〔〕进行删除。(A)A.队尾，队首B.队尾，队尾C.队首，队尾D.队首，队首6.链表适合于〔A〕查找。A.顺次B.二分C.随机D.顺次或二分7.数据的基本单位是〔A〕。A.数据元素B.数据结构C.数据项D.数据对象8.以下哪个不是算法的特性〔B〕。A.有穷性B.可数性C.可行性D.确定性9.在表长为n的顺次表中进行线性查找，它的平均查找长度为〔B〕。A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL=log2n10.一个线性表第一个元素的存储地址是320，每个元素的长度为3，那么第五个元素的地址是(C〕。A.311B.328C.332D.31311.设front、rear分别为循环双向链表结点的左指针和右指针，那么指针P所指的元素是双循环链表L的尾元素的条件是〔D〕。A.P==LB.P-front==LC.P==NULLD.P-rear==L12.已知P为单链表中的非首尾结点，删除P结点的后继结点Q的语句为〔A〕。

13.循环队列SQ队满的条件是〔B〕。A.SQ-rear==SQ-frontB.(SQ-rear+1)%MA*LEN==SQ-frontC.SQ-rear==0D.SQ-front==014.一组记录的排序码为〔46，79，56，38，40，84〕，那么利用堆排序的方法建立的初始堆为(B)。A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，3815.排序趟数与序列原始状态(原始排列)有关的排序方法是〔ACD〕方法。A、插入排序B、选择排序C、冒泡排序D、快速排序16.以下排序方法中，〔B〕是稳定的排序方法。A、径直选择排序B、二分法插入排序C、希尔排序D、快速排序17.数据序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中(C)的两趟排序后的结果。A、选择排序B、冒泡排序C、插入排序D、堆排序18.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为〔4，9，-1，8，20，7，15〕，那么采纳的是〔C〕排序。A、选择B、快速C、希尔D、冒泡19.一组待排序记录的关键字为〔46，79，56，38，40，84〕，那么利用快速排序，以第一个记录为基准元素得到的一次划分结果为〔C〕。A(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)20.用径直插入排序对下面四个序列进行排序〔由小到大〕，元素比较次数最少的是〔C〕。小到大的排序，所需进行的关键字比较总次数是〔B〕。A、10B、15C、21

D、3422.就排序算法所用的帮助空间而言，堆排序、快速排序和归并排序的关系〔A〕。A、堆排序快速排序归并排序B、堆排序归并排序快速排序C、堆排序归并排序快速排序D、堆排序快速排序归并排序23.最小生成树的构造可运用〔B〕算法。A.Dijkstra算法

B.Prim算法C.Haffman算法D.Floyd算法24.具有32个结点的完全二叉树的深度为〔B〕。A.5B.6C.7

D.825.在有n个叶子结点的哈夫曼树中，其结点总数为〔D〕。A．不确定B．2nC．2n+1D．2n-126.以下陈述正确的选项是〔B〕。A.二叉树是度为2的有序树B.二叉树中最多只有二棵树,且有左右子树之分C.二叉树必有度为2的结点D.二叉树中结点只有一个孩子时无左右之分27.先序为A，B，C的二叉树共有〔A〕种。A.3B.4C.5D.628.在树结构中,假设结点B有3个兄弟,A是B的父亲结点,那么A

的度为(B)。

A.3B.4C.5D.629.在一个图中，全部顶点的度数之和等于全部边数的〔B〕倍。A、1B、2C、3D、430.n个顶点的强连通图至少有〔A〕边。A、nB、n-1C、n+1D、n(n-1)31.在一个无向图中，全部顶点的度数之和等于全部边数的〔C〕倍；在一个有向图中，全部顶点的入度之和等于全部顶点出度之和的〔C〕倍。A、1/2B、2C、1

D、4无左右之分无序区〔初始为空〕的第一个32.任何一个无向连通图的最C、二叉树中必有度为2的结点记录交换的排序方法，称为选小生成树〔B〕。A、只有一棵B、一棵或多棵C、肯定有多棵D、可能不存在33.在图的表示法中，表示形式唯一的是〔A〕A、邻接矩阵表示法B、邻接表表示法C、逆邻接矩阵表示法D、逆邻接表表示法34.在一个具有n个顶点的无向图中，要连通全部顶点至少需要〔C〕条边。A.nB.n+1C.n-1D.n+235.在一个图中，全部顶点的度数之和等于图的边数的〔B〕。A．1/2B．2C．1D．436．有7个结点的有向完全图有〔C〕边。A.30B.40C.42D.5637.假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，那么叶子结点数为〔B〕。A、15B、16C、17D、4738.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是〔C〕。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙39.某二叉树的后序遍历序列为：DABEC，中序遍历序列为：DEBAC，那么前序遍历序列为〔D〕。A、ACBEDB、DECABC、DEABCD、CEDBA40.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，那么编号为45的结点的左孩子的编号为〔90〕，右孩子的编号为〔91〕。A、46B、47C、91D、9141.某树中，假设结点B有4个兄弟，A是B的父亲结点，那么A的度为〔C〕。A、3B、4C、5D、642.以下表达正确的选项是〔D〕A、二叉树是度为2的有序树B、二叉树结点只有一个孩子时D、二叉树中最多只有两棵子树，且有左右之分43.由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为〔D〕。A、23B、37C、46D、4444．在图的表示方法中，表示形式是唯一的是〔C〕。A.邻接表B.逆邻接表C.邻接矩阵D.其他44.以下关键字序列中，构成大根堆的是(D)A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，345.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为〔4，9，-1，8，20，7，15〕，那么采纳的是〔C〕排序。A.选择B.快速C.希尔D.冒泡46.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是〔C〕。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙二、填空题1.树和图都属于非线性结构。2.顺次表中规律上相邻的元素在物理位置上也相邻。3.双向链表有两个指针域，一个指向前趋，另一个指向__后继__。4.假设进栈的次序是A,B,C,D,E,写出两种出栈顺次_ABCDE、EDCBA。5.队列存取数据应遵循的原那么是先进先出。6.有20个结点的完全二叉树，编号为7的结点的父结点编号为3。7.两个序列分别为：L1={3，50，41，42，55，65，70，75}，L2={3，50，41，42，65，55，.10，5}，用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：L1。8.在排序方法中，从无序序列中选择关键字最小的记录，与择排序。9.有向图的边也称为弧，用邻接矩阵存储有向图，其第i行的全部元素之和等于顶点i的出度。10．树转换成的二叉树，其根结点的右子树肯定为空。11.二叉排序树是一种动态查找表。12.对一组记录〔50，40，95，20，15，70，60，45，80〕进行径直插入排序时，当把第7条记录60插入到有序表中时，为查找插入位置需比较15次。13.在树形结构中，树根结点没有〔前驱〕结点，其余每个结点有且只有1个前驱结点；叶子结点没有后继结点，其余结点的后继结点可以任意多个。14.在具有n个结点的二叉树中，有n+1个空指针。15.深度为k的完全二叉树至

少有2k-1个结点，至多有2k

-1个结点，假设按自上而下，从左到右次序给结点从1开始编号，那么编号最小的叶子结点的编号是。16.由a，b，c三个结点构成的二叉树，共有30种不同形态，假设是构成树，共有9种形态。17.树所对应的二叉树其根结点的右子树肯定为空。18.已知完全二叉树的第8层有8个结点，那么其叶结点数是68三、综合应用题。2.已知完全二叉树的第8层有4个结点，请计算它的叶子结点数和总结点数。〔写出计算过程〕。〔6分〕解：由题意可知，该完全二叉树有八层，其中第一层结点数为：1第二层结点数为：2第三层结点数为：4第四层结点数为：8第五层结点数为：16第六层结点数为：32第七层结点数为：64第八层结点数为：4由于第八层结点数为4，且为完全二叉树，那么第八层四个结点为叶子结点，第七层前两个结点有子结点，其余62个结点无子结点，那么第七层的后62个结点为叶子结点，故叶子结点数有4+62=66总结点数为1+2+4+8+16+32+64+4=131

一、选择题A、94,32,40,90,80,46,21,691.在规律上可以把数据结构分A.P-NE*T=Q-NE*T;FREE(Q);B、32,40,21,46,69,94,90,80成〔A〕B.Q-NE*T=P;FREE(Q);C21,32,46,40,80,69,90,94A.线性结构和非线性结构D、90,69,80,46,21,32,94,40B.动态结构和静态结构C.Q-NE*T=P-NE*T;FREE(Q);21.假设用冒泡排序对关键字序C.紧凑结构和非紧凑结构D.P-NE*T=S;S-NE*T=P;列〔18,16,14,12,10,8〕进行从D.内部结构和外部结构2.单链表中各结点之间的地址〔C〕A.需要连续B.部分需要连续C.不肯定连续D.以上均不对3.在一个长度为n的顺次表中向第i个元素〔0i=n+1〕之前插入一个新元素时，需向后移动〔B〕个元素。A、n-iB、n-i+1C、n-i-1D、i4.插入和删除操作只能在一端进行的线性表，称为〔C〕。A.队列B.线性表C.栈D.循环队列5、队列是仅允许在〔〕进行插入，而在〔〕进行删除。(A)A.队尾，队首B.队尾，队尾C.队首，队尾D.队首，队首6.链表适合于〔A〕查找。A.顺次B.二分C.随机D.顺次或二分7.数据的基本单位是〔A〕。A.数据元素B.数据结构C.数据项D.数据对象8.以下哪个不是算法的特性〔B〕。A.有穷性B.可数性C.可行性D.确定性9.在表长为n的顺次表中进行线性查找，它的平均查找长度为〔B〕。A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL=log2n10.一个线性表第一个元素的存储地址是320，每个元素的长度为3，那么第五个元素的地址是(C〕。A.311B.328C.332D.31311.设front、rear分别为循环双向链表结点的左指针和右指针，那么指针P所指的元素是双循环链表L的尾元素的条件是〔D〕。A.P==LB.P-front==LC.P==NULLD.P-rear==L12.已知P为单链表中的非首尾结点，删除P结点的后继结点Q的语句为〔A〕。

13.循环队列SQ队满的条件是〔B〕。A.SQ-rear==SQ-frontB.(SQ-rear+1)%MA*LEN==SQ-frontC.SQ-rear==0D.SQ-front==014.一组记录的排序码为〔46，79，56，38，40，84〕，那么利用堆排序的方法建立的初始堆为(B)。A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，3815.排序趟数与序列原始状态(原始排列)有关的排序方法是〔ACD〕方法。A、插入排序B、选择排序C、冒泡排序D、快速排序16.以下排序方法中，〔B〕是稳定的排序方法。A、径直选择排序B、二分法插入排序C、希尔排序D、快速排序17.数据序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中(C)的两趟排序后的结果。A、选择排序B、冒泡排序C、插入排序D、堆排序18.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为〔4，9，-1，8，20，7，15〕，那么采纳的是〔C〕排序。A、选择B、快速C、希尔D、冒泡19.一组待排序记录的关键字为〔46，79，56，38，40，84〕，那么利用快速排序，以第一个记录为基准元素得到的一次划分结果为〔C〕。A(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)20.用径直插入排序对下面四个序列进行排序〔由小到大〕，元素比较次数最少的是〔C〕。小到大的排序，所需进行的关键字比较总次数是〔B〕。A、10B、