数据结构基本复习题答案.doc

《数据结构基本复习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章绪论1自测习题二、选择题1．以下数据结构中，属于线性结构的是(B)A）有向图B）串C）线索二叉树D）B树2．下列与数据元素有关的叙述中错误的是(A)A）数据元素是有独立含义的数据最小单位B）数据元素是描述数据的基本单位C）数据元素可以称做结点D）数据元素可以称做记录3．以下术语中与数据的存储结构无关的是(A)A）栈B）散列表C）顺序表D）双链表4．以下数据结构中，属于线性结构的是(B)A）有向图B）串C）线索二叉树D）B树三、填空题1．数据结构包括的三方面容分别是：数据的逻辑结构、数据的存储结构和数据的运算。2．数据元素是数据的基本单位，在某些情况下也可

2、以称为结点、记录和顶点。3．数据逻辑结构的4种基本形态包括集合结构、线性结构、树型结构和图（网）结构。4．一个正确的算法应该具有5个特性：输入、输出、确定性、可行性和有穷性。5．数据的存储结构包括顺序、链式、索引和散列四种。6．一个数据结构在计算机中的映象称为存储结构。7．一个算法的效率主要是指该算法的时间效率和空间效率。8．以下程序段的时间复杂度T（n）=______。sum=0;for(i=0;i

3、从当前结点出发能够访问到任一结点的是（B）A）单向链表和双向链表B）双向链表和循环链表C）单向链表和循环链表D）单向链表、双向链表和循环链表2．线性表是具有n个(B)的有限序列。A）数据项B）数据元素C）表元素D）字符3．若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为(B)A）O(1)B）O(n)C）O(n2)D）O(log2n)4．在长度为n的顺序表中，若要删除第i（1≤i≤n）个元素，则需要向前移动的元素的次数为(B)A）iB）n-iC）n-i+1D）n-i-15．在长度为n的顺序表中第i（1≤i≤n）个位置上插入一个元素时，为留出

4、插入位置所需移动元素的次数为(C)A）n-iB）iC）n-i+1D）n-i-1三、填空题1．有一单链表结构如下：……datalinkBCDp图2-1填空题1附图若要删除值为c的结点，应做的操作是p->link=p->link->link。2．线性表L=(a1,a2,…an)用数组存储。假定删除表中任一元素的概率相同，则删除一个元素平均需要移动的元素个数是(n-1)/2。3．设有结点定义structnode{intdata;structnode*next;};且已建立如图2-2所示的带有头结点的单向链表：…head头^datanext图2-2填空题3附图函数su

5、m的功能是：计算链表中各结点数据域之和，作为函数值返回。请填空。intsum(structnode*head){ints=0;structnode*p;p=head->next;do{s=s+p->data;p=p->next;}while(p!=NULL);returns;}第3章栈和队列3自测习题二、选择题1．有6个元素按6、5、4、3、2、1的顺序进栈，进栈过程中可以出栈，则以下可能的出栈序列是（B，D）A）1、4、3、5、2、6B）6、5、4、3、2、1C）3、1、4、2、6、5D）5、6、3、4、2、12．栈和队列都是（C）A）顺序存储的线性结构B）

6、链式存储的线性结构C）限制存取点的线性结构D）限制存取点的非线性结构3．设循环队列的队首指针用front表示，队尾指针用rear表示，则判断队空的条件是（A）A）front==rearB）front+1=rearC）rear+1=frontD）rear==04、设有中缀算术表达式：15–3*（7+2）,其对应的后缀算术表达式为（B）A）153-72+*B）15372+*-C）153*72+D）153-*72+三、填空题1．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其操作特点是先进先出。2．设有一个空栈，栈顶指针值为100，现有输入序列为1，

7、2，3，4，5，经过操作序列：Push、Pop、Push、Push、Pop、Push、Push、Pop后，现在已出栈的序列是1、3、5，栈顶指针是102。3．设有后缀算术表达式：2xy+*3y-/，其对应的中缀表达式为2*(x+y)/(3-y)。4．已知一算术表达式的中缀形式为：(a+b)-(b+c)/2，其对应的前缀表达式形式应为-+ab/+bc2。第4章串4.1自测习题一．选择题1．设有一个字符串S=“ABC123XYZ”，问该串的长度为（C）A）9B）10C）11D）122．设有一个字符串S=”windows”，其子串的数目是(29个)A）25个B）26

8、个C）27个D）28个3．串是一种特殊