数据结构(C语言版)考研复习题.doc

《数据结构(C语言版)考研复习题.doc》由会员分享，可在线阅读，更多相关《数据结构(C语言版)考研复习题.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（C语言版）考研复习题第一章 绪论1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1.2 常用的存储表示方法有哪几种? 1.3 算法的时间复杂度仅与问题的规模相关吗?1.4 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大O记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优

2、，哪一个较劣? 函数 大O表示优劣 (1) T1(n)=5n2-3n+60lgn 5n2+O(n) (2) T2(n)=3n2+1000n+3lgn 3n2+O(n) (3) T3(n)=8n2+3lgn 8n2+O(lgn) (4) T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn) 第二章 线性表2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.3 为什么在单循环链表中设置尾指针比设置头指针更好?2.4 下述算法的功能是什么?LinkList Demo(LinkList L) / L

3、 是无头结点单链表ListNode *Q,*P;if(L&L-next)Q=L;L=L-next;P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL;return L;/ Demo2.5设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList. 2.6 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。2.7 写一算法在单链表上实现线性表的ListLength(L)运算。2.8 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。第三章

4、 栈和队列3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。3.2 链栈中为何不设置头结点?3.3 循环队列的优点是什么? 如何判别它的空和满?3.4

5、 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 3.5 指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( !

6、 StackEmpty (&tmp) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x);(3) void Demo2( SeqStack *S, int m) / 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S)if( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i);(4)void Demo3( CirQueue *Q) / 设DataType 为int 型int x; Se

7、qStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3(5) CirQueue Q1, Q2; / 设DataType 为int 型int x, i , n= 0;. / 设Q1已有内容， Q2已初始化过while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+;for (i=0; i=2)的k叉链表表示中，有

