数据结构(线性表习题含答案)

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=NULLC) head->next=head D) head!=NULL带头结点的单链表

2、head为空的判定条件是_B_。A) head=NULL B) head->next=NULLC) head->next=head D) head!=NULL非空的循环链表head的尾结点（由p所指向）满足_C_。A) p->next=NULL B) p=NULLC) 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-&g

3、t;right->left=s; s->left=p; s->right=p->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->nex

4、t=s; B) p->next=s->next; s->next=P;C) q->next=s; s->next=p; D) p->next=s; s->next=q;在一个单链表中，若p所指结点不是最后结点，在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所指结点的后续结点，则执

5、行_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 linknodeint data,/*数据域*/struct linknode * llink; /*llink是指向前驱结点的指针域*/struct linknode * rlink; /*rlink是指向后续结点的指针域*/ bnode要把一个q所指新结点

6、作为非空双向链表中的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; p->llink->rlink=q; p->llink=q;以上都不对,12,从一个具有n个结点的单链表中查找其

7、值等于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二.填空题(将正确的答案填在相应的空中)单链表是_线性表_的链接存储表示。向一个长度为n的向量中删除第i个元素（1in）时，需向前移动_n-i_个元素。可以使用_二叉链表_表示树形结构。在双链表中，

8、每个结点有两个指针域，一个指向_直接前驱_，另一个指向_直接后继_。在一个单链表中的p所指结点之前插入一个s所指结点时，可执行哪些操作_。在一个单链表中删除p所指结点时，应执行的操作_。带有一个头结点的单链表head为空的条件是 head->next=NULL_。在一个单链表中p所指结点之后插入一个s所指结点时，应执行 s->next=_p->next_和 p->next=_s_的操作。9,非空的循环链表head的尾结点（由p所指向），满足条件_p->next=head_。10,对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是_o(1)

9、_； 在给定值为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（最多元素为m0）为空的条件是_b_。A) ST->top!=0 B) ST->top=0 C) ST->top!=m0 D) ST->top=m0判定一个栈ST（最多元素为m0）为栈满的条

10、件是_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，则队列的输出序列是_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

11、) QU->front=QU->rear B) QU->front!=QU->rearC) 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->rearC) QU->front=(QU->rear+1)%m0 D) QU->front!=(QU->rear+1)%m0循环队列用数组Am存放其元素值，已知

12、其头尾指针分别是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) s->next=HS; HS=HS->

13、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分别为队首和

14、队尾指针，则删除一个结点的运算时_c_。A) r=f->next; B) r=r->next; C) f=f->next; D) f=r->next;二,填空题(将正确的答案填在相应的空中)向量、栈和队列都是_线性_结构，可以在向量的_端点_位置插入和删除元素；对于栈只能在 _栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和_队头_删除元素。向一个长度为n的向量的第i个元素之前插入一个元素时，需向后移动_n-i+1_个元素。向栈中压入元素的操作是_置入数据，栈顶指针加1_。对栈进行退栈时的操作是_栈顶指针减1，取出数据_。在一个循环队列中，队尾指针指向队尾元素的_

15、直接后继_。从循环队列中删除一个元素时，其操作是_取出队头指针所指数据元素，队头指针加1_。在具有n个单元的循环队列中，队满时共有_n-1_个元素。一个栈的输入序列是12345，则栈的输出序列43512是_错误的_。一个栈的输入序列是12345，则栈的输出序列12345是_正确的_。在栈顶指针为HS的链栈中，判定栈空的条件是_HS=NULL_。在栈顶指针为HS的链栈中，计算该链栈中结点个数的函数是_遍历函数_。串一,单项选择题空串与空格串是相同的，这种说法_b_。A) 正确 B) 不正确串是一种特殊的线性表，其特殊性体现在_b_。A) 可以顺序存储 B) 数据元素是一个字符C) 可以链接存储

16、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二,填空题串的两种最基本的存储方式是_顺序和链式_。两个串的长度相等的充分必要条件是_有效字

17、符相同_。空串是_“”_其长度等于_0_。空格串是_由空格组成的字符串_，其长度等于_空格的个数_。设s=“I AM A TEACHER”其长度是 14_。设s1=GOOD,s2= ,s3=BYE!,则s1、s2和s3连接后的结果是_GOOD BYE!_。数组和广义表一,单项填空题(其中Ai.j表示下标i到j)常对数组进行的两种基本操作是_C_。A) 建立与删除 B) 索引与修改 C) 查找和修改 D) 查找与索引二维数组M的每个成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要_D_个字节；M的第8列和第5行共占_A_个字节；

18、若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的_B_元素的起始地址一致。 A) 90 B) 180 C) 240 D) 540 A) 102 B) 114 C) 54 D) 60 A) M85 B) M310 C) M58 D) M09二维数组M的每个元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素_B_的起始地址相同。A） M24 B) M34 C) M35 D) M44数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在

19、存储器内，存放数组至少需要的单元数是_C_。A) 80 B) 100 C) 240 D) 270数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为_C_。A) SA+141 B) SA+144 C) SA+222 D) SA+255数组A中，每个元素A的长度为3个字节，行下标从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A58的起始地址为_B_。A) SA+141 B) SA+144 C) SA+222 D) SA+255稀疏矩阵一般的压缩存储方法有两种

20、，即_C_。A) 二维数组和三维数组 B） 三元组和散列C） 三元组和十字链表 D） 散列和十字链表若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点_A_ 。A） 正确 B） 错误设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组B1.n(n-1)/2中，对下三角部分中任一元素ai,j(ij)，在一组数组B中下标k的值是_B_。A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+ja1,1a2,1 a2,2A=,.an,1 an,2,.,a

21、n,n10,广义表（a）,a）的表头是_C_，表尾是_C_。A) a B) () C) (a) D) (a)广义表（a）的表头是_B_，表尾是_C_。A) a B) (a) C) () D) (a)广义表(a,b),c,d)的表头是_C_，表尾是_D_。A) a B) b C) (a,b) D) (c,d)广义表(a,b,c,d)表头是_A_，表尾是_D_。A) a B) b C) (a,b) D) (b,c,d)广义表（a,b,c,d）的表头是_C_，表尾是_B_。A) a B) () C) (a,b,c,d) D) (a,b,c,d)一个广义表的表头总是一个广义表，这个断言是_B_。A) 正确 B） 不正确一个广义表的表尾总是一个广义表，这个断言是_A_。A）正确 B） 不正确二填空题1,已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个的存储地址是LO