内容发布更新时间 : 2024/12/23 16:47:48星期一 下面是文章的全部内容请认真阅读。
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