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

数据结构第二章 线性表习题含答案

说明：顺序存储的线性表称为向量。

一,单项选择题一个向量第一个元素的地址是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为空的判定条件是__①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->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所指结点不是最后结点，在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,/*数据域*/

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; 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

二.填空题(将正确的答案填在相应的空中) 单链表是_线性表____的链接存储表示。

向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动__n-i___个元素。 可以使用_二叉链表____表示树形结构。 在双链表中，每个结点有两个指针域，一个指向__直接前驱___，另一个指向_直接后继____。 在一个单链表中的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)___； 在给定值为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）为栈满的条件是_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) 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->rear+1)%m0

循环队列用数组A[m]存放其元素值，已知其头尾指针分别是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->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分别为队首和队尾指针，则删除一个结点的运算时__c___。 A) r=f->next; B) r=r->next; C) f=f->next; D) f=r->next; 二,填空题(将正确的答案填在相应的空中)

向量、栈和队列都是_线性____结构，可以在向量的__端点___位置插入和删除元素；对于栈只能在 _栈顶____插入和删除元素；对于队列只能在_队尾____插入元素和__队头___删除元素。

向一个长度为n的向量的第i个元素之前插入一个元素时，需向后移动_n-i+1____个元素。 向栈中压入元素的操作是_置入数据，栈顶指针加1____。 对栈进行退栈时的操作是_栈顶指针减1，取出数据____。

在一个循环队列中，队尾指针指向队尾元素的_直接后继____。

从循环队列中删除一个元素时，其操作是__取出队头指针所指数据元素，队头指针加1___。 在具有n个单元的循环队列中，队满时共有_n-1____个元素。

一个栈的输入序列是12345，则栈的输出序列43512是_错误的____。 一个栈的输入序列是12345，则栈的输出序列12345是_正确的____。 在栈顶指针为HS的链栈中，判定栈空的条件是_HS==NULL____。

在栈顶指针为HS的链栈中，计算该链栈中结点个数的函数是_遍历函数____。 串一,单项选择题空串与空格串是相同的，这种说法_b___。

A) 正确 B) 不正确串是一种特殊的线性表，其特殊性体现在__b___。 A) 可以顺序存储 B) 数据元素是一个字符

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 AM A TEACHER”其长度是 14_____。

设s1=’GOOD’,s2=’ ’,s3=’BYE!’,则s1、s2和s3连接后的结果是_GOOD BYE!____。 数组和广义表一,单项填空题(其中A[i...j]表示下标i到j) 常对数组进行的两种基本操作是__C___。

A) 建立与删除 B) 索引与修改 C) 查找和修改 D) 查找与索引二维数组M的每个成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要__①_D__个字节；M的第8列和第5行共占__②_A__个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的__③B___元素的起始地址一致。 ① A) 90 B) 180 C) 240 D) 540 ② A) 102 B) 114 C) 54 D) 60

③ A) M[8][5] B) M[3][10] C) M[5][8] D) M[0][9]

二维数组M的每个元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素__B___的起始地址相同。

A） M[2][4] B) M[3][4] C) M[3][5] D) M{4}[4]

数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放数组至少需要的单元数是_C____。 A) 80 B) 100 C) 240 D) 270

数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为___C__。 A) SA+141 B) SA+144 C) SA+222 D) SA+255

数组A中，每个元素A的长度为3个字节，行下标从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为_B____。 A) SA+141 B) SA+144 C) SA+222 D) SA+255

稀疏矩阵一般的压缩存储方法有两种，即_C____。 A) 二维数组和三维数组 B） 三元组和散列

C） 三元组和十字链表 D） 散列和十字链表若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点__A___ 。 A） 正确 B） 错误设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组B[1..n(n-1)/2]中，对下三角部分中任一元素ai,j(i≥j)，在一组数组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+j a1,1 a2,1 a2,2 A=,..

an,1 an,2,.,an,n