1、计算机应用基础数据结构部分试题及答案1选择题：1.下面程序段的时间复杂度的量级为（）for(i=1;inext= p-next-next B. p=p-next C. p=p-next-next D. next=p27设单链表中指针 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-nextE. f-next=null F. f-next=p28设单链表中指针 p
2、指向结点 ai,指针 f 指向将要插入的新结点 x，则在链表中最后一个结点 an 之后插入时，只要先修改（）后修改（）即可。A. f-next= p B. f-next= p-next C. p-next=f D. p-next= f-nextE. f =null 29在一个单链表中，若要在 p 所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。A. 1 B. 2 C. 3 D.430在一个单链表中，若要在 p 所指向的结点之前插入一个新结点，则此算法的时间复杂性的量级为（）A. O(n) B.O(n/2) C. O(1) D.O(n1/2)21-25 D B A C B 26-
3、30 A (D.A) (B.C) B A31不带头结点的单链表 L 为空的判定条件是（） 。A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL32带头结点的单链表 L 为空的判定条件是（） 。A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL33在一个带有头结点的双向循环链表中，若要在 p 所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A. 2 B. 3 C. 4 D.634在一个带有头结点的双向循环链表中，若要在 p 所指向的结点之后插
4、入一个 q 指针所指向的结点，则需要对 q-next 赋值为（）A. p-prior B. p-next C. p-next-next D. p-prior -prior35对一个具有 n 个元素的线性表，建立其单链表的时间复杂度为（）A. O(n) B.O(1) C. O(n2) D.O(logn)36线性表采用链式存储时，其地址（）A. 必须是连续的B. 一定是不连续的C. 部分地址必须是连续的D. 连续与否均可以37假定利用数组 aN顺序存储一个栈，用 top 表示栈顶指针，top= =-1 表示栈空，并已知栈未满，当元素 x 进栈时所执行的操作为（）A. a-top=x B. atop
5、-=x C. a+top=x D .atop+=x38若已知一个栈的入栈序列是 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= =m040判定一个栈 S（最多元素为 m0）为满的条件是（）A .S. top!=0 B. S. top= =0 C. S. top!=m0-1 D .S. top= =m0-131-35 A B C B A 36-4
6、0 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，142从一个顺序循环队列中删除元素时，首先需要（）A. 前移队首指针 B. 后移队首指针C. 取出队首指针所指位置上的元素 D . 取出队尾指针所指位置上的元素43假定一个顺序循环队列的队首和队尾指针分别用 front 和 rear 表示，则判断队列空的条件为（）A.front+1= =rear B.rear+1= =front C. front= =0 D . front= =rear44假定一个顺序循环队列存储于数组 aN中
7、，其队首和队尾指针分别用 front和 rear 表示，则判断队列满的条件为（）A. （rear-1）%N= =front B. （rear+1 ）%N= =front C. （front-1 ） %N= =rear D . （front+1 ）%N= =rear45树中所有结点的度等于所有结点数加（）A.0 B.1 C.-1 D.246在一棵树中，每个结点最多有（）个前驱结点。A.0 B.1 C.2 D.任意多个47在一棵度为 3 的树中，度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点点数为 2 个，则度为 0 的结点数为（）个。A.3 B.4 C.5 D.64
8、8在一棵二叉树上第 5 层的结点数最多为（）A.16 B.15 C.8 D.3249在一棵具有 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 C.2i+1 D.2i+252设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（）A.2h B.2h-1
9、C.2h+1 D.h+153按照二叉树的定义，具有 3 个结点的二叉树有（）种状态。A.5 B.4 C.3 D.3054若查找每个元素的概率相等，则在长度为 n 的顺序表上查找任意元素的平均查找长度为（）A.n B.n+1 C.（n-1）/2 D.（n+1）/255顺序查找法适合于存储结构为（）的线性表。A.散列存储 B.顺序存储或链接存储C.压缩存储 D.索引存储56对于顺序存储的有序表（5，12，20，26，37，42，46，50，64） ，若采用折半查找，则查找元素 26 的查找长度（）A.2 B.3 C.4 D.557对线性表进行折半查找时，要求线性表必须（）A.以顺序方式存储 B.以
10、链接方式存储 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.2n60对 n 个元素进行直接插入排序时间复杂度为（）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 个元素进行快速排序的过程中，最好情况下需要
11、进行（）趟。A. n B. n/2 C. logn D. 2n62在对 n 个元素进行冒泡排序的过程中，至少需要（）趟完成。A. 1 B. n C. n-1 D. n/263在对 n 个元素进行快速排序的过程中，平均情况下的时间复杂度为（）A. O(1) B. O(logn) C. O(n2) D. O(nlogn)64排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）A. 插入排序 B. 起泡排序 C. 希尔排序 D. 选择排序65用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排
12、序时，元素序列的变化情况如下：（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对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（） 。A. 1，3，5，7，9 B. 5，7，9，1，3 C. 5， 3，1，7，9 D. 9，7，5，3，167若对 n 个元素进行
13、简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（）A. O(1) B. O(logn) C. O(n) D. O(n2)68若对 n 个元素进行堆排序，则在由初始堆进行每趟排序的过程中，共需要进行（）次筛运算。A. n+1 B. n/2 C. n D. n-169排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一段的方法，称为（） 。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序70一组记录的关键字为（45，80，55，40，42，85） ，则利用堆排序的方法建立的初始堆为（） 。A. （80，45，55，40，42，8
14、5） 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+172在对 n 个元素进行冒泡排序的过程中，第一趟至多需要进行（）次相邻元素之间的比较。A. n+1 B. n/2 C. n D. n-173若一个元素序列基本有序，则选用（）排序较快。A. 堆排序 B. 快速排序 C. 直接插入排序 D. 直接选择排序74
15、快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大 B. 要排序的数据中含有多个相同值C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数75排序方法中，将整个无序序列分割成若干个小的子序列并分别进行插入排序的方法，称为（） 。A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序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，
16、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，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如图所示，该二叉
17、树的前序遍历序列是（） 。A. EGFACDB B. EAGCFBD C. EACBDGF D. EGACDFB80已知某二叉树的后序遍历序列是 DACBE，中序序列是 DEBAC，则它的前序遍历序列是（） 。A. ACBED B. DEABC C. DECAB D. EDBAC71-75 C D C C A 76-80 B C B C D81已知某二叉树的前序遍历序列是 ABDEFGC，中序序列是 DEBGFAC，则对应的二叉树为（） 。81-85 B 2填空题1数据结构及数据的逻辑结构包括_,_,_,_四种类型。2数据的存储结构及物理结构包括_,_,_,_四种基本类型。3数据结构是研究数据
18、的_，_以及它们之间的相互关系，并对这种结构定义相应的_，设计出相应的_，而确保经过这些运算后所得到的新结构是_结构类型。4一个算法应具有_，_，_，_，_这五个特征。5一个算法的时间复杂度是该算法包含的_的多少，它是一个算法运行时间的相对度量，一个算法的空间复杂性是指该算法在运行过程中临时占用的_的大小。6一个算法的时间复杂性通常用它的_形式表示，当一个算法的时间复杂度与问题的规模 n 大小无关时，则表示为_；成正比时，则表示为_；成对数关系时，则表示为_；成平方时，则表示为_。7_是描述客观事物的数、字符以及所有能输入到计算机且被计算机程序加工处理的符号集合。_是数据的基本单位，有时这个单
19、位由若干个_组成，在这种情况下，又称它为记录，_是数据的最小单位，而由记录组成的线性表为_。8一种数据结构的元素集合 K 和他的二元关系 R 为：K=a,b,c,d,e,f,g,hR=,该数据结构具有_结构。9一种数据结构的元素集合 K 和他的二元关系 R 为：K=a,b,c,d,e,f,g,hR=,该数据结构具有_结构。10一种数据结构的元素集合 K 和他的二元关系 R 为：K=1,2,3,4,5,6R=(1,2), (2,3) ,(2,4), (3,4), (3,5), (3,6), (4,5), (4,6)该数据结构具有_结构。1集合、线性结构、树型结构、图形结构（网状结构）2顺序存储、
20、链式存储、散列、索引3物理结构、逻辑结构（二者顺序可颠倒） 、运算、算法、原来的4有穷性、确定性、可行性、输入性、输出性5语句执行次数、存储空间6数量级、O(1) 、O(n)、 O(logn)、O(n 2)7数据、数据元素、数据项、数据项、文件8线性结构9树型结构10图形结构（网状结构）11若经常需要对线性表进行插入和删除运算，则最好采用_存储结构，若经常需要对线性表进行查找运算，则最好采用_存储结构。12 访问一个线性表中具有给定值元素的时间复杂性的量级为_。13 对于一个长度为 n 的顺序表，在表头插入元素的时间复杂性为_，在表尾插入元素的时间复杂性为_。14 在一个单链表中指针 p 所指
21、向结点的后面插入一个指针 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 所指向结点的后继结点时，需要把_的值赋给 p-next 指针域。18在一个单链表中删除指针
22、 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-prior=_;11链式、顺序12O(n)13O(n)、O(1)14p-next、q15p-nex
23、t、s-data 、t16p-next= head、head=p17p-next-next18p-next-next19循环20p-prior、p 、s21在一个双向链表中指针 p 所指向结点之前插入一个新结点时，其时间复杂性的量级为_。22 线性表的长度是指_。23在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的，在线性表的链式存储中，元素之间的逻辑关系是通过_决定的。24根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_。25线性表、栈和队列都是_结构，对于栈只能在_插入和删除元素；对于队列只能在_插入元素，在_删除元素。26设有一空栈，现有输入序列 1，2，3，4，
24、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有一棵树如图所示，回答下列问题：（1）这棵树的根结点是（） ；（2）这棵树的叶子结点是（）（3）结点 C 的度是（） ，这棵树的度是 （） （4）结点 C 的子女是（）（5）结点 C 的
25、父结点是（） 30对于一个具有 n 个结点的二叉树，它可能具有的最小深度为_，具有的最大深度为_。21O(1)22线性表中包含数据元素的个数23物理存储地址、指针的值24单链表、双链表25线性、栈顶、队尾、队头262，327push(S,3) 、pop(S)、push(S,5)28n-129(1) A (2) B,E,G,D (3) 2,3 (4) E,F (5) A30log2n+1、n31一棵深度为 k 的满二叉树的结点总数为_，一棵深度为 k 的完全二叉树的结点总数的最小值为_，最大值_。32 由 a,b,c 三个结点构成的二叉树，共有 _种不同的结构。33 对于一棵具有 n 个结点的树
26、，该树中所有结点的度数之和为_。34 在一棵二叉树中，假定度为 2 的结点数为 5 个，度为 1 的结点数为 6 个，则叶子结点数为_个。35 假定一棵二叉树顺序存储在一维数组 a 中，但让编号为 1 的结点存入a0元素中，让编号为 2 的结点存入 a1元素中，其余类推，则编号为 i 结点的左孩子结点对应的数组下标为_，右孩子对应下标为_。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） ，对其进行快速排序，则第一次划分后的结果为_。312k-1、2k-1、2k-132533n-1346352i-1、2i36i/2(取整数部分)372 h-13846,56,38,40,79,84393
