《数据结构期末总复习题试题》由会员分享，可在线阅读，更多相关《数据结构期末总复习题试题（19页珍藏版）》请在金锄头文库上搜索。
1、所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的据元素的有序表中使用折半查找算法查找21的过程（关键字即为数序树中删除结点66后的树结构。（10分）已知一组关键字为（1图所示的有向图，顶点D的入度为，出度为，顶点D的度为。三、操学而不思则惘，思而不学则殆套题 1一、选择题（每题 2 分，共 15题，总计 30 分）1 以下叙述中正确的是_。 A 数组是数据的最小单位B 数据对象就是一组数据元素的集合C 顺序存储方式只能用于存储线形结构D 树对应到的二叉树其根结点的右子树总是空的2 一个数组的第一个元素的存储地址是 100 ，每个元素长度为 2，则第 5 个元素的存储地址是_。 A
2、110 B 108 C 100 D 1203 一个栈的入栈顺序是a,b,c,d,e ，则其出栈顺序不可能是_。 A a,b,c,d,e B e,d,c,b,a C 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，4 C 1，2，3，4，5 D 1 ，3，2，4，56 向一个长度为 10 的数组的第 5 个元素之前插入一个元素时，需向后移动_个元素。 A 3 B 5 C 6 D 77 若一棵二叉树有 101 个结点，且无度
3、为 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 在
4、序列 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+)地确定出该
5、二叉树？（4）说明由二叉树的前序遍历和后序遍历结果判定该链表为空的条件是。4在循环单链表中，头指针用head表共20空，总计40分）1判定下列程序段的时间复杂度为，其中语序列（2分）学而不思则惘，思而不学则殆将关键码DEC,FEBBEF学而不思则惘，思而不学则殆Aij=0;Bji=1;2 对线性表进行二分查找时，要求线性表必须_且_。3 对于一个头指针为 head 的带头结点的单链表， 判定该链表为空的条件是_，对于一个 不带头指针的单链表，判定该链表为空的条件是_。4 在循环单链表中，头指针用 head 表示，队尾结点用 p 指向，那么pnext 等于_。5 在选择数据结构的存储结构时，为了
6、方便地定位和读取某特定元素，数据结构宜采用_形式， 为了方便地进行数据元素的插入删除操作，数据结构宜采用_形式。6 深度为 5 的二叉树，最多有_个结点，最少有_个结点。7 若深度为 5 的二叉树中仅有度为 0 的结点和度为 2 的结点，那么这棵二叉树最多有_个结点， 最少有_个结点。8 在线索二叉树中， 若以 ltag 表示某结点的左标志域， 以 lch 表示某结点的左孩子域， 则结点 t 没有左子树 的条件是。9 在含有个 8 结点的二叉链表中有_个空链域。10 有_个结点的二叉树将会呈现 5 种不同的表现形式。11 在无向图的邻接矩阵中，若Aij=1,Aji= _。12 如下图所示的有向
7、图， 顶点 D 的入度为，出度为，顶点 D 的度为。BACEDF三、操作题（共 4 题，总计 20分） A1 已知一棵二叉树如下图所示：CD写出该二叉树的先根遍历序列(2 分)写出该二叉树的中根遍历序列(2 分)判断正误： 这棵二叉树的先根、 中根、后根遍历序列中， 叶子结点的相对次序保持不变，其实，任意一棵二叉树， 其叶子结点在先根、 中根、后根遍历序列中的相对次序都保持不变。（2 分）2 下面的程序段是一个在单链表表示的有序序列a,b,d,e 中插入新值c 并保持有序的算法，已知插入位置的前驱用 p 指向， 请将程序段补充完整。(6 分)p棵二叉树的前序序列为ABDGECFH，中序序列为：
8、DGBEA形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用形，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。（共20空，总计40分）1判定下列程序段的时间复杂度为，其中语e d学而不思则惘，思而不学则殆headabStatus ListInsert_L(LinkList &L, char c)s=(LinkList)malloc(sizeof(LNode);s next= ;pnext= ;return OK;/ListInsert_L3 下图为一个无向图 G，请给出该图从 A出发的两个可能的广度优先遍历序列ADCBEF(2 分)(2 分) 画出该图的邻接矩阵表示（ 4 分
9、）四、算法设计题（共 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,a C d,
10、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 下列排序算法中不稳定的是_。回其值的算法,请在画线部分填上代码。（5分）StatusLi4，0.04，0.23，0.10。要求：(1)画出赫夫曼树；头指针为head的带头结点的单链表，判定该表为空表的条件是（宜采用结构，为了方便地插入一个数据元素，数据结
11、构宜采用结构。学而不思则惘，思而不学则殆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 有关二叉树下列说法正确的是
