数据结构等级考试讲解

1、数据结构与算法 例题分析一、选择题1数据的 包括集合、线性结构、树型结构和图状结构四种基本类型。A) 算法描述 B) 基本运算 C) 逻辑结构 D) 存储结构 答案 C 分析 数据结构是数据元素之间逻辑关系的整体。 根据数据元素之间关系的不同特性， 数据的逻辑 结构通常包括集合、线性结构、树型结构和图状结构四种基本类型。2中任何两个结点之间都没有逻辑关系。A) 集合 B) 图状结构 C) 树型结构 D) 线性结构 答案 A 分析 树型结构具有分支、 层次特性， 其形态有点像自然界中的树。 集合中任何两个结点之间都没 有逻辑关系，组织形式松散。图状结构最复杂，其中的各个结点按逻辑关系互相关联，

2、任何两个结点都 可以邻接。线性结构中结点按逻辑关系依次排列形成一条“链” 。3数据的存储结构包括顺序、 、索引和散列四种基本类型。A) 向量 B) 数组 C) 集合 D) 链接 答案 D 分析 数据的计算机内部表示称为数据的存储结构。通常， 存储结点之间有四种关联方式， 称为四种基本存储方式，即：顺序存储、链式存储、索引存储和散列存储。4.计算机算法指的是 _。A)计算方法B)调度方法C)排序方法D)解决某一问题的有限运算序列答案 D分析 算法的定义是算法规定了求解给定类型问题所需的所有“处理方法与步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被求解，所以本题应选D。5下面 的时间复

3、杂性最好，即执行时间最短。3A)O(n) B)O(nlog2n) C)O(log2n) D)O(n 3) 答案 C 分析 算法的时间复杂性的数量级采用大O 表示，通常有常量级、 对数级、线性与对数乘积级、 平23 方级、立方级、指数级等级别，对应量级表示依次为O(1) ，O(log 2n) ，O(n) ， O(nlog 2n)，O(n2)，O(n3)，O(2n) 。当 n 较大时，量级越靠前的算法，其运行时间越短，或者说该算法效率越高。所以，上述四个 选项中应选 C。6把算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 (1) 和 (2) 。(1) A) 可实现性 B) 时间复杂度

4、C) 困难度 D) 计算有效性(2) A) 可行性 B) 高效性 C) 可实现性 D) 空间复杂度 答案 (1)B (2)D 分析 算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。 算法的计算量 是算法的时间复杂性，算法所需存储空间大小是算法的空间复杂性。7.在一个长度为n的顺序表中，向第i个元素(1 i n+1)位置插入一个新元素时，需要从后向前依次后移 个元素。A) n-i B) i C) n-i-1 D) n-i+l 答案 D分析线性表的插入运算是指在表的第i (1 n ext=pB)P=P-n ext-n extC)p-next=p-next-next D)p=p-

5、next; p_next=p-next-next答案C分析假设q为p指针所指向的结点的后继结点，则q=p-next，若要删除q，应将q的链域q-next的值传给 p 指针的链域 p-next，即 p-next=p-next-next。14在一个头指针为 ph的单链表中，若要在指针 q所指结点的后面插入一个由指针p所指向的结点,则执行操作。A)p- next=q- nextC)q- next=p-n ext答案B;q=pB)p-n ext=q- next;p_next=qD)q_next=p-next;q_next=p;p_next=q_next分析若要在指针q所指结点的后面插入一个由指针p所指

6、向的结点，应将结点p的链域p-next指向结点 q的后继结点(q-next);将结点q的链域 q-next改为指向结点po相应的操作为p-next=q-next : q-next=p 。15 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省时间。A)单链表 B)双链表 C)单循环链表 D) 带头结点的双循环链表答案D分析在单链表中，无论是在最后一个结点之后插入一个结点，还是删除最后一个结点，都必须首先从头指针开始顺序往下找，直至到达最后一个结点时才进行插入或删除操作。所以，采用这种存储方式的插入和删除操作并不方便。双链表、单循环链表与单链表一样，插入

