《数据结构习题.ppt》由会员分享，可在线阅读，更多相关《数据结构习题.ppt（67页珍藏版）》请在三一办公上搜索。
1、绪论,选择题,1.算法的计算量的大小称为计算的（）。A效率 B.复杂性 C.现实性 D.难度2.下面关于算法说法错误的是（）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的确定性是指指令不能有二义性 D.以上几个都是错误的,B,D,选择题,3从逻辑上可以把数据结构分为（）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构4在下面的程序段中，对x的赋值语句的频度为（）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n)BO(n)CO(n2)DO(log2n),
2、C,C,判断题,1.数据元素是数据的最小单位。()2.数据的逻辑结构是指数据的各数据项之间的逻辑关系；()3算法的优劣与算法描述语言无关，但与所用计算机有关。(),4数据的物理结构是指数据在计算机内的实际存储形式。()5.数据结构的抽象操作的定义与具体实现有关。(),填空题,1数据的物理结构包括 的表示和 的表示。2数据的逻辑结构是指。3抽象数据类型的定义仅取决于它的一组_（1）_，而与_（2）_无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。4数据结构中评价算法的两个重要指标是_ _,1数据元素 数据元素间关系,2数据的组织形式，即数据元素之间逻辑关系的总体。而逻
3、辑关系是指数据元素之间的关联方式或称“邻接关系”。,3（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性。,4算法的时间复杂度和空间复杂度。,线性结构,一.选择1若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。A单链表 B双链表 C单循环链表 D带头结点的双循环链表2.一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定 B.n-i+1 C.i D.n-i3.若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（）。A.i-j-1 B.i-j C.j-
4、i+1 D.不确定的,D,B,D,一.选择4下面关于串的的叙述中，哪一个是不正确的？（）A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储5.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13 B.33 C.18 D.40,B,B,一.选择6.对稀疏矩阵进行压缩存储目的是（）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度7.已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取
5、出LS中原子e的运算是()。head(tail(LS)tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS),C,C,二.应用1、在下面的程序段中，对x的赋值语句的频度为多少？（表示为n的函数）for(i=1;in;i+)for(j=1;ji;j+)for(k=1;kj;k+)xxdelta；,n3,2、已知如下程序段for（i=n;i1;i-）x=x+1；语句1 for(j=n;ji;j-)y=y+1;语句2 请回答语句1、语句2的执行的频度分别为多少？（表示为n的函数）,n n2,3、（1）若长度为n的线性表采用顺序存
6、储结构，访问结点和增加、删除结点的时间复杂度为多少？（2）若线性表（a1,a2,an）以链接方式存储时，访问第i位置元素的时间复杂度为多少？（1in）,O(1),O(n),O(n),O(n),4、线性表中数据元素（表元）的存储方式有顺序和链式两种，其中链式存储又分为：单向链表、单向循环链表、双向链表、双向循环链表。以下是对同一线性表的不同存储，请分析下列各存储表使用的是何种存储方式？（注：表左的s指向起始记录，编号为0的记录为空记录。）,s,表1：顺序存储方式,s,表2：单向循环链表存储方式,s,表3：单向链表,s,表4：双向循环链表,5、完善算法：已知单链表结点类型为：typedef str
7、uct ListNode int data;ListNode*next;ListNode;函数create建立以head为头指针的单链表。void create(1)ListNode*p,*q；int k；head=(ListNode*)malloc(sizeof(ListNode);,q=head；scanf(“%d”,ListNode*head p=(ListNode*)malloc(sizeof(ListNode)(3)p-data=k(4)q-next=p(5)q=p,6、有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个
8、出栈）的次序有哪几个？,三个：CDEBA，CDBEA，CDBAE,7、（1）单向循环链表中有一个指向后继的指针域next,在一个以 h 为头的单循环链表中，p 指针指向表尾的条件是什么？（2）双向链表中有两个指针域，llink和rlink，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入算法是什么？（3）在双向链表存储结构中，删除p所指的结点的算法是什么？,(1)p-next=h(2)p-llink-rlink=q;q-rlink=p;q-llink=p-llink;p-llink=q;(3)p-llink-rlink=p-rlink p-rl
9、ink-llink=p-llink;,8、下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空；操作完成后A，B保持不变，C中元素按递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A,B)实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再
10、删除并释放表示结果集合的链表的表头结点。,typedef struct node int element;struct node*link;NODE;NODE*A，*B，*C;NODE*append(NODE*last,int e)last-link=(NODE*)malloc(sizeof(NODE);last-link-element=e;return(last-link);NODE*difference(NODE*A,NODE*B)NODE*C,*last;C=last=(NODE*)malloc(sizeof(NODE);while(1)_ if(A-elementelement)la
11、st=append(last,A-element);A=A-link;else if(2)_ A=A-link;B=B-link;ELSE(3)_;while(4)_ last=append(last,A-element);A=A-link;(5)_;last=C;C=C-link;free(last);return(C);/*call form:C=difference(A,B);*/,(1)(A!=null&B!=null)两均未空时循环(2)A-element=B-element 两表中相等元素不作结果元素(3)B=B-link 向后移动B表指针(4)A!=null 将A 表剩余部分放入
12、结果表中(5)last-link=null 置链表尾,树型结构,1若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A9 B11 C15 D不确定2.有n个叶子的哈夫曼树的结点总数为（）。A不确定 B2n C2n+1 D2n-13一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D是任意一棵二叉树,B,C,D,选择题,4在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A都不相同B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同5.引
13、入二叉线索树的目的是（）A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一,B,A,6.由3 个结点可以构造出多少种不同的有向树？（）A2 B3 C4 D5 7.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A1.n中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（）AA2i(2i=n)BA2i+1(2i+1=n)CAi-2 D条件不充分，无法确定,A,D,填空题,1树在计算机内的表示方式有_(1)_，_(2)_，_(3)_。.2深度为k的完全二叉树至少有_(1)_个结
14、点，至多有_(2)_个结点。3设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有_(1)_个结点，右子树中有_(2)_个结点。,(1)双亲表示法(2)孩子表示法(3)孩子兄弟表示法,(1)2k-1(2)2k-1,(1)n1-1(2)n2+n3,填空题,4一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶子结点数为_。5.在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是_。,21
15、,双亲的右子树中最左下的叶子结点,1、有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，请回答以下两问：（1）构造一棵哈夫曼树，写出具体构造过程；（2）求其带权路径长度WPL为多少，字符c的编码是什么。,应用题,第一步：构造六棵只有根节点的树：第二步：取其中两棵根节点值最小的作为左右子树构造一个二叉树，该二叉树的根节点的值为左右孩子节点的值得和，然后删除以上两棵而根节点值最小的树。如下：第三步：如第二步操作依次构造，并进行删除如下：,第四步：如下：第五步：,第六步：(33)(2)WPL=7*2+8*2+9*2+4*3+2*4+3*4=80 C:1
16、10,2、试找出满足下列条件的二叉树：（1）先序序列与后序序列相同；（2）中序序列与后序序列相同；（3）先序序列与中序序列相同；,（1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。（2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。,3、二叉树先序序列：A B C D E F G H R,中序序列：B D C E A F H G R,画出二叉树,由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。,4、将树转换成二叉树，写出先序、中序和后序遍历序列,先序遍历：,中序遍
17、历：,后序遍历：,A,B,F,G,H,L,C,D,I,E,J,M,K,F,G,L,H,B,C,I,D,M,J,K,E,A,L,H,G,F,I,M,K,J,E,D,C,B,A,5.请编写一个算法，交换二叉树中每一个结点的左、右孩子,void exchangeLR(JD*bt)JD*q;if(bt!=NULL)q=bt-lchild;bt-lchild=bt-rchild;bt-rchild=q;exchangeLR(bt-lchild);exchangeLR(bt-rchild);,图结构,选择题,1图中有关路径的定义是（）。A由顶点和相邻顶点序偶构成的边所形成的序列B由不同顶点所形成的序列C由
18、不同边所形成的序列 D上述定义都不是2要连通具有n个顶点的有向图，至少需要（）条边。An-1 Bn Cn+1 D2n3在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A1/2 B2 C1 D4,A,B,B,C,4下列哪一种图的邻接矩阵是对称矩阵？（）A有向图 B无向图 CAOV网 DAOE网5.下列说法不正确的是（）。A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历C图的深度遍历不适用于有向图D图的深度遍历是一个递归过程6.关键路径是事件结点网络中（）。A从源点到汇点的最长路径
19、B从源点到汇点的最短路径C最长回路 D最短回路,B,C,A,填空题,1.判断一个无向图是一棵树的条件是_。2一个连通图的_是一个极小连通子图。3.遍历图的过程实质上是_，breath-first search遍历图的时间复杂度_；depth-first search遍历图的时间复杂度_，两者不同之处在于_，反映在数据结构上的差别是_。,有n个顶点，n-1条边的无向连通图,生成树,(1)查找顶点的邻接点的过程(2)O(n+e)(3)O(n+e)(4)访问顶点的顺序不同(5)队列和栈,填空题,4.Prim（普里姆）算法适用于求_的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_的网的最小
20、生成树5.Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按_次序依次产生，该算法弧上的权出现_情况时，不能正确产生最短路径。,边稠密 边稀疏,递增 负值,1.对有向图写出每个顶点入度与出度；邻接矩阵 邻接表,2 从顶点4出发，画出一棵深度优先生成树和广度优先生成树,4,4,2 从顶点4出发，画出一棵深度优先生成树和广度优先生成树,3 写出执行构造最小生成树Prim算法后的最小生成树,4 用Dijkstra算法求从顶点V1到其它各顶点的最短路径。,2015V3:15,20-25V2:20,-3025V6:25,-2930-V4:29,-30-V5:30,5.求关键路径，完成工
21、程最短时间,V1V2V3V4V5V6V7,a1a2a3a4a5a6a7a8a9a10a11,0,8,16,19,20,25,27,27,25,20,19,16,8,0,完成工程最短时间27天,查找、排序,选择题,1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A(n-1)/2 B.n/2 C.(n+1)/2 D.n2.下面关于二分查找的叙述正确的是()表必须有序，表可以顺序方式存储，也可以链表方式存储 B.表必须有序且表中数据必须是整型，实型或字符型 C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储
22、,C,D,选择题,C,D,3.既希望较快的查找又便于线性表动态变化的查找方法是()A顺序查找 B.折半查找 C.索引顺序查找 D.哈希法查找4.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()A8 B3 C5 D9,选择题,D,A,5某内排序方法的稳定性是指()。A该排序算法不允许有相同的关键字记录B该排序算法允许有相同的关键字记录C平均时间为0（n log n）的排序方法D以上都不对6下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。()
23、A选择排序法 B.插入排序法 C.快速排序法 D.堆积排序法,填空题,在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为_.2.哈希表是通过将查找码按选定的_(1)_和 _(2)_，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)_和 _(4)_。一个好的哈希函数其转换地址应尽可能_(5)_，而且函数运算应尽可能_(6)_。,4,(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单,填空题,3.平衡二叉树又称_，其定义是_。4.动态查找表和静态查找表
24、的重要区别在于前者包含有_和_运算，而后者不包含这两种运算,AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。,插入 删除,设哈希函数H（k）=3K mod 11，哈希表的大小为11(0.10)，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表：（1）线性探测再散列；（2）链地址法；（3）分别求出等概率下查找成功时的平均查找长度ASL线性和ASL链地址。,ASL线性=（1+1+1+2+1+2+1+2）/8=11/8ASL链地址=（51+32）/8=11/8,一棵二叉排序树结构如
25、下,各结点的值从小到大依次为1-9，请标出各结点的值。,依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树(1)试画出生成二叉排序树的全过程;(2)对该二叉排序树作中序遍历，试写出遍历序列;(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。,（2）对该二叉排序树作中序遍历，遍历序列为：10，12，15，20，24，28，30，35，46，50，55，68（3）假定每个元素的查找概率相等，该二叉排序树的平均查找长度为：ASL=（1+2*2+3*3+4*3+5*3）/12=41/12,设记录的关键字集合K=49、38、
26、65、97、76、13、27、48、55、4，给定的增量序列D=5，3，1，请写出对K按“希尔排序”排序时各趟排序的分组情况和结束时的结果。,取d1=5一趟排序：13 27 48 55 4 49 38 65 97 76取d2=3二趟排序：13 4 48 38 27 49 55 65 97 76取d3=1三趟排序：4 13 27 38 48 49 55 65 76 97,复习,(了解)1.绪论：数据结构、算法2.线性表：类型特点；顺序存储；链式存储（单链表、循环链表、双向链表）3.栈和队列：特点和应用(了解)4.串：表示和实现，模式匹配(了解)5.数组和广义表：顺序表示；矩阵压缩存储；广义表存储结构,复习,6.树和二叉树：类型定义、二叉树特点；遍历；树、二叉树、森林转换；赫夫曼树7.图：定义、存储；遍历、最小生成树、拓扑排序、关键路径、最短路径9.查找：静态查找表（顺序、折半）；二叉排序树（查找、插入、删除）；哈希表10.排序：插入(直接、折半、希尔)；快速(冒泡、快速)；选择(简单、堆),考试题型,一、填空题。（每空1分，共10分）二、简答题（每题10分，共30分）三、综合应用题（每题15分，共60分）,
