数据结构复习题Word文件下载.docx

1、A空或只有一个结点B完全二叉树C二叉排序树D高度等于其结点数13在一个图中，所有顶点的度数之和等于所有边数的C倍。 A 1/2 B 1 C 2 D 414在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。17、一个有n个顶点的无向图最多有C条边。A n B n（n-1） C n（n-1）/2 D 2n15、具有4个顶点的无向完全图有A条边。A 6 B 12 C 16 D 2016、采用邻接表存储的图的深度优先遍历类似于二叉树的A。A 先序遍历 B中序遍历 C后序遍历 D 按层遍历17、采用邻接表存储的图的广度优先遍历类似于二叉树的D。18、顺序查找法适合于存储结构为B的线性表。A

2、散列存储 B。顺序存储或链式存储 C。压缩存储 D。索引存储19、对线性表进行折半查找时，要求线性表必须C。A顺序存储 B。以链接方式存储 C。以顺序存储，并且结点按关键字有序排列。D以链接方式存储，并且结点按关键字有序排列。21数据结构在计算机内存中的表示是指 。A数据的存储结构 B数据结构 C数据的逻辑结构 D数据元素之间的关系22某线性表最常用的操作是在最后一个结点之后插入一个结点或删除一个结点，故采用 存储方式最节省运算时间。A单链表 B仅有表头结点的单循环链表 C双链表 D仅有表尾指针的单循环链表23如果最常用的操作是取第i个结点及其前驱，则采用 存储方式最节省运算时间。A单链表 B

3、双链表 C单循环链表 D顺序表24栈和队列的共同点是 。A都是先进后出 B都是先进先出 C只允许在端点处插入和删除元素 D没有共同点25空串与空白串是相同的，这种说法 。A正确 B不正确26数组元素之间的关系， 。A是线性的 B是树形的 C既是线性的又是树形的 D既不是线性的又不是树形的27树最适合用来表示 C。A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素这间无联系的数据28.如果T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的A。A先序B中序C后序D层次序29、具有6个顶点的无向图至少应该有A条边才能确保是一个连通图。A 5 B 6 C 7 D

4、830、采用邻接表存储的图的深度优先遍历类似于二叉树的A。31、采用邻接表存储的图的广度优先遍历类似于二叉树的D。32、顺序查找法适合于存储结构为B的线性表。33、对线性表进行折半查找时，要求线性表必须C。34、二叉树为二叉排序树的充分必要条件是其中任一结点的值大于其左儿子的值，小于其右儿子的值，这种说法B。A正确 B。不正确35算法分析的目的是 ，算法分析的两个主要方面是 。A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性A空间复杂度和时间复杂度 B正确性和简明性 C可读性与文挡性 D数据复杂性和程序复杂性36与单链表相比，双链表的

5、优点之一是 。A插入、删除操作更简单 B可以进行随机访问 C可以省略表头指针和表尾指针 D顺序访问相邻结点更灵活。37一个队列的入队序列是1，2，3，4，则队列的输出序列是 。A4，3，2，1 B。1，2，3，4 C。1，4，3，2 D。3，2，4，138 是 “abcd321ABCD”的子串。Aabcd B.321AB C.”abcABC” D.”21AB”39一个n*n的对称矩阵，如果以行序或列序放入内存，则容量为 。A.n*n B.n*n/2 C.n*（n-1）/2 D（n+1）*（n+1）/240二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法B。A正确B错误41

6、深度为15的二叉树至多有个结点。42、一个有19个顶点的无向图最多有 条边。43、具有n个顶点的无向图至少应该有c条边才能确保是一个连通图。A n B n+1 C n-1 D n/244、顺序查找法适合于存储结构为B的线性表。45、对线性表进行折半查找时，要求线性表必须C。46. 下列各选项中属于逻辑结构的是 B 。A.哈希表 B.有序表 C.单链表 D.顺序表47. 对于数据结构，以下叙述中不正确的是 B 。A.数据的逻辑结构与数据元素本身的形式和内容无关B.数据的逻辑结构是数据的各数据项之间的逻辑关系C.数据元素是数据的基本单位D.数据项是数据的最小单位48. 某算法的时间复杂度为O（n2

