数据结构导论练习题

1、一、选择题1.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。 Aq一）nextp一）next；p一）nextq； Bp一）nextq一）next；qp； Cq一）nextp一）next；p一）nextq； Dp一）nextq一）next； q一）nextp；2. 在一个顺序队列中，队首指针指向队首元素的位置：A前一个 B后一个 C当前3. 下列数据组织形式中，（      ）的结点按逻辑关系依次排列形成一个“锁链”。A.集合       

2、  B.树形结构 C.线性结构     D.图状结构4. 数据结构可以形式化地定义为（S，），其中S指某种逻辑结构，是指（      ）A.S上的算法      B.S的存储结构 C.在S上的一个基本运算集   D.在S上的所有数据元素5. 下列说法正确的是（      ）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存

3、中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算6. 设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（      ）A.s->next=p->next;p->next=s； B.p->next=s;s->next=p->next；C.s->next=p->next;p->nex

4、t=s;交换p->data和s->data； D.p=s;s->next=p；7. 将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（      ）A.无左、右孩子  B.有左孩子，无右孩子 C.有右孩子，无左孩子D.有左、右孩子8. 采用线性探测法解决冲突问题，所产生的一系列后继散列地址（      ）A.必须大于等于原散列地址 B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址 D.地址大小没有具体限制9. 用快速排序方法对包含

5、有n个关键字的序列进行排序，最坏情况下执行的时间复杂度为（      ）A.O(n)        B.O(log2n) C.O(nlog2n)       D.O(n2)10. 下列数据结构中，(      )不都是线性结构。A.栈和队列         &

6、#160; B.队列和数组 C.数组和串         D.文件和队列11. 为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用(      )方式。A.顺序存储       B.链式存储 C.索引存储    D.散列存储12. 具有100个结点的完全二叉树的深度为(    

7、;  )A.6               B.7              C.8                D.913. 顺序查找法与二分查找法对存储结

8、构的要求是(      )A.顺序查找与二分查找均只适用于顺序表B.顺序查找与二分查找既适用于顺序表，也适用于链表C.顺序查找只适用于顺序表D.二分查找只适用于顺序表14. 在开散列表上，每个地址单元所链接的同义词表(      )A.其键值相同       B.其元素值相同 C.其散列地址相同      D.其含义相同15. 一组记录的关键码为(46，79，56，3

9、8，40，84)，则利用快速排序方法，以第一个记录为基准得到的一次划分结果为(      )A.38，40，46，56，79，84              B.40，38，46，79，56，84C.40，38，46，56，79，84              D.40，38，46，84，

10、56，7916. 下列说法正确的是（）A数据是数据元素的基本单位 B数据元素是数据项中不可分割的最小标识单位C数据可由若干个数据元素构成 D数据项可由若干个数据元素构成17. 数据结构的基本任务是（）A逻辑结构和存储结构的设计   B数据结构的运算实现C数据结构的评价与选择    D数据结构的设计与实现18. 在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）AO（1）      BO（n） CO（nlog2n）  &

11、#160;  DO(n2)19. 顺序存储的线性表（a1,a2,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（）An       Bn/2 Cn+1       D(n+1)/220. 下列数据组织形式中，（）的各个结点可以任意邻接。A集合       B树形结构 C线性结构      D图状

12、结构21. 在线性表的下列存储结构中，读取元素花费时间最少的是（）A单链表      B双链表 C循环链表      D顺序表22. 除根结点外，树上每个结点（）A可有任意多个孩子、任意多个双亲 B可有任意多个孩子、一个双亲C可有一个孩子、任意多个双亲 D只有一个孩子、一个双亲23. 若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（）A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较24.

13、下列查找中，效率最高的查找方法是（）A.顺序查找       B.折半查找 C.索引顺序查找      D.分块查找25. 直接插入排序算法，其时间复杂性为（）A.O(1)        B.O(n) C.O(nlog2n)       D.O(n2)26. 数据的四种基本逻辑结构是指(  

14、0;  )A.数组、链表、树、图形结构                  B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构           D.集合、线性结构、树、图形结构27. 数据结构中，通常采用两种方法衡量算法的时间复杂性，即(     )

