数据结构复习题及答案

1、一、选择题1、一个n个顶点的无向连通图，其边的个数至少为（ ）。an-1 bn cn+1 dnlogn2、以下数据结构中，（ ）是非线性数据结构。a树 b字符串 c队列 d栈3、在长度为n的顺序表的第i个位置上插入一个元素（1in+1），元素的移动次数为（ ）。an i+1 bn i c i d i-14、与线性表的链接存贮不相符合的特性是（ ）。a便于插、删运算 b需要连续的存贮空间c只能顺序查找 d存贮空间动态分配5、顺序存放的循环队列的元素以数组am存放,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。a(rear-front+m)%m brear-front+1

2、c(front+rear+m)%m d(rear-front)%m6、一个有n个顶点的无向图最多有( )条边。an(n-1)/2 bn (n-1) cn-1 dn+17、设栈的入栈序列是1，2，3，4，则（ ）不可能是其出栈序列。a1，2，4，3 b2，1，3，4 c1，4，3，2 d4，3，1，2，8、从逻辑上可以把数据结构分为（ ）两大类。a动态结构、静态结构 b初等结构、构造型结构c线性结构、非线性结构 d树型结构、图型结构9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）a空或只有一个根结点 b高度等于其结点数c任一结点无左孩子 d任一结点无右孩子10、已知一个有向图用邻

3、接矩阵表示，要删除所有从第i个结点发出的边，应该（ ）。a将邻接矩阵的第 i 行删除 b将邻接矩阵的第 i 行元素全部置零c将邻接矩阵的第 i 列删除 d将邻接矩阵的第 i 列元素全部置零11、算法分析的两个主要方面是（ ）a空间复杂性和时间复杂性 b正确性和简明性c可读性和文档性 d数据复杂性和程序复杂性12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。a必须是连续的 b部分地址必须是连续的c一定是不连续的 d连续或不连续都可以13、具有6个顶点的无向连通图的生成树应有（ ）条边。a5 b6 c7 d814、设栈的输入序列是a、b、c，则（ ）不可能是其出栈序列。acba

4、 bcab cbca dacb15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（ ）。ahead=null bhead-next=nullchead-next= head dhead ！=null16、栈和队都是（ ）a顺序存储的线性结构 b链式存储的非线性结构c限制存取点的线性结构 d限制存取点的非线性结构17、在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;深度为k的完全二叉树结点个数小于或等于深度相同的满二叉树。 a b c d18、以下数据结构中，（ ）是非线性数据结构。a树 b字符串 c队列 d栈19、

5、设森林f中有三棵树，第一，第二，第三棵树的结点个数分别为m1，m2和m3。与森林f对应的二叉树根结点的右子树上的结点个数是（ ）。am1 bm1+m2 cm3 dm2+m320、在下面的程序段的时间复杂度为（ ）。for (int i=1;in;i+) for (int j=1;jn;j+) aij=i*j;ao(m2) bo(m*n) co(n2) do(log2n)21、二叉树的第i层上最多含有结点数为（ ）a2i b 2i-1-1 c 2i-1 d2i -122、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。a选择 b冒泡 c归并 d堆23、线性表第一个元素的

6、存储地址是100,每个元素的长度为2,则第5个元素的地址是( )a110 b 108 c 100 d 12024、栈中元素的进出原则是（ ）。先进先出 后进先出 栈空则进 栈满则出25、下列字符串中（ ）不是串abcabdeabx的子串。 aa bc bbx c ab dad26、对稀疏矩阵进行压缩存储目的是（ ）。 a便于进行矩阵运算 b便于输入和输出 c节省存储空间 d降低运算的时间复杂度27、设二维数组a1.5,1.6的每个元素占5个存储单元，将其按行优先顺序存储在起始地址是1000的连续内存单元中，则a5,5的存储地址是（ ）。a1140 b1145 c1120 d112528、外排序