7、），表明该算法的 C 。A.问题规模是n2 B.执行时间等于n2C.执行时间与n2成正比 D.问题规模与n2成正比4. 通常在单链表中增加一个头节点，其目的是为了 C 。A.使单链表至少有一个节点 B.标识表节点中首节点的位置C.方便单链表运算的实现 D.说明单链表是线性表的链式存储49. 删除某个双链表中的一个节点（非首、尾节点），需要修改 B 个指针域。A.1 B.2 C.3 D.450. 栈和队列是两种不同的数据结构，但它们中的元素具有相同的 B 。A.抽象数据类型 B.逻辑结构C.存储结构 D.运算51. 元素a、b、c、d、e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所

8、有的元素都出栈，则所有可能的出栈序列中，以元素d开头的序列有哪些 ？52. 设环形队列中数组的下标是0N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为 D 。A.r-f B.r-f-1 C.（r-f）N+1 D.（r-f+N）N53. 已知循环队列存储在一维数组A0.n-1中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A0处，则初始时front和rear的值分别是 B 。A.0，0 B.0，n-1 C.n-1，0 D.n-1，n-154. 对于n阶（n2）对称矩阵，采用压缩

9、方法以行序优先存放到内存中，则需要 A 个存储单元。A.n（n+1）/2 B.n（n-1）/2 C.n2 D.n2/255. 一棵度为4的树T中，若有18个度为4的节点，10个度为3的节点，1个度为2的节点，9个度为1的节点，则树T的叶子节点个数是 。56. 一个具有n（n2）个顶点的无向图，至少有 B 个连通分量，最多有 D 个连通分量。A.0 B.1 C.n-1 D.n57. 含有n（n2）个顶点的无向图的邻接矩阵必然是一个 A 。A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵58. 设有98个元素的有序顺序表，用折半查找时，成功时最大的比较次数是 。59. 已知一个长度为16的顺

10、序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则平均关键字比较的次数是 A 。A.70/17 B.70/16 C.60/17 D.60/1660. 以下关于m阶B-树的叙述中正确的是 C 。A.每个节点至少有两棵非空子树B.树中每个节点至多有m/2-1个关键字C.所有叶子节点均在同一层上D.当插入一个关键字引起B-树节点分裂时，树增高一层61. 为提高散列（哈希）表的查找效率，可以采取的正确措施是 D 。.增大装填（载）因子.设计冲突（碰撞）少的散列函数.处理冲突（碰撞）时避免产生聚集（堆积）现象A.仅 B.仅 C.仅、 D.仅、62. 数据序列15,16,17,4,5,

11、6,20,1,2只能是 C 的两趟排序后的结果。A.简单选择排序 B.冒泡排序 C.直接插入排序 D.堆排序63. 用某种排序方法对顺序表22,78,21,58,15,27,69,35,19进行排序，各趟元素序列的变化情况如下：（1）22,78,21,58,15,27,69,35, 19（2）19,15,21,22,58,27,69,35,78（3）15, 19,21,22,35,27,58,69,78（4）15, 19,21,22,27,35,58,69,78则所采用的排序方法是 B 。A. 简单选择排序 B.快速排序 C.直接插入排序 D.归并排序64. 若线性表最常用的运算是存取第i个元

12、素及其前趋元素的值，则采用 D 存储方式节省时间。A.单链表 B.双链表C.单循环链表 D.顺序表65. 在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为 D 。A.O（log2n） B.O（1）C.O（n2） D.O（n）66. 一个nn的对称矩阵A，如果采用以列优先（即以列序为主序）的压缩方式存放到一个一维数组B中，则B的容量为 C 。A. n2 B. C. D. 67. 若一棵3次树中有a个度为1的节点，b个度为2的节点，c个度为3的节点，则该树中有 D 个叶子节点。A.1+2b+3c B.a+2b+3c C.2b+3c D.1+b+2c68. 一棵完全二

