《数据结构与算法作业》由会员分享，可在线阅读，更多相关《数据结构与算法作业（29页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法数据结构与算法作业作业1)填空题：序号填空题：序号 1-80【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多一对多 关系，图形结构中元素之间存在 多对多多对多 关系。【2，1，2】为了最快地存取数据元素，物理结构宜采用 顺序存储顺序存储 结构。【3，1，2】数据结构的三要素是 逻辑结构逻辑结构， 物理结构物理结构 ， 操作操作 。【4，1，2】数据的逻辑结构可形式地用一个二元组 B(K，R)来表示，其中 K 是 数据元数据元 素的有限集合素的有限集合_，R 是 K K 上关系的有限集上关系的有限集_。【5，1，2】存储结构可根据数据元素在机器中的位置是
2、否一定连续分为 顺序存储结构顺序存储结构 _， 链式存储结构链式存储结构_。【6，1，4】度量算法效率可通过 时间复杂度时间复杂度_来进行。【7，1，4】算法的五个重要特性是确定性、 可行性可行性 、 有穷性有穷性 、输入和输 出。【8，1，4】设 n 为正整数，则下面程序段的时间复杂度是 O(n)_。 i=1；k=0； while(inext=LL-next=L 或或 L-prior=LL-prior=L 。【16，2，3】带头结点的单链表 Head 为空的条件是_ Head-next=NULL _。【17，2，3】非空单循环链表 L 中*p 是尾结点的条件是_p-next=L _。【18，
3、2，3】在一个单链表中 p 所指结点(p 所指不是最后结点)之后插入一个由指针 s 所指 结点，应执行 s-next=_ p-next _;和 p-next=_ s s_的操作。【19，2，3】在一个单链表中的指针 p 所指结点之前插入一个由指针 s 所指结点，可执行 以下操作序列： s-next= p-next；_; p-next=s; t=p-data; p-data=_ s-data;_; s-data=t;【20，2，3】在一个单链表中删除 p 所指结点时，应执行以下操作：q= p-next;p-data= p-next-data;p-next= p-next-next _ ;free
4、(q);【21，2，3】在单链表中，删除指针 P 所指结点的后继结点的语句是 P-next = P-next- next;_。【22，2，3】带头结点的单循环链表 Head 的判空条件是_ Head-next = Head;_； 不 带头结点的单循环链表的判空条件是_ Head = NULL; _。【23，2，3】删除带头结点的单循环链表 Head 的第一个结点的操作是_ Head-next = Head-next-next; _；删除不带头结点的单循环链表的第一个结点的操作是_ Head = Head -next;_。【24，2，3】已知 L 是带表头结点的非空单链表, 且 P 结点既然不首
5、元结点,也不是尾元结 点,试从下列提供的答案中选择合适的语句序列。 a. 删除 P 结点的直接前驱结点的语句序列是_10 12 8 11 4 14 _。 b. 删除结点 P 的语句序列是_10 12 7 3 14_。 c. 删除尾元结点的语句序列是_9 11 3 14_。 (1) P = P-next; (2) P-next = P; (3) P-next = P-next -next; (4) P = P-next -next; (5) while (P != NULL) P = P-next; (6) while (Q-next != NULL)P = Q; Q = Q-next; (7)
6、 while (P-next != Q) P = P-next; (8) while (P-next-next != Q) P = P-next; (9) while (P-next-next != NULL) P = P-next; (10) Q = P; (11) Q = P-next; (12) P = L; (13) L = L-next; (14) free (Q);【25，3，1】栈操作的原则是 先进后出先进后出/ /后进先出后进先出 。【26，3，1】对一个栈，给定输入的顺序是 A、B、C，则全部不可能的输出序列有 不可不可 能得到的输出序列有能得到的输出序列有 CAB 。【27
7、，3，1】数据 A、B、C、D 依次进栈后，再从栈中取一数据，则它是 D。则本栈得 到 DCBA 的输出序列，其理由是 根据后进先出的原则，首先得到根据后进先出的原则，首先得到 D，在栈内的数由底到，在栈内的数由底到 顶依次是顶依次是 A、B、C，而出栈的次序刚好相反，即，而出栈的次序刚好相反，即 DCBA。 。【28，3，1】.在栈顶指针为 HS 的链栈中，判定栈空的条件是 head-next=NULL 。【29，3，1】将递归算法改写成等价的非递归算法，通常应该设置 堆栈堆栈 的数据结构【30，3，2】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。 （每空 2 分）void c
8、onversion10_16() InitStack(scanf(“%d”,while(N) _Push(s, N%16)_ _ ;N = N/16;while(!StackEmpty(s) _Pop(s, e)_ ;if(e=j）对应 S 中的下标是 i*(i+1)/2i*(i+1)/2 + + j+1j+1 ；一维数组 S 的大小 M 至少为 (n+1)*(n+1)(n+1)*(n+1) 。【52，6，1】 已知一棵树边的集合是,。那么根结点是 e e ，结点 b 的双亲是 d d ，结点 a 的子孙有 bcdjbcdj ，树的深度是 4 4 ，树的度是 3 3 ，结点 g 在树的第 3
9、3 层。【53，6，2】通常使用 二叉链表二叉链表 来表示二叉树结构。【54，6，2】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本 的目的是 .树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题 。【55，6，2】在图 1 至图 5 中, _1,2,3,4,5_是树，_1,2,3,4_是 二叉树，_1,2,3_是完全二叉树，_1,3_是满二叉树。图 1 图 2 图 3 图 4 图 5【56，6，3】在图 4 中，结点 H 在这棵树的前序、中序和后序遍历次序中分别是_6_、 第_5_和第_3_个结点。
10、【57，6，2】满三叉树的第 i 层的结点个数为 3 3i-1i-1 ，深度为 h 时该树中共有 3 3h h-1-1 结点。【58，6，2】在图 4 中，A 是_根根_结点，D 是_叶子叶子_结点，B 是 E 的_父亲父亲 _，B 是 G 的_祖先祖先_，D 是 E 的_兄弟兄弟_。这棵树的度是_6_，深度 是_4_。【59，6，2】程序填空：下列算法是求以二叉链表存储的二叉树中的最小值，设数据域的 类型为 int。 void minnode(BiTree T, int *min) if(T!=NULL)if( *minT-data*minT-data ) *min = T-data;min
11、node(T-lchild,min);minnode(T-rchild,min)minnode(T-rchild,min) ; 【60，6，2】已知一棵完全二叉树有 56 个叶子结点，从上到下、从左到右对它的结点进行 编号，根结点为 1 号。则该完全二叉树总共结点有_111_个；有_7_层；第 91 号结点的双亲结点是_45_号；第 63 号结点的左孩子结点是_号。【61，6，2】下列表示的图中，共有_5_个是树；有_3_个是二叉树；有_2_个是完全二叉树。【62，6，3】下列二叉树的中序遍历序列是_DBNGOAEC_;后序遍历序列是_DNIGBECA_。【63，6，3】一棵二叉树的中序遍历序
12、列是 DBNGOAEC,后序遍历序列是 DNOGBECA，则其先序遍历的序列中的第一个元素是_ A _，第五个元素是_N _，最后一个元素是_E_【64，6，3】下列二叉树的先序遍历序列的第 5 个结点是_N_；第 8 个结点是 _E_；后序遍历序列的第 2 个结点是_N_；第 6 个结点是_E_。【65，6，3】如果某二叉树的后序遍历序列是 ABCDEFGHI，中序遍历序列是 ACBIDFEHG， 则其先序遍历序列的第一个字母是 I I ，最后一个字母是 G G 。【66，6，3】程序填空：设算法 DFS(Mgraph *G, int i)是无向图 G 从 i 顶点开始的深度优先 遍历算法。
13、下列算法是判断无向图 G 是否是连通的。 int isconnect(Mgraph *G) int i,k=0;for(i=0; ivexnum; i+)visitedi = 0;for(i=0; ivexnum; i+)if(!visitedi) k+k+ ；DFS(G, i); if(k=1) returnreturn 1 1 ；else return 0; 【67，7，2】图有 邻接矩阵邻接矩阵 和 邻接表邻接表 等存储结构。【68，7，2】设无权图 G 的邻接矩阵为 A，若（vi,vj）属于图 G 的边集合，则对应元素 Ai j等于 1 1 ，设无向图 G 的邻接矩阵为 A，若 Aij等于 0，则 Aji等于 0 0 。【69，7，2】若一个图用邻接矩阵表示，则计算第 i 个结点的入度的方法是 求矩阵第求矩阵第 i 列非零元素之和列非零元素之和 。【70，7，2】若一个图用邻接矩阵表示，则删除从第 i 个顶点出发的所有边的方法是 矩阵第矩阵第 i 行全部置为零行全部置为零 。【71，7，4】n 个顶点的连通图至少有 n1 条边。【72，7，4】设一个图 G=V,A,V=a,b,c,d,e,f,A=,。那么顶点 e 的入度是 2 2 ；出度是 1 1 ；通过顶点 f 的简单回路有