7、是指（ ）。a数据量很大，排序时要借外存进行的排序方法 b不需要使用内存的排序方法c数据量很大，需要人工干预的排序方法 d没有正确答案29、下列数据中不可能是平衡二叉树上结点的平衡因子的是（ ）。a-1 b0 c1 d230、在下面的程序段的时间复杂度为（ ）。for (int i=1;i m;i+) for (int j=1;jnext=s;s-next=p-next; bs-next=p-next;p-next=s;cp-next=s;p-next=s-next; dp-next=s-next;p-next=s;45、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。a1，2，4，

8、3， b2，1，3，4， c1，4，3，2， d4，3，1，2， e3，2，1，4，46、栈在（ ）中应用。a递归调用 b子程序调用 c表达式求值 da，b，c47、下列哪一种图的邻接矩阵是对称矩阵？（ ）a有向图 b无向图 caov网 daoe网48、下述哪一条是顺序存储结构的优点？（ a ）a存储密度大 b插入运算方便 c删除运算方便 d可方便地用于各种逻辑结构的存储表示49、线性表是具有n个（ c ）的有限序列（n0）。a表元素 b字符 c数据元素 d数据项 e信息项50、输入序列为abc，可以变为cba时，经过的栈操作为（ b ）a. push,pop,push,pop,push,po

9、p b. push,push,push,pop,pop,popc. push,push,pop,pop,push,pop d. push,pop,push,push,pop,pop51、从邻接阵矩可以看出，该图共有（ ）个顶点；如果是有向图该图共有（ ）条弧；如果是无向图，则共有（ ）条边。a9 b3 c6 d1 e以上答案均不正确a5 b4 c3 d2 e以上答案均不正确a5 b4 c3 d2 e以上答案均不正确52、最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是（ a ）。a. (rear+1) %n=front b. rear=front crear+1=f

10、ront d. (rear-l) % n=front53、循环队列a0.m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( a )。a. (rear-front+m)%m b. rear-front+1 c. rear-front-1 d. rear-front54、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ b ）。a. (rear+1) %n=front b. rear=front crear+1=front d. (rear-l) % n=front55、设树t的度为4，其中度为1，2，3和4的结点个数分别为4，2，

11、1，1 则t中的叶子数为（ c ）a5 b6 c7 d856、有n个叶子的哈夫曼树的结点总数为（ d ）。a不确定 b2n c2n+1 d2n-157、有关二叉树下列说法正确的是（ a ）a一棵二叉树的度可以小于2 b二叉树中至少有一个结点的度为2 c二叉树的度为2 d二叉树中任何一个结点的度都为258对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( a )。 a. 选择 b. 冒泡 c.

12、快速 d. 插入59、对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ c ）排序。a. 选择 b. 快速 c. 希尔 d. 冒泡60、若序列15，9，7，8，20，-1，4经一趟排序后的排列为9，15，7，8，20，-1，4，则采用的是（ c ）排序。a选择 b. 堆 c. 直接插入 d. 冒泡 61、下列排序算法中( b )不能保证每趟排序至少能将一个元素放到其最终的位置上。a.快速排序 b. shell排序 c. 堆排序 d.冒泡排序 62、下列排序算法中( c )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

13、a. 选择 b. 冒泡 c. 归并 d. 堆63、以下序列不是堆的是( )。a. (100,85,98,77,80,60,82,40,20,10,66) b. (100,98,85,82,80,77,66,60,40,20,10)c. (10,20,40,60,66,77,80,82,85,98,100) d. (100,85,40,77,80,60,66,98,82,10,20)64、下列四个序列中，哪一个是堆（ c ）。a. 75,65,30,15,25,45,20,10 b. 75,65,45,10,30,25,20,15c. 75,45,65,30,15,25,20,10 d. 75,

14、45,65,10,25,30,20,1565、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ d ）方法是散列文件的关键。a. 散列函数 b. 除余法中的质数 c. 冲突处理 d. 散列函数和冲突处理参考答案:0110: a a a b a a d c a b1120: a d a b b c d a d c2130: c c b b d c a a d b3140: d c d a b b ba d c4147: d b a b d d b 二判断题( )1、算法分析考虑的两个主要因素是空间复杂性和时间复杂性。( )2、非线性数据结构的

15、存储只能选用链式存储结构。( )3、任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。 ( )4、哈希文件是一种直接存取文件。( )5、含有n个结点的二叉排序树的平均查找长度和树的形态有关。( )6、满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。( )7、循环链表不是线性表。 ( )8、文件是记录的集合，文件上的操作主要有两类：检索和维护。( )9、对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为o（n2）。( )10、平衡二叉树（avl树），以每个分支结点为根的子树都是平衡的。 ( )姓名:_ 学号:_ 年级:_ 专业:_.密封线11、算法是由若干条指令组成的有穷序列

16、，而一个程序不一定满足有穷性。( )12、顺序存储方式只能用于存储线性结构数据。 ( )13、构造二叉排序树的过程即为对无序序列进行排序的过程。( )14、连通图上各边权值均不相同，则该图的最小生成树是唯一的。( )15、在单链表中，头结点是必不可少的。 ( )16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 ( )17、一个图的深度先遍历序列是唯一的。 ( )18、长度为1的串等价于一个字符常量。( )19、数组元素的下标值越大，存取时间越长。( )20、内部排序是指排序过程在内存中进行的排序。参考答案: 三、构造题15623418834781691231、设某二叉树的前序遍

17、历序列为abcdefgh，中序遍历序列为cdbafehg，试绘出这棵二叉树，并写出其后序遍历结果。2、从空树开始，逐个读入并插入下列关键字，构造一棵二叉树：（19，83，37，92，17，10，2，8）。3、设有无向连通网络g如下图所示：（1）画出其邻接矩阵存储；（2）从顶点搜索所得的深度优先搜索（dfs）序列和广度优先搜索（bfs）序列；（3）请采用普里姆或克鲁斯卡尔算法画出g的最小生成树。4、给定叶结点的权值：5，29，7，8，14，23，3，11。要求：（1)构造哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权) 。（2）计算该哈夫曼树的最小加权路径长度wpl。5、设散列表长度为1

