2016现代科技学院《软件技术基础》练习题+答案

1、软件技术基础练习题太原理工大学现代科技学院2016第一章算法一、选择题1 .算法的复杂度包括【】。A、时间复杂度B、空间复杂度C、时间及空间复杂度D、以上都不对2 .若x在长度为n的无序线性顺序表中的概率为 50%,则在该表中查找x的平均查找次数（平均 性态分析）为【1A、（n*3+1）/4B、（n-1）/2C、（n+1）/2D、（n+1）*n/23 .若x在长度为n的无序线性顺序表中的概率为50%,则在该表中查找x的最坏情况分析为【】A、n/2B、（n-1）/2C、（n+1）/2D、n4 .已知基本运算执行次数与n的关系，则下列哪个时间复杂度最大：【】。A. f（n） = 1B. f（n）

2、= 2n - 1C. f（n） = 10000n+10000D. f（n） = n2-100005 .算法分析的目的是【】。A,找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性、填空题1 .常用算法包括? 和回溯法2 .算法的基本特征有 ?有穷性、输入和输出。3 .下列程序段的时间复杂度是 。for （i=1 ； i<=n ； i+）Ai, i=0；4 .下列程序段的时间复杂度是 s=0；for（i=1 ； i<=2n ； i+）for（j=1 ; j<=n； j+）s=s+Bij；sum=s；5 .下列程序段的时间复

3、杂度是 i=1 ；while （i<=n）i=i*2 ；6 .在下面的程序段中，s= s + p；语句的执行次数为 , p= pxj语句的执行次数为 ，该程序段的时间复杂度为 。int i=0, s=0, p=1;while( +i<=n )for(j=1； j<=i； j+ )p = p Ks = s + p;7.常见时间复杂度的量级有：常数阶0()、对数阶0()、线性阶0()、平方阶0(而指数阶0()。三、判断题1.算法和程序没有区别，所以在数据结构中二者是通用的。第二章基本数据结构及其运算、选择题1 .数据结构的逻辑结构被形式地定义为（D,R）,其中口是【（1）的有限集

4、合，R是口上（2） 的有限集合。（1） A.算法B.数据元素C.数据操作D.逻辑结构（2） A.操作B.映像C.存储D.关系2 .在数据结构中，从逻辑上可以把数据结构分为【1A.动态结构和静态结构B.紧凑结构和非紧凑结构C,线性结构和非线性结构D,内部结构和外部结构3设进栈的输入序列是1,2,3,4,则【】不可能是其出栈序列。A. 1243B. 2134C. 1432D. 43124.设有一顺序栈s,元素s1, s2,s3,s4,s5,s6依次入栈，如果6个元素出栈的顺序是s2, s3,54, s6, s5, s1,则栈的容量至少应该是【 JoA. 2 B. 3 C. 5 D. 65 .线性表

5、若采用链表存储结构，要求内存中可用存储单元的地址11A.必须是连续的B.部分必须是连续的C. 一定是不连续的D.连续不连续都可以6 .有如下定义struct Snode int data; struct Snode *next; *p, *q;则将新结点q插入到单链表的p结点之后，下面的操作【】是正确的。A. q=p-> next;p-> next =q-> next;B. p-> next =q-> next;q=p-> next;C. q-> next =p-> next;p-> next =q;D. p-> next =q;q-

6、> next =p-> next;7 . 一个线性顺序表第一个元素的存储地址是2000,每个元素长度为4个字节，则第3个元素的起始存储地址为【】。A. 2008B. 2000C. 2004D. 20128 .下列关于二叉树的叙述中，正确的是【A.叶子结点总是比度为2的结点少一个B.叶子结点总是比度为2的结点多一个C.叶子结点数是度为2的结点数的两倍D.度为2的结点数是度为1的结点数的两倍9 .某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【A. 10B. 8C. 6D. 410 . 一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为【A. 16B. 10C.

7、6D. 411 .某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层） 【1 OA. 3 B. 4 C. 6 D. 712 .某二叉树有7个度为2的结点，则该二叉树中的叶子结点数是【】A.10B.8C.4D.613 . 一棵深度为k的满二叉树中结点的个数是【】A. 2kB. 2k-1C. 2k-1D. 2k-1-114 .在以下的叙述中，正确的是【A .线性表的线性存储结构优于链式存储结构B.二维数组是它的每个数据元素为一个线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出15 .以下说法正确的是【A.数据元素是数据的最小单位B.数据项是数据的

8、基本单位C.数据结构是带有结构的各数据项的集合D.数据结构是带有结构的数据元素的集合16 .线性表L=(a1, a2,，ai,，an),下列说法正确的是【A .每个元素都有一个直接前驱和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小的D .除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17 .对于顺序线性表的优缺点，以下说法错误的是【1A .无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任一结点C.插入和删除操作较方便D.由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)18 .在含有n

