《软件技术基础》练习题
太原理工大学现代科技学院2016
第一章 算法
一、选择题
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；
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. 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 14. 在以下的叙述中，正确的是【 】。
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+1
19. 在含有n个结点的顺序存储的线性表中，删除第i个结点所需移动结点的次数为【 】。 A．n/2 B．i C．n-i D．n-i+1
20. 在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为【 】。
A．n B．n/2 C．(n-1)/2 D．(n+1)/2
21. 在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为【 】。 A．n B．n/2 C．(n-1)/2 D．(n+1)/2 22. 带头结点的单链表为空的条件是【 】。
A．head=NULL B．head->next=NULL C．head->next=head D．head!=NULL 23. 在一个单链表中，若删除*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．6
27. 二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是【 】。
A．1208 B．1212 C．1368 D．1364
2016现代科技学院《软件技术基础》练习题+答案
