数据结构复习题.docx

1、数据结构复习题一、选择题1.栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树4.设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在（ ）位置，脚注(10)表示用10进制表示。 A688 B678 C692 D6965

2、.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( ) A. O（1） B. O（n） C. O（1og2n） D. O（n2）9.对于线性表（7，34，55，25

3、，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A1 B2 C3 D410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.811.一个链队列中，f，r分别为队首、队尾指针，则插入s所指结点的操作为( )。A）f-next=c；f=s； B） r-next=s；r=s；C）s-next=r；r=s； D） s-next=f；f=s；12.下列说法正确的是（ ）。A）二叉树中每个结点的度都为2 B）二叉树的度为2C）一棵二叉树的度可小于2 D）二叉树中至少有一个结点的度213.一棵非

4、空二叉树先序遍历与后序遍历序列正好相反，则该二叉树（ ）。A）所有的结点均无左孩子 B）所有的结点均无右孩子C）只有一个叶子结点 D）是任意一棵二叉树14.二叉排序树中，键值最小的结点一定（ ）。A）左指针为空 B）右指针为空C）左右指针均为空 D）左右指针均非空15.n个顶点的强连通图至少有（ ）条边。 A） n-1 B） n C）n+1 D）n(n-1)16.在一个有向图中，顶点入度之和与顶点出度之和的比值（ ）。 A）1/2 B）1 C）2 D）417.高度为h的二叉树只有度为0和2的结点，则此二叉树至少为（）结点。 A）2*h B）2*h1 C）2*h+1 D）h+118设某完全无向图

5、中有n个顶点，则该完全无向图中有（ ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-119设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 (A) 9 (B) 10 (C) 11 (D) 1220设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-121设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8

6、22.按照二叉树的定义，具有3个结点的二叉树有( )种形态。 A）3 B）4 C）5 D）623.下列排序算法中，可能会出现在最后一趟开始之前，所有元素都不在其最终位置上是( ). A） 堆排序 B） 冒泡排序 C）快速排序 D） 插入排序24.一组记录的排序码为46,79,56,38,40,84。用堆排序方法建立的初始堆为( )。A） 79,46,56,38,40,80 B） 84,79,56,38,40,46C） 84,79,56,46,40,38 D） 84,56,79,40,46,3825.将递归算法转换成对应的非递归算法时，通常需要使用( )。 A）栈 B）队列 C）链表 D）树26

7、.有10个结点的连通无向图，其边数至少有( )。 A）8条 B）9条 C）10条 D）11条27.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )。A）edcba B） decba C） dceab D） abcde28.高度为h的完全二叉树中所包含的结点数至少为( )。 A）2*h个 B）2h1个 C）2*h+1个 D）h+1个29设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)30设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 (A) 2k-1 (B)

8、 2k (C) 2k-1 (D) 2k-131设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 (A) n (B) e (C) 2n (D) 2e32在二叉排序树中插入一个结点的时间复杂度为（ ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)33设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 (A) n (B) n-1 (C) m (D) m-134设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3

9、(B) 4 (C) 5 (D) 835设用链表作为栈的存储结构则退栈操作（ ）。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别36设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2)37设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e38. 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。 (A) n(n-1) (B) n+1 (C

10、) n (D) n(n+1)39设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序40.下列四种排序中（ ）的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序二、填空题1. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为_，快速排序的平均时间复杂度为_。2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_（设结点中的两个指针域分别为llink和rlink）。3. 根据初始关键字序列(

11、19，22，01，38，10)建立的二叉排序树的高度为_。4. 深度为k的完全二叉树中最少有_个结点。5. 设初始记录关键字序列为(K1，K2，Kn)，则用筛选法思想建堆必须从第_个元素开始进行筛选。6. 设哈夫曼树中共有99个结点，则该树中有_个叶子结点；若采用二叉链表作为存储结构，则该树中有_个空指针域。7. 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_个队列元素；当前实际存储_个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。8. 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_个数据元素；删除第i个位置上

12、的数据元素需要移动表中_个元素。9. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为_。10. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为_。11.头结点为H的单循环链表为空的条件是_ _。12.线性表作为栈时，被称为_ _。13.在堆排序、快速排序和归并排序中，若只从最坏情况下排序最快并且要节省内存空间考虑，应选取 方法。14.一棵二叉树有11个度数为0的结点，则该二叉树的二度结点个数为_ _。15.平衡二叉树是每个结点的左右子树深度之差的绝对值不超过1的_ _。16.关键码序