9、个结点的顺序存储的线性表中，在任一结点i前插入一个结点所需移动结点的次数为【1 0A. n/2B. iC. n-iD. n-i+119 .在含有n个结点的顺序存储的线性表中，删除第i个结点所需移动结点的次数为【1A. n/2B. iC. n-iD. n-i+120 .在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数 为【A. nB. n/2C. (n-1)/2D. (n+1)/221 .在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为【1A. nB. n/2C. (n-1)/2D. (n+1)/222 .带头结点的单链表为空的条件是【1

10、A. head=NULL B, head->next=NULL C, head->next=head D. head!=NULL23 .在一个单链表中，若删除*p结点的后继结点，则执行【1A. q=p->next； p->next=q->next； free(q);B. p=p->next； p->next=p->next->next； free(p);C. p->next=p->next； free(p->next)；D. p=p->next->next； free(p->next)；24 .循环链表的

11、主要优点是【】。A.不再需要头指针了B.已知某个结点的位置后，容易找到它的直接前驱C.在进行插入、删除操作时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表25 .在线性表的下列存储结构中，读取元素花费时间最少的是【1A .单链表 B.双链表 C.循环链表D .顺序表26 .设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a肱次通过栈S, 一个元素出栈后即进入 队列Q,若出队的顺序为a2,a4,a3,a6,a5,a 1则栈S的容量至少应该为【A. 2 B. 3 C. 5 D. 627 .二维数组A11 , 6采用行序为主序方式存储，每个数据元素占4个存储单元，且

12、A0 , 0的存储地址是1000,则A8, 4的存储地址是【】。A. 1208 B. 1212 C. 1368 D. 136428 .对矩阵压缩存储是为了【】。A.方便运算 B.节省空间 C.方便存储D.提高运算速度29 .以下说法错误的是【】。A.树形结构的特点是一个结点可以有多个直接前驱B.线性结构中的一个结点至多只有一个直接后继C.二叉树与树是两种不同的数据结构D.树(及一切树形结构)是一种“分支层次结构30 .以下说法错误的是【】。A.二叉树可以是空集B.二叉树的任一结点都有两棵子树C.二叉树与树具有相同的树形结构D、二叉树中任一结点的两棵子树有次序之分31 . 一棵二叉树满足下列条件

13、：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有 结点的值，而大于右子树上所有结点的值。现采用【】遍历方式就可以得到这棵二叉树所有结点的递减序列。A .前序 B .中序 C.后序 D.层次32 .对含有】个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A. 0 B. 1C. 2 D.不存在这样的二叉树33 .已知某二叉树的后序遍历序列是 deacb),中序遍历序列是deabG它的前序遍历序列是【】。A. acbed B. baedcC. dceab D. cedba34 .某二叉树的前序遍历的结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf

14、,则其后序遍历的结点访问顺序是11A. bdgcefha B. gdbecfha C. bdgechfa D. gdbehfca35 .在图6-2中的二叉树中，【】不是完全二叉树。36 .树最适合用来表示【】。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据37 .在计算递归函数时，如不使用递归过程，则一般情况下必须借助于【】数据结构。A.栈 B.树C.双向队列 D.顺序表38 .对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【1A. N B. (N-1)*(N-1) C. N-1 D. N*N39 .以下说法错误的是【】。A.用邻

15、接矩阵法存储图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结 点个数有关，而与图的边数无关B.邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用C.存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下(或上)三角部分D.用邻接矩阵A表示图，判定任意两个结点 Vi和Vj之间是否有长度为m的路径相连，则只 要检查Am的第i行第j列的元素是否为0即可、填空题1 .通常，数据在计算机中的存储结构有 存储2构、存储2构、存储结构和存储结构四种基本存储结构。2 .设循环队列的容量为70 (序号为170),现经过一系列的入队与退队运算后，有： .front= 14,

16、 rear = 21,循环队列中有 个元素 .front = 23, rear = 12,循环队列中有 个元素3 .单链表表示法的基本思想是用 表示结点间的逻辑关系。4 .栈的逻辑特点是,队列的逻辑特点是5 . :可以作为实现递归函数调用的一种数据结构。6 .在队列中，新插入的结点只能添加到 o7 .设用一维数组An来表示一个栈，令 A0为栈底。用整型变量t来指示当前栈顶的位置，At 为栈顶元素。往栈中压入一个新元素时，变量 t的值,从栈中弹出一个元素时，变量 t的值。设空栈时，输入序列a, b, c经过push, pop, push, push, pop操作后，从栈中弹出的元 素是。8 .树

17、(及一切树形结构)是一种结构。在树中，结点没有直接前驱。9 .二叉树第i(i>0)层上至多有个结点。10 .深度为k(k>0)的二叉树至多有 个结点。11 .二叉树通常有 存储结构和存储结构两类存储结构。12 .对二叉链表的访问只能从 指针开始。13 .对无向图，其邻接矩阵是一个关于 对称的矩阵。14 .请填空完成线性表在顺序存储下的插入运算程序：在线性表 v中第i个位置插入值为x的元素 struct sqlistint elemMAXSIZE;int last;void insert(sqlist v, int i, int x)int k;if (i<1 | i>v

18、.last+1)printf(''插入位置不合适！ n” );else if (v.last>= MAXSIZE -1) printf("线性表已满！ n" );elsefor( k = v.last; k >= i; k-) v.elemi = x;v.last+; 15 .请填空完成线性表在顺序存储下的删除运算程序：在线性表v中删除第i个位置的元素struct sqlistint elemMAXSIZE;int last;void delete(sqlist v, int i) int k;if (i<1 | i>v.last)p

19、rintf("删除位置不合适！n”);else for( k = i+1; k <= v.last; k+ )v.elemk-1 = v.elemk;16 .请填空完成栈在顺序存储下的入栈运算程序：将值为x的元素入栈sstruct stack int sDataMAXSIZE;int top;/栈顶指针，指向当前栈顶的位置;void push(struct stack s, int x)/ 入栈运算if (s.top = MAXSIZE-1) printf("栈满溢出 n''); elses.sDatatop=x;17 .请填空完成栈在顺序存储下的出栈