7、、删除操作都不方便。在上述 选项中，只有带头结点的双循环链表可以通过头结点的链域ptior迅速地找到链表的最后一个结点，以便进行插入、删除操作。故采用带头结点的双循环链表存储方式最节省时间。16.在循环双链表的A)p- next=S ;p_n ext-prior=Ss-prior=ps-n ext=p-n ext C)p-n ext=S ;s-prior=pp_n ext-prior=S s-n ext=p-n ext答案Dp结点之后插入s结点的操作是 B)s-prior=p ; ；s-next=p-next ;p_next=S ; ;p_next-prior=S ;D)s-prior=p ;

8、 s-next=p-next ;p_next-prior=S ;p_next=S ;分析对于A选项，p-next指向的是p所指结点的后继结点，执行第一条语句后，s所指结点变 为p所指结点的后继结点，造成 p所指结点原来的后继结点丢失。故选项 A不正确。对于选项 B,错误 发生在第三、四条语句，第三条语句将 s所指结点指定为p所指结点的后继结点，而第四条语句又将 p 所指结点的后继结点即 s所指结点的直接前趋结点定义为 s，前后冲突。故选项 B也不正确。选项C与 选项A的错误类似。只有 D选项正确。17采用链接方式存储线性表的优点是 。A) 便于随机存取 B) 花费的存储空间较顺序存储少C) 便

9、于插入和删除操作 D) 数据元素的物理顺序和逻辑顺序相同 答案 C 分析 在链表上，对实现读表元运算必须对表结点进行扫描，其时间复杂度为O(n) ，故选项 A 不对。而插入和删除操作可通过修改链域的指针来完成，无须移动其他有关结点，这是链表的一个优点。故选项C正确。选项B和D用来描述链表不正确。 链表是通过指针来反映数据元素间的逻辑关系，因此，链表中数据元素的物理顺序与逻辑顺序可以不相同，但链表花费的存储空间比顺序存储多。18栈的插入和删除操作在 进行。A) 栈底 B) 栈顶 C) 指定位置 D) 任意位置 答案 B 分析 栈可以看成是一种 “特殊的” 线性表， 这种线性表上的插入和删除运算限

10、定在表的某一端进 行。允许进行插入和删除的这一端称为栈顶，另一端称为栈底。所以，选项B正确。19在下面栈的基本运算中，不是加工型运算的是 。A) 初始化 B) 进栈 C) 退栈 D) 判栈空 答案 D分析选项A初始化：加工型运算，其作用是设置一个空栈S。选项B进栈：加工型运算，其作用是将元素x插入栈S中，使x成为栈S的栈顶元素。选项 C退栈：加工型运算，其作用是当栈不空时， 取栈顶元素，并从栈中删除当前栈顶元素。选项D判栈空：引用型运算，功能是若栈S为空栈，则结果为真；否则结果为假。20实现递归调用属于 的应用。A) 栈 B) 数组 C) 队列 D) 二叉树 答案 A 分析 栈是一种应用范围广

11、泛的数据结构，适用于各种具有“后进先出”特性的问题。递归是一个重要的概念， 同时也是一种重要的程序设计方法。 简单地说， 如果在一个函数或数据结构的定义中又应 用了它自身，那么这个函数或数据结构称为是递归定义的，简称递归。应用栈与递归之间的关系， 可以解决很多实际问题，如计算一个数的阶乘。21在顺序栈中进行退栈操作时， 。A) 谁先谁后都可以B) 先移动栈顶指针，后取出元素C) 不分先后，同时进行 D) 先取出元素，后移动栈顶指针 答案 D 分析 在栈中进行退栈操作被称为删除栈顶元素运算。 退栈操作的步骤是先要将栈顶元素取出， 由 参数返回，并将栈顶下标减 1。22假定利用数组 an 顺序存储

