《2022年自学考试《高级语言程序设计方案》习题 .pdf》由会员分享，可在线阅读，更多相关《2022年自学考试《高级语言程序设计方案》习题 .pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、个人资料整理仅限学习使用2018 年自学考试高级语言程序设计习题第 1 部分引论二、选择1链式存储结构中，每个数据的存储结点里 D 指向邻接存储结点的指针，用以反映数据间的逻辑关系。A只能有1 个 B只能有2 个 C只能有3 个 D可以有多个2有下面的算法段：for (i=0 。 i k+ 。其时间复杂度为 B 。AO(1 BO(n CO(log2nDO(n2 四、应用1给出下面3 个算法段的时间复杂度：1） x+；2） for (j=1 。 j x+ 。3） for (j=1 。 j for (k=1 。 k x+ 。答： ； 。第 2 部分 线性表一、 填空1以顺序存储结构实现的线性表，被
2、称为顺序表。2以链式存储结构实现的线性表，被称为链表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 15 页个人资料整理仅限学习使用3不带表头结点的链表，是指该链表的表头指针直接指向该链表的起始结点。4顺序表Sq = (a1，a2，a3， an* w 。5当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用顺序 存储结构。二、选择1下面，对非空线性表特点的论述， C 是正确的。A所有结点有且只有一个直接前驱B所有结点有且只有一个直接后继C每个结点至多只有一个直接前驱，至多只有
3、一个直接后继D结点间是按照1 对多的邻接关系来维系其逻辑关系的2带表头结点的单链表Lk_h 为空的判定条件是 B 。ALk_h = NULL BLk_h-Next = NULL CLk_h-Next = Lk_h DLk_h != NULL 3往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动 B 个结点。AnBn/2Cn+ 1D(n+1/24在一个单链表中，已知qtr 所指结点是ptr 所指结点的直接前驱。现要在qtr 所指结点和ptr 所指结点之间插入一个rtr 所指的结点，要执行的操作应该是 C 。Artr-Next = ptr-Next 。ptr-Next = rtr 。
4、Bptr-Next = rtr-Next 。Cqtr-Next = rtr 。rtr-Next = ptr 。Dptr-Next = rtr 。rtr-Next = qtr-Next 。5在一个单链表中，若现在要删除ptr 指针所指结点的直接后继结点，则需要执行的操作是 A 。Aptr-Next = ptr-Next-Next 。Bptr = ptr-Next 。 ptr-Next = ptr-Next-Next 。Cptr = ptr-Next-Next 。Dptr-Next= ptr 。6在长度为n 的顺序表中，往其第i 个元素 1in）之前插入一个新的元素时，需要往后移动 B 个元素。A
5、n-iBn-i+1 Cn-i-1 Di7在长度为n 的顺序表中，删除第i 个元素 Next 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 15 页个人资料整理仅限学习使用 tail = tail-Next 。 free (tail 。 free (ptr 。Ctail = tail-Next-Next 。Dptr = tail-Next-Next 。Free (tail 。 tail-Next-Next = ptr-Next 。Free (ptr。 free (ptr 。9在单链表中，如果指针ptr 所指结点不是链表的尾结点，那么在
6、ptr 之后插入由指针 qtr 所指结点的操作应该是 B 。Aqtr-Next = ptr 。B qtr-Next = ptr-Next 。 ptr-Next = qtr 。 ptr-Next = qtr 。Cqtr-Next = ptr-Next 。Dptr-Next = qtr 。 ptr = qtr 。 qtr-Next = ptr 。四、应用1设计一个计算带表头结点的单链表L 的长度 Link p=L-next 。int sum=0。 while (p sum+ 。 p = p-next 。 return (sum 。 2、已知一个带表头结点的无序单链表L。试编写一个算法，功能是从表中
7、找出最大值和最小值。 typedef struct node ListItem element 。struct node next。Node,*link 。viod maxmin(link L int max,min 。 link p=L-next 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 15 页个人资料整理仅限学习使用 if(p max=p-element 。 min=p-element。 p=p-next。 while (p if(maxelement max=p-element 。 if(minp-element min
8、=p-element 。 p=p-next。 printf(max=%d,min=%dn,max,min。 3已知一个带表头结点的无序单链表L，不同结点的Data 域值有可能相同。编写一个算法，功能是计算出Data 域值为 x 的结点的个数。typedef struct node *link 。 typedef struct node ListItem data 。link next 。 Node 。答：int Count (link L, int x n = 0 。 link p=L-next 。 while (p if (p-data = = x n + 。 p= p-next retur
9、n (n 。 第 3 部分 栈与队列一、 填空1限定插入和删除操作只能在一端进行的线性表，被称为是栈。2如果在顺序栈满时仍打算进行进栈操作，就称为发生了“上溢 ”出错。3如果在顺序栈空时仍打算进行出栈操作，就称为发生了“ 下溢 ”出错。4在具有n个数据结点的循环队列中，队满时共有n-1 个数据元素。5如果操作顺序是先让字母A、B、C 进栈，做两次出栈；再让字母D、 E、F 进栈，做一次出栈；最后让字母G 进栈，做三次出栈。最终这个堆栈从栈顶到栈底的余留元素应该是 A 。6队列中，允许进行删除的一端称为队首。二、选择精选学习资料 - - - - - - - - - 名师归纳总结 - - - -
10、- - -第 4 页，共 15 页个人资料整理仅限学习使用1一个栈的元素进栈序列是a、b、 c、d、e，那么下面的 C 不能做为一个出栈序列。Ae、d、 c、b、a Bd、e、c、b、a Cd、c、 e、a、b. Da、b、c、d、e 2判定一个顺序队列Qs%m BCq_front = (Cq_front+1%(m+1CCq_rear = (Cq_rear+1%m DCq_rear = (Cq_rear+1%(m+15在一个循环顺序队列里，队首指针Cq_front 总是指向 A 。A队首元素B队首元素的前一个队位C任意位置D队首元素的后一个队位6若一个栈的进栈序列是1、 2、3、4，那么要求出
11、栈序列为3、 2、 1、4 时，进、出栈操作的顺序应该是 A 。注：所给顺序中，I 表示进栈操作，O 表示出栈操作）AIIIOOOIO BIOIOIOIO CIIOOIOIO DIOIIIOOO 第 4 部分 树一、 填空1树中结点的度，是指结点拥有孩子 的个数。2树中除根结点外，其他结点有且只有一个前驱结点，但可以有零个或多 个 后继结点。3在数据结构中，把nn0）棵互不相交的树的集合称为森林 。4在如图6-21 所示的树中，结点H 的祖先是 A、D、G 。图 6-21 树示例图 6-22 树示例5在树中，一个结点的孩子个数，称为该结点的度 。精选学习资料 - - - - - - - - -
12、 名师归纳总结 - - - - - - -第 5 页，共 15 页个人资料整理仅限学习使用6一棵树的形状如图6-22 所示。它的根结点是A ，叶结点是E、G、 I、J、K、L、N、O、P、Q、R ，这棵树的度是4 ，这棵树的深度是5 ，结点F 的孩子结点是J、K ，结点 G 的父结点是C，结点 M 、H、D、A 是结点 R 的祖先。7结点数为7 的二叉树的高度最矮是 3 ，最高是 7 。8如果一棵满二叉树的深度为6，那么它共有 63 个结点，有32 个叶结点。9由 n 个带权值的叶结点生成的哈夫曼树，最终共有2n-1 个结点。10将一棵完全二叉树按层次进行编号。那么，对编号为i 的结点，如果有
13、左孩子，则左孩子的编号应该是 2i ；如果有右孩子，则右孩子的编号应该是 2i+1 。11若二叉树共有n 个结点，采用二叉链表存储结构。那么在所有存储结点里，一共会有 2n 个指针域，其中有 n+1 个指针域是空的。12深度为5 的二叉树，至多有31 个结点。二、选择 1已知一棵单右支的二叉树，如下左图所示。把它还原成森林，应该是 D 。A B C D2将一棵树Tr 转换成相应的二叉树Bt，那么对Tr 的先序遍历是对Bt 的 A 。A先序遍历B中序遍历C后序遍历D无法确定3将一棵树Tr 转换成相应的二叉树Bt，那么对Tr 的后序遍历是对Bt 的 B 。A先序遍历B中序遍历C后序遍历D无法确定4
14、设森林F 中有 3 棵树，依次有结点n1、n2、n3 个。把该森林转换成对应的二叉树后，该二叉树的右子树上的结点个数是 D 。An1 Bn1+n2 Cn3 Dn2+n3 5设有由三棵树T1、T2、T3 组成的森林，其结点个数分别为n1、n2、n3。与该森林相应的二叉树为Bt。则该二叉树根结点的左子树中应该有结点 A 个。An1-1 Bn1 Cn1+1 Dn1+n2 6一棵有n 个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有B 个结点。An-2 Bn-1 Cn+1 Dn+2 7一棵有n 个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的右子树上共有 A 个结点。A
15、0 BnCn+1 Dn+2 8下列说法中，正确的是 A 。A树的先序遍历序列与其对应的二叉树的先序遍历序列相同B树的先序遍历序列与其对应的二叉树的后序遍历序列相同C树的后序遍历序列与其对应的二叉树的先序遍历序列相同D树的后序遍历序列与其对应的二叉树的后序遍历序列相同9在所给的4 棵二叉树中 ， C 不是完全二叉树。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 15 页个人资料整理仅限学习使用10设有一棵5 个结点的二叉树，其先序遍历序列为：A-B-C-D-E ，中序遍历序列为： B-A-D-C-E ，那么它的后序遍历序列为 B。AA-
16、B-D-E-C BB-D-E-C-A CD-E-C-A-B DA-B-C-D-E 11将一棵有50 个结点的完全二叉树按层编号，那么编号为25的结点是 B 。A无左、右孩子B有左孩子，无右孩子C有右孩子，无左孩子D有左、右孩子12深度为6 的二叉树，最多可以有 A 个结点。A63 B64 C127 D128 13在一棵非空二叉树的中序遍历序列里，根结点的右边 D 结点。A只有左子树上的部分B只有左子树上的所有C只有右子树上的部分D只有右子树上的所有14在任何一棵二叉树的各种遍历序列中，叶结点的相对次序是 A 。A不发生变化B发生变化C不能确定D以上都不对15权值为1、2、6、8 的四个结点，所
17、构造的哈夫曼树的带权路径长度是 D 。A18 B28 C19 D29 16一棵二叉树度2 的结点数为7，度 1的结点数为6。那么它的叶结点数是 C 。A6 B7 C8 D9 17在一棵二叉树中，第5 层上的结点数最多是C 个。A8 B15C16 D32 四、应用1将图 6-26 所示的二叉树转换成相应的森林。图 6-26 二叉树示例图 6-27 树示例答：转换成的森林如下图所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 15 页个人资料整理仅限学习使用2给出如图6-27 所示树的先序遍历序列和后序遍历序列。答：该树的先序遍历序列为
18、：A-B-E-F-K-L-M-C-G-D-H-I-J；该树的后序遍历序列是：E-K-M-L-F-B-G-C-H-I-J-D-A。3将图 6-28 所示的森林转换成对应的二叉树。图 6-28 森林示例图 6-29 树示例答：对应的二叉树如下图所示。4将图 6-29 所示的树转换成相对应的二叉树。答：对应的二叉树如下图所示精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 15 页个人资料整理仅限学习使用5分别写出如图5-32 所示二叉树的先序、中序、后序遍历序列。图 5-32 二叉树示例答：先序遍历序列为：A-B-C-D-F-G-H-E ，中
19、序遍历序列为：B-A-D-G-F-H-C-E ，后序遍历序列为：B-G-H-F-D-E-C-A。6权值序列为：10、16、20、6、 30、24，请用图示来表达构造一棵哈夫曼树的全过程。答：构造这棵哈夫曼树的全过程如下所示。第 5 部分 图一、 填空1在一个具有4 个顶点的无向图中，要连通全部顶点，至少需要3 条边。2在无向图中，若顶点vi和 vj之间有一条边。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 15 页个人资料整理仅限学习使用4在有向图中，把从顶点vi到顶点 vj的弧记为 ，而把从顶点vj到顶点vi的弧记为 ，这是两条不同
20、的弧。5对于一个无向图，其邻接矩阵中第i 行 Bn(n+1 Cn(n-1/2 Dn(n+1/2 3对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。因此，有 n 个顶点的有向完全图包含有A 条边。An(n-1 Bn(n+1 Cn(n-1/2 Dn(n+1/2 4在一个无向图中，所有顶点的度数之和，是其所有边数之和的C 倍。A1/2 B1 C2 D4 5在一个有向图中，所有顶点的入度之和B 所有顶点的出度之和。A二分之一于B等于C两倍于D四倍于6一个无向连通网图的最小生成树A。A有一棵或多棵B只有一棵C一定有多棵D可能不存在7一个无向图有n 个顶点，那么该图拥有的边数至少可以是D。
21、A2n Bn Cn/2 D0 8一个有n个顶点的无向连通网图，其生成树里含有C 条边。A4n-1 B2n-1 Cn-1 D n/2 9下面关于图的存储的叙述中，正确的是C。A用邻接表存储图，所用存储空间大小只与图中顶点个数有关，与边数无关B用邻接表存储图，所用存储空间大小只与图中边数有关，与顶点个数无精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 15 页个人资料整理仅限学习使用关C用邻接矩阵存储图，所用存储空间大小只与图中顶点个数有关，与边数无关. D用邻接矩阵存储图，所用存储空间大小只与图中边数有关，与顶点个数无关10对如图7-2
22、1 所示的无向图实施深度优先搜索遍历，可能的遍历序列是B。图 7-21 无向图示例三、问答图 7-23 无向图示例1有如图7-23 所示的一个无向图，给出它的邻接矩阵以及从顶点v1出发的深度优先遍历序列。答：它的邻接矩阵如图所示。从顶点v1出发的深度优先遍历序列为：v1-v2-v4-v5-v7-v6-v3注意，该序列是不唯一的。2对图 7-24 回答下列问题：1）顶点集合V；2）边集合E；4）一个长度为5 的路径；5）一个长度为4的回路；6）图的一个生成树；7）邻接矩阵；8）邻接表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 15
23、 页个人资料整理仅限学习使用图 7-24 图示例答： 1）顶点集合V= v1, v2, v3, v4, v5, v6 。2）边集合E=, , , , , , , 。=1，D(v2=3，D(v3=D(v4=4，D(v5=D( v6=2。 v2- v3- v6- v4- v5。 v3- v5- v4- v2。所示。所示。所示。问答 5 的6）/2 D(n-1/2 3设散列表长m=14，散列函数h(key=key%11 。表中已有四个记录，关键字分别为15、38、 61、84，采用二次探测法解决冲突。那么关键字为49 的记录的散列地址为D。A1 B3 C5 D9 4在下列各种查找方法中，只有A 查找
24、法的平均查找长度与表长n 无关。A散列查找B二叉查找树C折半查找D分块查找四、应用1有关键字序列：20、 10、30、15、25、5、35、 12、27，请一步步画出构造二叉查找树的过程。答：构造二叉查找树的过程如下：2给出如图8-21 所示的一棵二叉查找树，在其基础上分别做操作：1）删除关键字为 15 的记录； 所示 所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 15 页个人资料整理仅限学习使用第 7 部分 选择与排序一、 填空1若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是稳定 的。
25、2选择 排序方法是从未排序的序列中挑选出元素，然后将其依次放入排好序的序列的一端。3快速 排序方法是通过适当的位置交换，把序列中的元素一次性地放到了它的最终位置上。4对关键字序列22、 86、19、49、12、30、65、35、 18 做一趟排序后，得到的结果是18、 12、 19、22、 49、30、65、 35、86。因此，可以认为采用的排序方法是快速排序。二、选择1在下面给出的各种排序算法中，只有A 是稳定排序算法。A冒泡排序B快速排序C直接选择排序D堆排序2在下面给出的各种排序算法中，只有B 不是稳定排序算法。A冒泡排序B快速排序C直接插入排序D折半插入排序3对关键字序列：46、79、
26、 56、38、40、84 采用快速排序方法。若以46为枢轴，那么一次划分后的结果应该是D。A38，40，46，79，56， 84 B38，40，46，84，56，79 C40，38，46，79，84，56 D40，38，46，56，79，84 4从待排序序列中依次取出元素与已排好序的序列里的元素进行比较，并存放到已排序序列的正确位置上，这种排序方法是A。A直接插入排序B交换排序C冒泡排序D选择排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 15 页个人资料整理仅限学习使用5具有 24个记录的待排序列，采用冒泡排序时，最少需要进行的比较次数是B。A1 B23 C24 D512 6用某种排序方法对序列：24、84、21、 47、16、28、 66、35、20 进行排序，序列的变化情况为：24，84，21，47，16， 28，66，35，20 20，16，21，24，47， 28，66，35，84 16，20，21，24，35， 28，47，66，84 16，20，21，24，28， 35，47，66，84 那么，这里采用的排序方法是C。A直接插入排序B冒泡排序C快速排序D选择排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 15 页