《数据结构》复习题 (含部分参考答案版)
一、
单项选择题
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构
1. 按照数据逻辑结构的不同，可以将数据结构分成 C 。
２. 下列关于数据结构的叙述中正确的是 A 。 A. 数组是同类型值的集合
B． 递归算法的程序结构比迭代算法的程序结构更为复杂
C. 树是一种线性的数据结构
Ｄ. 用一维数组存储二叉树,总是以先序顺序遍历各结点
3． 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为 B A.逻辑结构 B.顺序存储结构 C.链式存储结构 D.以上都不对 4. 以下关于算法特性的描述中， Ｂ 是正确的。
(１）算法至少有一个输入和一个输出 （2）算法至少有一个输出但是可以没有输入 (3）算法可以永远运行下去
A. (１) B. （２) C. （３） Ｄ. （2)和（3) ５. 对顺序存储的线性表（a１,a２,…,aｎ）进行插入操作的时间复杂度是 Ｃ 。
Ａ.O(n) B． O（ｎ-ｉ) C． (ｎ/２) D. Ｏ（n-1）
6. 链表不具有的特点是 Ａ 。
A.可随机访问任一元素 Ｂ.插入和删除时不需要移动元素
C.不必事先估计存储空间 D．所需空间与线性表的长度成正比
7.线性链表中各链结点之间的地址 Ｃ 。
A．必须连续 B.部分地址必须连续 C.不一定连续 D.连续与否无关 ８. 以下关于链式存储结构的叙述中, C 是不正确的。
A.结点除自身信息外还包括指针域,因此存储密度小于顺序存储结构 B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第ｉ个结点的存储地址 D．插入、删除操作方便，不必移动结点
9. 设依次进入一个栈的元素序列为ｄ, a, c, ｂ,得不到出栈的元素序列为 D 。
A. dcba B. ａcdb Ｃ. abcd D. cbｄａ 10． 将新元素插入到链式队列中时,新元素只能插入到 B 。
A． 链头 Ｂ. 链尾 C. 链中 D. 第i个位置,ｉ大于等于１，大于等于表长加１
１１． 设栈Ｓ和队列Ｑ的初始状态为空,元素ｅ1、e２、e3、ｅ4、ｅ5和e6依次通过栈Ｓ,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e2、e４、ｅ３、e6、e5、和e1,则栈Ｓ容量至少应该是 C 。
A. 6 B. 4 C． 3 D. 2 1２.下面 D 是‘ａｂｃd３21ABCD’的子串。
A． abcｄ B. 3２1aｂ C. ‘ａbc ABＣ’ Ｄ． ‘21AB’
13.假设8行10列的二维数组A［1…8，1…1０]分别以行序为主序和以列序为主序顺序存储时,其首地址相同，那么以行序为主序时元素a[3,5］的地址与以列序为主序时 C 元素相同。
A. a[7，3] B. a[8，3］ Ｃ. ａ［1,4] D. ABC都不对
14． 数组A[０…5,0…6］的每个元素占5个字节,将其按列优先次序存储在起始地址为１000的内存单元中,则元素A[5，5]的地址为 A 。
A. 1175 B. 1180 C． １20５ D.
１21０
15.下列广义表中，长度为3的广义表为 B 。
A.（a，b,ｃ，（ )） B. （（g),(a，b,c，ｄ，ｆ），( ）) C. (a，(b,（d))） D. (（( ))）
16. 以下关于广义表的叙述中，正确的是 A 。
A. 广义表是０个或多个单元素或子表组成的有限序列 Ｂ． 广义表至少有一个元素是子表 C. 广义表不可以是自身的子表 D. 广义表不能为空表
1７.若树T有a个度为1的结点，b个度为２的结点，c个度为３的结点,则该树有 Ｄ 个叶结点。
Ａ. 1+2b+3ｃ B. ａ＋2b+3ｃ Ｃ.２ｂ+3ｃ D. 1+ｂ+2c
1８.若一棵二叉树有102片叶子结点，则度二叉树度为２的结点数是 B 。
A． 1０0 B． 101 C. 102 Ｄ． 103
1９． 在有n 个叶子结点的霍夫曼树中，其结点总数为: 。
A. ｎ B. 2n C. ２n +1 D. 2n － 1 20.具有12个结点的完全二叉树有 B 。
A. 5个叶子结点 B. 5个度为２的结点 Ｃ. 7个分支结点 Ｄ. 2个度为１的结点
21．设结点ｘ和ｙ是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中ｘ在ｙ之后,则ｘ和ｙ的关系是 C 。
Ａ. ｘ是y的左兄弟 B. x是y的右兄弟 Ｃ． x是ｙ的祖先 D. x是y的后代 22. 先序遍历序列与中序遍历序列相同的二叉树为 。
A. 根结点无左子树的二叉树 B.根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
２3.若二叉树T的前序遍历序列和中序遍历序列分别是bｄcaeｆ和cdeabf，则其后序遍历序列为 A 。
Ａ. ｃeａdfb B. feacdb Ｃ. ｅacdfｂ Ｄ. 以上都不对
24．设无向图的顶点个数为ｎ，则该图最多有 C 条边。
Ａ. n－1 B. n（n-１） C． n(n－1)/2 D. n
２5.对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是
Ｃ 。
A. e／2 Ｂ． e Ｃ. n+2e Ｄ． ｎ＋ｅ
26. 无向图G=(V,E),其中V=｛a,b,c,d,e,f},E=｛(a,b),(a,e),(a,c）,(ｂ,e），(ｃ，f),（ｆ，d）,（e,d)｝。
对该图进行深度优先遍历，下面不能得到的序列是 D 。
A. ａcfｄeｂ B. ａebdfｃ C． aｅdfcb D. aｂecｄf
2７．在下述排序方法中,不属于内排序方法的是 Ｃ 。
A． 插入排序法 B. 选择排序法 C． 拓扑排序法 D. 归并排序法
２8． 直接插入排序在最好情况下的时间复杂度为 B 。
A. Ｏ(lｏｇ2n) Ｂ. Ｏ(ｎ) Ｃ． Ｏ(nlｏg2n） D. O(n2）
29.对有n个记录的表作快速排序，在最坏情况,算法的时间复杂度是 Ｄ 。
Ａ. O(n3) B. O（ｎ) C． O(nlｏg２n） D. Ｏ(n2)
30.下面的排序算法中，稳定是 Ａ 。
Ａ． 直接插入排序法 B. 快速排序法 C． 直接选择排序法 D． 堆排序法
二、 填空题
１． 一个算法具有5个特性: 、 、 、有零个或多个输入，一个或多个输出。
2. .设数组a[1…5０,1…80]的基地址为２000,每个元素占２个存储单元,若以行序为主序顺序存储，则元素ａ[45,68]的存储地址为 9174 ；若以列序为主序顺序存储,则元素a[45,6８]的存储地址为 8788 。
3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时,应采用 存储结构。
4.两个字符串相等的充分必要条件是 长度相等且对应位置上的字符相等 。 5. 字符串“abcd”中共有 个长度大于0的字串。
6. 广义表liｓt=（5，（3，2,(１４,９，３),（),4)，2,(6,３,１0))的长度及深度分别 为 和 。
７.若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点 。 8．若无向图满足 有n－1条边的连通图 ,则该图是树。
9．若无向图中有n个顶点，则其边数最少为 n-1 ,最多为 n(n-1)／２ 。
10.堆排序的时间复杂度和空间复杂度分别为 O(nｌoｇ2n) 和 O(1) 。
三、 名词解释
(1)抽象数据类型 (２）算法及其特性 （3）串的模式匹配 (4)优先级队列 （５)完全二叉树 （６)堆(7）Hｕffmａn编码（8）Huｆfman树 (9)连通分量及重连通分量（10）最小生成树（11)克鲁斯卡尔算法 (12）普里姆算法(１3)希尔排序（14)快速排序 （1５）教材等等相关名次解释题
四、 简答题
１. 请对线性表进行顺序存储和链式存储的特点作比较。(西电2004年考研试题） 2． 单链表为什么要引入头结点? 3.线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点? 参考答案：
单链表的优点是空间动态分配,插入和删除时不需要移动数据，缺点是不能随机访问数据。和其它两种相比,它还节省了空间。
循环链表除了具有单链表的优点外,它从任意结点出发可以找到其它结点。
缺点同单链表的缺点。
双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前驱。缺点是增加了空间开销。
4．内存中一片连续空间（不妨假设地址从1到m），提供给两个栈使用,怎样分配这部分存储空间，使得对任一个栈,仅当这部分空间全满时才发生上溢。 5. 假设有一个适当大小的栈S,输入栈的序列为Ａ,B,Ｃ，D，Ｅ。
问：(1）能否得到下列的输出序列： ① Ｂ,C,D,E,A； ② Ｅ，A,B,C,Ｄ;
③E，Ｄ,C，Ｂ，A。
(２）写出所有可能正确的输出序列(至少5种)。
6.用向量表示的循环队列的队首和队尾位置分别为1和ｍax＿sizｅ,试给出判断队列为空和为满的边界条件。
参考答案:
队空条件为max_size==1;
队满的条件为（ｍax_ｓｉze＋1)％MAＸＳIZE.
7. 设一棵二叉树后序遍历序列为DGJHEＢIFCA,中序遍历序列为DBGEHJAＣIＦ，要求： （1)画出该二叉树;
(2)写出该二叉树的先序遍历序列；
(3)画出该二叉树对应的森林。
8.对二叉树中的结点按层次顺序（每一层自左向右)进行的访问操作称为二叉树的层次遍历。现已知一棵二叉树的层次序列为ＡEBＧFDIMH，中序遍历序列为GＥFAMDBHI。请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子 — 兄弟表示,请画出该森林。（西电2０0４年考研试题）
9. 已知某通信电文仅由A、B、C、Ｄ、E、Ｆ这6个字符构成,其出现的频率分别为23、5、１4、8、25、7,请给出它们的霍夫曼树及其对应的霍夫曼编码。 10.给定下列图Ｇ用两种不同表示法画出该图的存储结构图。
12A 8 4 E F B 20 C 15 4 12 G 10 D
11. 针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树,画出其逻辑结构。 12.总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、锦标赛排序、堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅助空间复杂度及稳定性。
1３.判断下面的每个结点序列是否表示一个堆,如果不是堆,请把它调整为堆。 （1）1００,９0,８0，60，８5，7５,20,25,1０，70,6５，５0 (２）100,70,５0,20，9０,75,60，25,１0,85,65，80
14．已知一序列(1２，70,３３,65,２４，５６，４8，９2,86,33）,问该序列是否是堆?如果不是,则把它调整为小顶堆。并问把该序列调整为堆共需要多少次元素间的比较？多少次元素间的交换。（西电200５年考研试题)
15.试为下列情况选择合适的排序算法:(西电２０06年考研试题) (1）ｎ=３０,且要求最坏情况下速度最快; （2)n=30，且要求既要快,又要排序稳定； （3)n=200０，要求平均情况下速度最快；
（4）n=2000,要求最坏情况下速度最快，又要节省存储空间。
五、 算法设计题
1. 实现一个算法,完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。 (教材P74页)
2.（a）实现一个函数,完成在带表头结点的双向循环链表中,建立一个包含有值vａｌｕe的新结点并将其插入到当前结点之后。（教材Ｐ９1页)
(b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点,同时让当前指
针指到链表中下一个结点位置。（教材Ｐ9１页)
3.（a)实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。（教材Ｐ107页） （b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。（教材Ｐ１
１7页)
４.对二叉链表,实现一个函数Pａｒｅｎt（＊ＢinTreeNode ｄe ６.熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的算法 7.若以域变量rｅaｒ和lｅnｇtｈ分别指示循环队列中队尾元素的位置和队列中元素的个数。请完成下面的入队列和出队列的算法:（西电2０04年考研试题) ＃define MAXQSIZE 1０0 //最大队列长度 Tyｐｅ stｒuct{ Ｑelemtｙｐe *bａsｅ; //base为队列所在区域的首地址 iｎt lｅｎgｔh； /／队列长度 ｉnt rear； ／/队尾元素位置 ｝ＳqQueue； Stａtｕs EｎQｕeue(SqＱｕｅue &Q, Qelｅmtype e) { if ( ① ) ｒｅtｕrｎ ERＲOR; /／ 队列满,无法插入 Ｑ.rｅar= ② ; /／计算元素ｅ的插入位置 ③ = ｅ; //在队尾加入新的元素 Ｑ.length+＋； /／队列长度加１ retuｒｎ OK; ｝ Statuｓ ＤeＱｕｅue(SqQuｅue &Ｑ， Qelemｔypｅ &e) //删除对头元素,并用e带 回其值 { iｆ ( ④ )ｒｅturn ＥRROR; /／队列满 e=Q．base［ ⑤ ]； //取队头元素 Q.ｌength --; ／/队列长度减1 reｔurｎ ＯK； ｝ 8.请运用快速排序思想,设计递归算法实现求n（ｎ＞1)个不同元素集合中的第i（1≤i≤n） 小元素。（西电２０04年考研试题） 9.阅读下列函数说明及相应代码，在空白处填入相应语句。 (西电2005年考研试题） [函数１］ 函数palｉnddrome(char s[])的功能是:判断字符串ｓ是否为回文字符串,若是,则返回０，否则返回-１。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LＥVAL”不是。 Ｉｎt pａlｉｎdrome (ｃhar s[]) {char *pi, ＊ｐｊ; Ｐi = ｓ; ｐj =ｓ ＋ ｓtrleｎ（s) – 1; /／*strlen（s)函数用于求得串s的串长 Ｗhile（ｐｉ＜pj &＆ ① ){ Ｐi ＋+; ｐi - - ; } if ( ② )ｒetｕrn － 1; elｓe retｕrｎ 0; } ［函数2] 函数ｉｎserｔ_sorｔ(int ａ[],iｎt cｏｕnt)是用直接插入排序法对指定数组的前ｃouｎt个元素从小到大排序。 Vｏｉd ｉnｓeｒｔ_ｓort(int a[], int count） { iｎt i， j， t; for (i＝1;i ⑤ ; } } １０. 假设以数组seｑ[０…m-1］存放循环队列中的元素，同时设变量rear和quelen分别指示循环队列中的队尾元素的位置和内含元素的个数。（西电2006年考研试题) 请给出： (1)给出循环队列的队满条件和队空条件; (2)写出相应的入队列和出队列的算法，并分别分析其时间代价； (３)如果用数组sｅqu[ｍ…ｎ］来存放循环队列中的元素,则（２）中的入队列和出队列的算法中的哪些语句要修改?如何修改？ 因篇幅问题不能全部显示，请点此查看更多更全内容