数据结构复习题目和答案.docx

1、数据结构复习题目和答案数据结构-C语言版第一章 绪论单项选择题1在数据结构中，数据的基本单位是_ _。A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2数据结构中数据元素之间的逻辑关系被称为_ _。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3在数据结构中，与所使用计算机无关的是数据的_ _。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 4在链式存储结构中，数据之间的关系是通过_ _体现的。A. 数据在内存的相对位置 B. 指示数据元素的指针C. 数据的存储地址 D. 指针5计算算法的时间复杂度是属于一种_ _。A

2、. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法6在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_ _。 A. n2 B. nlogn C. n D. logn 7设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_ _。A. O(1) B. O(n) C. O(200n) D. O(nlog2n)CDCBBDD第二章 线性表单项选择题1链表不具有的特点是_ _。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素C. 不必事先估计存储空间 D. 所需空间与线性

3、表的长度正比 2设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为 。A. 139 B. 140 C. 147 D. 1483在线性链表存储结构下，插入操作算法 。A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4在一个单链表中，若删除p所指结点的后继结点，则执行 。 A. p-next = p-next-next; B. p-next = p-next; C. p = p-next-next; D. p = p-next; p-next = p-next-next; 5将长度为n的单链

4、表接在长度为m的单链表之后的算法时间复杂度为 。 A. O(n) B. O(1) C. O(m) D. O(m+n)6需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是 。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB填空题1在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_结点。2在单链表中，指针p所指结点为最后一个结点的条件是 。3将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。 4在一个长度为n的顺序表中第i个元素（1in）之前插入一个元素时，需向后移动元素的个数是 。5在长度为n的顺序表中插入一个元素的时间复

5、杂度为 。1前驱 2 p-next=NULL3.14.n-i+15.O(n)例题解析【例2-1】 编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。 解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下： void inverse(Lnode *h) s=h-next; if(s=NULL) return; q=NULL; p=s; while(p!=NULL) p=p-next; s-next=q; /*逆转指针*/ q=s; /*指针前移*/ s=p; h-nex

