数据结构习题

1．数据结构是一门研究非数值计算的程序设计问题中计算机的⑴以及它们之间的⑵和运算等的学科。 ⑴A操作对象 B计算方法 C逻辑存储 D数据映像

⑵A结构 B关系 C运算 D算法 2．数据结构被形式定义为（K，R），其中K是⑴的有限集，R是K上的⑵有限集。 ⑴A算法 B数据元素 C数据操作 D逻辑结构 ⑵A操作 B映象 C存储 D关系 3．在数据结构中，从逻辑上可以把数据结构分成⑴。 ⑴A动态结构和表态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构

4．线性结构的顺序存储结构是一种⑴的存储结构，线性表的链式存储结构是一种⑵的存储结构。 ⑴A随机存取 B顺序存取 C索引存取 D散列存取 ⑵A随机存取 B顺序存取 C索引存取 D散列存取 5．算法分析的目的是⑴，算法分析的两个主要方面是⑵。 ⑴A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性 ⑵A空间复杂度和时间复杂度，正确性和简单性 B可读性和文档性 C数据复杂性和程序复杂性 6．计算机算法指的是⑴，它必须具备输入、输出和⑵等5个特性。 ⑴A计算方法 B排序方法 C解决问题的有限运算序列 D调度方法 ⑵A可执行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性 7．线性表的逻辑顺序与存储顺序总是一致的，这种说法⑴。 ⑴A正确 B不正确

8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址⑴。 ⑴A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以 9．在以下的叙述中，正确的是⑴。 ⑴A线性表的线性存储结构优于链表存储结构 B二维数组是其数据元素为线性表的线性表 C栈的操作方式是先进先出 D队列的操作方式是先进后出

10．每种数据结构都有具备三个基本运算：插入、删除、和查找，这种说法⑴。 ⑴A正确 B不正确 二、填空题

1．数据结构包括 、 和 三种类型，树形结构和图形结构全称为 。 2．在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。

3．在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点可以 。

4．在图形结构中，每个结点的前驱结点数和后续结点数可以 。

5．线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。

