《数据结构》课程复习资料
一、填空题：
1.设需要对5个不同的记录关键字进行排序，则至少需要比较 4 次，至多需要比较 10 次。 2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较 n 次。
3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有 1个，比较两次查找成功有结点数有2个。
4.数据结构从逻辑上划分为三种基本类型：线性结构、树型结构和 图型结构。
5.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有 n(n-1)条边。
6.向一棵B_树插入元素的过程中，若最终引起树根结点的，则新树比原树的高度增加1。
7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为O(log2n) ，整个堆排序过程的时间复杂度为O(nlog2n) 。
8.在快速排序、堆排序、归并排序中，归并排序是稳定的。 9.在有n个叶子结点的哈夫曼树中，总结点数是n-1 。
10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定左右子树空。
11.已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［5，6］对应的地址是1225 。 12.在有n个结点的无向图中，其边数最多为n(n-1)/2。
13.取出广义表A=(x,(a,b,c,d))中原子x的函数是head(A)。 14.对矩阵采用压缩存储是为了节省空间。
15.带头结点的双循环链表L为空表的条件是L->next=L->prior 或 L->next=L。
16.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是1044。
17.对于顺序存储的栈，因为栈的空间是有限的，在进行入栈（插入）运算时，可能发生栈的上溢，在进行出栈（删除）运算时，可能发生栈的下溢。
18.在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。 19.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。 20.折半查找的存储结构仅限于顺序存储结构，且是有序的。
21.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为O(n),在表尾插入元素的时间复杂度为O(1)。
22.在稀疏距阵所对应的三元组线形表中，每个三元组元素按行号为主序，列号为辅序的次序排列。 23.中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为3 x 2.4 5 ／6 －*＋。 24.在一棵高度为h的3叉树中，最多含有(3 h-1)/2结点。 25.分析下面算法（程序段），给出最大语句频度n3，该算法的时间复杂度是 O(n3)。
for (i=0;i 27.一个图的邻接矩阵表示法是唯一的，而邻接表表示法是不唯一的。 28.在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作： q=head; while (q->next!=p) q=q->next; s= new Node; s->data=e; q->next= s ; //填空 s->next= p ; //填空 29.在一个单链表中删除p所指结点的后继结点时，应执行以下操作： 专业整理 知识分享 完美WORD格式 q= p->next; p->next=q->next; //填空 delete q ; //填空 30.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。 31.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是200 +（6 * 20 + 12）= 326。 32.二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是1000 + ((18-10) * 6 + (9 - 5)) * 4 = 1208。 33.求下列广义表操作的结果： (1) GetTail[GetHead[((a,b),(c,d))]]; (b) (2) GetTail[GetHead[GetTail[((a,b),(c,d))]]] (d) 34.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是求矩阵第i列非零元素之和。 35.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是将矩阵第i行全部置为零。 36.在利用快速排序方法对一组记录（，38，96，23，15，72，60，45，83）进行快速排序时，递归调 用而使用的栈所能达到的最大深度为2，共需递归调用的次数为4，其中第二次递归调用是对（23，38，15）组记录进行快速排序。 37.在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下排序最快考虑，则应选取快速排序方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取堆排序方法。 38.称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和 f(n) 的数量级相同。 39.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。 40.假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为 10。 41.对于栈只能在栈顶插入和删除元素。 42.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为 3 。 43.数据结构一般包括三个方面内容：数据的 逻辑结构，数据的存储结构及数据的运算。 44.在包含n个结点的顺序表上做等概率插入运算，平均要移动n/2个结点。 45.队列的特性是先进先出。 46.已知二叉树中叶子数为30，仅有一个孩子的结点数为20，则总结点数为79。 47.中序遍历二叉排序树中的结点可以得到一个递增的关键字序列（选填“先序”、“中序”或“后序”）。 48.n个节点的连通图至少有n-1条边。 49.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑，应最好选择 快速排序排序。 50.带有一个头结点的单链表head为空的条件是（假设指针域的名称为next）head->next==NULL。 51.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为10,13,27,76,65,97,38。 52.在拓扑排序中，拓扑序列的第一个顶点必定是 入度为零 的顶点。 53.数据的逻辑结构分为两大类，它们是线性结构和 非线性结构。 .在单链表中（假设结点指针域名称为next），删除指针P所指结点的后继结点的语句是p->next=p->next->next。 55.已知循环队列用数组data[n]存储元素值，用front,rear分别作为头尾指针，则当前元素个数为(rear-front+n)%n。 56.若n为主串长，m 为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数（n-m+1）×m 。 57.广义表((a),((b),j,(((d)))))的表尾是(((b),j,(((d)))))。 58.已知二叉树有61个叶子节点，且仅有一个孩子的节点数为45，则总节点数为 166 。 专业整理 知识分享 完美WORD格式 59.解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个 队列 结构。 二、单项选择题： 1.队列的特点是 [ B ] A.先进后出 B.先进先出 C.任意位置进出 D.前面都不正确 2.有n 个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。[ B ] A.n B.d C.r D.n - d 3.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序 [ B ] A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同 4.设有198 个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为 [ C ] A.12 B.13 C.14 D.15 5.下面关于广义表的叙述中，不正确的是 [ B ] A.广义表可以是一个多层次的结构 B.广义表至少有一个元素 C.广义表可以被其他广义表所共享 D.广义表可以是一个递归表 6.设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是 [ B ] k+1k A.f>=c B.c>f C.f=2-a D.c>s-1 7.从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为 [ D ] A.head(tail(L)) B.head(head(tail(L))) C.tail(head(tail(L))) D.head(tail(head(tail(L)))) 8.下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是 [ A ] A.顺序结构 B.链接结构 C.索引结构 D.Hash结构 9.在数据结构中，数据元素可由 [ C ] A.实体 B.域 C.数据项 D.字段 10.对于有n个顶点的有向图，由弗洛伊德（FloyD算法求每一对顶之间的最短路径的时间复杂度是[ D ] 3 A.O(1) B.O(n) C.O(n) D.O(n) 11.对n个记录的文件进行快速排序，所需要的辅助存储空间为 [ B ] 2 A.O（1） B.O（log2n） C.O（n） D.O（n） 12.哈夫曼树中一定不存在 [ B ] A.度为0的结点 B.度为1的结点 C.度为2的结点 D.带权的结点 13.下述哪一条是顺序存储方式的优点？ [ A ] A.存储密度大 B.插入和删除运算方便 C.获取符合某种条件的元素方便 D.查找运算速度快 14.有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10 进制表示，m>3） [ D ] A.658 B.8 C.633 D.653 15.下列关于二叉树遍历的叙述中，正确的是 [ A ] A.若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B.若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C.若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 16.第K层二叉树的结点总数最多为 [ A ] kk+1k-1A.2-1 B.2 C.2K-1 D.2 17.线性表进行二分法查找，其前提条件是 [ C ] A.线性表以链接方式存储，并且按关键码值排好序 专业整理 知识分享 完美WORD格式 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C.线性表以顺序方式存储，并且按关键码值排好序 D.线性表以链接方式存储，并且按关键码值的检索频率排好序 18.n 个记录进行堆排序，所需要的辅助存储空间为 [ C ] 2 A.O(1og2n) B.O(n) C.O(1) D.O(n) 19.线性表（7，34，77，25，，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（ ）个。 [ D ] A.1 B.2 C.3 D.4 20.下列关于数据结构的叙述中，正确的是 [ D ] A.数组是不同类型值的集合 B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构 D.用一维数组存储一棵完全二叉树是有效的存储方法 21.以下数据结构中哪一个是线性结构？ [ B ] A.有向图 B.队列 C.线索二叉树 D.B树 22.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（ ）语句序列。 [ D ] A.p=q; p->next=q; B.p->next=q; q->next=p; C.p->next=q->next; p=q; D.q->next=p->next; p->next=q; 23.（ ）不是队列的基本运算。 [ A ] A.在队列第i个元素之后插入一个元素 B.从队头删除一个元素 C.判断一个队列是否为空 D.读取队头元素的值 24.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为 [ C ] A.i B.n=i C.n-i+1 D.不确定 25.栈的特点是（ B ），队列的特点是（A ）。 A.先进先出 B.先进后出 26.设有两个串p和q，求q在p中首次出现的位置的运算称作 [ B ] A.连接 B.模式匹配 C.求子串 D.求串长 27.二维数组A中，每个元素A[i][j]的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为 [ B ] A.SA+141 B.SA+180 C.SA+222 D.SA+225 28.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 [ D ] A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca 29.在一非空二叉树的中序遍历序列中，根结点的右边 [ A ] A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 30.具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 [ A ] A.5 B.6 C.7 D.8 31.二分查找和二叉排序树的时间性能 [ B ] A.相同 B.不相同 32.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 [ B ] A.O（n2） B.O(nlog2n) C.O(n) D.O(log2n) 33.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 [ A ] A.插入排序 B.选择排序 C.快速排序 D.归并排序 34.下述几种排序方法中，要求内存量最大的是 [ D ] A.插入排序 B.选择排序 C.快速排序 D.归并排序 专业整理 知识分享 完美WORD格式 35.设有两个串p和q，求q在p中首次出现的位置的运算称作 [ B ] A.连接 B.模式匹配 C.求子串 D.求串长 36.二维数组A中，每个元素A[i][j]的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA 开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为 [ B ] A.SA+141 B.SA+180 C.SA+222 D.SA+225 37.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 [ D ] A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca 38.在一非空二叉树的中序遍历序列中，根结点的右边 [ A ] A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 39.具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 [ A ] A.5 B.6 C.7 D.8 40.二分查找和二叉排序树的时间性能 [ B ] A.相同 B.不相同 C.可能相同 D.不确定 41.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 [ B ] A.O（n2） B.O(nlog2n) C.O(n) D.O(log2n) 42.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 [ A ] A.插入排序 B.选择排序 C.快速排序 D.归并排序 43.下面的序列中（ ）是大顶堆。 [ D ] A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2 C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,1 44.对一个算法的评价，不包括如下（ ）方面的内容。 [ B ] A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 45.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行 [ A ] A.p->next=HL->next; HL->next=p B.p->next=HL; HL=p C.p->next=HL; p=HL D.HL=p; p->next=HL 46.对线性表，在下列哪种情况下应当采用链表表示？ [ B ] A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 47.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 [ C ] A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 48.每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是 [ B ] A.冒泡排序 B.简单选择排序 C.希尔排序 D.直接插入排序 49.采用开放定址法处理散列表的冲突时，其平均查找长度 [ B ] A.低于链接法处理冲突 B.高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 50.若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 [ D ] A.值 B.函数 C.指针 D.引用 51.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的 [ A ] A.行号 B.列号 C.元素值 D.非零元素个数 52.快速排序在最坏情况下的时间复杂度为 [ D ] 2 A.O(log2n) B.O(nlog2n) C.O(n) D.O(n) 53.从二叉搜索树中查找一个元素时，其时间复杂度大致为 [ C ] 2 A.O(n) B.O(1) C.O(log2n) D.O(n) .设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的 专业整理 知识分享 完美WORD格式 时间复杂度为 [ D ] 2 A.O(log2n) B.O(1) C.O(n) D.O(n) 55.设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0= [ B ] A.Nl+N2+……+Nm B.l+N2+2N3+3N4+……+(m-1)Nm C.N2+2N3+3N4+……+(m-1)Nm D.2Nl+3N2+……+(m+1)Nm 56.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为 [ C ] A.SA+141 B.SA+144 C.SA+222 D.SA+225 57.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为 [ B ] A.uwvts B.vwuts C.wuvts D.wutsv 58.深度为5的二叉树至多有（ ）个结点。 [ C ] A.16 B.32 C.31 D.10 59.在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 [ C ] A.1/2 B.1 C.2 D.4 60.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 [ C ] A.n B.n/2 C.(n+1)/2 D.(n-1)/2 61.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 [ C ] 2 A.O（n） B.O(nlog2n) C.O(n) D.O(log2n) 62.下述几种排序方法中，要求内存量最大的是 [ D ] A.插入排序 B.选择排序 C.快速排序 D.归并排序 63.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 [ C ] A.希尔排序 B.起泡排序 C.插入排序 D.选择排序 .对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以 9。 [ C ] A.20 B.18 C.25 D.22 65.在有向图中每个顶点的度等于该顶点的 [ C ] A.入度 B.出度 C.入度与出度之和 D.入度与出度之差 66.在基于排序码比较的排序算法中，（ ）算法的最坏情况下的时间复杂度不高于O(n10g2n)。 [ C ] A.起泡排序 B.希尔排序 C.归并排序 D.快速排序 67.当α的值较小时，散列存储通常比其他存储方式具有（ ）的查找速度。 [ B ] A.较慢 B.较快 C.相同 D.不清楚 68.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（ ）个表项。 [ A ] (设搜索成功的平均搜索长度为Snl＝{1+l／(1一α)}／2，其中α为装填因子) A.400 B.526 C.624 D.676 69.堆是一个键值序列{k1,k2,…..kn},对I=1,2,….|_n/2_|,满足 [ C ] A.ki≤k2i≤k2i+1 B.ki 70.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上 [ B ] A.操作的有限集合 B.映象的有限集合 C.类型的有限集合 D.关系的有限集合 71.下列图示的顺序存储结构表示的二叉树是 [ A ] 专业整理 知识分享 完美WORD格式 72.由同一关键字集合构造的各棵二叉排序树 [ B ] A.其形态不一定相同，但平均查找长度相同 B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 73.ISAM文件和VSAM文件的区别之一是 [ C ] A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 74.下列描述中正确的是 [ D ] A.线性表的逻辑顺序与存储顺序总是一致的 B.每种数据结构都具备三个基本运算：插入、删除和查找 C.数据结构实质上包括逻辑结构和存储结构两方面的内容 D.选择合适的数据结构是解决应用问题的关键步骤 75.下面程序段的时间复杂度是 [ B ] I=s=0 While(s 76.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快。 [ A ] A.起泡排序 B.快速排序 C.堆排序 D.直接选择排序 77.算法分析的目的是 [ B ] A.辨别数据结构的合理性 B.评价算法的效率 C.研究算法中输入与输出的关系 D.鉴别算法的可读性 78.在线性表的下列运算中，不改变数据元素之间结构关系的运算是 [ C ] A.插入 B.删除 C.定位 D.排序 79.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为 [ D ] A.3，2，6，1，4，5 B.5，6，4，2，3，1 C.1，2，5，3，4，6 D.3，4，2，1，6，5 80.设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为 [ A ] 专业整理 知识分享 完美WORD格式 A.15 B.16 C.17 D.18 81.一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是 [ B ] A.108 B.112 C.116 D.120 82.从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（ ）个结点。 [ C ] A.n B.n/2 C.(n+1)/2 D.(n-1)/2 83.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 [ D ] A.不一定相同 B.互为逆序 C.都不相同 D.都相同 84.高度为5的二叉树至多有结点数为 [ A ] A.63 B.32 C.24 D. 85.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为 [ B ] A.图中每个顶点的出度 B.图中每个顶点的入度 C.图中弧的条数 D.图中连通分量的数目 86.图的邻接矩阵表示法一般不太适用于表示 [ A ] A.无向图 B.有向图 C.稠密图 D.稀疏图 87.循环队列是空队列的条件是 [ B ] A.Q->rear==Q->front B.(Q->rear+1)%maxsize==Q->front C.Q->rear==0 D.Q->front==0 88.设有一广义表E=（a,b,(c,d)），其长度为 [ A.2 B.3 C.4 D.5 .某二叉树的前序遍历序列为ABDEFC，中序遍历序列为DBEFAC，则后序遍历序列为 [ D ] A.DFEBCA B.DBECFA C.BDAECF D.DBEFCA 90.下列（ ）不是利用查找表中数据元素的关系进行查找的方法。 [ C ] A.有序表的查找 B.二叉排序树的查找 C.平衡二叉树 D.散列查找 91.下述几种排序方法中，要求内存量最大的是 [ B ] A.插入排序 B.快速排序 C.归并排序 D.选择排序 92.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 [ B ] A.1/2 B.1 C.2 D.4 93.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行 [ A ] A.p->next=HL->next; HL->next=p B.p->next=HL; HL=p C.p->next=HL; p=HL D.HL=p; p->next=HL 94.对线性表，在下列哪种情况下应当采用链表表示？ [ B ] A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 95.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 [ C ] A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 96.每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是 [ B ] A.冒泡排序 B.简单选择排序 C.希尔排序 D.直接插入排序97.采用开放定址法处理散列表的冲突时，其平均查找长度 [ B ] A.低于链接法处理冲突 B.高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 98.若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 [ D ] A.值 B.函数 C.指针 D.引用 99.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的 [ A ] A.行号 B.列号 C.元素值 D.非零元素个数 专业整理 知识分享 A ] 完美WORD格式 100.快速排序在最坏情况下的时间复杂度为 [ D ] 2 A.O(log2n) B.O(nlog2n) C.O(n) D.O(n) 101.从二叉搜索树中查找一个元素时，其时间复杂度大致为 [ C ] 2 A.O(n) B.O(1) C.O(log2n) D.O(n) 102.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为 [ D ] 2 A.O(log2n) B.O(1) C.O(n) D.O(n) 103.设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0= [ B ] A.Nl+N2+……+Nm B.l+N2+2N3+3N4+……+(m-1)Nm C.N2+2N3+3N4+……+(m-1)Nm D.2Nl+3N2+……+(m+1)Nm 104.设有序表中有1000个元素，则用二分查找查找元素X 最多需要比较（ ）次。 [ B ] A.25 B.10 C.7 D.1 105.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为 [ B ] A.abedfc B.acfebd C.aebdfc D.aedfcb 106.拓扑排序运算只能用于 [ C ] A.带权有向图 B.连通无向图 C.有向无环图 D.无向图 107.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 [ B ] 2 A.O(1) B.O(n) C.O(n) D.O(nlogn) 三、 计算与算法应用题： 1.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 2.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。 先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A 3.画出下列树对应的二叉树，并写出其先根遍历序列： A B C D F E G 4.将关键字序列为{，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。 专业整理 知识分享 完美WORD格式 5.试列出如下图中全部可能的拓扑排序序列。 123456 6.设某通信系统使用A，B ，C，D，E，F，G，H八个字符，他们出现的概率w={5，29，7，8，14，23，3，11}，试构造对应的哈夫曼树（请按左子树根结点的权小于右子树树根结点的权的次序构造）。 7.给定表（119，14，22，1，66，21，83，27，56，13，10）,请按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均长度。 8.已知一个有向图的顶点集V和边集G分别为： V={a,b,c,d,e,f,g,h} E={ 假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。 9.设散列表的长度为13，散列函数为H（h）= k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。 0 1 2 3 4 5 6 7 8 9 10 11 12 10.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。 (1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快速排序，写出排序过程。 11.如图所示二叉树，回答下列问题。 12.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种 旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。 13.已知一组记录的排序码为（ 46 ， 79 ， 56 ， 38 ， 40 ， 80, 95 ， 24 ），写出对其进行快 速排序的每一次划分结果。 14.一个线性表为 B= （ 12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36 ），设散列表为 HT[0..12] ，散列函数为 H （ key ） = key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 15.已知一棵二叉树的前序遍历的结果序列是 ABECDFGHIJ ，中序遍历的结果是 EBCDAFHIGJ ，试写出这 专业整理 知识分享 完美WORD格式 棵二叉树的后序遍历结果。 16.假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用H(K)=K％9作为散列函数，若分别 采用线性探查法和链接法处理冲突，则计算对应的平均查找长度。 17.已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列 {100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。 18.试画出下面带权无向图的一棵最小生成树。 2 a 9 b 6 7 d 3 9 7 c 8 4 e f 5 19.已知关键字序列为：{03, 87, 12, 61, 98, 70, 61*，97, 27, 53, 42，56，77，希尔(Shell)排序法对该序列作非递减排序.按5，3，1 分组，写出下列标明的趟的结果。 初始 03 ， 87， 12 ， 61， 98 ，70， 97， 27， 53， 42， 56， 77 第一趟 第二趟 每三趟 1.int AA(LNode *HL , ElemType x) { int n=0; LNode *p=HL; while (p!=NULL) { if (p->data= =x) n++; p=p->next; } return n; } 对于结点类型为LNode的单链表，以上算法的功能为： 2.int AA(LNode *HL , ElemType x) { int n=0; LNode *p=HL; while (p!=NULL) 专业整理 知识分享 请采用 } 四、阅读下列算法，分析它的作用： 完美WORD格式 { if (p->data= =x) n++; p=p->next; } return n; } 对于结点类型为LNode的单链表，以上算法的功能为： 3.假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。 # include < iostream.h> # include < stdlib.h > const int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” void main 【 】 { stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x; } while (!stackempty (a)) cout < 4.读下述算法，说明本算法完成什么功能。 template unknown (BinTreeNode temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } } 专业整理 知识分享 完美WORD格式 该算法的功能是：______________。 5.阅读下列算法，说明该算法的作用。 void Sqstack::push(ElemType x ) // 类定义 { if ( top==MAX-1 ) const int MAX=20; cout<<”\\n 满！”； typedef char ElemType ; else { top++; class Sqstack elem[top]=x; { private: } ElemType elem [MAX]; } // push int top ; public: Sqstack(){top=0}; ElemType pop(); void push(ElemType x); //…….; } ; 6.有如下图所示单链表，经过output（ ）算法处理后，单链表发生了什么变化？画出处理后的单链表图示。 void Link :output() struct Snode //结点结{ p=Head->next; 构 while( p !=NULL) { char data; { cout<<”\\n data=”< } // inordern 8.void AD(Lnode* & HL) { Insert(HL,30); Insert(HL,50); Delete(HL,26); Delete(HL,55); } 专业整理 知识分享 完美WORD格式 假定调用该算法时以HL为表头指针的单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：____________。 9.void AI(adjmatrrix GA,int i,int n) { cout< AI(GA,j,n); } 该算法的功能为：_______________。 10.阅读下列算法，说明该算法的作用。 // 类定义 ElemTtype Sqstack::pop【 】 const int MAX=20; { ElemType x; typedef char ElemType ; if ( top==0 ) x=-999; class Sqstack else { x = elem[top]; { private: top--; ElemType elem [MAX]; } int top ; return x; public: } // pop Sqstack(){top=0}; ElemType pop(); void push(ElemType x); //…….; } ; 11.有如下图所示单链表，经过reverse 算法处理后，单链表发生了什么变化？画出处理后的单链表图示。 void Link ::reverse() struct Snode //结点结{ Snode *p, *q ; 构 p= Head ->next; { char data; Head ->next=NULL; Snode *next ; while( p !=NULL) { q=p->next ; } ; p->next= Head ->next; class Link //链表类 Head >next=p; { private: p=q; Snode *Head; } public: } // reverse Link (){Head =NULL}; Head d a c b void creat(); e ^ void reverse (); void output(); //…….; 输出是什么？12.下列函数是二叉排序树的什么算法？如果K值为5，针对下图所示二叉树，运行下列算法，比较几次得到结果？ Void Bstree::Search( KeyType K) 专业整理 知识分享 完美WORD格式 { int flag = 0; BstNode *q=root, *p = NULL; while((q!=NULL)&&(flag==0)) { if(q->key==K) flag = 1; else if ( K else { p = q; q = q->rch; } } if(flag == 0) cout<<\"\\n 查找失败，无此结点！\\n\"; else cout<<\"\\n 查找成功，找到：\"< { LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL; while ( p->next!=HL ) p=p->next; newptr->next=HL; p->next=newptr; } 对于结点类型为LNode的单链表，以上算法的功能为： 14.void BB(List &L) { int i=0; while (i while (j for (int k=j+1;k 以上算法的功能为： 15.void CC(BTreeNode * & BST ) { ElemType a[6 ]={45，23，78，35，77，25}； 7 4 2 5 8 9 2 9 专业整理 知识分享 完美WORD格式 BST=NULL； for( int i=0,i<6;i++) Insert(BST , a[i]); } 调用该算法后，生成的二叉搜索数的中序序列为： 16.void DD ( ) { ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9); for ( int i=0; i<10; i++) cout< 17.template if (i<0 || i>last+1 || last== MaxSize-1) return 0; else { Last++; for(int j=last;j 四、 算法设计题： 1.编写复制一棵二叉树的非递归算法。 2.假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。 3.试用递归法编写输出从n个数中挑选 k个进行排列所得序列的算法。 4.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。 Head d a c be ^ 5.试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。 6.已知带头结点的单链表是一个递增有序表，试写一算法，删除表中值大于min且小于max的结点（若表中 专业整理 知识分享 完美WORD格式 有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。 Head 26 7 15 9 50 ^ 7.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。 8.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回true，否则返回false。 bool Find（BtreeNode*BST，ElemType&item） 9.设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A 10.已知单链表a和b的元素按值递增有序排列,编写算法归并a和b得到新的单链表c，c的元素按值递减有序。 11.编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 12.编写算法判别T是否为二叉排序树. 13.编写递归算法，在二叉树中求位于先序序列第k个位置的结点的值。 14.已知有向图和图中两个顶点u和v，试编写算法求有向图中从u到v的所有简单路径。 15.写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 16.编写按层次顺序（同一层自左至右）遍历二叉树的算法。 17.设计算法判断一个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。 专业整理 知识分享 完美WORD格式 《数据结构》课程复习参 一、填空题： 1.4，10 2.n 3.1，2 4.线性结构 树型结构 图型结构 5.n(n-1)/2 n(n-1) 6.增加1 7.O(log2n) O(nlog2n) 8.归并 9.n-1 10.左右子树空 11.1225 12.n(n-1)/2 13.head(A) 14.节省空间 15.L->next=L->prior 或 L->next=L 16.1044 17.入栈（插入） 出栈（删除） 18.前驱结点 后继结点 19.中序序列 20.顺序存储结构 有序的 21.O(n) O(1) 22.行号 列号 h 23.3 x 2.4 5 ／6 －*＋ 24.(3 -1)/2 33 25.n O (n) 26.零个字符的串 零 27.邻接矩阵 邻接表 28.s p 29.q->next q 30.两个串的长度相等且对应位置的字符相同 31.200+（6*20+12）= 326 32.1000+((18-10)*6 +(9-5))*4 = 1208 33.(1). (b) (2). (d) 34.求矩阵第i列非零元素之和 35.将矩阵第i行全部置为零 36.2. 2; 4; （23，38，15） 37.堆排序、快速排序、归并排序、归并排序、快速排序、堆排序 38.f(n) 39.O(n) 40.10 41.栈顶 42.3 43.逻辑结构 44.n/2 45.先进先出 46.79 47.中序 48.n-1 49.快速排序 50.head->next==NULL 51.10,13,27,76,65,97,38 52.入度为零 53.非线性结构 .p->next=p->next->next 55.(rear-front+n)%n 56.（n-m+1）×m 57.(((b),j,(((d))))) 58.166 59.队列 二、单项选择题： 1.B 2.B 3.B 4.C 5.B 6.B 7.D 8.A 9.C 10.D 11.B 12.B 13.A 14.D 15.A 16.A 17.C 18.C 19.D 20.D 21.B 22.D 23.A 24.C 25①.B 25②.A 26.B 27.B 28.D 29.A 30.A 31.B 32.B 33.A 34.D 35.B 36.B 37.D 38.A 39.A 40.B 41.B 42.A 43.D 44.B 45.A 46.B 47.C 48.B 49.B 50.D 51.A 52.D 53.C .D 55.B 56.C 57.B 58.C 59.C 60.C 61.C 62.D 63.C .C 65.C 66.C 67.B 68.A 69.C 70.B 71.A 72.B 73.C 74.D 75.B 76.A 77.B 78.C 79.D 80.A 81.B 82.C 83.D 84.A 85.B 86.A 87.B 88.A .D 90.C 91.B 92.B 93.A 94.B 95.C 96.B 97.B 98.D 99.A 100.D 101.C 102.D 103.B 104.B 105.B 106.C 107.B 三、计算与算法应用题： 1.普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 2.在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 3.画出下列树对应的二叉树，并写出其先根遍历序列： 专业整理 知识分享 完美WORD格式 A B 先根遍历序列： A B D E G F C D C E F G 4.将关键字序列为{，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。 29 37 86 71 91 8 31 44 26 29 37 86 71 91 8 31 26 44 29 37 86 8 31 71 91 26 44 8 29 31 37 71 86 91 26 44 8 26 29 31 37 44 71 86 91 5.全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、5123 6. 100 42 48 F 29 B 19 7. 23 D 8 H 11 29 E 14 C 7 G 3 A 5 8 15 专业整理 知识分享 完美WORD格式 平均长度为4。 8.深度优先搜索序列：a，b，f，h，c，d，g，e 广度优先搜索序列：a，b，c，f，d，e，h，g 9.计算机关键码得到的散列地址 关键码 19 14 23 01 68 20 84 27 散列地址 6 1 10 1 3 7 6 1 在散列表中散列结果 0 1 2 3 4 5 6 7 8 9 10 11 12 14 01 68 27 19 20 84 23 10.对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。这里要求10次，而7 - 1 + 2 * ( 3 - 1 ) = 10，这就要求2趟快速排序后，算法结束。所以，列举出来的序列，要求在做partition的时候，正好将序列平分。 (1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7 ....... (2)按自己序列完成 11.答案：(1)djbaechif (2)abdjcefhi (3)jdbeihfca 12.在这个AVL树中删除根结点时有两种方案： 【方案1】在根的左子树中沿右链走到底,用5递补根结点中原来的6,再删除5所在的结点。 【方案2】在根的右子树中沿左链走到底,用7递补根结点中原来的6,再删除7所在的结点。 专业整理 知识分享 完美WORD格式 13. 划分次序 划分结果 第一次 [38 24 40] 46 [56 80 95 79] 第二次 24 [38 40] 46 [56 80 95 79] 第三次 24 38 40 46 [56 80 95 79] 第四次 24 38 40 46 56 [80 95 14. 79] 0 1 2 3 4 5 第五次 24 38 40 46 56 79 [80 6 7 8 9 10 11 95] 12 第六次 24 38 40 46 56 79 80 95 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度： ASL SUCC =14/10= 1.4 15.此二叉树的后序遍历结果是：EDCBIHJGFA 16.13／7 1l／7 17.哈希表及查找各关键字要比较的次数如下图所示： ASL=18(4×1+1×2+1×4+2×5)=2.5 18.参： a 2 d b 6 3 c 4 f e 5 19. 初始 03， 87， 12， 61， 98， 70， 97， 27， 53， 42， 56， 77 专业整理 知识分享 完美WORD格式 第一趟 03， 77， 12， 53， 42， 56， 87， 27， 61， 98， 70， 97 第二趟 03， 27， 12， 53， 42， 56， 87， 70， 61， 98， 77， 97 每三趟 03， 12， 27， 42， 53， 56， 61， 70， 77， 87， 97， 98 四、阅读下列算法，分析它的作用： 1.统计单链表中结点的值等于给定值x的结点数。 2.对数组A中的n个元素进行排序，称为起泡算法。 3.该算法的输入结果是：34 91 30 45 63 78 4.该算法的功能是：交换二叉树的左右子树的递归算法。 5.该算法是顺序栈类的进栈算法。 如果栈满返回“满”；否则X元素进栈。 6.该算法是将链表的数据元素输出算法。 输出结果： a b c d Head a b c d e ^ 7.本算法要求二叉树中叶子结点的总数的算法。 用n值存储叶子结点的个数。 8.（15，30，48，50） 9.从初始点vi出发深度优先搜索遍历由邻接距阵GA所表示的图 10.该算法是顺序栈类的出栈算法。 如果栈空返回-999；否则返回出栈元素的值。 11.该算法是将链表逆置的算法。 链表逆置后，具体如下图： Head e d c b a ^ 12.输出是“ 查找成功，找到：5 ” 比较3次得到结果。 13.向单链表的末尾添加一个元素。 14.删除线性表中所有重复的元素。 专业整理 知识分享 完美WORD格式 25 35 45 77 78 16.1 2 3 4 5 6 7 8 9 10 17.顺序表插入算法 五、算法设计题： 1.将算法实现函数声明为二叉树类的友元函数，可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。 具体算法实现如下： // 文件路径名:exam5\\alg.h template void CopyBitree(BinaryTree if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr if (fromBtPtr->Empty()) { // 空二叉树 toBtPtr = NULL; // 空二叉树 } else { // 非空二叉树 LinkQueue fromRoot = fromBtPtr->GetRoot(); // 取出fromBtPtr的根 toRoot = new BinTreeNode fromQ.OutQueue(fromPtr); // 出队 toQ.OutQueue(toPtr); // 出队 if (fromPtr->leftChild != NULL) { // 左子树非空 toPtr->leftChild = new BinTreeNode // 复制fromPtr左孩子 fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队 } if (fromPtr->rightChild != NULL) { // 右子树非空 toPtr->rightChild = new BinTreeNode // 复制fromPtr左孩子 fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队 } } toBtPtr = new BinaryTree } } 2.从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。 专业整理 知识分享 完美WORD格式 具体算法实现如下： // 文件路径名:exam1\\alg.h ss ElemType> void DisplayHelp(BinTreeNode // 操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1 { if(r != NULL) { // 空树不显式，只显式非空树 DisplayHelp cout << \" \"; // 确保在第level列显示结点 cout << r->data; // 显示结点 DisplayHelp template void Display(const BinaryTree DisplayHelp 3.对于排列的解空间可构造一个虚拟的解空间树，比如n=5，k=3时的解空间树如下图所示，可采用对此树进行先序遍历方式进行遍历，并用递归法进行递归输出从n个数中挑选 k个进行排列所得序列。 具体算法实现如下： // 文件路径名:exam7\\alg.h template void Arrage(ElemType a[],int k,int n, int outlen=0) // 操作结果: 回溯法输出排列序列，a[0..k-1]为k个数的排列序列outlen为当前所求排列 // 序列的长度，其中outlen=k时的排列序列为所求；n为list数组长度 { if (k < 0 || k >= n) return; // 此时无排列 int i; // 临时变量 if (outlen == k + 1) { // 得到一个排列 for (i = 0; i < k; i++) { // 输出一个排列 cout << a[i]; // 输出a[i] } cout << \" \"; // 用空格分隔不同排列 } else { // 对解空间进行前序遍历，a[outlen..n]有多个排列，递归的生成排列 专业整理 知识分享 完美WORD格式 for (i = outlen; i < n; i++) { // 处理a[i] Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] Arrage(a, k, n, outlen + 1); // 对序列长度outlen+1递归 Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] } } } 4.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。 Head c a d be ^ void Link ::swap( NodeType *p) { NodeType *q,*r,*s; q=p->next; if(q!=NULL) { if(p==Head) {Head=Head->next; s=Head->next; Head->next=p; p->next=s; } Else // { r=Head; while(r->next!=p) r=r->next; r->next=q; p->next=q->next; q->next=p; } } } 5.可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。 具体算法实现如下： // 文件路径名:exam4\\alg.h #include \"binary_sort_tree.h\" // 二叉排序树类 template void InOrderHelp(BinTreeNode // 操作结果: 从大到小输出以r为根的二叉排序树中所有的关键字值不小于key的元素值 { if (r != NULL) { // 非空二叉排序树 InOrderHelp(r->leftChild, key); // 遍历左子树 if(r->data < key) cout << r->data << \" \"; // 输出根结点 else return; 专业整理 知识分享 完美WORD格式 InOrderHelp(r->rightChild, key); // 遍历右子树 } } template void InOrder(const BinarySortTree InOrderHelp(t.GetRoot(), key); // 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于key的元素值 } 6. void Link ::Delnode( ) { NodeType *p=Head->next, *q,*r=p; while(p!=NULL&&p->data while( q!=NULL && p->data r->next=q->next; r=p->next; while(r!=q) { delete p; p=r;r=r->next; } delete q; } // delpro 7.二叉树采取顺序结构存储，是按完全二叉树格式存储的。对非完全二叉树要补上“虚结点”。由于不是完全二叉树，在顺序结构存储中对叶子结点的判定是根据其左右子女为0。叶子和双亲结点下标间的关系满足完全二叉树的性质。 int Leaves(int h) //求深度为h以顺序结构存储的二叉树的叶子结点数 hh {int BT[]; int len=2-1, count=0; //BT是二叉树结点值一维数组，容量为2 for (i=1;i<=len;i++) //数组元素从下标1开始存放 if (BT[i]!=0) //假定二叉树结点值是整数，“虚结点”用0填充 if(i*2)>len) count++; //第i个结点没子女，肯定是叶子 else if(BT[2*i]==0 && 2*i+1<=len && BT[2*i+1]==0) count++; //无左右子女的结点是叶子 return (count) } //结束Leaves 8.bool Find（BtreeNode*BST，ElernType＆item） { while（BST！=NULL） { if（item= =BST一>data）{item=BST一>data； return true;} 专业整理 知识分享 完美WORD格式 else if（item＜BST一>data＝BST＝BST一>left; else BST=BST一>right； } return false; } 9. int Compare-List(SqList a, SqList b){ //a,b为顺序表，若a while (i<=a.length-1) && (i<=b.length-1) && (a.elem[i]=b.elem[i]) ++i; switch { case i=a.length && i=b.length : return 0; break; case (i=a.length && i<=b.length-1) ||(i<=a.length-1 && i<=b.length-1 && a.elem[i] 10. void MergeList(LinkList &a, LinkList &b, LinkList &c) { //已知单链表a和b的元素按值递增有序排列 //归并a和b得到新的单链表c，c的元素按值递减有序 c=a; p=a->next; q=b->next; c->next=NULL; while (p && q) if (p->data pn=p->next; p->next=c->next; c->next=p; p=pn; } else { qn=q->next; q->next=c->next; c->next=q; q=qn; } while (p) {pn=p->next; p->next=c->next; c->next=p; p=pn;} while (q) {qn=q->next; q->next=c->next; c->next=q; q=qn;} free(b); }//MergeList 11. Status Del-subtree(Bitree bt){ //删除bt所指二叉树，并释放相应的空间 if (bt) { Del-subtree(bt->lchild); Del-subtree(bt->rchild); free(bt); } return OK; }//Del-subtree Status Search-del(Bitree bt, TelemType x){ //在bt所指的二叉树中，查找所有元素值为x的结点，并删除以它为根的子树 if (bt){ if (bt->data=x) Del-subtree(bt); 专业整理 知识分享 完美WORD格式 else { Search-Del(bt->lchild, x); Search-Del(bt->rchild, x); } } return OK; }//Search-Del 12． TelemType Maxv(Bitree T){ //返回二叉排序树T中所有结点的最大值 for (p=T; p->rchild; p=p->rchild); return p->data; }//Maxv TelemType Minv(Bitree T){ //返回二叉排序树T中所有结点的最小值 for (p=T; p->lchild; p=p->lchild); return p->data; }//Minv Status IsBST(Bitree T){ //判别T是否为二叉排序树 if (!T) return OK; else if ((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild) &&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data ))) return OK else return ERROR; }//IsBST 13. void Get_PreSeq(Bitree T)//求先序序列为k的结点的值 { if(T) { c++; //每访问一个子树的根都会使前序序号计数器加1 if(c==k) { printf(\"Value is %d\\n\exit (1); } else { Get_PreSeq(T->lchild); //在左子树中查找 Get_PreSeq(T->rchild); //在右子树中查找 } }//if }//Get_PreSeq 14. int path[MAXSIZE],visited[MAXSIZE]; int Find_All_Path(ALGraph G,int u,int v,int k)//求有向图G中顶点u到v之间的所有简单 专业整理 知识分享 完美WORD格式 路径,k表示当前路径长度 { path[k]=u; //加入当前路径中 visited[u]=1; if(u==v) //找到了一条简单路径 { printf(\"Found one path!\\n\"); for(i=0;path[i];i++) printf(\"%d\打印输出 } Else for(p=G.vertices[u].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找 } visited[u]=0; path[k]=0; //回溯 }//Find_All_Path 15.先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结 点的值，重复上述过程直到最后一个结点。具体算法： Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素 { p=L->next;q=p->next; //p,q指向相邻两元素 while(p->next) { if(p->data!=q->data) { p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步 } Else { while(q->data==p->data) { s=q; q=q->next; free(s); } p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素 }//else }//while }//Delete_Equal 16. void LayerOrder(Bitree T)//层序遍历二叉树 { 专业整理 知识分享 完美WORD格式 InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 17. int PairBracket( char *SR) {//检查表达式ST中括号是否配对 int i; SeqStack S; //定义一个栈 InitStack (&s); for (i=0; i if (!StackEmpty(S))//栈不为空时，将栈顶元素出栈 Pop(&s); else return 0;//不匹配，返回0 } if EmptyStack(&s) return 1;// 匹配，返回1 else return 0;//不匹配，返回0 } 专业整理 知识分享 因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- xiaozhentang.com 版权所有 湘ICP备2023022495号-4
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务