数据结构复习题答案：绪论 问答题
1、解答：通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点：
（1）程序运行时所需输入的数据总量。 （2）计算机执行每条指令所需的时间。 （3）程序中指令重复执行的次数。
2、答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。 3、答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。
2 线性表
沈阳理工大学应用技术学院
信息与控制学院 计算机科学与技术教研室
2011-5-8
- 9 -
- 10 -
数据结构复习题：线性表 单选题
1、在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动_____个元素。 2、从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较__(n+1)/2___个结点。
3、在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行_____。 4、线性表是_____ 。
5、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的_____个元素。
6、线性表采用链式存储时，其地址_____。
7、设单链表中指针p指着结点m，指针f指着将要插入的新结点x，当x插在链表中最后一个结点m之后时，只要先修改_____后修改p->link=f即可。
8、在双向链表存储结构中，删除p所指的结点时需修改指针_____。
9、在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针_____。 10、根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和_____。 11、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上_____。 12、链表不具备的特点是_______。
13、不带头结点的单链表head为空的判定条件是______。 14、带头结点的单链表的head为空的判定条件是______。 15、带头结点的双循环表L为空表的条件是__L->next==L____。 16、非空的循环单链表head的尾结点(由p所指向)满足_______。
17、在循环双链表的p所指结点之前插入s所指结点的操作是_______。
18、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用___带头结点的双循环链表___存储方式最节省运算时间。
19、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用___仅有尾指针的单循环链表__存储方式最节省运算时间。
20、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是_______。
21、如果最常用的操作是取第i个结点及其前驱，则采用___顺序表___存储方式最节省时间。
22、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是______。
23、在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行____删除单链表中的最后一个元素____操作与链表的长度有关。
24、设线性表有n个元素，以下算法中，_______在顺序表上实现比在链表上实现效率更高。
25、设线性表中有2n个元素，算法___删除所有值为x的元素____，在单链表上实现要比在顺序表上实现效率更高。
26、与单链表相比，双链表的优点之一是________。 27、如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最后使用___只有表头指针没有表尾指针的循环双链表_____。 28、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用_______。
29、设有两个长度为n的单链表，结点类型相同。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_______。
30、在长度为n的______上，删除第一个结点，其算法的时间复度为O(n)。
31、将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是__n___。
- 11 -
32、带头结点的单链表L为空的判定条件是______。
33、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_______。 34、在一个长度为n(n>1)的带头结点的单链表h上，，另设有尾指针r(指向尾结点)，执行_______操作与链表的长度有关。
35、在一个双链表中，在*p结点之后插入结点*q的操作是______。 36、在一个双链表中，在*p结点之前插入*q结点的操作是______。 37、在一个双链表达式，删除*p结点的操作是_______。
38、在一个双链表中，删除*p结点之后的一个结点的操作是________。 39、非空的循环单链表L的尾结点(由p所指向)满足______。 40、带头结点的双循环链表L为空表的条件是______。
41、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_____带头结点的循环双链表____存储方式最节省运算时间。
42、如果对含有n(n>1)个元素的线性表的运算只有4种:删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用____只有头结点指针没有尾结点指针的循环双链表____。 43、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用____仅有尾结点指针的单循环链表___存储方式最节省运算时间。
44、设有两个长度为n的单链表，结点类型相同，若以h1为头结点的链表是非循环的，以h2为头结点指针的链表是循环的，则________。
45、在长度驎n(n>1)的___只有首结点指针h的不带头结点的循环单链表___上，删除第一个元素，其算法的时间复杂度为O(n)。
46、元素A、B、C、D依次进顺序栈后，栈顶元素是_______，栈底元素是______。 47、经过以下栈运算后，X的值是______。
InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);
48、经过以下的栈运算后，StackEmpty(s)的值是______。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)
49、设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是______。 50、若线性表最常用的运算是存取第i个元素及其前驱的值,则采用______存储方式节省时间. 51、链表不具备的特点是______.
52、在一个长度为n的顺序存储的线性表中，向第i个元素(1<=i<=n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素． 53、在一个长度为n的顺序存储的线性表中，删除第i个元素(1<=i<=n)时，需要从前向后依次前移____n-i_____个元素．
54、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，查找每个元素的概率都相等）为（ ）．
57、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_________。
数据结构复习题：线性表 判断题
1、顺序存储的线性表可以随机存取。
2、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象。T
3、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。
- 12 -
相关推荐：
loading