18、3，散列函数h(k)=k mod 13,对关键字序列19，14，23，01，68，20，84，27，55，11，10，79。（1）分别画出用线性探测和链地址法解决冲突时构造的散列表（哈希表）。jihgfecdbaa（2）设每个记录的查找概率相等，分别计算以上两种散列表查找成功的平均查找长度（aslsucc）以及查找不成功的平均查找长度(aslunsucc)。6、设有一棵树，如右图所示，回答下列问题：（1）哪个是此树的根结点？哪些是叶子结点？（2）树的度数和树的深度是多少？（3）写出结点g的双亲、祖先、孩子？（4）写出结点e的子孙、兄弟和结点e所在的层次？7、假设用于通信的电文由字符集a,b,c

19、,d,e,f,g，h中的字母构成。它们在电文中出现的频度分别为6,32,3,7,19,2, 21,10。要求：（1) 请为这8个字母设计哈夫曼编码，并画出对应的哈夫曼树；（2）计算该哈夫曼树的最小加权路径长度wpl。8、对给定的一组关键字：49，38，65，97，76，13，27，49，55，4分别写出直接插入排序、希尔排序（增量为5，3，1）、起泡排序、快速排序、直接选择排序和归并排序的前2趟排序结果。9、已知有6个顶点（顶点编号为05）的有向带权图g，其邻接矩阵a为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中：4654333要求：（1）写出图g的邻接矩阵a （2）画出有向带权图g （3）从顶点0搜索所得的深度优先搜索（dfs）序列和广度优先搜索（bfs）序列；（4）求图g的关键路径，并计算该关键路径的长度。四、算法设计题1、有序表r0至rn-1进行二分查找，成功时返回记录在表中的位置，失败时返回0。请在横线上填空，把算法补充完整。int binsrch(sqlist r ,keytype k) /* 在表r中查找关键字k */ int low ,high,mid; low=0; high