13、列为21,12,20,35,40,51,87,33,42,90,2,18,34。步长因子序列为3,1时，一趟希尔排序结果序列为_ _。17.顺序存储的线性表相对与链接存储的线性表，其优点是_ _。18.就排序的稳定性而言，简单选择排序方法是_ _。19.设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是_。20.设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_第i列上非0元素的个数（填等于，大于或小于）。21for(i=1，t=1，s=0；i=n；i+) t=t*i；s=s+t；的时间复杂度为_。22设指针变量p指向单链表中结点A，指针变量s指

14、向被插入的新结点X，则进行插入操作的语句序列为_（设结点的指针域为next）。23设有向图G的二元组形式表示为G =（D，R），D=1，2，3，4，5，R=r，r=，则给出该图的一种拓扑排序序列_。24设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_。25设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_个结点数。26设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_。27设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_。28简单选择排序和直接插入排序算法的平均时间复杂度

15、为_。29快速排序算法的空间复杂度平均情况下为_，最坏的情况下为_。30.散列表中解决冲突的两种方法是_和_。31.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_=p；s-right=p-right；_=s； p-right-left=s；（设结点中的两个指针域分别为left和right）。32.设完全有向图中有n个顶点，则该完全有向图中共有_条有向条；设完全无向图中有n个顶点，则该完全无向图中共有_条无向边。33.设关键字序列为(Kl，K2，Kn)，则用筛选法建初始堆必须从第_个元素开始进行筛选。34.解决散列表冲突的两种方法是_和

16、_。35.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该三叉树中度数为3的结点数有_个。36.高度为h的完全二叉树中最少有_个结点，最多有_个结点。37.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是_。38.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是_。39.设一棵二叉树的前序序列为ABC，则有_种不同的二叉树可以得到这种序列。40.顺序存储的长度为m的循环队列为空的条件是_ _。41.线性表作为队时，被称为_ _。42.就快排序和堆排序，若原始记录接近正序或反序

17、，则最好选用 方法。43.在有序表(12、24、36、48、60、72、84)中二分查找关键字72时所需进行的关键字比较次数为_ _。44.二叉排序树每个结点的左右子树深度之差的绝对值不超过1，称为_ _。45.n阶对称方阵A，以下三角矩阵压缩到一维数组Sn*(n+1)/2中，若按行序为主存储，则A的第i行第j列元素(i=j)对应在S中的存储位置是_ _。46.顺序存储的线性表相对与链接存储的线性表，其缺点是_ _。47.就排序的稳定性而言，快排序方法是_ _。48.设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_。49.设连通

18、图G中有n个顶点e条边，则对应的最小生成树上有_条边。50.设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与_相互交换即可。三、解答题1、序列70,50,18,26,37,45,62,23,46,59,105,按顺序插入结点，建立一棵二叉排序树，然后删除结点37，删除后树高不能增高。分别画出该二叉排序树及删除结点37后的二叉排序树。2、对带权图,给出以Prim算法构造最小生成树过程，并计算该树的权。3、对带权图, 给出以克鲁斯卡亚算法构造最小生成树过程，并计算该树的权。4、正文为“CDDDAABBEECAAECDAACEDDABE”,设

19、计ABCDE这5个字母的哈夫曼编码，使得正文编码最短。5、给定权值6,12,3,75,40,30,20,65,34，给出按算法建立的哈夫曼树静态三叉链表存储结构。6、给定权值6,12,3,75,40,30,20,65,34，构建哈夫曼树。7、先序遍历序列a,b,c,s,g,f,d,e,j,h,k,i和中序遍历序列s,c,b,d,f,e,g,a,h,k,j,i，的二叉树,画出此二叉树，并给出其后序遍历序列。8、画出深林转化的二叉树,并给出二叉树的先序、中序、后序遍历序列。9、给定按关键码序列76,42,32,17,73,54,48,62,98,89,92,105，构建小顶堆逐步筛选过程。10、给