12、一个栈，用 top 表示栈顶指针，用 top=n+l 表示栈空，该数组所能存 储的栈的最大长度为n则表示栈满的条件是。A)top = -1 B)top = 0 C)top l D)top = 1 答案 D 分析 栈空是指栈中不含任何数据元素， 栈满是指栈中没有任何的空闲空间。 根据本题的假设栈顶 指针top=n+l表示栈空，可知，该数组将栈底放在下标大的那端，它的下界为1，上界为n,当top=n时存入第一个元素，因为该数组所能存储的栈的最大长度为n，所以，栈满时栈顶指针top应等于1。23. 假设一个栈的输入序列为A, B, C, D, E,则下列序列中不可能是栈的输出序列的是 。A)B， C

13、，D，A，EB)E，D，A，C， BC)B, C,A,D,ED)A,E,D,C, B 答案 B 分析用1为进栈操作，0为出栈操作。对选项 A、选项C、选项D选项的输出序列可以分别通过 1101010010、1101001010、1011110000操作序列得到。而对于B选项的输出序列， 第一个输出元素是 E， 可知先执行了 11111操作，因为栈是后进先出的，所以在输出A之前，必须要输出 C, B。故选项B不可能是栈的输出序列。24. 在一个顺序存储的循环队列中，队头指针指向队头元素的 。A) 当前位置 B) 任意位置 C) 前一个位置 D) 后一个位置 答案 C 分析 循环队列的队头指针指示

14、队头元素在数组中实际位置的前一个位置，队尾指针指示队尾元素在数组中的实际位置。所以，选项 C正确。25在由n个单元组成的顺序存储的循环队列sq中，假定f和r分别为队头指针和队尾指针，则判断队满的条件是 。A)f = (r 十 1)n B) (r-1)n = f C)f = r D) (f+1)n = r 答案 A 分析 在由 n 个单元组成的循环队列 sq 中，因为出队和入队分别要将头指针 f 和尾指针 r 在循环 意义下加 1，所以某一元素出队后，若头指针已从前面追上尾指针，即sq-f = sq-r ，则当前队列为空：若某一元素入队后，尾指针已从后面追上头指针，即sq-r = sq-f ，则

15、当前队列为满。可见，仅凭等式 sq-r = sq-f 是无法区别循环队列是空还是满的。为了区分队空、队满的条件，采用下面的方 法：入队前，测试尾指针在循环意义下加 1 后是否等于头指针，若相等则认为是队满， 即判别队满的条 件是： (sq-r+1) n = sq-f 。从而也保证了 sq-r = sq-f 是队空的判别条件。注意：队满条件使 得循环队列中，始终有一个元素的空间(即队头指针指示的结点)是空的，即有n个单元组成的循环队列 只能表示长度不超过 n-1 的队列。26. 设循环队列中数组的下标范围是1n,其头尾指针分别为f和r,则其元素个数为 。A) r-f B) r-f+l C) (r

16、-f) mod (n+1) D) (r-f+n) mod n 答案 D分析因为队头指针指示的结点不用于存储队列元素，只起标志作用。所以，当rf时，队内元素个数为 (r-f) mod n ；当 rnext=head 。答案head-n ext=head9 在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。分析双链表的结点形式为：PriorDatan ext其中，链域prior，和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋指针和后继指针链接在一起。在双链表中找结点的前趋和后继都很容易。答案前趋；后继10.在一个双向链表

