发布时间 : 星期一 文章山东专升本计算机专业数据结构练习题 - 图文更新完毕开始阅读
济南铁道职业技术学院 专升本辅导教材 数据结构
(10)若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144则第1个数据元素的存储地址是101。 ( 100 )
(11)在长度为n的顺序表的第i个位置插入一个数据元素，i的合法值为1≤i≤N。 ( ) (12)删除长度为n的顺序表的第i个数据元素，i的合法值为1≤i≤n。 ( ) (13)在长度为n的顺序表中插入一个数据元素的时间复杂度为O(n)。 ( ) (14)线性表的链式存储结构不必占用地址连续的存储空间。 ( ) (15)链表中的每个链结点占用的存储空间不必连续。 ( )
(16)一个链结点的地址是指该链结点占用的若干存储单元的第一个单元的地址。 ( ) (17)非空线性链表的最后那个链结点的指针域不能为空，应该存放NULL。 ( ) (18)所谓空链表是指没有任何链结点的链表。 ( ) (19)任何一个链表都可以根据需要设置一个头结点。 ( ) (20)每个链表的前面都必须设置一个头结点。 ( )
(21)线性链表(单向链表)中的每个链结点只有后继结点，没有前驱结点。 ( ) (22)一个空的链表不占用任何存储空间。 ( )
(23)若指针变量list指向一个空链表，则list中什么也没有。 ( ) (24)无论出现在算法的什么地方，符号p->data表示的意思都一样。 ( ) (25)在算法中，符号p->link表示p所指的下一个链结点的地址。 ( )
(26)删除非空线性链表的第一个链结点只需执行语句list=list->link。 ( )
(27)循环链表的最后那个链结点的指针域中存放着链表最前面那个结点的地址。 ( ) (28)设置一个指针变量，它可以遍历整个循环链表。 ( )
(29)双向链表的头结点指针要比线性链表的头结点指针占用更多的存储空间。 ( ) (30)在链结点数目相同的前提下，双向链表占用的空间是线性链表的2倍。 ( ) 单项选择题。
(1)一个顺序表所占用的存储空间大小与——无关。
A．表的长度 B．元素的存放顺序 C．元素的类型 D。元素中各字段的类型
(2)设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地 址是指它所占用的单元的
A．第1个单元的地址 B．第2个单元的地址 C．第3个单元的地址 n第4个单元的地址
(3)若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100， 则第12个元素的存储地址是． 。 A．112 B．144 C．148 0．412
(4)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值 应该是——。
A．i>O B．i≤n C．1≤i≤n D．1≤i≤n+1
(5)若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是 A．i>O B．i≤n C．1≤i≤n D。1≤i≤n十1
(6)若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表 中——个数据元素。
A．n-i B．n+i C．n-i+l D．n-i-1
(7)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动 表中——个元素。 。
A．i B．n+i C．n-i+l D．n-i-1
(8)若频繁地对线性表进行插入和删除操作，该线性表应该采用——存储结构。
第 9 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
A．散列 B．顺序 C．链式 D．索引 (9)链表中所占用的存储单元地址一定是 。
A．无序的 B．连续的 C．不连续的 D．部分连续的 (10)链表中的每一个链结点所占用的存储单元——。
A．不必连续 B．一定连续 C．部分连续 D．连续与否无所谓 (11)与单链表相比，双向链表的优点之一是 。 A．插入、删除操作更简单 B．可以进行随机访问 C．可以省略头结点指针 D．顺序访问相邻结点更灵活
(12)若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域中存 放的是——。
A．1ist的地址 B．1ist的内容
C．1ist指的链结点的值 D．链表第一个链结点的地址
(13)若list是某带头结点的循环链表的头结点指针，当p(p与list同类型)指向链表的最后那 个链结点时，——。
A．该结点的指针域为空 B．p为空
C．p的内容与头结点的内容相同 D．该链结点指针域内容与list的内容相同
(14)若listl和list2分别为一个单链表与一个双向链表的第一个结点的指针，则——。 A．1ist2比listl占用更多的存储单元 B．1istl与list2占用相同的存储单元
C．1istl和list2应该是相同类型的指针变量D．双向链表比单链表占用更多的存储单元 (15)在表达式中，符号p->link表示——。 A．p所指的链结点的指针域(位置) B．p所指的链结点的指针域的内容
C．p所指的链结点的下一个链结点的地址
D．p所指的链结点的下一个链结点的地址(出现在表达式中)
(16)在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较 ——个链结点。
A．n B．n／2 C．(n+1)／2 D．(n-1)／Q
(17)从一个具有n个链结点的有序线性链表(即链结点按照数据域值有序链接)中插入一个 新的链结点，并且仍然保持链表有序的时间复杂度为——。 A．O(1) B．O(n) C．O( n(2) ) D．O( log2(n) )
(18)给定具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为——。 A．O(1) B．O(n) C．O( n(2) ) D．O( log2(n) )
(19)在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执 行——。
A．q->link=p；p->link=q； B．q->link=p->link；p->link=q； C．q->link=p->link；p=q； D．p->link=q；q->link=p；
(20)若删除非空线性链表中由p所指的链结点的直接后继链结点的过程是依次执行 ________.
A．r=p->link；p->link=r；free(r)；
B．r=p->link；p->link=r->link；free(r)； C．r=p->link；p->link=r->link；free(p)； D．p->link=p->link->link；free(p)；
(21)在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的动作依次 为：p->llink=Q；p->rlink=q->rlink；q->rlink=p；——。(空白处为一条赋值
第 10 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
语句)
A．q->llink=p B．q->rlink->llink=p
C．p->fiink->llink=p D．p->llink->llink=p
(22)在非空双向循环链表中由q所指的那个链结点前面插入一个p所指的链结点的动作对 应的语句依次为：p->rlink=Q；p->llink=q->llink；q->[1ink=p；——。(空白 处为一条赋值语句)
A．q->rlink=p； B．q->llink->rlink=p；
C．p->rlink->rlink=p； D．p->llink->rlink=p；
(23)在包含有1000个数据元素的线性表中实现如下四个操作，所需要的执行时间最长的是 一O
A．线性表采用顺序存储结构，在第10个元素后面插入一个新的元素 B．线性表采用链式存储结构，在第10个元素后面插入一个新的元素 C．线性表采用顺序存储结构，删除第990个元素 D．线性表采用链式存储结构，删除p所指的链结点 2．3填空题。
(1)顺序表是一种——线性表。
(2)在程序设计中，描述线性表的顺序存储结构一般都用——。
(3)在——情况下，删除线性表中一个数据元素平均要移动表中近一半的元素。 (4)在顺序表的——插入一个新的数据元素不必移动任何元素。
(5)若长度为n的线性表采用顺序存储结构，在其第i个位置(1≤i≤n+1)插入一个新的数据 元素，当不溢出时，首先——，然后——，最后——。
(6)若长度为n的线性表采用顺序存储结构，删除其第i个元素(1≤i≤n)，首先——，然 后——。
(7)若长度为n的线性表采用顺序存储结构，插入或删除一个元素的时间复杂度为——。
(8)若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素 的存储地址为——。
(9)线性表的链式存储结构主要包括——、——和——三种形式。
(10)线性表的顺序存储结构是通过——来直接反映数据元素之间的逻辑关系，而链式存 储结构则是通过——间接反映数据元素之间的逻辑关系。
(11)根据——的多少，可以将链表分为线性链表(单链表)与双向链表。
(12)若对线性表进行的操作主要不是插入和删除，则该线性表宜采用——存储结构，若 频繁地对线性表进行插入和删除操作，则该线性表宜采用——存储结构。 (13)删除由list所指的线性链表的第一个链结点是执行操作——。
(14)删除非空线性链表中由q所指的链结点(其直接前驱结点由r指出)的动作是执行语句 ——和——。
(15)在线性链表中由q所指的链结点后面插入一个地址为p的新结点的过程是依次执行操 作——和——。
(16)若p为指向循环链表中某链结点的指针变量，判断循环链表是否只有一个链结点的标志 是——。
(17)删除非空双向链表中由q所指的链结点的过程是执行语句——和——。 (18)在具有n个链结点的链表的已知位置插入一个链结点的时间复杂度为——。 (19)在具有n个链结点的链表中查找一个链结点的时间复杂度为——。 (20)一元多项式f(x)二9x1’—4x8+3x—5的线性链表表示为——。
2．4 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。
第 11 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
2．5 已知长度为n的线性表A采用顺序存储结构，请写出逆转该线性表的算法，即由A二(al，a2，?，An-l，An)产生A'：(An-1，An，?，A1，A2)，要求在逆转过程中用最少的附加空间(即用尽可能少的辅助变量)。
2．6 已知线性表A的长度为n，并且采用顺序存储结构，请写一算法，删除该线性表中所有值为d的数据元素，并讨论算法的时间复杂度。
2．7 已知长度为n的线性表A采用顺序存储结构，并且每个数据元素均为一个无符号整数，请写一算法，删除线性表中的所有奇数。
2．8 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)的算法，该算法删除线性表中原来序号为奇数的那些数据元素。 2．9 已知长度为n的线性表A采用顺序存储结构，写一算法，删除表中重复出现的所有数据元素 要求：剩余元素的相对位置保持不变。
2．10 已知长度为n的线性表A采用顺序存储结构，并且元素按值的大小非递减排列，请写一算法，在线性表中插入一个新的数据元素让em，要求插入以后线性表中元素仍然保持按值的大小非递减排列。 2．11 已知长度为n的线性表A采用顺序存储结构，写一算法，删除所有值大于x且小于y的数据元素。
2．12 请写一算法，通过键盘输入一系列数据元素，建立一个长度为n、且不包含重复元素的线性表A。这里，设线性表A采用的存储结构为顺序存储结构，并且假设空间足够。
2。13 已知线性表A与线性表B的长度分别为n与m，并且都采用顺序存储结构，写一算法，在线性表A的第i个位置插入线性表B。约定：不考虑存储空间溢出问题。
2．14 已知非空线性链表的第一个链结点的存储地址为list，写出删除该链表第i个链结点的算法。 2．15 已知非空线性链表第一个链结点的存储地址为1ist，试写出删除链表中从第i个链结点开始的(包括第i个链结点本身)连续k个链结点的算法。
2．16 已知线性链表第一个链结点的存储地址为1ist，写一算法，把该链表中数据域值为d的所有链结点的数据域值修改为p。
2．17 已知线性链表第一个链结点指针为list，写一算法，删除链表中数据域值最大的那个链结点。 2．18 已知线性链表第一个链结点指针为list，写一算法》，j断该链表是否是有序链表(即链结点是否按照数据域大小链接)，若是，算法返回1，否则返回—1。
2．19 已知线性链表第一个链结点指针为1ist，写一算法，交换p所指链结点与其下一个链结点的位置(设p指向的不是链表最后那个链结点)。
2．20 已知非空线性链表第一个链结点由list指出，请写一算法，将链表中数据域值最小的链结点移到链表最前面。
2．21 已知非空线性链表第一个结点的指针为list，试编写一算法按递减次序打印各链结点数据域的内容(提示：在链表中打出最大值结点，打印之后将其删除。反复执行，直到链表为空时为止)。
2．22 已知一个不带头结点也无头指针变量，并且长度大于1的循环链表，试写一算法，删除p所指链结点的直接前驱结点。
2．23 已知带有头结点的循环链表中头结点的指针为list，试写出删除并释放数据域内容为x的所有结点的算法。
2．24 已知线性链表第一个链结点的指针为list，试写一算法，删除数据域值相同的多余结点，即： 若链表中有多个结点具有相同的数据域值，只保留其中一个结点，其余结点均从链表中的最后删去，使得到的链表中所有结点的数据域值都不相同。
2．25 设线性表X=(x1，x2，?，Xn)与Y=(yl，y2，?，ym)都采用链式存储结构(两个链表第一个结点的指针不妨用X与Y分9U表示)。试写一个算法归并这两个线性链表为一个线性链表，使 ((x1，Y1，x2，y2，?，xm,Ym，Xm+1，?，Xn) 当m≤n时 ((x1，Y1，x2，y2，?，xn，yn，yn+1，?，ym) 当m>n时
第 12 页 共 63 页