广工2015数据结构复习题目及答案.doc

1、1数据结构-C 语言版第一章 绪论单项选择题1在数据结构中，数据的基本单位是_ _。A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2数据结构中数据元素之间的逻辑关系被称为_ _。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3在数据结构中，与所使用计算机无关的是数据的_ _。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 4在链式存储结构中，数据之间的关系是通过_ _体现的。A. 数据在内存的相对位置 B. 指示数据元素的指针C. 数据的存储地址 D. 指针5计算算法的时间复杂度是属于一种_ _。A. 事前统计的方法

2、 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法6在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_ _。 A. n2 B. nlogn C. n D. logn 7设使用某算法对 n 个元素进行处理，所需的时间是 T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_ _。A. O(1) B. O(n) C. O(200n) D. O(nlog2n)2CDCBBDD第二章 线性表单项选择题1链表不具有的特点是_ _。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素C. 不必事先估计存储空间 D. 所需空间与线性表的长度正

3、比 2设顺序表的每个元素占 8 个存储单元。第 1 个单元的存储地址是 100，则第 6 个元素占用的最后一个存储单元的地址为 。A. 139 B. 140 C. 147 D. 1483在线性链表存储结构下，插入操作算法 。A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4在一个单链表中，若删除 p 所指结点的后继结点，则执行 。 A. p-next = p-next-next; B. p-next = p-next; C. p = p-next-next; D. p = p-next; p-next = p-next-next; 5将长度为

4、 n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 。 A. O(n) B. O(1) C. O(m) D. O(m+n)6需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是 。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB填空题1在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_结点。2在单链表中，指针 p 所指结点为最后一个结点的条件是 。3将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是 。 4在一个长度为 n 的顺序表中第 i 个元素（1i n）之前插入一个元素时，需向后移动元素的个数是 。5在长度

5、为 n 的顺序表中插入一个元素的时间复杂度为 。1 前驱 2 p-next=NULL33.14.n-i+15.O(n)例题解析【 例 2-1】 编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下：void inverse(Lnode *h)s=h-next;if(s=NULL) return;q=NULL;p=s;while(p!=NULL) p=p-next;s-next=q; /*逆转指针*/q=s; /*指针前

6、移*/s=p;h-next=q; /*头指针 h 的后继是 p*/【 例 2-2】 编写一算法将两个按元素值递增有序排列的单链表 A 和 B 归并成一个按元素值递增有序排列的单链表 C。解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入 c 表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到 c 表尾。设 pa、pb 分别指向两表当前结点，p 指向 c 表的当前表尾结点。若设 A 中当前所指的元素为 a，B 中当前所指的元素为 b，则当前应插入到 C 中

