一、判断题1。

顺序表和一维数组一样，都可以按下标随机（或直接）访问。

( √）2. 数据的逻辑结构是指各数据元素之间的逻辑关系,是用户根据应用需要建立的.（√）3。

只有用面向对象的计算机语言才能描述数据结构算法。

（×）4。

在对双向循环链表做删除一个结点操作时,应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作.（√）5。

数据元素是数据的最小单位.（×）6. 算法和程序都应具有下面一些特征：输入,输出,确定性，有穷性,可行性.（√）7. 插入与删除操作是数据结构中最基本的两种操作,因此这两种操作在数组中也经常被使用。

（× ) 8。

线性表若采用链式存储表示, 在删除时不需要移动元素.( √ )9. 用一组地址连续的存储单元存放的元素一定构成线性表。

（× )10. 线性表的逻辑顺序与物理顺序总是一致的.（×）11. 线性表的顺序存储表示优于链式存储表示。

( ×）12.链表的每个结点中都恰好包含一个指针.（×）二、填空题1. 若经常需要对线性表进行查找操作，则最好采用（顺序）存储结构.2.(循环)链表从任何一个结点出发，都能访问到所有结点.3.若经常需要对线性表进行插入与删除操作，该线性表最好采用(链式)存储结构。

4.通常用时间复杂度和(空间复杂度)两种方法衡量算法的效率5.已知一顺序存储的线性表，每个元素占用k个存储单元,若第一个元素的地址为Loc1，则第i个元素的地址为（ Loc1+（i-1)*k )。

6.在以L为头指针的带头结点的单链表和单循环链表中,判断链表是否为空的条件分别为（L->next==NULL和_L—〉next==L）。

