资源描述
一、选择题（共50分，25小题，每小题2分）对下面各题，从给出的几个可供选择的答案中选一个正确的答案，答案一律写在题号左边线外。1下面叙述正确的是_。/C A) 算法的执行效率与数据的存储结构无关 B) 算法的空间复杂度是指算法程序中指令（或语句）的条数 C) 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D) 以上三种描述都不对2对于8皇后问题，最佳的算法设计方法是_ 。 /D 算法设计方法 A) 列举法（穷举法） B) 递归法 C) 减半递推法 D) 回溯法3从逻辑上来看，可以把数据结构划分成_两类。 /B A) 内部结构和外部结构 B) 线性结构和非线性结构 C) 紧凑结构和非紧凑结构 D) 动态结构和静态结构4下面关于线性表的叙述中，错误的是_/C 顺序结构与链式结构的区别 A) 线性表采用顺序存储，必须占用一片连续的存储单元 B) 线性表采用链接存储，不必占用一片连续的存储单元 C) 线性表采用顺序存储，便于进行插入和删除操作 D) 线性表采用链接存储，便于进行插入和删除操作5若采用顺序存储方式并且采用顺序查找方式，在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为_。 /A A) n B) n/2 C) (n+1)/2 D) n+16顺序查找法适用于存储结构为_ 的线性表。/D 顺序结构与链式结构的区别 A) 数组结构 B) 顺序结构 C)链接结构 D) 顺序或链接结构7栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则全部5个元素的出栈序列可能是_。 /D 栈 A) ABCED B) DBCEA C) CDABE D) DCBEA8在一个顺序循环队列中，队首指针指向队首元素的_位置。/A栈 A) 前一个 B) 后一个 C) 当前 D) 最后 9head是一个循环链表头结点指针，tail指向尾结点，欲将一个p指向的结点插入链表的尾部，正确的操作是_。/A 循环链表的运算 A) pnext = tailnext; tailnext=p; B) tailnext = p; pnext = headnext; C) tailnext = p; pnext = tailnext; D) tailnext = p; pnext = NULL;10a是一个nn的带宽为3的带状矩阵，在三条对角线上有3n-2个元素，按行方式存储矩阵的三条对角线上的元素到一维数组B中，则元素aij( |i-j|1 )存放在B数组中的位置是_。 /D 规则矩阵的存取 A) i+2j-1 B) i+j+2 C) 3i-j+1 D) 2i+j-2 11稀疏矩阵的压缩存储方法有_。/ D A) 三列二维数组和邻接表 B) 邻接矩阵和三列二维数组 C) 邻接矩阵和邻接表 D) 三列二维数组和十字链表12若线性表中的元素个数很多，在以下有关索引存储结构的描述中，_ 是正确的。 A) 采用索引存储结构，可降低线性表的存储空间。 /C 索引存储结构 B) 采用索引存储结构，降低了线性表的查找速度。 C) 采用索引存储结构，可提高线性表的查找速度。 D) 采用“顺序-索引-顺序”结构的存储空间比“顺序-索引-链接”多。13将68个结点的完全二叉树，按顺序存储结构存于数组A(1:68)中，叶子结点的最小顺序号是_。假定根结点的序号是1。 /C 二叉树的性质 A) 65 B) 64 C) 35 D) 3414具有100个结点的完全二叉树从根开始（根的编号为1），每层从左至右依次对结点编号，编号为47的结点的右儿子的编号为_。 /DA) 没有右儿子 B) 48 C) 94 D) 95 15邻接矩阵（关联矩阵）是对称矩阵的图为_。 /B A)有向图 B) 无向图 C)带权连通图 D) 带权有向图16一个有六个顶点的无向图的邻接矩阵如下图所示，则该图中结点B的度为_。 A) 3 B) 4 C) 6 D) 8 /B 图ABCDEFA011010B101011C110100D001001E110001F01011017对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这种排序方法是_。/CA) 直接选择排序 B) 直接插入排序 C) 快速排序 D) 冒泡排序18设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用_法。 /C A) 冒泡排序 B) 快速排序 C) 堆排序 D) shell排序 19软件工程学的目的是以较低的成本，研制_质量的软件。/B A) 较低 B) 较高 C) 可靠 D) 优秀20软件生存周期归纳为三个时期，下列_项不是其中的一个时期。/AA) 测试期 B) 定义期C) 维护期 D) 开发期21需求分析阶段的任务是确定_。/DA) 软件开发方法 B) 软件开发工具C) 软件开发费 D) 软件系统的功能22结构化分析SA主要使用_两种描术手段。/A A) 数据流图和数据字典 B) 数据流图和流程图 C) 流程图和文字说明 D) 流程图和数据字典23模块的独立性是软件模块化设计的关键之一，一般用_两个定性标准来度量模块的独立性。/C A) 软件的质量和可重用性 B) 软件的质量和聚合 C) 内聚和耦合 D) 软件的质量和耦合24软件测试的目的是_。/B A) 发现程序中的所有错误 B) 尽可能多地发现程序中的错误 C) 证明程序是正确的 D) 证明程序做了应做的事25在软件工程中,只根据程序功能说明而不关心程序内部逻辑的测试方法，称为_测试。/BA)白盒法 B) 黑盒法 C)灰盒法 D)综合法二、填空题（共30分，10小题，每小题3分）1构成数据结构的两个要素：一是_，二是_。答案：数据元素的集合，该集合上的一个关系（这里指二元关系）2数据流的类型分为_、_两种。答案：变换型，事务型3软件维护通常有四种类型，它们分别是_、_、完善性维护和预防性维护。 答案：改正性维护，适应性维护4设线性Hash表的长度 n=12，Hash码的计算公式为i = mod(k, n)+1，请先分别计算下列数据元素的Hash码，然后将该数据序列填入Hash表并写出每个数据元素在填入过程中发生的冲突次数。说明（1）在Hash表的填入过程中采用线性探测法处理冲突；（2）mod(k, n)的意义是k%n。数据元素序列为（19, 22, 14, 26, 29, 41, 30, 55, 11, 21, 35, 36） Hash码分别为：Hash表地址： 1 2 3 4 5 6 7 8 9 10 11 12 Hash表：冲突次数：以下为答案：数据元素序列为（19, 22, 14, 26, 29, 41, 30, 55, 11, 21, 35, 36）Hash码i： 8, 11, 3, 3, 6, 6, 7, 8, 12, 10, 12, 1Hash表地址： 1 2 3 4 5 6 7 8 9 10 11 12 Hash表：21213514263629411930552211冲突次数： 3 2 0 1 4 0 1 0 2 2 0 05对以下稀疏矩阵A可按行优先策略用三列二维数组B表示，请写出B。 答案：6已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，请画出该二叉树。abcde答案：7已知一有向图的邻接表存储结构如下：12 34 534 45 24 2根据有向图的深度优先遍历算法，从结点V1出发，得到的访问序列是_。若用广度优先遍历算法，则从结点V1出发，得到的访问序列是_。答案：深度优先：V1V3V4V5V2 广度优先：V1V3 V2V4V58已知关键字序列为82，51，56，20，90，03，80，95，44，30，46，76用希尔排序法对该序列进行排序，前两趟（即步长是6和3时）的结果依次是：(h=6)_ (h=3)_ 答案：(h=6) 80, 51, 44, 20, 46, 03, 82, 95, 56, 30, 90, 76 (h=3) 20, 46, 03, 30, 51, 44, 80, 90, 56, 82, 95, 76 9已知数据序列 24, 87, 7, 9, 82, 16, 73, 13, 79, 80, 75, 64，对该序列进行快速排序，则第一趟分割的结果是：（请先阅读下面的说明）_，此次的分割值为_对前半部分和后半部分再次分别分割后总的结果是：_，前半部分的分割值为_，后半部分的分割值为_。说明：选取分割元素的方法可以有如下两种：（您只要选取一种方法解题即可）（1）每次都是选取待分割数据序列的第一个元素作为分割值。（2）选取待分割数据序列的（第一，最后，中间点）三个元素的中间值作为分割值。您使用的是第_种方法得到的上述分割结果。答案：第（1）种方法第1趟分割后：13, 16, 7, 9, 24, 82, 73, 87, 79, 80, 75, 64, 此次的分割值为24第2趟分割后：9, 7, 13, 16, 24, 64, 73, 75, 79, 80, 82, 87, 前半部分的分割值为13，后半部分的分割值为82 第（2）种方法第1趟分割后：13, 16, 7, 9, 24, 82, 73, 87, 79, 80, 75, 64, 此次的分割值为24第2趟分割后：9, 7, 13, 16, 24, 64, 73, 75, 79, 80, 82, 87, 前半部分的分割值为13，后半部分的分割值为79 10一个无序数据序列为 71, 42, 47, 12, 85, 4, 73, 86, 32, 22, 38, 68, 14, 77, 57，请对该序列建堆。堆中的数据元素序列为：_提示：可用一个完全二叉树帮助理解堆。答案：86, 85, 77, 42, 71, 68, 73, 12, 32, 22, 38, 4, 14, 47, 57, 三、算法设计题（共20分，其中第1小题8分，第2小题12分）说明：请用C|C+ 语言描述您的算法。如果有困难，可以用算法描述语言（自然语言伪代码）描述您的算法设计思想。1整型数据序列存放在一维数组中，请写出简单直接插入排序算法。算法函数原型为：void insort(int a , int n) 其中参数a是待排序数组，n是数组元素个数。答案：void insort(int a , int n) int j, k, t; for(j=1; j=0)&(akt) / 2分 ak+1=ak; k-; / 1分ak+1=t; / 1分2 对于多项式： 假定：ai0, (i=1, 2, 3, , m)，且em em-1 e1 0可以使用循环链表将该多项式表示为：p-1 am ema1 e1am-1 em-1其中结点的定义如下：struct nodedouble coef; /* 系数域，表示系数ai */int exp; /* 指数域，表示指数ei */struct node *next; /* 下一结点指针 */;首结点的指数域值为 -1。请写出两个多项式A(x)和B(x)相加的算法。算法的函数原型为：C语言描述：struct node *addpoly(struct node *ah, struct node *bh)C语言描述：node *addpoly(node *ah, node *bh)参数ah和bh分别是指向多项式A(x)和B(x)环形链表的首指针，要求函数返回相加结果的环形链表的首指针。答案：/* 多项式的相加 */ struct node *addpoly(struct node *ah, struct node *bh) struct node *k,*p,*m,*n,*ch;int e;double d;p=(struct node *)malloc(sizeof(struct node); /首结点创建：2分p-exp = -1; p-next = p; ch=p; /* 建立一个只有首结点的空循环链表，存放结果 */ /首结点指针：1分k=p; /* 记住链尾 */m=ah-next; n=bh-next;while( (m-exp!=-1) | (n-exp!=-1) ) /循环条件：2分 if (m-exp=n-exp) /* 两个链当前结点的指数值相等 */ /相等处理：2分 d = m-coef + n-coef;e = m-exp;m = m-next; n = n-next;else if(m-exp n-exp) /* ah 链当前结点指数大于 bh 当前结点指数 */ d=m-coef; /大于小于处理：2分e=m-exp;m=m-next;else /* ah链当前结点指数小于 bh 当前结点指数 */d=n-coef; e=n-exp;n=n-next;if(d!=0) /* 如果系数不为0 */ /插入结点处理：2分p=(struct node *)malloc(sizeof(struct node);p-exp=e; p-coef=d;p-next=ch;k-next=p;k=p;return(ch); /返回首指针：1分
展开阅读全文