6．算法的五个重要特性是 、 、 、 、 。 7．指出下面程序段的时间复杂度。 [1]for (I=0;IA[I][j]=0;

[2]I=s=0; while(ss+=I;

}; [3]s=0;

for(I=0;Ifor(j=0;j[4]I=1;

while(I<=n) I=I*3;

第二章 线性表 一、填空题 1．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是⑴。 ⑴A100 B108 C100 D120 2．一个栈的入栈序列是abcde，则不可能的输出序列是⑴。 ⑴A edcba B decba C dceab D abcde 3．若已知一个栈的入栈序列是12345……n，其输出序列为p1，p2，p3，……， pn，若p1=n，则pi为⑴。 ⑴A I B n=I C n-I+1 D 不确定 4．栈结构通常采用的两种存储结构是⑴。 ⑴A线性存储结构和链表存储结构 B散列方式和索引方式 C链表存储结构和数组 D线性存储结构和非线性存储结构 5．判定一个栈ST（最多元素为m0）为空的条件是⑴。 ⑴A ST->top!=0 B ST->top==0

C ST->top!=m0-1 D ST->top==m0-1

6．判定一个栈ST（最多元素为m0）为栈满的条件是⑴。 ⑴A ST->top!=0 B ST->top==0

C ST->top!=m0-1 D ST->top==m0-1 7．栈的特点是⑴，队列的特点是⑵。 ⑴A先进先出 B先进后出

8．一个队列的入列序列是1234，则队列的输出序列是⑴。 ⑴A 4321 B 1234 C 1432 D 3241 9．判定一个队列Q（最多元素为m0）为空的条件的⑴。 ⑴A Q->rear-Q->front==m0 B Q->rear-Q->front-1==m0 C Q->front==Q->rear D Q->front==Q->rear+1 10．判定一个队列Q（最多元素为m0）为满队列的条件是⑴。 ⑴A Q->rear-Q->front==m0 B Q->rear-Q->front-1==m0 C Q->front==Q->rear D Q->front==Q->rear+1 11．判定一个循环队列Q（最多元素为m0）为空的条件的⑴。 ⑴A Q->front==Q->rear B Q->front!=Q->rear C Q->front==（Q->rear+1）%m0 D Q->front!=（Q->rear+1）%m0 12．判定一个循环队列Q（最多元素为m0）为满队列的条件的⑴。 ⑴A Q->front==Q->rear B Q->front!=Q->rear C Q->front==（Q->rear+1）%m0 D Q->front!=（Q->rear+1）%m0

13．循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是⑴。 ⑴A (rear-front+m)%m B rear-front+1 C rear-front-1 D rear-front 14．栈和队列的共同点是⑴。 ⑴A都有是先进后出 B都有是先进先出 C中允许在端点处插入和删除元素 D没有共同点 15．表达式a*(b+c)-d的中缀表达式是⑴。 ⑴A abcdd+- B abc+*d- C abc*+d- D -+*abcd 二、填空题

1．向量、栈和队列都是 结构，可以在向量的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入元素和 删除元素。 2．在一个长度为n的向量中的第I元素（1≤I≤n）之前插入一个元素，需要向后移动 个元素。

3．在一个长度为n的向量中删除第I元素（1≤I≤n），需要向前移动 个元素。 4．向栈中压入元素的操作是 。 5．对栈进行退栈时的操作是 。

6．在一个循环队列中，队首指针指向队首元素的 。 7．从循环队列中删除一个元素时，其操作是 。

8．在具有n个单元的循环队列中，队满时共有 个元素。 9．一个栈的输入序列是1234，则输出序列43512是 。 10．一个栈的输入序列12345，则输出序列12345是 。

第三章 链表 一、填空题

1．不带头结点的单链表head为空的判定条件是⑴。 ⑴A head==NULL B head->next==NULL C head->next==head D head!=NULL 2．带头结点的单链表head为空的判定条件是⑴。 ⑴A head==NULL B head->next==NULL C head->next==head D head!=NULL

3．非空的循环单链表head的尾结点（由p所指向）满足⑴。 ⑴A p->next==NULL B p==NULL C p->next==head D p==head

4．在循环双链表的p所指结点之后插入s所指结点的操作是⑴。 ⑴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;ls->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;

5．在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行⑴。 ⑴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;

6．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行⑴。 ⑴A s->next=p;p->next=s; B s->next=pnext;p->next=s; C s->next=p->next;p=s; D p->next=s;s->next=p; 7．在一个单链表中，若删除p所指结点的后续结点，则执行⑴。 ⑴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; 8．假设双链表结点的类型如下： typedef struct linknode { int data; struct linknode *llink; struct linknode *rlink; }bnode; 下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是⑴。 ⑴A q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q; B p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink; C q->llink=p->llink;q->rlink=p;p->llink->rlink=q;p->llink=q; D 以上都不对

9．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较⑴个结点。 ⑴A n B n/2 C (n-1)/2 D (n+1)/2

10．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是⑴。 ⑴A O(1) B O(n) C O(n2) D O(nlog2n) 11．给定有n个元素的向量，建立一个有序单链表的时间复杂度是⑴。 ⑴A O(1) B O(n) C O(n2) D O(nlog2n)

12．向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行⑴。 ⑴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;

13．从一个栈顶指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行⑴。 ⑴A x=hs;hs=hs->next; B x=hs->data; C hs=hs->next;x=hs->data; D x=hs->data;hs=hs->next;

14．在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时⑴。 ⑴A f->next=s;f=s; B r->next=s;r=s; C s->next=r;r=s; D s->next=f;f=s;

15．在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时⑴。 ⑴A r=f->next; B r=r->next; C f=f->next; D f=r->next; 二、填空题。

1．单链表是 的链接存储表示。 2．可以使用 表示树形结构。

3．在双链表中，每个结点有两个指针域，一个指向 ，另一个指向 。 4．在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如处操作： [1]s->next= ; [2]p->next=s; [3]t=p->data; [4]p->data= ; [5]s->data= ;

5．在一个单链表中删除p所指结点时，应执行以下操作： q=p->next; p->data=p->next->data; p->next= ; free(q);

6．带有一个头结点的单链表head为空的条件 。

7．在一个单链表中结点p所指结点之后插入一个s所指结点时，应执行s->next= 和p->next= 的操作。

8．非空的循环单链表head的尾结点（由p所指向），满足条件 。 9．在栈顶指针为hs的链栈中，判定栈空的条件是 。 10．在Q链队中，判定只有一个结点的条件是 。 11．在Q链队中，计算该链队中结点个数的函数是 。

12．对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是 ；在给定值为x的结点后插入一个新结点的时间复杂度是 。

第四章 串 一、选择题。

1．空串与空格串是相同的，这种说法⑴。 ⑴A正确 B不正确

2．串是一种特殊的线性表，其特殊性体现在⑴。 ⑴A可以顺序存储 B数据元素是一个字符 C可以链接存储 D数据元素可以是多个字符 3．设有两个串P和Q，求Q在P中首次出现的位置的运算称作⑴。 ⑴A连接 B模式匹配 C求子串 D求串长

4．设串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))的结果串是⑴。 ⑴A BCDEF B BCDEFG C BCPQRST D BCDEFEF 二、填空题

1．串的两种最基本的存储方式是 。 2．两个串相等的充分必要条件是 。 3．空串是 ，其长度等于 。 4．空格串是 ，其长度等于 。

5．设s=‟I AM A TEACHER‟其长度等于 。

6．设s1=‟GOOD‟，s2=‟ „，s3=‟BYE!‟，则s1、s2和s3连接后的结果是 。

第五章 数组和稀疏矩阵 一、选择题

1．常对数组进行的两种基本操作是⑴。 ⑴A建立和删除 B索引和修改 C查找和修改 D查找与索引

2．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放M至少需要⑴个字节，M的第8列和第5行共占⑵个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的元素的起始地址一致。 ⑴A90 B180 C240 D540 ⑵A108 B114 C54 D60 ⑶A M[8][5] B M[3][10] C M[5][8] D M[0][9]

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

4．数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是 ⑴。 ⑴A80 B100 C240 D270

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

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

7．稀疏矩阵一般的压缩方法有两种，即⑴。 ⑴A二维数组和三维数组 B三元组和散列

C三元组和十字链表 D散列和十字链表

8．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点⑴。 ⑴A正确 B错误 二、填空题。

1．已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A[0][0]），则A[I][j]的地址是 。

2．二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是 。

3．二维数组A[10..20][5..]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是 。

第六章 递归 一、选择题。

1．递归函数f(n)=f(n-1)+n(n>1)的递归出口是⑴。 ⑴A f(1)=0 B f(1)=1 C f(0 )=1 D f(n)=n

2．递归函数f(n)=f(n-1)+n(n>1)的递归体是⑴。 ⑴A f(1)=0 B f(0)=1 C f(n )=f(n-1)+n D f(n)=n)

