数据结构考试题库完整

. . . . . . . . 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类 型，树形结构和图状结构合称为(非线性结构)。

4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间 存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。

7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 . . . . . . . . 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.部结构和外部结构 5.线性表若采用链式存储结构时，要求存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性 确定性 可行性 有0或多个输入 有1或多个输出 线性结构

一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时， 需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 7.设目标T=‘abccdcdccbaa’，模式P=‘cdcc’则第(六)次匹配成功。。 . . . . . . . . 8. 顺序栈 S 中 ， 出 栈操作时 要执行的 语句序列 中有 S->top(--)；进栈操作时要执行的语句序列中有S->top(++)。 9.顺序表中逻辑上相邻元素的物理位置(一定)紧邻；单链表中 逻辑上相邻元素的物理位置(不一定)紧邻。 10.在(循环)链表中，从任何一结点出发都能访问到表中的所有结点。

11.栈和队列均是(运算受限)的线性表，栈的特点是(先进后出 后进先出)；队列的特点是(先进先出 后进后出)。

12.通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为(定长顺序存储)和(堆分配存储)。 13.循环队列头指针front指向队头元素，队尾指针rear指向队 尾元素后的一个空闲元素，队列的最大空间为Queuelen。在循环队列中 ， 队空标志为(front==rear)， 队满标志为(（rear+1）%max==front)。 当rear>=front时，队列长度为(rear-front)，当rear

队列 长度为(rear-front+max)。 14.在一个长度为n的线性表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动(n-i+1)个元素。 15.在具有n个单元的循环队列中，队满时共有(n-1)个元素。 16.带有一个头结点的单链表Head为空的条件是(Head->next==null)。 17.在一个单链表中删除指针p所指向结点的后继结点时，需要把(p->next->next)值赋给p->next指针域。 . . . . . . . . 18.一个顺序循环队列存于a[M]中，假定队首和队尾指针分别 为front和rear，则判断队空的条件为( a.front==a.rear)，判断队满的条件为(（a.rear+1）%M==a.front)。 19.在双向链表中，每个结点有两个指针域，一个指向其(前驱) 结点，另一个指向其(后继)结点最后一个结点的(后继结点)指针域为空。 *20. 若 D=((a ， (b ， c)) ， e ， a) ， 则 Head( D )=( ) ，Tail( D )=( )，Head(Tail( D ))=( )。（本人不会） 21.在循环链表中，每个结点有(一个)个指针域，指向其(后继)结点，最后一个结点的指针域(为空)。 *22. 若 S=(a ， (b ， c) ， e ， d) ， 则 Head( S )=( ) ， Tail( S )=( )，Head(Tail( S ))=( )。（本人不会） 二、选择题 1.在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则执行(A)。 A.s->link=p->link; p->link=s; B.p->link=s; s->link=q; C.p->link=s->link; s->link=p; D.q->link=s; s->link=p; 2.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指 针为R。若在逻辑上看一个环，则队列中元素的个数(A)。 A.R-F B.n+R-F C.(R-F+1)mod n D.(n+R-F)mod n 3.如下述中正确的是(A)。 A.串是一种特殊的线性表 B.串的长度必须大于零 . . . . . . . . C.串中元素只能是字母 D.空串就是空白串 4.若让元素1，2，3依次进栈，则出栈次序不可能出现(C) 的情况。 A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2 5.判定一个队列QU（最多元素为m0）为空的条件是(C)。 A.QU->rear-QU->front==m0 B.QU->rear-QU->front-1==m0 C.QU->front==QU->rear D.QU->front==QU->rear+1 6.设目标串S=‘abcdef’，模式串p=‘de’，则第(C)次匹配成功。 A.1 B.2 C.4 D.5 7.设字符串s1=‘ABCDEFG’，S2=‘PQRST’，T，sub1，sub2为空串 。 则运算 s=Concat(T ，SubString(sub1 ， s1 ， 2 ， SubLength(s2))，SubString(sub2，s1，SubLength(s2)，2)) 后的串T值为( D)。 A.‘BCDEF’ B.‘BCDEFG’ C.‘BCPQRST’ D.‘BCDEFEF’ 8.一个顺序线性表第一个元素的存储地址是100，每个元素的 长度为2，则第5个元素的地址是( B)。

A.100 B.108 C.110 D.120 9.非空的循环单链表head的尾结点（由p所指向）满足(C)。 A.p->next==NULL B.p==NULL C.p->next==head D.p==head 10.在一个链队中，假设f和r分别为队首和队尾指针，则删除 . . . . . . . . 一个结点的运算时(C)。 A.r=f->next; B.r=r->next; C.f=f->next; D.f=r->next; 11.在一个长度为n的线性表中，删除值为x的元素时，需要比 较元素和移动元素的总次数为(C)。

A.(n+1)/2 B.n/2 C.n D.n+1 12.在一个单链表中，若要在p所指向的结点之后插入一个新结 点，则需要相继修改(B)个指针域的值。 A.1 B.2 C.3 D.4 13.线性结构中，每个结点(C)。 A.无直接前驱 B.只有一个直接前驱和个数不受限制的直接后继 C.只有一个直接前驱和后继 D.有个数不受限制的直接前驱 和后继 14.队列是限定在(D)进行操作的线性表。 A.中间 B.队头 C.队尾 D.端点 15.设串S1=“ABCDEFG”，S2=“PQRST”，函数StrCat(x,y)返回x和y串的连接串，函数StrSub(Si，j)返回串S的从序号i 的字符开始的j个字符组成的子串，StrLen(S)返回串S的长度， 则StrCat(StrSub(S1，2，StrLen(S2))，StrSub(S1，StrLen (S2)，2))的结果串是(D)。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 16.学生成绩表是一种(C)结构。 . . . . . . . . A.图形 B.树形 C.线性 D.集合 17.在一个链队中，假设f和r分别为队首和队尾指针，则插入s 所指结点的运算时(C)。 A.f->next=s; f=s; B.r->next=s; r=s; C.s->next=r; r=s; D.s->next=f; f=s; 18.向顺序表中的i位置处插入元素，下面哪项能够准确的表明 i的位置是合法的。(D) A.i<=1||i>l->length+1 B.i>=1 C.i>=l->length+1 D.1<=i<=l->length+1 19.设线性链表中结点的结构为（data，next），已知指针q所 指结点是指针p所指结点的直接后继，若在*q和*p之间插入结点*s，则应执行(A)操作。 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->next==s; s->next=q; 20.一个栈的入栈序列为a，b，c，d，e，则出栈序列不可能的是(C)。 A.edcba B.dcbae C.dceab D.abcde 21.如果以链表作为栈的存储结构，则出栈操作时(B)。 A.必须判别栈是否满 B.必须判别栈是否为空 C.必须判别栈元素类型 D.可不做任何判断 22.设有两个串p和q，求q在p中首次出现的位置的运算称为 (B)。 A.连接 B.模式匹配 C.求子串 D.求串长 23.p指向线性链表中的某一结点，则在线性链表的表尾插入结 点S的语句序列是(A)。