20、运算程序：栈 s出栈，并将出栈元素作为函数返回值返回 struct stack int sDataMAXSIZE;int top;/栈顶指针，指向当前栈顶的位置;int pop(struct stack s) /退(出)栈运算 int x;if (s.top = -1)printf("栈空溢出 n'');exit(1); else x=s.sDatatop;return x;三、判断题1 .顺序存储的线性表可以随机存取。2 .顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的 元素需要移动。3 .在线性表的顺序存储结构中，逻辑上相邻的两

21、个元素在物理位置上不一定相邻。4 .在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。5 .在单链表中，可以从头结点开始查找任何一个元素。6 .线性表的链式存储结构优于顺序存储结构。7 .在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。8 .在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储 结构。9 .顺序存储方式只能用于存储线性结构。10 .循环队列中元素个数为rear-front。11 . 一个栈的输入序列是1,2,3,4,则在栈的输出序列中可以得到 4,3,1212 .若以链表作为栈的存储结构，则入栈需要判断

22、栈是否满.13 .数组是同类型值的集合。14 .数组是一组连续的内存单元。15 .数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。16 .插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。17 .使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。18 .二叉树是树的特殊形式。19 .树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一 棵子树的情况下也要明确指出该子树是左子树还是右子树。20 .用邻接矩阵法存储图时，所占用的存储空间大小仅与图中结点个数有关。21 .存储有向图的邻接矩阵一定是对称的。四、简答应用

23、题1 .有三个元素的进栈序列是 1,2, 3,举出此三个元素可能的出栈序列，并写出相应的进栈和出 栈操作序列（假设以I和。表示进栈和出栈操作）。2 .试将下列稀疏矩阵A用三元组（三列二维表格）形式来表示，并写出对应的辅助向量POS和NUM。400000300000006500003 .试写出对下图所示的二叉树分别按前序、中序和后序遍历时得到的结点序列。4 .画出下图所示的树对应的二叉树。5 .请写出下图对应的关联矩阵R及求值矩阵V,结点A,B,C,D,E分别用1,2,3,4,5编号6 .逻辑结构与存储结构是什么关系？7 .描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。8

24、.何时选用顺序表，何时选用链表作为线性表的存储结构为宜？9 .如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度 也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？10 .若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元 素，应该用哪种存储结构？为什么？11 .设计算法并写出程序，实现“计算带头结点的单链表的结点个数”。12 .已知一棵二叉树的中序序列和后序序列分别为 BDCEAFHG和DECBHGFA，试画出这棵二叉树, 并写出其前序遍历序列。第三章查找与排序、选择题1.对采用折半查找法进行查找操作的查找表，要求按【】

25、方式进行存储。A .顺序存储B.链式存储C .顺序存储且结点按关键字有序D.链式存储且结点按关键字有序2 .设有序表的关键字序列为(1, 4, 6, 10, 18, 35, 42, 53, 67, 71, 78, 84, 92, 99),当用折 半查找法查找键值为35的结点时，经【 】次比较后查找成功。A. 2 B. 3 C. 4 D. 63 .分块查找的时间性能1A .低于折半查找B.高于顺序查找而低于折半查找C.高于顺序查找D .低于顺序查找而高于折半查找4 .设哈希函数为H(key尸key%7, 一组关键字为(37, 21, 9, 20, 30, 19, 46),哈希表T的地址 空间为0

26、.6,用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为【1A. 012 342120 37 9 46 30 196206206B. 0123452146379301921 19 937 30 46D. 012345C. 01234520 37 3021 46 195 .设有一个用线性探测法解决冲突得到的哈希表：0123456789101325801617614哈希函数为H(key)=key%11,若要查找元素14,探测的次数是【A. 3 B. 6 C. 7 D. 96 .在哈希函数H(key)=key %m中，一般来讲，m应取【A .奇数 B .偶数 C.素数 D.充分大的数7

27、.以下说法错误的是【A.哈希法存储的基本思想是由关键字的值决定数据的存储地址8 .哈希表的结点中只包含数据元素自身的信息，不包含任何指针C.哈希表的基本思想与顺序查找、对分查找和分块查找都不同D .哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法8 .在关键字随机分布的情况下，用二叉排序树的方法进行查找，具平均查找长度与【】查找方法量级相当。A .分块 B .顺序 C .折半D.散列9 .在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为【A. O(n)B. O(1) C. O(log2n)D. O(n2)10 .哈希表的平均查找长度()。A.与处理冲突的

28、方法有关而与表的长度无关B.与处理冲突的方法无关而与表的长度有关C.与处理冲突的方法有关且与表的长度有关D.与处理冲突的方法无关且与表的长度无关11 .有数据(49,32,40,6,45,12,56),从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小, 则应选择下列【】输入序列。A. 45,12,49,6,40,56,32B. 40,12,6,32,49,45,56C. 6, 12, 32,40,45,49,56D. 32,12,6,40,45,56,4912 .在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为【1A. n B. log2nC. (h+1)/2

29、D. h13.1 方法是从未排序序列中依次取出元素与已经排序序列中的元素进行比较，将其放人已经 排序序列的正确位置上。A.双向冒泡排序B .插入排序C.冒泡排序D.选择排序14.1】方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。A.双向冒泡排序B .插入排序C.冒泡排序D.选择排序二、填空题1 .索引顺序表上的查找分两个阶段：一、 ;二、该查找方法称为 查找。2 .二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值 于其左 孩子(及其子孙)的键值且 于其右孩子(及其子孙)的键值。3 .中序遍历一棵二叉排序树所得到的结点访问序列是键值的 序列。4 .二叉

30、排序树上的查找长度不仅与 :有关，也与二叉排序树的 号关。5 .折半查找方法仅适用于这样的表：表中的记录必须 ,其存储结构必须是。6 .按照排序过程涉及的存储设备的不同，排序可分为 排序和排序。7 .请填空完成顺序查找算法程序：在线性表v中查找值为k的元素struct sqlist int elemMAXSIZE;int last;int seqsearch (struct sqlist v, int k) int i；for(i=1;i<=v.last;i+)if()return i; /*查找成功，返回被查元素在表中相对位置*/return 0; /*查找失败，返回0*/ 8 .请填

31、空完成改进型的顺序查找算法程序：在线性表v中查找值为k的元素struct sqlistint elemMAXSIZE;int last;；int seqsearch (struct sqlist v, int k) int i;v.elem0=k;while()i-;return i;/*返回被查元素在表中相对位置，0为失败，其他为成功*/9 .请填空完成对分查找算法程序：在线性表v中查找值为x的元素struct sqlistint elemMAXSIZE;int last;；int search (struct sqlist v, int x ) int low, high, mid;low

32、 = 1; high = v.last;while () mid = (low + high )/2;中间位置元素下标if ()return mid;/返回被查元素在表中相对位置if ()high=mid - 1; 取前半部分 else /取后半部分 return (-1); /查找失败，返回-110 .请填空完成选择排序算法程序：在具有 n个元素的线性表R按关键字进行排序 struct record int key;int otheritem;void selectsort(struct record R口,int n)/*注意待排记录放在R1到Rn中*/int i,j,k; struct

33、record temp;for(i=1;i<n;i+) k=i;for(;j<=n;j+) if(Rj.keyvRk.key)if(i!=k)/*交换元素，设结构体变量可以整体赋值*/temp=Rk; Rk=Ri; Ri=temp;三、判断题1 .分块查找方法的平均查找长度低于顺序查找，高于折半查找。2 .在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查 找时间。3 .虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的四、简答应用题1 .将关键字序列26,25,3,38, 6,7,12,24依次填入长度为n=12的线性哈希表中，哈希码为i

34、=INT(k / 4)+ 1,并指出各关键字元素在插入过程中的冲突次数。2 .依次输入以下元素序列：12,6,3,20,18,346请按照输入的顺序构造一棵二叉排序树，并计算出要在这棵二叉排序树中查找18,需要比较多少次？3 .有如下序列：12,6,20,18,34,10,请分别写出用冒泡法、选择法、插入法对该序列进行排序的过 程，并作出适当的标示。第四章资源管理技术一、选择题1 .操作系统是计算机系统的一种【A.应用软件 B.系统软件 c.通用软件 D.工具软件2 .允许多个用户以交互方式使用计算机的操作系统是【1A.分时操作系统B .批处理单道系统 C.实时操作系统D .批处理多道系统3

35、.下列系统中【】是实时系统。A.计算机图像处理系统B.办公自动化系统C.化学反应堆控制系统D .计算机辅助设计系统4 .操作系统是一种系统软件，它【A .控制程序的执行B.管理计算机系统的资源C.方便用户使用计算机D.管理计算机系统的资源和控制程序的执行5 .实时操作系统对可靠性和安全性要求极高，它【A.十分注重系统资源的利用率B.不强调响应速度C.不强求系统资源的利用率 D.不必向用户反馈信息1.1 】为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。A,处理器管理B.存储管理C.文件管理 D .作业管理7 .财务管理软件是一种专用程序，它属于【】A.系统软件B.应用

36、软件 C.接口软件D.支援软件8 .在多道程序设计技术的计算机系统中，中央处理器【1A.只能被一个程序占用B.可以被多个程序同时占用C.可以被多个程序交替占用 D.可以被操作系统和另一个程序同时占用二、填空题1.计算机是由硬件系统和 系统组成。2,使计算机系统使用方便和 是操作系统的两个主要设计目标。3 .批处理操作系统、和实时操作系统是基本的操作系统。4 .用户要求计算机系统中进行处理的一个计算机问题称为 o5 .在多道操作系统控制下，允许多个作业同时装入 ,使中央处理器轮流地执行各个作业。6 .批处理操作系统提高了计算机系统的 ，但在作业执行时用户不能直接干预作业的执行。7 .在分时系统中

37、，每个终端用户每次可以使用一个由 规定的CPU时间。8 .分时系统具有同时性、独立性、及时性和 等特点。9 .若干个进程均因互相等待对方所占有的资源而无限地等待，使计算机系统无法继续正常运行的现象，称之为 010 .当多个进程需要对系统中的同一个数据块进行操作时，进程之间常用的通信方式有两种：当多 个进程共享数据块或其他排他性使用的资源时，不能同时进入存取或使用，这种称为 ;进程之间为了合作完成一个任务，而需要互相等待和互相交换信息的相互制约关系称为 三、简答题1 .计算机系统的资源包括哪些？2 .为计算机设计操作系统要达到什么目的 ？设计时应考虑哪些目标？3 .简述操作系统的五大功能。4 .

38、简述程序和进程的区别。5 .简述进程的三种状态及其转化过程参考答案第一章一、选择题DADDC二、填空题1. 列举法、归纳法、递推法、递归法、减半递推法2. 可行性、确定性3. O(n)24. O(n2)5. O(log2n)6. n、n(n+1)/2、O(n2)7. 1、log2n、n、n2、2n三、判断题X第二章一、选择题BDCDBD CABCA DBBBDCADB二、填空题1.顺序、链式、索引、散列2.7、593 .指针4 .后进先出、先进先出5 .栈6 .队尾7 .力口 1、减 1、c8 .层次、根9 . 2i-110 . 2k-111 .顺序、链式12 .根13 .主对角线14 . v

39、.elemk+1 = v.elemk;15 . v.last-;16 . s.top+;17 . s.top-;三、判断题vxxw xvxxxBCDCB CBADD BABABDBBDCxxvvx xvxw四、简答应用题1.出栈序列I口Z2132313212.操作序列TOI_OiIO1IOIIOOIIIOIOIIIOO行号域列号域值域14542114332343465445k1234POS2335NUM10213.前序遍De DEABC 中序遍历：EDBAC 后序遍历：DACBE5.0 110 010 0 11R=1 0 0 1 00 110 00 10 0 001 0 1 1-卜1 00 -

40、 1 1 3V = 1 1 - 101 2-1 1 3 1 2 0 -1 8 -1-1 018116 .答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算 机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之 间的关系在计算机中的表示。7 .答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链 表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。8 .答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外

41、，还要额外设置指针域，因此当线性表长度变化不大、 易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作 主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表， 宜采用链表作为存储结构。9 .答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度 的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。10 .答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为0(1)。11 .答：int number(Linkedlist *head)/计算单链表中结点的个数p=head >next；i=0 ；wh