7、的元素 c 为ac例如：A=(3,5,8,11)B=(2,6,8,9,11,15,20)则 C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下：Lnode *hb(Lnode *pa,Lnode *pb)Lnode *p,*q,*pc;4pc=(Lnode*)malloc(sizeof(Lnode); /*建立表 c 的头结点 pc*/p=pc; /*p 指向 C 表头结点*/while(pa!=NULL /*建立新结点 q*/if(pb-datadata) /*比较 A、B 表中当前结点的数据域值的大小*/q-data=pb-data; /*B 中结点值小，将其

8、值赋给 q 的数据域*/pb=pb-next; /*B 中指针 pb 后移*/elseq-data=pa-data; /*相反，将 A 结点值赋给 q 的数据域*/pa=pa-next; /*A 中指针 pa 后移*/p-next=q; /*将 q 接在 p 的后面 */p=q; /*p 始终指向 C 表当前尾结点 */while(pa!=NULL) /*若表 A 比 B 长，将 A 余下的结点链在 C 表尾*/q=(Lnode*)malloc(sizeof(Lnode);q-data=pa-data;pa=pa-next;p-next=q;p=q;while(pb!=NULL) /*若表 B

9、 比 A 长，将 B 余下的结点链在 C 表尾*/q=(Lnode*)malloc(sizeof(Lnode);q-data=pb-data;pb=pb-next;p-next=q;p=q;p-next=NULL;p=pc; /*p 指向表 C 的头结点 pc*/pc=p-next; /*改变指针状态，使 pc 指向 p 的后继*/free(p); /*释放 p 空间*/return (pc); 此算法的时间复杂度为 O(m+n)，其中 m，n 分别是两个被合并表的表长。5第三章 栈和队列单项选择题1在初始为空的堆栈中依次插入元素 f，e，d，c，b，a 以后，连续进行了三次删除操作，此时栈顶

10、元素是 。A. B. C. D. 2若某堆栈的输入序列是 1，2，3，.，n，输出序列的第一个元素为 n，则第 i 个输出元素为 。A. i B. n-i C. n-i+1 D. 哪个元素无所谓3向一个栈顶指针为 h 的带头结点链栈中插入指针 s 所指的结点时，应执行 。A. h-next = s; B. s-next = h; C. s-next = h; h = h-next; D. s-next = h-next; h-next=s; 4一个栈的入栈序列是 a，b，c，d，e ，则栈的不可能的输出序列是 。A. edcba B. decba C. dceab D. abcde5栈和队列的

11、共同点是 。A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点6对于循环队列 。A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是7. 若用一个大小为 6 的数组来实现循环队列，且当前队尾指针 rear 和队头指针 front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为 。A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 18. 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是 。A. QU-front=QU-rear

12、B. QU-front!=QU-rearC. QU-front=(QU-rear+1) % m0 D. QU-front!=(QU-rear+1) % m0 9.判定一个循环队列 QU（最多元素为 m0）为空的条件是 。A. QU-front=QU-rear B. QU-front!=QU-rear C. QU-front=(QU-rear+1) % m0 D. QU-front!=(QU-rear+1) % m0 BCDCCDACA填空题1在求表达式值的算符优先算法中使用的主要数据结构是 。2设有一个空栈，现输入序列为 1，2，3，4，5。经过push，push，pop，push ，pop，

13、push，pop，push 后，输出序列是 。3仅允许在同一端进行插入和删除的线性表称为 。67在顺序栈 s 中，栈为空的条件是 ，栈为满的条件是_。4用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1234，为了得到 1342 出栈顺序，相应的 S、X 操作串为 。5用一个大小为 1000 的数组来实现循环队列，当前 rear 和 front 的值分别为 0 和 994，若要达到队满的条件，还需要继续入队的元素个数是 。1.栈2. 2 3 43.栈4.s.top=s.base, s.top-s.base=s.stacksize SXSSXSXX5.993例题解析【 例 3-1】 编

14、程实现：用除法把十进制数转换成二进制数。 解：算法思想：用初始十进制数除以 2 把余数记录下来并且若商不为 0 则再用商去除以 2 直到商为 0，这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）就得到了相应的二进制数，如把十进制数 35 转换成二进制数的过程如图 3-1 所示。图 3-1 十进制数转换成二进制数的过程由题意可知，我们可以用一个栈来保存所有的余数，当商为 0 时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下：void conversion()Stack S; int n; InitStack( printf(“Input a nu

15、mber to convert:n“);scanf(“%d“, 35178421011001余数 结果：100117if(n0) printf(“nThe number must be over 0.“); return;if(n=0) Push(S,0); while(n!=0) Push(S,n%2); n=n/2; printf(“the result is: “); while(!StackEmpty(*S) printf(“%d“, Pop(S);第四章 串单项选择题1串是一种特殊的线性表，其特殊性体现在 。A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据

16、元素可以是多个字符 2设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作 。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长3串是一个 B 的序列。A. 不少于一个字母 B. 有限个字符 C. 不少于一个字符 D. 空格或字母 4已知串 s=ABCDEFGH，则 s 的所有不同子串的个数为 。A. 8 B. 9 C. 36 D. 37BBBD填空题1两个串相等的充分必要条件是 。2空格串是 ,其长度等于 。3在串 S=tuition中，以 t 为首字符且值不相同的子串有 个。84. 使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2

17、)的串操作，可从串 s=conduction中的字符得到串 t=cont，则求 t 的串表达式为 。1.两个串的长度相等且对应位置的字符相同2.由一个或多个空格字符组成的串 其包含的空格个数3. 10 4. concat(subString(s,1,3),substring(s,7,1)第五章 数组与广义表单项选择题1常对数组进行的两种操作是 。A. 建立与删除 B. 索引和修改 C. 查找和修改 D. 查找与索引 2假设 8 行 10 列的二维数组 a1.8, 1.10分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素 a35的地址与以列序为主序时元素 _ _的地

18、址相同。A. a53 B. a83 C. a14 D. 答案 A、B、C 均不对 3将一个 A1.100,1.100的三对角矩阵以行序为主序存入一维数组 B1.298中，元素A66， 65在 B 数组中的位置 k 等于_ _。A. 198 B. 197 C. 196 D. 1954稀疏矩阵一般的压缩存储方法有两种，即 。 A. 二维数组和三维数组 B. 三元组和散列C. 三元组和十字链表 D. 散列和十字链表5. 一个非空广义表的表头_ _。A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是原子或子表6. 设 head(L)、tail(L)分别为取广义表表头、表尾操作，则从广

19、义表 L=(x,y,z),a,(u,v,w)中取出原子 u 的运算为_ _。A. head(tail(tail(head(L) B. tail(head(head(tail(L)C. head(tail(head(tail(L) D. head(head(tail(tail(L)7广义表(a,(b,(c,d,(e,f),g)的深度为_ _。A. 3 B. 4 C. 5 D. 6CDDCDDC填空题1将下三角矩阵 A1.8,1.8的下三角部分逐行地存储到起始地址为 1000 的内存单元中，已知每个元素占四个单元，则元素 A7,5的地址为 。 2二维数组 A0.9,0.19采用行序为主方式存储，每

20、个元素占一个存储单元，并且元素9A0,0的存储地址是 200，则元素 A6,12的地址是 。 3二维数组 A10.20,5.10采用行序为主方式存储，每个元素占 4 个存储单元，并且元素A10,5的存储地址是 1000，则元素 A18,9的地址是 。4有一个 10 阶对称矩阵 A，采用压缩存储方式（以行序为主序存储，且元素 A0,0地址为 1） ，则元素 A8,5的地址是 。5设 HAEDp为求广义表 p 的表头函数，TAILp为求广义表 p 的表尾函数，其中是函数的符号，给出下列广义表的运算结果： HEAD(a，b，c)的结果是 。 TAIL(a，b，c) 的结果是 。 HEAD(a)，(b

21、)的结果是 。 TAIL(a)，(b)的结果是 。 HEADTAIL(a，b，c)的结果是 。TAILHEAD(a，b)，(c，d)的结果是 。 HEADHEAD(a，b)，(c，d)的结果是 。 TAILTAIL(a， (c，d)的结果是 。 a；(b ，c) ； (a)；(b) ；b；(b) ；a ；( )1. 11002. 3323. 12084. 42 5. 第 6 章 树和二叉树选择题1 以下说法错误的是 。A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种“分支层次“结构2

22、. 如图 6-2 所示的 4 棵二叉树中， 不是完全二叉树。10图 6-2 4 棵二叉树3. 以下说法错误的是 。A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好4. 如图 6-3 所示的 4 棵二叉树， 是平衡二叉树。图 6-3 4 棵二叉树5. 如图 6-4 所示二叉树的中序遍历序列是 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagcbacd gef图 6-4 1 棵二叉树6. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 。