数据结构期末考试(题集) 下载本文

2 线性表的逻辑结构

选择题

(1) 线性表是具有n个( )的有限序列。 A.数据 B.字符 C.数据元素 D.数据项

(2) 线性表是( )。 A.一个有限序列,可以为空 B.一个有限序列,不能为空 C.一个无限序列,可以为空 D.一个无限序列,不能为空

(3) 关于线性表,下列说法中正确的是( )。 A.线性表中每个元素都有一个直接前驱和一个直接后继 B.线性表中的数据元素可以具有不同的数据类型 C.线性表中数据元素的类型是确定的

D.线性表中任意一对相邻的数据元素之间存在序偶关系

(4) ( )是一个线性表。 A.由n个实数组成的集合 B.由所有实数组成的集合 C.由所有整数组成的序列 D.由n个字符组成的序列

6

3 顺序线性表

选择题

(1) 已知一维数组A采用顺序存储结构,每个元素占用4个存储单元,第9个元

素的地址为144,则第一个元素的地址是( )。 A.108 B.180 C.176 D.112

(2) 在长度为n的线性表中查找值为x的数据元素的时间复杂度为( )。 A.○(0) B.○(1) C.○(n) D.○(n2)

(3) 在一个长度为n的线性表的第i(1≤i≤n+1)个元素之前插入一个元素,需

向后移动( )个元素,删除第i(1≤i≤n)个元素时,需向前移动( )个元素。 A.n-i B.n-i+1 C.n-i D.n-i+1

(4) 线性表的顺序存储结构是一种( )的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取

(5) 顺序存储结构的优点是( )。 A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示

(6) n个结点的线性表采用数组实现,算法的时间复杂度是○(1)的操作是( )。 A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) B.在第i个结点后插入一个新结点(1≤i≤n) C.删除第i个结点(1≤i≤n) D.以上都不对

(7) 对于顺序存储的线性表,访问某个元素和增加一个元素的时间复杂度为

( )。

A.○(n)、○(n) B.○(n)、○(1) C.○(1)、○(n) D.○(1)、○(1)

(8) 顺序表的插入算法中,当n个空间已满时,可再申请增加分配m个空间,若

申请失败,则说明系统没有( )可分配的存储空间。 A.m个 B.m个连续的 C.n+m个 D.n+m个连续的

应用题

(9) 设A是一个线性表(a1,a2,?,an),采用顺序存储结构,则在等概论的前

提下,平均每插入一个元素需要移动的元素个数为多少?若元素插在ai与ai+1之间(1≤i≤n)的概率为(n-i)/(n(n-1)/2),则平均每插入一个元素所移动的元素个数是多少?

(10) 设n表示线性表中的元素个数,E表示存储数据元素所需要的存储单元大小,

7

D表示可以在数组中存储线性表的最大元素个数(D≥n),则使用顺序存储方式存储线性表需要多少存储空间?

(11) 在什么情况下线性表使用顺序存储比较好?

算法设计题

(12) 试以顺序表作存储结构,实现线性表就地逆置。

(13) 设计算法判断给定字符串是否是回文。所谓回文是正读和反读均相同的字符

串,例如abcba或abba是回文,而abcda不是回文。

(14) 设计一个时间复杂度为○(n)的算法,实现将数组A[n]中所有元素循环左移k

个位置。

(15) 已知数组A[n]中的元素为整型,设计算法将其调整为左右两部分,左边所有

元素为奇数,右边所有元素为偶数,并要求算法的时间复杂度为○(n)。

(16) 假定数组中有多个零元素,设计算法将数组中所有非零元素移到数组的前端。

(17) 顺序存储的线性表A,其数据元素为整型,设计算法将A拆成B和C两个表,

使A中值大于0的元素存入表B,值小于0的元素存入表C,要求B和C不另外设置存储空间而利用A的空间。

(18) 已知顺序表L中的元素递增有序排列,设计算法将元素x插入到表L中并保

持表L仍递增有序。

(19) 设计一个高效算法,在顺序表中删除所有元素值为x的元素,要求空间复杂度

为○(1)。

(20) 设计算法实现从顺序表L中删除所有值在x和y之间的所有元素,要求时间

性能复杂度为○(n),空间性能为○(1)。

