第一章作业一、选择题1.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为( )。

A. 规则B. 结构C. 集合D. 运算2.在Data_Structure=(D,S)中，D是( )的有限集合。

A. 数据元素B. 算法C. 数据操作D.数据对象3.计算机所处理的数据一般具有某种关系，这是指( )之间存在的某种关系。

A. 数据与数据B. 数据元素与数据元素C. 元素内数据项与数据项D. 数据文件内记录与记录4.顺序存储表示中数据元素之间的逻辑关系是由( )表示的。

A. 指针B. 逻辑顺序C. 存储位置D. 问题上下文5.链接存储表示中数据元素之间的逻辑关系是由( )表示的。

A. 指针B. 逻辑顺序C. 存储位置D. 问题上下文6.从逻辑上可将数据结构分为( )。

A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 内部结构和外部结构D. 线性结构和非线性结构7.以下选项属于线性结构的是( )。

A. 广义表B. 二叉树C. 串D. 稀疏数组8.以下选项属于非线性结构的是( )。

A. 广义表B. 队列C. 优先队列D. 栈9.以下属于逻辑结构的是( )A. 顺序表B. 散列表C. 有序表D. 单链表10.一个完整的算法应该具有( )等特性。

A. 可执行性、可修改性和可维护性B. 可行性、确定性和有穷性C. 确定性、有穷性和可靠性D. 正确性、可读性和有效性11.若一个问题既可以用迭代方法也可以用递归方法求解，则( )的方法具有更高的时空效率。

A. 迭代B. 递归C. 先递归后迭代D. 先迭代后递归12.一个递归算法必须包括( )A. 递归部分B. 终止条件和递归部分C. 迭代部分D. 终止条件和迭代部分13.算法的时间复杂度与( )有关。

A. 问题规模B. 源程序长度C. 计算机硬件运行速度D. 编译后执行程序的质量二、指出下列各算法的功能并求出其时间复杂度。

