四川大学锦城学院数据结构与算法期末复习总结

1、从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等结构、构造型结构 2、以下数据结构中，哪一个是线性结构（ D ）？

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串

3、在下面的程序段中，对x的赋值语句的频度为（ C ）

for (i=1;i<=n;i++)

for (j=1;j<=n;i++)

x=x+1;

A． O(2n) B．O(n) C．O(n2) D．O(log2n)

4、下面关于线性表的叙述中，错误的是哪一个？（ B ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个

元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指

针的单循环链表

6、 静态链表中指针表示的是（ B ）.

A． 内存地址 B．数组下标 C．下一元素地址 D．左、右

孩子地址

7、下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比

B. 线性表在链式存储时，查找第i个元素的时间同i的值无关

C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比

D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

8、 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的

算法的时间复杂度为（ C ）(1<=i<=n+1)。

A. O(0) B. O(1) C. O(n) D. O(n2) 9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。

A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;

10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是

（ B ）

A．head==NULL B．head→next==NULL C．head→next==head

D．head!=NULL

11、 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i

（1<=i<=n）个元素是（ B ）。

A. 不确定 B. n-i+1 C. i D. n-i

12、 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出

栈序列？（ C ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1

5 6

13、 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出

栈排列是( C )。

A．XYZ B. YZX C. ZXY D. ZYX

14、 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m

D．(rear-front)%m

15、 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别

为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分

别为多少？( B )

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

16、下面关于串的的叙述中，哪一个是不正确的？（ B ）

A．串是字符的有限序列 B．空串是由空格构成的串->(空格串是

由空格组成的)

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用

链式存储

17、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法

称为（ C ）

A．求子串 B．联接 C．匹配 D．求串长

18、 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的

值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素

A[5，8]的存储首地址为( B )。30*6＝180

A. BA+141 B. BA+180 C. BA+222 D.

BA+225

19、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算

是（ D ）。

A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail

（L）））)）

20、广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ D ）。

Head(Tail(Head(Tail(Tail(A)))))

A. (g) B. (d) C. c D. d

二、判断题

1、 数据元素是数据的最小单位。( × )

2、算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描

述，则算法实际上就是程序了。( Y )

3、 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( × )

4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。

( × )

5、线性表的特点是每个元素都有一个前驱和一个后继。( × )

6、一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下

标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ × ）

7、所谓取广义表的表尾就是返回广义表中最后一个元素。（ × ）

9．在一棵高度为k的满二叉树中，结点总数为（ C）

A．2k-1 B．2k C．2k-1 D．?log2k?+1

20．由3 个结点可以构造出多少种不同的二叉树？（ D ）

A．2 B．3 C．4 D．5

22．从下列有关树的叙述中,选出5条正确的叙述(共5分) （ CDFHI ）

A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

B．当K≥1时高度为K的二叉树至多有2k-1个结点。

C．用树的前序周游和中序周游可以导出树的后序周游。

D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。

E．将一棵树转换成二叉树后,根结点没有左子树。

F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+1。

G．在二叉树中插入结点,该二叉树便不再是二叉树。

H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。

I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。

J．用一维数组存储二叉树时,总是以前序周游存储结点。

判断题

1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。√

2. 二叉树只能用二叉链表表示。×

3．在二叉树的第i层上至少有2i-1个结点(i>=1) ×

4．度为二的树就是二叉树。×

5. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。√

第十章

选择题

1．下面给出的四种排序法中( D )排序法是不稳定性排序法。

A. 插入 B. 冒泡 C. 二路归并 D. 堆排

序

2．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序 B. 快速排序，堆排序

C. 直接选择排序，归并排序 D. 归并排序，冒泡排序

3．下面的排序算法中，不稳定的是（ CDF ）

A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数

排序 F.堆排序。

4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中

的变化为

（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84

则采用的排序是 (A )。

A. 选择 B. 冒泡 C. 快速 D. 插入

5. 在下面的排序方法中，辅助空间为O（n）的是( D ) 。

A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排

序

6. 下列排序算法中，占用辅助空间最多的是：(A )

A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序

7．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。

A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80

C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40

8．直接插入排序在最好情况下的时间复杂度为（ B ）