(21) 设计算法删除顺序表中重复的元素,要求算法移动元素的次数较少并使剩余元

素间的相对次序保持不变。

(22) 给定n个记录的有序序列A[n]和m个记录的有序序列B[m],将它们归并为一

个有序序列,存放在C[n+m]中,试写出这一算法(假设A、B和C均为升序序列)。

8

4 线性链表

选择题

(1) 线性表的链接存储结构是一种( )的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取

(2) 线性表采用链接存储时,其( )。 A.地址必须是连续的 B.部分地址必须是连续的 C.地址一定是不连续的 D.地址连续与否均可以

(3) 链表不具有的特点是( )。 A.可随机访问任一元素 B.插入、删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表长度成正比

(4) 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是

( )。 A.○(1) B.○(n) C.○(n2) D.○(nlog2n1)

(5) 对于n个元素组成的线性表,建立一个单链表的时间复杂度是( )。 A.○(1) B.○(n) C.○(n2) D.○(nlog2n1)

(6) 对于n个元素组成的线性表,建立一个有序单链表的时间复杂度是( )。 A.○(1) B.○(n) C.○(n2) D.○(nlog2n1)

(7) 在单链表中删除指针p所指结点的后续结点,则执行( )。 A.p->next=p->next->next B.p->next=p->next C.p=p->next->next D.p=p->next; p->next=p->next->next

(8) 在一个单链表中,已知q所指结点是p所指结点的直接前驱,若在q和p之间

插入s所指结点,则执行( )操作。 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

(9) 在一个长度为n(n>1)的带头结点的单链表h上,另设有尾指针r指向尾结

点,执行( )操作与链表的长度有关。 A.删除单链表中的第一个元素 B.删除单链表中的最后一个元素

C.在单链表第一个元素前插入一个新元素

D.在单链表的最后一个元素后插入一个新元素

(10) 在单链表中附加头结点的目的是为了( )。 A.保证单链表中至少有一个结点 B.标识单链表中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储

9

(11) 将长度为n个单链表链接在长度为m的单链表之后的算法,其时间复杂度是

( )。 A.○(1) B.○(n) C.○(m) D.○(n+m)

(12) 循环单链表的主要优点是( )。 A.不再需要头指针了

B.从表中任一结点出发都能扫描到整个链表

C.已知某个结点的位置后,能够容易找到它的直接前驱 D.在进行插入、删除操作时,能更好地保证链表不断开

(13) 将线性表(a1,a2,?,an)组织为一个带头结点的循环单链表,设H为链表

的头指针,则链表中最后一个结点的指针域中存放的是( )。 A.变量H的地址 B.变量H的值 C.元素a1的地址 D.空指针

(14) 非空的循环单链表L的尾结点p满足( )。 A.p=NULL B.p->next=NULL C.p->next=L D.p=L

(15) 若要在○(1)的时间内实现两个循环单链表的首尾相接,则两个循环单链表应

各设一个指针,分别指向( )。 A.各自的头结点 B.各自的尾结点 C.各自的第一个元素结点 D.一个表的头结点,一个表的尾结点

(16) 设线性表非空,( )可以在○(1)的时间内在表尾插入一个新结点。 A.带头结点的单链表,有一个链表指针指向头结点 B.带头结点的循环单链表,有一个链表指针指向头结点

C.不带头结点的单链表,有一个链表指针指向表的第一个结点

D.不带头结点的循环单链表,有一个链表指针指向表中某个结点(除第一个结点外)

(17) 设指针rear指向带头结点的循环单链表的尾指针,若要删除链表的第一个元

素结点,正确的操作是( )。 A.s=rear; rear=rear->next; B.rear=rear->next;

C.rear=rear->next->next;

D.s=rear->next->next; rear->next->next=s->next;

(18) 设有两个长度为n个单链表,以h1为头指针的链表是非循环的,以h2为尾指

针的链表是循环的,则( )。

A.在两个链表上删除第一个结点的操作,其时间复杂度均为○(1) B.在两个链表的表尾插入一个结点的操作,其时间复杂度均为○(n) C.循环链表要比非循环链表占用更多的存储空间 D.循环链表要比非循环链表占用更少的存储空间

(19) 使用双链表存储线性表,其优点是可以( )。

10