20、定按关键码序列76,42,32,17,73,54,48,62,78,89,2,10，构建大顶堆逐步筛选过程。11、画出有向图的邻接表和逆邻接表存储示意图。12、画出图的邻接表存储示意图，并按邻接表给出深度优先搜索序列和广度优先搜索序列。13、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7，基本表长度为10，用线性探测法解决冲突，关键码按给出的顺序填入表中。请画出哈希表，并求等概率情况下查找成功的平均查找长度。14、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7，基本表长度为10，用二

21、次探测法解决冲突，关键码按给出的顺序填入表中。请画出哈希表，并求等概率情况下查找成功的平均查找长度。15、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7，基本表长度为7，用拉链法解决冲突，关键码按给出的顺序填入表中，且总是在链表的第一个结点前插入。请画出哈希表，并求等概率情况下查找成功的平均查找长度。四、算法设计题typedef struct int c,m; ELEM; /c为语文成绩,m为数学成绩typedef struct ELEM t; int cnt; TBL;/表定义1、对数学成绩，将不及格和及格的学生分成前后两部分，使表前面

22、为不及格的学生，后面为及格的学生。不要求对这些元素按数学成绩排序，但要求尽量减少交换次数。void F1(TBL *tbl)/tbl为学生表 int low,high;ELEM m; for(low=0,high=t-1;lowhigh;) while(lowhigh & tbl.tlow.m60) low+; while(low=60) high-; if(lowcnt-1;j=0;pa-cnt+=pb-cnt;len=pa-cnt-1; while(i=0 & jcnt) if(pa-ti.c pb-tj.c) pa-tlen=pa-ti-; else pa-tlen=pb-tj+; le

23、n-; for(;jcnt;j+,len-) pa-tlen=pb-tj;5、表A按语文成绩非递减有序，向表中添加一个学生，并保持A表的有序性。void F5(TBL *ta,ELEM e)/ta为学生表A,e为添加的学生元素 int i; for(i=ta-cnt-1;i=0 & ta-ti.c e.c; i-) ta-ti+1=ta-ti; ta-ti+1=e; typedef struct nodeELEM e; struct node *next;NODE; /链表结点类型 6、对两个按语文成绩非递减有序的带头结点单链表A和B，将B表并入A表，而不改变其排序性，并将B表设置为空表。 v

24、oid F6(NODE *ah,NODE *bh) /ah、bh分别为a表和b表的头结点 NODE *pa,*pb,*s; for(pa=ah,pb=bh-next;pb;) for(;pa-next& pb-e.c=pa-next-e.c;) pa=pa-next; s=pb; pb=pb-next; s-next=pa-next; pa-next=s; pa=s; bh-next=NULL; 7、逆置单链表，即将结点顺序为：H-a1-a2-an，置换为：H-an-a2-a1。要求，不交换元素值，通过修改结点指针完成。 void F7(NODE *ah) /ah为表的头结点 NODE *p,

25、*s; for(p=ah-next,ah-next=NULL;p;) s=p; p=p-next; s-next=ah-next; ah-next=s; 8、求带头结点的单循环链表中的结点个数，不包括头结点。 int F8(NODE *ah) /ah为表的头结点 int num=0;NODE *s; for(s=ah-next;s!=ah;s=s-next) num+; return num; 下列各题使用的结点类型：typedef struct node ELEM e; struct node *lc,rc;NODE;9、统计二叉树中叶子结点数目 int F9(NODE *t) int nu

26、m=0; if(t) if(t-lc=NULL & t-rc=NULL) num+; num+=F9(t-lc)+ F9(t-rc); return num; 10、统计二叉树中只有一个子女(度为1)的结点数目 int F10(NODE *t) int num=0; if(t) if(t-lc=NULL & t-rc!=NULL)| (t-lc!=NULL & t-rc=NULL) num+; num+=F10(t-lc)+ F10(t-rc); return num; 11、统计二叉树中有两个子女(度为2)的结点数目 int F11(NODE *t) int num=0; if(t) if(t-lc & t-rc) num+; num+=F11(t-lc)+ F11(t-rc); return num; 12、统计二叉树中空指针域个数 int F12(NODE *t) int num=0; if(t) if(t-lc=NULL) num+; if(t-rc=NULL) num+; num+=F12(t-lc)+ F12(t-rc); return num; 13、求二叉树深度 int F13(NODE *t) int num=0,k; if(t) num=F13(t-lc); k=F13(t-rc); if(numk) num=k; num+; return num;