《软件技术基础》练习题太原理工大学现代科技学院2016第一章算法一、选择题1. 算法的复杂度包括【】。

A、时间复杂度B、空间复杂度C、时间及空间复杂度D、以上都不对2. 若x在长度为n的无序线性顺序表中的概率为50%，则在该表中查找x的平均查找次数（平均性态分析）为【】。

A、(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) = 2n - 1C. f(n) = 10000n+10000D. f(n) = n2-100005. 算法分析的目的是【】。

A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性二、填空题1. 常用算法包括_________、_________、_________、_________、_________和回溯法。

2. 算法的基本特征有_________、_________、有穷性、输入和输出。

3. 下列程序段的时间复杂度是____。

for (i=1；i<=n；i++)A[i，i]=0；4.下列程序段的时间复杂度是____s=0；for(i=1；i<=2n；i++)for(j=1；j<=n；j++)s=s+B[i][j]；sum=s；5. 下列程序段的时间复杂度是____i=1；while (i<=n)i=i*2；6. 在下面的程序段中，s= s + p；语句的执行次数为_________，p= p×j语句的执行次数为_________ ，该程序段的时间复杂度为________ 。

int i=0, s=0, p=1;while( ++i<=n ){for(j=1; j<=i; j++ )p = p×j;s = s + p;}7. 常见时间复杂度的量级有：常数阶O(_________)、对数阶O(_________)、线性阶O(_________)、平方阶O(_________)和指数阶O(_________)。

三、判断题1. 算法和程序没有区别，所以在数据结构中二者是通用的。

第二章基本数据结构及其运算一、选择题1. 数据结构的逻辑结构被形式地定义为(D，R)，其中D是【（1）】的有限集合，R是D上【（2）】的有限集合。

(1) A．算法B．数据元素C．数据操作D．逻辑结构(2) A．操作B．映像C．存储D．关系2. 在数据结构中，从逻辑上可以把数据结构分为【】。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构3 设进栈的输入序列是1,2,3,4，则【】不可能是其出栈序列。

A. 1243B. 2134C. 1432D. 43124. 设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是【】。

A．2 B．3 C．5 D．65. 线性表若采用链表存储结构，要求内存中可用存储单元的地址【】。

A．必须是连续的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-> 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. 6D. 411. 某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层) 【】。

A. 3B. 4C. 6D. 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．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．数据结构是带有结构的数据元素的集合16. 线性表L=(a1，a2，…，ai，…，an)，下列说法正确的是【】。

A．每个元素都有一个直接前驱和直接后继B．线性表中至少要有一个元素C．表中诸元素的排列顺序必须是由小到大或由大到小的D．除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17. 对于顺序线性表的优缺点，以下说法错误的是【】。

A．无需为表示结点间的逻辑关系而增加额外的存储空间B．可以方便地随机存取表中的任一结点C．插入和删除操作较方便D．由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)18. 在含有n个结点的顺序存储的线性表中，在任一结点i前插入一个结点所需移动结点的次数为【】。

A．n/2 B．i C．n-i D．n-i+119. 在含有n个结点的顺序存储的线性表中，删除第i个结点所需移动结点的次数为【】。

A．n/2 B．i C．n-i D．n-i+120. 在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为【】。

A．n B．n/2 C．(n-1)/2 D．(n+1)/221. 在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为【】。

A．n B．n/2 C．(n-1)/2 D．(n+1)/222. 带头结点的单链表为空的条件是【】。

A．head=NULL B．head->next=NULL C．head->next=head D．head!=NULL23. 在一个单链表中，若删除*p结点的后继结点，则执行【】。

A．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. 循环链表的主要优点是【】。

A．不再需要头指针了B．已知某个结点的位置后，容易找到它的直接前驱C．在进行插入、删除操作时，能更好地保证链表不断开D．从表中任一结点出发都能扫描到整个链表25. 在线性表的下列存储结构中，读取元素花费时间最少的是【】。

A．单链表B．双链表C．循环链表D．顺序表26. 设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为a2,a4,a3,a6,a5,a1，则栈S的容量至少应该为【】。

A．2 B．3 C．5 D．627. 二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是【】。

A．1208 B．1212 C．1368 D．136428. 对矩阵压缩存储是为了【】。

A．方便运算B．节省空间C．方便存储D．提高运算速度29. 以下说法错误的是【】。

A．树形结构的特点是一个结点可以有多个直接前驱B．线性结构中的一个结点至多只有一个直接后继C．二叉树与树是两种不同的数据结构D．树(及一切树形结构)是一种“分支层次’结构30. 以下说法错误的是【】。

A．二叉树可以是空集B．二叉树的任一结点都有两棵子树C．二叉树与树具有相同的树形结构D、二叉树中任一结点的两棵子树有次序之分31. 一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。

现采用【】遍历方式就可以得到这棵二叉树所有结点的递减序列。

A．前序B．中序C．后序D．层次32. 对含有【】个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A．0 B．1 C．2 D．不存在这样的二叉树33. 已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是【】。

A．acbed B．baedc C．dceab D．cedba34. 某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是【】。

A．bdgcefha B．gdbecfha C．bdgechfa D．gdbehfca35. 在图6-2中的二叉树中，【】不是完全二叉树。

36. 树最适合用来表示【】。

A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据37. 在计算递归函数时，如不使用递归过程，则一般情况下必须借助于【】数据结构。

A．栈B．树C．双向队列D．顺序表38. 对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【】。

A．N B．(N-1)*(N-1) C．N-1 D．N*N39. 以下说法错误的是【】。

A．用邻接矩阵法存储图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关B．邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用C．存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下(或上)三角部分D．用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可二、填空题1. 通常，数据在计算机中的存储结构有_____存储结构、______存储结构、______存储结构和_____存储结构四种基本存储结构。