(1)int Prime(int n){int i=2,x=(int)sqrt(n); //sqrt(n)为求n的平方根while(i<=x){if(n%i==0)break;i++;}if(i>x) return 1;else return 0;}(2)int sum1(int n){int p=1,s=0;for(int i=1;i<=n;i++){p*=i;s+=p;}return s;}(3)int sum2(int n){int s=0;for(int i=1;i<=n;i++){int p=1;for(int j=1;i<=i;j++) p*=j;s+=p;}return s;}(4)int fun(int n){int i=1,s=1;while(s<n) s+=++i;return i;}(5)void mtable(int n){for(int i=1;i<=n;i++){for(int j=i;j<=n;j++)cout<<i<<"*"<<j<<"="<<setw(2)<<i*j<<" ";cout<<endl;}}第二章作业一、选择题1. 在线性表中的每一个表元素都是不可再分的( )A. 数据项B. 数据记录C. 数据元素D. 数据字段2. 顺序表是线性表的( )存储表示。

A. 有序B. 连续C. 数组D. 顺序存取3. 若长度为n 的非空线性表采用顺序存储结构，在表中的第i 个位置插入一个数据元素，i 的合法值应该是( )A. n i ≤≤1B. 11+≤≤n iC. 10-≤≤n iD. n i ≤≤04. 若设一个顺序表的长度为n ，那么，在表中顺序查找一个值为x 的元素时，在等概率的情况下，查找成功的数据平均比较次数为( )A. nB. 2/nC. 2/)1(+nD. 2/)1(-n5. 在长度为n 的顺序表的表尾插入一个新的元素的时间复杂度为( )A. )(n OB. )1(OC. )(2n OD. )(log 2n O6. 数据结构反映了数据元素之间的结构关系。

单链表是一种( )。

A. 顺序存储线性表B. 非顺序存储非线性表C. 顺序存储非线性表D. 非顺序存储线性表7. 单链表又称为线性链表，在单链表上实施插入和删除操作( )A. 不需移动结点，不需改变结点指针B. 不需移动结点，只需改变结点指针C. 只需移动结点，不需改变结点指针D. 既需移动结点，又需改变结点指针8. 已知L 是带头结点的单链表，则删除首元素结点的语句是( )A. L=L->next;B. L->next=L->next->next;C. L=L->next->next;D. L->next=L;9. 已知单链表A 长度为m ，单链表B 长度为n ，若将B 链接在A 的末尾，在没有链尾指针的情况下，算法的时间复杂度应为( )。

A. )1(OB. )(m OC. )(n OD. )(n m O +10. 给定有n 个元素的一维数组，建立一个有序单链表的时间复杂度是( )A. )1(OB. )(n OC. )(2n OD. )log (2n n O二、算法设计1. 设计一个算法，从顺序表L 中(SqList L)删除具有给定值x(ElemType x)的所有元素。

2. 设计一个算法，从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

3. 设计一个算法，在非递减有序的带头结点的单链表中删除值相同的多余结点。

第三章作业一、选择题1. 用S 表示进栈操作，用X 表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S 和X 的操作序列为( )A. SXSXSSXXB. SSSXXSXXC. SXSSXXSXD. SXSSXSXX2. 假设一个栈的输入序列是1，2，3，4，则不可能得到的输出序列是( )A. 1,2,3,4B. 4,1,2,3C. 4,3,2,1D. 1,3,4,23. 已知一个栈的进栈序列为1,2,3,…,n ，其输出序列的第一个元素是i ，则第j 个出栈元素是( )。

A. i j -B. i n -C. 1+-i jD. 不确定4. 已知一个栈的进栈序列为n ,,3,2,1Λ，其输出序列是n p p p p ,,,,321Λ。

若n p =1，则i p 的值是( )A. iB. i n -C. 1+-i nD. 不确定5. 已知一个栈的进栈序列为n ,,3,2,1Λ，其输出序列是n p p p p ,,,,321Λ。

若31=p ，则2p 的值是( )A.一定是2B. 一定是1C.可能是1D. 可能是26. 已知一个栈的进栈序列为n p p p p ,,,,321Λ，其输出序列是n ,,3,2,1Λ。

若13=p ，则1p 的值是( )A.一定是2B. 可能是2C.不可能是2D. 一定是37. 已知一个栈的进栈序列为n p p p p ,,,,321Λ，其输出序列是n ,,3,2,1Λ。

若33=p ，则1p 的值是( )A.一定是2B. 可能是2C.不可能是1D. 一定是18. 已知一个栈的进栈序列为n p p p p ,,,,321Λ，其输出序列是n ,,3,2,1Λ。

若1=n p ，则1p 的值是( )A. 1+-i nB. i n -C. iD. 不确定9. 设栈S 和队列Q 的初始状态均为空，元素1,2,3,4,5,6,7，依次进入S 。

如果每个元素出栈后立即进入队列Q ，且7个元素的出队顺序为2,4,3,6,5,1,7，则栈S 的容量至少是( )A. 1B. 2C. 3D. 410.对中缀表达式53--++求值，在求值过程中扫描到6时，操作数栈和操作符栈的内4(*2*26)32*容分别是( )A. 3,2,4,2,2和+,*,(,+,*B. 3,2,4,4和+,*,(,+C. 3,2,8和+,*,(D. 3,2,8,6和+,*,(,-二、算法设计题1. 详见《数据结构题集(C语言版)》第25页3.24。

2. 详见《数据结构题集(C语言版)》第25页3.25。

第四章作业11.串是一种特殊的线性表，其特殊性体现在( )A. 可以顺序存储B. 数据元素是一个字符C. 可以链式存储D. 数据元素可以是多个字符12.设有两个串T和P，求P在T中首次出现的位置的运算叫做( )。

A. 求子串B. 模式匹配C. 串替换D. 串连接13.下面关于串的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储14.串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数15.两个串相等的充分必要条件是（）A．串中所含的字符相同B．串中所含字符的个数相同，且对应位置上的字符也相同C．串中所含的字符个数相同D．串中对应位置上的字符相同6. 已知p=”abcaabbabcabaacbacb”，求出next函数值。

第五章作业一、选择题16. 数组通常具有的操作是( )A. 顺序存取B. 直接存取C. 散列存取D. 索引存取17. 多维数组实际上是由( )实现的。

A. 一维数组B. 多项式C. 三元组表D. 简单变量18. 在二维数组A[8][10]中，每一个数组元素A[i][j]占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是( )。

A. 80B. 100C. 240D. 27019. 一个二维数组A[10][20]按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为( )A. 226B. 322C. 341D. 34220. 一个二维数组A[10][20]按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为( )A. 226B. 322C. 341D. 34221. 在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA 开始按行连续存放，在这种情况下，元素A[8][5]的起始地址为( )A. SA+141B. SA+144C. SA+222D. SA+25522. 将一个n n ⨯的对称矩阵A 的下三角部分按存放在一个一维数组B 中，A[0][0]存放在B[0]中，那么第i 行的对角元素A[i ][i ]在B 中的存放位置是( )A. 2/)3(i i +B. 2/)1(i i +C. 2/)12(i i n +-D. 2/)12(i i n --23. 将一个n n ⨯的对称矩阵A 的上三角部分按存放在一个一维数组B 中，A[0][0]存放在B[0]中，那么第i 行的对角元素A[i ][i ]在B 中的存放位置是( )A. 2/)3(i i +B. 2/)1(i i +C. 2/)12(i i n +-D. 2/)12(i i n --24. 设A 是一个n n ⨯的对称矩阵，将A 的对角线及对角线上方的元素以列优先(以列为主序)的方式存放在一维数组]2/)1([+n n B 中，则矩阵中任一元素),,0(j i n j i a ij ≤<≤在B 中的存放位置是( )A. i j j ++2/)1(B. 12/)1(-+-i j jC. j i i ++2/)1(D. 12/)1(-+-j i i25. 设n 阶三对角矩阵A 的三条对角线上的元素被按行压缩存储到一维数组B 中，A[0][0]存放于B[0]。