《数据结构(线性表习题含答案)》由会员分享，可在线阅读，更多相关《数据结构(线性表习题含答案)（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构第二章线性表习题含答案说明：顺序存储的线性表称为向量。一,单项选择题一个向量第一个元素的地址是 100，每个元素的长度为 2，则第 5 个元素的 地址是_B_。 A) 110 B) 108 C) 100 D) 120 线性结构通常采用的两种存储结构是_A_。 A) 顺序存储结构和链式存储结构 B) 散列方式和索引方式 C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构不带头结点的单链表 head 为 空的判定条件是_A_. A) head=NULL B) head-next=NULL C) head-next=head D) head!=NULL 带头结点的单链表 head
2、为空的判定条件是_B_。 A) head=NULL B) head-next=NULL C) head-next=head D) head!=NULL 非空的循环链表 head 的尾结点（由 p 所指向）满足_C_。 A) p-next=NULL B) p=NULL C) P-next=head D) p=head 在循环双链表的 p 所指结点之后插入 s 所指结点的操作是_C_。 A) p-right=s; s-left=p; p-right-left=s; s-right=p-right; B) p-right=s; p-right-left=s; s-left=p; s-right=p-
3、right; C) s-left=p; s-right=p-right; p-right=s; p-right-left=s; D) s-left=p; s-right=p-right; p-right-left=s; p-right=s; 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点, 则执行_c_。 A) s-next=p-next; p-next=s; B) p-next=s-next; s-next=P; C) q-next=s; s-next=p; D) p-next=s; s-next=q; 在一个单链表中，若 p 所指结点不是
4、最后结点，在 p 之后插入 s 所指结点，则执行_b_。 A) s-next=p; p-next=s; B) s-next=p-next; p-next=s; C) s-next=p-next; p=s; D) p-next=s; s-next=p; 在一个单链表中，若删除 p 所指结点的后续结点，则执行_a_。 A) p-next=p-next-next; B) p=p-next; p-next=p-next-next; C) p-next=p-next; D) p=p-next-next; 10,假设双链表结点的类型如下： typedef struct linknode int data,
5、/*数据域*/ struct linknode * llink; /*llink 是指向前驱结点的指针域*/ struct linknode * rlink; /*rlink 是指向后续结点的指针域*/ bnode 要把一个 q 所指新结点作为非空双向链表中的 p 所指结点的前驱结点插入到该双链表中， 其算法是_c_。 q-rlink=p; q-llink=p-llink; p-llink=q; p-llink-rlink=q; p-llink=q; q-llink=p; p-llink-rlink=q; q-llink=p-llink; q-llink=p-llink; q-rlink=p;
6、 p-llink-rlink=q; p-llink=q; 以上都不对, 12,从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均 比较_d_个结点。 A) n B) n/2 C) (n-1)/2 D) (n+1)/2 一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_b_。 A) O(1) B) O(n) C) O(n2) D) O(nlog2n) 给定有 n 个元素的向量，建立一个有序单链表的时间频度是_d_。 A) n B) n/2 C) (n-1)/2 D) (n+1)/2 二.填空题(将正确的答案填在相应的空中) 单链表是_线性
7、表_的链接存储表示。 向一个长度为 n 的向量中删除第 i 个元素（1in）时，需向前移动_n-i_个元素。 可以使用_二叉链表_表示树形结构。 在双链表中，每个结点有两个指针域，一个指向_直接前驱_，另一个指向_直接后继 _。 在一个单链表中的 p 所指结点之前插入一个 s 所指结点时，可执行哪些操作_。 在一个单链表中删除 p 所指结点时，应执行的操作_。 带有一个头结点的单链表 head 为空的条件是 head-next=NULL_。 在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行 s-next=_p-next_ 和 p-next=_s_的操作。 9,非空的循环链表 h
8、ead 的尾结点（由 p 所指向） ，满足条件_p-next=head_。 10,对于一个具有 n 个结点的单链表，在已知 p 所指结点后插入一个新结点的时间复杂度是 _o(1)_； 在给定值为 x 的结点后插入一个新结点的时间复杂度是_o(n)_。 栈和队列个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是_c_。 A) edcba B) dceba C) dceab D) abcde 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1,p2,p3,pn,若 p1=n，则 pi 为_c_。 A) i B) n-i C) n-i+1 D) 不确定 判定一个栈 ST（最多元
9、素为 m0）为空的条件是_b_。 A) ST-top!=0 B) ST-top=0 C) ST-top!=m0 D) ST-top=m0 判定一个栈 ST（最多元素为 m0）为栈满的条件是_d_。 A) ST-top!=0 B) ST-top=0 C) ST-top!=m0 D) ST-top=m0 栈的特点是_b_，队列的特点是_a_。 A) 先进先出 B) 先进后出在以下的叙述中，正确的是_c_。A) 线性表的线性存储结构优于链表存储结构 B) 栈的操作方式是先进先出 C) 二维数组是其数据元素为线性表的线性表 D) 队列的操作方式是先进后出一个队列的 入队序列是 1，2，3，4，则队列的
10、输出序列是_b_。 A) 4,3,2,1 B) 1,2,3,4 C) 1,4,3,2 D) 3,2,4,1 判定一个循环队列 QU（最多元素为 m0）为空的条件是_a_。 A) QU-front=QU-rear B) QU-front!=QU-rear C) QU-front=(QU-rear+1)%m0 D) QU-front!=(QU-rear+1)%m0 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是_d_。 A) QU-front=QU-rear B) QU-front!=QU-rear C) QU-front=(QU-rear+1)%m0 D) QU-front!=(QU
11、-rear+1)%m0 循环队列用数组 Am存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中 的元素个数是_a_。 A) (rear-front+m)%m B) rear-front+1 C) rear-front-1 D) rear-front 栈和队列的共同点是_c_。 A) 都是先进后出 B) 都是先进先出 C) 只允许在端点处插入和删除 D) 没有共同点 向一个栈顶指针为 HS 的链栈中插入一个 s 所指结点时，则执行_c_。 A) HS-next=s; B) s-next=HS-next; HS-next=s; C) s-next=HS; HS=s; D)
12、s-next=HS; HS=HS-next; 从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行 _d_。 A) x=HS; HS=HS-next; B) x=HS-data; C) HS=HS-next; x=HS-data; D) x=HS-data; HS=HS-next; 在一个链队中，假设 f 和 r 分别为队首和队尾指针，则插入 s 所指结点的运算时_b_。 A) f-next=s; f=s; B) r-next=s; r=s; C) s-next=r; r=s; D) s-next=f; f=s; 17,在一个链队中，假设 f 和 r 分别为队首和队
13、尾指针，则删除一个结点的运算时_c_。 A) r=f-next; B) r=r-next; C) f=f-next; D) f=r-next; 二,填空题(将正确的答案填在相应的空中) 向量、栈和队列都是_线性_结构，可以在向量的_端点_位置插入和删除元素；对于 栈只能在 _栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和_队头_删 除元素。 向一个长度为 n 的向量的第 i 个元素之前插入一个元素时，需向后移动_n-i+1_个元素。 向栈中压入元素的操作是_置入数据，栈顶指针加 1_。 对栈进行退栈时的操作是_栈顶指针减 1，取出数据_。 在一个循环队列中，队尾指针指向队尾元素的_直接
14、后继_。 从循环队列中删除一个元素时，其操作是_取出队头指针所指数据元素，队头指针加 1_。 在具有 n 个单元的循环队列中，队满时共有_n-1_个元素。 一个栈的输入序列是 12345，则栈的输出序列 43512 是_错误的_。 一个栈的输入序列是 12345，则栈的输出序列 12345 是_正确的_。 在栈顶指针为 HS 的链栈中，判定栈空的条件是_HS=NULL_。 在栈顶指针为 HS 的链栈中，计算该链栈中结点个数的函数是_遍历函数_。 串一,单项选择题空串与空格串是相同的，这种说法_b_。 A) 正确 B) 不正确串是一种特殊的线性表，其特殊性体现在_b_。A) 可以顺序存储 B)
15、数据元素是一个字符 C) 可以链接存储 D) 数据元素可以是多个字符设有两个串 p 和 q，求 q 在 p 中首次出现的 位置的运算称作_b_。 A) 连接 B) 模式匹配 C) 求子串 D) 求串长设串 s1=ABCDEFG,s2=PQRST,函数 con(x,y)返回 x 和 y 串的连接串，subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成 的子串，len(s)返回串 s 的长度，则 con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果串是 _d_。 A) BCDEF B) BCDEFG C) BDPQRST D) BCDEFEF 二,填空题串的两种最基本的存储方式是_顺序和链式_。 两个串的长度相等的充分必要条件是_有效字符相同_。 空串是_“”_其长度等于_0_。 空格串是_由空格组成的字符串_，其长度等于_空格的个数_。 设 s=“I
