选择填空判断

一、判断题

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. i

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

个元素。

A.n-i B.n-i+1 C.n-i-1 D.i 6. 链表不具有的特点是____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-i B. n-i+1 C. n-i-1 D. i

10. 下面算法的时间复杂度为______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

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

A存储和逻辑结构 C理想和抽象

B存储和抽象 D理想与逻辑

2

2

13. 算法分析的目的是___B______

A、找出数据结构的合理性 B、分析算法的效率以求改进、研究算法中的 C、输入和输出的关系D、分析算法的易懂性和文档性 14. 算法分析的两个主要方面是：A

A 空间复杂性和时间复杂性 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．P knext s->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->next p->data!=x p=p->next q->next=p->next

5.下列算法为删除单链表中值为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->next q->nex=p->next

6.下列算法为利用尾插法，建立一个单链表，将程序填完整程序

本文来源：https://www.bwwdw.com/article/9b1d.html