2022年数据结构GCT复习题收集 .pdf

数据结构复习题：第一章知识点：数据结构：（P3）包括 3 个方面的内容：逻辑结构、物理结构及运算数据结构从逻辑上分包括线性结构和非线性结构算法 5 个特性（ P13）练习题：1、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（错）数据的逻辑结构是指数据的数据元素之间的逻辑关系。（对）2、在数据结构上，从逻辑上可以把数据结构分成（ C ） 。A、 动态结构和静态结构B、紧凑结构和非紧凑结构C、 线性结构和非线性结构D 、内部结构和外部结构3、算法的五个重要特性是什么？答：有穷性 、确定性、可行性、输入和输出。4、算法的时间复杂度仅与问题的规模有关吗？算法的时间复杂度与问题的规模有关外，还与输入实例的(初始状态 )有关。一般，将算法求解问题的输入量称为(问题的规模)。评价一个算法时间性能的主要标准是(算法的时间复杂度)。5、常用的存储表示方法有哪几种？顺序存储、链式存储、索引存储及散列存储6、算法的时间复杂度取决于（ C）A问题的规模 B. 待处理数据的初态 C. A和 B 7、集合与线性表的区别在于是否按关键字排序。( 错 ) 8、运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。栈和队列，逻辑结构和存储方式完全相同，但运算不同。9、在编制管理通讯录的程序时, 什么样的数据结构合适 ? 为什么? A：应从两方面进行讨论：如通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方便，既能顺序查找也可随机查找；若通讯录经常有增删操作，用链式存储结构较为合适，因为不需要因为数据的变动移动大量数据。10、试举一例， 说明对相同的逻辑结构 ,同一种运算在不同的存储方式下实现，其运算效率不同。A：线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为 O（n） ；而在链式存储方式下，插入和删除时间复杂度都是O（1） 。11、对于一个数据结构，一般包括哪三个方面的讨论？A：逻辑结构、存储结构、操作（运算） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 线性结构知识点：线性表、栈、队列区别；顺序表与链表；子串练习题：1、线性链表不具有的特点是（ A ） 。A、随机访问 B、不必事先估计所需存储空间大小C、插入与删除时不必移动元素 D、所需空间与线性表长度成正比或：线性表的顺序存储结构是一种(随机存取)的存储结构。2、不带头结点的单链表head为空的判定条件是（A ） 。A、head=NULL B、 head-nex= NULL C、head-next=head D、 head!=NULL 2-1 带头结点的单链表 head为空的判定条件是（B ） 。A、head=NULL B、 head-nex= NULL C、head-next=head D、 head!=NULL 3、栈与一般的线性表的区别在于( B )。A数据元素的类型不同。B运算是否受限制。C数据元素的个数不同。D逻辑结构不同。4、 线性表（ a1,a2, ,an ） 以链接方式存储时， 访问第 i 位置元素的时间复杂性为 （ C ）AO （i ） BO （1） CO （n） DO （i-1 ）5、在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（对）6、顺序表中逻辑上相邻的元素的物理位置_相邻_ 。7、在一个长度为 n 的顺序表中删除第i 个元素，要移动 _n - i_个元素。8、在( C )运算中，使用顺序表比链表好。A、插入B、删除 C、根据序号查找D、根据元素值查找9、 在一个单链表中，指针p 所指结点之后插入一个指针s 所指结点时，应执行s-next= p-next 和 p-next= s 的操作。9-1、设单链表的结点结构为 (data,next)，next 为指针域，已知指针px 指向单链表中 data为 x 的结点，指针 py 指向 data为 y 的新结点, 若将结点 y 插入结点 x 之后，则需要执行以下语句 : py-next=px-next； px-next=py_; 10、对于一个具有n 个结点的单链表，在 *p 结点之后插入一个新结点的时间复杂度是O(1)；在给定值为 x 的结点后插入一个新结点的时间复杂度为O(n)。11、在单链表、双链表和单循环链表中，若仅知道指针p 指向某结点，不知道头指针，能否将结点 *p 从相应的链表中删去 ?若可以，其时间复杂度各为多少? 答：单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p 结点后的结点。但是由于不知道其头指针，所以无法访问到p 指针指向的结点的直接前趋。因此无法删去该结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 双链表。由于这样的链表提供双向指针，根据*p 结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继 )，又因为是循环链表，所以我们可以通过查找，得到p 结点的直接前趋。因此可以删去p 所指结点。其时间复杂度应为 O(n)。12、 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（错）（以下请参考严蔚敏数据结构教材P63-65 页）13、若用一个大小为 6 的一维数组来实现循环队列， 且当前 rear 和 front的值分别为 0和 3。当从队列删除一个元素，再加入两个元素后，rear 和 front的值分别是（ B ） 。A、 1 和 5 B、 2 和 4 C、 4 和 2 D、 5 和 1 答：Rear = (Rear + 2)%6 = 2； Front = (Front + 1)%6 = 4 13-1、 循环队列用数组 A0.m-1 存放其元素值，已知其头尾指针分别是front和 rear ，则当前队列的元素个数是_（rear-front+m）% m_ 。13-2、循环队列的优点是什么 ? 如何判别它的空和满 ? 答：循环队列的优点是：它可以克服顺序队列的 假上溢 现象，能够使存储队列的向量空间得到充分的利用。 判别循环队列的空或 满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间, 每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。14、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( C ) 最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表15、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（带尾指针的单循环链表）存储方式最节省运算时间。16、线性表的特点是每个元素都有一个前驱和一个后继。（错）17、取线性表的第 i 个元素的时间同 i 的大小有关 . ( 错 ) 17、链表是采用链式存储结构的线性表, 进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（对 ）18、循环链表不是线性表。 ( 错 ) 19、链表中的头结点仅起到标识的作用。(错 ) 或，在链表的开始结点前设置头结点的优点是什么？答：头结点是在链表的开始结点之前附加一个结点。它具有两个优点：（1）由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。20、取线性表的第 i 个元素的时间同 i 的大小有关 . ( 错 ) 21、何谓队列的 假溢现象？如何解决？答：队列的假溢现象是指用数组实现的顺序队列中，队尾指针已到达数组的下标上界产生上溢而队头指针之前还有若干空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间首尾相连。（以下请参考严蔚敏数据结构教材P22、P24页）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 22、请写出在顺序线性表、单链线性表的第i 个位置之前插入元素e 的算法。要求：（1） 写出存储结构。（2） 写出该算法的设计思想。（3） 用 C 、C+ 或者 JAVA描述该算法。23、请写出在顺序线性表、单链线性表中删除第i 个元素的算法。要求：（1）写出存储结构。（2）写出该算法的设计思想。（3）用 C、C+ 或者 JAVA描述该算法。(1) #define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef struct ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量(以 sizeof(ElemType)为单位 ) SqList; (2) 首先判断i 合法与否；其次，如果当前存储空间已满，可再申请增加空间；再次为待插入的值腾出空间，需要依次移动第n 个元素到第i+1 个元素；最后把待插入元素放在第i 个元素所在的位置。(3) Status ListInsert_Sq(Sqlist &L, int i, ElemType e) / 在顺序线性表L 的第 i 个位置之前插入新的元素e / i 的合法值为1=i=ListLength_Sq(L) + 1 if(iL.length+1) return ERROR; / i 值不合法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.elemi-1); / q 为插入位置for(p=&(L.elemL.length-1); p=q; -p) *(p+1)=*p; / 插入位置及之后的元素后移*q=e; / 插入 e +L.length; / 表长增 1 return OK; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 数组和广义表知识点：广义表定义（ P106） 、运算、稀疏矩阵（ P96）1、二维数组 A1020采用列优先顺序存储，每个元素占1 个存储单元，并且第一个元素的存储地址是200，则 A612的地址是 365。 （ A612地址应该为 326 ）200 + 12*10 + 6 = 326 2、 设广义表 L=（ （a， b） , （c， d） ） ， 运算 head （head （tail （L） ） ） 的值是C 。3、对稀疏矩阵进行压缩存储目的是（ C ） 。A便于进行矩阵运算 B便于输入和输出C节省存储空间D降低运算的时间复杂度4、 已知广义表 LS(a,b,c),(d,e,f),运用 head 和 tail函数取出 LS中原子 e 的运算是( C )。A. head(tail(LS) B. tail(head(LS) C. head(tail(head(tail(LS) D. head(tail(tail(head(LS) 5、 下面说法不正确的是 ( A )。A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构6、 求下列广义表运算的结果：(1)head (p,h,w); (2)tail(b,k,p,h); (3) head (a,b),(c,d); (4)tail(a,b),(c,d); (5)head(tail(a,b),(c,d); (6)tailhead)(a,b),(c,d). 答：(1)head (p,h,w)=p; (2)tail(b,k,p,h)=(k,p,h); (3)head (a,b),(c,d)=(a,b); (4)tail(a,b),(c,d)=(c,d); (5)head(tail(a,b),(c,d)=(c,d); (6)tail(head(a,b),(c,d)=(b) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 树和二叉树（ P118）知识点：树与二叉树区别、 线索二叉树（P132） 、 哈夫曼树（P144） 、 完全二叉树、满二叉树（P124） ；遍历（先序、中序、后序、层次）练习题：1、二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索。（ F ）2、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。 （T ）3、 哈夫曼树一定是满二叉树。 （ F ）4、 哈夫曼编码是最优前缀码。 （T ）5、二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索。（ F ）6、由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（ F ）7、按二叉树的定义，具有三个结点的二叉树共有6 种。 （ F ）5 种8、给定二叉树的先序和后序遍历序列，能否重构出该二叉树？若能，试证明之；否则，给出反例。答：不能重构出二叉树。如先序序列都是AB ，后序序列是 BA ，但可构造出 2 个二叉树，如下图，：9、以数据集2，3，4，7，8，9为结点权值构造哈夫曼树。并求其带权路径长度WPL,最后给出每个结点的哈夫曼编码。解：哈夫曼树如下：带权路径长度 WPL9*2+2*4+3*4+4*3+7*2+8*2=80名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 哈夫曼编码： 2：1010 3：1011 4：100 7：00 8：01 9：11另：请参考p148 例 6-2 10、 （简答）说出树和二叉树的差别。答：树和二叉树是两种不同的数据结构。对于二叉树来说，每个结点最多只有两个孩子，分别叫左孩子和右孩子；如果只有一个孩子，则该孩子还是有左右之分的。而树则不然。11、在一非空二叉树的中序遍历序列中，根结点的右边( A ) 。A只有右子树上的所有结点 B只有右子树上的部分结点C只有左子树上的部分结点 D只有左子树上的所有结点12、有n 个结点的二叉链表中，其中空的指针域为n+1. 指向孩子的指针个数为33 。注：2N - （N+1 ）13、二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK ；中序遍历 : HFIEJKG 。该二叉树根的右子树的根是( C )。A、 E B、 F C、 G D、 H注：见教材 P154，例 6-5 14、一棵二叉树有 67 个结点，这些结点的度要么是0，要么是 2。这棵二叉树中度为2的结点有 33 个。注：利用二叉树性质3，见教材 P124 15、一棵树按照左子女 - 右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有 _右_子女。16、 （P128）以二叉链表为存储结构，试写出三种递归遍历二叉树的算法。用二叉链表做为存储结构，中序遍历算法可描述为：typedef char DataType； / 用户可根据具体应用定义DataType 的实际类型typedef struct node DataType data； Struct node *lchild，*rchild； / 左右孩子指针BinTNode； / 结点类型typedef BinTNode *BinTree；/BinTree为指向 BinTNode类型结点的指针类型void InOrder(BinTree T) /算法里 是为了说明执行过程加入的标号 if(T) / 如果二叉树非空 InOrder(T-lchild)； printf(c ，T-data) ； / 访问结点 InOrder(T-rchild); / InOrder 17、二叉树的遍历算法可写为通用形式。例如通用的中序遍历为：void Inorder(BinTree,T,void(* visit)(DataType x) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - if (T) Inorder(T-lchild,Visit);/遍历左子树Visit(T-data);/通过函数指针调用它所指的函数来访问结点Inorder(T-rchild,Visit);/遍历右子树 其中 Visit是一个函数指针，它指向形如void f(DataType x)的函数。因此我们可以将访问结点的操作写在函数f 中通过调用语句Inorder(root,f)将 f 的地址传递给Visit,来执行遍历操作。 请写一个打印结点数据的函数，通过调用上述算法来完成书中的中序遍历。解：函数如下：void PrintNode(BinTree T) printf(%c,T-data); / 定义二叉树链式存储结构typedef char DataType;/定义 DataType 类型typedef struct node DataType data; struct node *lchild, *rchild;/左右孩子子树BinTNode; /结点类型typedef BinTNode *BinTree ;/二叉树类型void Inorder(BinTree T,void(* Visit)(DataType x) if(T) Inorder(T-lchild,Visit);/遍历左子树Visit(T-data); /通过函数指针调用它所指的函数访问结点Inorder(T-rchild,Visit);/遍历右子树 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 图知识点：邻接矩阵（ P161） 、邻接表（ P163） 、有（无）向图、 DFS 和 BFS（P167）练习题：1、在图的遍历算法中 , 设置一向量记录已访问过的结点是为了避免重复访问同一顶点。（ T ）2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（ F ）3、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 （F ）4、下面关于图的存储的叙述中，哪一个是正确的。 ( A ) A用邻接矩阵法存储图 , 占用的存储空间数只与图中结点个数有关, 与边数无关。B用邻接矩阵法存储图 , 占用的存储空间数只与图中边数有关, 与结点个数无关。C用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边数无关。D用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个数无关。5、对于一个具有n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为( A )。An B. n+1 C. n-1 D. n+e 6、图的广度优先搜索类似于树的（ D ）次序遍历。A、先序 B 、中序C 、后序 D 、层次7、对于一个具有n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为( A )。A、N B、n+1 C、n-1 D、n+e 8、 （简答）DFS 和 BFS 遍历各采用什么样的数据结构来暂存顶点? 当要求连通图的生成树的高度最小，应采用何种遍历? 答：DFS 遍历采用栈来暂存顶点。BFS 采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS 遍历。9、n (n 0) 个顶点的无向图最多有 _n(n-1)/2_条边，最少有 _0_条边。10、一个 n 个顶点的连通无向图，其边的个数至少为（ A ） 。An-1 Bn Cn+1 Dnlogn ；10-1、n 个结点的完全有向图含有边的数目（D ） 。An*n n（n） Cn2 Dn*（nl ）11、用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？设图的顶点个数为n(n 0) ，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。12、请回答下列关于图(Graph) 的一些问题： （每题 4 分）（1） 有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边? （2） 表示有 1000 个顶点、 l000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？答: （1）n(n-1) ， n (2) 106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 查找基本知识点：静态查找（顺序查找、折半查找、分块查找）动态查找（二叉排序树、平衡二叉树、B树）散列表查找（除留余数法、冲突解决方法）1、按 13、24、37、90、53 的次序形成平衡二叉树， 该平衡二叉树的高度为 3 、根为 24 、左子树的数据为 13 、右子树的数据为 37 、53、90 。2、一个线性表中共有625 个元素，假定每个元素的查找概率相同，如果采用分块查找，则对这些元素共分为 25 索引块为最佳（基本查找方法都采用顺序查找）。3、顺序查找中监视哨的作用是什么？答：其作用主要有两个：(1) 防止下标越界(2) 减少比较次数，提高查找效率。4、一棵树，如果它的左右子树都是AVL（平衡二叉树） 的，则该树是 AVL 的。 （ F ）5、二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（T ）6、 （简答）从一棵空的二叉排序树开始， 将以下关键码值依次插入： 25,13,15,31,7,20,37 ，请画出插入全部完成后的二叉排序树。提示：请参考 P229二叉排序树的构造过程。7、 （简答）设散列表的地址空间为0 10，散列函数为H（key）=key%11 ，采用线性探查法解决冲突，并将键值序列15，36，50，27，19，48依次存储到散列表中，请画出相应的散列表，当查找键值48 时需比较多少次？解：散列表如下图：0 1 2 3 4 5 6 7 8 9 10 36 15 27 50 48 19 当查找键值 48 时需比较 4 次。8、画出对长度为 18 的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。解：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 等概率情况下，查找成功的平均查找长度为：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 排序知识点：五大内排、（不）稳定排序、冒泡练习题：1、内部排序方法可分成哪5 类？(1)插入排序(2)选择排序(3)交换排序(4)归并排序(5)分配排序2、两个序列如下：L1=25，57，48，37，92，86，12，33 L2=25，37，33，12，48，57，86，92 用冒泡排序方法分别对序列L1 和 L2 进行排序，交换次序较少的是序列L2 。提示：因为 L2 基本有序，实际上只有前面4 个元素是无序的3、若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变。则这种排序方法是稳定的排序方法。4、有 10万个无序且互不相等的正整数序列，采用顺序存储方式组织，希望能最快地找出前 10 个最大正整数，采用 (C) 方法比较好。A、快速排序B、希尔排序C、堆排序D、归并排序5、下列数据中，（ C ）是非线性数据结构。A栈 B. 队列 C. 完全二叉树 D. 堆6、对一组数据（ 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. 快速 D. 插入提示：选择排序的特点是每次都是从无序的序列中选取最小的元素。7、下列序列中， （ D ）是执行第一趟快速排序后所得的序列。 A. 11，18，68 69 23，93，73 B. 11， 69，23 68 18，93，73 C. 93，73 68 11， 69，23，18 D. 11， 68，23，18 69 93，73 提示：第一趟快速排序的结果是枢轴69 的左边的元素都小于它，右边的元素都大于它。8、请写出对 49 ，38，65，97，76，13，27，49，55，04每趟希尔排序的结果。提示：见教材 271 9、请写出对 49 ，38，65，97，76，13，27每趟归并排序的结果。提示：见教材 283 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -