2022年自学考试《高级语言程序设计方案》习题 .docx

精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用2022 年自学考试高级语言程序设计习题第 1 部分 引论二、选择1链式储备结构中,每个数据的储备结点里 映数据间的规律关系； D 指向邻接储备结点的指针,用以反A 只能有 1 个 B只能有 2 个 C只能有 3 个 D可以有多个 2有下面的算法段：for i=0 ； i<n ； i+> k+ ；其时间复杂度为 B ；BOn> COlog 2n>DOn2> A O1> 四、应用1给出下面 3 个算法段的时间复杂度：<1） x+；<2） for j=1 ； j<n ； j+> x+ ；<3） for j=1 ； j<=n ； j+> for k=1 ； k<=m ； k+> x+ ；答： <1）的时间复杂度为 O1>；<2）的时间复杂度 <3）的时间复杂度是On>；On2>；第 2 部分 线性表一、 填空名师归纳总结 1以次序储备结构实现的线性表,被称为次序表；第 1 页,共 15 页2以链式储备结构实现的线性表,被称为链表；- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理仅限学习使用起始结点；3不带表头结点的链表,是指该链表的表头指针直接指向该链表的4次序表 Sq = a1,a2,a3, , an>< n1）中,每个数据元素需要占用 w 个储备单元；如 m 为元素 a1 的起始地址,那么元素 an 的储备地址是 m+n-1>* w ；5当线性表的数据元素个数基本稳固、很少进行插入和删除操作,但却要求以最快的速度存取表中的元素时,我们应当对该表采纳 次序 储备结构；二、选择1下面,对非空线性表特点的论述, C 是正确的；A 全部结点有且只有一个直接前驱B全部结点有且只有一个直接后继C每个结点至多只有一个直接前驱,至多只有一个直接后继D结点间是根据 1 对多的邻接关系来维系其规律关系的2带表头结点的单链表 Lk_h 为空的判定条件是 B ；A Lk_h = NULL BLk_h->Next = NULL CLk_h->Next = Lk_h DLk_h .= NULL 3往一个次序表的任一结点前插入一个新数据结点时,平均而言,需要移动 B 个结点；A nBn/2Cn+ 1Dn+ 1>/24在一个单链表中,已知 qtr 所指结点是 ptr 所指结点的直接前驱；现要在 qtr 所指结点和 ptr 所指结点之间插入一个 rtr 所指的结点,要执行的操作应当是 C ；A rtr->Next = ptr->Next ；ptr->Next = rtr ；Bptr->Next = rtr->Next ；Cqtr->Next = rtr ；rtr->Next = ptr ；Dptr->Next = rtr ；rtr->Next = qtr->Next ；5在一个单链表中,如现在要删除 的操作是 A ；A ptr->Next = ptr->Next->Next ；ptr 指针所指结点的直接后继结点,就需要执行Bptr = ptr->Next ； ptr->Next = ptr->Next->Next ；Cptr = ptr->Next->Next ；Dptr->Next= ptr ；6在长度为n 的次序表中,往其第i 个元素 <1in）之前插入一个新的元素时,需要往后移动 B 个元素；A n-i Bn-i +1 Cn-i-1 Dii 个元素 <1in）时,需要往前移动A 个元7在长度为n 的次序表中,删除第素；名师归纳总结 A n-i Bn-i +1 Cn-i-1 Di第 2 页,共 15 页8设tail 是指向一个非空带表头结点的循环单链表的尾指针；那么,删除链表起始结点的操作应当是 D ；A ptr = tail ；Btail = tail->Next ；- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 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 所指结点不是链表的尾结点,那么在 ptr 之后插入由指针 qtr 所指结点的操作应当是 B ；A qtr->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设计一个运算带表头结点的单链表 typedef struct node *link ；L 的长度 <即结点个数）的算法； typedef struct node ListItem element ；link next ；Node ；答：算法设计如下：int Length link L> Link p=L->next ；int sum=0； while p> sum+ ； p = p->next ； return sum> ； 2、已知一个带表头结点的无序单链表 小值；L；试编写一个算法,功能是从表中找出最大值和最 typedef struct node ListItem element ；struct node next；Node,*link ；viod maxminlink L> int max,min ； link p=L->next ；名师归纳总结 - - - - - - -第 3 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 ifp> max=p->element ； min=p->element ； p=p->next； while p> ifmax<p->element> max=p->element ； ifmin>p->element> min=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 return n> ； 第 3 部分 栈与队列一、 填空1限定插入和删除操作只能在一端进行的线性表,被称为是“栈；2假如在次序栈满时仍准备进行进栈操作,就称为发生了“上溢 ” 出错；3假如在次序栈空时仍准备进行出栈操作,就称为发生了下溢 ” 出错；4在具有 n 个数据结点的循环队列中,队满时共有n-1 个数据元素；5假如操作次序是先让字母A、B、C 进栈,做两次出栈；再让字母D、 E、F 进栈,做一次出栈；最终让字母 素应当是 A ；G 进栈,做三次出栈；最终这个堆栈从栈顶到栈底的余留元6队列中,答应进行删除的一端称为队首；二、选择名师归纳总结 - - - - - - -第 4 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用1一个栈的元素进栈序列是a、b、 c、d、e,那么下面的 C 不能做为一个出栈序列；A e、d、 c、b、a B d、e、c、b、a Cd、c、 e、a、b. Da、b、c、d、e 2判定一个次序队列 Qs<最多有 n 个元素）为空的条件是 C；A Qs_rear-Qs_front = n*size BQs_rear-Qs_front+1 = n*sizeCQs_front = Qs_rearD Qs_front = Qs_rear+size 3链栈与次序栈相比,一个较为明显的优点是 D ；A 通常不会显现栈空的情形 B插入操作更加便利C删除操作更加便利 D通常不会显现栈满的情形4一个循环队列的最大容量为m+1, front 为队首指针, rear 为队尾指针；那么进队操作时求队位号应当使用公式 D ；A Cq_front = Cq_front+1>%m CCq_rear = Cq_rear+1>%m BCq_front = Cq_front+1>%m+1> DCq_rear = Cq_rear+1>%m+1>5在一个循环次序队列里,队首指针 Cq_front 总是指向 A ；A 队首元素 B队首元素的前一个队位C任意位置 D队首元素的后一个队位6如一个栈的进栈序列是 1、 2、3、4,那么要求出栈序列为 3、 2、 1、4 时,进、出栈操作的次序应当是 A ；<注：所给次序中,I 表示进栈操作,O 表示出栈操作）A IIIOOOIO BIOIOIOIO CIIOOIOIO DIOIIIOOO 第 4 部分 树一、 填空1树中结点的度,是指结点拥有孩子 的个数；前驱结点,但可以有零个或多 个 后2树中除根结点外,其他结点有且只有一个继结点；3在数据结构中,把n<n0）棵互不相交的树的集合称为森林 ；4在如图 6-21 所示的树中,结点H 的祖先是 A、D、G ；名师归纳总结 图 6-21 树示例图 6-22 树示例度 ；第 5 页,共 15 页5在树中,一个结点的孩子个数,称为该结点的- - - - - - -精选学习资料 - - - - - - - - - 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 的结点,假如有左孩子,就左孩子的编号应当是 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设森林 F 中有 3 棵树,依次有结点 n1、n2、n3 个；把该森林转换成对应的二叉树后,该二叉树的右子树上的结点个数是 D ；An1 B n1+n2 Cn3 Dn2+n3 5设有由三棵树 T1、T2、T3 组成的森林,其结点个数分别为 n1、n2、n3；与该森林相应的二叉树为 Bt；就该二叉树根结点的左子树中应当有结点 A 个；A n1-1 Bn1 Cn1+1 Dn1+n2 6一棵有 n 个结点的树,在把它转换成对应的二叉树之后,该二叉树根结点的左子树上共有 B 个结点；A n-2 Bn-1 Cn+1 Dn+2 7一棵有 n 个结点的树,在把它转换成对应的二叉树之后,该二叉树根结点的右子树上共有 A 个结点；A 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；A A-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 个结点；A 63 B64 C127 D128 13在一棵非空二叉树的中序遍历序列里,根结点的右边 D 结点；A 只有左子树上的部分 B只有左子树上的全部C只有右子树上的部分 D只有右子树上的全部14在任何一棵二叉树的各种遍历序列中,叶结点的相对次序是 A ；A 不发生变化 B发生变化C不能确定 D以上都不对15权值为 1、2、6、8 的四个结点,所构造的哈夫曼树的带权路径长度是 D ；A 18 B28 C19 D29 16一棵二叉树度 2 的结点数为 7,度 1 的结点数为 6；那么它的叶结点数是 C ；A 6 B7 C8 D9 17在一棵二叉树中,第 5 层上的结点数最多是 C 个；A 8 B15C16 D32 四、应用1将图 6-26 所示的二叉树转换成相应的森林；图 6-26 二叉树示例 图 6-27 树示例答：转换成的森林如下图所示；名师归纳总结 - - - - - - -第 7 页,共 15 页精选学习资料 - - - - - - - - - 2给出如图个人资料整理仅限学习使用6-27 所示树的先序遍历序列和后序遍历序列；答：该树的先序遍历序列为：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 ,中序遍历序列为：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之间有一条边 <vi,vj）存在,那么就称顶点 v i 和 vj互为 邻接 点；名师归纳总结 3图中顶点vi的“ 度” ,是指与它相邻接 的顶点的个数,并记为Dv i>；第 9 页,共 15 页- - - - - - -精选学习资料 - - - - - - - - - 4在有向图中,把从顶点个人资料整理仅限学习使用vj到顶点 vivi到顶点 vj的弧记为 < vi,vj >,而把从顶点的弧记为 < v j,vi >,这是两条不同的弧；5对于一个无向图,其邻接矩阵中第 正好是第 i 个顶点 v i 的 度；i 行 <或第 i 列）里非零或非元素的个数,6对于一个有向图,其邻接矩阵中第 i 行里非零或非元素的个数,正好是第 i 个顶点 vi 的出度 ；其邻接矩阵中第 i 列里非零或非元素的个数,正好是第 i 个顶点 vi 的 入度；7在无向图中,如从顶点 vi 到顶点 vj 之间有 路径 存在,就称 vi 与 vj 是连通的；8假如无向图 G 中任意 一对顶点之间都是连通的,就称该图 G 为连通图,否就是非连通图；9在无向图G 中,尽可能多地从集合V 及 E 里收集顶点和边,使它们成为该图的一个极大的连通子图,这个子图就被称为是无向图G 的一个 连通重量 ；10包含无向连通图G 的全部n 个顶点在内的微小连通子图,是这个图的生成树；11只要在无向连通图的生成树里削减任意一条边,它就成为了一个 非连通图 ；12对图的广度优先搜寻,类似于对树进行 按层次 遍历；二、选择1在一个有n 个顶点的无向图中,要连通全部顶点,至少需要C 条边；A nBn+1 Cn-1 Dn/2 2对于一个无向完全图来说,它的每个不同顶点对之间,都存在有一条边；因此,有 n 个顶点的无向完全图包含有C 条边；Cnn-1>/2 A nn-1> Bnn+1> Dnn+1>/2 3对于一个有向完全图来说,它的每个不同顶点对之间,都存在有两条弧；因此,有 n 个顶点的有向完全图包含有A 条边；Cnn-1>/2 A nn-1> Bnn+1> Dnn+1>/2 4在一个无向图中,全部顶点的度数之和,是其全部边数之和的 C 倍；A 1/2 B1 C2 D4 5在一个有向图中,全部顶点的入度之和B 全部顶点的出度之和；A 二分之一于B等于C两倍于D四倍于6一个无向连通网图的最小生成树A ；C肯定有多棵A 有一棵或多棵B只有一棵D可能不存在7一个无向图有 n 个顶点,那么该图拥有的边数至少可以是 D；A 2n Bn Cn/2 D0 8一个有 n 个顶点的无向连通网图,其生成树里含有 C 条边；A 4n-1 B2n-1 Cn-1 D n/2 9下面关于图的储备的表达中,正确选项 C；A 用邻接表储备图,所用储备空间大小只与图中顶点个数有关,与边数无关B用邻接表储备图,所用储备空间大小只与图中边数有关,与顶点个数无名师归纳总结 - - - - - - -第 10 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用关 C用邻接矩阵储备图,所用储备空间大小只与图中顶点个数有关,与边数无关. D用邻接矩阵储备图,所用储备空间大小只与图中边数有关,与顶点个数无关10对如图 7-21 所示的无向图实施深度优先搜寻遍历,可能的遍历序列是 B；图 7-21 无向图示例三、问答图 7-23 无向图示例1有如图7-23 所示的一个无向图,给出它的邻接矩阵以及从顶点v1动身的深度优先遍历序列；答：它的邻接矩阵如下列图；从顶点v 1动身的深度优先遍历序列为：v 1->v 2->v 4->v 5->v 7->v 6->v 3 留意,该序列是不唯独的；2对图 7-24 回答以下问题：<1）顶点集合V；<2）边集合 E；<3）每个顶点x 的度 Dx> ；<4）一个长度为5 的路径；<5 ）一个长度为4的回路；名师归纳总结 <6）图的一个生成树；<7）邻接矩阵；<8）邻接表；第 11 页,共 15 页- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用图 7-24 图示例答： <1）顶点集合 V= v1, v2, v3, v4, v5, v6 ；<2）边集合 E=< v1, v2>, < v2, v3>, < v2, v4>, < v3, v4>, < v3, v5>, < v4, v5>, < v3, v6>, < v4, v6> ；<3）每个顶点的度：Dv1>=1,Dv2>=3,Dv 3>=D v4>=4,Dv5>=D v6>=2；<4）一个长度为 5 的路径是： v1-> v2-> v3-> v6-> v4-> v5；<5）一个长度为 4 的回路是： v2-> v3-> v5-> v4-> v2；<6）如下图 a>所示；<7）如下图 b>所示；<8）如下图 c>所示；问答 5 的 <6） <8）答案第 6 部分 二叉排序树与散列表一、 填空1在散列查找中使用的函数,称为“列表或哈希表；散列函数 ” ；在散列法中的查找表,称为散2散列法中,假如两个不同的关键字经过散列函数的运算后,得到了相同的索引 地址,那么这种现象被称作“冲突 ” ；3散列法中,运算后得到相同索引地址的那些不同关键字,被称作“同义词 ” ；二、选择1在对线性表进行折半查找时,要求线性表必需 B；A 以次序方式储备B以次序方式储备,且结点按关键字有序排列名师归纳总结 - - - - - - -第 12 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用C以链式方式储备D以链式方式储备,且结点按关键字有序排列2采纳次序查找法查找长度为 n 的线性表时,其平均查找长度为 C；A n Bn/2 Cn+1>/2 Dn-1>/2 3设散列表长 m=14,散列函数 hkey>=key%11 ；表中已有四个记录,关键字分别为 15、38、 61、84,采纳二次探测法解决冲突；那么关键字为 D；49 的记录的散列地址为A 1 B3 C5 D9 4在以下各种查找方法中,只有 A 查找法的平均查找长度与表长 n 无关；A 散列查找 B二叉查找树 C折半查找D分块查找四、应用1有关键字序列：20、 10、30、15、25、5、35、 12、27,请一步步画出构造二叉查找树的过程；答：构造二叉查找树的过程如下：2给出如图8-21 所示的一棵二叉查找树,在其基础上分别做操作：<1）删除关键字为 15 的记录； <2）插入关键字为20 的记录；画出这两个操作完成后该树的外形；图 8-21 二叉查找树示例名师归纳总结 答： 1）删除关键字为15 的记录后,该树的外形如图a>所示第 13 页,共 15 页 <2）插入关键字为20 的记录后,该树的外形如图c>所示；- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用第 7 部分 选择与排序一、 填空1如经过某种排序之后,那些有相同关键字值的记录间的相对位置保持不变,那么称这种排序方法是 稳固 的；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、 56、38、40、84 采纳快速排序方法；如以46 为枢轴,那么一次划分后的结果应当是D；A 38,40,46,79,56, 84 C40,38,46,79,84,56 B38,40,46,84,56,79 D40,38,46,56,79,84 4从待排序序列中依次取出元素与已排好序的序列里的元素进行比较,并存放到已排序序列的正确位置上,这种排序方法是A；C冒泡排序A 直接插入排序B交换排序D选择排序名师归纳总结 - - - - - - -第 14 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用5具有 24 个记录的待排序列,采纳冒泡排序时,最少需要进行的比较次数是 B；A 1 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；B冒泡排序C快速排序A 直接插入排序D选择排序名师归纳总结 - - - - - - -第 15 页,共 15 页