第 2 章 基本线性结构
1.选择题
(1)A (2)A (3)D (4)C (5)C (6)B (7)C (8)B (9)A (10)D
(11)B (12)D (13)C (14)B (15)D (16)B (17)B (18)C (19)B (20)D
(21)C (22)C
2.判断题
(1)Ⅹ (2)√ (3)Ⅹ (4)√ (5)Ⅹ (6)√ (7)Ⅹ (8)√ (9)√ (10)Ⅹ
(11)Ⅹ(12)Ⅹ (13)√ (14)√ (15)√(16)Ⅹ (17)Ⅹ
3.简答题
1.循环队列的优点是什么?如何判别它的空和满?
循环队列的优点是能够克服“假溢满”现象。
设有循环队列 sq,队满的判别条件为:
(sq->rear+1)%maxsize==sq->front;或 sq->num==maxsize。
队空的判别条件为:
sq->rear==sq->front。
2.栈和队列数据结构各有什么特点,什么情况下用到栈,什么情况下用到队列?
栈和队列都是操作受限的线性表,栈的运算规则是“后进先出”,队列的运算规则是“先进先出”。栈
的应用如数制转换、递归算法的实现等,队列的应用如树的层次遍历等。
3.什么是递归?递归程序有什么优缺点?
一个函数在结束本函数之前,直接或间接调用函数自身,称为递归。例如,函数 f 在执行中,又调用
函数 f 自身,这称为直接递归;若函数 f 在执行中,调用函数 g,而 g 在执行中,又调用函数 f,这称为间
接递归。在实际应用中,多为直接递归,也常简称为递归。
递归程序的优点是程序结构简单、清晰,易证明其正确性。缺点是执行中占内存空间较多,运行效率
低。
4.设有编号为 1,2,3,4 的四辆车,顺序进入一个栈式结构的站台,试写出这四辆车开出车站的所有可
能的顺序(每辆车可能入站,可能不入站,时间也可能不等)。
1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321
二.算法设计题
1.设线性表存放在向量 A[arrsize]的前 elenum 个分量中,且递增有序。试写一算法,将 x 插入到线
性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构(顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定
将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储,分配的存储空间是固定大小的,
所以首先确定是否还有存储空间,若有,则根据原线性表中元素的有序性,来确定插入元素的插入位置,
后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位)然后插入 x ,最后修改表示表
长的变量。