13、叉树中有401个叶子节点，则至少有 个节点。69. 在含有n个结点的线索二叉树中，线索的数目为 C 。A.n-1 B.n C.n+1 D.2n 73. 有一个长度为12的有序表R0.11，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为 B 。A.35/12 B.37/12 C.39/12 D.43/1274. 数据序列8,9,10,4,5,6,20,1,2只能是 A 的两趟排序后的结果。A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D.堆排序75. 有一些内排序算法，在最后一趟排序结束前可能所有的数据都没有放在其最终的位置上，这些排序算法是 C 。.

14、希尔排序 .快速排序 .归并排序 .堆排序A.仅、 B.仅、 C.仅、 D.仅、76. 在以下排序方法中，关键字比较的次数与元素的初始排列次序无关的是 D 。A.快速排序 B.冒泡排序 C.插入排序 D.简单选择排序 77若串S=“CHINAFZ”，其子串的个数是 78一维数组和线性表的区别是 A 。 A前者长度固定，后者长度可变 B后者长度固定，前者长度可变 C两者长度均固定 D两者长度均可变二、解答题。1、已知某二叉树的先序遍历序列是ABDGCEFH，中序遍历序列是DGBAECHF，给出它的后序遍历序列。GDBEHFCA2、设给定权集W=2，3，4，7，9，请构造出关于W的一棵哈夫曼树，并

15、求出带权路径长度WPL。3、有一份电文中共使用5个字符A，B，C，D，E，它们出现的频率依次为4，7，5，2，9，请画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。A：001 B：10 C：01 D：000 E：114. 简要叙述堆和二叉排序树的区别，并给出关键字序列23,26,32,71,48,40,99,75,53,87调整为大根堆后的结果（直接画出调整后的大根堆）。5. 按关键字13、24、37、90、53的次序构造一棵平衡二叉树，回答以下问题：（1）该平衡二叉树的高度是多少？（2）其根节点的关键字是什么？（3）其中经过了哪些调整（指出调整名称和次数）。答：如图1所示是构造平衡二叉树的过

16、程，回答问题如下：（1）该平衡二叉树的高度是3。（2）根节点的关键字是24。（3）其中经过了一次RR调整和一次RL调整。图1 构造平衡二叉树的过程6. 一棵二叉排序树按先序遍历得到的关键字序列为：（70,38,30,47,40,48,82,60,95,100）。回答以下问题：（1）画出该二叉排序树。（2）求在等概率条件下的查找成功的平均查找长度。7. 有一个无向带权图如图2所示，采用Dijkstra算法求顶点0到其他顶点的最短路径和最短路径长度，要求给出求解过程（即给出求最短路径中各步骤的S、dist和path值）。图2 一个无向图8. 将整数序列14,15,27,23,14,30,6中的数依

17、次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，要求用图形给出构造过程，不需编写程序。9求算法的时间复杂度为多少类型的题目？10. 指出以下关于堆及堆排序叙述的正确性。（10分）（1）任何一棵完全二叉树一定是一个堆。（2）在大根堆中，最大的元素在根节点中，最小的元素一定在某个叶子节点中。（3）在大根堆中，堆中任一节点的关键字均大于它的左、右孩子的关键字。（4）在一个小根堆中，从根节点到某个叶子节点的路径上的所有结点的关键字正好构成一个递增序列。（5）堆排序在最坏情况下的时间复杂度为O（n2）。（6）堆排序是一种与初始排序序列无关的排序方法。三、算法设计题1. 设计一个算法，将一个带头结点

