数据结构考试习题集

《数据结构考试习题集》由会员分享，可在线阅读，更多相关《数据结构考试习题集（9页珍藏版）》请在金锄头文库上搜索。

1、第一章： 时间复杂度： 例如：1.数据元素是数据的基本单位，其中（）数据项A.只能包含一个B.不包括 C.可以包含多个D.可以包括也可以不包括 2.逻辑关系是指数据元素的（） A.关系 B.存储方式 C.结构 D.数据项 3.算法在发生非法操作时可以作出处理的特性称为（） A.正确性 B.易读性 C.高效性 D.健壮性 4.数据的基本单位是_ 5.一个算法应具备_、_、_、_、_5 个特性 6.数据的逻辑结构被分为_、_、_、_四种。 7.计算下列算法的时间复杂度 x = 1; for(i = 1,i next = _; p-next = s; t=p-data; p-data=_; s-da

2、ta=_; 在一个双链表中，在 p 所指向的结点之后插入 q 所指向的结点的操作是？ 在一个双链表中，在*p 结点之前插入*q 结点的操作是？ 在双链表中，删除*p 结点的操作是？ 在双链表中，删除*p 结点之后的一个结点的操作是？(不释放空间) 若某表最常用的操作是在最后一个结点之后插入一个结点或者删除最后一个结点， 在采用_存储方式最节省时间。 A 单链表 B 给出表头指针的循环单链表 C 双链表 D 带头结点的循环双链表 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则 采用_存储方式最节省运算时间。 A 单链表 B 仅有头结点的单循环链表 C 双链表 D 仅有尾

3、结点指针的单循环链表 线性表是具有 n 个（）的有限序列 A.表元素 B.字符 C.数据元素 D.数据项 线性表采用链表存储时，其地址（） A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.连续与否均可以 线性表的顺序存储中，元素之间的逻辑关系是通过_决定的，而在链式存储中，元素之间的逻辑关系是通过_决定的。 向一个长度为 n 的顺序表中的第 i 个元素（1next =NULL C.L-next=L D.L!=NULL 在一个长度为 n（n1）的带头结点的单链表 h 上，另设有尾指针 r（指向最后一个 结点） ，执行（ ）操作时其复杂度与链表的长度有关。 A.删除单链表的第一

4、个元素 B.删除单链表的最后一个元素 C.在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 在单链表中，要删除某一个指定的结点，必须找到该结点的_结点。 在一个单链表中，指针 p 所指结点为最后一个结点的条件是_ 在一个单链表（已知每个结点含有数据域 data 和指针域 next）中删除 p 所指结点 时，应执行如下操作： (1)q=p-next; (2)p-next =_; (3)free(q); 线性表是具有 n 个_的有限序列。 线性表采用链表存储时 ，其元素地址（） A.必须连续B.一定不连续 C.部分必须连续D.连续与否都可以 先行表中每个元素都有一个直接

5、前驱和一个直接后继？（） 带头结点的单链表 head 为空的条件是_。 链表不具备的特点是（） 可随机访问任意结点 插入删除不需要移动元素 不必事先估计存储空间 所需空间与其长度成正比 设线性表有 2n 个元素， （）在单链表上实现要比顺序表实现效率高？ A.删除指定元素 B.在最后一个元素后面插入一个新元素 C.顺序输出前 k 个元素 D.交换第 i 个元素和第 2n-i-1 个元素的值 删除顺序表的_元素，需要移动的元素最多。算法设计算法设计 已知有某带头结点的单链表，其头指针为 head，现在需要寻找表中的元素 20，并 在其后添加一个元素 30，请编写能执行添加的函数，函数的原型如下：

6、NODE* insert(NODE * head ,int x,int y)其中 x 是要寻找的元素,y 是要添加的元素，结构体的定义就借鉴以前的内容。 第三章 请编写程序，让四个字符 ABCD 按照 DCBA 的顺序入栈，但是出栈顺序是 CDAB，应如 何安排他们进栈和出栈 栈是操作受限制的线性表，插入操作和删除操作都必须在表的_进行。 它的元素在栈中的进出遵循_原则。 栈中没有元素，称为_，如果元素个数达到了顺序栈所能容纳的最大值，称为 _。 栈中总是设置一个表示栈顶元素下标的变量，叫做_。 有一个栈，元素 A，B，C，D 只能依次进栈，则出栈序列中以下哪个是不可能得 到的（） A. D、

7、C、B、A B. C、B、A、D C. A、B、C、D D. D、C、A、B 有一单向铁路行驶道， （1）如果进站的车厢序列为 123，则可能得到的出站车厢的序列有哪些可能性。 （2）如果进站的车厢序列为 123456，则能否得到 435612 和 135426 的序列，说明为什么 不能得到或者如何得到。 设 n 个元素进栈序列是 1,2,3.,n，输出序列是 p1,p2,.pn,若 p1=3,则 p2 的值（） A.一定是 2 B.一定是 1 C.不可能是 1 D.以上都不对 有 5 个元素，它们的进栈顺序是 A,B,C,D,E,在可能的出栈顺序中，以元素 CD 最先 出栈的次序有哪几个？

8、判定一个顺序栈 st 为空的条件是（） A.st.top=0; B.st.top!=0; C.st.top!=MAX;D.st.top=MAX; 判定一个顺序栈 st 为栈满的条件是（） ； A.st.top=0; B.st.top!=0; C.st.top!=MAX-1;D.st.top=MAX-1; 将 f=1+1/2+1/3+.+1/n 转化成递归函数，其递归出口（终结条件）是_递归公 式是_。 队列也是操作受到限制的线性表，它只能在表的_插入，这一端称为_在表 的_删除,这一端称为_。 队列中元素在表中的进出遵循_的原则。 顺序队列在多次出队和入队操作之后，会出现一种元素并没有装满，却

9、无法再次入 队的情况，我们称为_现象。 在队列中我们常常设置一个指针 front，指向_的位置，我们称为队首指针， 又设置一个指针 rear,志向_的位置，我们称为_。 循环队列 qu，已满的条件是（） A.（qu.rear+1）%MAX=(qu.front+1)%MAX B. （qu.rear+1）%MAX=qu.front+1 C.（qu.rear+1）%MAX=qu.front D.qu.rear=qu.front 循环队列 qu，已空的条件是（）A.（qu.rear+1）%MAX=(qu.front+1)%MAX B. （qu.rear+1）%MAX=qu.front+1 C.（qu.

10、rear+1）%MAX=qu.front D.qu.rear=qu.front 某循环队列中数组下标是 0n-1，其头指针 front 和 rear 值分别为 f 和 r，则元素的 个数为_。带头结点的链队 qu，对头和队尾指针分别为 front 和 rear，则判断队空的条件是 （） A.qu.front=qu.rearB.qu.front!=NULL C.qu.rear!=NULL D.qu.front=NULL 某链队 qu,目前只有一个元素，要将此元素删除，应当怎么做。 p=qu-front-next; qu-front-next =_; _ = qu-front; free(p);

11、5.在栈中允许插入和删除的一端称为_，另一端称为_。栈的插入操作通常称为_，而 删除操作则称为_。栈中无元素时称为_。 6.已知一个栈的进栈序列是 1234n，其输出序列的第一个元素是 i，则第 j 个出栈元素是 （i-j+1） 。 A.I B.n-I C.j-i+1 D.不确定 7.设 n 个元素进栈序列是 123.n，其输出序列是 p1p2,.pn,则 p33，则 p2 的值（） 。 A. 一定是 2 B.一定是 1 C.不可能是 2 D.不可能是 3 6.顺序栈中元素值的大小是有序的？ 7.N 个元素进栈后，他们的出栈顺序一定和进栈顺序正好相反。 8.栈顶元素和栈底元素可能是同一个元素。

12、 9.判定一个顺序栈 st 为空的条件是（） ； A.st.top=0; B.st.top!=0; C.st.top!=MAX;D.st.top=MAX; 10.判定一个顺序栈 st 为栈满的条件是（） ； A.st.top=0; B.st.top!=0; C.st.top!=MAX-1;D.st.top=MAX-1; C.f(0)=1 D.f(n)=n 第四章 第五章 有如下矩阵，则用三元组法表示应该如何表示？第六章有某树中序序列为 DGBAECF 后序序列为 GDBEFCA，请构造出此二叉树。 给定某树的中序遍历序列为 BDCAEHGKF，后序遍历为：DCBHKGFEA，请画出 树的形态图

13、。某通信系统中可能出现 8 个字符 a,b,c,d,e,f,g,h，出现的频度分别为 (5,29,7,8,14,23,3,11)，为此 8 个字符设计哈夫曼编码。 按照树的定义，具有 3 个结点的二叉树有（）种 A.3B.4 C.5D.6 一个满二叉树，有 n 个结点和 m 个叶子,深度为 h，则 A.n=h+mB.h+m=2n C.m=h-1D.n=2h-1 在一棵完全二叉树中，结点数目为 n，从 1 开始从上到下，从左到右编号，编号最 大的分支结点编号是_。 二叉树有 50 个叶子结点，则二叉树的总结点数目至少有多少个？ 在一非空二叉树的中序编列序列中，根结点的左边（） A.只有右子树上的

14、所有结点 B.只有右子树上的部分结点 C.只有左子树上的所有结点 D.只有左子树上的部分结点 任何一棵二叉树的叶子结点在三种遍历序列中的相对次序（） A.不发生改变B.发生改变 C.不能确定D.以上都不对 一棵二叉树的先序遍历序列为 ABCDEFG，它的中序序列可能是（） A.CABDEFGB.ABCDEFG C.DACEFBGD.ADCFEGB 一棵二叉树的先序序列是 ABCDEF，中序为 CBAEDF，则后序为（） A.CBEFDAB.FEDCBA C.CBEDFAD.不确定 二叉树先序序列和中序序列相同的条件是_。 n 个结点的线索二叉树上含有的线索数目为 A.2nB.n-1 C.n+1

15、D.n 线索二叉树中左线索指向_，右线索指向_. 引入线索二叉树的目的是（） A.加快查找结点前驱和后继的速度 B.为了能在树中方便插入和删除C.为了能方便找到双亲 D.使得二叉树的遍历结果唯一哈夫曼树中，叶子有 n 个，则非叶子结点的个数为（） A.n-1B.n1 C.2nD.n 有 13 个权值，用它们组成一棵哈夫曼树，则该树有（）个结点 A.13B.12 C.26D.25 以4,5,6,7,8作为叶子权值构造哈夫曼树，其带权路径长度为_，各结点对 应的哈夫曼编码为_。 按照树的定义，具有 3 个结点的二叉树有（）种 A.3B. C.D.ABCDE FG得出此森林的先根遍历和后根遍历 第七章