《软件技术基础》练习题
太原理工大学现代科技学院2016
1
第一章 算法
一、选择题
1. 算法的复杂度包括【 】。
A、时间复杂度 B、空间复杂度
C、时间及空间复杂度 D、以上都不对
2. 若x在长度为n的无序线性顺序表中的概率为50%，则在该表中查找x的平均查找次数（平均性态分析）为【 】。
A、(n*3+1)/4 B、(n-1)/2 C、(n+1)/2 D、(n+1)*n/2
3. 若x在长度为n的无序线性顺序表中的概率为50%，则在该表中查找x的最坏情况分析为【 】。
A、n/2 B、(n-1)/2 C、(n+1)/2 D、n
4. 已知基本运算执行次数与n的关系，则下列哪个时间复杂度最大：【 】。
A. f(n) = 1 B. f(n) = 2n - 1
C. f(n) = 10000n+10000 D. f(n) = n2-10000
5. 算法分析的目的是【 】。
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；
2
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. 算法和程序没有区别，所以在数据结构中二者是通用的。
3
第二章 基本数据结构及其运算
一、选择题
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. 1243 B. 2134 C. 1432 D. 4312
4. 设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是【 】。 A．2 B．3 C．5 D．6
5. 线性表若采用链表存储结构，要求内存中可用存储单元的地址【 】。
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. 2008 B. 2000 C. 2004 D. 2012
8. 下列关于二叉树的叙述中，正确的是【 】。
A. 叶子结点总是比度为2的结点少一个 B. 叶子结点总是比度为2的结点多一个 C. 叶子结点数是度为2的结点数的两倍
D. 度为2的结点数是度为1的结点数的两倍
9. 某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【 】。
A. 10 B. 8 C. 6 D. 4
10. 一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为【 】。
A. 16 B. 10 C. 6 D. 4
11. 某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层) 【 】。
A. 3 B. 4 C. 6 D. 7
12. 某二叉树有7个度为2的结点，则该二叉树中的叶子结点数是【 】
A.10 B.8 C.4 D.6 13. 一棵深度为k的满二叉树中结点的个数是【 】
A. 2k B. 2k -1 C. 2k-1 D. 2k-1-1
4
相关推荐：
loading