《数据结构复习题及答案(12级)》由会员分享,可在线阅读,更多相关《数据结构复习题及答案(12级)(17页珍藏版)》请在金锄头文库上搜索。
1、一、选择题。(每小题 2 分,共 40 分)(1) 计算机识别.存储和加工处理的对象被统称为_A_ 。A.数据 B.数据元素 C.数据结构 D.数据类型(2) 数据结构通常是研究数据的_ A _及它们之间的联系。A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑(3) 不是数据的逻辑结构是_ A _。A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为,其中 D 是_ B _的有限集,R 是_ C _的有限集。A.算法 B.数据元素 C.数据操作 D.逻辑结构(5) 组成数据的基本单位是_ A _。 A.数据项 B.数据类型C.数据元素 D.数据变
2、量(6) 设数据结构 A=(D,R),其中 D=1,2,3,4,R=r,r=, ,则数据结构A 是_ A _。A.线性结构 B.树型结构 C.图型结构 D.集合(7) 数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为_ C _。A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为_ A _。A.内部结构与外部结构 B.静态结构与动态结构C.线性结构与非线性结构 D.紧凑结构与非紧凑结构(9) 对一个算法的评价,不包括如下_ B _方面的内容。A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度(10) 算法分
3、析的两个方面是_ A _。A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性(11) 线性表是具有 n 个_ C _的有限序列(n0)。A.表元素 B.字符 C.数据元素 D.数据项(12) 线性表的存储结构是一种_ B _的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.HASH 存取(13) 在一个长度为 n 的顺序表中,向第 i 个元素(1 i n)之前插入一个新元素时,需要向后移动_ B _个元素。A.n-i B.n-i+1 C.n-i-1 D.i(14) 链表是一种采用_ B _存储结构存储的线性表;A.顺序 B.链式 C.星式 D.
4、网状(15) 下面关于线性表的叙述错误的是_ D _。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现(16) 设指针 q 指向单链表中结点 A,指针 p 指向单链表中结点 A 的后继结点 B,指针 s 指向被插入的结点 X,则在结点 A 和结点 B 之间插入结点 X 的操作序列为_ B _。A. s-next=p-next;p-next=-s;B. q-next=s; s-next=p;C. p-next=s-next;s-next=p;D. p-nex
5、t=s;s-next=q;(17) 设指针变量 p 指向单链表结点 A,则删除结点 A 的后继结点 B 需要的操作为_ A _。A. p-next=p-next-next B. p=p-nextC. p=p-next-next D. p-next=p(18) 下列说法哪个正确?_ D _ A. 堆栈是在两端操作、先进后出的线性表B. 堆栈是在一端操作、先进先出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表(19) 栈和队列的共同点是 _ C _。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点(20) 栈与一般
6、线性表的区别主要在_D _。A、元素个数 B、元素类型 C、逻辑结构 D、插入、删除元素的位置(21) 链栈与顺序栈相比,比较明显的优点是_D _。A、插入操作更加方便 B、删除操作更加方便C、不会出现下溢的情况 D、不会出现上溢的情况(22) 以下数据结构中哪一个是非线性结构_ D _ 。A.队列 B.栈 C.线性表 D.二叉树 (23) 若已知一个栈的入栈序列是 1,2,3,n,其输出序列为 p1,p2,p3,pn,若 p1=n,则 pi 为 _ C _。A. i B. B. n=i C. n-i+1 D.不确定(24) 当利用大小为 N 的一维数组顺序存储一个栈时,假定用 top=N 表
7、示栈空,则向这个栈插入一个元素时,首先应执行 _ B _语句修改 top 指针。A. top+ B. top- C. top=0 D. top(25) 4 个元素进 S 栈的顺序是 A,B,C,D,经运算 POP(S)后,栈顶元素是_ C _。A. A B. B C. C D. D(26) 一个栈的输入序列是 a,b,c,d,e,则栈的不可能的输出序列是_ C _。A. edcba B. decba C. dceab D. abcde(27) 设输入序列是 1、2、3、n,经过栈的作用后输出序列的第一个元素是 n,则输出序列中第 i 个输出元素是_ C _。A. n-i B. n-1-i C.
8、 n+1-i D.不能确定(28) 字符 A、 B、C、D 依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成_ B _个不同的字符串?A. 15 B. 14 C. 16 D. 21(29) 设指针变量 top 指向当前链式栈的栈顶,则删除栈顶元素的操作序列为_ D _。A. top=top+1; B. top=top-1; C. top-next=top; D. top=top-next; (30) 设栈 S 和队列 Q 的初始状态为空,元素 E1、E2、E3、E4、E5 和 E6 依次通过栈 S,一个元素出栈后即进入队列 Q,若 6 个元素出列的顺序为 E2、E4、E3、E6、
9、E5 和 E1,则栈 S 的容量至少应该是_ C _。A. 6 B. 4 C. 3 D. 2(31) 若用一个大小为 6 的数组来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为 _ B _。A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1(32) 设顺序循环队列 Q0:M-1的头指针和尾指针分别为 F 和 R,头指针 F 总是指向队头元素的前一位置,尾指针 R 总是指向队尾元素的当前位置,则该循环队列中的元素个数为_ C _。A. R-F B. F-R C. (R-F+
10、M)%M D. (F-R+M)%M (33) 设指针变量 front 表示链式队列的队头指针,指针变量 rear 表示链式队列的队尾指针,指针变量 s 指向将要入队列的结点 X,则入队列的操作序列为 _ C _。A. front-next=s;front=s; B. s-next=rear;rear=s; C. rear-next=s;rear=s; D. s-next=front;front=s;(34) 如下陈述中正确的是_ A _。A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串(35) 下列关于串的叙述中,正确的是 _ D _。A.
11、串长度是指串中不同字符的个数 B. 串是 n 个字母的有限序列C. 如果两个串含有相同的字符,则它们相等 D. 只有当两个串的长度相等,并且各个对应位置的字符都相符时才相等(36) 字符串的长度是指_ C _。A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 (37) 两个字符串相等的充要条件是_ C _。A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等C. 同时具备(A)和(B)两个条件 D. 以上答案都不对(38) 串是一种特殊的线性表,其特殊性体现在_ B _ 。A. 可以顺序存储 B. 数据元素是一个字符C. 可以
12、链接存储 D. 数据元素可以是多个字符(39) 设有两个串 p 和 q,求 q 在 p 中首次出现的位置的运算称作 _ B _。A. 连接 B. 模式匹配 C. 求子串 D. 求串长(40) 设串 sI=ABCDEFG,s2=PQRST,函数 con(x,y)返回 x 和 y 串的连接串,subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串, len(s)返回串 s 的长度,则 con(subs(s1,2,1en(s2),subs(sl,len(s2) ,2)的结果串是_ D _。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF (41) 函数 substr(“DATASTRUCTURE”,5,9) 的返回值为_ A _。A. “STRUCTURE” B. “DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE”(42) 设串 S=”I AM A TEACHER!”,其长度是_ D _。A. 16 B. 11 C. 14 D. 15 (43) 假定在一棵二叉树中,双分支结点数为 15 个,单分支结点数为 32 个,则叶子结点数为_B_。 A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉树的结点数为 18 个,则它的