3．将递归算法转换成对应的非递归算法时，通常需要使用⑴。 ⑴A栈 B队列 C链表 D树 二、填空题。

1．将f=1+1/2+1/3+……+1/n转化成递归函数，其递归出口是 ，递归体是 。 2．下列程序利用递归方法判别由链表表示的两个非递归列表是否相等，其中的非递归列表定义为：一个列表或者是没有元素的空列表，或者是由元素序列组成的一个列表，其中的元素可以是一个字符或者满足本定义的另一个列表。这种列表的例子如下图所示。 s f „a‟ t ^ f „b‟ f „c‟ ^

列表s由两个元素组成，第一个元素是字符a（标志是f），第二个元素是另一个列表（标志是t），它由两个元素即（标志都为f）字符b和字符c组成，两个非递递归列表相等是指它们的元素个数相等，且表中元素依次相同。程序如下： struct listpointer { struct listpointer *link; int tag; union { char data; struct listpointer *dlink; }val; }; int equal(struct listpointer *s,struct linstpointer *t) { int same; if(s==NULL &&t==NULL) ; else if( ) { if( ) { if(s->tag==0)

same=( );

else same=( ); if(same) ;

} } return(same); }

3．有如下递归过程： void print(int w) { int I; if(w!=0) { print(w-1); for(I=1;I<=w;I++) printf(“%3d”,w); printf(“\\n”); } }

调用语句print(4)的结果是 。 4．有如下递归过程： void reverse(int m) { printf(“%d”,n%10); if(n/10!=0) reverse(n/10); }

调用语句reverse(582)的结果是 。