7.顺序表中逻辑上相邻的元素的物理位置(相邻），单链表中逻辑上相邻的元素的物理位置(不一定相邻）.8.数据的逻辑结构包括集合、(线性结构）、树形结构和图状结构四种类型。

9.已知有实现同一功能的两个算法，其时间复杂度分别为O(log2n)和O(n），哪个算法的效率更高？( O（log2n））10.在一个单链表L中，若要在指针q所指结点的后面插入一个由指针p所指向的结点,则应进行的操作序列为：（ p-〉next=q—>next），q一〉next=p。

11.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对(头指针）进行特殊处理.12.在双向链表中，每个结点含有两个指针域，一个指向(直接前驱）结点,另一个指向（直接后继)结点。

13.在非空线性表中除第一个元素外，集合中每个数据元素只有一个(直接前驱）；除最后一个元素之外，集合中每个数据元素均只有一个(直接后继)。

14.一个算法一该具有有穷性，(确定性）,可行性，输入和输出这五种特性。

三、选择题1. 计算机识别、存储和加工处理的对象被统称为_____A___.A。

数据 B。

数据元素 C。

数据结构 D。

数据类型2.线性表若采用链式存储结构时,要求内存中可用存储单元的地址__D______。

A. 必须是连续的B. 部分地址必须是连续的C。

一定是不连续的 D. 连续，不连续都可以3.线性表若采用顺序存储结构时，要求内存中可用存储单元的地址__A______.A。

必须是连续的 B。

部分地址必须是连续的C. 一定是不连续的 D。

连续，不连续都可以4.在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置之前插入一个新元素时,需要移动___B_____个元素。

A. n—i B。

n-i+1 C。

n-i-1 D. i5.在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移____A____个元素。

A.n—i B。

n-i+1C。

n—i-1 D。

i6.链表不具有的特点是____A____.A. 随机访问B. 不必事先估计所需存储空间大小C. 插入与删除时不必移动元素 D。

所需空间与线性表长度成正比7.在一个单链表L中,若要删除由指针q所指向结点的后继结点,则执行____D____.A. q=q—>next； B。

q—>next=p-〉next；C. p=q-〉next；D. q->next=q-〉next—>next;8.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行__B___。

A.p = q->next ; p-〉next = q->next； B。

p = q—〉next ； q->next = p-〉next；C。

p = q—〉next ; q—>next = p； D.q—〉next = q->next—〉next; q—>next = q;9.在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n)时，需要移动____A____个元素.A. n—iB. n—i+1C. n—i-1 D。

i10.下面算法的时间复杂度为______B______。

int f（ unsigned int n ) ｛if （ n==0 ｜｜ n==1 ) return 1; else return n*f（n-1)；｝A。

O(1) B。

O（n)C。

O（n2） D. O(n！）11.下面程序段的时间复杂度为_______C_____。

for（int i=0； i<m； i++)for（int j=0; j<n； j++)A［i］［j]=i*j;A. O（m2） B。

O(n2) C. O（m＊n） D。

O(m+n)12.数据结构通常是研究数据的 A 及它们之间的联系。

A存储和逻辑结构B存储和抽象C理想和抽象D理想与逻辑13.算法分析的目的是___B______A、找出数据结构的合理性B、分析算法的效率以求改进、研究算法中的C、输入和输出的关系D、分析算法的易懂性和文档性14.算法分析的两个主要方面是：AA 空间复杂性和时间复杂性B 正确性和简明性C 可读性和文档性D 数据复杂性和程序复杂15.线性表Ｌ在 B 情况下适用于使用链式结构实现.A 需经常修改Ｌ中的结点值B 需不断对Ｌ进行删除插入C Ｌ中含有大量的结点D Ｌ中结点结构复杂四、程序题typedef struct LNode {int data;struct LNode ＊next；｝LNode, ＊LinkList；1.将下面算法填完整。

void ListInsert_L(node L,int i,elementtype x）｛ LinkList p=L,s； int k=0;while （＆& )｛；k++;}if （!p ｜|j〉i—1) return ERROR;s=（LinkList） malloc （sizeof(node））;s->data=x；；；}1．Pk〈i-1p=p—〉nexts—〉next=p—〉next；p->next=s;2. 简述下面算法的功能void AC （LinkList &L） {// L为一个无头结点的单链表if （L&&L-〉next) ｛q=L; L=L—>next; p=L;while (p->next） p=p-〉next;p—>next=q； q—>next=NULL；｝｝将该单链表的表头元素移到表尾3. 简述下面算法的功能void AE (LNode ＊s， LNode *q） {p=s；while （p->next!=q) p=p->next；p—>next=s；}void AD （LNode *pa, LNode ＊pb）｛// pa和pb分别指向单循环链表中的两个结点AE (pa, pb）;AE (pb, pa);｝将一个单循环链表拆分成两个单循环链表(指针pa和pb分别指向这两个单循环链表中的某两个节点) 4.下列算法为删除带头结点的单链表head中值为x的算法，将程序填完整（每空2分)已知结构体：typedef struct LNode {ElemType data；struct LNode *next；｝LNode，＊LinkList；void del(LinkList head）{ q=head；;while（p ＆＆ )){ q=p；_________;｝if(p= = null) printf（“error”）;else｛______________；free(p);printf（“success!"）；}｝p=q—>nextp—〉data!=xp=p-〉nextq—>next=p-〉next5。

下列算法为删除单链表中值为X的算法，将程序填完整（4分，每空2分)已知结构体： struct node {ElemType data；struct LNode ＊next;｝；void del（struct node *head){ q=head;p=q—〉next;while(（p ）＆＆(p-〉data！=x )）{ q=p；___ ___；}if（p= = null) printf（“error”)；else{__ ____;free(p）；printf(“success！"）；}}p=q->nextq—>nex=p—>next6。

下列算法为利用尾插法，建立一个单链表，将程序填完整程序void CreateList (LinkList ＆L,int n）{LinkList r,p;int i;L=（LinkList）malloc(sizeof(node）)；L—〉next=NULL；;for(i=n;i>0；——i)｛p=(LinkList)malloc（sizeof（node));scanf(“%c”,&p-〉data）;；r—>next=p；；｝｝r=L;p—〉next=NULL；r=p;队栈串数组广义表一、判断题：1.递归的算法简单、易懂、容易编写,而且执行效率也高.（ f ）2.链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。

( t ）3.堆栈、队列和数组的逻辑结构都是线性表结构。

（ t ）4.单链表形式的队列,头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点（f )5.若某堆栈的输入序列为1,2,3，4，则4,3，1,2不可能是堆栈的输出序列之一。

（t ）6.栈和队列都是限制取点的线性结构( t )7.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同.（ t ）8.稀疏矩阵压缩存储后，必会失去随机存取功能.（ t ）9.如果两个串中含有相同的字符，则这两个串相等（ f ）10.广义表的表头和表尾既可以是单元素,也可以是广义表。