15、A.最大时间复杂性和最小时间复杂性          B.最好时间复杂性和最坏时间复杂性C.部分时间复杂性和总体时间复杂性 D.平均时间复杂性和最坏时间复杂性28. 下列关于线性表的叙述中，不正确的是(     )A.线性表是n个结点的有穷序列 B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继D.线性表结点间的逻辑关系是1:1的联系29. 在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是(  &

16、#160;  )A.p=p->next             B.p->next=p->next C.p->next=p->next->next   D.p->next=p30. 栈和队列(     )A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没

17、有共同之处31. 要解决散列引起的冲突问题，常采用的方法有(     )A.数字分析法、平方取中法         B.数字分析法、线性探测法C.二次探测法、平方取中法 D.二次探测法、链地址法32. 若在长度为n的顺序表中插入一个结点，则其结点的移动次数(      )A.最少为0，最多为n     B.最少为1，最多为nC.最少为0，最多为n+1  &#

18、160; D.最少为1，最多为n+133. 在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是(      )A.s->next=q；p->next=s->next B.p->next=q；p->next=sC.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next34. 若有一串数字5、6、7、8入栈，则其不可能的输出序列为(  

19、0;   )A.5、6、7、8       B.8、7、6、5 C.8、7、5、6        D.5、6、8、735. 数据的四种基本存储结构是指（）A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B顺序存储结构、索引存储结构、链式存储结构、散列存储结构C顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构36. 有关栈的描述，正确的是（）A.栈是一种先进先出的

20、特殊的线性表 B.只能从栈顶执行插入、删除操作C.只能从栈顶执行插入、栈底执行删除 D.栈顶和栈底均可执行插入、删除操作37. 关于二叉树性质的描述，正确的是（）A.二叉树结点的个数可以为0B.二叉树至少含有一个根结点C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子38. 具有4个结点的二叉树可有（）A.4种形态  B.7种形态 C.10种形态  D.11种形态39. 下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A.集合  B.线性结构 C.树形结构 D.图形结构40. 计算

21、机算法指的是(      )。  A.计算方法       B.排序方法  C.解决某一问题的有限运算序列     D.调度方法41. 循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是(      )。  A.(rear-front+m) MOD m      B.rea

22、r-front+1 C.rear-front-1      D.rear-front42. 栈和队列的共同特点是(      )。  A.都是先进后出      B.都是先进先出   C.只允许在端点处插入和删除元素      D.没有共同点43. 深度为n的二叉树中所含叶子结点的个数最多为(      )个。  A.2n  &

23、#160;   B.n      C.2n-1      D.2n-144. 对线性表进行二分查找时，要求线性表必须(      )。   A.以顺序方式存储    B.以链接方式存储   C.以顺序方式存储，且结点按关键字有序排序   D.以链接方式存储，且结点按关键字有序排序2008-12-5添加1下列关于数据结构的叙述中，错误的是（ ）A、数据结构是相关数据元素的集合 B

24、、数据元素是由若干数据项构成的C、数据结构就是文件 D、数据结构分逻辑结构和物理结构2数据的逻辑结构和物理结构之间的关系是（ ）A、逻辑结构反映物理结构 B、物理结构反映逻辑结构C、逻辑结构和物理结构相互反映 D、逻辑结构和物理结构无任何关系3在数据的存储结构中，结点（ ）A、就是数据元素 B、不是数据元素 C、就是系统数据 D、元素数据和系统数据的组合体4关于算法效率，下面说法正确的是（ ）A、执行时间越快越好 B、占用空间越少越好 C、既要执行快又要空间少D、时空折中5向顺序表插入结点时，（ ）A、一定要移动结点 B、一定不要移动结点 C、不一定要移动结点D、不知道是否要移动结点6单链表的

25、结点中含有一个（ ）指针A、向前 B、向后 C、空 D、任意7下列关于查找的说法中，正确的是（ ）A、只要给定了查找值，就一定能找到一个结点B、如果给定值是关于查找表主关键字的，就一定能找到一个结点C、查找表可以是关于关键字的有序表，或无序表D、查找过程是对结点进行比较和交换的过程8栈是一种特殊的（ ）表，其插入、删除操作在表的同一端进行A、链表 B、顺序表 C、线性表 D、循环链表9判断一个顺序栈是否为空栈的依据是（ ）A、栈顶指针栈底指针 B、栈顶指针< 栈底指针 C、栈顶指针> 栈底指针D、测试栈的每一个元素是否都是空栈10出栈操作的结果是（ ）A、取出并返回栈顶元素值 B、

26、将栈顶元素清空 C、移动栈顶指针指向下一个元素 D、向栈顶方向依次移动一个元素11设一个栈存储在一维数组stackm中，并设栈底为第m个数组元素，栈顶指针为top。在执行压栈操作中，首先执行（ ）A、top=top+1 B、top=top-1 C、top=m D、top=m-112对于一个用一维数组存储一个顺序队列的情况，当（ ）时队列为空A、队头指针队尾指针 B、队头指针队尾指针0C、队尾指针0 D、队头指针013下列关于子串的的说法中，错误的是（ ）A、一个串是自身的子串 B、空串是任何串的子串 C、子串的长度一定小于主串的长度 D、子串是包含在主串中的串14若树的度为3，则（ ）A、每个

27、结点都有3个分支 B、根结点有3个分支 C、每个结点有不超过3个分支 D、树最多有3层15已知一棵二叉树的（ ），就可画出这棵二叉树A、先根遍历和后根遍历序列 B、先根遍历序列 C、后根遍历序列D、先根遍历和中根遍历序列16下列关于树的说法中，错误的是（ ）A、树的叶子结点没有后继结点 B、树的任何一个结点必在一个层子上C、一棵非空树必有一个根结点，它没有前驱结点，但有多个后继结点D、一般树都是无序树17对一个具有n个顶点和e条边的无向图，若采用邻接表表示，则邻接表中所用结点个数为（ ）A、e/2 B、e C、2e D、ne18在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍

28、A、1/2 B、1 C、2 D、419具有5个顶点的无向图至少应有（ ）条边，才能确保图是一个连通的A、5 B、6 C、4 D、820存储在散列表中的结点的顺序是（ ）的A、时间顺序 B、关键字顺序 C、随机顺序 D、不可预测顺序21散列的查找效率与（ ）有关A、结点个数 B、散列表大小 C、散列函数 D、散列函数和解决冲突的方法二、填空题1数据的逻辑结构被分为_、_、_和_四种。2对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度_为，在表尾插入元素的时间复杂度为_。3在广义表的存储结构中，每个结点均包含有_个域。4当用长度为N的数组顺序存储一个栈时，假定角topN表示栈空，则表

29、示栈满的条件为_。5.在一棵二叉树中，第5层上的结点数最多为_。6. 在线性表的散列存储中，处理冲突有_和_两种方法。7.快速排序在平均情况下的空间复杂度为_，在最坏情况下的空间复杂度为_。8. 线性表(a0,a1,a2,an)(n1)中，每个元素占c个存储单元，m为a0的首地址，则按顺序存储方式存储线性表，an的存储地址是_。9. 在栈的顺序实现中，设栈顶指针为top，栈空的条件为_。10. 队列中允许进行插入的一端称为_。11. 深度为90的满二叉树上，第11层有_个结点。12. 通常采用拉链法、线性探测法、多重散列法、二次探测法、公共溢出区法等解决散列地址冲突问题，若要避免“堆积”现象发

30、生应采用_。13. 对有序表(25,30,32,38,47,54,62,68,90,95)用二分查找法查找32，则所需的比较次数为 _。14. 树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的_关系。15. 下列程序段的时间复杂性的量级为_。   for (i=1;i<n;i+)      for(j=i;j<n;j+)         t=t+116. 设某非空单链表，其结点形式为  

31、             ， 若要删除指针q所指结点的直接后继结点，则需执行下列语句序列：   p=q->next;_;free(p);17. 队列可以看成是一种运算受限制的线性表，也称为_线性表。18. 表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_和散列存储方式。19. 队列中允许进行删除的一端为_。20. 在顺序存储的线性表（a1,a2，an）中的第i (1in)个元素之前插入一个元素，则需向后移动_个元素。21. 在栈

32、的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：_；sq -> datasq -> top=x；22. 对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是_。23. 快速排序法在待排序数据_的情况下最不利于发挥其长处。24. 从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和_。25. 对顺序表执行插入操作，其插入算法的平均时间复杂性为_。26. 在具有n个单元、且采用顺序存储的循环队列中，队满时共有_个元素。27. 若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则循环队

33、列为空的条件是_。28. 树的遍历主要有先根遍历、后根遍历和_三种。29. 在最好的情况下，对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为_次。30. 判断带头结点head的单链表为空的条件是_。31. 若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为_。32若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是_。33. 若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为_。34. 图主要采用_两种存储结构存放。35. 对顺序表执行删除操作，其删除算法的平

34、均时间复杂性为_。36. 若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为_。37. 一个算法通常可从正确性、易读性、健壮性和_等四个方面评价、分析。38. 对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行_趟起泡。39. 通常从四个方面评价算法的质量：_、_、_和_。40. 设head为单链表的头结点，则判断单链表为空的条件是：_。41. 直接插入排序需要_个记录的辅助空间。42. 在插入和选择排序中，若初始数据基本正序，则选用_；若初始数据基本反序，则选用_。43.三、算法阅读1Void AA (List&L) InitList(L); InsertRear(L,30); InsertFront(L,50); Int a4 = 5, 8, 12, 15; For (int I=0; i<4; i+) InsertRear