计算机应用基础数据结构部分试题及答案.doc

《计算机应用基础数据结构部分试题及答案.doc》由会员分享，可在线阅读，更多相关《计算机应用基础数据结构部分试题及答案.doc（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、计算机应用基础数据结构部分试题及答案计算机应用基础数据结构部分试题及答案1选择题：选择题：1.下面程序段的时间复杂度的量级为（）for(i=1;inext= p-next-next B. p=p-next C. p=p-next-next D. next=p 27设单链表中指针 p 指向结点 ai,指针 f 指向将要插入的新结点 x，则当 x 插 在链表中两个数据元素 ai和 ai+1之间时，只要先修改（ ）后修改（）即可。 A. p-next= f B. p-next= p-next-next C. p-next=f-next D. f-next= p-next E. f-next=null

2、 F. f-next=p28设单链表中指针 p 指向结点 ai,指针 f 指向将要插入的新结点 x，则在链表 中最后一个结点 an之后插入时，只要先修改（）后修改（）即可。 A. f-next= p B. f-next= p-next C. p-next=f D. p-next= f-next E. f =null 29在一个单链表中，若要在 p 所指向的结点之后插入一个新结点，则需要相 继修改（）个指针域的值。 A. 1 B. 2 C. 3 D.4 30在一个单链表中，若要在 p 所指向的结点之前插入一个新结点，则此算法 的时间复杂性的量级为（） A. O(n) B.O(n/2) C. O(

3、1) D.O(n1/2)21-25 D B A C B 26-30 A (D.A) (B.C) B A31不带头结点的单链表 L 为空的判定条件是（） 。 A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL 32带头结点的单链表 L 为空的判定条件是（） 。 A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL 33在一个带有头结点的双向循环链表中，若要在 p 所指向的结点之前插入一 个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4

4、D.6 34在一个带有头结点的双向循环链表中，若要在 p 所指向的结点之后插入一 个 q 指针所指向的结点，则需要对 q-next 赋值为（） A. p-prior B. p-next C. p-next-next D. p-prior -prior 35对一个具有 n 个元素的线性表，建立其单链表的时间复杂度为（） A. O(n) B.O(1) C. O(n2) D.O(logn) 36线性表采用链式存储时，其地址（） A. 必须是连续的 B. 一定是不连续的 C. 部分地址必须是连续的 D. 连续与否均可以 37假定利用数组 aN顺序存储一个栈，用 top 表示栈顶指针，top= =-1

5、表示栈 空，并已知栈未满，当元素 x 进栈时所执行的操作为（） A. a-top=x B. atop-=x C. a+top=x D .atop+=x 38若已知一个栈的入栈序列是 1，2，3，.n，其输出序列为 p1, p2, p3,. pn，若 p1=n，则 pi 为（） A. i B.n-i C. n-i+1 D.不确定 39判定一个栈 S（最多元素为 m0）为空的条件是（） A. S. top!=0 B. S. top= =0 C. S. top!=m0 D .S. top= =m0 40判定一个栈 S（最多元素为 m0）为满的条件是（） A .S. top!=0 B. S. top=

6、 =0 C. S. top!=m0-1 D .S. top= =m0-131-35 A B C B A 36-40 D C C B D41一个队列的入队序列是 1，2，3，4，则队列的输出序列是（） A.4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D .3，2，4，1 42从一个顺序循环队列中删除元素时，首先需要（） A. 前移队首指针 B. 后移队首指针 C. 取出队首指针所指位置上的元素 D . 取出队尾指针所指位置上的元素 43假定一个顺序循环队列的队首和队尾指针分别用 front 和 rear 表示，则判断 队列空的条件为（） A.front+1= =rear B.re

7、ar+1= =front C. front= =0 D . front= =rear 44假定一个顺序循环队列存储于数组 aN中，其队首和队尾指针分别用 front 和 rear 表示，则判断队列满的条件为（） A. （rear-1）%N= =front B. （rear+1）%N= =front C. （front-1）%N= =rear D . （front+1）%N= =rear 45树中所有结点的度等于所有结点数加（） A.0 B.1 C.-1 D.2 46在一棵树中，每个结点最多有（）个前驱结点。 A.0 B.1 C.2 D.任意多个 47在一棵度为 3 的树中，度为 3 的结点数为

8、 2 个，度为 2 的结点数为 1 个， 度为 1 的结点点数为 2 个，则度为 0 的结点数为（）个。 A.3 B.4 C.5 D.6 48在一棵二叉树上第 5 层的结点数最多为（） A.16 B.15 C.8 D.32 49在一棵具有 n 个结点的二叉树的第 i 层上，最多具有（）个结点。 A.2i B. 2i+1 C. 2i-1 D. 2n 50一颗具有 35 个结点的完全二叉树的深度为（） A.6 B.7 C.5 D.841-45 B B D B C 46-50 B D A C A51在一棵完全二叉树中，若编号为 i 的结点存在右孩子，则右孩子结点的编 号为（） A.2i B.2i-1

9、 C.2i+1 D.2i+2 52设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包 含的结点数至少为（） A.2h B.2h-1 C.2h+1 D.h+1 53按照二叉树的定义，具有 3 个结点的二叉树有（）种状态。 A.5 B.4 C.3 D.30 54若查找每个元素的概率相等，则在长度为 n 的顺序表上查找任意元素的平 均查找长度为（） A.n B.n+1 C.（n-1）/2 D.（n+1）/2 55顺序查找法适合于存储结构为（）的线性表。 A.散列存储 B.顺序存储或链接存储 C.压缩存储 D.索引存储 56对于顺序存储的有序表（5，12，20，26，37，4

10、2，46，50，64） ，若采用 折半查找，则查找元素 26 的查找长度（） A.2 B.3 C.4 D.557对线性表进行折半查找时，要求线性表必须（） A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序 58采用折半查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 （） A. O(n2) B. O(nlogn) C. O(n) D. O(logn) 59在对 n 个元素进行直接插入排序的过程中，共需要进行（）趟。 A .n B.n+1 C.n-1 D.2n 60对 n 个元素进行直接插入排序时间复杂度为

11、（） A. O(1) B. O(n2) C. O(n) D. O(nlog2n)51-55 C B A D B 56-60 C C D C B61在对 n 个元素进行快速排序的过程中，最好情况下需要进行（）趟。 A. n B. n/2 C. logn D. 2n 62在对 n 个元素进行冒泡排序的过程中，至少需要（）趟完成。 A. 1 B. n C. n-1 D. n/2 63在对 n 个元素进行快速排序的过程中，平均情况下的时间复杂度为（） A. O(1) B. O(logn) C. O(n2) D. O(nlogn) 64排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空） 中

12、的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（） A. 插入排序 B. 起泡排序 C. 希尔排序 D. 选择排序 65用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行 排序时，元素序列的变化情况如下： （1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 则采用的排序方法是（） 。 A. 选择排序 B. 希尔排序 C. 插入排序 D. 快速排序 66对下列四个序列

13、进行快速排序，各以第一个元素为基准进行第一次划分， 则在该次划分过程中需要移动元素次数最多的序列为（） 。 A. 1，3，5，7，9 B. 5，7，9，1，3 C. 5，3，1，7，9 D. 9，7，5，3，1 67若对 n 个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最 小值元素所需要的时间复杂度为（） A. O(1) B. O(logn) C. O(n) D. O(n2) 68若对 n 个元素进行堆排序，则在由初始堆进行每趟排序的过程中，共需要 进行（）次筛运算。 A. n+1 B. n/2 C. n D. n-1 69排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序

14、列（初 始时为空）的一段的方法，称为（） 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序70一组记录的关键字为（45，80，55，40，42，85） ，则利用堆排序的方法建 立的初始堆为（） 。 A. （80，45，55，40，42，85） B. （85，80，55，40，42，45） C. （85，80，55，45，42，40） D. （85，55，80，42，45，40）61-65 C A D A D 66-70 B C D D B71若对 n 个元素进行直接插入排序，则进行第 i 趟排序过程前，有序表中的 元素个数为（） 。 A. 1 B.i-1 C.i D. i+1

15、 72在对 n 个元素进行冒泡排序的过程中，第一趟至多需要进行（）次相邻元 素之间的比较。 A. n+1 B. n/2 C. n D. n-1 73若一个元素序列基本有序，则选用（）排序较快。 A. 堆排序 B. 快速排序 C. 直接插入排序 D. 直接选择排序 74快速排序方法在（）情况下最不利于发挥其长处。 A.要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 75排序方法中，将整个无序序列分割成若干个小的子序列并分别进行插入排 序的方法，称为（） 。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序

16、76用直接插入排序方法对下列 4 个表由小到大进行排序，比较次数最少的是 （） 。 A. （94，32，40，90，80，46，21，69） B. （21，32，46，40，80，69，90，94） C. （32，40，21，46，69，94，90，80） D. （90，69，80，46，21，32，94，40） 77一组记录的关键码为（46，79，56，38，40，84） ，则利用快速排序方法， 以第一个纪录为基准得到的一次划分结果为（） 。 A.（38，40，46，56，79，84） B.（40，38，46，79，56，84） C.（40，38，46，56，79，84） D.（40，38，

17、46，84，56，79） 78如果对元素序列（7，2，5，8，1，11）进行堆排序，并且采用小根堆，则 由初始数据构成的初始堆为（） 。 A.（1，2，5，7，8，11） B.（1，2，5，8，7，11） C.（1，5，2，7，8，11） D.（1，5，2，8，11，7） 79如图所示，该二叉树的前序遍历序列是（） 。 A. EGFACDB B. EAGCFBD C. EACBDGF D. EGACDFB80已知某二叉树的后序遍历序列是 DACBE，中序序列是 DEBAC，则它的前 序遍历序列是（） 。 A. ACBED B. DEABC C. DECAB D. EDBAC71-75 C D

18、C C A 76-80 B C B C D81已知某二叉树的前序遍历序列是 ABDEFGC，中序序列是 DEBGFAC，则 对应的二叉树为（） 。81-85 B 2填空题填空题1数据结构及数据的逻辑结构包括_,_,_,_四种类型。 2数据的存储结构及物理结构包括_,_,_,_四种基本类 型。 3数据结构是研究数据的_，_以及它们之间的相互关系，并对这种结 构定义相应的_，设计出相应的_，而确保经过这些运算后所得到的 新结构是_结构类型。 4一个算法应具有_，_，_，_，_这五个特征。 5一个算法的时间复杂度是该算法包含的_的多少，它是一个算法运行时 间的相对度量，一个算法的空间复杂性是指该算法

19、在运行过程中临时占用的 _的大小。 6一个算法的时间复杂性通常用它的_形式表示，当一个算法的时间复杂 度与问题的规模 n 大小无关时，则表示为_；成正比时，则表示为 _；成对数关系时，则表示为_；成平方时，则表示为_。 7_是描述客观事物的数、字符以及所有能输入到计算机且被计算机程序 加工处理的符号集合。_是数据的基本单位，有时这个单位由若干个_组成，在这种情况下，又称它为记录，_是数据的最小单位，而由 记录组成的线性表为_。 8一种数据结构的元素集合 K 和他的二元关系 R 为： K=a,b,c,d,e,f,g,h R=, 该数据结构具有_结构。 9一种数据结构的元素集合 K 和他的二元关系

20、 R 为： K=a,b,c,d,e,f,g,h R=, 该数据结构具有_结构。 10一种数据结构的元素集合 K 和他的二元关系 R 为： K=1,2,3,4,5,6 R=(1,2), (2,3) ,(2,4), (3,4), (3,5), (3,6), (4,5), (4,6) 该数据结构具有_结构。 1集合、线性结构、树型结构、图形结构（网状结构）集合、线性结构、树型结构、图形结构（网状结构） 2顺序存储、链式存储、散列、索引顺序存储、链式存储、散列、索引 3物理结构、逻辑结构（二者顺序可颠倒）物理结构、逻辑结构（二者顺序可颠倒） 、运算、算法、原来的、运算、算法、原来的 4有穷性、确定性、

21、可行性、输入性、输出性有穷性、确定性、可行性、输入性、输出性 5语句执行次数、存储空间语句执行次数、存储空间 6数量级、数量级、O(1)、O(n)、O(logn)、O(n2) 7数据、数据元素、数据项、数据项、文件数据、数据元素、数据项、数据项、文件 8线性结构线性结构 9树型结构树型结构 10图形结构（网状结构）图形结构（网状结构） 11若经常需要对线性表进行插入和删除运算，则最好采用_存储结构，若 经常需要对线性表进行查找运算，则最好采用_存储结构。 12访问一个线性表中具有给定值元素的时间复杂性的量级为_。 13对于一个长度为 n 的顺序表，在表头插入元素的时间复杂性为_， 在表尾插入元

22、素的时间复杂性为_。 14在一个单链表中指针 p 所指向结点的后面插入一个指针 q 所指向的结点 时，首先把_的值赋给 q-next，然后把_的值赋给 p-next。 15在一个单链表中的 p 所指向结点之前插入一个指针 s 所指向的结点时， 可执行如下操作： （1）s-next=_; (2) p-next= s； (3) t= p-data； (4) p-data=_； (5) s-data=_； 16假定指向单链表中第一个结点的表头指针为 head，则向该单链表的表头插 入指针 p 所指向的新结点时，首先执行_赋值操作，然后执行_赋值操 作。 17在一个单链表中删除指针 p 所指向结点的后

23、继结点时，需要把_的值赋 给 p-next 指针域。 18在一个单链表中删除指针 p 所指向结点时，应执行一下操作：q=p-next;p-data= p-next-data;p-next=_； free(q); 19在_链表中，既可以通过设定一个头指针也可以通过设定一个尾指针来 确定它，即通过头指针或尾指针可以访问到该链表中的每个结点。 20在一个带有头结点的双向循环链表中的 p 所指向的结点之前插入一个指针 s 所指向结点时,可执行如下操作： （1）s-data= element; (2) s -prior=_； (3) p-prior-next=s; (4) s-next=_; (5) p

24、-prior=_; 11链式、顺序链式、顺序 12O(n) 13O(n)、O(1) 14p-next、q 15p-next、s-data、t 16p-next= head、head=p 17p-next-next 18p-next-next 19循环循环 20p-prior、p、s 21在一个双向链表中指针 p 所指向结点之前插入一个新结点时，其时间复杂 性的量级为_。 22 线性表的长度是指_。 23在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的，在线 性表的链式存储中，元素之间的逻辑关系是通过_决定的。 24根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为 _和_。 2

25、5线性表、栈和队列都是_结构，对于栈只能在_插入和删除元 素；对于队列只能在_插入元素，在_删除元素。 26设有一空栈，现有输入序列 1，2，3，4，5，经过 push, push, pop, push ,pop, push ,push 后，对应的输出序列是_。 27设元素 1，2，3，4，5 依次进栈，若要在输出端得到序列 34251，则应进 行的操作序列为 push(S,1),push(S,2), _，pop(S)，push(S,4)，pop(S)， _，_,pop(S)，pop(S)。 28在一个具有 n 个存储单元的循环队列中，当队列满时共有_个元素。 29有一棵树如图所示，回答下列问

26、题： （1）这棵树的根结点是（） ； （2）这棵树的叶子结点是（） （3）结点 C 的度是（） ，这棵树的度是（） （4）结点 C 的子女是（） （5）结点 C 的父结点是（） 30对于一个具有 n 个结点的二叉树，它可能具有的最小深度为_，具有 的最大深度为_。 21O(1) 22线性表中包含数据元素的个数线性表中包含数据元素的个数 23物理存储地址、指针的值物理存储地址、指针的值 24单链表、双链表单链表、双链表 25线性、栈顶、队尾、队头线性、栈顶、队尾、队头 262，3 27push(S,3)、pop(S)、push(S,5) 28n-1 29(1) A (2) B,E,G,D (3)

27、 2,3 (4) E,F (5) A 30log2n+1、n 31一棵深度为 k 的满二叉树的结点总数为_，一棵深度为 k 的完全二叉 树的结点总数的最小值为_，最大值_。 32由 a,b,c 三个结点构成的二叉树，共有_种不同的结构。 33对于一棵具有 n 个结点的树，该树中所有结点的度数之和为_。 34在一棵二叉树中，假定度为 2 的结点数为 5 个，度为 1 的结点数为 6 个， 则叶子结点数为_个。 35假定一棵二叉树顺序存储在一维数组 a 中，但让编号为 1 的结点存入 a0元素中，让编号为 2 的结点存入 a1元素中，其余类推，则编号为 i 结 点的左孩子结点对应的数组下标为_，右

28、孩子对应下标为_。 36一棵 n 个结点的完全二叉树从根结点这一层开始，每一层上的结点按从 左到右的顺序存储于数组 A1.n中，设某个结点在数组中的位置为 i（1in） ，则其父结点的位置是_。 37设二叉树的深度为 h，且只有度为 0 和 2 的结点，则此二叉树中所含结点 数最多为_。 38假定一组记录为（46,79,56,38,40,84） ，在冒泡排序的过程中进行第一趟排 序后的结果为_。 39假定一组记录为（46,79,56,38,40,80） ，对其进行快速排序的过程中，共需 要_趟排序。 40假定一组记录为（46,79,56,38,40,80） ，对其进行快速排序，则第一次划分 后

29、的结果为_。 312k-1、2k-1、2k-1 325 33n-1 346 352i-1、2i 36i/2(取整数部分取整数部分) 372h-1 3846,56,38,40,79,84 3934040,38,46,56,79,80 41对 n 个记录的有序表进行折半查找时，最大的比较次数是_。 42折半查找法的存储结构仅限于_，且是有序的。 43在单链表中，要删除某一指定的结点，必须找到该结点的_。 44线性表的最基本的四种操作分别是插入、删除、查找和_操作。 45循环单链表与非循环单链表的主要不同是循环单链表的尾结点指针 _，而非循环单链表的尾结点指针_。 46访问单链表中的结点，必须沿着_

30、依次进行。 47在双向链表中，每个结点有两个指针域，一个指向_，另一个指向 _。 48在一个双向链表中删除指针 p 所指向的结点时，需要对 p-next-prior 指针 域赋值为_。 49设 head 为单循环链表 L 的头结点，则 L 为空表的条件是_。 50栈又称为_表，队列又称为_表。 41log2n 42顺序存储结构顺序存储结构 43前驱结点前驱结点 44排序排序 45指向链表头结点，指向空指向链表头结点，指向空 46指针域或指针域或 next 域域 47前驱结点，后继结点前驱结点，后继结点 48p-prior 49head-next=head 50后进先出，先进先出后进先出，先进先

31、出 51假设以 S 和 X 分别表示进栈和退栈操作，则对输入序列 a, b, c ,d, e 进行一 系列栈操作 SSXSXSSXXX 之后，得到的输出序列是_。 52在一个用一维数组 an表示的顺序栈中，该栈所含元素的个数最少为 _个，最多为_。 53在一个长度为 n 的顺序表中的删除第 i 个元素（0in-1） ，需要向前移 动_个元素。 54一个数据结构在计算机中的表示（映象）称为_。 55在线性结构和树型结构中，前驱结点和后继结点之间分别存在着_和 _的联系。 51b, c ,e, d, a 520，n-1 53n-i 54数据的存储结构数据的存储结构 55一对一，一对多一对一，一对多 56每次从无序子表中取出一个元素，然后插入到有序子表中的适当位置，此 中排序方法叫做_排序；每次从无序表中挑选出一个最大或者最小元素， 把它交换到有序表的一端，此种方法叫做_排序。 57如图所示，该二叉树的中序遍历序列是_。56插入，选择插入，选择 57A B C D E G F