数据结构1-10题目

数据结构作业

班级： 学号： 姓名： 教师：

第一章：概述

一．单项选择。

1、数据结构是一门研究数值计算得程序设计问题中计算机的 以及它们之间的 和运算等的学科。

(1)A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 （2）A．结构 B关系 C运算 D算法 2、数据结构被形式地定义为（K，R），其中K是 的有限集，R是K上的 有限集。 （1）A.算法 B.数据元素 C.数据操作 D.逻辑结构 （2）A.操作 B.映像 C.存储 D.关系

3、 线性结构的顺序存储结构是一种 的存储结构，线性表的链式存储结构式一种 的存储结构。

A．随机存取 B.顺序存取 C.索引存取 D.散列存取

4、计算机算法指的是 ，它必须必备输入，输出和 等5个特性。 （1）A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2）A.可执行性、可移值性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性

5、线性表的逻辑顺序与存储顺序与总是一致的，此说法 。 A.对 B.错

6、以下哪一个术语与数据的存储结构无关？ 。 A.顺序表 B.链表 C.散列表 D.队列 7、研究数据结构就是研究 。

A．数据的逻辑结构 。 B．数据的存储结构。

C．数据的逻辑结构和存储结构。

D．数据的逻辑结构、存储结构及其数据的运算。 8、逻辑结构是指数据元素的 。

A．关联方式 B．存储方式 C．结构 D．数据项 9、在以下的叙述中，正确的是 。 A.线性表的线性存储结构优与链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出

10、每种数据结构都具三个基本运算：插入、删除、查找，此说法 。 A.对 B.错

11、以下哪一个术语与数据的存储结构无关？ 。 A.顺序表 B.链表 C.散列表 D.队列

12、算法在发生非法操作时可以做出处理的特性称为 。

A．正确性 B．易读性 C．健壮性 D．高效性

1

二、填空。

1树型结构和图型结构合称为（ ）。

2在线性结构中第一个结点（ ）前驱结点，其余每个结点有且只有（ ）个前驱结点；最后一个结点（ ）后续结点，其余每个结点有且只有（ ）个后续结点。

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

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

5线性结构中元素之间存在（ ）的关系，树型结构中元素之间存在（ ）的关系，图型结构中元素之间存在（ ）的关系。 6算法的无个重要特性是（ ）、（ ）、（ ）、（ ）、（ ）。 7下面程序的时间复杂度是（ ） for (i=o;i

8下面程序段的时间复杂度是（ ） i=s=0; while(s

9下面程序段的时间复杂度是（ ） s=0;

for(I=0;I

10下面程序段的时间复杂度是（ ） I=1;

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

三、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。 1. A=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={，，，

e>，，，}。 2. B=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={，，，

c>，，，}。 3. C=（K，R），其中：K={ a，b，c，d，e }，R={r}，r={，，，，

，，}。 4. D=（K，R），其中：K={48，25，64，57，82，36，75}，R={r1，r2}，r1={<25，36>，<36，

48>，<48，57>，<57，64>，<64，75>，<75，82>}；r2={<48，25>，<48，64>，<64，57>，<64，82>，<25，36>，<25，75>}。

5. E=（K，R），其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，<1，4>，<4，

1>，<2，3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。

2

第二章：链 表

一、单项选择。

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

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=p->next;p->next=s; C.s->next=p->next;p=s; D.p->next=s;s->next=p; 7、假设双链表结点的类型如下: typedef struct linknode {int data; /*数据域*/

struct linknode *llink; /*llink是指向前驱结点的指针域*/ struct linknode *rlink; /*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.以上答案都不对。 8、从一个具有N个结点的单链表中查找其值等于X结点时，在查找成功的情况下，需平均比较______ 个结点。

3

A N B N/2 C （N-1）/2 D （N+1）/2

9、在一个具有N个结点的有序单链表中插入一个新结点并仍然有序的的时间复杂度是 。

2

A O（1） B O（N） C O（N） D O（nlog2n）

10、给定有N个元素的线性表，建立一个有序单链表的时间复杂度是 。

2

A O（1） B O（N） C O（N） D O (nlog2n) 11、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 A.110 B.108 C.100 D.120 12、线性表是 。

A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 13、在单链表中，增加头结点的目的是 。 A．使单链表至少有一结点 B．标志表中首结点位置

C．方便运算的实现 D．说明单链表是线性表的链式存储实现 14、下列有关线性表的叙述中，正确的是 。 A．线性表中的元素之间是线性关系 B．线性表中至少有一个元素

C．线性表中任何一个元素有且仅有一个直接前趋 D．线性表中任何一个元素有且仅有一个直接后继

15、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的 。

A．直接前趋 B．直接后继 C．开始结点 D．终端结点

16、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。 A．n B.2n-1 C.2n D.n-1 17、链表不具有的特点是 。

A．随机访问 B．不必事先估计存储空间 C．插入删除时不需移动元素 D．所需的空间与线性表成正比 18、一个顺序表一旦说明，其中可用空间大小 。

A．已固定 B．可以改变 C．不能固定 D．动态变化

19、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 存储方式最节省时间。

A.顺序表 B．单链表 C．双向链表 D．单循环链表 20、下面关于线性表的叙述中，错误的是 。

A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于进行插入和删除操作

21、在长度为n的顺序线性表中删除第i个元素(1<=i<=n)，则需要向前移动的元素个数为（ ）。 A．n-i B． n+1-i C． n-1-i D． i

二 填空题

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

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

4

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