数据结构期末总复习题

1套题1一、选择题（每题2分，共15题，总计30分）1以下叙述中正确的是_。A数组是数据的最小单位B数据对象就是一组数据元素的集合C顺序存储方式只能用于存储线形结构D树对应到的二叉树其根结点的右子树总是空的2一个数组的第一个元素的存储地址是100，每个元素长度为2，则第5个元素的存储地址是_。A110B108C100D1203一个栈的入栈顺序是A,B,C,D,E，则其出栈顺序不可能是_。AA,B,C,D,EBE,D,C,B,ACD,C,E,A,BDD,E,C,B,A4栈的特点是_。A先进先出B先进后出C随即存取D链式实现5一个队列的入队顺序是1，2，3，4，5，那么出队顺序是_。A5，4，3，2，1B1，2，3，5，4C1，2，3，4，5D1，3，2，4，56向一个长度为10的数组的第5个元素之前插入一个元素时，需向后移动_个元素。A3B5C6D77若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_。A48B49C50D518高度为6的完全二叉树中第4层结点的个数为_。A2B4C8D169具有N个顶点的无向完全图，其边数为_。ANBNN1CNN1/2DN210具有N个顶点的有向完全图，其边数为_。ANBNN1CNN1/2DN211在有7个顶点的无向图中至少有_条边才能确保该图连通。A1B6C7D2112对于一个有N个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是_。AN1BNCN12DN213在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_。A2B3C4D614采用顺序查找方法查找长度为N的线性表时，每个元素的平均查找长度为_。AONBONLOGNCON2DOLOGN15在待排序元素基本有序的前提下，效率最高的排序方法是_。A插入排序B选择排序C快速排序D归并排序二、填空题（每空2分，共20空，总计40分）1判定下列程序段的时间复杂度为_，其中语句AIJ频度为_FORI0INEXT_PNEXTSTPDATAPDATA_SDATA_3在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是_，需要内存容量最多的排序是_。4对线性表进行二分查找时，要求线性表必须_。5对于一个头指针为HEAD的带头结点的单链表，判定该链表为空的条件是_，对于一个不带头指针的单链表，判定该链表为空的条件是_。6数据的存储结构是指，设有一批数据元素，为了方便地定位和读取某特定元素，数据结构宜采用_形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用_形式。7已知一棵二叉树，其先序序列为ABCDE，中序序列为CDBEA，则其后序序列为_。8高度为6的二叉树，其结点个数最多为_个，最少为_个。9在线索二叉树中，若以LTAG表示某结点的左标志域，以LCH表示某结点的左孩子域，则结点T没有左子5树的条件是。10在含有个20结点的二叉链表中有_个空链域。11有_个结点的二叉树将会呈现5种不同的表现形式。12如下图所示的AOE网，其关键路径为。DFECBA35212323三、算法题（每题8分，共2题，总计16分）1、关键字序列A,B,C，D的链式存储如下，编写算法，通过更改指针实现关键字序列A，D，C,B的链式存储。2、设计算法，现有一字符串“12468”（即该变量为字符数组，每个单元存放一个CHAR型的值，分别为1，2，4，6，8），若该字符串表示的是数值型的八进制数值，即（12468）8，设计算法将它转换为十进制数并输出。四、操作题（每题6分，共4题，总计24分）1、已知一棵树如下图所示，要求给出树的先根遍历序列和后根遍历序列（3分）将该树转化为二叉树（3分）2、设有一组关键字为8,7,13,10,9,23,15，哈希函数为HKEYKEYMOD7，按开放定址的线性探测再散列解决冲突，即增量序列为1，2，3，构造表地址空间为09的哈希表。ABCDHEADABCDEFGHIJK6请画出该哈希表（3分）0123456789计算对关键字23进行查找时的查找长度并写出计算过程（3分）3、下图为一个无向图G请给出该图的邻接表表示3分依据你所作的邻接表，从A出发，给出该图的深度优先遍历序列（3分）4、下图所示为一棵3阶B树请给出删除元素25之后的3阶B树3分在的基础上，给出插入15之后的3阶B树（3分）ABCDEF7套题3一、选择题（共10题，每题2分，共20分）1、从逻辑上可以把数据结构分为（）两大类。A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构2、下面关于线性表的叙述中，错误的是哪一个（）A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。3、设无向图的顶点个数为N，则该图最多有（）条边。AN1BNN1/2CNN1/2D04、对线性表进行二分查找时，要求线性表必须（）A以顺序方式存储B以顺序方式存储且元素有序C以链式方式存储D以链式方式存储且元素有序121621231082425282085、下面给出的四种排序法中排序法是不稳定性排序法。A插入B冒泡C二路归并D堆6、以下说法正确的是_。A数据元素是数据的最小单位B数据项是数据的最小单位C数据结构是带有结构的各数据项的集合D数据结构是带有结构的数据元素的集合7、下列说法不正确的是（）A）图的遍历是从给定的源点出发每一个顶点仅被访问一次B）遍历的基本算法有两种深度遍历和广度遍历C）图的深度遍历不适用于有向图D）图的深度遍历是一个递归过程8、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A9B11C15D不确定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的值为_。93、在单链表P结点之后插入S结点的操作是_。4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用_结构，为了方便地插入一个数据元素，数据结构宜采用_结构。5、在一个无向图中，所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。6、对于一个头指针为HEAD的带头结点的单链表，判定该表为空表的条件是_。7、二叉树的第I层上最多含有结点数为。8、具有N个结点的二叉树，采用二叉链表存储，共有_个空链域。9、一个有NN0个结点的图，最少有个连通分量，最多有个连通分量。三、算法题（共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），则按哈希函数HKEYKEYMOD13和链地址法处理冲突构造哈希表。（5分）3、对于下面的有向图G，请写出所有可能的拓扑序列。（5分）4、已知一棵二叉树前序为ABDEGCF，中序为DBGEACF，画出这棵二叉树。（5分）BACDE105、写出对数据（15，9，7，8，20，1，7，4）进行快速排序中第一趟的序列。（5分）6、无向图GV，E，其中VA，B，C，D，E，F，EA，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，则该图最多有（）条边。AN1BNN1/2CNN1/2D04、线性表是具有N个（）的有限序列（N0）。A表元素B字符C数据元素D数据项5、下面给出的四种排序法中排序法是稳定性排序法。A希尔B快速C二路归并D堆6、若需在ONLOG2N的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A快速排序B堆排序C归并排序D直接插入排序7、下列说法不正确的是（）。A）图的遍历是从给定的源点出发每一个顶点仅被访问一次B）遍历的基本算法有两种深度遍历和广度遍历C）图的深度遍历不适用于有向图D）图的深度遍历是一个递归过程8、若一棵二叉树具有14个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。A9B11C15D不确定9、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储11方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表10、若查找每个记录的概率均等，则在具有N个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为。A）N1/2BN/2CN1/2DN二、填空题（共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个位置上插入一个元素（1IN1），元素的移动次数为。三、算法题（共3题，每题5分，共15分）1、请写一算法，求带有头结点的单向循环链表的表长。2、请用非递归算法写出在二叉树中计算叶子结点个数的算法。3、请写出简单选择排序的算法。12四、操作题（共6题，第1题10分，其余每题5分，共35分）1、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数HKEYKEYMOD13和链地址法处理冲突构造哈希表。（10分）2、请写出在如下具有11个数据元素的有序表中使用折半查找算法查找21的过程（关键字即为数据元素的值）。（5分）（05，13，19，21，37，56，64，75，80，88，92）3、对于下面的有向图G，请写出所有可能的拓扑序列。（5分）4、写出对数据（49，38，65，97，76，13，27，49）进行快速排序中第一趟的序列。（5分）5、无向图GV，E，其中VA，B，C，D，E，F,EA，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的带头结点的单链表，判定该表为空表的条件是（）AHEADNULLBHEADNEXTHEADCHEADNEXTNULLDHEADNULL3对于栈操作数据的原则是（）。A先进先出B后进先出C后进后出D不分顺序ABCDE134若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A9B11C15D不确定5树的后根遍历序列等同于该树对应的二叉树的A先序序列B中序序列C后序序列D不一定6N个结点的完全有向图含有边的数目（）。ANNBN（N）CN2DN（NL）7下列哪一种图的邻接矩阵是对称矩阵（）A有向图B无向图CAOV网DAOE网8下面关于哈希HASH，杂凑查找的说法正确的是A哈希函数构造的越复杂越好，因为这样随机性好，冲突小B除留余数法是所有哈希函数中最好的C不存在特别好与坏的哈希函数，要视情况而定D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可9下列排序算法中，其中（）是稳定的。A堆排序，冒泡排序B快速排序，堆排序C直接选择排序，归并排序D归并排序，冒泡排序10堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆A16，72，31，23，94，53B94，53，31，72，16，23C16，53，23，94，31，72D16，31，23，94，53，72二、填空题（每空2分，共20空，总计40分）1在下面的程序段中，语句X1的频度是_，语句AIJ1的频度是_，整个程序的时间复杂度是_。FORI0IK），则该森林必有_棵树。6构造连通网最小生成树的两个典型算法是_和_。7设G是一个非连通无向图，共有28条边，则该图至少有_个顶点。8若U,V是EG中的一条边，则称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。其中结点定义为STRUCTNODECHARDATASTRUCTNODENEXT2、请写出快速排序的算法。（5分）对503，87，512，61，908，170，897，275，653，462，以第一个记录为枢轴，写出按升序进行一趟快速排序的结果。（3分）ABCDHEAD15四、操作题（每题6分，共4题，总计24分）1、已知某栈结构定义如下，现有一字符序列以A，B，C，D的顺序进栈,试完成下面的操作，使最终的输出序列为A，C，B，DSTRUCTSTACKINTBASEINTTOPSTACTSIZEN/N4/MAIN（）INITSTACKPUSHAPOP/栈顶元素C出栈/；PUSHDPOP/ENDOFMAIN/2、假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该二叉树。4分将此二叉树转化成其对应的森林。（2分）3、无向图GV,E,其中VA,B,C,D,E,F,EA,B,A,E,A,C,B,E,C,F,F,D,E,D请画出该图，并给出该图的邻接矩阵表示4分依据你所作的邻接矩阵，从A出发，给出该图的深度优先遍历序列（2分）得分阅卷人BASETOP164、将关键码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树。（6分）套题6一、选择题（共10题，每题2分，共20分）1、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为。A、（N1）/2B、N/2C、ND、（1N）N/22、若长度为N的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为（）1NEXT（2）PNEXTQNEXTEQDATAFREEQRETURNOK2、以下程序的功能是在一有序表ST中折半查找其关键字等于KEY的数据元素。若找到，则函数值为该元素中的位置，否则为0,请在画线部分填上代码。（5分）INTSEARCH_BINSSTABLEST,KEYTYPEKEY/在有序表ST中折半查找其关键字等于KEY的数据元素。若找到，则函数值为/该元素在表中的位置，否则为0。/INTLOW,HIGH,MIDLOW1/置区间初值/HIGHSTLENGTHWHILELOWHIGH1IFEQKEY,STELEMMIDKEY/找到待查元素/RETURNMIDELSEIFLTKEY,STELEMMIDKEY2