17、中删除指针p所指向的结点时，需要对 p-next-prior 指针域赋值为 。分析双向链表中每个结点包含有两个指针域prior和next，分别指向其前趋结点和后继结点。删除指针p所指向的结点时，结点p的后继结点(p-next)的prior指针域应指向结点 p的前趋结点p-prior 。即 p-nex-prior = p-prior 。答案p-prior11 存储结点中数据域占用的存储量与整个结点占用存储量之比称为。分析存储结点中数据域占用的存储量与整个结点占用存储量之比称为存储密度。存储密度w1,值越大表示空间利用率越高。 顺序表的存储密度(=1)高于链表的存储密度(45,相应的令l=m+l，

18、这时，m为6,且54 r2.key ,则将两个记录交换和第三个记录的关键字比较,依次类推,直到第n - 1 个记录和第 n 个记录进行比较交换。这时最明显的效果是将关键字最大的记录换到了最后。 答案 冒泡排序数据结构与算法 练习题一、选择题1研究数据结构就是研究 。A) 数据的存储结构 B) 数据的逻辑结构C) 数据的逻辑结构和存储结构D) 数据的逻辑结构、存储结构及其数据在运算上的实现2在数据的树型结构中，数据元素之间为 的关系。A) 0: 0B)1: 1 C) 1 : n D) m : n3算法的计算量大小称为算法的 。A) 现实性 B) 复杂性 C) 效率 D) 难度4数据的最小标识单位

19、是 。A)数据结构B)文件 C)数据元素D)数据项5数据的 包括查找、插入、删除、更新、排序等操作类型。A) 逻辑结构 B) 存储结构 C) 算法描述D) 基本运算6下面关于线性表的叙述中，错误的是 。A) 线性表采用顺序存储，必须占用一片连续的存储单元B) 线性表采用链接存储，不必占用一片连续的存储单元C) 线性表采用链接存储，可以随机存取表中的任一结点D) 线性表采用顺序存储，无须为表示结点间的逻辑关系而增加额外的存储空间 7在单链表中，头结点的作用是用于标识单链表D) 用于标识首结点位置A)方便运算的实现B)C) 使单链表中至少有一个结点8在一个长度为 n 的顺序表中，删除值为x 的元素

20、需要比较和移动元素的平均次数为A)n/2 B)(n+1)/2C)n D)n+19在一个顺序表的表尾插一个元素的时间复杂性的量级为( )A)O(n) B)O(n log 2 n) C) O(1) D) O(log 2 n)10在一个单链表中，己知指针所指向的两个结点之间插入指针q 所指向的结点是指针 P 所指向的结点的前趋结点，若在指针 s 指向的结点，则执行 。A) p-next = s; s-next=qB) q-next = s; s-next=p； s-next=qC) S-next=p-next; p-next = s D) p-next=s-next 11在一个单链表中，若要在 p

21、所指向的结点之前插入一个新结点，则此算法的时间复杂性的量级为12己知指针 p 指向单链表中的某结点，则下列各组语句能删除链表中结点的是 。A)p = p_nextB)q= p_next ; q = q_nextC)p-next = p_next-nextD)q= p_next ; p= p_next ; q = p_next13在一个表头指针为ph 的单链表中，若要向表头插入一个由指针p 指向的结点，则应执行 操作。A)ph=p ； p-next=ph B)p-next=Ph； p=phC)p-next=ph-next ； ph=p D)p-next=ph-next ； ph-next=p14

22、在有 n 个结点且不带头结点的双向链表中，值为非空的链域的个数为 。A)2n+2 B)n+1 C)n-1D)2n-215非空的循环单链表 head 的尾结点 ( 有指针 p 所指 ) 满足 。A)p-next=NULLB)p-next=headC) p=NULLD)p=head16在一个带头结点的循环双向链表中，若要删除指针p 所指向的结点则执行 嗓作。A) p = p-prior； p-prior-next = p-nextB) p-prior-next = p； p-next = p-next-priorC) p-next-prior = p； p-next = p-next-nextD)

23、 p-prior-next = p-next； p-next-prior = p-priorp 所指结点的操17设 rear 是指向非空带头结点的循环单链表的尾指针，则在起始结点之前插入指针 作可表示为 。A) p-next = rear-next-nextB) p-next = rear-next ；C) p-next = rear-next-nextD) p-next = rear-next-next； rear-next = p rear-next-next = p； rear-next-next = p； rear-next-next = p-next18带头结点的循环单链表head