6、t=q; /*头指针h的后继是p*/【例2-2】 编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到 C中的元素c为 例如：A=(3,5,8,11) B=(2,6,8,9,11,1

7、5,20)则 C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下：Lnode *hb(Lnode *pa,Lnode *pb)Lnode *p,*q,*pc; pc=(Lnode*)malloc(sizeof(Lnode); /*建立表c 的头结点pc*/ p=pc; /*p指向C表头结点*/ while(pa!=NULL&pb!=NULL) q=(Lnode*)malloc(sizeof(Lnode); /*建立新结点q*/ if(pb-datadata) /*比较A、B表中当前结点的数据域值的大小*/ q-data=pb-data; /*B中结点值小，将其值赋

8、给q的数据域*/ pb=pb-next; /*B中指针pb后移*/ else q-data=pa-data; /*相反，将A结点值赋给q的数据域*/ pa=pa-next; /*A中指针pa后移*/ p-next=q; /*将q接在p的后面*/p=q; /*p始终指向C表当前尾结点*/while(pa!=NULL) /*若表A比B长，将A余下的结点链在C表尾*/ q=(Lnode*)malloc(sizeof(Lnode); q-data=pa-data; pa=pa-next; p-next=q; p=q; while(pb!=NULL) /*若表B比A长，将B余下的结点链在C表尾*/ q=

9、(Lnode*)malloc(sizeof(Lnode); q-data=pb-data; pb=pb-next; p-next=q; p=q; p-next=NULL;p=pc; /*p指向表C的头结点pc*/pc=p-next; /*改变指针状态，使pc指向p的后继*/free(p); /*释放p空间*/return (pc); 此算法的时间复杂度为O(m+n)，其中m，n分别是两个被合并表的表长。第三章栈和队列单项选择题1在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是 。 A. B.C. D. 2若某堆栈的输入序列是1，2，3，.，n，输

10、出序列的第一个元素为n，则第i个输出元素为 。A. i B. n-i C. n-i+1 D. 哪个元素无所谓3向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行 。 A. h-next = s; B. s-next = h; C. s-next = h; h = h-next; D. s-next = h-next; h-next=s; 4一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是 。 A. edcba B. decba C. dceab D. abcde5栈和队列的共同点是 。A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D.

11、 没有共同点6对于循环队列 。A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是7. 若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 。A. 1和5 B. 2和4 C. 4和2 D. 5和18. 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是 。A. QU-front=QU-rear B. QU-front!=QU-rearC. QU-front=(QU-rear+1) % m0 D. QU-front!=(QU-

12、rear+1) % m0 9.判定一个循环队列 QU（最多元素为 m0）为空的条件是 。A. QU-front=QU-rear B. QU-front!=QU-rear C. QU-front=(QU-rear+1) % m0 D. QU-front!=(QU-rear+1) % m0 BCDCCDACA填空题1在求表达式值的算符优先算法中使用的主要数据结构是 。2设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是 。3仅允许在同一端进行插入和删除的线性表称为 。7在顺序栈s中，栈为空的条件是 ，栈为满的条件

13、是_。4用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为 。5用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是 。1.栈2. 2 3 43.栈4.s.top=s.base, s.top-s.base=s.stacksize SXSSXSXX5.993例题解析【例3-1】 编程实现：用除法把十进制数转换成二进制数。 解：算法思想：用初始十进制数除以2把余数记录下来并且若商不为0则再用商去除以2直到商为0，这时把所有的余数按出现的逆序排列起来（先出现的余数

14、排在后面，后出现的余数排在前面）就得到了相应的二进制数，如把十进制数35转换成二进制数的过程如图3-1所示。 图3-1 十进制数转换成二进制数的过程由题意可知，我们可以用一个栈来保存所有的余数，当商为0时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下：void conversion()Stack S; int n; InitStack(&S); printf(Input a number to convert:n);scanf(%d,&n); if(n0）个结点的满二叉树共有 个叶子和 个非终端结点。 答： 2 4. 具有n个结点的完全二叉树的深度为 。5. 哈夫曼树是带权路径

15、度_的树，通常权值较大的结点离根_。最短 较近6在_遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。1.答： k1 k2 k5 k7 k4 2 3 4 k5，k6 k12. 3. 4.floor(log2n)+15. 6. 先根例题解析【例6-1】由如图 6-1 所示的二叉树，回答以下问题。 （1）其中序遍历序列为 ； （2）其前序遍历序列为 ； （3）其后序遍历序列为 ； （4）该二叉树的中序线索二叉树为 ； （5）该二叉树的后序线索二叉树为 ； （6）该二叉树对应的森林是 。图6-1 1棵二叉树解： 中序遍历序列为dgbaechif 前序遍历序列为abdgcefhi

16、 后序遍历序列为gdbeihfca 该二叉树的中序线索二叉树如图 6.1.1(a)所示 该二叉树的后序线索二叉树如图6-1-1 (b)所示 该二叉树对应的森林如图6-1-2所示图6-1-1 二叉树的中序线索二叉树和后序线索二叉树图6-1-2 二叉树对应的森林1二叉树结点数值采用顺序存储结构，如表6-2所示。表6-2 二叉树的顺序存储结构1234567891011121314151617181920eafdgcjhib（1）画出二叉树表示； （2）写出前序遍历，中序遍历和后序遍历的结果； （3）写出结点值 c 的父结点，其左、右孩子。解： （1）该二叉树如图 6-9 所示。图 6-9 1棵二叉树

17、（2）本题二叉树的各种遍历结果如下： 前序遍历：eadcbjfghi 中序遍历：abcdjefhgi 后序遍历：bcjdahigfa （3）c 的父结点为 d，左孩子为 j，没有右孩子。 2有一份电文中共使用 5 个字符：a、b、c、d、e，它们的出现频率依次为 4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。 解：依题意，本题对应的哈夫曼树如图 6-15 所示。各字符对应的哈夫曼编码如下： a：001 b：10 c：01 d：000 e：11图6-15 一棵哈夫曼树3设给定权集 w=2，3，4，7，8，9，试构造

18、关于 w 的一棵哈夫曼树，并求其加权路径长度 WPL。 解：本题的哈夫曼树如图 6-16 所示。图6-16 一棵哈夫曼树其加权路径长度 WPL=72+82+43+24+34+92=80 4. 已知一棵二叉树的中序序列为 cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。解：由后序序列的最后一个结点 a 可推出该二叉树的树根为 a，由中序序列可推出 a的左子树由 cbed 组成，右子树由 hgijf 组成，又由 cbed 在后序序列中的顺序可推出该子树的根结点为 b，其左子树只有一个结点 c，右子树由 ed 组成，显然这里的 e 是根结点，其右子树为结点 d，这样可得到根结点 a 的左子树的先序序列为：bcde；再依次推出右子树的先序序列为：fghij。因此该二叉树如图 6-17所示。图 6-17 二叉树设二叉树的先序线索链表如图 6-18所示。图 6-18 二叉树的先序线索链表第7章 图单项选择题1在一个图中，所有顶点的度数之和等于所有边数的 倍。A. 1/2 B. 1 C. 2 D. 4 2在一个有向图中，所有顶点的入度之和等于所有顶点