18、的数据域依次为a1，a2，an（n3）的双链表的所有结点逆置，即第一个结点的数据域变为an，即第二个结点的数据域变为an-1，最后一个结点的数据域为a1。双链表中每个结点的类型如下：typedef struct nhode ElemType data; struct node *prior,*next; DLinkList;解：采用前插法建表，算法如下：void Reverse（DLinkList *&h） DLinkList *p=h-next,*q=p-next; h-next=NULL; while （p!=NULL） p-next=h- /*将p所指结点插入到头结点之后*/ p-pri

19、or=h; p=q; q=p- 2. 假设二叉树采用二叉链存储结构进行存储，每个结点有data、lchild和rchild三个域。设计一个算法，计算一棵给定二叉树中节点值为x的节点个数（注意在一棵二叉树中可能存在相同节点值的节点），并给出你所写出的算法的时间复杂度（设二叉树中结点个数为n）。对应的递归算法如下：int FindSum（BTNode *b） if （b=NULL） return 0; if （b-data=x） return（1+FindSum（b-lchild）+FindSum（b-rchild）; else return（FindSum（b-3. 假设一个不带权的无向图采用邻

20、接表G进行存储，设计一个算法FindaPath（G,u,v,&has），判断该图中顶点u到顶点v是否连通，如果连通，has为1，否则has为0，在调用该算法之前has置初值为0。对应的算法如下：int visitedMAXV=0; /全局变量void FindaPath（ALGraph *G,int u,int v,bool &has）/has表示uv是否连通，初始时has为0 int w; ArcNode *p; visitedu=1; p=G-adjlistu.firstarc; /p指向u的第一条边 w=p-adjvex; /w为u的邻接顶点 if （w=v） /从u到v找到一条路径，说

21、经u到v是连通的 has=1; return; else if （visitedw=0） /若顶点未标记访问，则递归访问之 FindaPath（G,w,v,has）; /从顶点w出发继续查找 p=p-nextarc /找u的下一个邻接顶点4有一个线性表（a1,a2,an），采用带头节点的单链表L存储，设计一个就地算法将其所有元素逆置。所谓就地算法是指算法的空间复杂度为O（1）。void Reverse1（LinkList *&L） LinkList *p=L-next,*q; /p指向开始节点 L- q=p-next=L- /将*p节点插入到新建链表的前面 L-next=p;5假设二叉树采用二

22、叉链存储结构，设计一个算法把一棵含有n个节点的二叉树b复制到另一棵二叉树t中。void Copy（BTNode *b,BTNode *&t） if （b=NULL） t=NULL; t=（BTNode *）malloc（sizeof（BTNode）; t-data=b-data; /复制一个根节点*t Copy（b-lchild,t-lchild）; /递归复制左子树rchild,t-rchild）； /递归复制右子树6. 假设一个不带权的有向图G采用邻接表存储，设计一个算法判断图G中是否存在顶点i到顶点j的边，若存在这样的边返回1，否则返回0。int HasArc（AGraph *G,int

23、 i,int j） /判断图G中是否存在边 ArcNode *p;adjlisti.firstarc;=NULL & p-adjvex!=j）nextarc; if （p=NULL） return 0; return 1;7. 设ha=（a1,a2,an）和hb=（b1,b2, ,bm） 是两个带头结点的循环单链表，编写将这两个表合并为带头结点的循环单链表hc的算法。答案：void Merge（LinkList *ha, LinkList *hb, LinkList *&hc） LinkList *p=ha- hc=ha; while （p-next!=ha） /找到ha的最后一个节点*p p

24、=p-next=hb- /将ha的最后一个节点的next指向hb的第一个数据节点=hb） p=p- /找到hb的最后一个节点*pnext=hc; /构成循环单链表 free（hb）； /释放hb单链表的头节点8. 有两个串s1和s2，设计一个算法求一个这样的串，该串中的字符是s1和s2中公共字符（不是子串关系）。SqString CommChar（SqString s1,SqString s2） SqString s3; int i,j,k=0; for （i=0;is1.length;i+） for （j=0;js2.length;j+） if （s2.dataj=s1.datai） break; if （j /判断左子树 if （!b1 | predt=bt-key） /