A． O(logn) B． O(n) C． O(n*logn) D． O(n2)

9．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ A ）。

A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9}

C． {21,9,17,30,25,23,5} Ｄ． {5,9,17,21,23,25,30}

10．下列四个序列中，哪一个是堆（ C ）。

A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15

C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15

判断

1．内排序要求数据一定要以顺序方式存储。 （ × ）

2．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ × ）

3．直接选择排序算法在最好情况下的时间复杂度为O（N）。（× ）

4．在待排数据基本有序的情况下，快速排序效果最好。（ × ）

5．快速排序总比选择排序快。（√）

填空

1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__比较__和记录的_移动_。

2．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_ Q A C S Q D F X R H M Y ____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是__ F H C D M A Q S R Q Y X ____。

第九章

选择题

1、 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A )

A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2

2. 下面关于二分查找的叙述正确的是 ( D )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储

C. 表必须有序，而且只能从小到大排列

B. 表必须有序且表中数据必须是整型，实型或字符型

D. 表必须有序，且表只能以顺序方式存储

3. 二叉查找树的查找效率与二叉树的( （1）C )有关, 在 (（2）C)时其查找效率最低

(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位

置

(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复

杂。

4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）

A) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C)

（1） A．17 B. 13 C. 16 D. 任意

（2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题

1．Hash表的平均查找长度与处理冲突的方法无关。 ×

2. 若散列表的负载因子α<1，则可避免碰撞的产生。×

3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。× 填空题

1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为__4____.

 

第二篇：数据结构期末复习总结

一、填空题

4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 非线性结构

4. 算法分析的两个主要方面是：

12. 在顺序表中插入，需要移动元素。具体移动的元素个数与 表长和该元素在表中的位置 有关。

13. 线性表中结点的集合是的。

14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。

15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。

16. 在顺序表中访问任意一结点的时间复杂度均为因此，顺序表也称为的数据结构。

17. 顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置 相邻。

18．在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。

19． 在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。

20. 向量、栈和队列都是 结构，可以在向量的 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。

23. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。

24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。

25. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 ；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

26． 由３个结点所构成的二叉树有种形态。 课本P127,128

27. 一棵深度为6的满二叉树有 126-1个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。或总结点数可算，叶子结点数可算，两个相减

28． 一棵具有２５７个结点的完全二叉树，它的深度为（ 注：用? log2(n) ?+1= ? 8.xx ?+1=9

29．设一棵完全二叉树有700个结点，则共有答：最快方法：用叶子数＝[n/2]＝350

30． 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。

答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.

31．在数据的存放无规律而言的线性表中进行检索的最佳方法是。

32. 线性有序表（a1，a2，a3，?，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。即树高

33. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O（log2n）<5次（2）。即第一层第二层第三层的结点数。但具体是多少次，则

不应当按照公式

ASL?n?1m）。因为这是在假设n＝2-1的情况下log2(n?1)来计算（即（21×log221）/20＝4.6次并不正确！n5

推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！

34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

二、判断正误（在正确的说法后面打勾，反之打叉）

（ × ）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（ × ）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。

（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。

（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”

（ × ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（ × ）7. 线性表在物理存储空间中也一定是连续的。

错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。

（ × ）9. 顺序存储方式只能用于存储线性结构。

错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）

（ × ）10. 线性表的逻辑顺序与存储顺序总是一致的。

错，理由同7。链式存储就无需一致。

（ √ ）13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）14. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ × ）15. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

（ √ ）17. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ √ ）18. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（ √ ）21. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （ √ ）23.二叉树中每个结点的两棵子树是有序的。

（ × ）26.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）

（ × ）27.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（ √ ）29.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

三、单项选择题

（ B ）1. 非线性结构是数据元素之间存在一种：

A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系

（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；

A) 存储 B) 物理 C) 逻辑 D) 物理和存储

（ C ）3. 算法分析的目的是：

A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系

C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性

（ B ）17. 判定一个栈ST（最多元素为m0）为空的条件是

Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0

（ B ）22．在表长为ｎ的链表中进行线性查找，它的平均查找长度为

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;

Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

（ C ）24．对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 公式p229 A．3 B．4 C．5 D． 6

相关推荐

专栏推荐