24、为空的判断条件是 A) head = NULL B) head != NULLC) head-next = head D) head-next = NULL19线性表的顺序存储比链接存储最有利于进行 操作。A)按值查找 B)按值插入或删除C) 表尾插入或删除 D) 表头插入或删除20线性表的链接存储比顺序存储最有利于进行 操作。A)按值查找B)按值插入或删除C)表尾插入或删除D)表头插入或删除21栈和队列的共同特点是A)没有共冋点C)都是先进后出B)都是先进先出D)只允许在端点处插入和删除元素22向顺序栈中压入元素时，是 。A) 同时进行 B) 无所谓谁先谁后C)先存入元素，后移动栈顶指针D)

25、先移动栈顶指针，后存入元素 23假定利用数组 aN 顺序存储一个栈，用 top 表示栈顶元素的下标位置，用 top= =-1 表示栈空，用 top= =N - 1 表示栈满，则该数组所能存储的栈的最大长度为A)N - 1 B)N C)N 十 1 D)N 十 224假定利用数组am 顺序存储一个栈，用top 表示栈顶指针，用top= =-1 表示空，该数组所能存储的栈的最大长度为 m当时，再做进栈运算会发生“上溢”A)top = m - 1 B)top = 0C)top = m - 2 D)top = 125假定利用数组 am顺序存储一个栈，用top表示栈顶指针，用top= =0表示栈满，该数组

26、所能存储的栈的最大长度为m当时，再做退栈运算会发生“下溢”。A)top = m-1 B)top = 0C)top = m D)top = 126.若让元素1， 2， 3， 4 依次进栈，则出栈次序不可能出现的情况。A) 3 ， 2，1，4 B) 4 ， 3， 2， 1C) 2 ， 1， 3， 4 D) 1 ， 4， 2， 327. 不是队列的基本运算。A) 设置一个空队列C) 判断一个队列是否为空队列B) 从队列中删除第 i 个元素D) 从队届插入一个新元素28. 当利用大小为 n 的数组循环顺序存储一个队列时，该队列的最大长度为 A)n 十 1 B)nC)n-1 D)n-229. 设数组 D

27、atam+1 作为循环队列 sq 的存储空间， front 成为队头指针， 入队操作的语句为 。rear 为队尾指针，则执行A)rear = rear+1B) rear = (rear+1)mC)front = (front+1) m D) rear = (rear+1) m + 130. 假定一个顺序循环队列存储于数组 an 中，其队首和队尾指针分别用 front 和 rear 表示，则判断 队满的条件为 。A) (rear - 1) n = frontB) (rear + 1) n = frontC) (front - 1) n = rear D) (front + 1) n = rear

28、31. 下列与数据的存储结构无关的术语是 。A) 栈 B) 散列表 C) 双链表 D) 二叉树32. 在一棵树中， 没有前趋结点。A) 叶子结点 B) 树根结点 C) 空结点 D)树枝结点33. 在完全二叉树中，若一个结点是叶子结点，则它没有 。A)兄弟结点B)父结点C)左子结点和右子结点D)左子结点、右子结点和兄弟结点34 .深度为n的二叉树中所含叶子结点的个数最多为 个。n-1nn 4A)2 B)n C)2D)2-135. 在一棵具有n个结点的二叉树的第i层上，最多具有 个结点。A)2iB)2i+1C)2 n D)2i-136. 在一棵具有35个结点的完全二叉树中，该树的深度为 。A)5B)6C)7D)837. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则右孩子结点的编号为 A)2iB)2i+1C)2i+2D)2i-138. 对右图的二叉树，按后根遍历得到的结点序列为。A)ABDEHICFG B)DBHEIAFCGC)DHIEBFGCA D)DHIEBAFCG39. 对长度为n的单有序表，若查找每元素的概率相等，则查找