数据结构期末总复习题.docx

19套题1一、选择题（每题2 分，共15题，总计30 分）1 以下叙述中正确的是_。A 数组是数据的最小单位B 数据对象就是一组数据元素的集合C 顺序存储方式只能用于存储线形结构D 树对应到的二叉树其根结点的右子树总是空的2 一个数组的第一个元素的存储地址是100，每个元素长度为2，则第5个元素的存储地址是_。A 110 B 108 C 100 D 1203 一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_。A a,b,c,d,e B e,d,c,b,aC d,c,e,a,b D d,e,c,b,a4 栈的特点是_。A 先进先出 B 先进后出 C 随即存取 D 链式实现5 一个队列的入队顺序是1，2，3，4，5，那么出队顺序是_。A 5，4，3，2，1 B 1，2，3，5，4C 1，2，3，4，5 D 1，3，2，4，56 向一个长度为10的数组的第5个元素之前插入一个元素时，需向后移动_个元素。A 3 B 5 C 6 D 77若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_。 A 48 B 49 C 50 D 518 高度为6的完全二叉树中第4层结点的个数为_。A 2 B 4 C 8 D 169具有n个顶点的无向完全图，其边数为_。A n B n(n-1) C n(n-1)/2 D n210具有n个顶点的有向完全图，其边数为_。A n B n(n-1) C n(n-1)/2 D n211在有7个顶点的无向图中至少有_条边才能确保该图连通。A 1 B 6 C 7 D 2112对于一个有n个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是_。A n-1 B n C (n-1)2 D n213在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_。A 2 B 3 C 4 D 614 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_。AO( n) B O(nlogn) C O(n2) D O(logn)15 在待排序元素基本有序的前提下，效率最高的排序方法是_。A 插入排序 B 选择排序 C 快速排序 D 归并排序二、填空题 （每空2 分，共20空，总计40 分）1 判定下列程序段的时间复杂度为_，其中语句Aij频度为_for(i=0;in;i+) for(j=0;j=n;j+) Aij=0; Bji=1;2对线性表进行二分查找时，要求线性表必须_且_。3 对于一个头指针为head的带头结点的单链表，判定该链表为空的条件是_，对于一个不带头指针的单链表，判定该链表为空的条件是_。4 在循环单链表中，头指针用head表示，队尾结点用p指向，那么pnext等于_。5 在选择数据结构的存储结构时，为了方便地定位和读取某特定元素，数据结构宜采用_形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用_形式。6深度为5的二叉树，最多有_个结点，最少有_个结点。7若深度为5的二叉树中仅有度为0的结点和度为2的结点，那么这棵二叉树最多有_个结点，最少有_个结点。8 在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是 。9在含有个8结点的二叉链表中有_个空链域。10 有_个结点的二叉树将会呈现5种不同的表现形式。11在无向图的邻接矩阵中，若Aij=1,Aji= _。12如下图所示的有向图，顶点D的入度为 ，出度为 ，顶点D的度为 。ABCDEF三、操作题（共4题，总计20分）1已知一棵二叉树如下图所示：写出该二叉树的先根遍历序列(2分)写出该二叉树的中根遍历序列(2分)判断正误：这棵二叉树的先根、中根、后根遍历序列中，叶子结点的相对次序保持不变，其实，任意一棵二叉树，其叶子结点在先根、中根、后根遍历序列中的相对次序都保持不变。 （2分）p2 下面的程序段是一个在单链表表示的有序序列a,b,d,e中插入新值c并保持有序的算法，已知插入位置的前驱用p指向，请将程序段补充完整。(6分)abde head Status ListInsert_L(LinkList &L, char c)s=(LinkList)malloc(sizeof(LNode); ;snext= ;pnext= ;return OK;/ListInsert_LABCDEF3下图为一个无向图G，请给出该图从A出发的两个可能的广度优先遍历序列 (2分) (2分) 画出该图的邻接矩阵表示（4分）四、算法设计题（共1题，总计10分）设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区O.maxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。套题2一、选择题（每题2 分，共10题，总计20 分）1 一个数组的第一个元素的存储地址是1000，每个元素长度为4，则第4个元素的存储地址是_。A 1004 B 1008 C 1012 D 10162 一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_。A a,b,c,d,e B e,d,c,b,aC d,c,e,a,b D d,e,c,b,a3 从一个具有n个结点的单链表中查找值等于x的结点，在查找成功的前提下，其平均比较次数为_。A n B n/2 C (n-1)/2 D (n+1)/24 在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_。A 2 B 3 C 4 D 65 下列排序算法中不稳定的是_。A 堆排序 B 折半插入排序C 直接插入排序 D 链式基数排序6 向一个长度为100的数组的第45个元素之前插入一个元素时，需向后移动_个元素。A 45 B 46 C 55 D 567若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_。 A 48 B 49 C 50 D 518具有n个顶点的无向完全图，其边数为_。A n B n(n-1) C n(n-1)/2 D n29 下列关于图的描述，错误的是_。A 无向图中所有顶点的度数之和为边数之和的2倍B 有向图中所有顶点的度数之和为边数之和的2倍C 有向图中所有顶点的入度之和等于出度之和D 具有n个顶点，n-1条边的无向图是连通图10 有关二叉树下列说法正确的是_。A 二叉树是度为2的树B 一棵二叉树的度可以小于2C 二叉树中至少有一个结点的度为2D 二叉树中所有结点的度都为2二、填空题 （每空2 分，共12题，总计40 分）1 判定下列程序段的时间复杂度为_，其语句频度为_for(i=0;in;i+) for(j=0;jnext=_; p-next=s;t=p-data;p-data=_;s-data=_;3 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是_，需要内存容量最多的排序是_。4 对线性表进行二分查找时，要求线性表必须_。5 对于一个头指针为head的带头结点的单链表，判定该链表为空的条件是_，对于一个不带头指针的单链表，判定该链表为空的条件是_。6 数据的存储结构是指 ，设有一批数据元素，为了方便地定位和读取某特定元素，数据结构宜采用_形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用_形式。7 已知一棵二叉树，其先序序列为ABCDE，中序序列为CDBEA，则其后序序列为_ 。8高度为6的二叉树，其结点个数最多为_个，最少为_个。9 在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是 。10在含有个20结点的二叉链表中有_个空链域。11 有_个结点的二叉树将会呈现5种不同的表现形式。12如下图所示的AOE网，其关键路径为 。三、算法题（每题8分，共2题，总计16分）1、关键字序列a,b,c，d的链式存储如下，编写算法，通过更改指针实现关键字序列a，d，c,b的链式存储。abcd head2、设计算法，现有一字符串“12468”（即该变量为字符数组，每个单元存放一个char型的值，分别为1，2，4，6，8），若该字符串表示的是数值型的八进制数值，即（12468）8，设计算法将它转换为十进制数并输出。四、操作题（每题6分，共4题，总计24分）ABCDEFGHIJK1、已知一棵树如下图所示，要求：给出树的先根遍历序列和后根遍历序列（3分）将该树转化为二叉树（3分）2、设有一组关键字为8,7,13,10,9,23,15，哈希函数为H(key)=key MOD 7，按开放定址的线性探测再散列解决冲突，即增量序列为1，2，3，构造表地址空间为0-9的哈希表。请画出该哈希表（3分）0123456789计算对关键字23进行查找时的查找长度并写出计算过程（3分）3、下图为一个无向图G请给出该图的邻接表表示(3分)依据你所作的邻接表，从A出发，给出该图的深度优先遍历序列（3分）ABCDEF4、下图所示为一棵3阶B-树 请给出删除元素25之后的3阶B-树(3分) 在的基础上，给出插入15之后的3阶B-树（3分）12 1621 231082425 2820套题3一、选择题（共10 题，每题2分，共20分）： 1、从逻辑上可以把数据结构分为（ ）两大类。A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构2、下面关于线性表的叙述中，错误的是哪一个？（ ）A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。3、设无向图的顶点个数为n，则该图最多有（ ）条边。 A) n-1B) n(n-1)/2 C) n(n+1)/2 D) 04、对线性表进行二分查找时，要求线性表必须（ ）A) 以顺序方式存储 B) 以顺序方式存储且元素有序C) 以链式方式存储 D) 以链式方式存储且元素有序5、下面给出的四种排序法中( )排序法是不稳定性排序法。A) 插入 B) 冒泡 C) 二路归并D) 堆6、以下说法正确的是_。A) 数据元素是数据的最小单位B) 数据项是数据的最小单位C) 数据结构是带有结构的各数据项的集合D) 数据结构是带有结构的数据元素的集合7、下列说法不正确的是（ ）A）图的遍历是从给定的源点出发每一个顶点仅被访问一次 B）遍历的基本算法有两种：深度遍历和广度遍历C）图的深度遍历不适用于有向图 D）图的深度遍历是一个递归过程8、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A) 9 B) 11 C) 15 D) 不确定9、栈和队列的共同点是（ ）A) 都是先进先出 B) 都是先进后出C) 只允许在端点处插入和删除元素 D) 没有共同点10、有关二叉树下列说法正确的是（ ）A） 二叉树的度为2B） 一棵二叉树的度可以小于2C） 二叉树中至少有一个结点的度为2D) 二叉树中任何一个结点的度都为2二、填空题（共15 空，每空 2 分，共 30 分）1、当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 1） 查邻接表中入度为_ _的顶点，并进栈； 2） 若栈不空，则输出栈顶元素Vj，并退栈；查Vj的直接后继Vk，对Vk进行入度处理，处理方法是_ _ _； 3） 若栈空时，输出顶点数小于图的顶点数，说明有_ _ _，否则拓扑排序完成。2、给定一组数据6，2，7，10，3，12以它构造一棵哈夫曼树，则树深度为_，带权路径长度WPL的值为_ _ _。3、在单链表p结点之后插入s结点的操作是：_ _ 。4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用_结构，为了方便地插入一个数据元素，数据结构宜采用_结构。5、在一个无向图中，所有顶点的度数之和等于所有边数 倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 倍。6、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_ _。7、二叉树的第i层上最多含有结点数为。8、具有N个结点的二叉树，采用二叉链表存储，共有_个空链域。9、一个有n(n0)个结点的图，最少有 个连通分量，最多有 个连通分量。三、算法题（共3题，每题5分，共15分）1、 写一算法，求带有头结点的单链表的表长。2、请用非递归算法写出折半查找的算法。3、请写出直接插入排序的算法。四、操作题（共6题，第1题10分，其余每题5分，共35分）1、输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。 （1）按次序构造一棵二叉排序树BS。(2) 依此二叉排序树，如何得到一个从大到小的有序序列？ （3）画出在此二叉排序树中删除结点66后的树结构。（10分）2、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key) = key mod 13 和链地址法处理冲突构造哈希表。（5分）3、 对于下面的有向图G，请写出所有可能的拓扑序列。（5分）BACDE4、已知一棵二叉树前序为ABDEGCF，中序为DBGEACF，画出这棵二叉树。（5分）5、写出对数据（15，9，7，8，20，-1，7，4）进行快速排序中第一趟的序列。（5分）6、无向图G=(V，E)，其中：V=a，b，c，d，e，f，E=(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)，写出对该图进行深度优先遍历的一个序列。（5分）套题 4一、选择题（共10 题，每题2分，共20分）： 1、以下属于逻辑结构的是（ ）。A）顺序表 B）哈希表 C）有序表 D）单链表2、下面关于线性表的叙述中，错误的是哪一个？（ ）。A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。3、设无向图的顶点个数为n，则该图最多有（ ）条边。 A) n-1B) n(n-1)/2 C) n(n+1)/2 D) 04、线性表是具有n个（ ）的有限序列（n0）。A) 表元素 B) 字符 C) 数据元素 D) 数据项5、下面给出的四种排序法中( )排序法是稳定性排序法。A) 希尔 B) 快速 C) 二路归并D) 堆6、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。A) 快速排序 B) 堆排序 C) 归并排序 D) 直接插入排序7、下列说法不正确的是（ ）。A）图的遍历是从给定的源点出发每一个顶点仅被访问一次 B）遍历的基本算法有两种：深度遍历和广度遍历C）图的深度遍历不适用于有向图 D）图的深度遍历是一个递归过程8、若一棵二叉树具有14个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。 A) 9 B) 11 C) 15 D) 不确定9、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A) 顺序表 B) 双链表C) 带头结点的双循环链表 D) 单循环链表10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A）(n-1)/2 B) n/2 C) (n+1)/2 D) n二、填空题（共15 空，每空 2 分，共 30 分）1、数据的物理结构包括 的表示和 的表示。2、给定一组数据6，2，7，10，3，12以它构造一棵哈夫曼树，则树深度为_，带权路径长度WPL的值为_ _ _。3、在单链表p结点之后删除s结点的操作是：_ _ 。4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用_结构，为了方便地插入一个数据元素，数据结构宜采用_结构。5、在拓扑排序中，拓扑序列的第一个顶点必须是_的顶点。6、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_ _。7、二叉树的第i层上最多含有结点数为。8、具有N个结点的二叉树，采用二叉链表存储，共有_个空链域。9、一个有n（n0）个结点的图，最少有 个连通分量，最多有 个连通分量。10、对于具有N个结点的完全二叉树，其深度为 。11、在长度为n的顺序表的第i个位置上插入一个元素（1 i n+1），元素的移动次数为 。三、 算法题（共3题，每题5分，共15分）1、请写一算法，求带有头结点的单向循环链表的表长。2、请用非递归算法写出在二叉树中计算叶子结点个数的算法。3、请写出简单选择排序的算法。四、操作题（共6题，第1题10分，其余每题5分，共35分）1、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key) = key mod 13 和链地址法处理冲突构造哈希表。（10分）2、请写出在如下具有11个数据元素的有序表中使用折半查找算法查找21的过程（关键字即为数据元素的值）。（5分）（05， 13，19，21，37，56，64，75，80，88，92）3、对于下面的有向图G，请写出所有可能的拓扑序列。（5分）ABCDE4、写出对数据（49，38，65，97，76，13，27，49）进行快速排序中第一趟的序列。（5分）5、无向图G=(V，E)，其中：V=a，b，c，d，e，f,E=(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)，写出对该图进行广度优先遍历的序列。（5分）6、已知一棵二叉树前序为ABDEGCF，中序为DBGEACF，画出这棵二叉树。（5分）套题5一、选择题（每题2 分，共10题，总计20 分）1以下那一个术语与数据的存储结构无关？（ ）A栈 B. 哈希表 C. 线索树 D. 双向链表2对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）Ahead=NULL Bheadnext= head Cheadnext= NULL Dhead!=NULL3. 对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序4若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定5树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 D不一定6n个结点的完全有向图含有边的数目（）。An*n Bn（n） Cn2 Dn*（nl）7下列哪一种图的邻接矩阵是对称矩阵？（ ）A有向图 B无向图 CAOV网 DAOE网8. 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) A哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B除留余数法是所有哈希函数中最好的 C不存在特别好与坏的哈希函数，要视情况而定 D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可9下列排序算法中，其中（ ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序10堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆( )A16，72，31，23，94，53 B94，53，31，72，16，23C16，53，23，94，31，72 D16，31，23，94，53，72二、填空题（每空2 分，共20空，总计40 分）1在下面的程序段中，语句x+=1的频度是_，语句Aij=1的频度是_，整个程序的时间复杂度是_。for(i=0;in;i+) x+=1； for(j=0;j K），则该森林必有 _ 棵树。6构造连通网最小生成树的两个典型算法是_和_。7设G是一个非连通无向图，共有28条边，则该图至少有_个顶点。8若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为_ 。9一棵具有20个结点的完全二叉树的树高度（深度）是 。10 具有10个叶结点的二叉树中有 个度为2的结点。11有3个结点的二叉树将会呈现 种不同的表现形式。12N个顶点的连通图的生成树含有_ _条边。13具有N个结点的二叉树，采用二叉链表存储，共有 个空链域。14二叉树中某一结点左子树的深度减去右子树的深度称为该结点的 。15有一个长度为12的有序表，按二分查找法对该表进行查找，且查找每个元素的概率相同，则查找成功所需的平均查找长度为 。三、算法题（每题8分，共2题，总计16分）1关键字序列a,b,c，d的链式存储如下，编写算法删除d所在的结点，是删除之后的新序列为a，b，e。其中结点定义为：struct nodechar data;struct node * next;abcd head2、请写出快速排序的算法。（5分）对503，87，512，61，908，170，897，275，653，462，以第一个记录为枢轴，写出按升序进行一趟快速排序的结果。（3分）得分阅卷人四、操作题（每题6分，共4题，总计24分）1、已知某栈结构定义如下，现有一字符序列以a，b，c，d的顺序进栈,试完成下 面的操作，使最终的输出序列为a，c，b，dstruct stackint base;int top;stactsize N;/*N4*/;main（）basetopInit (stack);Push (a); ; ; ;Pop; /*栈顶元素c出栈*/ ；Push (d);Pop;/*end of main*/2、假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该二叉树。(4分)将此二叉树转化成其对应的森林。（2分）3、无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 请画出该图，并给出该图的邻接矩阵表示(4分)依据你所作的邻接矩阵，从A出发，给出该图的深度优先遍历序列（2分）4、将关键码DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树。（6分）套题6一、选择题（共10题，每题2分，共20分）1、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 。A、（N+1）/2 B、N/2 C、N D、（1+N）*N /22、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=inext&jnext) |ji-1) return ERROR; （2） ;p-next = q-next;e=q-data;free(q);return OK;2、以下程序的功能是在一有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素中的位置，否则为0,请在画线部分填上代码。（5分）int Search_Bin(SSTable ST,KeyType key) /* 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 */ /* 该元素在表中