下载文档原格式
北航《算法与数据结构》在线作业二一、单选题：1.若线性表最常用的操作是存取第i个元素及其前趋的值，则采用( )存储方式节省时间。
(满分:4)A. 单链表B. 双链表C. 单循环链表D. 顺序表正确答案:D2.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。
(满分:4)A. 头指针B. 尾指针C. 指针型变量D. 空指针正确答案:D3.栈的插入和删除操作在( )进行。
(满分:4)A. 栈顶B. 栈底C. 任意位置D. 指定位置正确答案:A4.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分( )个结点最佳(满分:4)A. 10B. 25C. 6D. 625正确答案:B5.图的深度优先遍历类似于二叉树的( )。
(满分:4)A. 先序遍历B. 中序遍历C. 后序遍历D. 层次遍历正确答案:A6.计算机的算法是( )。
(满分:4)A. 计算方法B. 排序方法C. 对特定问题求解步骤的一种描述D. 调度算法正确答案:C7.以下四种排序方法中，要求附加的内存容量最大的是( ) (满分:4)A. 插入排序B. 选择排序C. 快速排序D. 归并排序正确答案:D8.对于顺序表，以下说法错误的是( ) (满分:4)A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C. 顺序表的特点是正确答案:A9.二叉树第i层上至多有( )结点。
(满分:4)逻辑结构中相邻的结点在存储结构中仍相邻D. 顺序表的特点是正确答案:D10.深度为6（根的层次为1）的二叉树至多有( )结点。
(满分:4)逻辑上相邻的元素，存储在物理位置也相邻的单元中正确答案:D11.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )。
(满分:4)A. 2iB. 2的i次方C. 2i-1D. 2 的（i-1）次方正确答案:C12.从一棵B树删除元素的过程中，若最终引起树根结点的合并，则新树高度是( )。
装 订 线 内 不 得 答 题自觉遵 守考 试 规 则，诚 信 考 试，绝 不作 弊(A) 空或只有一个结点 (B) 高度等于其结点数(C) 任一结点无左孩子 (D) 任一结点无右孩子6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序7.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。
(A) 2n (B) n+l (C) 2n-1 (D) 2n+l8.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)9. 下列程序段的时间复杂度为（）。
i=0，s=0； while (s<n) {s=s+i；i++；}(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)10. 深度为k的完全二叉树中最少有( )个结点。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-111.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为( )。
(A) front->next=s;front=s; (B) s->next=rear;rear=s;(C) rear->next=s;rear=s; (D) s->next=front;front=s;12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)13.设某哈夫曼树中有199个结点，则该哈夫曼树中有( )个叶子结点。
(A) 99 (B) 100 (C) 101 (D) 10214.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。
1、填空题（1）有N个顶点组成的无向连通图，最多可以有_____________________条边。
（2）对于具有144个记录的文件，采用分块查找法查找，块间和块内均采用顺序查找。
假定每块长度为12个记录，则平均查找长度为----------。
（3）在有n个结点的二叉链表中，空链域的个数为_________。
（4）快速排序算法的时间复杂度为_______________。
（5）稀疏矩阵的存储策略是只存储______________元素。
（6）单循环链表L中指针P所指结点为尾结点的条件是____________。
（7）用开放地址法解决Hash冲突，冲突后Hash地址的计算公式是Hi=___________。
（8）冒泡排序、归并排序、基数排序、选择排序这四种排序方法中，_________________是不稳定的。
（9）一棵有n个叶子结点的哈夫曼树共有__________个结点。
（10）有时在单链表的第一个结点之前附加一个"头结点"，其作用是____________。
2、假设一一维数组A[0。
M]存储循环队列的元素，同时设变量rear和length分别指示循环队列到中队尾元素的位置和队列中所含元素的个数。
试编写元素出队的算法就。
3、已知二叉树的中序和后序遍历序列如下，试构造该二叉树。
中序：A C B D H G E F后序：A B C D E F G H4、什么是堆？试对序列{40，38，60，95，76，10，25，50，99}用堆排序方法进行从小到大排序。
要求写出主要过程。
5、设有权无向图G有N个顶点，E条边，试编写一个用邻接表存储该图的算法。
6、设有一个包含11个关键字的有序表，试画出用二分查找法在该表中进行查找的比较树，并计算在查找成功时平均查找长度。
7、编写在二叉排序树中查找关键字K的算法。
8、已知AOE网如下，试求其关键路径。
要求写出计算过程。
9、试写出在中序线索二叉树中求某结点前趋和后继结点的算法。
《数据结构实验》指导书Data Structures and Algorithms Laboratory Projects王金荣2014-09-11目录1《数据结构实验》课程实验教学大纲--------------------------------------12 实验准备: 如何使用VC 6.0? ----------------------------------------------33 Projects---------------------------------------------------------------------------8 3.1 Project 1: 算法性能测量-------------------------------------------------8 3.2 Project 2: 有序表归并实验---------------------------------------------10 3.3 Project 3: 数据转换------------------------------------------------------11 3.4 Project 4: 二叉树遍历实验---------------------------------------------12 3.5 Project 5-1: 堆排序算法实现------------------------------------------13 3.6 Project 5-2: 归并排序算法实现---------------------------------------14 3.7 Project 5-3: 快速排序算法实现---------------------------------------15 3.8 Project 6-1: 图的深度优先搜索---------------------------------------16 3.9 Project 6-2: 图的广度优先搜索---------------------------------------173.10 Project 7: 散列实验---------------------------------------------------184.1 ACM题目-------------------------------------------------------------------19 4.1 ACM 1: ACboy needs your help again!-------------------------------19 4.2 ACM 2: Jumping the Queue--------------------------------------------21 4.3 ACM 3: Median ----------------------------------------------------------234.4 ACM 4: Ignatius and the Princess I------------------------------------255 实验报告格式-----------------------------------------------------------------28 6实验报告上交说明-----------------------------------------------------------291《数据结构实验》课程实验教学大纲课程中文名称：数据结构实验课程英文名称：Data Structure Practices实验课程性质：独立设课课程编码：044209101一、学时、学分课程总学时：34 实验学时：34课程总学分：1 实验学分：1二、适用专业及年级计算机科学与技术专业，软件工程专业，第二学期三、实验教学目的与基本要求“数据结构实验”的总体目标是：通过实验使学生对课堂讲授的内容有实际的体验，加深对概念、算法、技术的理解、掌握、应用，并激发学生进一步的思考和发挥，注重培养学生的学习兴趣和创新思维。
东北大学15春学期《数据结构Ⅰ》在线作业及满分答案一、单选题（共20 道试题，共100 分。
）1.在一个带权连通图G中，权值最小的边一定包含在G的A. 最小生成树中B. 深度优先生成树中C. 广度优先生成树中D. 深度优先生成森林中正确答案：A2.高度为5的完全二叉树中含有的结点数至少为A. 16B. 17D. 32正确答案：A3.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于A. 1.0B. 2.9C. 3.4D. 5.5正确答案：B4.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为A. O(n) O(n)B. O(n) O(1)C.D. O(1) O(1)正确答案：C5.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是A. 1B. 2C. 3D. 概念上是错误的正确答案：B6.除第一层外，满二叉树中每一层结点个数是上一层结点个数的A. 1/2倍B. 1倍D. 3倍正确答案：C7.二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l， (8)列下标为j=1，2．…．10。
设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是A. A[8，5]B. A[3，10]C.A[5，8]D. A[0，9]正确答案：B8.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是B. front= =rearC. (rear-front)%m= =m-1D. front= =(rear+1)%m正确答案：B9.按排序过程中依据的原则分类，快速排序属于A.插入类的排序方法B. 选择类的排序方法C.交换类的排序方法D. . 归并类的排序方法正确答案：C10.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为A. 5B. 6C. 7D. 8正确答案：D11.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为A.(19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)正确答案：D12.下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是堆排序B. 冒泡排序C.直接选择排序D. 快速排序正确答案：A13.深度为h的满m叉树的第k层的结点(1=<k=<h)数有A. mk-1B. mk-1C. mh-1D. mh-1正确答案：A14.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能G中有弧<Vi，Vj>B. G中有一条从Vi到Vj的路径C. G中没有弧<Vi,Vj>D. G中有一条从Vj到Vi的路径正确答案：D15.若要在单链表中的结点p之后插入一个结点s，则应执行的语句是A. s->next=p->next; p->next=s;B. p->next=s; s->next=p->next;C. p->next=s->next; s->next=p;D. s->next=p; p->next=s->next;正确答案：A16.A. 树的后根遍历与其对应的二叉树的后根遍历相同B.树的后根遍历与其对应的二叉树的中根遍历相同C.树的先根遍历与其对应的二叉树的中根遍历相同D.以上都不对正确答案：B17.带行表的三元组表是稀疏矩阵的一种A. 顺序存储结构B. 链式存储结构C. 索引存储结构正确答案：A18.当采用分快查找时，数据的组织方式为A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同正确答案：B19.在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进最新在线作业试卷A. LL型B. LR型C. RL型D. RR型正确答案：B20.适宜进行批量处理的文件类型是A. 顺序文件B. 索引顺序文件C. 散列文件D. 多关键字文件正确答案：A最新在线作业试卷_______________________________________________。
《数据结构》2015年春学期在线作业（一）单选题1. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）。
A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 6?正确答案：C2. 一个堆栈的入栈序列为abcde，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（）。
A. edcbaB. decbaC. decabD. abcde?正确答案：C3. 以下说法错误的是（）。
A. 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表。
B. 对单链表来说，只有从头结点开始才能扫描表中全部结点。
C. 双链表的特点是找结点的前趋和后继都很容易。
D. 对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
?正确答案：A4. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
A. 顺序表B. 单链表C. 双链表D. 单循环链表?正确答案：A5. 题目和答案如下图所示：A.B.C.D.?正确答案：B6. 以下判断不正确的是（）。
A. 顺序存储的线性表可随机存取。
B. 同一线性表中的数据元素应具有相同的特性。
C. 顺序存储方式的优点是存储密度大，插入、删除操效率高。
D. 在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。
?正确答案：C7. 用堆栈求算术表达式a+b*(c-d)-e/f的后缀表达式为（）。
A. abcd-*+ef/-B. a+b*(c-d)-e/fC. abcdef-*+/-D. abc-d*ef/+-?正确答案：B8. （）是指数据中的一个个的个体，是数据的基本单位。
A. 数据相B. 数据元素C. 数据结构D. 数据类型?正确答案：A9. 关于逻辑结构和存储结构，正确的描述是（）。
A. 线性数据结构必须采用链式存储结构B. 一种逻辑结构，可以用不同的存储结构来存储，反之亦然C. 一种逻辑结构，可以用不同的存储结构来存储，反之不然D. 一种存储结构只能表示一种逻辑结构?正确答案：B10. 单链表中，增加头结点的目的是为了（）。
装 订 线 内 不 得 答 题自觉遵 守考 试 规 则，诚 信 考 试，绝 不作 弊(A) 空或只有一个结点 (B) 高度等于其结点数(C) 任一结点无左孩子 (D) 任一结点无右孩子6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序7.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。
(A) 2n (B) n+l (C) 2n-1 (D) 2n+l8.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)9. 下列程序段的时间复杂度为（）。
i=0，s=0； while (s<n) {s=s+i；i++；}(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)10. 深度为k的完全二叉树中最少有( )个结点。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-111.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为( )。
(A) front->next=s;front=s; (B) s->next=rear;rear=s;(C) rear->next=s;rear=s; (D) s->next=front;front=s;12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)13.设某哈夫曼树中有199个结点，则该哈夫曼树中有( )个叶子结点。
(A) 99 (B) 100 (C) 101 (D) 10214.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。
北语15春《数据结构》作业1一、单选题（共20 道试题，共100 分。
）V 1. A. AB. BC. CD. D满分：5 分2. 算法指的是___。
A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列满分：5 分3. 不定长文件是指___。
A. 文件的长度不固定B. 记录的长度不固定C. 字段的长度不固定D. 关键字项的长度不固定满分：5 分4. A. AB. BC. CD. D满分：5 分5. 设数据结果A=(D,R)，其中D={1,2,3,4}，R={r}，r={<1,2>，<2,3>，<3,4>，<4,1>}，则数据结构A是___。
A. 线性结构B. 树型结构C. 图型结构D. 集合满分：5 分6. A. AB. BC. CD. D满分：5 分7. 栈的插入和删除操作在___进行。
A. 栈顶B. 栈底C. 任意位置D. 指定位置8.下列关于数据结构基本概念的叙述中，正确的是______。
A. 数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线性结构C. 数据元素是数据的基本单位D.结点是有独立含义的数据最小单位满分：5 分9. A. AB. BC. CD. D10. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为___。
A. O（1）B. O（n）C. O（m）D. O（m+n）满分：5 分11. 组成数据的基本单位是___。
A. 数据项B. 数据类型C. 数据元素D. 数据变量满分：5 分12. 用链接方式存储的队列，在进行插入运算时___。
A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D. 头、尾指针可能都要修改满分：5 分13. 设有以下四种排序方法，则___的空间复杂度最大。
A. 冒泡排序B. 快速排序C. 堆排序D. 希尔排序满分：5 分14. 由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___。
第二章线性表顺序表的操作1、顺序表的建立（从键盘或者数组中导入数据）Status InitList(SqList &L){ //构造一个空的顺序表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;}2、顺序表按照值查找位置int LocateElem(SqList L, ElemType e){ //根据数据元素的值，返回它在线性表L中的位置int i=0;while ((i<=L.length)&&(*(L.elem+i-1)!=e))i++;if (i<=L.length)return i;elsereturn(-1);}3、顺序表按照序号查找元素的值Status GetElem(SqList L,int i,ElemType &e){ //根据数据元素在线性表L中的位置，返回它的值if(i<1||i>L.length )return ERROR;e=*(L.elem+i-1);return OK;}4、顺序表数据元素的插入Status ListInsert(SqList &L,int i,ElemType e){ // 在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *p,*q,*newbase;if(i<1||i>L.length+1)return ERROR;if(L.length>=L.listsize){newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q; --p)*(p+1)=*p;*q=e;++L.length ;return OK;}5、顺序表数据元素的删除Status ListDelete(SqList &L,int i,ElemType &e){ //删除L的第i个数据元素，并用e返回其值，L的长度减1ElemType *q,*p;if(i<1||i>L.length)return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p) *(p-1)=*p;--L.length;return OK;}6、顺序表数据元素的输出Status visit(SqList L){ //按序输出顺序表的各个元素值int i;for(i=1;i<=L.length;i++)printf("%d ",*(L.elem+i-1));cout<<endl;printf("L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);return OK;}单链表的操作1、单链表的建立void CreateList(LinkList &L,int n){ // 逆位序输入n个元素的值，建立带表头结构的单链线性表Lint i;LinkList p;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;printf("请输入%d个数据\n",n);for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=L->next;L->next=p;}}void CreateList2(LinkList &L,int n){ // 正位序输入n个元素的值，建立带表头结构的单链线性表int i;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;q=L;printf("请输入%d个数据\n",n);for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);q->next=p;q=q->next;}p->next=NULL;}2、单链表的输出Status visit(LinkList L){ //按序输出单链表的各个元素值LinkList p=L->next;while(p){printf("%d ",p->data);p=p->next;}printf("\n");return OK;}3、单链表结点的插入Status ListInsert(LinkList &L,int i,ElemType e){LinkList p,s;p=L;int j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)return ERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return OK;}4、单链表结点的删除Status ListDelete(LinkList&L,int i,ElemType e){LinkList p,q;p=L;int j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;}5、单链表中按照结点的值查找结点的位序int LocateElem(LinkList L,ElemType e){ //返回L中第1个值为e 的数据元素的位序，若这样的数据元素不存在,则返回值为0 int i=0;LinkList p=L->next;while(p){ i++;if(p->data==e)return i;p=p->next;}return 0;}6、单链表中按照结点的位序返回结点的值Status GetElem(LinkList L,int i,ElemType &e){ // L为带头结点的单链表的头指针。
2015年秋季学期《数据结构》课程作业 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分） 1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K是 ____C__的有限集合，R是K上的___H___的有限集合。（第一章） a 存储 b 数据操作 c数据元素 d操作 e逻辑结构 f 映象 g算法 h关系 2.以下关于算法的说法不正确的是____B _________。（第一章） a 一个算法应包含有限个步骤 b算法越简单越好 c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之 d算法中的每个步骤都能在有限时间内完成 3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是______B________。（第一章） a 线性结构 b 树型结构 c 物理结构 d 图型结构 4.下面程序段的时间复杂度为___C___（第一章） int sum=0; for(i=0; ifor(j=i;j s++; a. O(m+n) b. O(n*n) c. O(m*n) d. O(m*logn) 5. 下列有关线性表的叙述中，正确的是____A____。（第二章） a 一个线性表是 n 个数据元素的有限序列 b 线性表中任何一个元素有且仅有一个直接前驱 c 线性表中任何一个元素有且仅有一个直接后继 d 以上说法都不正确 6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为___B___（第二章） a．n b．n/2 c．(n+1)/2 d．(n-1)/2 7.链表不具备的特点是______D___。（第二章） a不必事先估计存储空间 b 插入删除不需要移动元素 c 可顺序访问任一结点 d 所需空间与其长度无关 8.带附加头结点的双循环链表L为空表的条件是_______C_____。（第二章） a L==NULL b L->next==NULL c L->prior==L d L->prior==NULL 9.设广义表L=（（a,b,c））,则L的长度与深度分别为___D_________。（第三章） a 1和1 b 1和3 c 2和3 d 1和2 10. 若栈采用链式存储结构,则下面的说法中正确的是____A____（第四章） a.不需要判断栈满但需要判断栈是否为空 b.需要判断栈是否栈空与栈满 c.需要判断栈满但不需要判断栈空 d.栈满栈空都不需要判断 11. 在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为_____B_______。 （第四章） a t->next=r;t=r; b r->next=s;s=r; c s->next=r;s=r; d r->next=t; 12.一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列___B___（第四章） a. 1, 2, 3, 4, 5, 6 b. 3, 2, 6, 4, 5, 1 c. 2, 4, 6, 5, 3, 1 d. 6, 5, 4, 3, 2, 1 13. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_____A_______。（第四章） a (rear-front+m)%m b rear-front+1 c rear-front-1 d rear-front 14.栈和队列的共同特点是______A____。（第四章） a.只允许在端点处插入和删除元素 b.都是先进后出 c.都是先进先出 d.没有共同点 15.中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是__D____（第四章） a．AB+D*E/FA+*DC+ b．ABD*+EFAD*+/C+ c．ABDEFADC+*+/+*+ d．AB+D*EFAD*+/+C+ 16.如下图所示的4棵二叉树，____C_____不是完全二叉树。（第五章）
17. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为_____C_______。（第五章） a 9 b 10 c 11 d 12 18. 深度为6(根的层次为1)的二叉树至多有____B___结点（第五章） a.64 b.63 c.31 d.32 19.二叉树的第k层的结点数最多为________D____。（第五章） a. 2k-1 b. 2K+1 c. 2K-1 d. 2k-1
20.如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是____B___。（第五章） a 空或只有一个结点 b 高度等于其结点数 c 任一结点无右孩子 d 任一结点无左孩子 21. 树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论_______A__是正确的。（第五章） a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 b.树的后根遍历序列与其对应的二叉树的先序遍历序列相同 c.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 d.以上都不对 22.根据使用频率为5个字符设计的哈夫曼编码不可能是______B______。（第六章） a 111，110，10，01，00 b 000，001，010，011，01 c 001，000，01，11，10 d 100，111，110，101，0 23. 下列数据结构中,不属于二叉树的是______D______（第六章） a. 堆 b. 哈夫曼树 c. 线索二叉树 d. B树 24.采用邻接表存储的图的广度优先遍历算法类似于二叉树的_____D_____。（第七章） a 先序遍历 b 中序遍历 c 后序遍历 d 层次遍历 25.对用邻接表表示的图进行深度优先遍历时，通常是借助___A______来实现算法。（第七章） a 栈 b 队列 c 树 d 图 26. 在一个图中，所有顶点的度数之和等于图的边数的____C_____倍。（第七章） a. 1/2 b. 1 c. 2 d. 4 27.对线性表进行二分查找，要求线性表必须_______B_____。（第九章） a 以顺序方式存储 b 以顺序方式存储，且结点按关键字有序排序 c 以链接方式存储 d 结点按关键字有序排序，存储方式无所谓 28.排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为_______C_____。（第十章） a 希尔排序 b 冒泡排序 c选择排序 d 插入排序 29.下列四种排序中，_______C_____的空间复杂度最大。（第十章） a. 插入排序 b. 冒泡排序 c. 归并排序 d. 快速排序 二. 填空题，请将正确答案填在____上。（每空1分，共30分） 1.数据结构分为____逻辑结构____和物理结构两种结构。（第一章） 2.线性结构中元素之间存在一对一关系，而树形结构中元素之间存在__一对多___关系，图形结构中元素之间存在多对多关系。（第一章） 3.一个算法的最基本的原操作执行次数为(3n2+2nlog2n+4n-7)/(5n),则该算法的时间复杂度为____ O(n)_____。（第一章） 4.链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过___指针_______间接地反映。（第二章） 5.向一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_____N-i+1_______个元素。（第二章） 6.当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用_____链式_____存储结构。（第二章） 7.在单链表中，要删除某一指定的结点，必须找到该结点的______前驱______结点。（第二章） 8.删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行q=____ P->next __,p->next=__ q->next ____和___ delete q____的操作。（第二章） 9.设广义表L=（（a，（b,c,d）））,则L的长度为_____1___，深度为_____3____。（第三章） 10.队列的特点是先进先出，与之对应，栈的特点是___后进先出_________。（第四章） 11.在栈顶进行插入删除一个元素的时间复杂度是___ O(1)_____。（第四章） 12.后缀算式9 2 3 +- 10 2 / -的值为__-1____。（第四章） 13.一个环形队列中共有MaxSize个单元，那么队满时共有__ MaxSize – 1 ____个元素。（第四章） 14.设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是______5______。（第四章） 15.一棵高度为6的完全二叉树至少有____32____个结点，最多有___63___个结点。（第五章） 16.如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为__2n或2n-1___。（第五章） 17.设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为______CABD____。（第五章） 18.已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是__求矩形第i行非
零元素之和__。（第七章）
1、 19.一个图的三种存储方法中，__________邻接矩阵， 邻接表和边集数组____________表示法是不唯一的。（第七章） 2、 20.一个有n个顶点的无向连通图最少有__n-1 _条边，最多___ n(n-1)/2___条边。（第七章） 21.设一个连通图G中有n个顶点e条边，则其最小生成树上有_____n-1___条边。（第八章） 22.外排序是指在排序前后，数据在___外存____上，排序时数据调入内存进行的排序方法。（第十章） 23.在选择排序、冒泡排序、归并排序中，_____选择____排序是不稳定的。（第十章） 三. 简答题。（每小题4分，共40分） 1.简述顺序表和链表存储方式的特点。（第二章） 顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不