8、多少个空指针?6.8 假设二叉树包含的结点数据为1，3，7，12。(1)画出两棵高度最大的二叉树；(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。第七章 图7.1 在图7.23所示的各无向图中：(1)找出所有的简单环。(2)哪些图是连通图?对非连通图给出其连通分量。(3)哪些图是自由树(或森林)?7.2 在图7.24(下图)所示的有向图中： (1) 该图是强连通的吗? 若不是，则给出其强连通分量。(2) 请给出所有的简单路径及有向环。(3) 请给出每个顶点的度，入度和出度。(4) 请给出其邻接表、邻接矩阵及逆邻接表。7.3 假设图的顶点是A,B.，请根据下述的邻接矩阵画出相应

9、的无向图或有向图。 | 0 1 1 0 0 | | 0 1 1 1 | | 0 0 0 1 0 | | 1 0 1 1 | | 0 0 0 1 0 | | 1 1 0 1 | | 1 0 0 0 1 | | 1 1 1 0 | | 0 1 0 1 0 | (a) (b)7.4 假设一棵完全二叉树包括A,B,C.等七个结点，写出其邻接表和邻接矩阵。7.5 对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题? (1) 图中有多少条边? (2)任意两个顶点i和j是否有边相连? (3) 任意一个顶点的度是多少?7.6 n个顶点的连通图至少有几条边?强连通图呢?7.7 DFS和

10、BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?7.8 画出以顶点v1为初始源点遍历图7.25（下图）所示的有向图所得到的DFS 和BFS生成森林。第八章 排序8.1以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。(1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序(5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。8.

11、2 上题的排序方法中，哪些易于在链表(包括各种单、双、循环链表)上实现?8.3 当Rlow.high中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)?8.4 若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好?8.5 若文件初态是反序的，且要求输入稳定，则在直接插入、直接选择、冒泡和快速排序中就选选哪种方法为宜? 8.6 有序数组是堆吗?8.7 高度为h的堆中，最多有多少个元素?最少有多少个元素?在大根堆中，关键字最小的元素可能存放在堆的哪些地方? 8.8 判别下列序列是否为

12、堆(小根堆或大根堆)，若不是，则将其调整为堆：(1) (100,86,73,35,39,42,57,66,21);(2) (12,70,33,65,24,56,48,92,86,33);(3) (103,97,56,38,66,23,42,12,30,52,06,20);(4) (05,56,20,23,40,38,29,61,35,76,28,100). 第九章 查找9.1对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?9.2 若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找不成功，即表中

13、无关键字等于给定值K的记录；(2)查找成功，即表中有关键字等于给定值K的记录。9.3 画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。9.4 为什么有序的单链表不能进行折半查找?9.5 设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。 9.6 将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空

14、的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T,若再将for 插入T中得到的二叉排序树T是否与T相同?最后给出T的先序、中序和后序序列。9.7 对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?9.8 将二叉排序树T的先序序列中的关键字依次插入一空树中，所得和二叉排序树T与T否相同?为什么?第十章 文件10.1 常见的文件组织方式有哪几种?各有何特点? 文件上的操作有哪几种? 如何评价文件组织的效率?10.2 索引文件、散列文件和多关键字文件适合存放在磁带上吗?为什么?10.3 设有一个职工文件，其记录格式为(职工号、姓名、性别、职务

15、、年龄、工资)。其中职工号为关键字，并设该文件有如下五个记录： 地址 职工号 姓名 性别 职务 年龄 工资 A 39 张恒珊 男 程序员 25 3270 B 50 王莉 女 分析员 31 5685 C 10 季迎宾 男 程序员 28 3575 D 75 丁达芬 女 操作员 18 1650 E 27 赵军 男 分析员 33 6280 (1)若该记录为顺序文件，请写出文件的存储结构； (2)若该文件为索引顺序文件，请写出索引表； (3)若该文件为倒排序文件，请写出关于性别的倒排表和关于职务的倒排表。10.4 在上题所述的文件中，对下列检索写出检索条件的表达式，并写出结果记录的职工号。(1)男性职工

16、(2)工资超过平均工资的职工；(3)职务为程序员和分析员的职工；(4)年龄超过25岁的男性程序员或分析员；10.5 B+树和B-树的主要差异是什么？模拟试题一一、单项选择(每题1分，共10分)1. 若广义表K满足head(K)=tail(K),则K为 () A.( ) B.( ( ) ) C. ( () ),( () ) D.( (),(),() )2.若要求尽可能快地对实数数组进行稳定的排序，则应选()A.快速排序 B.堆排序 C.归并排序 D.基数排序3. 请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做多少次关键码比较。（）A.2 B

17、.3 C.4 D.5 4对包含N个元素的散列表进行查找，平均查找长度 （. ）A、为 O(log2N) B、为O(N) C、不直接依赖于N D、上述三者都不是 5.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（） A. 1，3，2，4 B. 2，3，4，1C. 4，3，1，2 D. 3，4，2，1 6 下面关于图的存储的叙述中，哪一个是正确的。 （） A用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无

18、关 D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 7. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()A.前序遍历 B.后序遍历 C.中序遍历 D.层次遍历8.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是()A、小于 B、大于 C、等于、D、不小于9.下面关于B-树和B+树的叙述中，不正确的是 ()A. B-树和B+树都是平衡的多分树 B. B-树和B+树都是可用于文件的索引结构 C. B-树和B+树都能有效地支持顺序检索 D. B-树和B+树都能有效地支持随机检索 10. 给定下列有向图和初始结点V1,按

19、深度优先遍历的结点序列为()A、V1，V2，V4，V5，V3B、V1，V3，V4，V5，V2C、V1，V2，V5，V3，V4D、V1，V2，V3，V4，V5二、填空题 (每小题2分,共20分) 1.从逻辑结构看，线性表是典型的.，树是典型的. 。 2.设有二维数组A0.9,0.19，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A6,6的存储地址为.，按列优顺序存储，元素A6,6的存储地址为.。 3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为.且小于n时，结点I的右兄弟是结点.，否则结点i没有右兄弟。 4.求具有最小带权外部路径长

20、度的扩充二叉树的算法称为.算法。堆排序中建堆的方法称作.。 5.一个串，除自身之外的所有子串都是该串的.。 6、在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为一.,称为.回路。 7、树形选择排序总的时间开销为.。 8、6阶B-树中，每个结点至多包含.个关键码，除根和叶结点外，每个结点至少包含 .个关键码。 9、散列文件是根据文件中关键字的特点设计一种.函数和.方法将记录散列到存储器上的文件。 10、磁带和磁盘中，.适合随机存储，.适合顺序存储。三、简答题(每小题4分，共16分)1.设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中

21、，至少要进行多少次探测? 2. 什么是二叉排序树?什么是二叉平衡树?3.一棵树有度为1的结点n1个，度为2的结点n2个,度为m的结点nm个，问它有多少个叶结点?4. 什么是散列表的装填因子?为什么说当装填因子非常接近1时，线性探查类似于顺序查找?为什么说当装填因子比较小(比如=0.7左右)时，散列查找的平均查找时间为O(1)? 四、应用题：(每题5分，共20分)1.把下面的树变成二叉树。2. 在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、5、1，29，请画出所得到的二叉查找树。3.画出下列网络的最小生成树。 4.假设用于通信的电文仅由A-H八个字母组成，字母在

22、电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这八个字母设计哈夫曼编码。图： 五、算法题(共34分)1.试写一算法写出用二叉链表表示给定二叉树的叶结点总数。 (12分)2.下面给出了冒泡排序算法，请填写算法中的空框，使算法正确。(10分)typedef struct int key； datatype info;/设datatype已经定义 node； void BubbleSort ( node R)/R中元素个数为n个 int i,j; Boolean flag； node X； for(i=1;i=i;j-).(2). if(.(3).)Rj.key flag =TU

23、RE； X=Rj;.(4).;Rj1= X; if(.(5).)return; / 算法结束 3.设一单链表的头指针为head,链表的结点中包含着整数类型的key域，试设计算法将此链表的结点按照key递增次序进行就地排序。 (12分)模拟试题二一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i(1in+1)个位置上插入一

24、个元素，元素的移动次数为( ) A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.6 D.7 5.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位 6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字

25、符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( ) A.P=SCIENCE B.P=STUDY C.S=SCIENCE D.S=STUDY 7.三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A45的存储地址为( ) A.356 B.358 C.360 D.362 8.如右图所示广义表是一种( ) A.线性表 B.纯表 C.结点共享表 D.递归表 9.下列陈述中正确的是( ) A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树

26、中最多只有两棵子树，并且有左右之分 10.n个顶点的有向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 11.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( ) A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b 12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 13.不可能生成右图所示二叉排序树的关键字序列是( ) A.4 5 3 1 2 B.4 2 5 3 1 C

27、.4 5 2 1 3 D.4 2 3 1 5 14.ALV树是一种平衡的二叉排序树，树中任一结点的( ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15.在VSAM文件的控制区间中，记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接 二、填空题(本大题共10小题，每小题2分， 若有两个空格，每个空格1分，共20分) 16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_。 17.在如图所示的链表中，若在指针p所指的结点之后插入数据域值

28、相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_和_。 18.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_。 19.串S=I am a worker的长度是_。 20.假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为_。 21.在n个结点的线索二叉链表中，有_个线索指针。 22.若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为_。 23.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_。 24.

29、由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到_。 25.若要找出所有工资低于1500元，职称是副教授，及所有工资低于2000元，职称是教授的记录，则查询条件是_。 三、解答题(本大题共4小题，每小题5分，共20分) 26.已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4和5。当以带行表的三元组表作存储结构时，其行表RowTab中的值依次为0，0，2，2，3和5。请写出该稀疏矩阵(注：矩阵元素的行列下标均从1开始)。 27.已知树T的先序遍历序列为A

30、BCDEFGHJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。 28.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。 初始堆：_ 第1趟：_ 第2趟：_ 第3趟：_ 29.在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。 四、算法阅读题(本大题共4小题，每小题5分，共20分) 30.以下函数中，h是带头结点的双向循环链表的头指针。 (1)说明程序的功能； (2)当链表中结点数

31、分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。 int f(DListNode *h) DListNode *p,*q; int j=1; p=h-next; q=h-prior; while(p!=q & p-prior!=q) if(p-data=q-data) p=p-next; q=q-prior; else j=0; return j; 31.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。 void algo(Stack *S) int i=0; Queue Q; Stack T; InitQueue(&Q

32、);InitStack(&T); while (!StackEmpty(S) if(i=!i)!=0)Push(&T,Pop(&S); else EnQueue(&Q,Pop(&S); while(!QueueEmpty(Q) Push(&S,DeQueue(&Q); while(!StackEmpty(T) Push(&S,Pop(&T)； 32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下： #define MaxNum 50/图的最大顶点数 #define INFINITY INT_MAX /INT_MAX为最大整数，表示 typedef struct char vexsMax

33、Num;/字符类型的顶点表 int edgesMaxNumMaxMum;/权值为整型的邻接矩阵 int n,e;/图中当前的顶点数和边数 MGraph;/邻接矩阵结构描述 typedef struct node int adjvex;/邻接点域 int weight;/边的权值 struct node *next;/链指针域 EdgeNode;/边表结点结构描述 typedef struct char vertex;/顶点域 EdgeNode * firstedge;/边表头指针 VertexNode ;/顶点表结点结构描述 typedef struct VertexNode adjlistMaxNum;/邻接表 int n,e;/图中当前的顶点数和边数 ALGraph;/邻接表结构描述 下列算法是根据一